It is proved under reasonable assumptions that the stochastic proximal-gradient method reaches an $\epsilon$-KKT point within $O(\epsilon^{-2})$ iterations with high probability and implies almost-sure termination in finitely many iterations and an $O(\epsilon^{-2})$ bound on the expected iteration complexity.
Abstract
A stochastic proximal-gradient method is proposed and analyzed for solving regularized optimization problems subject to nonlinear equality constraints and nonnegativity bounds. The objective function's values and gradients are available only through inexact stochastic oracles. The method decomposes each trial step into one component that reduces linearized infeasibility and a second component that seeks optimality while preserving that reduction. Trial steps are accepted or rejected through a relaxed sufficient decrease condition subject to stochastic merit function evaluations. Without assuming unbiasedness of stochastic gradient estimates, it is proved under reasonable assumptions that the method reaches an $\epsilon$-KKT point within $O(\epsilon^{-2})$ iterations with high probability. This guarantee further implies almost-sure termination in finitely many iterations and an $O(\epsilon^{-2})$ bound on the expected iteration complexity.
We study difference-of-convex optimization problems with several composite inequality constraints and develop a majorization-guided switching proximal gradient (MGSPG) method. Specifically, at each feasible outer point, quadratic majorization and linearization yield a strongly convex composite surrogate problem. To sol...
Yun-Cheng Liu, Chuang-Liang Zhang, Bo Yang· 0 citations
We develop accelerated gradient-free methods for stochastic convex optimization with constraints defined by expectations. Our batched primal-dual sliding method uses two-point evaluations sharing a random sample and guarantees expected objective error and expected maximum constraint violation at most $\varepsilon$. It...
Vadim Abronin, A. Gasnikov, D. Dvinskikh· 0 citations
Last-iterate convergence guarantees for stochastic gradient methods have attracted significant attention as practical implementations typically return the last iterate instead of an average of the iterates. In this paper, we study two approaches for analyzing the last-iterate convergence of proximal and projected stoch...
Kevin Kurian Thomas Vaidyan, Ahmet Alacaoglu, M. Friedlander· 0 citations
The Stochastic Frank–Wolfe (SFW) algorithm is proposed, a projection-free framework that leverages linear minimization oracles to bypass expensive projection operations and achieves rigorous convergence rate guarantees for both convex and non-convex objectives.
Yong Zhao, Yue-Lei Zhu, Wang Chen et al.· Positivity (Dordrecht)· 0 citations
In this paper, we propose a variance-reduced stochastic quasi-Newton sequential quadratic constrained quadratic programming method (VR-QN-SQCQP) for finite-sum nonlinear optimization with equality and inequality constraints. Exact nonlinear-constraint Hessians are replaced entirely by safeguarded symmetric rank-one (SR...
We study first-order optimization with inexact gradients whose errors combine a component proportional to the true gradient norm and a uniformly bounded absolute component. We develop an adaptive gradient descent scheme that selects estimates of the smoothness constant and both error parameters through a computable bac...
A. Vasin, A. Tyurin, A. Gasnikov· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.