La descente en pente converge-t-elle toujours vers un optimum?

Je me demande s'il existe un scénario dans lequel la descente en pente ne converge pas au minimum.

Je suis conscient que la descente en pente n'est pas toujours garantie de converger vers un optimum global. Je suis également conscient qu'il peut s'écarter d'un optimum si, par exemple, la taille du pas est trop grande. Cependant, il me semble que s'il s'écarte d'un optimum, il finira par passer à un autre optimum.

Par conséquent, la descente du gradient serait garantie de converger vers un optimum local ou global. Est-ce correct? Sinon, pourriez-vous fournir un contre-exemple approximatif?

Gradient Descent est un algorithme conçu pour trouver les points optimaux, mais ces points optimaux ne sont pas nécessairement globaux. Et oui s'il arrive qu'il diverge d'un emplacement local il peut converger vers un autre point optimal mais sa probabilité n'est pas trop. La raison en est que la taille du pas peut être trop grande pour le faire reculer d'un point optimal et la probabilité qu'il oscille est bien plus que la convergence.

À propos de la descente de gradient, il existe deux perspectives principales, l'ère de l'apprentissage automatique et l'ère de l'apprentissage en profondeur. Au cours de l'ère de l'apprentissage automatique, il a été considéré que la descente de gradient trouverait l'optimum local / global, mais à l'ère de l'apprentissage profond où la dimension des caractéristiques d'entrée est trop élevée, il est démontré en pratique que la probabilité que toutes les caractéristiques soient situées dans la valeur optimale à un seul point n'est pas trop et vu plutôt avoir des emplacements optimaux dans les fonctions de coût, la plupart du temps les points de selle sont observés. C'est l'une des raisons pour lesquelles la formation avec beaucoup de données et les périodes de formation font que les modèles d'apprentissage profond surpassent les autres algorithmes. Donc, si vous entraînez votre modèle, il trouvera un détour ou trouvera son chemin pour descendre et ne restera pas coincé dans les points de selle, mais vous devez avoir des tailles de pas appropriées.

Pour plus d'intuitions, je vous suggère de vous référer ici et ici .

Mis à part les points que vous avez mentionnés (convergence vers des minimums non globaux et grandes tailles de pas pouvant conduire à des algorithmes non convergents), les "plages d'inflexion" peuvent également être un problème.

Considérez le type de fonction «fauteuil inclinable» suivant.

De toute évidence, cela peut être construit de sorte qu'il y ait une plage au milieu où le gradient est le vecteur 0. Dans cette plage, l'algorithme peut être bloqué indéfiniment. Les points d'inflexion ne sont généralement pas considérés comme des extrema locaux.

Le gradient conjugué n'est pas garanti pour atteindre un optimum global ou un optimum local! Il y a des points où le gradient est très petit, qui ne sont pas optima (points d'inflexion, points de selle). La descente en gradient pourrait converger vers un point pour la fonction .f ( x ) = x $x = 0$$f(x) = x^3$

[Note 5 avril 2019: une nouvelle version du document a été mise à jour sur arXiv avec de nombreux nouveaux résultats. Nous introduisons également des versions de retour arrière de Momentum et NAG, et prouvons la convergence sous les mêmes hypothèses que pour la descente de gradient de retour arrière.

Les codes sources sont disponibles sur GitHub sur le lien: https://github.com/hank-nguyen/MBT-optimizer

Nous avons amélioré les algorithmes d'application à DNN et obtenu de meilleures performances que les algorithmes de pointe tels que MMT, NAG, Adam, Adamax, Adagrad, ...

La caractéristique la plus spéciale de nos algorithmes est qu'ils sont automatiques, vous n'avez pas besoin de régler manuellement les taux d'apprentissage comme une pratique courante. Notre réglage automatique est de nature différente d'Adam, Adamax, Adagrad, ... et ainsi de suite. Plus de détails sont dans le papier.

]

Basé sur des résultats très récents: Dans mon travail conjoint dans cet article https://arxiv.org/abs/1808.05160

$f$

Sur la base de ce qui précède, nous avons proposé une nouvelle méthode d'apprentissage en profondeur qui est à égalité avec les méthodes actuelles de pointe et ne nécessite pas de réglage manuel précis des taux d'apprentissage. (En un mot , l'idée est que vous exécutez une descente de gradient de retour arrière un certain temps, jusqu'à ce que vous voyiez que les taux d'apprentissage, qui changent à chaque itération, se stabilisent. Nous nous attendons à cette stabilisation, en particulier à un point critique qui est C ^ 2 et est non dégénéré, en raison du résultat de convergence que j'ai mentionné ci-dessus. À ce stade, vous passez à la méthode de descente en gradient standard. Veuillez consulter l'article cité pour plus de détails. Cette méthode peut également être appliquée à d'autres algorithmes optimaux .)

PS En ce qui concerne votre question initiale sur la méthode de descente à gradient standard, à ma connaissance uniquement dans le cas où la dérivée de la carte est globalement Lipschitz et le taux d'apprentissage est suffisamment petit pour que la méthode de descente à gradient standard converge. [Si ces conditions ne sont pas remplies, il existe de simples contre-exemples montrant qu'aucun résultat de convergence n'est possible, voir l'article cité pour certains.] Dans l'article cité ci-dessus, nous avons soutenu qu'à long terme, la méthode de descente en gradient de retour en arrière deviendra la méthode de descente en gradient standard, qui explique pourquoi la méthode de descente en gradient standard fonctionne généralement bien en pratique.