Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 37th AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-880-0

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

9

Strana od-do

8447-8455

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

Washington, DC

Datum konání akce

7. 2. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—