Matrix completion : statistical and computational aspects - Archive ouverte HAL Access content directly
Theses Year : 2016

Matrix completion : statistical and computational aspects

Complétion de matrice : aspects statistiques et computationnels

(1)
1

Abstract

This thesis deals with the low rank matrix completion methods and focuses on some related problems, of both statistical and algorithmic nature. The first part of this work extends the existing statistical guarantees obained for sub-Gaussian additive noise models, to more general distributions. In particular,we provide upper bounds on the prediction error of trace norm penalized estimatorwith high probability for multinomial distributions and for distributions belonging to the exponential family. For the latter, we prove that the trace norm penalized estimators are minimax optimal up to a logarithmic factor by giving a lower bound.The second part of this work focuses on the conditionnal gradient algorithm, which is used in particular to compute previous estimators. We consider the stochastic optimization framework and gives the convergence rate of twovariants of the conditional gradient algorithm. We gives the conditions under which these algorithms match the performance of projected gradient algorithms.
Dans cette thèse nous nous intéressons aux méthodes de complétion de matrices de faible rang et étudions certains problèmes reliés. Un premier ensemble de résultats visent à étendre les garanties statistiques existantes pour les modèles de complétion avec bruit additif sous-gaussiens à des distributions plus générales. Nous considérons en particulier les distributions multinationales et les distributions appartenant à la famille exponentielle. Pour ces dernières, nous prouvons l'optimalité (au sens minimax) à un facteur logarithmique près des estimateurs à pénalité norme trace. Un second ensemble de résultats concernent l'algorithme du gradient conditionnel qui est notamment utilisé pour calculer les estimateurs précédents. Nous considérons en particulier deux algorithmes de type gradient conditionnel dans le cadre de l'optimisation stochastique. Nous donnons les conditions sous lesquelles ces algorithmes atteignent les performance des algorithmes de type gradient projeté.
Fichier principal
Vignette du fichier
73645LAFOND2016archivage.pdf (3.19 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-01529861 , version 1 (31-05-2017)

Identifiers

  • HAL Id : tel-01529861 , version 1

Cite

Jean Lafond. Complétion de matrice : aspects statistiques et computationnels. Statistiques [math.ST]. Université Paris Saclay (COmUE), 2016. Français. ⟨NNT : 2016SACLT002⟩. ⟨tel-01529861⟩
440 View
330 Download

Share

Gmail Facebook Twitter LinkedIn More