An online semi-definite programming with a generalised log-determinant regularizer and its applications

Yaxiong Liu, Ken-ichiro Moridomi, Kohei Hatano, Eiji Takimoto
Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:1113-1128, 2021.

Abstract

We consider a variant of the online semi-definite programming problem: The decision space consists of positive semi-definite matrices with bounded diagonal entries and bounded $\Gamma$-trace norm, which is a generalization of the trace norm defined by a positive definite matrix $\Gamma$. To solve this problem, we propose a follow-the-regularized-leader algorithm with a novel regularizer, which is a generalisation of the log-determinant function parameterized by the matrix $\Gamma$. Then we apply our algorithm to online binary matrix completion (OBMC) with side information and online similarity prediction with side information, and improve mistake bounds by logarithmic factors. In particular, for OBMC our mistake bound is optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v157-liu21e, title = {An online semi-definite programming with a generalised log-determinant regularizer and its applications}, author = {Liu, Yaxiong and Moridomi, Ken-ichiro and Hatano, Kohei and Takimoto, Eiji}, booktitle = {Proceedings of The 13th Asian Conference on Machine Learning}, pages = {1113--1128}, year = {2021}, editor = {Balasubramanian, Vineeth N. and Tsang, Ivor}, volume = {157}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v157/liu21e/liu21e.pdf}, url = {https://proceedings.mlr.press/v157/liu21e.html}, abstract = {We consider a variant of the online semi-definite programming problem: The decision space consists of positive semi-definite matrices with bounded diagonal entries and bounded $\Gamma$-trace norm, which is a generalization of the trace norm defined by a positive definite matrix $\Gamma$. To solve this problem, we propose a follow-the-regularized-leader algorithm with a novel regularizer, which is a generalisation of the log-determinant function parameterized by the matrix $\Gamma$. Then we apply our algorithm to online binary matrix completion (OBMC) with side information and online similarity prediction with side information, and improve mistake bounds by logarithmic factors. In particular, for OBMC our mistake bound is optimal.} }
Endnote
%0 Conference Paper %T An online semi-definite programming with a generalised log-determinant regularizer and its applications %A Yaxiong Liu %A Ken-ichiro Moridomi %A Kohei Hatano %A Eiji Takimoto %B Proceedings of The 13th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Vineeth N. Balasubramanian %E Ivor Tsang %F pmlr-v157-liu21e %I PMLR %P 1113--1128 %U https://proceedings.mlr.press/v157/liu21e.html %V 157 %X We consider a variant of the online semi-definite programming problem: The decision space consists of positive semi-definite matrices with bounded diagonal entries and bounded $\Gamma$-trace norm, which is a generalization of the trace norm defined by a positive definite matrix $\Gamma$. To solve this problem, we propose a follow-the-regularized-leader algorithm with a novel regularizer, which is a generalisation of the log-determinant function parameterized by the matrix $\Gamma$. Then we apply our algorithm to online binary matrix completion (OBMC) with side information and online similarity prediction with side information, and improve mistake bounds by logarithmic factors. In particular, for OBMC our mistake bound is optimal.
APA
Liu, Y., Moridomi, K., Hatano, K. & Takimoto, E.. (2021). An online semi-definite programming with a generalised log-determinant regularizer and its applications. Proceedings of The 13th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 157:1113-1128 Available from https://proceedings.mlr.press/v157/liu21e.html.

Related Material