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

1.1 Three questions

• The introduction identifies three unresolved challenges: dependence-robust selection, selection across heterogeneous classes, and explicit control of the computational cost of exploring exponentially many models.DCIC addresses them through coded model complexity rather than restrictive near-orthogonality assumptions or uniform size-only penalties.Source: §1.1 · pp. 2–3, §1.4 · p. 7

1.2 A descriptive-complexity framework and main results

• DCIC establishes selection consistency without RIP/SRC-type conditions and provides nonasymptotic oracle risk bounds under model misspecification through approximation-error separation.The framework can imply minimax-adaptive rates in canonical settings while accommodating arbitrary mean vectors for risk analysis.Source: §1.1 · p. 2, §1.2 · p. 4
• DCIC compares heterogeneous model classes using a common Kraft-admissible complexity scale, with class-label cost of order log M, enabling class–model recovery and risk adaptation.The extension is illustrated through adaptive basis-family selection in sparse additive models.Source: §1.1 · p. 2, §1.2 · p. 4
• Along the decreasing-λ path, larger penalties produce polynomial-size retained regions, while smaller penalties expand search and sharpen the oracle risk benchmark under misspecification.The path also provides finite-sample false-positive and false-negative control and an exact-recovery region under beta-min conditions.Source: §1.1 · p. 2, §1.2 · p. 4

1.3 Motivating illustrations of the computation–statistics trade-off

• The motivating illustrations show DCIC improving support recovery in well-specified correlated designs and identifying more strong variables under misspecification, with lower ASE than competitors at sufficiently small λ.These gains occur as the selected model expands along the path, at additional computational cost.Source: §1.3 · pp. 4–5, Figure 1 · p. 5, Figure 2 · p. 5

1.4 Related literature

• Relative to coding-based risk theory, information criteria, correlated-design subset-selection work, and solution-path methods, DCIC unifies model-specific complexity, selection, adaptation, and computation-guided search.The paper positions DCIC as complementary to mixed-integer optimization rather than a replacement for modern solvers.Source: §1.4 · pp. 6–7

2 Model selection consistency of DCIC

• The atom-level formulation represents structured candidate collections as admissible unions of selection atoms, with complexity gaps and local/global multiplicity controls defined at the atom level.Additive atom-level codes automatically control overfitted models, leaving APP bounds for underfitted and wrong competitors.Source: §2 · p. 8, §2.1 · p. 9

2.1 Model selection consistency of DCIC

• Under APP-separation conditions, DCIC is selection consistent when Kraft complexity controls overfitted models, omitted atoms create signal loss, and wrong models are separated by approximation error.The theorem handles wrong models in two stages: sufficiently large penalty gaps eliminate some automatically, while borderline cases require additional approximation-error separation.Source: §2.1 · pp. 8–9

2.2 Consistency for all-subset selection

• For all-subset selection, the framework recovers the fixed-size BSS consistency margin as a special case while allowing alternative EBIC-order complexities that penalize large models less heavily.When s* is fixed, s log p and s log(ep/s) + log p are equivalent in order; diverging s* may require stronger dimensional penalties.Source: §2.2 · p. 10

2.3 Consistency for group selection

• For group selection, treating groups as atoms yields Kraft complexity proportional to the number of selected groups and consistency under corresponding APP-separation conditions.The construction uses p = m×d and complexity C_S = g log m.Source: §2.3 · pp. 10–11

2.4 Consistency for double-sparse structure

• For double-sparse models, DCIC combines group-selection and within-group sparsity codes, with four Kraft-admissible terms encoding groups, active variables, active-group counts, and subset sizes.Theorem 2.1 then gives selection consistency under the corresponding APP-separation conditions.Source: §2.4 · p. 11

2.5 Representative designs with strong dependence

• Under equicorrelation, weak alignment, and shadow-predictor designs, DCIC remains selection consistent with beta-min conditions of order σ^2(log p + log n)/n, even when RIP/SRC fail.When log n = O(log p), the scale is optimal for subset selection; in Scenarios 1 and 3, the condition becomes β_min^2 ≥ cσ^2s*log p/n.Source: §2.5 · p. 12

