# Compression, Generalization and Learning

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 50 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Builds on (most cited first, 9 of 9)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [The Scenario Approach for Stochastic Model Predictive Control with Bounds on Closed-Loop Constraint Violations](https://mlsanity.com/paper/1307.5640/) (2013)
- [Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs](https://mlsanity.com/paper/1307.0345/) (2013)
- [A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines](https://mlsanity.com/paper/2004.05839/) (2020)
- [A scenario approach for non-convex control design](https://mlsanity.com/paper/1401.2200/) (2014)
- [Randomized Methods for Design of Uncertain Systems: Sample Complexity and Sequential Algorithms](https://mlsanity.com/paper/1304.0678/) (2013)
- [On the Sample Size of Random Convex Programs with Structured Dependence on the Uncertainty (Extended Version)](https://mlsanity.com/paper/1502.00803/) (2015)
- [Distributed constrained optimization and consensus in uncertain networks via proximal minimization](https://mlsanity.com/paper/1603.02239/) (2016)

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

- [Open-Endedness is Essential for Artificial Superhuman Intelligence](https://mlsanity.com/paper/2406.04268/) (2024)
- [Weak-to-Strong Generalization Through the Data-Centric Lens](https://mlsanity.com/paper/2412.03881/) (2024)
- [Bridging conformal prediction and scenario optimization](https://mlsanity.com/paper/2503.23561/) (2025)
- [Pick-to-Learn for Systems and Control: Data-driven Synthesis with State-of-the-art Safety Guarantees](https://mlsanity.com/paper/2512.04781/) (2025)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks](https://mlsanity.com/paper/2410.13577/) (2024)
- [A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes](https://mlsanity.com/paper/2510.25569/) (2025)
- [Risk Analysis and Design Against Adversarial Actions](https://mlsanity.com/paper/2505.01130/) (2025)
- [Finite sample learning of moving targets](https://mlsanity.com/paper/2408.04406/) (2024)
- [Sample Compression for Self Certified Continual Learning](https://mlsanity.com/paper/2503.10503/) (2025)
- [Tuning without Peeking: Provable Generalization Bounds and Robust LLM Post-Training](https://mlsanity.com/paper/2507.01752/) (2025)
- [Learning Decision-Sufficient Representations for Linear Optimization](https://mlsanity.com/paper/2603.18551/) (2026)
- [Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocation](https://mlsanity.com/paper/2603.19396/) (2026)
- [Robust optimization for adversarial learning with finite sample complexity guarantees](https://mlsanity.com/paper/2403.15207/) (2024)
- [Improved Compression Bounds for Scenario Decision Making](https://mlsanity.com/paper/2501.08884/) (2025)
- [PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions](https://mlsanity.com/paper/2501.08887/) (2025)
- [Online Complexity Estimation for Repetitive Scenario Design](https://mlsanity.com/paper/2509.02103/) (2025)
- [Scenario Approach with Post-Design Certification of User-Specified Properties](https://mlsanity.com/paper/2602.15568/) (2026)
- [Pick-to-Learn Calibration of an MPC Policy for an Origin-to-Destination Flight Problem](https://mlsanity.com/paper/2607.16084/) (2026)
- [Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification](https://mlsanity.com/paper/2609.01355/) (2026)
- [Preferent Compression Bounds Are Tight](https://mlsanity.com/paper/2609.36030/) (2026)

## Abstract (arXiv)

A compression function is a map that slims down an observational set into a subset of reduced size, while preserving its informational content. In multiple applications, the condition that one new observation makes the compressed set change is interpreted that this observation brings in extra information and, in learning theory, this corresponds to misclassification, or misprediction. In this paper, we lay the foundations of a new theory that allows one to keep control on the probability of change of compression (which maps into the statistical "risk" in learning applications). Under suitable conditions, the cardinality of the compressed set is shown to be a consistent estimator of the probability of change of compression (without any upper limit on the size of the compressed set); moreover, unprecedentedly tight finite-sample bounds to evaluate the probability of change of compression are obtained under a generally applicable condition of preference. All results are usable in a fully agnostic setup, i.e., without requiring any a priori knowledge on the probability distribution of the observations. Not only these results offer a valid support to develop trust in observation-driven methodologies, they also play a fundamental role in learning techniques as a tool for hyper-parameter tuning.