Optimization Online


Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints

Mengdi Wang (mengdiw***at***princeton.edu)
Yichen Chen (yichenc***at***Princeton.EDU)

Abstract: Consider convex optimization problems subject to a large number of constraints. We focus on stochastic problems in which the objective takes the form of expected values and the feasible set is the intersection of a large number of convex sets. We propose a class of algorithms that perform both stochastic gradient descent and random feasibility updates simultaneously. At every iteration, the algorithms sample a number of projection points onto a randomly selected small subsets of all constraints. Three feasibility update schemes are considered: averaging over random projected points, projecting onto the most distant sample, projecting onto a special polyhedral set constructed based on sample points. We prove the almost sure convergence of these algorithms, and analyze the iterates' feasibility error and optimality error, respectively. We provide new convergence rate benchmarks for stochastic first-order optimization with many constraints. The rate analysis and numerical experiments reveal that the algorithm using the polyhedral-set projection scheme is the most efficient one within known algorithms.

Keywords: stochastic gradient, convex optimization, stochastic algorithms, random projection

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 11/10/2015
Entry Accepted: 11/10/2015
Entry Last Modified: 04/13/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society