• DCIC remains risk-valid for misspecified candidate collections, including settings where strong dependence makes exact model recovery too stringent.The analysis does not assume a distinguished true model S∗ and instead evaluates approximation and estimation performance.Source: §3 · p. 12
• Theorem 3.1 bounds DCIC risk by the best approximation–complexity trade-off over the candidate collection.The result holds with high probability for penalties λ≥λrisk and confidence level δ∈(0,1), under the stated Kraft and ηn conditions.Source: §3 · p. 13
• For all-subset selection, CS=s log(ep/s)+log p with ηn=log n and α=2 yields the minimax rate over s∗-sparse linear models without design assumptions.The specialization additionally takes log n=O(log(ep/s∗)).Source: §3 · p. 13
• Group selection with CS=g log(em/g)+log m matches the minimax rate up to a logarithmic factor in the within-group estimation term.Double-sparse selection uses an additional structured code length and is minimax optimal under the stated sparsity condition.Source: §3 · p. 13

4 Model-class uncertainty

• DCIC aggregates class–model pairs with an added log M identification cost, preserving Kraft admissibility and enabling multi-class selection consistency under a unique identifiable true pair.When classes are statistically indistinguishable, risk adaptation is the more natural target than exact pair recovery.Source: §4 · p. 13, §4.1 · p. 14

4.1 Multi-class extension of DCIC

• The multi-class risk bound incurs an additional term of order (log M)^2/α/n up to constants, representing the cost of selecting among M classes.The extension remains valid for misspecified class–model candidates through the aggregated risk formulation.Source: §4.1 · p. 15

4.2 Basis-family selection in nonparametric sparse additive models

• In sparse additive regression, DCIC jointly selects the basis family, active components, and within-family representations, achieving the sparse-additive minimax rate up to log M/n when a candidate family attains the optimal univariate rate.If M grows polynomially in n, the class-selection term is (log n)/n and does not affect the overall convergence rate.Source: §4.2 · pp. 15–16

4.3 Fourier, Spline or Wavelet

• Exact family and within-family recovery requires approximation gaps for cross-class competitors to dominate their complexity thresholds; otherwise, the procedure adapts to the best approximation–complexity trade-off.The recovery result assumes a unique finite representation and a unique true class–model pair.Source: §4.3 · pp. 17–18
• For periodic Sobolev functions with β > 4, Fourier has the best one-dimensional rate, while for non-periodic Sobolev classes with β ∈(1, 4], splines are optimal among candidates; for the 1,1([0, 1]) class, Haar is optimal up to a logarithmic factor.The corresponding rates are Fourier n^−2β/(2β+1), spline n^−2β/(2β+1) with Fourier n^−1/2, and Haar n^−2/3 log n in the final class.Source: §4.3 · p. 18

5 A complexity-guided search strategy

• The strategy improves practical tractability through complexity-guided pruning, while providing high-probability retained-region bounds and finite-sample FP–FN control without removing worst-case NP-hardness.It applies to all-subset selection under sub-Gaussian noise, with analogous constructions for other model classes.Source: §5 · p. 18

5.1 Complexity-guided search strategy

• Kraft-admissible model complexities create a λ-dependent budget that determines search order, pruning priorities, retained regions, and the oracle risk benchmark.The preliminary ranking can come from LASSO or marginal correlation, and DCIC minimizer complexity is nondecreasing as λ decreases.Source: §5.1 · p. 19

5.1.1 First-stage pruning of model sizes

• The first pruning stage restricts candidate models to admissible sizes s ≤ s ≤ ¯s, excluding sizes that cannot satisfy the current complexity-budget constraint.The restriction follows from feasibility of the previous minimizer, nonnegative RSS, and monotonicity of model complexity.Source: §5.1.1 · p. 19

5.1.2 Second-stage pruning of candidate variables

