Modelling functions with kernels: from logistic regression to global optimisation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Thèse Année : 2022

Modelling functions with kernels: from logistic regression to global optimisation

De la régression logistique à l'optimisation globale, modéliser des fonctions avec des noyaux

Résumé

In this thesis at the boundary between statistical learning, optimization and modelling, we study different non-parametric models for functions based on reproducing kernel Hilbert spaces. We first study the expected risk minimization problem through the solving of the regularized empirical risk minimization problem on a reproducing kernel Hilbert space. We extend the precise bias-variance trade offs known for least squares regression to a broader class of functions by controlling the evolution of their Hessians. This class of functions, called generalized self-concordant functions, includes the logistic loss, which is widely used for classification. We also extend the fast rates and fast algorithms known for least squares to this class of functions, characterizing the difficulty of a problem through interpretable quantities. We then introduce a model for non-negative functions, which is linearly parametrized by a symmetric operator and which enforces non-negativity through a positive semidefinite constraint on this operator. We study the properties of this model and show that it has good approximation properties, preserves the convexity of machine learning loss functions, and is integrable in closed form in certain cases. In particular, this last property allows us to use this model to approximate probability densities, and we develop a sampling algorithm based on these models to sample from an arbitrary probability density known via function evaluations. Finally, we apply this model for non-negative functions in order to approximate the global minimum of a function with certain regularity properties. In the same spirit as moment-SOS hierarchies for polynomial optimization, we look for the global minimum as the maximum lower bound of the function, and refine our approximation guarantees from the previous paragraph in order to obtain a near optimal algorithm to solve global optimization given a fixed number of function evaluations. We also pave the way to generalize this approach to functions defined on manifolds, by introducing a second order sufficient condition for a non-negative regular function to be decomposable as sums of squares of regular functions.
Cette thèse se situe à l'interaction entre les domaines de l'apprentissage statistique, de l'optimisation, et de la modélisation. Nous étudions différents modèles de fonctions, fondés sur les espaces de Hilbert à noyau reproduisant. Nous commençons par étudier les propriétés statistiques et algorithmiques de l'estimateur de minimisation du risque empirique régularisé, dans le cadre de la minimisation du risque (en espérance) sur des espaces à noyau reproduisant. Nous généralisons la décomposition biais-variance très précise bien connue dans le cadre de la régression linéaire à une plus grande classe de fonctions en contrôlant précisément l'évolution locale de leurs Hessiennes. Cette classe de fonctions appelées fonctions auto-concordante généralisées contient la perte logistique, qui est très utilisée en classification. Nous étendons également les taux de convergence rapides ainsi que les algorithmes rapides établis dans le cadre de la régression linéaire à cette classe de fonctions, caractérisant au passage la difficulté du problème statistique sous-jacent à l'aide de deux quantités caractérisant la régularité de la solution, ainsi que celle de l'espace à noyau reproduisant utilisé. Dans un deuxième temps, nous introduisons un modèle pour les fonctions positives, qui est linéairement paramétré par un opérateur symétrique sur un espace à noyau reproduisant, et où la contrainte de positivité est garantie au moyen d'une contrainte de positivité semi-définie sur cet opérateur. Nous étudions les propriétés de ce modèle, et montrons qu'il a de bonnes propriétés d'approximation, qu'il préserve la convexité des fonctions de perte standard en apprentissage statistique, et qu'il est intégrable et différentiable en forme close lorsqu'il est défini avec des noyaux particuliers. En outre, cette dernière propriété nous permet d'utiliser ce modèle pour estimer des densités de probabilité, et nous développons un algorithme d'échantillonnage d'une densité de probabilité quelconque, accessible à partir de ses valeurs en certains points. Enfin, nous appliquons ce modèle de fonctions positives afin d'approcher le minimum global d'une fonction régulière. Dans le même esprit que les hiérarchies de Lasserre pour l'optimisation polynomiale, nous cherchons le minimum global d'une fonction comme sa plus grande borne inférieure, et affinons les garanties d'approximation du paragraphe précédent afin d'obtenir un algorithme quasi-optimal pour trouver le minimum global d'une fonction \`a partir de ses valeurs en un nombre donné de points. Nous établissons également des résultats théoriques permettant de généraliser cette approche à des fonctions définies sur des variétés.
Fichier principal
Vignette du fichier
manuscrit_principal.pdf (5.52 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-03989753 , version 1 (15-02-2023)

Identifiants

  • HAL Id : tel-03989753 , version 1

Citer

Ulysse Marteau-Ferey. Modelling functions with kernels: from logistic regression to global optimisation. Mathematics [math]. PSL, 2022. English. ⟨NNT : ⟩. ⟨tel-03989753⟩
53 Consultations
72 Téléchargements

Partager

Gmail Facebook X LinkedIn More