CS Paper Radar

A Unified Descriptive-Complexity Framework for Model Selection under Correlated Designs

Yanhang Zhang, Wei Liu, Yuhong Yang

cs.LG stat.ML ·submitted 2026-08-27 05:02 UTC · v1
benchmark

Abstract

Model selection becomes particularly challenging under strong predictor dependence and model-class uncertainty, especially when there are exponentially many models. We propose a Descriptive-Complexity Information Criterion (DCIC) that regularizes large candidate model collections through Kraft-admissible code lengths. Under sub-Weibull noise, we establish selection consistency through approximation-error separation without relying on RIP-type conditions, together with nonasymptotic oracle risk bounds that remain valid under model misspecification. The same coding principle places heterogeneous classes on a common complexity scale at a small additional class-identification cost. This extension yields class--model recovery under suitable identifiability conditions and risk adaptation across classes. We further develop a complexity-guided search path that makes the computation--statistics trade-off explicit. Large penalties yield polynomial-size retained search regions with high probability, whereas smaller penalties sharpen the oracle risk benchmark. Numerical experiments illustrate stable support recovery and favorable estimation performance under strong dependence and model-class uncertainty.

Comment
73 pages, 14 figures, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

cs.LG ·2026-10-18 ·Guangjian Zhang
theory similarity 0.58
Abstract · 92 pages

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

0.30

Bagging Robustly Learns VC Classes with Linear Sample Complexity

cs.DS stat.MLcs.LG ·2026-08-13 ·Omar Montasser
theory similarity 0.58
Abstract

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.

0.32

Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness

cs.LG stat.ML ·2026-10-18 ·Guangjian Zhang
theoryhot direction similarity 0.56
Abstract · 68 pages

Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity $Θ(((\log M)^2/ρ^2+\log(1/δ))/\varepsilon)$ for classes of cardinality at most $M$, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general $ρ^{-1}$ dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses $O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon)$ samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of $d$ finite threshold chains of length $k$, we determine the exact rate $Θ((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon)$. We also characterize deterministic learning, the very-small-$ρ$ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent $3/2$ independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.

0.30

Communication Complexity of Universal Features

cs.DS stat.MLcs.LG ·2026-10-19 ·Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty
theory similarity 0.56
Abstract

Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.

0.21

Sample-Optimal Multi-Group Learning with an ERM Oracle

cs.LG cs.DScs.GT ·2026-10-11 ·Princewill Okoroafor
theory similarity 0.56
Abstract

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $Ω((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.

0.16

Sparse Regression Distilled from a Single Robust Fit

cs.LG stat.MLstat.ME ·2026-09-20 ·Wooyoung Shin, Seunghwan Park
similarity 0.56
Abstract · 68 pages, including appendices; 8 figures

Robust linear fits can resist response contamination yet remain too dense or unstable for useful global explanations. We propose penalized distillation, which fits a smoothly clipped absolute deviation (SCAD) estimator to a robust initial estimator's empirical fitted surface along a safeguarded coordinate-descent path and evaluates candidate states separately for fidelity, parsimony, perturbation stability, and held-out prediction. The new results attach to the states the algorithm actually computes. Conditional on a fixed uncontaminated design, deterministic bounds transfer response-replacement boundedness from the initial fit to every retained path state. Turning to fixed dimension, we characterize the oracle-support branch by its empirical-Gram projection and influence function, give conditions for covariance-weighted least-squares approximation equivalence, and establish a path-conditional generalized information criterion. By contrast, at large dimension-to-sample ratios the full-coordinate robust fit collapses without warning, and screening restores the construction. Under a sure-screening framework, the robustness bound and the support and selection guarantees transfer to the screened fit. Simulations separate robustness transfer from support recovery, efficiency, and computation across the dimension-to-sample ratio, with p up to 240, and the signal density, which isolates what the sparse stage adds once the screen over-selects. In a duplicate-grouped superconductivity study, the distilled estimator remains predictively stable under prespecified training-response shifts but retains 66.8--68.8 of 81 slopes. Stronger sparsification reduces the model to 12.6--14.0 slopes only at visible fidelity and prediction cost. Distillation therefore preserves predictive stability on these data without substantiating a compact coordinate-level explanation.

0.35

Efficient Robust Learning at the Information-Theoretic Limit

cs.DS cs.LGstat.ML ·2026-09-15 ·Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
similarity 0.55
Abstract · Corrected the arXiv abstract to match the pdf

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon$. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). Here we resolve this problem and give such an algorithm. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits low-degree polynomial approximators with respect to hypercontractive distributions. This captures basic settings including halfspaces with respect to Gaussian marginals. Our techniques make new connections to various types of online convex optimization algorithms. As a surprising consequence, we show that efficient SQ learnability in the agnostic setting implies efficient learning with contamination (with respect to Gaussians or uniform over the hypercube).

0.37

The Sample Complexity of Multicalibration with an ERM Oracle

cs.LG cs.DScs.GT ·2026-10-09 ·Princewill Okoroafor
hot direction similarity 0.55
Abstract · 58 pages

A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about $\varepsilon^{-3}$ samples are necessary and sufficient to learn a predictor with multicalibration error $\varepsilon$, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}(d/\varepsilon^{3})$ samples and polynomially many ERM calls, where $d$ is the VC dimension of the class. Its dependence on $\varepsilon$ is optimal for all learners. When $d$ is at least about $1/\varepsilon$, every learner that can only access the class through polynomially many ERM calls needs $\tildeΩ(d/\varepsilon^{3})$ samples. Learners with unlimited computation need only $\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$ samples, so the extra factor $1/\varepsilon$ on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, $\tildeΘ(d/\varepsilon^{3})$ samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.

0.57