Descente en gradient sur des fonctions non convexes

Quelles situations connaissons-nous où la descente de gradient peut converger (soit vers un point critique, soit vers un minimum local / global) pour des fonctions non convexes?

Pour SGD sur les fonctions non convexes, un type de preuve a été examiné ici, http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf

Voir l'annexe B1 dans https://web.stanford.edu/~boyd/cvxbook/ .

La fonction et la contrainte peuvent être non convexes dans un programme quadratique à contraintes quadratiques, et vous pouvez toujours voir une forte dualité (elle est garantie si une condition technique connue sous le nom de qualificatif de contrainte de Slater est vérifiée)

Une forte dualité en termes faibles signifie que nous pouvons résoudre le problème d'optimisation. A partir du problème d'origine qui est appelé le primal, vous pouvez formuler un problème alternatif appelé le problème dual. La solution du double problème fournit une solution qui, dans un certain sens, est la "meilleure borne inférieure" pour vos problèmes d'origine

Dans de nombreux problèmes d'optimisation qui ne sont pas convexes, il y aura un écart entre les solutions primale et double, c'est-à-dire que la limite inférieure peut être bien en dessous de la vraie valeur optimale (même l'infini négatif). Dans certains cas particuliers, la limite est serrée. Ces cas particuliers sont ceux dans lesquels nous avons une forte dualité.

L'algorithme est une TECHNIQUE utilisée pour arriver au point optimal. La solution optimale et notre capacité à la trouver dépendent de la GÉOMÉTRIE du problème (qui est ce à quoi la dualité essaie d'arriver). Autrement dit, l'analyse indique que si l'optimisation correctement configurée converge vers un minimum.

En général, la descente de gradient convergera vers un point stationnaire. Ce point peut être un minimum local / minimum global / minimum selle. Dans seulement quelques cas non convexes, nous pouvons garantir ce à quoi il converge

Dans cette réponse, j'explorerai deux articles intéressants et pertinents qui ont été évoqués dans les commentaires. Avant de le faire, je vais tenter de formaliser le problème et de faire la lumière sur certaines hypothèses et définitions. Je commence par un article de 2016 de Lee et al.

Nous cherchons à minimiser une fonction non convexe $f: \mathbb{R}^d \to \mathbb{R}$qui est délimité ci-dessous. Nous exigeons qu'il soit différenciable deux fois. Nous utilisons un algorithme de descente de gradient de la forme:

$\pmb{x}_{t+1} = \pmb{x}_t - \alpha\nabla f(\pmb{x}_t)$.

De plus, nous avons l'exigence suivante:

$\| \nabla f(\pmb{x}_1)-\nabla f(\pmb{x}_2) \| \leq \ell \| \pmb{x}_1 - \pmb{x}_2 \|, \quad \text{for all } \pmb{x}_1, \pmb{x}_2$.

Autrement dit, nous exigeons que notre fonction soit -Lipschitz dans sa dérivée première. En anglais, cela se traduit par l'idée que notre gradient ne peut pas changer trop rapidement n'importe où dans le domaine. Cette hypothèse garantit que nous pouvons choisir une taille de pas telle que nous ne nous retrouvons jamais avec des étapes qui divergent.$\ell$

Rappelons qu'un point est dit être une selle stricte si et et . Si toutes les valeurs propres de la Hesse ont le même signe, le point est un minimum (si elles sont positives) ou un maximum (si elles sont négatives). S'il y a des valeurs propres 0 alors il est dit dégénéré et ce n'est pas une selle stricte.$\pmb{x}$$\nabla f(\pmb{x}) = 0$$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right) < 0$$\lambda_{\max}\left(\nabla^2 f(\pmb{x})\right) > 0$

L'article montre qu'avec les hypothèses ci-dessus, ainsi que l'hypothèse que tous les points de selle de la fonction sont strictement selle, la descente du gradient est garantie de converger vers un minimum.

La preuve est assez technique, mais l'intuition est la suivante: définir un ensemble , où est un point de selle. Je n'aime pas du tout cette notation. Ce qu'ils essaient de comprendre, c'est que est l'ensemble des valeurs de départ pour lesquelles la carte de gradient envoie à . Plus simplement, c'est l'ensemble des initialisations aléatoires qui convergeront finalement vers une selle.$W^s(\pmb{x}^s) = \{\pmb{x} : \lim_k g^k(\pmb{x}) = \pmb{x}^s \}$$\pmb{x}^s$$W$$g : \mathbb{R}^d \to \mathbb{R}^d$$\pmb{x}_k$$\pmb{x}^s$

