An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems

Résumé

In this work, we revisit the problem of solving large-scale semidefinite programs using randomized first-order methods and stochastic smoothing. We introduce two oblivious stochastic mirror descent algorithms based on a complementary composite setting. One algorithm is designed for non-smooth objectives, while an accelerated version is tailored for smooth objectives. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. For the non-smooth case with $\mathcal{M}-$bounded oracles, we prove a convergence rate of $ O( {\mathcal{M}}/{\sqrt{T}} ) $. For the $L$-smooth case with a feasible set bounded by $D$, we derive a convergence rate of $ O( {L^2 D^2}/{(T^{2}\sqrt{T})} + {(D_0^2+\sigma^2)}/{\sqrt{T}} )$, where $D_0$ is the starting distance to an optimal solution, and $ \sigma^2$ is the stochastic oracle variance. These rates had only been obtained so far by either assuming prior knowledge of the Lipschitz constant or the starting distance to an optimal solution. We further show how to extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.

Dates et versions

hal-04230909 , version 1 (06-10-2023)

Identifiants

Citer

Clément Lezane, Cristóbal Guzmán, Alexandre d'Aspremont. An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems. 2023. ⟨hal-04230909⟩
17 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More