Parameter-free Stochastic Optimization of Variationally Coherent Functions
It provides a parameter-free algorithm that simultaneously guarantees convergence for non-convex functions and near-optimal rates for convex functions, addressing a bottleneck in stochastic optimization.
The paper tackles the problem of first-order stochastic optimization for a broad class of functions, including convex and non-convex variationally coherent ones, achieving almost sure convergence to the global minimizer and an expected suboptimality gap of ̃O(||x* - x0|| T^{-1/2+ε}) for convex functions.
We design and analyze an algorithm for first-order stochastic optimization of a large class of functions on $\mathbb{R}^d$. In particular, we consider the \emph{variationally coherent} functions which can be convex or non-convex. The iterates of our algorithm on variationally coherent functions converge almost surely to the global minimizer $\boldsymbol{x}^*$. Additionally, the very same algorithm with the same hyperparameters, after $T$ iterations guarantees on convex functions that the expected suboptimality gap is bounded by $\widetilde{O}(\|\boldsymbol{x}^* - \boldsymbol{x}_0\| T^{-1/2+ε})$ for any $ε>0$. It is the first algorithm to achieve both these properties at the same time. Also, the rate for convex functions essentially matches the performance of parameter-free algorithms. Our algorithm is an instance of the Follow The Regularized Leader algorithm with the added twist of using \emph{rescaled gradients} and time-varying linearithmic regularizers.