• The second stage screens variables within each admissible size, retains only supports satisfying rank-index bounds, and completes optimization by depth-first search with remaining-budget pruning.Theorem 5.2 gives a polynomial-size retained region with high probability when λ ≳ n/log p, while smaller λ sharpens the oracle benchmark.Source: §5.1.2 · pp. 19–20
• Under a uniform code, the polynomial-regime guarantee requires fixed sparsity, whereas rank-adaptive coding permits s∗log∗(τn) ≤ c1 log p.Here τn is the maximum preliminary rank of the true support, and the condition ensures the true support satisfies the budget constraint.Source: §5.1.2 · p. 20

5.2 FP and FN guarantees along a λ-path

• With probability at least 1 − cδ, the λ-path couples false positives and false negatives; under beta-min conditions, an interval can yield exact recovery bSλ = S∗.The exact-recovery interval is nonempty under stated growth and penalty conditions, including ηn = log n and polynomial growth of L and s∗.Source: §5.2 · p. 21

5.3 A concrete λ-path and the computation–statistics trade-off

• The concrete geometric λ-path remains polynomial in p through kpoly ≍ log_1/ρ p, while continuing beyond that boundary reaches minimax oracle risk near kstat.A smaller τn moves statistical entry earlier; when kstat ≲ kpoly, conservative stopping and risk-optimal continuation are both available.Source: §5.3 · pp. 21–22, Table 1 · p. 22, Table 2 · p. 23

6.1 All-subset selection under strongly correlated designs

• Under severe within-block collinearity, no method achieves exact support recovery, but DCIC robustly controls FP and FN while sustaining high MCC and strong parameter estimation.HTP and ABESS tend to underselect, whereas penalized competitors generally show higher FP or weaker overall recovery.Source: §6.1 · p. 26, Figure 4 · p. 26

6.2 Empirical evaluation of multi-class basis selection

• DCIC achieves the lowest ASE and highest MCC among non-oracle competitors under Fourier and spline truth, while FIA and ORA rapidly approach one.Under spline truth, the LASSO-type baseline reduces FN but substantially inflates FP, weakening overall recovery.Source: §6.2 · p. 28, Figure 5 · p. 28, Figure 6 · p. 29
• Under Haar truth, DCIC attains the highest FaMCC over most sample sizes, indicating accurate family identification and within-family sparse-structure recovery.Figures 5–7 demonstrate adaptation across ordered and subset-selection families.Source: §6.2 · p. 29, Figure 7 · p. 29

Main contributions

• DCIC achieves selection consistency and nonasymptotic oracle risk bounds under sub-Weibull noise and model misspecification without RIP/SRC-type near-orthogonality conditions.Its guarantees rely on approximation-error separation and remain applicable under strong predictor dependence.Source: §7 · p. 30

Class uncertainty

• Encoding class labels places heterogeneous model classes on a common complexity scale, enabling exact pair recovery under identifiability and risk adaptation across classes.The framework addresses uncertainty over both models and model classes.Source: §7 · p. 30

Computation–statistics trade-off

• Larger λ yields polynomial-size retained search regions with high probability, whereas smaller λ sharpens the oracle risk benchmark; the path also controls false positives and false negatives.This complexity-guided path makes the computation–statistics trade-off explicit.Source: §7 · p. 30

Empirical scope and future work

• Simulations illustrate stable DCIC behavior under strongly correlated designs and basis-family uncertainty, while robust criteria for weaker tails and contaminated observations remain future work.The proposed extension direction is motivated by Oliveira and Resende (2025).Source: §7 · p. 30

A Proofs of main results

• For overfitted models, (A1) imposes complexity dominance over the target model and controls complexity growth across model-size differences.The argument uses C_S ≥ C_S* together with the relation between model-size differences and complexity terms.Source: A Proofs of main results · pp. 30, 32
• For underfitted and wrong models, (A2) and (A3) provide the separation conditions used to control approximation error, truncation, and stochastic terms.The wrong-model case uses truncation constants B_S, while the underfitted case invokes auxiliary lemmas to obtain the required bounds.Source: A Proofs of main results · pp. 30, 33, 35
• Lemma A.1 establishes the central three-case reduction for overfitted, underfitted, and wrong competing models under assumptions (A1)–(A3).The proof treats the three model classes separately and combines the resulting bounds.Source: A Proofs of main results · pp. 30–31

