RUDI Alessandro

La théorie du filtrage spectral est un outil remarquable pour comprendre les propriétés statistiques de l'apprentissage avec des noyaux. Pour les moindres carrés, elle permet de dériver divers schémas de régularisation qui donnent des taux de convergence de l'excès de risque plus rapides qu'avec la régularisation de Tikhonov. On y parvient généralement en s'appuyant sur des hypothèses classiques appelées conditions de source et de capacité, qui caractérisent la difficulté de la tâche d'apprentissage. Afin de comprendre les estimateurs dérivés d'autres fonctions de perte, Marteau-Ferey et al. ont étendu la théorie de la régularisation de Tikhonov aux fonctions de perte autoconcordantes généralisées (GSC), qui contiennent, par exemple, la perte logistique. Dans cet article, nous allons plus loin et montrons que des taux rapides et optimaux peuvent être atteints pour les GSC en utilisant le schéma de régularisation de Tikhonov itéré, qui est intrinsèquement lié à la méthode du point proximal en optimisation, et qui surmonte les limitations de la régularisation de Tikhonov classique.

Une approche puissante et flexible de la prédiction structurée consiste à intégrer les objets structurés à prédire dans un espace caractéristique de dimension éventuellement infinie au moyen de noyaux de sortie, puis à résoudre un problème de régression dans cet espace de sortie. Une prédiction dans l'espace original est calculée en résolvant un problème de pré-image. Dans une telle approche, l'intégration, liée à la perte cible, est définie avant la phase d'apprentissage. Dans ce travail, nous proposons d'apprendre conjointement une approximation finie de l'encastrement de sortie et de la fonction de régression dans le nouvel espace caractéristique. À cette fin, nous exploitons des informations a priori sur les sorties ainsi que des données de sortie non supervisées non exploitées, qui sont toutes deux souvent disponibles dans les problèmes de prédiction structurée. Nous prouvons que le prédicteur structuré résultant est un estimateur cohérent, et nous dérivons une limite de risque excédentaire. En outre, le nouvel outil de prédiction structurée présente une complexité de calcul nettement inférieure à celle des anciennes méthodes à noyau de sortie. L'approche testée empiriquement sur divers problèmes de prédiction structurée se révèle polyvalente et capable de traiter de grands ensembles de données.

Nous introduisons une méthode d'approximation pour résoudre un problème de contrôle optimal via le dual de Lagrange de sa formulation faible. Elle est basée sur une représentation de la somme des carrés de l'hamiltonien, et étend une méthode précédente de l'optimisation polynomiale au cas générique des problèmes lisses. Une telle représentation est infiniment dimensionnelle et repose sur un espace particulier de fonctions - un espace de Hilbert à noyau reproducteur - choisi pour s'adapter à la structure du problème de contrôle. Après sous-échantillonnage, elle conduit à une méthode pratique qui revient à résoudre un programme semi-défini. Nous illustrons notre approche par une application numérique sur un problème de contrôle simple de faible dimension.

Il a été démontré que la mixité est un outil puissant pour obtenir des algorithmes avec un regret optimal. Cependant, les méthodes résultantes souffrent souvent d'une complexité de calcul élevée qui a réduit leur applicabilité pratique. Par exemple, dans le cas de la régression logistique multiclasse, le prévisionniste agrégatif (Foster et al. (2018)) atteint un regret de $O(\log(Bn))$ alors que Online Newton Step atteint $O(e^B\log(n))$ obtenant un gain doublement exponentiel en $B$ (une borne sur la norme des fonctions comparatives). Cependant, cette haute performance statistique est au prix d'une complexité computationnelle prohibitive $O(n^{37})$.

L'apprentissage automatique abordé par l'apprentissage supervisé nécessite une annotation coûteuse des données. Cela motive l'apprentissage faiblement supervisé, où les données sont annotées avec des informations incomplètes mais discriminantes. Dans cet article, nous nous concentrons sur l'étiquetage partiel, une instance de supervision faible où, à partir d'une entrée donnée, on nous donne un ensemble de cibles potentielles. Nous passons en revue un principe de désambiguïsation pour récupérer la supervision complète à partir de la supervision faible, et nous proposons un algorithme de désambiguïsation empirique. Nous prouvons des taux de convergence exponentiels de notre algorithme sous les hypothèses classiques d'apprenabilité, et nous illustrons l'utilité de notre méthode sur des exemples pratiques.

