PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yanhang Zhang, Wei Liu, Yuhong Yang

arXiv:2608.26618v1stat.MLcs.LG

TL;DR

Model selection under strong dependence, model-class uncertainty, and exponentially large candidate collections requires guarantees beyond restrictive design assumptions and fixed model classes. The paper proposes DCIC, a Kraft-coded criterion with consistency, misspecification-robust oracle bounds, cross-class adaptation, and a complexity-guided search path. Its guarantees include exact class–model recovery under identifiability and risk adaptation across heterogeneous classes, while larger penalties yield polynomial-size retained regions and smaller penalties sharpen the oracle benchmark.

  • Problem

    The paper asks how to obtain selection consistency and oracle risk guarantees under strong predictor dependence while selecting across heterogeneous model classes and controlling exploration of exponentially many models.

  • Method

    DCIC uses Kraft-admissible descriptive complexities to regularize candidate models, encode class labels, and control a λ-dependent search budget under sub-Weibull noise.

  • Results

    DCIC achieves selection consistency without RIP/SRC-type conditions, provides nonasymptotic oracle risk bounds under misspecification, and supports class–model recovery or risk adaptation across classes.

  • Takeaways & Limitations

    The framework links model complexity, heterogeneous-class selection, statistical risk, and computational search through one coding principle.

  • Takeaways & Limitations

    Exact class–model recovery applies only when the true class–model pair is identifiable; indistinguishable classes call for risk adaptation instead.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses model selection under strong predictor dependence, heterogeneous model classes, and exponentially large search spaces. It introduces DCIC to provide consistency, misspecification-robust risk guarantees, cross-class selection, and an explicit computation–statistics trade-off.

  • Motivation: Existing consistency analyses often impose RIP or SRC conditions that exclude strongly dependent designs.The paper instead asks whether consistency and oracle risk guarantees can hold under dependence commonly encountered in high-dimensional data.
  • Motivation: Model-class uncertainty motivates selecting across heterogeneous approximation systems rather than restricting analysis to a prespecified basis family.Different classes can have different approximation behavior and complexity, making within-class selection potentially misspecified.
  • Framework: DCIC uses Kraft-admissible, model-specific code lengths to compare large candidate collections on a common descriptive-complexity scale.Its tuning parameter controls a nonuniform complexity budget instead of assigning every model of the same size an identical selection cost.
  • Guarantees: Under sub-Weibull noise, the framework establishes selection consistency through approximation-error separation without RIP/SRC-type conditions and gives nonasymptotic oracle risk bounds under misspecification.The risk perspective does not require a distinguished true model, which is relevant when candidate collections are misspecified or dependence makes exact recovery too stringent.
  • Multi-class selection: Encoding class labels at an additional cost of order log M puts heterogeneous classes on a common scale and supports exact class–model recovery or risk adaptation.Exact pair recovery requires identifiability; when classes are statistically indistinguishable, risk adaptation is the more natural target.
  • Computation–statistics trade-off: Along the decreasing-λ path, larger penalties retain polynomial-size search regions with high probability, whereas smaller penalties expand exploration and sharpen the oracle benchmark.Illustrations report improved support recovery or lower ASE as the explored region expands, at additional computational cost.

2 Model selection consistency of DCIC

DCIC establishes selection consistency for structured model collections by combining Kraft-admissible descriptive complexity with approximation-error separation. The framework applies to strongly correlated designs, including group and double-sparse structures, without requiring RIP/SRC conditions.

  • General framework: The atom-level framework represents structured candidates as admissible unions of selection atoms and partitions competitors into overfitted, underfitted, and wrong models.The proof controls these competitor types through complexity gaps, approximation-error lower bounds, and APP conditions.
  • General framework: Kraft-admissible descriptive complexities control overfitted models automatically, leaving APP bounds for underfitted and wrong competitors.This is the central separation mechanism behind the consistency theorem.
  • Structured models: For double-sparse models, the complexity encodes selected groups, within-group variables, active-group counts, and within-group subset sizes.The resulting criterion yields selection consistency under the corresponding APP-separation conditions.
  • Representative designs: Theorem 2.8 establishes DCIC selection consistency under three representative correlated-design scenarios, including equicorrelation, weak alignment with spurious predictors, and shadow predictors.These scenarios permit strong dependence while retaining verifiable APP separation.
  • Representative designs: The beta-min conditions are of order σ2(log p + log n)/n when ω, λ∗, and ϵ0 are constants.For Scenarios 1 and 3, the condition becomes β2_min ≥ cσ2s∗(log p + log n)/n, simplifying to cσ2s∗log p/n when log n = O(log p).
  • Representative designs: RIP- and SRC-based consistency analyses are no longer applicable in the strongly correlated regimes considered, whereas APP-based separation remains verifiable.The all-subset penalty alternative s log(ep/s) + log p is less severe for large models than s log p.

