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

Yaxiong Liu, Ken-ichiro Moridomi, Kohei Hatano and Eiji Takimoto
Additional contact information
Yaxiong Liu: Department of Informatics, Kyushu University, Fukuoka 819-0395, Japan
Ken-ichiro Moridomi: SMN Corporation, Tokyo 141-0032, Japan
Kohei Hatano: Department of Informatics, Kyushu University, Fukuoka 819-0395, Japan
Eiji Takimoto: Department of Informatics, Kyushu University, Fukuoka 819-0395, Japan

Mathematics, 2022, vol. 10, issue 7, 1-22

Abstract: We consider a variant of the online semi-definite programming problem (OSDP). Specifically, 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 problems. 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.

Keywords: online semi-definite programming; log-determinant; sparse loss matrix; side information; online binary matrix completion (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/7/1055/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/7/1055/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:7:p:1055-:d:779510

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().