sample complexity

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

    Stochastic nested primal-dual method for nonconvex constrained composition optimization

  • Ling-Zi Jin
  • Xiao Wang
    • Categories Constrained Nonlinear Optimization, Data Science Algorithms, Stochastic Programming Tags , , , , , , ,

    In this paper we study the nonconvex constrained composition optimization, in which the objective contains a composition of two expected-value functions whose accurate information is normally expensive to calculate. We propose a STochastic nEsted Primal-dual (STEP) method for such problems. In each iteration, with an auxiliary variable introduced to track inner layer function values we … Read more

    Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

  • Lin Xiao
  • Junyu Zhang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , ,

    We consider the problem of minimizing composite functions of the form $f(g(x))+h(x)$, where~$f$ and~$h$ are convex functions (which can be nonsmooth) and $g$ is a smooth vector mapping. In addition, we assume that $g$ is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose … Read more

    Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

  • Lin Xiao
  • Junyu Zhang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    We consider minimization of composite functions of the form $f(g(x))+h(x)$, where $f$ and $h$ are convex functions (which can be nonsmooth) and $g$ is a smooth vector mapping. In addition, we assume that $g$ is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose … Read more

    Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions

  • Ethan Fang
  • Mengdi Wang
  • Han Liu
    • Categories Convex Optimization, Statistics, Stochastic Programming Tags , , , ,

    Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \E_v\[f_v\big(\E_w [g_w(x)]\big) \]$. In order to solve this stochastic composition problem, we propose a class … Read more