Research map / Optimization / Optimizers
Learning from Uncertain Data: From Possible Worlds to Possible Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Zorro, which uses zonotope abstract interpretation to symbolically run gradient descent over all possible dataset variants of uncertain data, yielding closed-form fixed points that soundly over-approximate possible ridge-regression models and prediction ranges.
Problem
Learning linear models from uncertain training data (missing values, errors, label/feature noise) produces predictive multiplicity; enumerating all possible datasets and training a model for each is infeasible, and existing prediction-range methods only handle label uncertainty with loose interval a
Approach
Represent dataset uncertainty as a zonotope and abstractly execute gradient descent on all possible worlds at once, using linearization and a transformation-based order reduction whose fixed point admits a closed-form solution for ridge regression, giving sound over-approximations of possible optimal models and prediction ranges.
Key results
- Zorro certifies substantially higher robustness ratios than the interval-based Meyer baseline; e.g., at 10% uncertain MPG data with 5-20% label radius, Zorro certifies 100% robustness while Meyer returns 0%.
- Zorro tightly over-approximates the ground-truth loss range by enumeration, with the gap widening as uncertainty radius grows.
- Small positive regularization (e.g., 0.02 or 0.025) generally gives the best worst-case test loss, and higher regularization yields more robust predictions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use zonotopes instead of interval arithmetic for training-label uncertainty | Robustness certification with linear regression · MPG, 10% uncertain data; uncertainty radius >5% and <20% of label range | robustness ratio: 0% -> 100% | Helped |
| Use zonotopes instead of interval arithmetic for training-label uncertainty | Robustness certification with linear regression · Insurance, 10% uncertain data; 4% uncertainty radius | robustness ratio: 0% -> above 95% | Helped |
| Introduce uncertainty in training features rather than labels | Zorro linear regression · MPG, 10% uncertain data; feature uncertainty in weight column at 12% radius versus label uncertainty at 15% radius | robustness ratio: more than 90% -> 0% | Hurt |
| Increase training-label uncertainty radius from 15% to 20% | Zorro linear regression · MPG, 10% uncertain data | robustness ratio: more than 90% -> 80% | Hurt |
| Increase the regularization coefficient | Zorro linear regression · MPG, uncertain features and labels | robustness ratio | Helped |
| Use a small positive regularization coefficient (e.g., 0.02 or 0.025) instead of λ = 0 | Zorro linear regression · MPG, worst-case test loss across uncertain-data scenarios | worst-case test loss | Helped |
Surprising findings
- Zero regularization is not optimal for worst-case loss, especially when the fraction of uncertain instances is high.
- Feature uncertainty yields less robust predictions than label uncertainty at similar radius, due to more high-order terms in the closed-form solution.
Limitations
- Linearization introduces over-approximation error that grows with uncertainty radius and higher-order gradient terms.
- Currently limited to linear models (ridge regression); extension to other architectures is challenging.
Experimental setup
Datasets: MPG Insurance
Benchmarks: MPG Insurance
Metrics: robustness ratio worst-case test loss prediction interval tightness vs ground truth loss range
Baselines: Meyer et al. (interval arithmetic) KNN imputation enumeration ground truth (GT)
Builds on: abstract interpretation polynomial zonotopes Meyer et al. interval-based prediction ranges
Closest papers by meaning
- probly: Uncertainty-Aware Machine Learning (NeurIPS 2026 · similarity 0.88)
- Optimization over Continuous and Multi-dimensional Decisions with Observational Data (NeurIPS 2018 · similarity 0.87)
- Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent (NeurIPS 2023 · similarity 0.86)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.85)
- Structure-informed Risk Minimization for Robust Ensemble Learning (ICML 2025 · similarity 0.85)
- Maxitive Donsker-Varadhan Formulation for Possibilistic Variational Inference (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.