Estudo teórico dos métodos de descida coordenada

Estou preparando algum material do curso sobre heurística para otimização e tenho estudado métodos de descida coordenada. A configuração é aqui uma função multivariada que você deseja otimizar. tem a propriedade restrita a qualquer variável, é fácil otimizar. Portanto, a descida de coordenadas prossegue alternando as coordenadas, fixando tudo, exceto a escolhida, e minimizando ao longo dessa coordenada. Eventualmente, as melhorias ficam lentas e você termina.$f$$f$

Minha pergunta é: existe algum estudo teórico de métodos de descida de coordenadas que fale sobre taxas de convergência e propriedades de que fazem o método funcionar bem, e assim por diante? Obviamente, não estou esperando respostas totalmente gerais, mas respostas que iluminam casos em que a heurística se sai bem seriam úteis.$f$

Além disso: a técnica de otimização alternada usada para médias pode ser vista como um exemplo de descida de coordenadas, e o algoritmo de Frank-Wolfe parece relacionado (mas não é um exemplo direto da estrutura)$k$

(Editar notas: reorganizei isso depois de surtar demais.)

A literatura sobre descida de coordenadas pode ser um pouco difícil de localizar. Aqui estão algumas razões para isso.

1. Muitas das propriedades conhecidas dos métodos de coordenadas são capturadas em teoremas gerais para métodos de descida mais gerais. Dois exemplos deste, dadas abaixo, são a convergência rápida sob forte convexidade (preensão para qualquer mais íngreme descida), e a convergência geral destes métodos (usualmente atribuída ao Zoutendijk).$l^p$

2. Nomear não é padrão. Mesmo o termo "descida mais íngreme" não é padrão. Você pode ter sucesso pesquisando qualquer um dos termos "descida cíclica das coordenadas", "descida das coordenadas", "Gauss-Seidel", "Gauss-Southwell". o uso não é consistente.

3. A variante cíclica raramente recebe menção especial. Em vez disso, geralmente apenas a melhor escolha única de coordenada é discutida. Mas isso quase sempre fornece a garantia cíclica, embora com um fator extra (número de variáveis): isso ocorre porque a maioria das análises de convergência ocorre limitando mais a melhoria de uma única etapa e você pode ignorar as coordenadas extras. Também parece difícil dizer algo geral sobre o que o cíclico compra, para que as pessoas façam a melhor coordenada e o fator geralmente possa ser verificado.$n$$n$

Taxa sob forte convexidade. O caso mais simples é que sua função objetivo é fortemente convexa. Aqui, todas as variantes de descida de gradiente têm a taxa . Isso está comprovado no livro de Boyd & Vandenberghe. A prova primeiro dá o resultado em gradiente descendente, e, em seguida, usa norma equivalência para dar o resultado para geral mais íngreme descida.$\mathcal O(\ln (1/\epsilon))$$l^p$

Restrições. Sem forte convexidade, você deve começar a ter um pouco de cuidado. Você não disse nada sobre restrições e, portanto, em geral, o mínimo pode não ser atingível. Vou dizer brevemente sobre o tópico das restrições que a abordagem padrão (com métodos de descida) é projetar em sua restrição, definir cada iteração para manter a viabilidade ou usar barreiras para rolar as restrições em sua função objetivo. No caso do primeiro, não sei como ele funciona com a descida coordenada; no caso deste último, funciona bem com descida coordenada, e essas barreiras podem ser fortemente convexas.

Mais especificamente para métodos de coordenadas, em vez de projetar, muitas pessoas simplesmente fazem com que a atualização de coordenadas mantenha a viabilidade: este é exatamente o caso do algoritmo de Frank-Wolfe e suas variantes (ou seja, usá-lo para resolver SDPs).

Também observarei brevemente que o algoritmo SMO para SVMs pode ser visto como um método de descida de coordenadas, onde você está atualizando duas variáveis ​​ao mesmo tempo e mantendo uma restrição de viabilidade enquanto o faz. A escolha das variáveis ​​é heurística neste método e, portanto, as garantias são realmente apenas as garantias cíclicas. Não tenho certeza se essa conexão aparece na literatura padrão; Aprendi sobre o método SMO com as anotações do curso de Andrew Ng e as achei bastante limpas.

Garantia geral de convergência. O que eu sei nessa configuração mais geral (para descida de coordenadas) é muito mais fraco. Primeiro, há um resultado antigo, devido a Zoutendijk, de que todas essas variantes de gradiente têm convergência garantida; você pode encontrar isso no livro de Nocedal & Wright, e também aparece em alguns dos livros de Bertsekas (no mínimo, a "programação não-linear" possui). Esses resultados são novamente para algo mais geral do que a descida de coordenadas, mas você pode especializá-los para coordenar a descida e obter a parte cíclica multiplicando por .$n$

