Scalable branch-and-bound model selection with non-monotonic criteria including AIC, BIC and Mallows's $\mathit{C_p}$

• URL: http://arxiv.org/abs/2512.12221v1
• Date: Sat, 13 Dec 2025 07:16:10 GMT
• Title: Scalable branch-and-bound model selection with non-monotonic criteria including AIC, BIC and Mallows's $\mathit{C_p}$
• Authors: Jakob Vanhoefer, Antonia Körner, Domagoj Doresic, Jan Hasenauer, Dilan Pathirana,
• Abstract summary: We introduce a simple but novel bound that enables the development of branch-and-bound algorithms tailored for non-monotonic functions.<n>We demonstrate that our approach guarantees identification of the optimal model(s) across diverse model classes, sizes, and applications.
• Score: 1.3592625530347717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Model selection is a pivotal process in the quantitative sciences, where researchers must navigate between numerous candidate models of varying complexity. Traditional information criteria, such as the corrected Akaike Information Criterion (AICc), Bayesian Information Criterion (BIC), and Mallows's $\mathit{C_p}$, are valuable tools for identifying optimal models. However, the exponential increase in candidate models with each additional model parameter renders the evaluation of these criteria for all models -- a strategy known as exhaustive, or brute-force, searches -- computationally prohibitive. Consequently, heuristic approaches like stepwise regression are commonly employed, albeit without guarantees of finding the globally-optimal model. In this study, we challenge the prevailing notion that non-monotonicity in information criteria precludes bounds on the search space. We introduce a simple but novel bound that enables the development of branch-and-bound algorithms tailored for these non-monotonic functions. We demonstrate that our approach guarantees identification of the optimal model(s) across diverse model classes, sizes, and applications, often with orders of magnitude computational speedups. For instance, in one previously-published model selection task involving $2^{32}$ (approximately 4 billion) candidate models, our method achieves a computational speedup exceeding 6,000. These findings have broad implications for the scalability and effectiveness of model selection in complex scientific domains.

Related papers

• Model Class Selection [2.377712112950261]
  We introduce the idea of model class selection (MCS)<n>In MCS, multiple model collections are evaluated, and all collections that contain at least one optimal model are sought for identification.<n>As a direct consequence, for particular datasets we are able to investigate whether classes of simpler and more interpretable statistical models are able to perform on par with more complex black-box machine learning models.
  arXiv  Detail & Related papers  (2025-11-14T14:43:26Z)
• Generalized Top-k Mallows Model for Ranked Choices [7.389630498367403]
  We present a novel sampling scheme tailored to top-k Mallows models and an efficient algorithm for computing choice probabilities.<n>We also present an active learning algorithm for estimating the model parameters from observed choice data.<n>These contributions provide new tools for analysis and prediction in critical decision-making scenarios.
  arXiv  Detail & Related papers  (2025-10-24T21:49:21Z)
• Automated Constitutive Model Discovery by Pairing Sparse Regression Algorithms with Model Selection Criteria [0.27998963147546146]
  The framework is applied to both isotropic and anisotropic hyperelasticity, utilizing both synthetic and experimental datasets.<n>Results reveal that all nine algorithm-criterion combinations perform consistently well in discovering isotropic and anisotropic materials.
  arXiv  Detail & Related papers  (2025-09-19T14:50:04Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  We study the sample complexity of reinforcement learning in Mean-Field Games (MFGs) with model-based function approximation. We introduce the Partial Model-Based Eluder Dimension (P-MBED), a more effective notion to characterize the model class complexity.
  arXiv  Detail & Related papers  (2024-02-08T14:54:47Z)
• On Least Square Estimation in Softmax Gating Mixture of Experts [78.3687645289918]
  We investigate the performance of the least squares estimators (LSE) under a deterministic MoE model. We establish a condition called strong identifiability to characterize the convergence behavior of various types of expert functions. Our findings have important practical implications for expert selection.
  arXiv  Detail & Related papers  (2024-02-05T12:31:18Z)
• Modeling Choice via Self-Attention [8.394221523847325]
  We show that our attention-based choice model is a low-optimal generalization of the Halo Multinomial Logit (Halo-MNL) model. We also establish the first realistic-scale benchmark for choice estimation on real data, conducting an evaluation of existing models.
  arXiv  Detail & Related papers  (2023-11-11T11:13:07Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• On Statistical Efficiency in Learning [37.08000833961712]
  We address the challenge of model selection to strike a balance between model fitting and model complexity. We propose an online algorithm that sequentially expands the model complexity to enhance selection stability and reduce cost. Experimental studies show that the proposed method has desirable predictive power and significantly less computational cost than some popular methods.
  arXiv  Detail & Related papers  (2020-12-24T16:08:29Z)
• Goal-directed Generation of Discrete Structures with Conditional Generative Models [85.51463588099556]
  We introduce a novel approach to directly optimize a reinforcement learning objective, maximizing an expected reward. We test our methodology on two tasks: generating molecules with user-defined properties and identifying short python expressions which evaluate to a given target value.
  arXiv  Detail & Related papers  (2020-10-05T20:03:13Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.