3 Oracle risk bounds under model misspecification

The misspecification analysis removes the need for a distinguished true model and bounds DCIC risk by the best approximation–complexity trade-off over the candidate collection. These bounds recover minimax-optimal or near-optimal rates for several sparse structures.

  • Setup: DCIC risk analysis allows arbitrary mean vectors and does not require a true model or even a linear representation in X.This perspective targets candidate collections that are misspecified or settings where exact recovery is too stringent.
  • Setup: The selected least-squares model is evaluated through average squared error against the target mean.The index of resolvability characterizes the optimal approximation–complexity trade-off over the candidate set.
  • Oracle bound: Theorem 3.1 controls DCIC risk by the best approximation–complexity trade-off over the candidate collection.The result holds nonasymptotically with high probability under Kraft-admissible complexity and suitable tuning.
  • Sparse structures: For all-subset selection, the risk bound is minimax optimal over s∗-sparse linear models without design assumptions.The stated complexity is CS = s log(ep/s) + log p with log n = O(log(ep/s∗)).
  • Sparse structures: Group selection matches the minimax rate up to a logarithmic factor in the within-group estimation term.This uses CS = g log(em/g) + log m.
  • Sparse structures: Double-sparse selection is minimax optimal under the stated sparsity-growth condition.Its complexity combines group selection, within-group variable selection, active-group counts, and within-group subset sizes.

4 Model-class uncertainty

DCIC compares heterogeneous candidate classes by adding a Kraft-admissible class-identification cost to model complexity. This supports exact class–model recovery under identifiability and risk adaptation to the best approximation–complexity trade-off.

  • 4.1 Multi-class extension of DCIC: DCIC aggregates class–model pairs and adds a log M class-identification cost while preserving Kraft admissibility.The added term encodes the cost of identifying one class among M candidates.
  • 4.1 Multi-class extension of DCIC: Under aggregated approximation-error separation, DCIC achieves exact recovery of a unique true class–model pair.The guarantee requires the conditions of Theorem 2.1 on the aggregated candidate list.
  • 4.1 Multi-class extension of DCIC: When exact pair identifiability fails, the multi-class risk bound adapts to the best approximation–complexity trade-off across classes.The extension adds a risk cost of order (log M)2/α/n up to constants relative to the single-class setting.
  • 4.1 Multi-class extension of DCIC: Minimizing multi-class DCIC jointly selects the candidate class, active components, and within-class representations.In sparse additive regression, the class identifies a basis family, while the within-class model specifies active components and basis representations.
  • 4.2 Basis-family selection in nonparametric sparse additive models: For sparse additive estimation with a candidate family attaining rm(n) ≍ n−2β/(2β+1), the adaptive rate matches the minimax rate up to log M/n.If M grows at most polynomially in n, the additional term is of order (log n)/n and does not affect the overall convergence rate.
  • 4.2 Basis-family selection in nonparametric sparse additive models: Basis-family performance depends on smoothness: spline is optimal for β ∈ (1,4], whereas Fourier achieves the best one-dimensional rate among the three families when β > 4.Periodic Fourier can be suboptimal without boundary matching, while fixed-order splines and Haar saturate in their approximation regimes.

5 A complexity-guided search strategy