Les problèmes d'apprentissage supervisé discrets tels que la classification sont souvent abordés en introduisant un problème de substitution continu semblable à la régression. Le fait de limiter l'erreur initiale, entre l'estimation et la solution, par l'erreur de substitution confère aux problèmes discrets des taux de convergence déjà démontrés pour les instances continues. Pourtant, les approches actuelles n'exploitent pas le fait que les problèmes discrets prédisent essentiellement une sortie discrète alors que les problèmes continus prédisent une valeur continue. Dans cet article, nous abordons cette question pour des problèmes de prédiction structurés généraux, ouvrant la voie à des taux "super rapides", c'est-à-dire des taux de convergence pour l'excès de risque plus rapides que n -1 , où n est le nombre d'observations, avec même des taux exponentiels avec les hypothèses les plus fortes. Nous l'illustrons d'abord pour les prédicteurs basés sur les plus proches voisins, en généralisant les taux connus pour la classification binaire à tout problème discret dans le cadre de la prédiction structurée. Nous considérons ensuite la régression ridge à noyau où nous améliorons les taux connus en n -1/4 à des taux arbitrairement rapides, dépendant d'un paramètre caractérisant la dureté du problème, permettant ainsi, sous des hypothèses de lissage, de contourner la malédiction de la dimensionnalité.

L'annotation des ensembles de données est l'un des principaux coûts de l'apprentissage supervisé actuel. L'objectif de la supervision faible est de permettre aux modèles d'apprendre en utilisant uniquement des formes d'étiquetage qui sont moins coûteuses à collecter, comme l'étiquetage partiel. Il s'agit d'un type d'annotation incomplète où, pour chaque point de données, la supervision est présentée comme un ensemble d'étiquettes contenant la vraie étiquette. Le problème de l'apprentissage supervisé avec étiquetage partiel a été étudié pour des cas spécifiques tels que la classification, le multi-label, le classement ou la segmentation, mais un cadre général fait toujours défaut. Cet article fournit un cadre unifié basé sur la prédiction structurée et sur le concept de perte infimum pour traiter l'étiquetage partiel sur une large famille de problèmes d'apprentissage et de fonctions de perte. Le cadre conduit naturellement à des algorithmes explicites qui peuvent être facilement mis en œuvre et pour lesquels la cohérence statistique et les taux d'apprentissage sont prouvés. Les expériences confirment la supériorité de l'approche proposée par rapport aux méthodes de base couramment utilisées.

Les modèles linéaires ont montré une grande efficacité et une grande flexibilité dans de nombreux domaines tels que l'apprentissage automatique, le traitement du signal et les statistiques. Ils peuvent représenter de riches espaces de fonctions tout en préservant la convexité des problèmes d'optimisation où ils sont utilisés, et sont simples à évaluer, différencier et intégrer. Cependant, pour la modélisation des fonctions non négatives, qui sont cruciales pour l'apprentissage non supervisé, l'estimation de densité ou les méthodes bayésiennes non paramétriques, les modèles linéaires ne sont pas directement applicables. De plus, les modèles actuels de l'état de l'art, comme les modèles linéaires généralisés, conduisent à des problèmes d'optimisation non convexes ou ne peuvent pas être facilement intégrés. Dans cet article, nous proposons le premier modèle pour les fonctions non négatives qui bénéficie des mêmes bonnes propriétés que les modèles linéaires. En particulier, nous prouvons qu'il admet un théorème de représentation et fournissons une formulation duale efficace pour les problèmes convexes. Nous étudions son pouvoir de représentation, en montrant que l'espace de fonctions résultant est strictement plus riche que celui des modèles linéaires généralisés. Enfin, nous étendons le modèle et les résultats théoriques aux fonctions avec des sorties dans des cônes convexes. L'article est complété par une évaluation expérimentale du modèle montrant son efficacité en termes de formulation, de dérivation algorithmique et de résultats pratiques sur les problèmes d'estimation de densité, de régression avec erreurs hétéroscédastiques et de régression quantile multiple.

