Descente de coordonnées vs descente de gradient

Je me demandais quels sont les différents cas d'utilisation pour les deux algorithmes, Descente de coordonnées et Descente de gradient .

Je sais que la descente de coordonnées a des problèmes avec les fonctions non lisses mais elle est utilisée dans des algorithmes populaires comme SVM et LASSO.

La descente en pente est cependant, je pense, utilisée plus largement, en particulier avec la résurgence des RNA, et pour de nombreuses autres tâches d'apprentissage automatique.

Ma question est la suivante: quel type de problèmes convient à l'un mais pas à l'autre et, à cet égard, qu'est-ce qui rend l'ajustement de descente coordonnée pour les SVM et le LASSO, mais l'ajustement de descente en gradient pour les ANN?

Comment choisir entre les deux lors du choix d'un algorithme d'optimisation?

Je pense que c'est généralement une question de simplicité / facilité d'élaboration du gradient de la partie lisse de la fonction et / ou de l'opérateur proximal de la pénalité.

Parfois, il est beaucoup plus simple de trouver une solution exacte du problème dans le cas d'une seule variable (ou d'un bloc ou de variables), que de la trouver simultanément pour toutes les variables. D'autres fois, il est tout simplement trop coûteux de calculer le gradient par rapport aux dérivés individuels. De plus, la convergence de la descente de coordonnées est la même que pour ista, , où est le nombre d'itérations, mais il peut parfois être meilleur comparé à ISTA et FISTA, voir par exemple http: //statweb.stanford .edu / ~ tibs / comparaison.txt .$1/k^2$$k$

De telles choses influenceront le choix de la descente coordonnée par rapport à ISTA / FISTA, par exemple.

La descente coordonnée met à jour un paramètre à la fois, tandis que la descente en gradient tente de mettre à jour tous les paramètres à la fois.

Il est difficile de spécifier exactement quand un algorithme fera mieux que l'autre. Par exemple, j'ai été très choqué d'apprendre que la descente coordonnée était à la pointe de la technologie pour LASSO. Et je n'étais pas le seul; voir diapo 17 .

Cela dit, certaines caractéristiques peuvent rendre un problème plus modifiable pour coordonner la descente:

(1) Mises à jour conditionnelles rapides. Si, pour une raison quelconque, le problème permet d'optimiser individuellement très rapidement les paramètres, la descente de coordonnées peut en faire usage. Par exemple, on peut être en mesure de mettre à jour certains paramètres en utilisant uniquement un sous-ensemble des données, ce qui réduit considérablement le coût de calcul de ces mises à jour. Un autre cas est s'il existe une solution de forme fermée pour un paramètre individuel, conditionnelle aux valeurs de tous les autres paramètres.

(2) Modes relativement indépendants pour les paramètres. Si la valeur optimale d'un paramètre est complètement indépendante des autres valeurs des paramètres, alors un tour de descente de coordonnées conduira à la solution (en supposant que chaque mise à jour de coordonnées trouve le mode actuel). D'un autre côté, si le mode pour un paramètre donné dépend très fortement d'autres valeurs de paramètre, la descente de coordonnées est très susceptible de progresser, avec de très petites mises à jour à chaque tour.

Malheureusement, pour la plupart des problèmes, (2) ne tient pas, il est donc rare que la descente de coordonnées fasse bien par rapport aux algorithmes alternatifs. Je crois que la raison pour laquelle il fonctionne bien pour LASSO est qu'il existe de nombreuses astuces que l'on peut utiliser pour appliquer la condition (1).

Pour la descente de gradient, cet algorithme fonctionnera bien si la dérivée seconde est relativement stable, un bon est sélectionné et la hors diagonale de la Hesse est relativement petite par rapport aux entrées diagonales. Ces conditions sont également rares, de sorte qu'il fonctionne généralement moins bien que les algorithmes tels que L-BFGS.$\alpha$

Je me rends compte que c'est une vieille question et a de très bonnes réponses. Je voudrais partager une expérience personnelle pratique.

$k$

• Toutes les probabilités doivent être positives.
• Tous les éléments de l'ensemble de probabilités doivent résumer à un

C'est en réalité beaucoup demander. Avec la descente de gradient, on traite généralement les contraintes via une fonction de pénalité. Ici, cela ne fonctionnera pas. Dès qu'une valeur viole l'une de ces contraintes, votre code génère généralement une sorte d'erreur numérique. Il faut donc gérer les contraintes en ne permettant jamais à l'algorithme d'optimisation de le traverser.

Il existe de nombreuses transformations que vous pouvez appliquer à votre problème pour satisfaire les contraintes afin de permettre une descente de gradient. Cependant, si vous cherchez le moyen le plus simple et le plus paresseux de l'implémenter, la descente en coordonnées est la voie à suivre:

$p_i$

• $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
• $p_i = \min(\max(p_i,0),1)$
• Mettez à jour tous les p_i:$\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i}$

Pour quelqu'un comme moi qui travaille en Python, cela signifie généralement que je dois utiliser une boucle for supplémentaire qui a un impact assez négatif sur les performances. La descente en pente me permet d'utiliser Numpy qui est optimisé en termes de performances. On peut obtenir une très bonne vitesse avec cela, cependant, ce n'est pas possible avec une descente coordonnée, donc j'utilise généralement une technique de transformation.

Donc, la conclusion est vraiment que la descente de coordonnées est l'option la plus simple pour faire face à des contraintes très strictes telles que le paramètre de taux dans la distribution de Poisson. Si son devient négatif, votre code se plaint, etc.

J'espère que cela a ajouté un peu de perspicacité.