Data-Driven Performance Guarantees for Parametric Optimization Problems
Jingyi Huang, Paul Goulart, Kostas Margellos · 2025
Read Data-Driven Performance Guarantees for Parametric Optimization Problems by Jingyi Huang, Paul Goulart, Kostas Margellos (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-2506-23819.txt.
Introduction
Jingyi Huang, Paul Goulart, and Kostas Margellos wrote a 2025 paper on giving firm promises about how fast solving methods behave when a problem's inputs change. Many online tasks must finish within a fixed time budget, and older promises about run time are often missing or far too cautious. Their method builds promises from sampled data instead.
They recast the question of how many steps a method needs as a sampling problem over many drawn cases. That framing yields chances-based bounds on step counts and on the quality left after a fixed number of steps. A tuning step trades steps against risk. Tests on simulated problems showed the bounds held up well.
Catalog record
| CREATOR | Jingyi Huang, Paul Goulart, Kostas Margellos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-23819
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Data-Driven Performance Guarantees for Parametric Optimization Problems Jingyi Huang, Paul Goulart, Kostas Margellos Abstract We propose a data-driven method to establish probabilistic performance guarantees for parametric optimization problems solved via iterative algorithms. Our approach addresses two key challenges: providing convergence guarantees to characterize the worst-case number of iterations required to achieve a predefined tolerance, and upper bounding a performance metric after a fixed number of iterations. These guarantees are particularly useful for online optimization problems with limited computational time, where existing performance guarantees are often unavailable or unduly conservative. We formulate the convergence analysis problem as a scenario optimization program based on a finite set of sampled parameter instances. Leveraging tools from scenario optimization theory enables us to derive probabilistic guarantees on the number of iterations needed to meet a given tolerance level. Using recent advancements in scenario optimization, we further introduce a relaxation approach to trade the number of iterations against the risk of violating convergence criteria thresholds. Additionally, we analyze the trade-off between solution accuracy and time efficiency for fixed-iteration optimization problems by casting them into scenario optimization programs. Numerical simulations demonstrate the efficacy of our approach in providing reliable probabilistic convergence guarantees and evaluating the trade-off between solution accuracy and computational cost. I INTRODUCTION Online parametric optimization problems arise frequently in control theory, with model predictive control (MPC) [ 1 , 2 ] being a key example in which the parameters correspond to the initial states. A major challenge in online optimization is the limited computational time available, often restricting the solver to a fixed number of iterations. In online optimization with strict time constraints such as MPC, analytical convergence guarantees are often very conservative relative to the actual optimization performance observed in practice. This raises two critical questions: (i) Can we ensure convergence within a given iteration budget based on numerical experiment?; and (ii) How can we determine the minimal number of iterations needed to achieve satisfactory performance? In this paper, we address these questions by providing a probabilistic convergence guarantee, learning the minimum number of iterations required for convergence, and quantifying the trade-off between iterations and performance. Throughout, we will consider parametric constrained optimization problems of the form, \begin{split}\min_{z}\quad&f(z,x)\\ \text{subject to:}\quad&f_{i}(z,x)=0,\quad i=1,\ldots,I,\\ &g_{j}(z,x)\geq 0,\quad j=1,\ldots,J,\end{split} (1) where z\in\mathbb{R}^{n} is the optimization variable, x\in\Delta\subset\mathbb{R}^{d} is the problem parameter, and \Delta is the parameter space representing the set of all possible values of x for which the parametric optimization problem has at least one feasible solution for z . The (potentially local) optimal solution to the problem ( 1 ) will be denoted z^{*}(x) . We will assume that such a solution is unique (for any given parameter); otherwise a particular solution can be singled-out by means of a tie-break rule. Problems in the form of ( 1 ) typically appear in optimization-based control techniques such as MPC, where they must be solved repeatedly for varying initial conditions x . In this context, the optimization variable z represents the open-loop state and input sequences, while the objective function f:\mathbb{R}^{n}\times\mathbb{R}^{d}\rightarrow\mathbb{R} defines the criterion to be minimized for optimal control. The functions f_{i}(z,x) and g_{j}(z,x) account for the system dynamics, and the input and state constraints, respectively. Theoretical convergence analysis for iterative optimization methods generally provide a-priori convergence rates based only on the problem structure. An overview of convergence analysis across different optimization methods can be found in [ 3 , Chapter 9-15] and [ 4 ] . Some studies have also investigated worst-case convergence rates for unconstrained optimization problems via a computer-assisted analysis [ 5 , 6 ] . However, since these approaches do not exploit the properties of the problem parameters, their convergence rates tend to be conservative. Incorporating the characteristics of the problem parameters could lead to a tighter convergence guarantee. The authors of [ 7 ] proposed a data-driven approach based on sample convergence bounds [ 8 , 9 ] . Their method provides probabilistic performance guarantees for user-specified iteration counts, ensuring each evaluation holds with a pre-defined confidence level of 1-\beta , where \beta\in(0,1) . By evaluating N^{\mathrm{eval}} distinct iteration counts, they quantify the trade-off between optimization performance and iteration count, with an overall confidence level of 1-N^{\mathrm{eval}}\beta . However, this method cannot leverage sample-dependent information to select iteration counts for performance evaluation, potentially requiring more evaluations to establish an informative trade-off between computation time and performance, thereby reducing the overall confidence level. Inspired by [ 7 ] , we propose a data-driven method based on the so called scenario approach [ 10 , 11 , 12 , 13 , 14 , 15 , 16 ] to establish sharp convergence guarantees with high confidence. Our approach solves a scenario optimization problem to automatically determine the worst-case iteration count required to achieve a prescribed tolerance level across sampled parameters, while providing probabilistic guarantees that certify its validity for unseen instances. As such, our approach integrates sample information through scenario programming, enabling us to simultaneously learn the iteration count for convergence and provide a generalization guarantee . Our contributions can be summarized are as follows: • We propose a data-driven method to establish convergence guarantees for parametric optimization problems, providing generalization guarantees through the scenario approach. • We construct data-driven guarantees for the upper bound of a user-defined performance metric in parametric optimization problems. • We demonstrate the effectiveness of our method using an MPC example, showcasing its ability to provide probabilistic convergence guarantees and evaluate the trade-off between iteration count and performance. Section II formulates the convergence guarantee analysis as robust and relaxed scenario optimization problems, providing generalization guarantees for each formulation. Section III presents a data-driven approach to determine the upper bound for a user-defined performance metric in parametric optimization problems. Section IV illustrates the effectiveness of our method through numerical examples. Finally, Section V concludes the paper. II Data-driven convergence guarantees We consider optimization problems as in ( 1 ) and are interested in quantifying convergence to an optimizer z^{*}(x) . We consider convergence in the iterates rather than objective value, i.e., \lim_{k\rightarrow\infty}\|z^{k}(x)-z^{*}(x)\|=0 , where z^{k}(x) represents the optimization variable after the k th iteration of the optimization solver. Both the (local) optimal solution z^{*}(x) and the iterative optimization variables z^{k}(x) depend on the problem parameters x , and we explicitly indicate this dependency. We denote the set of local optimizers for problem ( 1 ) by \mathcal{Z}_{\text{local}}^{*}(x) . By our definition of \Delta , the set \mathcal{Z}_{\text{local}}^{*}(x) is non-empty. In practice, z^{*}(x)\in\mathcal{Z}_{\text{local}}^{*}(x) would be the solution returned by a solver once a given numerical tolerance is met. In this section, we formulate the problem of establishing convergence guarantees as a scenario optimization problem, learning the number of iterations for convergence and providing a generalization guarantee through the scenario approach. II-A Problem formulation We define n(x) as the number of iterations required for an optimization algorithm to solve problem ( 1 ) with parameter x\in\Delta to within a specified tolerance. In other words, for a given x , \|z^{n(x)}(x)-z^{*}(x)\|\leq\eta , where \eta is a prespecified, user-chosen tolerance level. We denote by n^{*} the minimum number of iterations needed so that this tolerance is met for all possible realizations of x . Determining n^{*} provides an upper bound on the computational effort required to