Research map / Learning theory and algorithms / Kernels and regression theory
Learning from Interval Targets
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.
Studies regression with interval targets via a projection loss with non-asymptotic bounds based on Lipschitz smoothness, and proposes minmax variants (including pseudo-label PL methods) that constrain worst-case labels to smooth hypotheses.
Problem
Regression when only lower and upper bounds (intervals) on the target are available instead of exact labels; standard regression losses cannot be applied and prior analyses rely on restrictive realizability and small ambiguity degree assumptions.
Approach
Use a projection loss that penalizes predictions outside the interval, derive non-asymptotic generalization bounds via Lipschitz smoothness that shrink the intervals (no ambiguity-degree assumption), and propose a minmax objective whose worst-case labels are restricted to outputs of smooth hypotheses (Minmax reg, PL Max/Mean), with Lipschitz MLPs controlling smoothness.
Key results
- On 18 tabular regression datasets, LipMLP achieves lower test MAE than standard MLP on 14 datasets (e.g., Superconduct 0.540 vs 1.459, Miami House 1.013 vs 1.671).
- Lipschitz-constrained hypotheses yield smaller reduced intervals, with average interval size decreasing as the Lipschitz constant decreases.
- Naive minmax performs best when the target is near the interval center, while projection and PL methods perform best in uniform interval settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a Lipschitz-constrained MLP instead of a standard MLP | Interval-target regression · 18 tabular regression datasets | test MAE | Mixed |
| Use LipMLP instead of MLP | Interval-target regression · Ailerons | test MAE: 4.323 ± 0.098 -> 3.278 ± 0.034 | Helped |
| Use LipMLP instead of MLP | Interval-target regression · Allstate Claims | test MAE: 86.542 ± 0.002 -> 86.547 ± 0.001 | No clear effect |
| Use LipMLP instead of MLP | Interval-target regression · GPU | test MAE: 25.123 ± 0.888 -> 29.817 ± 0.100 | Hurt |
| Use LipMLP instead of MLP | Interval-target regression · Mercedes | test MAE: 11.207 ± 0.218 -> 8.791 ± 0.187 | Helped |
| Use LipMLP instead of MLP | Interval-target regression · Miami House | test MAE: 1.671 ± 0.055 -> 1.013 ± 0.028 | Helped |
| Use LipMLP instead of MLP | Interval-target regression · Superconduct | test MAE: 1.459 ± 0.099 -> 0.540 ± 0.021 | Helped |
| Use projection objective or PL methods instead of naive minmax | Interval-target regression · Uniform interval setting | test MAE | Helped |
| Use naive minmax instead of projection/PL methods | Interval-target regression · Intervals centered near target | test MAE | Helped |
| Decrease the Lipschitz constant (ablation) | Lipschitz MLP · Interval-target experiments | average interval size | Helped |
| Tune the Lipschitz constant to balance smoothness and model capacity (ablation) | Lipschitz MLP · Interval-target experiments | test MAE | Helped |
Surprising findings
- Naive minmax (midpoint regression) can have arbitrarily large error while the constrained minmax variant has zero error in a constructed example (Proposition on worst-case labels).
Limitations
- Generalization bounds rely on uniform convergence, which may be suboptimal compared to specialized analyses.
- Assumes deterministic labels and Lipschitz continuity of the hypothesis class.
- Does not address noisy settings where targets may lie outside intervals or non-i.i.d. data such as time series.
Experimental setup
Datasets: UCI Machine Learning Repository datasets (5) 18 tabular regression datasets
Benchmarks: UCI regression datasets (interval targets) tabular regression benchmark (18 datasets)
Metrics: test MAE
Baselines: projection loss with standard MLP minmax loss with standard MLP midpoint supervised regression PL (Max) PL (Mean)
Builds on: partial-label learning spectral normalization
Closest papers by meaning
- Weakly Supervised Regression with Interval Targets (ICML 2023 · similarity 0.88)
- Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization (NeurIPS 2022 · similarity 0.86)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.84)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.84)
- Near-Optimal Solutions of Constrained Learning Problems (ICLR 2024 · similarity 0.84)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.83)
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.