A.1 Proof of Theorem 2.1

• The proof of Theorem 2.1 verifies Lemma A.1’s assumptions: (A1) and (A2) directly from Theorem 2.1’s assumptions, then (A3b), yielding verification of (A3).Source: §A.1 · pp. 35–37
• The (A3b) verification combines the theorem’s approximation-error assumption with minimization and arithmetic–geometric mean arguments to cover both truncation regimes.When u_S < 2B_S, the theorem assumption supplies APP(S) ≥ 2(2B_S − u_S); when u_S ≥ 2B_S, the proof uses a separate bound.Source: §A.1 · p. 37

A.2 Proof of Corollary 2.3

• Corollary 2.3 first verifies that the induced model complexities satisfy the Kraft inequality required by Theorem 2.1.The proof then shows the relevant summation term is uniformly bounded in j, so (A1) holds because η_n → ∞.Source: §A.2 · pp. 37–38
• The corollary’s remaining assumptions coincide with conditions (ii)–(iii) of Theorem 2.1, so its conclusion follows directly from that theorem.The proof also verifies (A1) for overfitted models using U(S*) ⊆ U(S) and the prescribed choice of λ_sel.Source: §A.2 · pp. 37–38

Selection-consistency result

• The double-sparse selection-consistency conclusion follows once the assumptions of Theorem 2.1 are verified under the conditions of Corollary A.2.The proof establishes the Kraft inequality and verifies the remaining theorem assumptions.Source: §A.3 · pp. 38–40

Kraft inequality

• The double-sparse code complexity is CS = g log m + s log d + 2 log(g + 1) + 2.Summing the code weights over all double-sparse supports verifies Kraft admissibility.Source: §A.3 · pp. 38–39

Overfitted-model control

• For sub-Weibull noise, the proof assumes g*≤d^γ and takes λ≥λ_sel ∨ c_{α,ζ}(1 + γ)^(2/α) to control overfitted models.The lower bound on λ makes the exponential-bound coefficient exceed 1 + γ, enabling the required summability.Source: §A.3 · pp. 38–39

Sub-Gaussian specialization

• In the sub-Gaussian case α=2, the restriction g*≤d^γ and the γ-dependent lower bound on λ can be removed by taking η_n=A_η log n when g*≤n.This modification leaves the order of the separation conditions unchanged.Source: §A.3 · p. 39

Overfitted-model control

• The overfitted-model argument groups supports by excess size j, bounds the associated code sums using monotonicity and Vandermonde’s identity, and obtains assumption (A1).For supports with Δ+(S)=j, the proof writes t=g−g* and uses j≥1 together with η_n→∞.Source: §A.3 · pp. 39–40

A.4 Proof of Theorem 2.8

• The proof establishes lower bounds for APP(S) over S ∈ Msub ∪ Mw and then applies Corollary 2.4 to obtain the desired selection consistency.Source: §A.4 · pp. 40, 43
• Wrong models larger than twice the true size are automatically excluded for sufficiently large n, while remaining wrong models satisfy the required lower bounds.For s > 2s∗, the proof obtains 2B_S < u_S; smaller wrong models are handled with rank and complexity terms.Source: §A.4 · p. 42

A.5 Proof of Theorem 3.1

• Theorem 3.1’s proof derives simultaneous high-probability inequalities over all candidate models by controlling empirical remainder terms and applying union bounds with Kraft admissibility.The two remainder controls separately use quadratic-form concentration and Lemma B.2, then combine for every λ ≥ λrisk with probability at least 1 − δ.Source: §A.5 · pp. 44–46
• The risk-proof construction controls rem1(S) and rem2(S) separately before combining them into the DCIC comparison uniformly over the candidate collection.The argument uses x_S based on C_S + log(4/δ), the projection rank r_S, and the Kraft inequality.Source: §A.5 · pp. 45–46

