【免费】《过参数化机器学习理论》综述论文

需积分: 0 177 浏览量 2021-09-23 11:35:33 上传评论 1 收藏 2.03MB PDF 举报

资源推荐

资源详情

资源评论

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

粉丝: 158
资源: 1196

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

机器学习算法的超参数优化：理论与实践.pdf

机器学习优化方法及超参数设置综述v1.pdf

Isight参数化理论与实例详解

3种常见深度学习重参数化论文、解读、使用方法、实现代码整理（Re-Parameter）

机器学习结课论文-期望最大化（EM）.docx

基于ProE的齿轮参数化设计系统开发毕业论文.doc

近似弧长参数化曲线综述

贝叶斯机器学习前沿进展综述_朱军

《机器学习理论初探》概述

元自步学习（综述论文）

基于机器学习算法在数据分类中的应用研究

机器学习非参数方法.pptx

论文研究-基于参数化流形学习的压缩传感重构方法.pdf

对于吴恩达机器学习的学习笔记

机器学习结课论文-基于多种机器学习算法的分类预测研究

各种机器学习算法的简要回顾-研究论文

斯坦福机器学习课程的笔记

贝叶斯机器学习前沿进展综述

统计机器学习中参数可辨识性研究及其关键问题.pdf

完整车牌号识别程序，可以识别车牌和颜色，可以集成到项目中 支持win7+

ChatGPT教程（终极版）最全整理

博客中Kmeans以及FCM算法数据（免积分）

神经网络回归预测--气温数据集

hugging face的models-openai-clip-vit-large-patch14文件夹

XGBoost+LightGBM+LSTM-光伏发电量预测

中文短信数据集-带标签

Mathwork+Matlab+编程手册

时间序列预测模型实战案例(Xgboost)(Python)(机器学习)包括时间序列预测和时间序列分类，点击即可运行！

Chatgpt 4omni 发布 GPT 4o / chatgpt-4 桌面版 chchatgpt 4 下载 / darkgpt

最新资源

完整车牌号识别程序，可以识别车牌和颜色，可以集成到项目中支持win7+