Parcimonie et grande dimension

Sparsity and convexity are ubiquitous notions in Machine Learning and Statistics. In this course, we study the mathematical foundations of some powerful methods based on convex relaxation: L1-regularisation techniques in Statistics and Signal Processing; Nuclear Norm minimization in Matrix Completion. These approaches turned to be Semi-Definite representable (SDP) and hence tractable in practice. The theoretical part of the course will focus on the guarantees of these algorithms under the sparsity assumption. The practical part of this course will present the standard solvers of these learning problems.

I. Introduction

• Présentation du cours et des objectifs
• Rappels de mathématiques utiles pour le cours

II. Parcimonie et convexité en apprentissage automatique et statistiques

• Introduction aux notions de parcimonie et de convexité
• Application de ces notions en apprentissage automatique et en statistiques

III. Régularisation L1 en statistiques et traitement du signal

• Présentation des techniques de régularisation L1
• Méthodes de résolution de problèmes d'optimisation sous contraintes de parcimonie

IV. Minimisation de la norme nucléaire dans la complétion de matrices

• Introduction à la complétion de matrices
• Présentation de la minimisation de la norme nucléaire pour résoudre des problèmes de complétion de matrices

V. Représentabilité semi-définie et relaxation convexe

• Introduction à la représentabilité semi-définie (SDP)
• Application de la SDP pour la traçabilité des méthodes basées sur la relaxation convexe

VI. Garanties des algorithmes sous l'hypothèse de parcimonie

• Évaluation des garanties des algorithmes d'apprentissage automatique sous l'hypothèse de parcimonie

VII. Solveurs standard pour les problèmes d'apprentissage automatique basés sur la régularisation L1 et la minimisation de la norme nucléaire

• Présentation des solveurs standard pour résoudre les problèmes d'apprentissage automatique basés sur la régularisation L1 et la minimisation de la norme nucléaire

VIII. Conclusion et applications pratiques

• Récapitulation des notions vues dans le cours
• Applications pratiques des méthodes et algorithmes étudiés dans le cours