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

2025/11/21 by Jisun Park, Park, Jisun, Vinit Ranjan +3 · 1 voice
Computer Science · Decision Sciences · Engineering · #math.OC

paper · pdf · doi:10.48550/arxiv.2511.17834

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 and Wasserstein distributionally robust optimization, we formulate the analysis as a tractable conic 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 convex quadratic minimization and Lasso show that our method significantly reduces the conservatism of classical worst-case bounds and narrows the gap between theoretical and empirical performance.

Citations

• Subgradient Methods for Nonsmooth Convex Functions with Adversarial Errors
• Data-Driven Performance Guarantees for Parametric Optimization Problems
• Optimal Smoothed Analysis of the Simplex Method
• High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming
• Exact Verification of First-Order Methods via Mixed-Integer Linear Programming
• A Proof of the Exact Convergence Rate of Gradient Descent
• Average-case optimization analysis for distributed consensus algorithms on regular graphs
• Clarabel: An interior-point solver for conic programs with quadratic objectives
• Learning to optimize: A tutorial for continuous and mixed-integer optimization
• Data-Driven Performance Guarantees for Classical and Learned Optimizers
• Verification of First-Order Methods for Parametric Quadratic Optimization
• Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
• Learning to Warm-Start Fixed-Point Optimization Algorithms
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems
• Automated tight Lyapunov analysis for first-order methods
• Mean Robust Optimization
• Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime
• Exact Optimal Accelerated Complexity for Fixed-Point Iterations
• PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python
• Distributionally Robust Learning
• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k²) Rate on Squared Gradient Norm
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• On the oracle complexity of smooth strongly convex minimization
• Average-case Acceleration for Bilinear Games and Normal Matrices
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality
• Principled Analyses and Design of First-Order Methods with Inexact Proximal Operators
• Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis
• Operator splitting for a homogeneous embedding of the linear\n complementarity problem
• Wasserstein Distributionally Robust Optimization: Theory and\n Applications in Machine Learning
• Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions
• Operator Splitting Performance Estimation: Tight contraction factors and\n optimal parameter selection
• Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• A Friendly Smoothed Analysis of the Simplex Method
• Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
• Distributionally Robust Stochastic Optimization with Wasserstein Distance
• Distributionally Robust Stochastic Optimization with Wasserstein Distance
• Data-driven Distributionally Robust Optimization Using the Wasserstein\n Metric: Performance Guarantees and Tractable Reformulations
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of\n First-order Methods
• On the rate of convergence in Wasserstein distance of the empirical\n measure
• Performance of first-order methods for smooth convex minimization: a\n novel approach
• Distributionally robust joint chance constraints with second-order moment information
• Выпуклая оптимизация
• Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time

Discussions

• 📢 Updated preprint "Data-driven Analysis of First-Order Methods via Distributionally Robust Optimization" with Jisun Park and Vinit Ranjan. ✨ New: probabilistic convergence rates beyond worst-case O( [bsky, 4 points, 0 comments]

Related

• Decomposition Algorithm for Distributionally Robust Optimization using Wasserstein Metric
• Distributionally Robust Optimization with Adversarial Data Contamination
• A General Wasserstein Framework for Data-driven Distributionally Robust Optimization: Tractability and Applications
• Learning Models with Uniform Performance via Distributionally Robust\n Optimization
• Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis