adaptive sampling

Exploiting Negative Curvature in Conjunction with Adaptive Sampling: Theoretical Results and a Practical Algorithm

  • Albert S. Berahas
  • Raghu Bollapragada
  • Wanping Dong
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic and stochastic inexact settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees … Read more

    Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods

  • Thomas O'Leary-Roseberry
  • Raghu Bollapragada
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We consider minimizing finite-sum and expectation objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast \(\mathcal{O}\left(\sqrt{\frac{\log k}{k}}\right)\) local superlinear convergence for strongly convex functions in high … Read more

    An Adaptive Sampling Sequential Quadratic Programming Method for Equality Constrained Stochastic Optimization

  • Albert S. Berahas
  • Raghu Bollapragada
  • Baoyu Zhou
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    This paper presents a methodology for using varying sample sizes in sequential quadratic programming (SQP) methods for solving equality constrained stochastic optimization problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the gradient in conjunction with inexact solutions to the SQP subproblems. Under reasonable … Read more

    Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization

  • Raghu Bollapragada
  • Stefan M. Wild
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    We consider unconstrained stochastic optimization problems with no available gradient information. Such problems arise in settings from derivative-free simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We develop modified versions of a norm … Read more

    Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization

  • Rishabh Gupta
  • Qi Zhang
    • Categories Applications - OR and Management Sciences, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. Specifically, we consider the data-driven setting in which the available data are noisy observations of optimal solutions that correspond to different instances of the linear program. We introduce a new formulation of the problem that, … Read more

    Adaptive Sampling Quasi-Newton Methods for Derivative-Free Stochastic Optimization

  • Raghu Bollapragada
  • Stefan M. Wild
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    We consider stochastic zero-order optimization problems, which arise in settings from simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We employ modified versions of a norm test and an inner product quasi-Newton test … Read more

    Adaptive Sampling Strategies for Stochastic Optimization

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    In this paper, we propose a stochastic optimization method that adaptively controls the sample size used in the computation of gradient approximations. Unlike other variance reduction techniques that either require additional storage or the regular computation of full gradients, the proposed method reduces variance by increasing the sample size as needed. The decision to increase … Read more

    The Adaptive Sampling Gradient Method: Optimizing Smooth Functions with an Inexact Oracle

  • Fatemeh Hashemi
  • Raghu Pasupathy
  • Michael Taaffe
    • Categories Nonlinear Optimization, Optimization of Simulated Systems, Stochastic Programming Tags , ,

    Consider settings such as stochastic optimization where a smooth objective function $f$ is unknown but can be estimated with an \emph{inexact oracle} such as quasi-Monte Carlo (QMC) or numerical quadrature. The inexact oracle is assumed to yield function estimates having error that decays with increasing oracle effort. For solving such problems, we present the Adaptive … Read more