About

Raghavendra Bollapragada is an Assistant Professor in the Department of Research at The University of Texas at Austin. His research areas include Analytics and Probabilistic Modeling. His work involves developing and analyzing optimization methods, including Newton-Sketch and subsampled Newton methods, as well as nonlinear acceleration of primal-dual algorithms. He has contributed to the field through various publications on stochastic optimization, distributed optimization, and machine learning, focusing on improving computational efficiency and balancing communication and computation in large-scale systems.

Research topics

• Computer Science
• Algorithm
• Mathematical optimization
• Mathematics
• Mathematical analysis
• Applied mathematics
• Economics

Selected publications

• Negative Curvature Methods with High-Probability Complexity Guarantees for Stochastic Nonconvex Optimization

  Open MIND · 2026-03-04

  preprint

  This paper develops negative curvature methods for continuous nonlinear unconstrained optimization in stochastic settings, in which function, gradient, and Hessian information is available only through probabilistic oracles, i.e., oracles that return approximations of a certain accuracy and reliability. We introduce conditions on these oracles and design a two-step framework that systematically combines gradient and negative curvature steps. The framework employs an early-stopping mechanism to guarantee sufficient progress and uses an adaptive mechanism based on an Armijo-type criterion to select the step sizes for both steps. We establish high-probability iteration-complexity guarantees for attaining second-order stationary points, deriving explicit tail bounds that quantify the convergence neighborhood and its dependence on oracle noise. Importantly, these bounds match deterministic rates up to noise-dependent terms, and the framework recovers the deterministic results as a special case. Finally, numerical experiments demonstrate the practical benefits of exploiting negative curvature directions even in the presence of noise.

  DOI

• Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm

  Computational Optimization and Applications · 2026-02-12

  articleOpen access

  Abstract In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic inexact and stochastic 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 for both settings. To tackle large-scale problems, we develop a practical variant that utilizes the conjugate gradient method with negative curvature detection and early stopping to compute a step, a simple adaptive step size scheme, and a strategy for selecting the sample sizes of the gradient and Hessian approximations as the optimization progresses. Numerical results on two machine learning problems showcase the efficacy and efficiency of the practical method.

  PublisherOA PDFDOI

• Negative Curvature Methods with High-Probability Complexity Guarantees for Stochastic Nonconvex Optimization

  ArXiv.org · 2026-03-04

  articleOpen access

  This paper develops negative curvature methods for continuous nonlinear unconstrained optimization in stochastic settings, in which function, gradient, and Hessian information is available only through probabilistic oracles, i.e., oracles that return approximations of a certain accuracy and reliability. We introduce conditions on these oracles and design a two-step framework that systematically combines gradient and negative curvature steps. The framework employs an early-stopping mechanism to guarantee sufficient progress and uses an adaptive mechanism based on an Armijo-type criterion to select the step sizes for both steps. We establish high-probability iteration-complexity guarantees for attaining second-order stationary points, deriving explicit tail bounds that quantify the convergence neighborhood and its dependence on oracle noise. Importantly, these bounds match deterministic rates up to noise-dependent terms, and the framework recovers the deterministic results as a special case. Finally, numerical experiments demonstrate the practical benefits of exploiting negative curvature directions even in the presence of noise.

  PublisherOA PDF

• Efficient mathematical programming formulation and algorithmic framework for optimal camera placement

  Computers & Operations Research · 2026-05-01

  preprintOpen accessCorresponding
  PublisherOA PDFDOI

