high probability

Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method

  • Jiaming Liang
    • Categories Convex Optimization, Stochastic Programming Tags , , , , ,

    This paper proposes a stochastic proximal point method to solve a stochastic convex composite optimization problem. High probability results in stochastic optimization typically hinge on restrictive assumptions on the stochastic gradient noise, for example, sub-Gaussian distributions. Assuming only weak conditions such as bounded variance of the stochastic gradient, this paper establishes a low sample complexity … Read more

    Robust stochastic optimization with the proximal point method

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    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 … Read more