Comment définir la condition de terminaison de la descente en pente?

En fait, je voulais vous demander comment puis-je définir la condition de fin pour la descente en gradient.

Puis-je l'arrêter en fonction du nombre d'itérations, c'est-à-dire en tenant compte des valeurs des paramètres pour, disons, 100 itérations?

Ou dois-je attendre de telle sorte que les différentes valeurs des deux paramètres «nouveau» et «ancien» soient très petites de l'ordre de disons ? Cela prendra certainement beaucoup de temps. $10^{-6}$

Quel est le meilleur moyen? Dans mon cas, une seule itération prend beaucoup de temps. Dans cette situation, si j'attends la deuxième condition, cela peut même prendre des semaines, je suppose.

Alors quelle approche dois-je utiliser. Comment faire face à ce scénario?

algorithms optimization gradient-descent user31820
la source

Ce n'est pas explicitement indiqué, mais je suppose que vous essayez de trouver un MLE. Votre résultat dépend vraiment entièrement de votre espace de paramètres, de votre fonction de vraisemblance et de vos besoins (c'est-à-dire que le mieux n'est pas bien défini). Si vous recherchez simplement une justification théorique telle que l'efficacité asymptotique; dans les conditions Le'Cam, vous pouvez simplement utiliser le MLE en une étape (sous l'hypothèse supplémentaire que vous utilisez la méthode de Newton et la fonction de score pour votre descente de gradient). Cela nécessite que votre valeur initiale soit telle que en probabilité.

n^{1 / 2} {\hat{θ}}_{0} \to θ

$n^{1/2}\hat{\theta}_0 \rightarrow \theta$

Jonathan Lisic

alors attendez, quand vous dites "nouveau" - "ancien" est suffisamment petit, est-ce une condition de terminaison incorrecte pour la descente en pente? (si un point fixe comme des théorèmes s'appliquent, cette condition devrait être correcte?)

Charlie Parker

On pourrait s'arrêter lorsque l'une des valeurs de fonction , ou les gradients , ou les paramètres , semblent cesser de bouger, qu'ils soient relatifs ou absolus. Mais en pratique paramètres .. est beaucoup trop nombreux donc ils sont pliés, mais chaque programme fait ça différemment. Voir Tolérances et critères d'arrêt Mathworks pour une image.

f_{i}

$f_i$

\nabla f_{i}

$\nabla f_i$

x_{i}

$x_i$

3 \times 2

$3 \times 2$ ftolabs ftolrelxtolabs

denis

Bonne question. J'ai vu beaucoup de règles d'arrêt dans la littérature, et il y a des avantages et des inconvénients pour chacun, selon le contexte. La optimfonction dans R, par exemple, a au moins trois règles d'arrêt différentes:

maxit, c'est-à-dire un nombre maximum prédéterminé d'itérations. Une autre alternative similaire que j'ai vue dans la littérature est un nombre maximum de secondes avant expiration. Si tout ce dont vous avez besoin est une solution approximative, cela peut être très raisonnable. En fait, il existe des classes de modèles (en particulier les modèles linéaires) pour lesquels un arrêt précoce est similaire à la mise en priorité gaussienne de vos valeurs de paramètres. Un habitué dirait que vous avez une "norme L2" plutôt qu'un précédent, mais il pense aussi que c'est une chose raisonnable à faire. J'ai seulement survolé ce document , mais il parle de la relation entre l'arrêt précoce et la régularisation et pourrait vous aider à vous orienter vers plus d'informations. Mais la version courte est, oui, un arrêt précoce peut être une chose parfaitement respectable, selon ce que vous ''
abstol, c'est-à-dire s'arrêter lorsque la fonction est "assez proche" de zéro. Cela peut ne pas être pertinent pour vous (il ne semble pas que vous vous attendiez à un zéro), donc je vais le sauter.
reltol, ce qui est comme votre deuxième suggestion - arrêtez-vous lorsque l'amélioration descend en dessous d'un seuil. Je ne sais pas vraiment combien il y a de théorie à ce sujet, mais vous aurez probablement tendance à obtenir des minima inférieurs de cette façon qu'avec un petit nombre maximum d'itérations. Si cela est important pour vous, il peut être utile d'exécuter le code pour plus d'itérations.

Une autre famille de règles d'arrêt concerne l'optimisation d'une fonction de coût sur un ensemble de données de validation (ou avec validation croisée) plutôt que sur les données de formation. Selon l'utilisation que vous souhaitez faire de votre modèle, vous souhaiterez peut-être vous arrêter bien avant d'atteindre le minimum local sur vos données d'entraînement, car cela pourrait impliquer un surapprentissage. Je suis à peu près sûr que Trevor Hastie a écrit sur les bonnes façons de le faire, mais je ne me souviens pas de la citation.

D'autres options possibles pour trouver des minima inférieurs dans un délai raisonnable pourraient inclure:

Descente de gradient stochastique, qui ne nécessite d'estimer les gradients que pour une petite partie de vos données à la fois (par exemple, un point de données pour le SGD "pur" ou de petits mini-lots).
Fonctions d'optimisation plus avancées (par exemple, méthodes de type Newton ou gradient conjugué), qui utilisent des informations sur la courbure de votre fonction objectif pour vous aider à pointer dans de meilleures directions et à prendre de meilleures tailles de pas lorsque vous descendez.
Un terme "dynamique" dans votre règle de mise à jour, pour que votre optimiseur fasse un meilleur travail de descente plutôt que de délimiter les parois du canyon dans votre fonction d'objectif.

Ces approches sont toutes discutées dans ces notes de cours que j'ai trouvées en ligne.

J'espère que cela t'aides!

Modifiez oh, et vous pouvez également essayer d'obtenir de meilleures valeurs de départ (par exemple en résolvant une version plus simple du problème) de sorte qu'il faut moins d'itérations pour se rapprocher de l'optimum à partir de votre "démarrage à chaud".

David J. Harris
la source

le problème avec le choix d'un nombre fixe d'itérations est que, sauf si vous pouvez tracer clairement votre courbe de coût (et qu'il y a un petit bruit), il est difficile de savoir combien d'itérations est trop, surtout si la fonction d'optimisation est compliquée et qui sait combien de minimums locaux il possède et si vous avez une initialisation aléatoire, cela aggrave encore le problème, car il est encore plus difficile de deviner ce qu'est un bon "petit" nombre d'itérations. Comment abordez-vous ces problèmes dans la réalité si vous souhaitez réellement utiliser l'arrêt anticipé? Comment vous assurez-vous de ne pas trop tirer ou ne pas trop dépasser?

Charlie Parker

Je voudrais clarifier ce que signifie reltol(c'est-à-dire quand il n'y a plus "d'amélioration"). La première amélioration signifie une diminution de la fonction de coût. Je suppose donc que vous voulez dire que lorsque la fonction de coût cesse de diminuer suffisamment (ou commence à augmenter), on s'arrête, non? On ne fait pas vraiment "| ancien - nouveau |" type de règle de mise à jour, non?

Charlie Parker

Le abstolparamètre n'a de sens que si vous prenez la tolérance du gradient de la fonction de coût, pas la fonction de coût elle-même. Dans un optimiseur local, la valeur du gradient est nulle; mais pas la valeur de la fonction.

Mario Becerra

"démarrage à chaud" est un truc très intelligent! merci

Mehdi LAMRANI

Comment définir la condition de terminaison de la descente en pente?

Réponses: