Publications

Preprints

1. An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit

   Manu Upadhyaya, Daniel Berg Thomsen, Aymeric Dieuleveut, and Adrien B. Taylor

   2026

   Abs arXiv

   We introduce Prox-ITEM, an optimal proximal gradient method for minimizing f + g, where f is smooth and strongly convex, and g is convex, proper, and lower semicontinuous. In the smooth case g = 0, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for f and an arbitrary number of proximal-oracle calls for g. We also identify the stationary limit of Prox-ITEM, denoted Prox-TMM, which gives a proximal extension of the triple momentum method (TMM) to the composite setting and achieves the corresponding TMM distance-convergence rate.

2. The Chambolle-Pock method converges weakly with \(0 < θ\le 1/2\,\,\)and \(τσ\|L\|^2 < 4θ(2-θ)/(1 - 2θ+ 9θ^2 - 4θ^3)\)

   Manu Upadhyaya

   2026

   Abs arXiv

   The Chambolle-Pock method, also known as the primal-dual hybrid gradient method, is a standard first-order algorithm for convex-concave saddle-point problems and composite convex optimization. We establish weak sequential convergence of its primal-dual iterates in real Hilbert spaces for every \(0 < θ\le 1/2\,\,\)whenever \(τσ\|L\|^2 < 4θ(2-θ)/(1 - 2θ+ 9θ^2 - 4θ^3)\). This extends the weak-convergence theory to a previously unexplored range of extrapolation parameters.

3. The AutoLyap software suite for computer-assisted Lyapunov analyses of first-order methods

   Manu Upadhyaya, Shuvomoy Das Gupta, Adrien B. Taylor, Sebastian Banert, and Pontus Giselsson

   2026

   Abs arXiv Website

   We introduce AutoLyap, a software suite that assists with Lyapunov analyses of a wide class of first-order methods for structured optimization and inclusion problems. Lyapunov analyses are structured proof patterns, with historical roots in the study of dynamical systems, commonly used to establish convergence results for first-order methods. Building on previous work, the core idea behind AutoLyap is to recast the verification of the existence of a Lyapunov analysis as a semidefinite program (SDP), which can then be solved numerically using standard SDP solvers. Users of the package specify (i) the class of optimization or inclusion problems, (ii) the first-order method in question, and (iii) the type of Lyapunov analysis they wish to test. Once these inputs are provided, AutoLyap handles the SDP modeling and proceeds to solve the SDP numerically. We use the package to numerically verify and extend several convergence results. AutoLyap is currently available in Python and Julia.

Journal articles

1. A Lyapunov analysis of Korpelevich’s extragradient method with fast and flexible extensions

   Manu Upadhyaya, Puya Latafat, and Pontus Giselsson

   Mathematical Programming, 2026

   Abs DOI arXiv

   We develop a Lyapunov-based analysis of Korpelevich’s extragradient method and show that it achieves an \(o(1/k)\,\,\)last-iterate convergence rate of the constructed Lyapunov function. This Lyapunov function simultaneously upper bounds several standard measures of optimality, which allows our analysis to sharpen existing last-iterate convergence guarantees for these measures. Moreover, the same analysis enables the design of a class of flexible extensions of the extragradient method in which extragradient steps are adaptively blended with user-specified directions via a Lyapunov-guided line-search procedure. These extensions retain global convergence under practical assumptions and can attain superlinear rates when the directions are chosen appropriately. Numerical experiments confirm the simplicity and efficiency of the proposed framework.

