論文

査読有り
2018年6月1日

Online linear optimization with the log-determinant regularizer

IEICE Transactions on Information and Systems
  • Ken-ichiro Moridomi
  • ,
  • Kohei Hatano
  • ,
  • Eiji Takimoto

E101D
6
開始ページ
1511
終了ページ
1520
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1587/transinf.2017EDP7317
出版者・発行元
Institute of Electronics, Information and Communication, Engineers, IEICE

SUMMARY We consider online linear optimization over symmetric positive semi-definite matrices, which has various applications including the online collaborative filtering. The problem is formulated as a repeated game between the algorithm and the adversary, where in each round t the algorithm and the adversary choose matrices Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. The goal of the algorithm is to minimize the cumulative loss. We can employ a standard framework called Follow the Regularized Leader (FTRL) for designing algorithms, where we need to choose an appropriate regularization function to obtain a good performance guarantee. We show that the log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt are all sparse. Using this property, we show that our algorithm achieves an optimal performance guarantee for the online collaborative filtering. The technical contribution of the paper is to develop a new technique of deriving performance bounds by exploiting the property of strong convexity of the log-determinant with respect to the loss matrices, while in the previous analysis the strong convexity is defined with respect to a norm. Intuitively, skipping the norm analysis results in the improved bound. Moreover, we apply our method to online linear optimization over vectors and show that the FTRL with the Burg entropy regularizer, which is the analogue of the lo -determinant re ularizer in the vector case works well.

リンク情報
DOI
https://doi.org/10.1587/transinf.2017EDP7317
DBLP
https://dblp.uni-trier.de/rec/journals/ieicet/MoridomiHT18
URL
http://dblp.uni-trier.de/db/journals/ieicet/ieicet101d.html#journals/ieicet/MoridomiHT18
ID情報
  • DOI : 10.1587/transinf.2017EDP7317
  • ISSN : 1745-1361
  • ISSN : 0916-8532
  • DBLP ID : journals/ieicet/MoridomiHT18
  • SCOPUS ID : 85048018774

エクスポート
BibTeX RIS