Research map / Learning theory and algorithms / Prediction and decision losses
Understanding the Impact of Introducing Constraints at Inference Time on Generalization Error
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.
Theoretical analysis of how adding constraints only at inference time (ITV) changes generalization error relative to the best constrained model, showing which loss functions preserve relative error.
Problem
When constraints on model outputs are imposed only at inference time, it is unclear how generalization error changes, especially in non-PAC-learnable settings and across different multi-class loss functions.
Approach
Defines "preservation of relative error" (the gap to the best unconstrained model does not increase after inference-time constraints) and gives conditions under which binary and multi-class surrogate losses (softmax CE, one-versus-rest, pairwise comparison, binary CE for structured outputs) preserve it, while multi-class margin loss does not, with worst-case analysis.
Key results
- Relative error is preserved for binary classification under inference-time constraints (Theorem 4.2).
- Softmax cross-entropy, one-versus-rest, and pairwise comparison (zero-one, sigmoid, ramp) losses preserve relative error, with a necessary and sufficient condition given (Theorem 4.3).
- Multi-class margin loss does not preserve relative error; worst-case relative error can reach at least 1/2 (Theorem 5.3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Impose constraints at inference time | Binary classification with a margin-based loss · Binary classification | relative error | Helped |
| Impose constraints at inference time | Softmax cross-entropy loss · Multi-class classification | relative error | Helped |
| Impose constraints at inference time | One-versus-rest loss with a binary surrogate loss · Multi-class classification | relative error | Helped |
| Impose constraints at inference time using zero-one, sigmoid, or ramp binary loss | Pairwise comparison loss · Multi-class classification | relative error | Helped |
| Impose constraints at inference time | Binary cross-entropy loss · Structured prediction | relative error | Helped |
| Combine multi-class margin loss with zero-one, ramp, or sigmoid binary loss and impose constraints | Multi-class margin loss · Multi-class classification | relative error | Hurt |
| Combine pairwise comparison loss with hinge or logistic loss and impose constraints | Pairwise comparison loss · Multi-class classification | relative error | Hurt |
| Impose constraints in a worst-case construction | Multi-class margin loss with zero-one, ramp, or sigmoid binary loss · Multi-class classification | relative error: R(h)−R(g⋆) = 0; R(hc)−R(f⋆c) ≥ 1/2 | Hurt |
Surprising findings
- Multi-class margin loss, a common choice, can produce worst-case relative error of at least 1/2 under inference-time constraints.
- Relative error preservation depends on the choice of multi-class loss even though it is not an issue for binary classification.
Limitations
- Assumes a feasible output exists for every input; infeasible inputs require a rejection extension.
- Identifying the best constrained hypothesis in the hypothesis class under ITV remains an open problem.
- Purely theoretical; no empirical experiments.
Experimental setup
Metrics: relative generalization error
Builds on: Nishino et al. (2022) learning with a verifier Sugiyama et al. (2022) classification-calibrated losses
Closest papers by meaning
- On Regularization and Inference with Label Constraints (ICML 2023 · similarity 0.88)
- Generalization Error of Generalized Linear Models in High Dimensions (ICML 2020 · similarity 0.87)
- Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization (NeurIPS 2020 · similarity 0.86)
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.86)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.85)
- Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · 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.