2025/11/21 by Jisun Park, Park, Jisun, Vinit Ranjan +3 · 1 voice
Computer Science · Decision Sciences · Engineering · Mathematics · #math.OC
paper · pdf · doi:10.48550/arxiv.2511.17834
arxiv created 2026/08/05 · arxiv updated 2026/08/06
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. Our open-source implementation computes these guarantees directly from sampled algorithm trajectories using off-the-shelf conic solvers. Experiments on convex quadratic minimization, real-data logistic regression using a credit-scoring dataset, and Lasso show that our method significantly reduces the conservatism of classical worst-case bounds and narrows the gap between theoretical and empirical performance.