• Fast finite-sum optimization via cyclically-sampled Hessian averaging methods

  Mathematical Programming · 2026-04-07

  articleOpen accessSenior authorCorresponding

  Abstract We consider minimizing finite-sum 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{\tfrac{\log k}{k}}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:msqrt> <mml:mstyle> <mml:mfrac> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> <mml:mi>k</mml:mi> </mml:mfrac> </mml:mstyle> </mml:msqrt> </mml:mfenced> </mml:mrow> </mml:math> local superlinear convergence for strongly convex functions in high probability, while maintaining fixed per-iteration Hessian costs. These methods, however, require gradient exactness and strong convexity, which poses challenges for their practical implementation. To address this concern we consider Hessian-averaged methods that allow gradient inexactness via norm condition based adaptive-sampling strategies. Furthermore, to better control the error in the subsampled Hessian approximations, we utilize Hessian averaging with deterministic cyclic sampling techniques instead of random sampling, which leads to fast local superlinear convergence. We develop a comprehensive convergence theory, including global linear and sublinear convergence rates for strongly convex and nonconvex functions, respectively. Additionally, we establish an improved local superlinear convergence rate of $$\mathcal {O}\left( \tfrac{1}{k}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mfenced> <mml:mstyle> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>k</mml:mi> </mml:mfrac> </mml:mstyle> </mml:mfenced> </mml:mrow> </mml:math> . Our analysis introduces novel techniques that differ from previous probabilistic approaches. We investigate the performance of these methods on logistic regression problems, demonstrating significant improvements in convergence over similar Hessian-averaging methods that utilize stochastic sampling.

  PublisherOA PDFDOI

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

  ArXiv.org · 2025-07-19

  articleOpen access1st authorCorresponding

  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, making it computationally expensive or impractical to evaluate its gradient. To address this, we utilize gradient estimates within the proximal gradient framework. Our methods dynamically adjust the accuracy of these estimates, increasing it as the iterates approach a solution, thereby enabling high-precision solutions with minimal computational cost. We analyze the methods when the smooth component is nonconvex, convex, or strongly convex, using a biased gradient estimate. In all cases, the methods achieve the optimal iteration complexity for first-order methods. When the gradient estimate is unbiased, we further refine the analysis to show that the methods simultaneously achieve optimal iteration complexity and optimal complexity in terms of the number of stochastic gradient evaluations. Finally, we validate our theoretical results through numerical experiments.

  PublisherOA PDF

• A Stochastic Gradient Tracking Algorithm for Decentralized Optimization With Inexact Communication

  IEEE Transactions on Automatic Control · 2025-03-06 · 2 citations

  articleSenior author

  Decentralized optimization is typically studied under the assumption of noise-free transmission. However, real-world scenarios often involve the presence of noise due to factors such as additive white Gaussian noise channels or probabilistic quantization of transmitted data. These sources of noise have the potential to degrade the performance of decentralized optimization algorithms if not effectively addressed. In this article, we focus on the noisy communication setting and propose an algorithm that bridges the performance gap caused by communication noise while also mitigating other challenges like data heterogeneity. We establish theoretical results of the proposed algorithm that quantify the effect of communication noise and gradient noise on the performance of the algorithm. Notably, our algorithm achieves the optimal convergence rate for minimizing strongly convex, smooth functions in the context of inexact communication and stochastic gradients. Finally, we illustrate the superior performance of the proposed algorithm compared to its state-of-the-art counterparts on machine learning problems using MNIST and CIFAR-10 datasets.

  PublisherDOI

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

  ArXiv.org · 2025-05-26

  preprintOpen access

  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 the optimization. Such frameworks retain the advantages of deterministic optimization methods, such as fast convergence, while achieving the optimal performance of stochastic methods without the need to redesign algorithmic components. For problems with general nonlinear equality constraints, we present a framework that can employ any deterministic solver and analyze its theoretical work complexity. We then present an instance of the framework that employs a deterministic Sequential Quadratic Programming (SQP) method and that achieves optimal complexity in terms of gradient evaluations and linear system solves for this class of problems. For problems with general nonlinear constraints, we present an RA-based algorithm that employs an SQP method with robust subproblems. Finally, we demonstrate the empirical performance of the proposed framework on multi-class logistic regression problems and benchmark instances from the CUTEst test set, comparing its results to established methods from the literature.

  PublisherOA PDFDOI

• Derivative-free stochastic optimization via adaptive sampling strategies

  Optimization methods & software · 2025-09-17 · 3 citations

  article1st authorCorresponding
  PublisherDOI

• A flexible gradient tracking algorithmic framework for decentralized optimization

  Computational Optimization and Applications · 2025-05-11

  article
  PublisherDOI

Frequent coauthors

• Albert S. Berahas

  University of Michigan–Ann Arbor

  15 shared

• Jorge Nocedal

  13 shared

• Stefan M. Wild

  Lawrence Berkeley National Laboratory

  8 shared

• Richard Byrd

  University of Colorado Boulder

  7 shared

• Tyler Chen

  4 shared

• Ermin Wei

  Northwestern University

  4 shared

• Raghu Pasupathy

  4 shared

• Ping Tang

  Chinese Academy of Sciences

  3 shared