The complexity-guided strategy uses a decreasing-λ DCIC path and two pruning stages to connect retained search size with statistical benchmarks. Larger λ yields polynomial-size certified regions, while smaller λ improves oracle risk and can support exact recovery under beta-min conditions.

  • 5 A complexity-guided search strategy: The strategy prunes exponentially many subset candidates using a Kraft-based complexity budget and provides high-probability retained-region and finite-sample FP–FN guarantees.It does not remove the worst-case NP-hardness of best subset selection.
  • 5.1 Complexity-guided pruning: As λ decreases, DCIC minimizers have nondecreasing complexity, so the search region expands along the path.For 0 < λ1 < λ2, the selected complexity satisfies C(bSλ1) ≥ C(bSλ2).
  • 5.1 Complexity-guided pruning: Two pruning stages first restrict admissible model sizes and then screen variables within each retained size before depth-first search.The remaining search is further pruned using the residual complexity budget.
  • 5.3 A concrete λ-path and the computation–statistics trade-off: Larger λ, with λ ≳ n/log p, yields a polynomial-size retained region with high probability, whereas smaller λ sharpens the oracle benchmark.The path therefore makes computational exploration and statistical performance explicit.
  • 5.1.2 Second-stage pruning of candidate variables: The polynomial-regime support guarantee requires s∗log∗(τn) ≤ c1 log p; under uniform coding, this reduces to fixed sparsity s∗ = O(1).Thus, the analogous guarantee is more restrictive when the code does not exploit ranking information.
  • 5.2 FP and FN guarantees along a λ-path: Under suitable beta-min conditions, an interval of λ values yields exact support recovery throughout the path.If λ− < λ+, then bSλ = S∗ for all λ in the corresponding grid interval.
  • 5.3 A concrete λ-path and the computation–statistics trade-off: The statistical entry reaches the minimax risk benchmark at k ≳ kstat, while ranking quality determines whether this entry lies within the certified polynomial region.A smaller rank envelope τn shifts statistical entry earlier, and the condition is kstat ≲ kpoly.

6 Numerical Experiments

The experiments evaluate DCIC under strongly correlated designs and uncertainty across sparse additive basis families. DCIC shows robust support recovery and estimation performance, including competitive results in the most challenging correlated setting and strong adaptation across Fourier, spline, and Haar families.

  • 6.1 All-subset selection under strongly correlated designs: 100 repetitions compare DCIC with SCAD, MCP, HTP, and ABESS under correlated-design settings with varying sample sizes.The main text focuses on Setting 3, using within- and between-block correlations of 0.9 and highly clustered signals.
  • 6.1 All-subset selection under strongly correlated designs: Under Setting 3, severe within-block collinearity degrades every method, yet DCIC remains robust in parameter estimation and model selection.No method achieves exact support recovery; DCIC maintains high MCC by controlling both false positives and false negatives, while HTP and ABESS tend to underselect.
  • 6.2 Empirical evaluation of multi-class basis selection: The multi-class experiment compares Fourier, spline, and Haar basis families with family- and within-family selection metrics.Fourier and spline use ordered dictionaries, while Haar uses a three-level wavelet dictionary; the study reports ASE, FP, FN, MCC, FIA, ORA, and FaMCC.
  • 6.2 Empirical evaluation of multi-class basis selection: Under Fourier and spline truth, DCIC attains the lowest ASE and highest MCC among non-oracle competitors, while FIA and ORA rapidly approach one.Under spline truth, the LASSO-type baseline reduces FN but substantially inflates FP, weakening overall recovery.
  • 6.2 Empirical evaluation of multi-class basis selection: Under Haar truth, DCIC achieves the highest FaMCC over most sample sizes, indicating accurate family and within-family sparse-structure recovery.Across Figures 5–7, the reported results are consistent with adaptation across ordered and subset-selection families.

7 Conclusion and Discussion

The conclusion presents DCIC as a coding-based criterion for model and class selection under strong dependence and misspecification. It also identifies extensions toward weaker tail assumptions and contaminated observations as future work.

  • Conclusion: DCIC uses Kraft-admissible code lengths to compare large candidate collections under strong predictor dependence and model-class uncertainty.The framework combines selection consistency, oracle risk guarantees, class recovery, risk adaptation, and a complexity-dependent search budget.
  • Conclusion: Under sub-Weibull noise, DCIC obtains selection consistency without RIP/SRC-type conditions and nonasymptotic oracle risk bounds under model misspecification.Encoding class labels puts heterogeneous classes on a common complexity scale and supports exact pair recovery under identifiability.
  • Conclusion: Larger λ values produce polynomial-size retained search regions with high probability, whereas smaller values sharpen the oracle risk benchmark.The same path also provides finite-sample control of false positives and false negatives.
  • Discussion: Extending DCIC to weaker tail conditions and contaminated observations remains a direction for further investigation.The paper specifically points to robust criteria as a possible route for this extension.

A Proofs of main results

