Etude théorique des méthodes de descente coordonnée

Je prépare du matériel de cours sur l'heuristique pour l'optimisation et j'ai étudié les méthodes de descente de coordonnées. Le réglage est ici une fonction multivariée que vous souhaitez optimiser. f a la propriété qui se limite à une seule variable, il est facile à optimiser. Ainsi, la descente de coordonnées se poursuit en parcourant les coordonnées, en fixant tout sauf celui choisi et en minimisant le long de cette coordonnée. Finalement, les améliorations ralentissent et s'arrêtent.$f$$f$

Ma question est la suivante: existe-t-il une étude théorique des méthodes de descente de coordonnées qui parle des taux de convergence et des propriétés de qui font bien fonctionner la méthode, etc.? Évidemment, je ne m'attends pas à des réponses entièrement générales, mais des réponses qui éclairent les cas où l'heuristique fonctionne bien seraient utiles.$f$

À part: la technique d'optimisation alternée utilisée pour les moyens peut être considérée comme un exemple de descente de coordonnées, et l' algorithme de Frank-Wolfe semble lié (mais n'est pas un exemple direct du cadre)$k$

(Modifier les notes: j'ai réorganisé cela après avoir paniqué à sa longueur.)

La littérature sur la descente coordonnée peut être un peu difficile à retrouver. Voici quelques raisons à cela.

1. De nombreuses propriétés connues des méthodes de coordonnées sont capturées dans des théorèmes généraux pour des méthodes de descente plus générales. Deux exemples de cela, donnés ci-dessous, sont la convergence rapide sous forte convexité (maintenue pour toute descente plus raide), et la convergence générale de ces méthodes (généralement attribuée à Zoutendijk).$l^p$

2. La dénomination n'est pas standard. Même le terme "descente la plus raide" n'est pas standard. Vous pouvez réussir à googler l'un des termes "descente de coordonnées cycliques", "descente de coordonnées", "Gauss-Seidel", "Gauss-Southwell". l'utilisation n'est pas cohérente.

3. La variante cyclique reçoit rarement une mention spéciale. Au lieu de cela, généralement, seul le meilleur choix unique de coordonnées est discuté. Mais cela donne presque toujours la garantie cyclique, mais avec un facteur supplémentaire (nombre de variables): c'est parce que la plupart des analyses de convergence procèdent en limitant l'amélioration d'une étape, et vous pouvez ignorer les coordonnées supplémentaires. Il semble également difficile de dire quoi que ce soit de général sur ce que le cyclique vous achète, donc les gens font juste la meilleure coordonnée et le facteur n peut généralement être vérifié.$n$$n$

Taux sous forte convexité. Le cas le plus simple est que votre fonction objectif est fortement convexe. Ici, toutes les variantes de descente de gradient ont le taux . Cela est prouvé dans le livre de Boyd & Vandenberghe. La preuve donne d'abord le résultat de la descente de gradient, puis utilise l'équivalence de norme pour donner le résultat de la descente générale l p la plus raide.$\mathcal O(\ln (1/\epsilon))$$l^p$

Contraintes. Sans forte convexité, vous devez commencer à être un peu prudent. Vous n'avez rien dit sur les contraintes, et donc en général, l'infimum peut ne pas être atteignable. Je dirai brièvement au sujet des contraintes que l'approche standard (avec les méthodes de descente) consiste à projeter sur votre ensemble de contraintes à chaque itération pour maintenir la faisabilité, ou à utiliser des barrières pour intégrer les contraintes dans votre fonction objectif. Dans le cas du premier, je ne sais pas comment ça joue avec la descente coordonnée; dans ce dernier cas, cela fonctionne très bien avec une descente coordonnée, et ces barrières peuvent être fortement convexes.

Plus spécifiquement pour les méthodes de coordonnées, plutôt que de projeter, beaucoup de gens font simplement que la mise à jour des coordonnées reste faisable: c'est par exemple exactement le cas avec l'algorithme de Frank-Wolfe et ses variantes (c'est-à-dire en l'utilisant pour résoudre les SDP).

Je noterai également brièvement que l'algorithme SMO pour les SVM peut être considéré comme une méthode de descente de coordonnées, où vous mettez à jour deux variables à la fois et conservez une contrainte de faisabilité pendant que vous le faites. Le choix des variables est heuristique dans cette méthode, et donc les garanties ne sont vraiment que les garanties cycliques. Je ne sais pas si cette connexion apparaît dans la littérature standard; J'ai appris la méthode SMO grâce aux notes de cours d'Andrew Ng et je les ai trouvées assez propres.

Garantie de convergence générale.$n$

$\mathcal O(\ln(1/\epsilon))$

Il y a des résultats plus récents sur la descente de coordonnées, j'ai vu des trucs sur arXiv. De plus, luo & tseng ont des papiers plus récents. mais c'est l'essentiel.

$\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$$g$$(a_i)_1^m$$\lambda$$\exp(1/\epsilon^2)$$\mathcal O(1/\epsilon)$

Le problème avec les mises à jour exactes. En outre, il arrive très souvent que vous n'ayez pas de mise à jour de coordonnées uniques de forme fermée. Ou la solution exacte peut tout simplement ne pas exister. Mais heureusement, il existe de très nombreuses méthodes de recherche de ligne qui obtiennent essentiellement les mêmes garanties qu'une solution exacte. Ce matériel peut être trouvé dans des textes de programmation non linéaire standard, par exemple dans les livres de Bertsekas ou Nocedal & Wright mentionnés ci-dessus.

Vis à vis de votre deuxième paragraphe: quand ceux-ci fonctionnent bien. Tout d'abord, bon nombre des analyses mentionnées ci-dessus pour le travail de gradient pour la descente de coordonnées. Alors pourquoi ne pas toujours utiliser la descente coordonnée? La réponse est que pour de nombreux problèmes où la descente de gradient est applicable, vous pouvez également utiliser des méthodes de Newton, pour lesquelles une convergence supérieure peut être prouvée. Je ne connais aucun moyen d'obtenir l'avantage de Newton avec une descente coordonnée. De plus, le coût élevé des méthodes Newton peut être atténué avec les mises à jour de Quasinewton (voir par exemple LBFGS).

$l^0$$k$$k$$k$$k$ . Il y a un grand article sur ce sujet, par Shalev-Shwartz, Srebro et Zhang, intitulé "trading precision for sparsity in optimization problems with sparsity contraintes". Plus précisément au deuxième paragraphe de votre question, cet article donne de plus amples$f$

Je suggère de regarder ici, nous avons fait du travail dans ce domaine:

http://arxiv.org/abs/1107.2848

À votre santé

Peter

Nous venons de publier un article sur arXiv ( http://arxiv.org/abs/1201.1214 ) qui prouve les limites inférieures génériques des «algorithmes statistiques» pour les problèmes d'optimisation, chaque «problème» ayant sa propre limite inférieure en fonction de son propriétés diverses.

La descente coordonnée (et à peu près tout ce à quoi nous pouvons penser) peut être considérée comme un algorithme statistique dans notre cadre, donc j'espère que ce document a des résultats qui vous intéresseront.

Notez que dans l'optimisation, le "taux de convergence" signifie généralement un comportement asymptotique. Autrement dit, le taux ne s'applique qu'au voisinage des solutions optimales. Dans ce sens, Luo & Tseng ont démontré des taux de convergence linéaires pour certaines fonctions objectives non fortement convexes dans l'article "Sur la convergence de la méthode de descente de coordonnées pour la minimisation convexe différentiable".

Le taux de convergence non asymptotique, également appelé "complexité d'itération", est généralement plus utile pour délimiter le nombre d'itérations d'algorithmes de minalisation. Pour les fonctions objectives fortement convexes, la complexité d'itération des méthodes de descente de coordonnées cycliques est déjà montrée dans les limites d'erreur de Luo & Tseng et l'analyse de convergence des méthodes de descente réalisables: une approche générale si une limite d'erreur globale est utilisée. Pour les problèmes non fortement convexes, nous avons de nouveaux résultats dans la complexité d'itération des méthodes de descente réalisables pour l'optimisation convexe. Pour être précis, nous avons montré la complexité d'itération des méthodes de descente de coordonnées cycliques sur des problèmes tels que la double forme des SVM et les méthodes de Gauss-Seidel. De plus, les résultats couvrent également d'autres méthodes de descente possibles, y compris la descente en pente et les amis.