Raghu Bollapragada

On the Convergence and Complexity of Proximal Gradient and Accelerated Proximal Gradient Methods under Adaptive Gradient Estimation

  • Raghu Bollapragada
  • Shagun Gupta
    • Categories Nonlinear Optimization, Optimization in Data Science, Stochastic Programming Tags , , , ,

    In this paper, we propose a proximal gradient method and an accelerated proximal gradient method for solving composite optimization problems, where the objective function is the sum of a smooth and a convex, possibly nonsmooth, function. We consider settings where the smooth component is either a finite-sum function or an expectation of a stochastic function, … Read more

    Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints

  • Shagun Gupta
  • Raghu Bollapragada
  • Albert S. Berahas
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    In this paper, we propose a framework based on the Retrospective Approximation (RA) paradigm to solve optimization problems with a stochastic objective function and general nonlinear deterministic constraints. This framework sequentially constructs increasingly accurate approximations of the true problems which are solved to a specified accuracy via a deterministic solver, thereby decoupling the uncertainty from … Read more

    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

    Modified Line Search Sequential Quadratic Methods for Equality-Constrained Optimization with Unified Global and Local Convergence Guarantees

  • Albert S. Berahas
  • Raghu Bollapragada
  • Jiahao Shi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Other Topics Tags , ,

    In this paper, we propose a method that has foundations in the line search sequential quadratic programming paradigm for solving general nonlinear equality constrained optimization problems. The method employs a carefully designed modified line search strategy that utilizes second-order information of both the objective and constraint functions, as required, to mitigate the Maratos effect. Contrary … Read more

    Adaptive Consensus: A network pruning approach for decentralized optimization

  • Suhail Mohmad Shah
  • Albert S. Berahas
  • Raghu Bollapragada
    • Categories Convex Optimization, Network Optimization, Nonlinear Optimization Tags , ,

    We consider network-based decentralized optimization problems, where each node in the network possesses a local function and the objective is to collectively attain a consensus solution that minimizes the sum of all the local functions. A major challenge in decentralized optimization is the reliance on communication which remains a considerable bottleneck in many applications. To … Read more

    Balancing Communication and Computation in Gradient Tracking Algorithms for Decentralized Optimization

  • Albert S. Berahas
  • Raghu Bollapragada
  • Shagun Gupta
    • Categories Convex Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    Gradient tracking methods have emerged as one of the most popular approaches for solving decentralized optimization problems over networks. In this setting, each node in the network has a portion of the global objective function, and the goal is to collectively optimize this function. At every iteration, gradient tracking methods perform two operations (steps): (1) … 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

    Constrained and Composite Optimization via Adaptive Sampling Methods

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
  • Yuchen Xie
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming

    The motivation for this paper stems from the desire to develop an adaptive sampling method for solving constrained optimization problems in which the objective function is stochastic and the constraints are deterministic. The method proposed in this paper is a proximal gradient method that can also be applied to the composite optimization problem min f(x) … Read more