# A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines

arXiv: https://arxiv.org/abs/2004.05839 · HTML: https://mlsanity.com/paper/2004.05839/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2020.

## Built on by (most cited first, 9 of 9)

- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [Bridging conformal prediction and scenario optimization](https://mlsanity.com/paper/2503.23561/) (2025)
- [Risk Analysis and Design Against Adversarial Actions](https://mlsanity.com/paper/2505.01130/) (2025)
- [Robust Event-Driven Interactions in Cooperative Multi-Agent Learning](https://mlsanity.com/paper/2204.03361/) (2022)
- [Robust optimization for adversarial learning with finite sample complexity guarantees](https://mlsanity.com/paper/2403.15207/) (2024)
- [Gaussian kernel expansion with basis functions uniformly bounded in L∞](https://mlsanity.com/paper/2410.01394/) (2024)
- [Adversarially and Distributionally Robust Virtual Energy Storage Systems via the Scenario Approach](https://mlsanity.com/paper/2511.09427/) (2025)
- [Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees](https://mlsanity.com/paper/2604.12654/) (2026)
- [Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate](https://mlsanity.com/paper/2610.13442/) (2026)

## Abstract (arXiv)

In this paper we consider optimization with relaxation, an ample paradigm to make data-driven designs. This approach was previously considered by the same authors of this work in Garatti and Campi (2019), a study that revealed a deep-seated connection between two concepts: risk (probability of not satisfying a new, out-of-sample, constraint) and complexity (according to a definition introduced in paper Garatti and Campi (2019)). This connection was shown to have profound implications in applications because it implied that the risk can be estimated from the complexity, a quantity that can be measured from the data without any knowledge of the data-generation mechanism. In the present work we establish new results. First, we expand the scope of Garatti and Campi (2019) so as to embrace a more general setup that covers various algorithms in machine learning. Then, we study classical support vector methods - including SVM (Support Vector Machine), SVR (Support Vector Regression) and SVDD (Support Vector Data Description) - and derive new results for the ability of these methods to generalize. All results are valid for any finite size of the data set. When the sample size tends to infinity, we establish the unprecedented result that the risk approaches the ratio between the complexity and the cardinality of the data sample, regardless of the value of the complexity.