《过参数化机器学习理论》综述论文_什么是过度参数化

过参数化

ML理论

需积分: 0 131 浏览量更新于2023-05-26 评论收藏 2.03MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

A Farewell to the Bias-Variance Tradeoff?

An Overview of the Theory of Overparameterized Machine Learning

Yehuda Dar

Vidya Muthukumar

†

Richard G. Baraniuk

‡

Abstract

The rapid recent progress in machine learning (ML) has raised a number of scientiﬁc questions

that challenge the longstanding dogma of the ﬁeld. One of the most important riddles is the good

empirical generalization of overparameterized models. Overparameterized models are excessively

complex with respect to the size of the training dataset, which results in them perfectly ﬁtting

(i.e., interpolating) the training data, which is usually noisy. Such interpolation of noisy data is

traditionally associated with detrimental overﬁtting, and yet a wide range of interpolating models

– from simple linear models to deep neural networks – have recently been observed to generalize

extremely well on fresh test data. Indeed, the recently discovered double descent phenomenon

has revealed that highly overparameterized models often improve over the best underparameterized

model in test performance.

Understanding learning in this overparameterized regime requires new theory and foundational

empirical studies, even for the simplest case of the linear model. The underpinnings of this under-

standing have been laid in very recent analyses of overparameterized linear regression and related

statistical learning tasks, which resulted in precise analytic characterizations of double descent.

This paper provides a succinct overview of this emerging theory of overparameterized ML (hence-

forth abbreviated as TOPML) that explains these recent ﬁndings through a statistical signal pro-

cessing perspective. We emphasize the unique aspects that deﬁne the TOPML research area as a

subﬁeld of modern ML theory and outline interesting open questions that remain.

1. Introduction

Deep learning techniques have revolutionized the way many engineering and scientiﬁc problems

are addressed, establishing the data-driven approach as a leading choice for practical success. Con-

temporary deep learning methods are extreme, extensively developed versions of classical machine

learning (ML) settings that were previously restricted by limited computational resources and in-

sufﬁcient availability of training data. Established practice today is to learn a highly complex deep

neural network (DNN) from a set of training examples that, while itself large, is quite small rela-

tive to the number of parameters in the DNN. While such overparameterized DNNs comprise the

state-of-the-art in ML practice, the fundamental reasons for this practical success remain unclear.

Particularly mysterious are two empirical observations: i) the explicit beneﬁt (in generalization) of

adding more parameters into the model, and ii) the ability of these models to generalize well despite

perfectly ﬁtting even noisy training data. These observations endure across diverse architectures in

modern ML — while they were ﬁrst made for complex, state-of-the-art DNNs (Neyshabur et al.,

Electrical and Computer Engineering Department, Rice University. E-mail: ydar@rice.edu

†

Schools of Electrical and Computer Engineering, and Industrial and Systems Engineering, Georgia Institute of Tech-

nology. E-mail: vmuthukumar8@gatech.edu

‡

Electrical and Computer Engineering Department, Rice University. E-mail: richb@rice.edu

arXiv:2109.02355v1 [stat.ML] 6 Sep 2021

Figure 1: Double descent of test errors (i.e., generalization errors) with respect to the complex-

ity of the learned model. TOPML studies often consider settings in which the learned

model complexity is expressed as the number of (independently tunable) parameters in

the model. In this qualitative demonstration, the global minimum of the test error is

achieved by maximal overparameterization.

2014; Zhang et al., 2017), they have since been unearthed in far simpler model families including

wide neural networks, kernel methods, and even linear models (Belkin et al., 2018b; Spigler et al.,

2019; Geiger et al., 2020; Belkin et al., 2019a).

In this paper, we survey the recently developed theory of overparameterized machine learning

(henceforth abbreviated as TOPML) that establishes foundational mathematical principles underly-

ing phenomena related to interpolation (i.e., perfect ﬁtting) of training data. We will shortly provide

