We consider the problem of finding stationary points for stochastic convex optimization problems. Rather than surrogates to stationarity, such as a proximity-to-stationarity guarantee or small gradient of the Moreau envelope, we ask for a stronger notion: that the subdifferential of the objective actually contains a small element. This criterion is non-trivial, because subdifferentials of convex functions fail to converge uniformly, even in arbitrarily small neighborhoods of the optimum. Our convergence guarantees rely on dimension theory to decompose the graph of the subdifferential of a convex function, showing how stochastic sampling preserves"pieces"of these graphs, and allowing effective application of proximal-point-like methods.
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...
Felipe Areces, John C. Duchi, Malo Sommers· 0 citations
We analyze a stochastic Newton optimization scheme for locating the unique global minimizer of a general nonconvex objective function. The method couples a Newton algorithm to additive Gaussian noise with state-dependent variance. In the bounded domain setting, we prove global almost sure convergence. The proof is base...
This paper studies stochastic algorithms for minimizing paraconvex functions, a function class that generalizes weakly convex functions and includes, for instance, H\"older smooth functions and compositions of convex functions with H\"older smooth maps. We first establish the convergence of the stochastic subgradient m...
This work considers a quadratic minmax problem with coupled inner constraints and proposes a method to compute a class of stationary points and shows in particular that the method is polynomial in the special case where the inner feasible set of the authors' constrained minmax problem is independent from outer variable...
Stefano Cipolla, O. Stein, Alain B. Zemkoho· 1 citation
We investigate the optimization problem of minimizing a nonsmooth function that satisfies a nonsmooth version of the descent lemma over a nonempty and closed but not necessarily convex set. The objective function belongs to the class of upper-$\mathcal{C}^2$ functions, whereas the constraints may promote a sparse or lo...
Christian Kanzow, Jannis Krüger, Leo Lehmann· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
