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

Yanhang Zhang; Wei Liu; Yuhong Yang

stat.MLAug 27, 2026

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

Authors: Yanhang Zhang, Wei Liu, Yuhong Yang

Organizations: Yau Mathematical Sciences Center, Tsinghua University. · Citigroup. · Beijing Institute of Mathematical Sciences and Applications.

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.

Figures & tables

Figure 1: Computation–statistics trade-off under a well-specified, strongly correlated design with

n=200

p=1000

s^{*}=20

\sigma=2

\rho_{\mathrm{in}}=\rho_{\mathrm{out}}=0.9

, and

w=0.5

Figure 2: Computation–statistics trade-off under a misspecified dense-signal model with

n=200

p=1000

\sigma=2

\rho_{\mathrm{in}}=\rho_{\mathrm{out}}=0.7

, and

w=0.5

. The coefficient vector contains

10

strong,

50

moderate, and

940

weak signals. The variables are partitioned into ten equal-sized blocks, each containing one strong and five moderate signals. Signal magnitudes are drawn independently from

\operatorname{Unif}(1,1.3)

\operatorname{Unif}(0.2,0.4)

, and

\operatorname{Unif}(0,0.1)

, respectively, with independent random signs.

Growth of $p$	Computational certificate	Statistical benchmarks
Growth of $p$	$k\leq k_{\rm poly}$	ASE benchmark	Minimax beta-min scale
$n^{\gamma},\gamma>0$	$k\leq\big\lceil\log_{1/\rho}(\gamma\log n)\big\rceil$	$\sigma^{2}s^{*}\log n/n$	$\beta_{\min}^{2}\gtrsim\sigma^{2}\log n/(n\underline{\omega})$
$\exp(n^{\xi}),\ 0<\xi<1$	$k\leq\big\lceil\log_{1/\rho}(n^{\xi})\big\rceil$	$\sigma^{2}s^{*}n^{\xi-1}$	$\beta_{\min}^{2}\gtrsim\sigma^{2}n^{\xi-1}/\underline{\omega}$
$\exp(n)$	$k\leq\big\lceil\log_{1/\rho}(n)\big\rceil$	$\sigma^{2}s^{*}$	$\beta_{\min}^{2}\gtrsim\sigma^{2}/\underline{\omega}$

Table 1: Dimension-dependent scales along the DCIC path. Here

k_{\rm poly}

is the endpoint of the certified polynomial range. The last two columns report the target statistical benchmarks, whose ranking-dependent entry points are given in Table 2 .

Ranking regime	$k\geq k_{\rm stat}$	Certified beta-min scale
Near-oracle: $\tau_{n}\asymp s^{*}$	$\displaystyle k\geq\left\lceil\log_{1/\rho}\left\{\frac{n\log^{}(s^{})}{\log p}\right\}\right\rceil$	$\displaystyle\beta_{\min}^{2}\gtrsim\frac{\sigma^{2}}{\underline{\omega}}\left\{\frac{\log^{}(s^{})}{\log p}+\frac{\log n}{n}\right\}$
Favorable: $\log^{*}(\tau_{n})=o(\log p)$	$\displaystyle k\geq\left\lceil\log_{1/\rho}\left\{\frac{n\log^{*}(\tau_{n})}{\log p}\right\}\right\rceil$	$\displaystyle\beta_{\min}^{2}\gtrsim\frac{\sigma^{2}}{\underline{\omega}}\left\{\frac{\log^{*}(\tau_{n})}{\log p}+\frac{\log n}{n}\right\}$
Uninformative: $\log^{*}(\tau_{n})\asymp\log p$	$\displaystyle k\geq\left\lceil\log_{1/\rho}(n)\right\rceil$	$\displaystyle\beta_{\min}^{2}\gtrsim\sigma^{2}/\underline{\omega}$

Table 2: Effect of ranking quality on the statistical entry and certified beta-min scale along the DCIC path. Here

k_{\rm stat}

denotes the entry index at which the oracle benchmark reaches the minimax ASE scale, and the certified beta-min scale refers to the minimum signal strength for exact recovery within the certified range

k\leq k_{\rm poly}

Panel of Figure 3 — Figure 3: A schematic illustration of the pathwise computation–statistics trade-off. The dashed line marks the boundary of the polynomial-in- $p$ certified region. Panel (a) shows the entry to the minimax ASE benchmark, while panel (b) shows the corresponding exact-recovery entry under the beta-min scale. The colored expressions give high-probability search-size bounds at these entries. An entry lies within the certified region when $k_{\rm stat}\lesssim k_{\rm poly}$ .

Figure 4: Performance metrics under Setting 3 with an increasing sample size. The suffix “-CV” indicates tuning by 10-fold cross-validation. The suffix “-IC” indicates tuning by information criterion.

Figure 5: Performance metrics under Fourier truth with an increasing sample size.

Figure 6: Performance metrics under spline truth with an increasing sample size.

Figure 7: Performance metrics under Haar truth with an increasing sample size.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Performance metrics under Setting 1 with an increasing sample size. The suffix “-CV” indicates tuning by 10-fold cross-validation. The suffix “-IC” indicates tuning by information criterion.

