Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
From MaRDI portal
Abstract: Stochastic gradient methods (SGMs) have been widely used for solving stochastic optimization problems. A majority of existing works assume no constraints or easy-to-project constraints. In this paper, we consider convex stochastic optimization problems with expectation constraints. For these problems, it is often extremely expensive to perform projection onto the feasible set. Several SGMs in the literature can be applied to solve the expectation-constrained stochastic problems. We propose a novel primal-dual type SGM based on the Lagrangian function. Different from existing methods, our method incorporates an adaptiveness technique to speed up convergence. At each iteration, our method inquires an unbiased stochastic subgradient of the Lagrangian function, and then it renews the primal variables by an adaptive-SGM update and the dual variables by a vanilla-SGM update. We show that the proposed method has a convergence rate of in terms of the objective error and the constraint violation. Although the convergence rate is the same as those of existing SGMs, we observe its significantly faster convergence than an existing non-adaptive primal-dual SGM and a primal SGM on solving the Neyman-Pearson classification and quadratically constrained quadratic programs. Furthermore, we modify the proposed method to solve convex-concave stochastic minimax problems, for which we perform adaptive-SGM updates to both primal and dual variables. A convergence rate of is also established to the modified method for solving minimax problems in terms of primal-dual gap.
Recommendations
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- scientific article; zbMATH DE number 819402
- Spectral projected gradient method for stochastic optimization
- A fully stochastic primal-dual algorithm
- Algorithms for stochastic optimization with function or expectation constraints
Cites work
- A level-set method for convex optimization with a feasible solution path
- A Neyman–Pearson Approach to Statistical Learning
- A primal-dual algorithm with line search for general convex-concave saddle point problems
- A Sample Approximation Approach for Optimization with Probabilistic Constraints
- A Stochastic Approximation Method
- ADADELTA
- Adaptive subgradient methods for online learning and stochastic optimization
- Algorithms for stochastic optimization with function or expectation constraints
- Graph implementations for nonsmooth convex programs
- scientific article; zbMATH DE number 6617274 (Why is no real title available?)
- scientific article; zbMATH DE number 7064055 (Why is no real title available?)
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
- Lectures on stochastic programming. Modeling and theory.
- Neyman-Pearson classification, convexity and stochastic constraints
- Optimal primal-dual methods for a class of saddle point problems
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sample average approximation method for chance constrained programming: Theory and applications
- Solving variational inequalities with stochastic mirror-prox algorithm
- Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
- Stochastic first-order methods with random constraint projection
- The Scenario Approach to Robust Control Design
- Uncertain convex programs: randomized solutions and confidence levels
Cited in
(18)- APriD
- Algorithms for stochastic optimization with function or expectation constraints
- Primal-dual mirror descent method for constraint stochastic optimization problems
- SPAR: Stochastic Programming with Adversarial Recourse
- A data efficient and feasible level set method for stochastic convex optimization with expectation constraints
- Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
- Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization
- Variance reduced moving balls approximation method for smooth constrained minimization problems
- A two-phase stochastic momentum-based algorithm for nonconvex expectation-constrained optimization
- Unified convergence analysis for adaptive optimization with moving average estimator
- Stochastic-constrained stochastic optimization with Markovian data
- A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization
- Adaptive-batch stochastic gradient descent for constrained optimization based on relaxed barrier functions
- Robust stochastic gradient descent for linearly constrained problems via adaptive barrier amplification
- Tailed-average SGD: a Polyak-Ruppert modification for optimal-rate constrained optimization
- Survey on first-order algorithms for solving functional constrained optimization problems
This page was built for publication: Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2146450)