a formal deﬁnition of overparameterized ML, but describe here some salient properties that a model

must satisfy to qualify as overparameterized. First, such a model must be highly complex in the

sense that its number of independently tunable parameters

is signiﬁcantly higher than the number

of examples in the training dataset. Second, such a model must not be explicitly regularized in

any way. DNNs are popular instances of overparameterized models that are usually trained with-

out explicit regularization (see, e.g., Neyshabur et al., 2014; Zhang et al., 2017). This combination

of overparameterization and lack of explicit regularization yields a learned model that interpolates

the training examples and therefore achieves zero training error on any training dataset. The train-

ing data is usually considered to be noisy realizations from an underlying data class (i.e., noisy

data model). Hence, interpolating models perfectly ﬁt both the underlying data and the noise in

their training examples. Conventional statistical learning has always associated such perfect ﬁtting

of noise with poor generalization performance (e.g., Friedman et al., 2001, p. 194); hence, it is re-

markable that these interpolating solutions often generalize well to new test data beyond the training

dataset.

The observation that overparameterized models interpolate noise and yet generalize well was

ﬁrst elucidated in pioneering experiments by Neyshabur et al. (2014); Zhang et al. (2017). These

ﬁndings sparked widespread conversation across deep learning practitioners and theorists, and in-

spired several new research directions in deep learning theory. However, meaningful progress in

1. The number of parameters is an accepted measure of learned model complexity for simple cases such as ordinary least

squares regression in the underparameterized regime and underlies classical complexity measures like Akaike’s infor-

mation criterion (Akaike, 1998). For overparameterized models, the correct deﬁnition of learned model complexity

is an open question at the heart of TOPML research. See Section 7.3 for a detailed exposition.

understanding the inner workings of overparameterized DNNs has remained elusive

owing to their

multiple challenging aspects. Indeed, the way for recent TOPML research was largely paved by

the discovery of similar empirical behavior in far simpler parametric model families (Belkin et al.,

2019a; Geiger et al., 2020; Spigler et al., 2019; Advani et al., 2020).

In particular, Belkin et al. (2019a); Spigler et al. (2019) explicitly evaluated the test error of

these model families as a function of the number of tunable parameters and showed that it exhibits

a remarkable double descent behavior (pictured in Figure 1). The ﬁrst descent occurs in the under-

parameterized regime and is a consequence of the classical bias–variance tradeoff; indeed, the test

error peaks when the learned model ﬁrst becomes sufﬁciently complex to interpolate the training

data. More unusual is the behavior in the overparameterized regime: there, the test error is observed

to decrease monotonically with the number of parameters, forming the second descent in the double

descent curve. The double descent phenomenon suggests that the classical bias–variance tradeoff,

a cornerstone of conventional ML, is predictive only in the underparameterized regime where the

learned model is not sufﬁciently complex to interpolate the training data. A fascinating implica-

tion of the double descent phenomenon is that the global minimum of the generalization error can

be achieved by a highly overparameterized model even without explicit regularization, and despite

perfect ﬁtting of noisy training data.

Somewhat surprisingly, a good explanation for the double descent behavior did not exist until

recently even for the simplest case of the overparameterized linear model — for example, classi-

cal theories that aim to examine the optimal number of variables in a linear regression task (e.g.,

Breiman and Freedman, 1983) only considered the underparameterized regime

. Particularly mys-

terious was the behavior of linear models that interpolate noise in data. The aforementioned double

descent experiments (Belkin et al., 2019a; Spigler et al., 2019) inspired substantial TOPML research

in the simple linear model

. The theoretical foundations of this research originate in the studies by

Belkin et al. (2020); Bartlett et al. (2020); Hastie et al. (2019); Muthukumar et al. (2020b) in early

2019. These studies provide a precise analytical characterization of the test error of minimum-norm

solutions to the task of overparameterized linear regression with the squared loss (henceforth abbre-

viated as LS regression). Of course, linear regression is a much simpler task than learning a deep

