{"ID":22918762,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17798","arxiv_id":"2609.17798","title":"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 $\\sqrt{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 $\\sqrt{\\log d / n}$.","short_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 $\\sqrt{d/n}$ for $d$-dimensional problems given $n$ ob...","url_abs":"https://arxiv.org/abs/2609.17798","url_pdf":"https://arxiv.org/pdf/2609.17798v1","authors":"[\"Felipe Areces\",\"John C. Duchi\",\"Malo Sommers\"]","published":"2026-09-15T20:08:31Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}