Stochastic first-order methods with random constraint projection

Mengdi Wang, Dimitri P. Bertsekas

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

We consider convex optimization problems with structures that are suitable for sequential treatment or online sampling. In particular, we focus on problems where the objective function is an expected value, and the constraint set is the intersection of a large number of simpler sets. We propose an algorithmic framework for stochastic first-order methods using random projection/proximal updates and random constraint updates, which contain as special cases several known algorithms as well as many new algorithms. To analyze the convergence of these algorithms in a unified manner, we prove a general coupled convergence theorem. It states that the convergence is obtained from an interplay between two coupled processes: progress toward feasibility and progress toward optimality. Under suitable stepsize assumptions, we show that the optimality error decreases at a rate of O(1/√ k) and the feasibility error decreases at a rate of O(log k/k). We also consider a number of typical sampling processes for generating stochastic first-order information and random constraints, which are common in data-intensive applications, online learning, and simulation optimization. By using the coupled convergence theorem as a modular architecture, we are able to analyze the convergence of stochastic algorithms that use arbitrary combinations of these sampling processes.

Original languageEnglish (US)
Pages (from-to)681-717
Number of pages37
JournalSIAM Journal on Optimization
Volume26
Issue number1
DOIs
StatePublished - Jan 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Feasibility
  • Large-scale optimization
  • Online optimization
  • Projection
  • Proximal
  • Randomized algorithm
  • Stochastic approximation
  • Subgradient

Fingerprint Dive into the research topics of 'Stochastic first-order methods with random constraint projection'. Together they form a unique fingerprint.

  • Cite this