Nous considérons le cadre de la régression logistique en ligne et considérons le regret par rapport à la 2-boule de rayon B. Il est connu (voir [Hazan et al., 2014]) que tout algorithme propre qui a un regret logarithmique en nombre d'échantillons (noté n) souffre nécessairement d'une constante multiplicative exponentielle en B. Dans ce travail, nous concevons un algorithme impropre efficace qui évite cette constante exponentielle tout en préservant un regret logarithmique. En effet, [Foster et al, 2018] ont montré que la borne inférieure ne s'applique pas aux algorithmes impropres et ont proposé une stratégie basée sur des poids exponentiels avec une complexité de calcul prohibitive. Notre nouvel algorithme basé sur la minimisation empirique régularisée du risque avec des pertes de substitution satisfait un regret s'échelonnant comme O(B log(Bn)) avec une complexité temporelle par tour d'ordre O(d^2).

Nous considérons la minimisation globale de fonctions lisses basée uniquement sur des évaluations de fonctions. Les algorithmes qui atteignent le nombre optimal d'évaluations de fonctions pour un niveau de précision donné reposent généralement sur la construction explicite d'une approximation de la fonction, qui est ensuite minimisée par des algorithmes dont la complexité est exponentielle. Dans cet article, nous considérons une approche qui modélise conjointement la fonction à approximer et trouve un minimum global. Ceci est réalisé en utilisant des sommes infinies de fonctions lisses carrées et a des liens forts avec les hiérarchies de sommes de carrés polynomiales. En exploitant les propriétés de représentation récentes des espaces de Hilbert à noyau reproducteur, le problème d'optimisation en dimension infinie peut être résolu par sous-échantillonnage en temps polynomial par rapport au nombre d'évaluations de la fonction, et avec des garanties théoriques sur le minimum obtenu. Pour $n$ échantillons, le coût de calcul est de $O(n^{3.5})$ en temps, $O(n^2)$ en espace, et nous obtenons un taux de convergence vers l'optimum global de $O(n^{-m/d + 1/2 + 3/d})$ où $m$ est le degré de différentiabilité de la fonction et $d$ le nombre de dimensions. Ce taux est presque optimal dans le cas des fonctions de Sobolev et plus généralement rend la méthode proposée particulièrement adaptée aux fonctions qui ont un grand nombre de dérivées. En effet, lorsque $m$ est de l'ordre de $d$, le taux de convergence vers l'optimum global ne souffre pas de la malédiction de la dimensionnalité, qui n'affecte que les constantes du pire cas (que nous suivons explicitement tout au long de l'article).

Pas de résumé disponible.

Dans cet article, nous étudions les algorithmes d'optimisation convexe à grande échelle basés sur la méthode de Newton appliquée aux pertes autoconcordantes généralisées régularisées, qui comprennent la régression logistique et la régression softmax. Nous prouvons d'abord que notre nouveau schéma simple basé sur une séquence de problèmes avec des paramètres de régularisation décroissants est globalement convergent, que cette convergence est linéaire avec un facteur constant qui n'évolue que logarithmiquement avec le nombre de conditions. Dans le cadre paramétrique, nous obtenons un algorithme avec la même échelle que les méthodes régulières du premier ordre mais avec un comportement amélioré, en particulier dans les problèmes mal conditionnés. Deuxièmement, dans le cadre de l'apprentissage automatique non paramétrique, nous fournissons un algorithme explicite combinant le schéma précédent avec les techniques de projection de Nyström, et nous prouvons qu'il atteint des limites de généralisation optimales avec une complexité temporelle d'ordre O(ndf λ), une complexité mémoire d'ordre O(df 2 λ) et aucune dépendance du nombre de conditions, généralisant les résultats connus pour la régression des moindres carrés. Ici, n est le nombre d'observations et df λ est le nombre de degrés de liberté associé. En particulier, il s'agit du premier algorithme à grande échelle pour résoudre les régressions logistiques et softmax dans le cadre non-paramétrique avec de grands nombres de condition et des garanties théoriques.

Les inégalités de Poincaré sont omniprésentes en probabilité et en analyse et ont diverses applications en statistique (concentration de la mesure, taux de convergence des chaînes de Markov). La constante de Poincaré, pour laquelle l'inégalité est serrée, est liée au taux de convergence typique des diffusions vers leur mesure d'équilibre. Dans cet article, nous montrons à la fois théoriquement et expérimentalement que, étant donné un nombre suffisant d'échantillons d'une mesure, nous pouvons estimer sa constante de Poincaré. Comme sous-produit de l'estimation de la constante de Poincaré, nous dérivons un algorithme qui capture une représentation de faible dimension des données en trouvant des directions qui sont difficiles à échantillonner. Ces directions sont d'une importance cruciale pour l'échantillonnage ou dans des domaines comme la dynamique moléculaire, où elles sont appelées coordonnées de réaction. Leur connaissance permet d'exploiter, par une simple étape de conditionnement, les goulots d'étranglement computationnels en utilisant des techniques d'échantillonnage par importance.

Dans ce travail, nous fournissons un estimateur pour la matrice de covariance d'une distribution multivariée à queue lourde. Nous prouvons que l'estimateur proposé $\widehat{\mathbf{S}}$ admet une limite \textit{affine-invariante} de la forme $$(1-\epsilon )\mathbf{S}\preccurlyeq \hat{\mathbf{S}}\preccurlyeq (1+\epsilon )\mathbf{S}$$ avec une probabilité élevée, où $\mathbf{S}$ est la matrice de covariance inconnue, et $\preccurlyeq$ est l'ordre semi-défini positif sur les matrices symétriques. Le résultat ne requiert que l'existence de moments d'ordre 4, et autorise $\varepsilon = O(\sqrt{\kappa^4 d\log(d/\delta)/n})$ où $\kappa^4$ est une mesure de l'aplatissement de la distribution, $d$ est la dimensionnalité de l'espace, $n$ est la taille de l'échantillon, et $1-\delta$ est le niveau de confiance souhaité. De manière plus générale, on peut autoriser une régularisation avec le niveau $\lambda$, $d$ étant alors remplacé par le nombre de degrés de liberté. En désignant par $\text{cond}(\mathbf{S})$ le nombre de conditions de $\mathbf{S}$, le coût de calcul du nouvel estimateur est de $O(d^2 n + d^3\log(\text{cond}(\mathbf{S})))$, ce qui est comparable au coût de l'estimateur de covariance d'échantillon dans le régime statistiquement intéressant $n \ge d$. Nous considérons des applications de notre estimateur à l'estimation des valeurs propres avec une erreur relative, et à la régression ridge avec un plan aléatoire à queue lourde.

Nous nous intéressons à un cadre d'apprentissage en ligne avec des noyaux pour des ensembles de données de faible dimension mais à grande échelle et potentiellement adversaires. Nous étudions les performances informatiques et théoriques de variations en ligne de la régression de Ridge à noyau. Malgré sa simplicité, l'algorithme que nous étudions est le premier à atteindre le regret optimal pour une large gamme de noyaux avec une complexité par tour d'ordre $n^\alpha$ avec $\alpha < 2$. L'algorithme que nous considérons est basé sur l'approximation du noyau avec l'étendue linéaire des fonctions de base. Nos contributions sont de deux ordres : 1) Pour le noyau gaussien, nous proposons de construire la base au préalable (indépendamment des données) par expansion de Taylor. Pour des entrées de $d$-dimensions, nous fournissons un regret (proche de) optimal d'ordre $O((\log n)^{d+1})$ avec une complexité temporelle par tour et une complexité spatiale $O((\log n)^{2d})$. Cela fait de l'algorithme un choix approprié dès que $n \gg e^d$, ce qui est susceptible de se produire dans un scénario avec des données de petite dimension et à grande échelle. 2) Pour les noyaux généraux à faible dimension effective, les fonctions de base sont mises à jour séquentiellement de manière adaptée aux données par échantillonnage de points de Nyström. Dans ce cas, notre algorithme améliore le compromis de calcul connu pour la régression par noyau en ligne.

