Primal-dual stochastic gradient method for convex programs with many functional constraints

Abstract

Stochastic gradient method (SGM) has been popularly applied to solve optimization problems with objective that is stochastic or an average of many functions. Most existing works on SGMs assume that the underlying problem is unconstrained or has an easy-to-project constraint set. In this paper, we consider problems that have a stochastic objective and also many functional constraints. For such problems, it could be extremely expensive to project a point to the feasible set, or even compute subgradient and/or function value of all constraint functions. To find solutions of these problems, we propose a novel (adaptive) SGM based on the classical augmented Lagrangian function. Within every iteration, it inquires a stochastic subgradient of the objective, and a subgradient and the function value of one randomly sampled constraint function. Hence, the per-iteration complexity is low. We establish its convergence rate for convex problems and also problems with strongly convex objective. It can achieve the optimal $O(1/\sqrt{k})$ convergence rate for convex case and nearly optimal $O((\log k)/k)$ rate for strongly convex case. Numerical experiments on a sample approximation problem of the robust portfolio selection and quadratically constrained quadratic programming are conducted to demonstrate its efficiency.

One technical mistake was corrected, and a feature with adaptive learning was added to the algorithm

References in corpus (5)

• Proximal-Proximal-Gradient Method
• Algorithms for stochastic optimization with functional or expectation constraints
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• Block-Normalized Gradient Method: An Empirical Study for Training Deep Neural Network
• A Primal-Dual Parallel Method with $O(1/\epsilon )$ Convergence for Constrained Composite Convex Programs

Cited by in corpus (5)

• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
• A Randomized Nonlinear Rescaling Method in Large-Scale Constrained Convex Optimization