Um Novo Algoritmo com Menor Complexidade para Otimização Bilevel

Vários algoritmos estocásticos foram propostos para resolver o problema de otimização bilevel, onde a função de nível inferior é fortemente convexa e a função de valor de nível superior é não convexa. Em particular, algoritmos existentes sem inversão de Hessiana que utilizam recursão de momento ou técnicas de redução de variância podem alcançar um ponto -estacionário com uma complexidade de O (^-1. 5) sob condições usuais de suavidade. No entanto, O (^-1. 5) é uma complexidade maior do que O (^-1. 5). Como fazer um algoritmo sem inversão de Hessiana alcançar a complexidade de O (^-1. 5) sob condições usuais de suavidade continua sendo um problema não resolvido. Neste artigo, propomos um novo algoritmo sem inversão de Hessiana baseado no método de descida de gradiente estocástico projetada e técnica de redução de variância do SPIDER. Este algoritmo pode alcançar uma complexidade de O (^-1. 5) sob condições usuais de suavidade, independentemente de operar em uma estrutura de laço único completo ou em laço duplo. Finalmente, validamos nossos resultados teóricos por meio de experimentos sintéticos e demonstramos a eficiência do nosso algoritmo em algumas aplicações de aprendizado de máquina.