The appendix proves the main selection results by separating overfitted, underfitted, and wrong models under Kraft-controlled descriptive complexity. The argument combines approximation-error separation with sub-Weibull concentration and verifies the required conditions through case analysis.

  • Model separation: Lemma A.1 separates overfitted, underfitted, and wrong models through assumptions on descriptive complexity and approximation error.These conditions form the core separation step used in the main selection-consistency proof.
  • Proof strategy: The proof verifies the lemma’s assumptions using sub-Weibull noise control, complexity comparisons, and bounds for model counts and approximation errors.The argument proceeds through three cases and invokes auxiliary lemmas to establish the required inequalities.
  • Conclusion of proof: The remaining theorem conditions are matched to the assumptions of Lemma A.1, completing the selection-consistency argument.The appendix concludes by combining the three cases and applying the main theorem.
  • Kraft control: Kraft-inequality verification bounds the summation over coded models, enabling the theorem’s uniform control over candidate collections.The proof uses the induced complexity definition and summability of exponential code terms.

A.3 Proof of the double-sparse selection result

The double-sparse selection proof establishes the stated consistency result by verifying Kraft control and the overfitted-model separation condition. Its assumptions include a growth condition on the true group count that can be relaxed in the sub-Gaussian case.

  • Selection-consistency result: The double-sparse result begins from the precise selection-consistency statement and a descriptive complexity containing group and within-group terms.The displayed complexity is CS = g log m + s log d + 2 log(g + 1) + 2.
  • Overfitted models: For λ above the stated threshold, the proof verifies the overfitted-model summability required by the main theorem.The argument chooses the penalty-dependent constant so the relevant exponent exceeds 1 + γ.
  • Scope of assumptions: In the sub-Gaussian case, the growth condition g∗≤d^γ and its γ-dependent lower bound on λ can be removed when g∗≤n and η_n is enlarged.The modification does not change the order of the separation conditions.
  • Kraft control: The proof first establishes the Kraft inequality by summing over all double-sparse supports.This supplies the coding control needed for the theorem’s uniform model comparison.
  • Proof completion: The remaining inequalities establish the separation condition and transfer the conclusion from the main theorem to the double-sparse setting.The proof uses auxiliary inequalities and concludes after verifying the theorem’s remaining assumptions.

A.4 Proof of Theorem 2.8

The proof verifies the conditions needed for DCIC selection consistency across underfitted, overfitted, and wrong models. It combines approximation-error bounds, complexity controls, projection arguments, and Kraft-based concentration to conclude consistency.

  • Separation conditions: For remaining competitors, covariance lower bounds and projection properties provide the approximation-error separation required by the consistency corollary.The proof verifies design conditions for submodels and wrong models, including Scenario 2 and orthogonality across signal–shadow pairs.
  • Case decomposition: The proof partitions competitors by underfitting, overfitting, and wrong-model status, using ℓ and j to measure omitted and added variables.The notation sets ℓ:=∆−(S) and j:=∆+(S), then treats the resulting cases separately.
  • Wrong models: Strongly oversized wrong models are automatically excluded because their complexity control dominates the associated stochastic term.For s>2s∗, the proof obtains 2BS<uS for sufficiently large n.
  • Uniform concentration: Kraft-admissible complexities enable uniform deviation control over the candidate collection through union bounds.The proof repeatedly applies the Kraft inequality to control residual and projection-noise terms simultaneously over models.
  • Conclusion: Corollary 2.4 then yields selection consistency once the verified inequalities hold for every candidate model.The final comparison establishes DCIC(S)>DCIC(S∗) for competing models.

A.7 Proof of Corollary 4.4

The proof extends the consistency argument to class–model pairs by aggregating class and within-class code lengths. It verifies overfitted, underfitted, and wrong-pair conditions before applying the class-model consistency corollary.

  • Conclusion: The remaining conditions imply class–model selection consistency through Corollary 4.1.The proof concludes after verifying all three conditions on the aggregated candidate list.
  • Overfitted pairs: Overfitted pairs remain within the true class, so the additive log M class term cancels from their comparison.The within-class overfitted summability condition is unchanged by aggregation.
  • Aggregated complexity: Aggregated class–model complexities preserve the Kraft inequality while adding the class-identification cost.The proof treats each pair (m,S) as a candidate and uses the aggregated code construction.
  • Underfitted pairs: Underfitted pairs are controlled by the class-specific approximation and complexity conditions inherited from the single-class theorem.The proof verifies the corresponding assumption after replacing models with class–model pairs.
  • Wrong pairs: Sufficiently large wrong pairs are excluded because their code complexity dominates the stochastic comparison term.For s(m,S)>(1+κ)s∗, the proof derives 2B(m,S)<u(m,S) for sufficiently large n.

