PreprintarXiv licencearXiv
Random tilts to find stationary points in stochastic convex optimization
Abstract
We consider the problem of finding stationary points of stochastic convex functions and related variational inequalities. For each, we show that regularized empirical risk minimization, coupled with a random tilting perturbation, obtains stationarity residual order √(d/n) for d-dimensional problems given n observations. We present a few complementary results that show that some dimension dependence is necessary, in distinction from standard stochastic optimization and empirical risk minimization, by providing minimax lower bounds scaling as √(log d / n).
Related
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems
- Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Maximal volume of convex bodies avoiding random points and lacunary dilates
BibTeX
@misc{areces2026random,
title = {{Random tilts to find stationary points in stochastic convex optimization}},
author = {Felipe Areces and John C. Duchi and Malo Sommers},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17798},
eprint = {2609.17798},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17798},
}
RIS
TY - UNPB
TI - Random tilts to find stationary points in stochastic convex optimization
AU - Felipe Areces
AU - John C. Duchi
AU - Malo Sommers
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17798
UR - https://arxiv.org/abs/2609.17798
AB - We consider the problem of finding stationary points of stochastic convex functions and related variational inequalities. For each, we show that regularized empirical risk minimization, coupled with a random tilting perturbation, obtains stationarity residual order √(d/n) for d-dimensional problems given n observations. We present a few complementary results that show that some dimension dependence is necessary, in distinction from standard stochastic optimization and empirical risk minimization, by providing minimax lower bounds scaling as √(log d / n).
ER -