neural network; however, it is a natural starting point for theory and itself of great independent in-

terest for a number of reasons. First, minimum `

-norm solutions to linear regression do not include

explicit regularization to avoid interpolating noise in training data, unlike more classical estimators

such as ridge and the Lasso. Second, the closed form of the minimum `

-norm solution to linear

regression is equivalent to the solution obtained by gradient descent when the optimization process

initialized at zero (Engl et al., 1996); thus, this solution arises easily and ubiquitously in practice.

2. For example, the original paper (Zhang et al., 2017) now appears in a 2021 version of Communications of the

ACM (Zhang et al., 2021). The latter survey highlights that almost all of the questions posed in the original paper

remain open.

3. This problem is usually called principal component regression. Recently, Xu and Hsu (2019) showed that double

descent can occur with principal component regression in the overparameterized regime.

4. The pioneering experiments by Belkin et al. (2018b) also inspired a parallel thread of mathematical research on

harmless interpolation of noise by nonparametric and local methods beginning with Belkin et al. (2018a, 2019b);

Liang and Rakhlin (2020). These models are not explicitly parameterized and are not surveyed in this paper, but

possess possible connections to TOPML research of future interest.

1.1. Contents of this paper

In this paper, we survey the emerging ﬁeld of TOPML research with a principal focus on founda-

tional principles developed in the past few years. Compared to other recent surveys (Bartlett et al.,

2021; Belkin, 2021), we take a more elementary signal processing perspective to elucidate these

principles. Formally, we deﬁne the TOPML research area as the sub-ﬁeld of ML theory where

1. there is clear consideration of exact or near interpolation of training data

2. the learned model complexity is high with respect to the training dataset size. Note that the

complexity of the learned model is typically affected by (implicit or explicit) regularization

aspects as a consequence of the learning process.

Importantly, this deﬁnition highlights that while TOPML was inspired by observations in deep

learning, several aspects of deep learning theory do not involve overparameterization. More strik-

ingly, TOPML is relevant to diverse model families other than DNNs.

The ﬁrst studies of TOPML were conducted for the linear regression task; accordingly, much of

our treatment centers around a comprehensive survey of overparameterized linear regression. How-

ever, TOPML goes well beyond the linear regression task. Overparameterization naturally arises in

diverse ML tasks, such as classiﬁcation (e.g., Muthukumar et al., 2020a), subspace learning for di-

mensionality reduction (Dar et al., 2020), data generation (Luzi et al., 2021), and dictionary learning

for sparse representations (Sulam et al., 2020). In addition, overparameterization arises in various

learning settings that are more complex than elementary fully supervised learning: unsupervised and

semi-supervised learning (Dar et al., 2020), transfer learning (Dar and Baraniuk, 2020), pruning of

learned models (Chang et al., 2021), and others. We also survey recent work in these topics.

This paper is organized as follows. In Section 2 we introduce the basics of interpolating so-

lutions in overparameterized learning, as a machine learning domain that is outside the scope of

the classical bias–variance tradeoff. In Section 3 we overview recent results on overparameterized

regression. Here, we provide intuitive explanations of the fundamentals of overparameterized learn-

ing by taking a signal processing perspective. In Section 4 we review the state-of-the-art ﬁndings on

overparameterized classiﬁcation. In Section 5 we overview recent work on overparameterized sub-

space learning. In Section 6 we examine recent research on overparameterized learning problems

beyond regression and classiﬁcation. In Section 7 we discuss the main open questions in the theory

of overparameterized ML.

2. Beyond the classical bias–variance tradeoff: The realm of interpolating solutions

We start by setting up basic notation and deﬁnitions for both underparameterized and overparam-

eterized models. Consider a supervised learning setting with n training examples in the dataset

D = {(x

, y

)}

i=1

. The examples in D reﬂect an unknown functional relationship f

true

: X → Y

