Generalization Analysis of Deep Non-linear Matrix Completion

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00381149" target="_blank" >RIV/68407700:21240/24:00381149 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Generalization Analysis of Deep Non-linear Matrix Completion

Popis výsledku v původním jazyce

We provide generalization bounds for matrix completion with Schatten ???? quasi-norm constraints, which is equivalent to deep matrix factorization with Frobenius constraints. In the uniform sampling regime, the sample complexity scales like ????˜(????????) where ???? is the size of the matrix and ???? is a constraint of the same order as the ground truth rank in the isotropic case. In the distribution-free setting, the bounds scale as ????˜(????1-????2????1+????2), which reduces to the familiar ????root ????32 for ????=1 . Furthermore, we provide an analogue of the weighted trace norm for this setting which brings the sample complexity down to ????˜(????????) in all cases. We then present a non-linear model, Functionally Rescaled Matrix Completion (FRMC) which applies a single trainable function from ℝ->ℝ to each entry of a latent matrix, and prove that this adds only negligible terms of the overall sample complexity, whilst experiments demonstrate that this simple model improvement already leads to significant gains on real data. We also provide extensions of our results to various neural architectures, thereby providing the first comprehensive uniform convergence PAC analysis of neural network matrix completion.

Název v anglickém jazyce

Generalization Analysis of Deep Non-linear Matrix Completion

Popis výsledku anglicky

We provide generalization bounds for matrix completion with Schatten ???? quasi-norm constraints, which is equivalent to deep matrix factorization with Frobenius constraints. In the uniform sampling regime, the sample complexity scales like ????˜(????????) where ???? is the size of the matrix and ???? is a constraint of the same order as the ground truth rank in the isotropic case. In the distribution-free setting, the bounds scale as ????˜(????1-????2????1+????2), which reduces to the familiar ????root ????32 for ????=1 . Furthermore, we provide an analogue of the weighted trace norm for this setting which brings the sample complexity down to ????˜(????????) in all cases. We then present a non-linear model, Functionally Rescaled Matrix Completion (FRMC) which applies a single trainable function from ℝ->ℝ to each entry of a latent matrix, and prove that this adds only negligible terms of the overall sample complexity, whilst experiments demonstrate that this simple model improvement already leads to significant gains on real data. We also provide extensions of our results to various neural architectures, thereby providing the first comprehensive uniform convergence PAC analysis of neural network matrix completion.

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í

2024

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 Machine Learning Research

ISBN

—

ISSN

2640-3498

e-ISSN

2640-3498

Počet stran výsledku

71

Strana od-do

26290-26360

Název nakladatele

Proceedings of Machine Learning Research

Místo vydání

—

Místo konání akce

Vienna

Datum konání akce

21. 7. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

—