Mais especificamente para a descida cíclica de coordenadas, há um artigo de Luo & Tseng intitulado "Na convergência do método de descida de coordenadas para minimização diferenciável convexa". Esses resultados exigem que o menor seja possível. Não há taxas aqui, apenas garantias de convergência, mas esses resultados foram aplicados a algumas configurações mais especializadas para obter taxas; por exemplo, ao impulsionar (no caso especial em que o menor é atingível), Warmuth, Mika, Raetsch e Warmuth ("na convergência da alavancagem") foram capazes de mostrar taxas de .$\mathcal O(\ln(1/\epsilon))$

Existem alguns resultados mais recentes sobre descida de coordenadas. Já vi coisas no arXiv. Além disso, luo e tseng têm alguns papéis mais recentes. mas este é o material principal.

Mais taxas de convergência no caso especial de reforço. Devido à sua importância, houve outra especialização no caso de reforço. Este é um caso especial bastante grave, pois seu objetivo pode ser escrito que é uma função univariada (convexa) e a é vetores fixos ( é a variável de otimização). Bickel, Ritov e Zakai ("alguma teoria para algoritmos de impulso generalizados") mostraram que você pode obter em geral, e há resultados mais recentes de outras pessoas mostrando . A dificuldade neles é que o infimum não é considerado atingível.$\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$$g$$(a_i)_1^m$$\lambda$$\exp(1/\epsilon^2)$$\mathcal O(1/\epsilon)$

O problema com atualizações exatas. Além disso, é muito comum que você não tenha uma atualização de coordenada única de formulário fechado. Ou a solução exata pode simplesmente não existir. Felizmente, porém, existem muitos e muitos métodos de pesquisa de linha que obtêm basicamente as mesmas garantias que uma solução exata. Esse material pode ser encontrado em textos de programação não lineares padrão, por exemplo, nos livros Bertsekas ou Nocedal & Wright mencionados acima.

Vis a vis seu segundo parágrafo: quando estes funcionam bem. Primeiro, muitas das análises acima mencionadas para trabalho em gradiente para descida de coordenadas. Então, por que nem sempre usar descida de coordenadas? A resposta é que, para muitos problemas em que a descida do gradiente é aplicável, você também pode usar os métodos de Newton, para os quais é comprovada uma convergência superior. Não sei como obter a vantagem de Newton com descida coordenada. Além disso, o alto custo dos métodos de Newton pode ser mitigado com as atualizações do Quasinewton (veja, por exemplo, LBFGS).

$l^0$$k$$k$$k$$k$$f$ que permitem convergência rápida e boa esparsidade (fiel ao seu título).

Sugiro que, olhando aqui, fizemos alguns trabalhos nesta área:

http://arxiv.org/abs/1107.2848

Felicidades

Pedro

Acabamos de publicar um artigo no arXiv ( http://arxiv.org/abs/1201.1214 ) que comprova os limites inferiores genéricos para "algoritmos estatísticos" para problemas de otimização, com cada "problema" tendo seu próprio limite inferior, dependendo do seu várias propriedades.

A descida de coordenadas (e praticamente qualquer outra coisa em que possamos pensar) pode ser vista como um algoritmo estatístico em nossa estrutura, portanto, esperamos que este documento tenha alguns resultados que serão do seu interesse.

Observe que, na otimização, "taxa de convergência" geralmente significa comportamento assintótico. Ou seja, a taxa se aplica apenas à vizinhança de soluções ideais. Nesse sentido, Luo & Tseng provaram taxas de convergência linear para algumas funções objetivas não fortemente convexas no artigo "Sobre a convergência do método de descida de coordenadas para minimização diferenciável convexa".

A taxa de convergência não assintótica, também conhecida como "complexidade da iteração", é geralmente mais útil para limitar os números de iteração dos algoritmos de minização. Para funções objetivas fortemente convexas, a complexidade da iteração dos métodos de descida de coordenadas cíclicas já é mostrada nos limites de erro de Luo & Tseng e na análise de convergência de métodos de descida viáveis: uma abordagem geral se um erro de ligação global for usado. Para problemas não fortemente convexos, temos alguns novos resultados em Complexidade da iteração de métodos viáveis ​​de descida para otimização convexa. Para ser específico, mostramos a complexidade da iteração para métodos de descida de coordenadas cíclicas em problemas como a forma dupla dos métodos SVMs e Gauss-Seidel. Além disso, os resultados também abrangem outros métodos de descida viáveis, incluindo descida em gradiente e amigos.