Optimization Online


Robust stochastic optimization with the proximal point method

Damek Davis (dsd95***at***cornell.edu)
Dmitriy Drusvyatskiy (ddrusv***at***uw.edu)

Abstract: Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. In this work, we show that a wide class of such algorithms on strongly convex problems can be augmented with sub-exponential confidence bounds at an overhead cost that is only polylogarithmic in the condition number and the confidence level. We discuss consequences both for streaming and offline algorithms.

Keywords: stochastic, proximal point, acceleration, high probability, median of means

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Stochastic Programming

Citation: 07/2019

Download: [PDF]

Entry Submitted: 07/31/2019
Entry Accepted: 07/31/2019
Entry Last Modified: 08/01/2019

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