that in its ideal, clean form maps a d-dimensional input vector x ∈ X ⊆ R

to an output

y = f

true

(x), (1)

where the output domain Y depends on the speciﬁc problem (e.g., Y = R in regression with scalar

response values, and Y = {0, 1} in binary classiﬁcation). The mathematical notations and analysis

in this paper consider one-dimensional output domain Y, unless otherwise speciﬁed (e.g., in Section

5). One can also perceive f

true

as a signal that should be estimated from the measurements in D.

Importantly, it is commonly the case that the output y is degraded by noise. For example, a popular

noisy data model for regression extends (1) into

y = f

true

(x) +  (2)

where  ∼ P



is a scalar-valued noise term that has zero mean and variance σ



. Moreover, the noise

 is also independent of the input x ∼ P

The input vector can be perceived as a random vector x ∼ P

that, together with the unknown

mapping f

true

and the relevant noise model, induces a probability distribution P

x,y

over X × Y

for the input-output pair (x, y). Moreover, the n training examples {(x

, y

)}

i=1

in D are usually

considered to be i.i.d. random draws from P

x,y

The goal of supervised learning is to provide a mapping f : X → Y such that f(x) constitutes

a good estimate of the true output y for a new sample (x, y) ∼ P

x,y

. This mapping f is learned

from the n training examples in the dataset D; consequently, a mapping f that operates well on a

new (x, y) ∼ P

x,y

beyond the training dataset is said to generalize well. Let us now formulate the

learning process and its performance evaluation. Consider a loss function L : Y × Y → R

≥0

that

evaluates the distance, or error, between two elements in the output domain. Then, the learning of

f is done by minimizing the training error given by

train

(f) =

i=1

L(f(x

), y

). (3)

The training error is simply the empirical average (over the training data) of the error in estimating

an output y given an input x. The search for the mapping f that minimizes E

train

(f) is done within

a limited set F of mappings that are induced by speciﬁc computational architectures. For example,

in linear regression with scalar-valued response, F denotes the set of all the linear mappings from

X = R

to Y = R. Accordingly, the training process can be written as

f = arg min

f∈F

train

(f) (4)

where

f denotes the mapping with minimal training error among the constrained set of mappings

F. The generalization performance of a mapping f is evaluated using the test error

test

(f) = E

x,y

[L(f(x), y)] (5)

where (x, y) ∼ P

x,y

are random test data. The best generalization performance corresponds to the

lowest test error, which is achieved by the optimal mapping

opt

= arg min

f:X→Y

test

(f). (6)

Note that the optimal mapping as deﬁned above does not posit any restrictions on the function

class. If the solution space F of the constrained optimization problem in (4) includes the optimal

mapping f

opt

, the learning architecture is considered as well speciﬁed. Otherwise, the training

procedure cannot possibly induce the optimal mapping f

opt

, and the learning architecture is said to

be misspeciﬁed.

剩余47页未读，继续阅读

syp_net

粉丝: 147
资源: 1197

会员权益专享

《过参数化机器学习理论》综述论文

评论0

会员权益专享

最新资源

《过参数化机器学习理论》综述论文

评论0

请接着上述内容，继续完成机器学习的综述

自动化机器学习（AutoML）之自动贝叶斯调参

机器学习中的trick

学习机器学习有哪些挑战

机器学习python大作业

请向我详细介绍一下2.2.1 自动化机器学习

机器学习 深度学习

sklearn通用机器学习

制作 3d 软体机器人的机器学习算法

机器学习算法的数学解析与python实现

python机器学习代码及数据

机器学习个人笔记完整版v5.4.docx

怎么将pytest框架中的yaml参数化升级为mysql参数化

机器学习的三要素两过程

怎样用python进行机器学习

maxwell参数化建模

机器学习如何在卡尔曼滤波中应用

推荐一个基于ChatGPT4的工具.zip

python从入门到精通

会员权益专享

最新资源

机器学习深度学习