A.6 Precise formulation and proof of Corollary 4.1 using class-model pairs

• Corollary A.4 formulates selection over aggregated class–model pairs, assuming a unique true pair and pair-indexed support and submodel conditions.The proof partitions wrong pairs by class membership and extends the single-class assumptions to the pair-indexed candidate list.Source: §A.6 · pp. 47–48
• The aggregated class–model list satisfies the required Kraft and concentration conditions, yielding DCIC(m, S) > DCIC(m∗, S∗) for every competing pair.The verification treats the projection rank for (A3a) and defines Γ(m,S) := APP(m, S) + u(m,S) − B(m,S) for (A3b).Source: §A.6 · pp. 48–49

A.7 Proof of Corollary 4.4

• For wrong pairs exceeding (1 + κ)s∗ complexity, the code penalty dominates, giving 2B(m,S) < u(m,S) for sufficiently large n.The argument derives C(m,S) ≥ 2C(m∗,S∗) and then bounds the comparison using D(m,S) and approximation terms.Source: §A.7 · p. 51
• All three conditions of Theorem 2.1 are verified for the aggregated candidate class, yielding Corollary 4.4.The proof separately handles overfitted, underfitted, and wrong pairs before invoking Corollary 4.1.Source: §A.7 · pp. 50, 52

A.8 Proof of Corollary 4.3

• The approximation candidate in Corollary 4.3 has componentwise, estimation, and within-family costs of order g∗r_m◦(n), plus support and class-code costs.The residual c/n term is absorbed because g∗log(ep/g∗) ≥ 1.Source: §A.8 · p. 52

A.9 Proof of Lemma 5.1

• The proof of Lemma 5.1 concludes by adding the two established inequalities and simplifying algebraically.Source: §A.9 · p. 53

A.10 Proof of Theorem 5.2

• Under sub-Gaussian noise, the proof shows B0 = O_P(n) and bounds the candidate collection through the Kraft inequality.The event controlling B0 has probability at least 1 − exp(−c3n), and the search condition implies C_S ≤ B0/λ.Source: §A.10 · pp. 53–54
• When λ ≥ c5 n/log p, the preceding high-probability control establishes the search-size claim in Theorem 5.2.Source: §A.10 · p. 54

A.11 Proof of Theorem 5.3

• Theorem 5.3 is proved by treating competitors in Msup, Msub, and Mw separately through decompositions (10), (12), and (16).The proof selects λζ according to ζ and analyzes each class relative to S∗.Source: §A.11 · pp. 54–56
• For Msup competitors, projection-noise expectations and Lemma B.1 yield conditions ensuring DCIC(S) − DCIC(S∗) > 0.The argument uses E{ε⊤(PS − PS∗)ε} = σ2(rS − rS∗) and the complexity gap xS.Source: §A.11 · pp. 54–55
• For Msub competitors, positive semidefiniteness of PS∗ − PS and Lemma B.2 similarly guarantee DCIC(S) − DCIC(S∗) > 0.The proof assumes cζλζ ≥ 2 and applies the resulting concentration bound to underfitted competitors.Source: §A.11 · pp. 55–56
• For Mw competitors, the proof combines the two preceding arguments and separates models inside and outside the retained region Lλ.Models outside Lλ automatically satisfy DCIC(S) − DCIC(S∗) > 0, while models inside it are handled by the displayed bound.Source: §A.11 · pp. 56–57
• The final theorem bound holds simultaneously for every λ ∈ Λ with probability at least 1−cδ after union bounds and the Kraft condition.The proof combines the classwise bounds, applies a union bound over Λ, and uses Kraft admissibility in the probability control.Source: §A.11 · p. 57

B Auxiliary Lemmas

• The auxiliary lemmas establish concentration tools for independent, mean-zero sub-Weibull (α, ζ) errors with α ∈ (0, 2].Lemma B.1 concerns quadratic forms, while Lemma B.2 provides bounds for deterministic linear forms under the same tail assumption.Source: B Auxiliary Lemmas · p. 58