Nous considérons des méthodes d'apprentissage basées sur la régularisation d'un risque empirique convexe par une norme hilbertienne carrée, un cadre qui inclut des prédicteurs linéaires et des prédicteurs non linéaires par des noyaux positifs-définis. Afin d'aller au-delà de l'analyse générique conduisant à des taux de convergence de l'excès de risque de $O(1/\sqrt{n})$ à partir de $n$ observations, nous supposons que les pertes individuelles sont autoconcordantes, c'est-à-dire que leurs dérivées de troisième ordre sont limitées par leurs dérivées de deuxième ordre. Ce cadre inclut les moindres carrés, ainsi que tous les modèles linéaires généralisés tels que la régression logistique et softmax. Pour cette classe de pertes, nous fournissons une décomposition biais-variance et montrons que les hypothèses communément faites dans la régression des moindres carrés, telles que les conditions de source et de capacité, peuvent être adaptées pour obtenir des taux de convergence rapides non asymptotiques en améliorant les termes de biais, les termes de variance ou les deux.

Dans cet article, nous étudions les problèmes de régression sur un espace de Hilbert séparable avec la perte carrée, couvrant la régression non-paramétrique sur un espace de Hilbert à noyau reproducteur. Nous étudions une classe d'algorithmes spectraux/régularisés, y compris la régression ridge, la régression en composantes principales et les méthodes de gradient. Nous prouvons des résultats de convergence optimaux et à haute probabilité en termes de variantes de normes pour les algorithmes étudiés, en considérant une hypothèse de capacité sur l'espace des hypothèses et une condition de source générale sur la fonction cible. Par conséquent, nous obtenons des résultats de convergence presque sûrs avec des taux optimaux. Nos résultats améliorent et généralisent les résultats précédents, comblant un vide théorique pour les cas non réalisables.

