Robust stochastic optimization with the proximal point method

Damek Davis (dsd95cornell.edu)
Dmitriy Drusvyatskiy (ddrusvuw.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