Figure 9: Performance metrics under Setting 2 with an increasing sample size. The suffix “-CV” indicates tuning by 10-fold cross-validation. The suffix “-IC” indicates tuning by information criterion.

Figure 10: Pathwise computation–statistics trade-off under different ranking informativeness. The curves are averaged over 100 replications.

Figure 11: Performance of different ranking procedures under a strongly correlated design.

Figure 12: Performance of different ranking procedures under a moderately correlated AR(1) design.

Figure 13: Representative large-scale runtime illustration of the pathwise computation–statistics trade-off, with

n=200

p=5000

, and

s^{*}=20

. The curves report ASE and MCC against accumulated computational time under different rank envelopes

\tau_{n}

. Panel (a) corresponds to the strongly correlated design in Setting 1 of Section 6.1 , with

\rho_{\mathrm{in}}=\rho_{\mathrm{out}}=0.9

and

w=0.5

; panel (b) corresponds to an AR(1) design with

\Sigma_{ij}=0.6^{|i-j|}

Regime	Budget factor	ASE	MCC	TP	FN	Truncated	Runtime (s)
Moderate	$0.6$	0.730	0.863	7.98	2.02	12	173.52
Moderate	$0.8$	0.738	0.863	7.98	2.02	0	15.85
Moderate	$1.0$	0.779	0.852	7.86	2.14	0	0.82
Strong	$0.6$	1.171	0.647	5.35	4.65	23	283.12
Strong	$0.8$	1.092	0.676	5.76	4.24	1	35.61
Strong	$1.0$	1.201	0.647	5.34	4.66	0	1.51

Appendix

Table 3: Sensitivity to the RSS-based budget-tightening factor.

Regime	Prefix size	ASE	MCC	TP	FN	Truncated	Runtime (s)
Moderate	$p$	2.952	0.870	8.03	1.97	0	22.02
Moderate	$p/2$	2.952	0.870	8.03	1.97	0	13.85
Moderate	$p/5$	2.952	0.870	8.03	1.97	0	2.97
Moderate	$p/10$	2.966	0.868	7.98	2.02	0	0.17
Strong	$p$	5.020	0.675	5.36	4.64	3	177.45
Strong	$p/2$	5.020	0.675	5.36	4.64	3	101.44

Appendix

Table 4: Sensitivity to the ranked-search prefix size.

Figure 14: Performance under the AR(1) design with

\Sigma_{ij}=0.6^{|i-j|}

as the sample size increases. The suffix “-CV” denotes tuning by 10-fold cross-validation, whereas “-IC” denotes tuning by an information criterion.

Model Selection

Model selection chooses models, features, or configurations that balance predictive fit, generalization, complexity, and deployment constraints.

See all 96 papers

Exact Algebraic Computation of Learning Coefficients for Two-Dimensional Singular Models
Aug 20, 2026Grégoire Sergeant-Perthuis, Elias Tsigaridas, Jules TsukaharaSingular Learning Theory
CQSB, Sorbonne Université · Ouragan Team, INRIA · Ouragan team, Inria Paris
How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
Sep 16, 2026Tetsuji KuboyamaModel Selection Selective Prediction
Computer Centre, Gakushuin University
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Jun 3, 2026Qian Li, Xinyu Mao, Shang-Hua Teng +1Minimum Description Length Approximation Algorithms
Shenzhen Research Institute of Big Data · University of Southern California

Aug 20, 2026J/K move · Enter open · S save

Exact Algebraic Computation of Learning Coefficients for Two-Dimensional Singular Models

Grégoire Sergeant-Perthuis, Elias Tsigaridas, Jules Tsukahara

CQSB, Sorbonne Université · Ouragan Team, INRIA · Ouragan team, Inria Paris

Singular Learning Theory

Open paper AskPDF arXiv

Classical information criteria such as the Bayesian Information Criterion (BIC) rely on regularity assumptions that break down for singular models, leading to incorrect model selection in settings such as deep learning. The Widely Applicable Bayesian Information Criterion (WBIC) relies on local learning coefficients

λ

, which in the analytic case coincides with local Real Log Canonical Thresholds (RLCT) of the Kullback-Leibler divergence of the model, to capture correct marginal likelihood asymptotics. Exact computation of the learning coefficients has been limited to special cases, and only sampling-based estimation methods are generally applicable. We present the first deterministic algorithm that computes local RLCTs exactly for any two-dimensional model whose Kullback-Leibler distance is contact equivalent to a polynomial, derive a bound on its complexity, and demonstrate its effectiveness for a broad class of models, with applications including polynomial neural networks. Beyond providing ground truth to calibrate sampling-based estimators, exact computation reveals algebraic structure in learning coefficients that sampling cannot and out-speeds it in the shallow regime.

Abstract

Model Selection

Explore similar work

Exact Algebraic Computation of Learning Coefficients for Two-Dimensional Singular Models

How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction

Prediction Under Imperfect Compression: A Theory of Approximate MDL