Overall patterns

• Across covariance mixes, increasing n improves ASE, FP, FN, and MCC, while performance improves as w decreases toward AR(1)-dominated correlation.Improvement rates and method gaps depend on signal clustering and within-block collinearity.Source: §C.1 · pp. 58–59

Setting 1

• With n ≥240 in the one-per-block setting, DCIC and SCAD-IC achieve nearly exact support recovery, while DCIC, SCAD-CV, and SCAD-IC attain substantially lower ASE than other methods.DCIC also keeps false positives and false negatives low; HTP and ABESS show elevated false negatives and higher ASE under correlated competitor variables.Source: §C.1 · pp. 59–60, Figure 8 · p. 59

Setting 2

• In the moderately clustered setting, DCIC has a clear MCC advantage through joint control of false positives and false negatives, while its ASE matches or improves upon the best competitors.HTP and ABESS omit true predictors, whereas cross-validated SCAD and MCP produce inflated false positives at small n.Source: §C.1 · pp. 60–61, Figure 9 · p. 60

Summary

• Under strong correlation, HTP and ABESS tend to select overly sparse models, yielding higher false negatives and weaker support recovery (Zhang et al., 2025).These results support DCIC as a robust model-selection method for strongly correlated designs.Source: §C.1 · p. 61

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

• Informative rankings reach favorable ASE and MCC earlier with smaller search regions, whereas uninformative rankings require substantially larger evaluated searches and later λ-path iterations.The mechanism is that informative rankings reduce τ_n, causing earlier statistical entry at larger λ values; weaker rankings delay recovery until search size grows rapidly.Source: §C.2 · pp. 61–62, Figure 10 · p. 61
• LASSO ranking approximates favorable oracle-prefix rankings under strong correlation and remains competitive under moderate AR(1) correlation, while marginal correlation deteriorates mainly under strong dependence.Under strong correlation, LASSO improves toward the τ_n = 20 reference as n increases; under moderate AR(1), both LASSO and marginal correlation perform reasonably well.Source: §C.2 · pp. 62–63, Figure 11 · p. 62, Figure 12 · p. 63
• Smaller rank envelopes reach low ASE and high MCC earlier in runtime, whereas larger envelopes require longer computation and may miss the favorable statistical region within the same budget.This large-scale illustration uses n = 200, p = 5000, and s∗ = 20 under both strongly correlated and AR(1) designs.Source: §C.2 · p. 63, Figure 13 · p. 64

C.3.1 RSS-based budget tightening

• Across heuristic settings, the RSS-based factor 0.8 provides the intended compromise, retaining near-conservative statistical performance while substantially reducing computation and improving strong-regime recovery.Factor 0.6 retains more branches but causes larger runtime and truncation, whereas factor 1.0 is faster but slightly less accurate, especially under strong correlation.Source: §C.3 · p. 64, §C.3.1 · p. 65, Table 3 · p. 65

C.3.2 Ranked-search prefix size

• Reducing the ranked-search prefix substantially decreases runtime while preserving competitive statistical performance, making the default p/5 a practical compromise between broad and highly restricted searches.The comparison considers prefix sizes {p, p/2, p/5, p/10}; p/5 is faster than p or p/2 and more conservative than p/10.Source: §C.3.2 · pp. 65–66, Table 4 · p. 66

C.4 Additional setting of all-subset selection

• Under the additional AR(1) all-subset setting, HTP, ABESS, and DCIC have the strongest support-recovery performance, with MCC approaching one as sample size becomes moderate to large.False negatives and false positives decrease rapidly with n for these methods; MCP-IC is reasonable, while SCAD-CV retains irrelevant variables and SCAD-IC improves more slowly.Source: §C.4 · pp. 66–67, Figure 14 · p. 67
• HTP and ABESS are consistently fastest, while DCIC is more demanding at small n but becomes markedly faster as screening and pruning eliminate more inferior candidates.The reported runtime pattern is attributed to more favorable recovery regimes enabling stronger pre-search screening and pruning.Source: §C.4 · p. 67