An Online Semi-Definite Programming with a Generalized Log-Determinant Regularizer and Its Applications

Yaxiong Liu, Ken Ichiro Moridomi, Kohei Hatano, Eiji Takimoto

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We consider a variant of the online semi-definite programming problem (OSDP). Specif-ically, in our problem, the setting of the decision space is a set of positive semi-definite matrices constrained by two norms in parallel: the L norm to the diagonal entries and the Γ-trace norm, which is a generalized trace norm with a positive definite matrix Γ. Our setting recovers the original one when Γ is an identity matrix. To solve this problem, we design a follow-the-regularized-leader algorithm with a Γ-dependent regularizer, which also generalizes the log-determinant function. Next, we focus on online binary matrix completion (OBMC) with side information and online similarity prediction with side information. By reducing to the OSDP framework and applying our proposed algorithm, we remove the logarithmic factors in the previous mistake bound of the above two prob-lems. In particular, for OBMC, our bound is optimal. Furthermore, our result implies a better offline generalization bound for the algorithm, which is similar to those of SVMs with the best kernel, if the side information is involved in advance.

Original languageEnglish
Article number1055
JournalMathematics
Volume10
Issue number7
DOIs
Publication statusPublished - Apr 1 2022

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Engineering (miscellaneous)
  • General Mathematics

Fingerprint

Dive into the research topics of 'An Online Semi-Definite Programming with a Generalized Log-Determinant Regularizer and Its Applications'. Together they form a unique fingerprint.

Cite this