Data-driven Analysis of First-Order Methods via Distributionally Robust Optimization

Jisun Park, Vinit Ranjan, Bartolomeo Stellato · 2025

Read Data-driven Analysis of First-Order Methods via Distributionally Robust Optimization by Jisun Park, Vinit Ranjan, Bartolomeo Stellato (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17834.txt.

Introduction

Jisun Park, Vinit Ranjan, and Bartolomeo Stellato analyze how well first order optimization methods perform when problems come from an unknown distribution known only through samples. Classic worst case bounds are often far too cautious compared with what users see in practice.

They combine performance estimation with robust optimization over nearby distributions, turning the analysis into a tractable conic program. Results give probabilistic guarantees for an expected score or for a risk measure focused on bad cases. Tests on quadratic problems, credit scoring data, and a sparse regression method show much tighter bounds that narrow the gap with observed behavior.

Catalog record

CREATORJisun Park, Vinit Ranjan, Bartolomeo Stellato
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-17834

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Data-driven Analysis of First-Order Methods via Distributionally Robust Optimization Jisun Park, Vinit Ranjan, Bartolomeo Stellato Abstract We consider the problem of analyzing the probabilistic performance of first-order methods when solving convex optimization problems drawn from an unknown distribution only accessible through samples. By combining performance estimation (PEP) and Wasserstein distributionally robust optimization (DRO), we formulate the analysis as a tractable semidefinite program. Our approach unifies worst-case and average-case analyses by incorporating data-driven information from the observed convergence of first-order methods on a limited number of problem instances. This yields probabilistic, data-driven performance guarantees in terms of the expectation or conditional value-at-risk of the selected performance metric. Experiments on smooth convex minimization, logistics regression, and Lasso show that our method significantly reduces the conservatism of classical worst-case bounds and narrows the gap between theoretical and empirical performance. 1 Introduction First-order methods have gained significant attention over the past decade due to their low computational cost per iteration, modest memory requirements, and ability to warm-start from previous solutions [ 4 , 60 ] . These advantages make them particularly valuable for large-scale problems in data science and machine learning, as well as embedded optimization applications in engineering and optimal control. These algorithms have been around since the 1950s [ 23 ] , and have been extended to handle nondifferentiable functions and constraints via proximal operators [ 54 ] , and composite functions via operator splitting techniques such as the alternating directions method of multipliers (ADMM) [ 10 ] , or primal-dual hybrid gradient method (PDHG) [ 12 ] . Recently, several general-purpose solvers based on first-order methods appeared in the literature, including PDLP [ 1 , 2 ] for linear programs (LPs), OSQP [ 67 ] for quadratic programs (QPs), and SCS [ 52 , 51 ] and COSMO [ 25 ] for semidefinite programs (SDPs). Despite these advances, the behavior of these algorithms are still highly sensitive to data, often exhibiting slow convergence for badly-scaled problems. To design faster and more reliable first-order methods, a central question is to understand the accuracy of the solutions returned. In most convergence analyses, this translates into estimating the worst-case accuracy after a certain number of iterations for a given function class. While most of these results focus on asymptotic convergence rates [ 6 , 49 ] , a recent line of work called the performance estimation problem (PEP) [ 21 , 69 ] , focuses on constructing finite-step guarantees by solving a semidefinite program (SDP). By defining the appropriate constraints, i.e. , interpolation conditions , this technique allows us to represent various popular convex function classes ( e.g. , strongly convex, smooth, Lipschitz, indicators) and virtually all first-order methods used in practice. This approach has led to several new results in the optimization community including tighter convergence rate proofs [ 68 , 73 ] , and even faster optimization algorithms [ 35 , 55 , 32 ] . However, the practical convergence behavior of these schemes can be very different from the best known classical or computer-assisted worst-case bounds. In some cases, first-order methods might converge significantly faster, as outlined in the following example. Example 1 (Motivating example) . Consider a least-squares problem with box constraints: \begin{array}[]{ll}\textnormal{minimize}&f(x)=(1/2)\|Ax-b\|^{2}\\ \textnormal{subject to}&0\leq x\leq 1,\end{array} (1) where A\in{\mathbf{R}}^{n\times d} , x\in{\mathbf{R}}^{d} , and b\in{\mathbf{R}}^{n} with n<d . We denote the optimal solution as x^{\star} . To solve ( 1 ), we apply projected gradient descent with step size 1/L , where L is the maximum eigenvalue of A^{T}A , obtaining iterations of the form x^{k+1}=\Pi_{[0,1]}\big(x^{k}-(1/L)\nabla f(x^{k})\big)=\Pi_{[0,1]}\big(x^{k}-(1/L)A^{T}(Ax^{k}-b)\big),\quad k=0,1,\dots, where \Pi_{[0,1]} is an elementwise projection onto the interval [0,1] . It is well-known [ 5 , 54 ] , that, for this algorithm, the worst-case convergence behavior in terms of suboptimality is f(x^{K})-f(x^{\star})\leq\frac{L}{2K}\|x^{0}-x^{\star}\|^{2}. However, if we specifically consider the problem instances of the form ( 1 ) with varying b , the actual performance can be significantly better. To see this, we construct the objective matrix A=U\Lambda V , with random orthogonal matrices U\in{\mathbf{R}}^{n\times n} and V\in{\mathbf{R}}^{d\times d} , along with rectangular matrix \Lambda\in{\mathbf{R}}^{n\times d} only with diagonal entries \Lambda_{ii} for i=1,\dots,n , drawn from the uniform distribution \mathcal{U}[0,\sqrt{L}] with L=1 . We create 1000 instances of ( 1 ) by sampling the corresponding vectors b with i.i.d. entries b_{i}\sim\mathcal{N}(0,1) . Figure 1: Convergence bound of projected gradient descent on the box-constrained least-squares problem ( 1 ). The theoretical O(K^{-1}) worst-case bound on f(x^{K})-f^{\star} is pessimistic when compared to the sample 90 th -percentile and sample average. Figure 1 shows the function-value gap across iterations for different bounds: the theoretical worst-case, the empirical average, and the 90 th -percentile across instances. This highlights a commonly observed discrepancy between worst-case convergence guarantees and actual performance observed in practice. 1.1 Contributions In this paper, we develop a data-driven performance estimation framework for analyzing the convergence of deterministic first-order methods over a distribution of convex optimization problems. By combining a priori information on the function classes considered, and a posteriori information from observing the algorithm trajectories, our data-driven technique narrows the gap between theoretical and empirical performance. Our contributions are as follows: • We combine the performance estimation framework (PEP) with data-driven Wasserstein distributionally robust optimization (DRO) to analyze performance of a first-order method over a distribution of convex optimization problems. To achieve this, we directly formulate the analysis as a tractable conic program that depends on the observed trajectories of the algorithm on a finite set of problem instances. • We establish finite-sample performance guarantees on unseen problem instances in terms of the average value, conditional value-at-risk, or worst-case value on optimality measures such as function-value gap and distance-to-solution. • Numerical experiments on quadratic minimization, logistic regression, and Lasso show that our approach significantly reduces the pessimism of state-of-the-art computer-assisted worst-case bounds. Specifically, our bounds capture convergence behaviors that the worst-case analysis is not able to guarantee, such as point convergence for smooth convex functions. In addition, we provide numerical evidence to conjecture faster probabilistic rates of convergence by fitting the bounds obtained by our procedure. 1.2 Related works Classical convergence analysis and algorithm design First-order methods have been widely adopted to solve large-scale optimization problems. Unfortunately, they can require a large number of iterations to reach high-quality solutions, especially for badly-scaled problems. This led to a significant amount of effort to analyze the worst-case performance of first-order methods under different assumptions on the problem classes involved. The convergence behavior depends critically on problem structure. Gradient descent exhibit fast linear convergence [ 43 ] or even super-linear convergence [ 71 ] when the objective function is strongly convex or satisfies error bound conditions. Without strong convexity, it converges sublinearly [ 11 ] . Similar sublinear rates hold for other methods, including the proximal point method [ 29 , 30 ] , the iterative shrinkage-thresholding algorithm (ISTA), primal-dual hybrid gradient (PDHG) [ 12 ] , and the alternating direction method of multipliers (ADMM) when applied to non-smooth convex optimization. To mitigate this slow convergence behavior, Nesterov introduced the famous fast gradient method (FGM) [ 48 ] which employs an auxiliary iterate sequence to improve worst-case convergence rates. Several extensions build on this concept: the optimized gradient method (OGM) for smooth convex minimization [

Read the complete text