Revisiting minimum description length complexity in overparameterized models

• URL: http://arxiv.org/abs/2006.10189v4
• Date: Thu, 12 Oct 2023 23:18:22 GMT
• Title: Revisiting minimum description length complexity in overparameterized models
• Authors: Raaz Dwivedi, Chandan Singh, Bin Yu, Martin J. Wainwright
• Abstract summary: We provide an extensive theoretical characterization of MDL-COMP for linear models and kernel methods. For kernel methods, we show that MDL-COMP informs minimax in-sample error, and can decrease as the dimensionality of the input increases. We also prove that MDL-COMP bounds the in-sample mean squared error (MSE)
• Score: 38.21167656112762
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complexity is a fundamental concept underlying statistical learning theory that aims to inform generalization performance. Parameter count, while successful in low-dimensional settings, is not well-justified for overparameterized settings when the number of parameters is more than the number of training samples. We revisit complexity measures based on Rissanen's principle of minimum description length (MDL) and define a novel MDL-based complexity (MDL-COMP) that remains valid for overparameterized models. MDL-COMP is defined via an optimality criterion over the encodings induced by a good Ridge estimator class. We provide an extensive theoretical characterization of MDL-COMP for linear models and kernel methods and show that it is not just a function of parameter count, but rather a function of the singular values of the design or the kernel matrix and the signal-to-noise ratio. For a linear model with $n$ observations, $d$ parameters, and i.i.d. Gaussian predictors, MDL-COMP scales linearly with $d$ when $d<n$, but the scaling is exponentially smaller -- $\log d$ for $d>n$. For kernel methods, we show that MDL-COMP informs minimax in-sample error, and can decrease as the dimensionality of the input increases. We also prove that MDL-COMP upper bounds the in-sample mean squared error (MSE). Via an array of simulations and real-data experiments, we show that a data-driven Prac-MDL-COMP informs hyper-parameter tuning for optimizing test MSE with ridge regression in limited data settings, sometimes improving upon cross-validation and (always) saving computational costs. Finally, our findings also suggest that the recently observed double decent phenomenons in overparameterized models might be a consequence of the choice of non-ideal estimators.

Related papers

• Data-freeWeight Compress and Denoise for Large Language Models [101.53420111286952]
  We propose a novel approach termed Data-free Joint Rank-k Approximation for compressing the parameter matrices. We achieve a model pruning of 80% parameters while retaining 93.43% of the original performance without any calibration data.
  arXiv  Detail & Related papers  (2024-02-26T05:51:47Z)
• Online Variational Sequential Monte Carlo [49.97673761305336]
  We build upon the variational sequential Monte Carlo (VSMC) method, which provides computationally efficient and accurate model parameter estimation and Bayesian latent-state inference. Online VSMC is capable of performing efficiently, entirely on-the-fly, both parameter estimation and particle proposal adaptation.
  arXiv  Detail & Related papers  (2023-12-19T21:45:38Z)
• Parameter-Agnostic Optimization under Relaxed Smoothness [25.608968462899316]
  We show that Normalized Gradient Descent with Momentum (NSGD-M) can achieve a rate-optimal complexity without prior knowledge of any problem parameter. In deterministic settings, the exponential factor can be neutralized by employing Gradient Descent with a Backtracking Line Search.
  arXiv  Detail & Related papers  (2023-11-06T16:39:53Z)
• Exact and general decoupled solutions of the LMC Multitask Gaussian Process model [28.32223907511862]
  The Linear Model of Co-regionalization (LMC) is a very general model of multitask gaussian process for regression or classification. Recent work has shown that under some conditions the latent processes of the model can be decoupled, leading to a complexity that is only linear in the number of said processes. We here extend these results, showing from the most general assumptions that the only condition necessary to an efficient exact computation of the LMC is a mild hypothesis on the noise model.
  arXiv  Detail & Related papers  (2023-10-18T15:16:24Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  We propose to solve linear MDPs through the lens of Value-Biased Maximum Likelihood Estimation (VBMLE) VBMLE is computationally more efficient as it only requires solving one optimization problem in each time step. In our regret analysis, we offer a generic convergence result of MLE in linear MDPs through a novel supermartingale construct.
  arXiv  Detail & Related papers  (2023-10-17T18:27:27Z)
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [61.87673435273466]
  This paper investigates model robustness in reinforcement learning (RL) to reduce the sim-to-real gap in practice. We adopt the framework of distributionally robust Markov decision processes (RMDPs), aimed at learning a policy that optimize the worst-case performance when the deployed environment falls within a prescribed uncertainty set around the nominal MDP.
  arXiv  Detail & Related papers  (2023-05-26T02:32:03Z)
• Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice [79.48432795639403]
  Mirror descent value iteration (MDVI) is an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL) We study MDVI with linear function approximation through its sample complexity required to identify an $varepsilon$-optimal policy. We present Variance-Weighted Least-Squares MDVI, the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs.
  arXiv  Detail & Related papers  (2023-05-22T16:13:05Z)
• Inverting brain grey matter models with likelihood-free inference: a tool for trustable cytoarchitecture measurements [62.997667081978825]
  characterisation of the brain grey matter cytoarchitecture with quantitative sensitivity to soma density and volume remains an unsolved challenge in dMRI. We propose a new forward model, specifically a new system of equations, requiring a few relatively sparse b-shells. We then apply modern tools from Bayesian analysis known as likelihood-free inference (LFI) to invert our proposed model.
  arXiv  Detail & Related papers  (2021-11-15T09:08:27Z)
• A Data-driven feature selection and machine-learning model benchmark for the prediction of longitudinal dispersion coefficient [29.58577229101903]
  An accurate prediction on Longitudinal Dispersion(LD) coefficient can produce a performance leap in related simulation. In this study, a global optimal feature set was proposed through numerical comparison of the distilled local optimums in performance with representative ML models. Results show that the support vector machine has significantly better performance than other models.
  arXiv  Detail & Related papers  (2021-07-16T09:50:38Z)
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions [41.7567932118769]
  Empirical Risk Minimization algorithms are widely used in a variety of estimation and prediction tasks. In this paper, we characterize for the first time the fundamental limits on the statistical accuracy of convex ERM for inference.
  arXiv  Detail & Related papers  (2020-06-16T04:27:38Z)

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.