Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization
This addresses scalability issues in large-scale machine learning and optimization by reducing dependence on dimension, though it is an incremental improvement over existing methods.
The paper tackles the problem of high-dimensional nonconvex stochastic optimization, where sample complexity often scales linearly with dimension, by proposing dimension-insensitive stochastic first-order methods (DISFOMs) that achieve sample complexities of O((log d)/ε^4) and O((log d)^{2/3}/ε^{10/3}) for obtaining an ε-stationary point.
When the nonconvex problem is complicated by stochasticity, the sample complexity of stochastic first-order methods may depend linearly on the problem dimension, which is undesirable for large-scale problems. In this work, we propose dimension-insensitive stochastic first-order methods (DISFOMs) to address nonconvex optimization with expected-valued objective function. Our algorithms allow for non-Euclidean and non-smooth distance functions as the proximal terms. Under mild assumptions, we show that DISFOM using minibatches to estimate the gradient enjoys sample complexity of $ \mathcal{O} ( (\log d) / ε^4 ) $ to obtain an $ε$-stationary point. Furthermore, we prove that DISFOM employing variance reduction can sharpen this bound to $\mathcal{O} ( (\log d)^{2/3}/ε^{10/3} )$, which perhaps leads to the best-known sample complexity result in terms of $d$. We provide two choices of the non-smooth distance functions, both of which allow for closed-form solutions to the proximal step. Numerical experiments are conducted to illustrate the dimension insensitive property of the proposed frameworks.