variance reduction

Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees

  • Zhaosong Lu
  • Sanyou Mei
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    \(\) In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an \(\epsilon\)-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy \(\epsilon\). However, in many practical applications, it is crucial that the constraints be nearly satisfied with … Read more

    Doubly stochastic primal dual splitting algorithm with variance reduction for saddle point problems

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    The structured saddle-point problem involving the infimal convolution in real Hilbert spaces finds applicability in many applied mathematics disciplines. For this purpose, we develop a stochastic primal-dual splitting algorithm with loopless variance-reduction for solving this generic problem. We first prove the weak almost sure convergence of the iterates. We then demonstrate that our algorithm achieves … Read more

    Adaptive Importance Sampling Based Surrogation Methods for Bayesian Hierarchical Models, via Logarithmic Integral Optimization

  • Ziyu He
  • Junyi Liu
  • Jong-Shi Pang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

    We explore Maximum a Posteriori inference of Bayesian Hierarchical Models (BHMs) with intractable normalizers, which are increasingly prevalent in contemporary applications and pose computational challenges when combined with nonconvexity and nondifferentiability. To address these, we propose the Adaptive Importance Sampling-based Surrogation method, which efficiently handles nonconvexity and nondifferentiability while improving the sampling approximation of the … Read more

    Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

  • Jiajun Xu
  • Suvrajeet Sen
    • Categories Applications - Science and Engineering, Dynamic Programming, Stochastic Programming Tags , , , , ,

    This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

    Accelerating Stochastic Sequential Quadratic Programming for Equality Constrained Optimization using Predictive Variance Reduction

  • Albert S. Berahas
  • Jiahao Shi
  • Zihong Yi
  • Baoyu Zhou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we propose a stochastic variance reduction method for solving equality constrained optimization problems. Specifically, we develop a method based on the sequential quadratic programming paradigm that utilizes gradient approximations via predictive variance reduction techniques. Under reasonable assumptions, we prove that a measure of first-order stationarity evaluated at the iterates generated by our … Read more

    Training Structured Neural Networks Through Manifold Identification and Variance Reduction

  • Zih-Syuan Huang
  • Ching-pei Lee
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper proposes an algorithm, RMDA, for training neural networks (NNs) with a regularization term for promoting desired structures. RMDA does not incur computation additional to proximal SGD with momentum, and achieves variance reduction without requiring the objective function to be of the finite-sum form. Through the tool of manifold identification from nonlinear optimization, 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

    Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters

  • Filip Hanzely
    • Categories Convex Optimization, Stochastic Programming Tags , , , , ,

    Many key problems in machine learning and data science are routinely modeled as optimization problems and solved via optimization algorithms. With the increase of the volume of data and the size and complexity of the statistical models used to formulate these often ill-conditioned optimization tasks, there is a need for new efficient algorithms able to … 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

    Variance Reduction of Stochastic Gradients Without Full Gradient Evaluation

  • Florian Jarre
  • Felix Lieder
    • Categories Unconstrained Optimization Tags ,

    A standard concept for reducing the variance of stochastic gradient approximations is based on full gradient evaluations every now and then. In this paper an approach is considered that — while approximating a local minimizer of a sum of functions — also generates approximations of the gradient and the function values without relying on full … Read more