Le problème de la conception de stratégies d'apprentissage pour les pertes discrètes (par exemple, le multi-étiquetage, le classement) est actuellement abordé avec des méthodes et des analyses théoriques ad-hoc pour chaque perte. Dans cet article, nous étudions un cadre des moindres carrés pour concevoir systématiquement des algorithmes d'apprentissage pour les pertes discrètes, avec des caractérisations quantitatives en termes de complexité statistique et informatique. En particulier, nous améliorons les résultats existants en fournissant une dépendance explicite du nombre de labels pour une large classe de pertes et des taux d'apprentissage plus rapides dans des conditions de faible bruit. Les résultats théoriques sont complétés par des expériences sur des ensembles de données réels, montrant l'efficacité de l'approche générale proposée.

Nous considérons la descente de gradient stochastique (SGD) pour la régression des moindres carrés avec potentiellement plusieurs passages sur les données. Alors qu'il a été largement démontré que plusieurs passages sont pratiquement plus performants en termes de prédiction sur des données non vues, l'analyse théorique existante de la SGD suggère qu'un seul passage est statistiquement optimal. Bien que cela soit vrai pour les problèmes faciles de faible dimension, nous montrons que pour les problèmes difficiles, plusieurs passages conduisent à des prédictions statistiquement optimales alors qu'un seul passage ne le fait pas. Nous montrons également que dans ces modèles difficiles, le nombre optimal de passages sur les données augmente avec la taille de l'échantillon. Afin de définir la notion de dureté et de montrer que nos performances prédictives sont optimales, nous considérons des modèles potentiellement de dimension infinie et des notions typiquement associées aux méthodes à noyau, à savoir la décroissance des valeurs propres de la matrice de covariance des caractéristiques et la complexité du prédicteur optimal telle que mesurée par la matrice de covariance. Nous illustrons nos résultats sur des expériences synthétiques avec des méthodes à noyau non linéaires et sur un benchmark classique avec un modèle linéaire.

Les applications du transport optimal ont récemment fait l'objet d'une attention remarquable grâce aux avantages computationnels de la régularisation entropique. Cependant, dans la plupart des situations, l'approximation de Sinkhorn de la distance de Wasserstein est remplacée par une version régularisée qui est moins précise mais facile à différencier. Dans ce travail, nous caractérisons les propriétés différentielles de la distance de Sinkhorn originale, en prouvant qu'elle jouit de la même régularité que sa version régularisée et nous fournissons explicitement un algorithme efficace pour calculer son gradient. Nous montrons que ce résultat profite à la fois à la théorie et aux applications : d'une part, la régularité d'ordre élevé confère des garanties statistiques à l'apprentissage avec des approximations de Wasserstein. D'autre part, la formule du gradient nous permet de résoudre efficacement les problèmes d'apprentissage et d'optimisation en pratique. Des expériences préliminaires prometteuses complètent notre analyse.