2. Automated tight Lyapunov analysis for first-order methods

   Manu Upadhyaya, Sebastian Banert, Adrien B. Taylor, and Pontus Giselsson

   Mathematical Programming, 2025

   Abs DOI arXiv

   We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and (iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions. We present a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality within a predefined class of Lyapunov inequalities, which amounts to solving a small-sized semidefinite program. We showcase our methodology on several first-order methods that fit the framework. Most notably, our methodology allows us to significantly extend the region of parameter choices that allow for duality gap convergence in the Chambolle-Pock method when the linear operator is the identity mapping.

3. The Chambolle-Pock method converges weakly with \(θ> 1/2\,\,\)and \(τσ\|L\|^2 < 4/(1+2θ)\)

   Sebastian Banert, Manu Upadhyaya, and Pontus Giselsson

   Optimization Letters, 2025

   Abs DOI arXiv

   The Chambolle-Pock method is a versatile three-parameter algorithm designed to solve a broad class of composite convex optimization problems, which encompass two proper, lower semicontinuous, and convex functions, along with a linear operator \(L\). The functions are accessed via their proximal operators, while the linear operator is evaluated in a forward manner. Among the three algorithm parameters \(τ\), \(σ\), and \(θ\); \(τ\), \(σ> 0\,\,\)serve as step sizes for the proximal operators, and \(θ\,\,\)is an extrapolation step parameter. Previous convergence results have been based on the assumption that \(θ= 1\). We demonstrate that weak convergence is achievable whenever \(θ> 1/2\,\,\)and \(τσ\|L\|^2 < 4/(1+2θ)\). Moreover, we establish tightness of the step size bound by providing an example that is nonconvergent whenever the second bound is violated.

Conference proceedings

1. Finding simple proofs for first-order optimization

   Daniel Berg Thomsen, Manu Upadhyaya, Baptiste Goujaud, Aymeric Dieuleveut, and Adrien B. Taylor

   NeurIPS, 2026

   Short version accepted at the ICML 2026 AI4Research Workshop.

   Abs arXiv

   Starting from dense dual certificates produced by performance estimation problems, this work formulates a second optimization stage to uncover simpler proof structures. It combines exhaustive sparsification, weighted \(\ell_1\)-type heuristics, and semidefinite programming to remove redundant inequalities and reveal reusable arguments for gradient, proximal, and accelerated methods. The resulting certificates expose compact patterns and intermediate Lyapunov lemmas, reducing the effort needed for human interpretation and formalization.

2. The feeling of success: Does touch sensing help predict grasp outcomes?

   Roberto Calandra, Andrew Owens, Manu Upadhyaya, Wenzhen Yuan, Justin Lin, Edward H. Adelson, and Sergey Levine

   Conference on Robot Learning (CoRL), 2017

   Abs arXiv Website

   A successful grasp requires careful balancing of the contact forces. Deducing whether a particular grasp will be successful from indirect measurements, such as vision, is therefore quite challenging, and direct sensing of contacts through touch sensing provides an appealing avenue toward more successful and consistent robotic grasping. However, in order to fully evaluate the value of touch sensing for grasp outcome prediction, we must understand how touch sensing can influence outcome prediction accuracy when combined with other modalities. Doing so using conventional model-based techniques is exceptionally difficult. In this work, we investigate the question of whether touch sensing aids in predicting grasp outcomes within a multimodal sensing framework that combines vision and touch. To that end, we collected more than 9,000 grasping trials using a two-finger gripper equipped with GelSight high-resolution tactile sensors on each finger, and evaluated visuo-tactile deep neural network models to directly predict grasp outcomes from either modality individually, and from both modalities together. Our experimental results indicate that incorporating tactile readings substantially improve grasping performance.

Theses

1. Lyapunov analyses for first-order methods: Theory, automation, and algorithm design

   Manu Upadhyaya

   PhD thesis, 2025

   Abs HTML

   This thesis, comprising four research papers, contributes to the field of systematic and computer-aided analyses and design of first-order methods. The first two papers focus on developing new methodologies, while the remaining two apply these techniques to refine complexity and convergence results, as well as to design new methods. A central theme of the work is the use of Lyapunov-type analyses, a structured proof technique with historical roots in the study of dynamical systems, which is widely used to establish complexity and convergence properties of first-order methods.

2. Covariance matrix regularization for portfolio selection: Achieving desired risk

   Manu Upadhyaya

   Master’s thesis, 2020

   Abs HTML

   The modus operandi of most asset managers is to promise clients an annual risk target, where risk is measured by the realized standard deviation of portfolio returns. Moreover, Markowitz (1952) portfolio selection requires an estimate of the covariance matrix of the returns of the financial instruments under consideration. To address both these problems, we develop a data-driven method for covariance matrix regularization. The data-driven method critically depends on a novel risk-targeting loss function. In addition, the risk targeting loss function is analyzed under large-dimensional asymptotics, resulting in an asymptotically optimal covariance matrix regularization. In an ex-post analysis, using historical price data from multiple future markets, the data-driven method outperforms other regularization methods compared against.