A.11 Proof of Theorem 5.3

The proof establishes uniform DCIC separation from the true model along the complexity-guided search path. It handles overfitted, underfitted, and wrong competitors, then applies union bounds across the path.

  • Competitor decomposition: The proof analyzes overfitted, underfitted, and wrong models separately using the corresponding DCIC decompositions.A tuning constant λζ is selected so that all three competitor classes can be controlled.
  • Separation along the path: For each competitor class, high-probability inequalities guarantee DCIC(S)−DCIC(S∗)>0 under explicit separation conditions.The proof derives sufficient conditions for positive DCIC gaps in each case.
  • Uniform control: The Kraft condition controls the aggregate probability of deviations across the candidate models.The proof invokes the Kraft condition when summing the relevant tail bounds.
  • Simultaneous path guarantee: A union bound over the tuning-parameter set makes the resulting inequality hold simultaneously for all λ∈Λ with high probability.The final statement combines the fixed-λ bounds across the entire path.

C.1 Additional results for Section 6.1

Additional simulations show that larger samples and less block-dominated correlation improve prediction and support recovery, while signal clustering and within-block collinearity shape method differences. DCIC performs strongly in dispersed and moderately clustered settings.

  • Overall patterns: As n increases, all methods improve in ASE, FP, FN, and MCC across covariance mixes.Performance also improves as w decreases, shifting the design toward AR(1)-dominated correlation.
  • One-per-block signals: When n≥240 with one signal per block, DCIC and SCAD-IC achieve nearly exact support recovery and outperform other methods.DCIC, SCAD-CV, and SCAD-IC also deliver substantially lower ASE than the remaining competitors.
  • One-per-block signals: HTP and ABESS show elevated false negatives in the one-per-block setting, corresponding to missed true predictors and higher ASE.The passage links their sparse selections under correlated competitors to weaker recovery.
  • Moderately clustered signals: With moderately clustered signals, DCIC has a clear MCC advantage through low false-positive and false-negative levels.HTP and ABESS omit many true predictors, while SCAD and MCP can have inflated false positives at small n.
  • Moderately clustered signals: In the moderately clustered setting, DCIC’s ASE matches or improves upon the best competitors.The reported outcome indicates competitive estimation performance.
  • Summary: Overall, best-subset methods tend to select overly sparse models under strong correlation, producing higher false negatives and weaker support recovery.This summarizes the reported contrast between DCIC and HTP/ABESS under correlated designs.

C.2 Illustration of the pathwise computation–statistics trade-off

The experiments show that more informative rankings reach favorable statistical performance earlier with smaller searches, while weaker rankings require broader exploration. Data-driven ranking quality and search heuristics determine the computation–statistics trade-off, and DCIC achieves strong support recovery as sample size grows.

  • Pathwise computation–statistics trade-off: Informative rankings achieve low ASE and high MCC at early path iterations while evaluating relatively few models.With less informative rankings, similar accuracy is reached only after the search region expands substantially.
  • Pathwise computation–statistics trade-off: The ranking determines when statistical recovery begins: smaller rank envelopes enter favorable regions at larger λ, whereas weaker rankings delay recovery until model evaluations grow rapidly.This links ranking informativeness, penalty strength, and the size of the explored search space.
  • Ranking procedures: LASSO ranking approaches the favorable τn = 20 reference as n increases, while marginal correlation performs substantially worse under strong correlation.Under the moderate AR(1) design, LASSO remains competitive with the τn = 20 reference across all four metrics, whereas marginal correlation is more adequate in the easier setting.
  • Runtime illustration: On the runtime scale, smaller rank envelopes reach low ASE and high MCC much earlier, while larger envelopes require substantially longer computation.The large-scale illustration uses n = 200, p = 5000, and s∗= 20 under both strongly correlated and AR(1) designs.
  • Search heuristics: The conservative budget-tightening factor 0.6 retains more branches but increases runtime, whereas factor 1.0 is faster with slightly lower recovery accuracy; factor 0.8 offers an intermediate compromise.Reducing the ranked-search prefix also lowers runtime, with p/5 described as a useful compromise between speed and conservatism.
  • Comparison across sample sizes: As sample size increases, HTP, ABESS, and DCIC show the strongest overall support-recovery performance, while HTP and ABESS remain consistently fastest.DCIC is more computationally demanding for small n but its runtime decreases markedly as n increases.
Loading 2608.26618v1…