La clé de la prédiction structurée consiste à exploiter la structure du problème pour simplifier le processus d'apprentissage. Un défi majeur se pose lorsque les données présentent une structure locale (par exemple, elles sont composées de "parties") qui peut être exploitée pour mieux approximer la relation entre (parties de) l'entrée et (parties de) la sortie. La littérature récente sur le traitement du signal, et en particulier la vision par ordinateur, a montré que la capture de ces aspects est en effet essentielle pour atteindre des performances de pointe. Alors que ces algorithmes sont généralement dérivés au cas par cas, nous proposons dans ce travail le premier cadre théorique pour traiter les données basées sur les parties d'un point de vue général. Nous dérivons une nouvelle approche pour traiter ces problèmes et étudions ses propriétés de généralisation dans le cadre de la théorie de l'apprentissage statistique. Notre analyse est nouvelle en ce sens qu'elle quantifie explicitement les avantages de l'exploitation de la structure du problème basée sur les parties en ce qui concerne les taux d'apprentissage de l'estimateur proposé.

Nous considérons des problèmes de classification binaire avec des noyaux définis positifs et une perte au carré, et nous étudions les taux de convergence des méthodes de gradient stochastique. Nous montrons que si l'excès de perte de test (perte au carré) converge lentement vers zéro lorsque le nombre d'observations (et donc d'itérations) va vers l'infini, l'erreur de test (erreur de classification) converge exponentiellement vite si l'on suppose des conditions de faible bruit.

Les méthodes d'esquisse et de gradient stochastique sont sans doute les techniques les plus courantes pour dériver des algorithmes d'apprentissage efficaces à grande échelle. Dans cet article, nous étudions leur application dans le contexte de l'apprentissage statistique non paramétrique. Plus précisément, nous étudions l'estimateur défini par le gradient stochastique avec des mini-lots et des caractéristiques aléatoires. Ce dernier peut être vu comme une forme d'esquisse non linéaire et utilisé pour définir des méthodes approximatives à noyau. L'estimateur considéré n'est pas explicitement pénalisé/contraint et la régularisation est implicite. En effet, notre étude met en évidence comment différents paramètres, tels que le nombre de caractéristiques, d'itérations, de pas et de mini-lots, contrôlent les propriétés d'apprentissage des solutions. Nous faisons cela en dérivant des limites optimales d'échantillons finis, sous des hypothèses standard. Les résultats obtenus sont corroborés et illustrés par des expériences numériques.

La prédiction structurée fournit un cadre général pour traiter les problèmes supervisés où les sorties ont une structure sémantiquement riche. Alors que les approches classiques considèrent des espaces de sortie finis, bien que potentiellement énormes, nous examinons dans cet article comment la prédiction structurée peut être étendue à un scénario continu. Plus précisément, nous étudions une approche de prédiction structurée pour la régression à valeurs multiples. Nous caractérisons une classe de problèmes pour lesquels l'approche considérée est statistiquement cohérente et nous étudions comment l'optimisation géométrique peut être utilisée pour calculer l'estimateur correspondant. Des résultats expérimentaux prometteurs sur des données simulées et réelles complètent notre étude.

L'échantillonnage par score à effet de levier constitue un moyen attrayant d'effectuer des calculs approximatifs pour les grandes matrices. En effet, il permet de dériver des approximations fidèles avec une complexité adaptée au problème à traiter. Cependant, l'exécution de l'échantillonnage de scores de levier est un défi en soi qui nécessite des approximations supplémentaires. Dans cet article, nous étudions le problème de l'échantillonnage des scores de levier pour les matrices définies positives définies par un noyau. Notre contribution est double. Premièrement, nous fournissons un nouvel algorithme pour l'échantillonnage du score de levier et deuxièmement, nous exploitons la méthode proposée dans l'apprentissage statistique en dérivant un nouveau solveur pour la régression ridge à noyau. Notre principale contribution technique est de montrer que les algorithmes proposés sont actuellement les plus efficaces et les plus précis pour ces problèmes.