Generalization Bounds for Inductive Matrix Completion in Low-noise Settings
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00369584" target="_blank" >RIV/68407700:21240/23:00369584 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1609/aaai.v37i7.26018" target="_blank" >https://doi.org/10.1609/aaai.v37i7.26018</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1609/aaai.v37i7.26018" target="_blank" >10.1609/aaai.v37i7.26018</a>
Alternative languages
Result language
angličtina
Original language name
Generalization Bounds for Inductive Matrix Completion in Low-noise Settings
Original language description
We study inductive matrix completion (matrix completion with side information) under an i.i.d. subgaussian noise assumption at a low noise regime, with uniform sampling of the entries. We obtain for the first time generalization bounds with the following three properties: (1) they scale like the standard deviation of the noise and in particular approach zero in the exact recovery case; (2) even in the presence of noise, they converge to zero when the sample size approaches infinity; and (3) for a fixed dimension of the side information, they only have a logarithmic dependence on the size of the matrix. Differently from many works in approximate recovery, we present results both for bounded Lipschitz losses and for the absolute loss, with the latter relying on Talagrand-type inequalities. The proofs create a bridge between two approaches to the theoretical analysis of matrix completion, since they consist in a combination of techniques from both the exact recovery literature and the approximate recovery literature.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 37th AAAI Conference on Artificial Intelligence
ISBN
978-1-57735-880-0
ISSN
2159-5399
e-ISSN
2374-3468
Number of pages
9
Pages from-to
8447-8455
Publisher name
AAAI Press
Place of publication
Menlo Park
Event location
Washington, DC
Event date
Feb 7, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—