3arXiv cs.LG (Machine Learning)·
Fundamental limits of distributed multiclass classification from binary decisions
This arXiv paper analyzes the theoretical performance limits of constructing a K-class classifier from O(log K) binary classifiers, a paradigm relevant to distributed or hierarchical classification systems. The authors focus on hyperplane binary classifiers in a stylized Gaussian setting, deriving explicit performance bounds across decoding and dimensional regimes. Results are validated with simulation experiments.
Related guides (1)
Related events (8)
Large deviation analysis shows most interpolating classifiers share the same generalization performance
A new arXiv preprint establishes a large deviation principle characterizing the generalization performance of interpolating linear classifiers in the overparameterized regime (n/d → α, small α). The key result is a concentration phenomenon: all but an exponentially small fraction of interpolators achieve approximately the same generalization error, determined by a unique rate-function maximizer. Empirically, gradient descent and a natural linear program both outperform this typical interpolator, providing theoretical grounding for benign overfitting in overparameterized models.
Unified MAIR framework bridges GP-UCB and DEC approaches in kernel bandits
A new arXiv preprint unifies two major theoretical frameworks for frequentist RKHS bandits — Gaussian-process upper confidence bound (GP-UCB) and decision-estimation-coefficient (DEC) methods — under a common algorithmic-information language called MAIR. The paper generalizes both the GP-UCB analysis and the MAMS algorithm, proposes a safeguarded master algorithm combining their advantages, and demonstrates that algorithmic complexity can be more informative than class-wide minimax certificates in overparameterized models. The work clarifies a foundational distinction between algorithmic information and minimax coefficients in bandit theory.
Co-failure ceiling theorem bounds maximum gains from LLM routing, voting, and mixture-of-agents across 67 frontier models
A new arXiv paper introduces the concept of a 'co-failure ceiling' — the rate at which all models in an ensemble fail on the same query — and proves that no routing, voting, or cascade policy can exceed accuracy of (1 - beta) where beta is this all-wrong rate. Empirically evaluated across 67 models from 21 providers, the paper finds that standard pairwise error correlation metrics systematically underprice the co-failure tail by ~2.5x on open-ended mathematics, and that combining models rarely beats the single best model without strong query-level routing signals. The work provides a finite-sample certificate (via Clopper-Pearson bounds) for the maximum achievable gain from multi-model systems before training a router, and identifies answer format rather than subject matter as a key driver of co-failure on GPQA-Diamond.
Computational limitations in robust classification and win-win results
OpenAI published research examining computational limitations in robust classification, exploring theoretical bounds on adversarially robust machine learning. The work investigates so-called 'win-win' results where both standard and robust accuracy can be achieved simultaneously. This is a foundational safety and robustness research contribution from 2019, addressing hardness results in adversarial ML.
Optimal deterministic multicalibration achieved, resolving open problem on randomization necessity
A new arXiv preprint resolves an open problem in multicalibration theory by constructing a minimax-optimal multicalibration algorithm that outputs a deterministic predictor, achieving the same O(ε⁻³) sample complexity previously only attainable by randomized predictors. The result extends to outcome indistinguishability, deterministic omnipredictors, and panpredictors with optimal sample complexity, resolving multiple open problems from recent works. Multicalibration is a fairness and reliability property requiring calibration to hold across reweighted subgroups, making this relevant to trustworthy ML research.
Theoretical analysis of generalization scaling laws in quadratic two-layer neural networks
A new arXiv preprint derives explicit characterizations of generalization error as a joint function of model width, sample count, and regularization in a quadratic two-layer network with structured data. The analysis reveals a phase diagram with distinct scaling regimes governed by data-dependent power laws tied to the spectral structure of the target function. The work extends scaling law theory beyond fixed-feature or infinite-width regimes by operating in a finite-sample, feature-learning setting, and characterizes interpolation threshold transitions.
Language Generation in the Limit with Bounded Memory: Characterization via Sperner's Theorem
This paper studies language generation in the limit under bounded memory constraints, extending classical learning theory to the generation setting. The authors characterize when memoryless generation is possible, derive minimax density bounds using Sperner's theorem and symmetric chain decompositions, and show that adaptively chosen memory outperforms sliding-window memory. They also revisit incremental identification in the limit, finding that exact identification fails for collections of three or more languages but an approximate relaxation is achievable for all finite collections.
Theoretical unification of discrete diffusion model objectives via Oracle Distance theorem
A new arXiv preprint provides a rigorous theoretical framework for understanding what discrete diffusion models learn, proving the 'Oracle Distance' theorem: the negative ELBO exactly equals data entropy plus the path KL from the oracle reverse process to the learned one. The work shows that denoiser, score ratio, and bridge plug-in parameterizations are the same object in different coordinates, with closed-form conversions among them. It unifies several existing discrete diffusion losses (MDM, UDM, SEDD, GIDD) as special cases and identifies practical consequences, such as why denoiser parameterization causes the uniform ELBO to diverge at initialization. All identities are verified numerically on an exactly solvable model.