Leur argument repose sur le théorème du collecteur stable. Avec les hypothèses ci-dessus et un tas de mathématiques ésotériques, ils concluent que l'ensemble doit être de mesure zéro, c'est-à-dire qu'il n'y a aucune probabilité d'initialisation aléatoire sur un point qui convergera vers un point de selle. Comme nous savons que la descente de gradient sur des fonctions du type décrit dans les hypothèses avec des tailles de pas convenablement petites atteindra finalement un point critique, et nous savons maintenant (presque sûrement) qu'elle n'atterrira jamais sur une selle, nous savons qu'elle converge vers un minimiseur.$W^s$

Le deuxième article, plus récent, de Reddi et al. J'aborderai plus en détail. Il existe plusieurs différences. Premièrement, ils ne travaillent plus dans un cadre déterministe, optant plutôt pour le cadre d'approximation stochastique plus pertinent sur une somme finie (pensez à la descente de gradient stochastique). Les principales différences sont que la taille du pas nécessite des soins supplémentaires et que le gradient devient une variable aléatoire. De plus, ils relâchent l'hypothèse que toutes les selles sont strictes et recherchent un point stationnaire de second ordre. Autrement dit, un point tel que, $\|\nabla(f) \| \leq \epsilon, \quad \text{and}, \quad \lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\geq -\sqrt{\rho\epsilon}$

Où est la constante de Lipschitz pour la Hesse. (C'est-à-dire, en plus de l'exigence que notre gradient ne varie pas trop rapidement, nous avons maintenant une exigence similaire sur notre Hesse. Essentiellement, les auteurs recherchent un point qui ressemble à un minimum dans la dérivée première et seconde.$rho$

La méthode par laquelle ils accomplissent cela consiste à utiliser une variante (choisissez votre préférée) de descente de gradient stochastique la plupart du temps. Mais partout où ils rencontrent un point où , ils utilisent une méthode de second ordre convenablement choisie pour échapper à la selle. Ils montrent qu'en incorporant ces informations de second ordre selon les besoins, ils convergeront vers un point stationnaire de second ordre.$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\leq 0$

Techniquement, il s'agit d'une méthode de gradient de second ordre, qui peut ou non relever de l'algorithme qui vous intéressait.

Il s'agit d'un domaine de recherche très actif et j'ai omis de nombreuses contributions importantes (ex Ge et al. ). Je suis également nouveau sur le sujet, cette question m'a donc permis de regarder. Je suis heureux de poursuivre la discussion s'il y a un intérêt.

*** Choisi de manière appropriée signifie un point qui se révèle converger vers un point stationnaire de second ordre. Ils utilisent la méthode de Newton régularisée cubique de Nesterov et Polyak.

Je vais essayer de répondre à la partie "quand la descente du gradient converge-t-elle vers un point critique" de la question.

L'article "Convergence des méthodes de descente pour les problèmes semi-algébriques et apprivoisés: algorithmes proximaux, fractionnement avant-arrière et méthodes de Gauss-Seidel régularisées"

par Attouch, Bolte et Svaiter,

montre que si la fonction objectif satisfait l'inégalité de Kurdyka-Lojasiewicz (KL), alors GD et d'autres méthodes de descente convergent en fait vers un minimiseur. Notez que la condition KL est extrêmement générale mais difficile à saisir. Les fonctions qui satisfont KL sont par exemple données par des fonctions semi-algébriques (encore une fois très générales mais pas une notion simple).

Afin de donner quelques intuitions sur ces notions je vais essayer d'être moins vague mais aussi pas trop technique, donc nu avec moi. Une fonction satisfait la condition KL à un point critique s'il existe une fonction (notez que je laisse de côté certaines conditions) telles que pour tout tel que pour certains . L'intuition est qu'il existe une fonction qui reparamétrise notre fonction d'intérêt$f$$\bar{x}$$\phi$

La semialgebricité est en revanche un peu plus difficile. Le domaine qui l'étudie est également connu sous le nom de géométrie apprivoisée . Je pense que le nom apprivoisé capture très bien l'essence. Les fonctions appartenant à cette classe ne peuvent pas être arbitrairement «sauvages».