Bias/Variance is not the same as Approximation/Estimation
Authors: Gavin Brown
Riccardo Ali
Venue: Accepted by TMLR ()

Abstract: We study the relation between two classical results: the bias-variance decomposition, and the approximation-estimation decomposition. Both are important conceptual tools in Machine Learning, helping us describe the nature of model fitting. It is commonly stated that they are “closely related”, or “similar in spirit”. However, sometimes it is said they are equivalent. In fact they are different, but have subtle connections cutting across learning theory, classical statistics, and information geometry, that (very surprisingly) have not been previously observed. We present several results for losses expressible as Bregman divergences: a broad family with a known bias-variance decomposition. Discussion and future directions are presented for more general losses, including the 0/1 classification loss.

Published in Transactions on Machine Learning Research (02/2024)
B is not the same as
Gavin Brown
wueit.broom@@maanchsseee....uu
Department of Computer Science, The University of Manchester
Riccardo Ali
rma55@cam.ac. uk
Department of Computer Science & Technology, The University of Cambridge
Reviewed on OpenReview: https: opwreevee.. net/ net/ forun? id- 4TTFbvIGNK
Abstract
We study the relation between two classical results: the bias-variance decomposition, and the approximation-estmmaain chine Learning, helping us describe the nature of model fitting. It is commonly stated that they are "closely related", or "similar spirit". However, sometimes is said they are equivalent. In fact. they are different, but have subtle connections cutting across learning theory, classical statisties, and information geometry, that (very surprisingly) have not been previously observed. We present several results for losses expressible as Bregman diver- genee: a broad family with a known bias-variance decomposition. Discussion and future directions are presented for more general losses, including the 0/1 classification loss.
decomposition. Both are important conceptual tools in Ma-
1 Introduction
Geman et al. (1992) introduced the bias-variance decomposition the Machine Learning community, and Vapnik & Chervonenkis (1974) introduced the approxination-cstinen of statistical learning theory. Both decompositions help us understand model fitting: referring to model size, and some kind of trade-off. The terms are often used interchangeably. And yet, they are different things. The approciaatonn-simaaioon decomposition refers to models drawn from some function class F, and considers an ercess risk that is, the risk above that of the Bayes model breaking it into two components:
decomposition, founding the field
excess risk approximation crror + cstimation error.
(1)
We might choose to increase the size of our function class, perhaps by adding more parameters to our model. In this situation it is commonly understood that the approximation error will decrease, and the estimation error will increase (Von Luxburg & Schölkopf, 2011), beyond a certain point resulting in over-fitting of the model. In contrast to the abstract notion of a "function class", the variance decomposition considers the risk of real, trained models, in expectation over possible training scts, Assuming there unique correct response for each given input æ (i.e., no noise) it breaks the expected risk into two components:
expected risk bias variance.
(2)
As we increase model size: the bias tends to decrease, and the variance tends to increase, again determining the degree of over-fittin. Recently, it has bocome apparent that this trado-off is not always simple, c.g. with wver-parameterised models; but, the decomposition still holds even if simple trade-off does not. We note that this decomposition, as used in the Machine Learning literature, concerns inference of the asspossetargge variable-and not of the parameters, as is more common in classical statistics.
It is easy, and common, lo conflate these decompositions. With a literature review (see Appendix C) one can observe innocent (but imprecise) statements such as, they are "similar in spirit", but also the more extreme (and incorreet poorreet/mislaadingg "the trade-off between estimation crror and approximation crror often called the bias/vart bas/vvariacee trade-off". In contrast, we identify the precise relationships. We present detailed analysis for Bregman divergences in section 3, and offer discussion for more general losses in section 4.

---

Published in Transactions on Machine Learning Research (02/2024)
Underfitting Overfitting
Underfitting
Overfitting
excess risk
expected risk
estimation
varlance
approximation
bias
Size of hypothesis space
Number of parameters
Two diagrams (same on /rft/tight is intentional) illustrating how the approximationn/stinatii and bias/varianc variance trade-ofls are commonly described, and easily confused.
Figure 1:
2
Background
We introduce notation and review the two decompositions. We introduce these ideas in an intentionally manner, to avoid any possibility of confusion terminology.
2.1 Preliminaries
Consider a standard supervised learning setup, where the task to map from an input æ E S Rd to an output y C IR* and assume there exists an unknown distribution P(æ, y). This is achieved by learning model f, which can also be as selecting function f from restricted function class F C Fall, where Fall is the space of all measurable functions X' + V. The discrepancy of f f(x) from the true y is quantified with a loss fyy, (x)), which may may not be symmetric. We define the risk of a model f as,
f Myy. ((=) dP(æ, y)
R(S) Eny Ley [())
(3)
A Bayes model y is a (not necessarily unique) function which minimizes this quantity at each m, i.e.
y arg inf R(f), JEF.
where we follow Bach (2023, Prop 2.1) using the convention that the arginf returns set if non-unique. We acknowledge slight abuse of notation, using y² as function in Fau a vector in R as needed the intention will always be made clear from context. Given that we picked restricted family F C Fall. we have no guarantee that contains y" best-in-famill model f is defined similarly,
f" E arg inf R(f). JEF
These are defined in terms of the true distribution P(x, y). In practice, we only have finite sample: points (z), yi,..., (I,, yn) each drawn i.i.d. from P(x, y), as realisation of the random variable D p" The empirical risk of model F is then defined:
Remp (f) 1 1
Σ
elv.. f(x))),
(6)
and a model in that minimizes this, known as an empirical risk minimizer (ERM), is defined:
ferm E arg Rfm
(7)
FEF
Note that form is a random variable, as is dependent on D. The empirical risks are the same for any two ERMs, but their population risks may be different. We cover the specifies for the two decompositions.
2

---

Published in Transactions on Machine Learning Research (02/2024)
2.2 The ppproimattion-Esimaatiee decomposition
The tpproxinattoon-sstmmaiion decomposition is seminal observation from the 1970s work of Vapnik and Chervonenkis, reviewed in Vapnik (1999). An excellent historical account can be found in Bottou (2013).
The result deals with the eacess risk R((ferm) - R(y"), i.e. the risk of ferm above that of the Bayes model, y". The approximation approxination-ssimatioo estimation decomposition, applicable for any loss L, breaks this into two terms:
R(ferm) - R(y")
R(ferm)- -
+ R(y")
(8)
risk
estimation error
approximation error
The approximation error is the additional risk due to using a restricted family F, rather than the space of all functions Fall- This is a systematic quantity, not dependent on any particular data sample. The estimation error is the additional risk due to our finite training data, when trying to find f E F. This random variable, dependent on the particular data sample. There is natural trade-off (see Figure 1, left) as we change the size of F, keeping data size fixed. As we increase [F), approximation error will likely decrease (potentially to zero, if yy E F), but cstimation error will increase, as it becomes harder to find f in the larger space. The reason behind this is, in effect, the classical malliple hypothesis lesting problem we cannot reliably distinguish many hypotheses when our dataset is small. Bottou & Bousquet (2007) extended Equation 8, recognising that it is often intractable to find a global minimum of the training risk, and we can only have a sub-optimal model f. An additional risk component then emerges, and the excess risk of f now decomposes inlo sum of oplimisalion error, estimation error, and approximation error:
RC R(y")
R(} -R(fer))
+ ( + (U)--R(y')
(9)
excess risk of /
optimisation error
estimation error
approximation crror
These three terms describe the learning process in abstract form: accounting respectively for the choice of learning algorithm, the quality/amount /amount of data, and the capacity of the model family.
2.3 The Varianar decomposition
A bias-variance decomposition involves the expected risk of a trained model f. where the expectation ED is over the random variable D ~ P(æx, y)", i.e., all possible training sets of a fixed size n. Focusing on a squared loss, and y E R, Geman et al. (1992) showed:
ED Emn f(x))) Emy (w - --
+ Eg - (DD=(()()))) " + E. -EDI(())) (10)
expected risk
noise
bias
variance
where y" = Eyl is the Bayes-optimal prediction at each point x. The bias a systematic component, independent of any particular training sample, and commonly regarded as measuring the 'strength' of a model. The variance measures the sensitivity of ff to changes in the training sample, independent of the true label y. The noise is constant, independent of any model paramelers. There is again perceived trade-off with these terms (see Figure 1, right). As the size of the (un-regularised) model increases: bias tends to decrease, and variance tends to increase. However, the tradc-off can be more complex (c.g. with over-parameterized models) and the exact dynamics are an open research issue.
Bias- Variance decompositions hold for more than just squared loss. In fact the same form holds for several other losses, including the broad family of Bregman divergences (Brogman, 1967).
Definition 1 (Bregman divergence) For a convex set y C IR, let y + R be a strictly conver func- lion, continuously differentiable on the interior of y, which is assumed non-emply. The Bregman divergence Bø : y x ri())- + [0, oc) is defined, for points p E y and q E ri()), as
Ba(p, = =(p) - ((g)
(11)
The function Φ is conventionally referred to as a 'gencrator' function choice of which leads to different well-known losses, e.g. <(y) =2 gives Bo f) = (y f)2. We refer the reader to Banerjee et al. (2005b) for excellent tutorial on Bregman divergences.
3

---

Published in Transactions on Machine Learning Research (02/2024)
Key to understanding generalised bias-variance decompositions is the notion of centroid. Nielsen & Nock (2009) provide a thorough characterisation for the centroids of Bregman divergences.
Definition 2 (Left-sided Bregman centroid) Assume a Bregman divergence BB : y x ri()) + oo), with generator @ : y/ + R. Define set of models of the form f : X + ri()), induced by random variable D, then the side Bregman centroid of the model distribution is:
id(a)) = arg min ED (Bo(z, = [[+]] =EY
ED ((((())))
(12)
If we choose <(v) = y², then Bølv. f) (y - f)² and fa(m) = ED(s(z)), but this is not always the case. The left centroid is in general a quasi-arithmetic mean, is unique (Nielsen & Nock, 2009, Theorem 3.2), and guaranteed to exist (Nielsen & Nock, 2020, Theorem 1). Examples of Bregman centroids are below.
Table 1: Examples of Bregman divergences, with corresponding left centroids.
Name
Domain
Bo f(x))
Centroid fo(x)
Squared KL-divergence Ikatura-Saito
y E R y E RK 8.t. S.t =1 y E (0,
(w- f-x))2 DKL 11 f(x))
Eo]f(z)] Z exp(plln /()))
nom In taai
1/Eplf(x)-")
A vari-nari decomposition for Bregman divergences was shown by Pfau (2013), taking the form:
ED (yy. [()))]] Bay (o((.)") + E. Boly" fo(:)) + Er (fs(e)
(13)
expected risk
noise
bias
variance
where Jo(ar) is the left centroid, and y" = Eylely] is the Bayes model (Banerjee el al., 2005b, Prop. 1). We note that given f X - ri(V), and the fact that VΦ is a homeomorphism (by the invariance of domain theorem), this implies (x) E ri()). The bias/variane caaviiaieeee terms take different functional forms for each loss. This has a consequence for nomenclature: the term in Equation 10 is sometimes called "squared bias". But, the square is an artefact from using squared loss, not present in other cases, hence we use simply "bias! Note that the KL example implies decomposition for the cross-entropy, since the two differ only by constant. It is interesting to note that generalised decompositions only appeared in the ML community with Heskes (1998), but the idea seemss to be known much earlier in statistics, e.g., Hastie & Tibshirani (1986, Eq. 19).
Bias- Variance decompositions do not hold for all losses. The approximation-cstimatinn docomposi- tion, Equation 9, applies for any loss. This not the case for the bias-variance decomposition. For example, the form of Equation 13 does not hold for the 0/1 loss-in this case, the variance term becomes dependent the label distribution (Friedman, 1997). Several authors proposed alternative decompositions (Wolpert, 1997; James& & Hastie, 1997; Heskes, 1998; Domingos, 2000). It is interesting to note that the concept of the loss centroid also occurs in this literature, referred to as the 'systematic' or 'main' prediction (Geurts, 2002). The necessary and sufficient conditions for such a decomposition are an open research question.
2.4 Summary
These decompositions are conceptual tools to describe the nature of model fitting. They are by no means perfect reflections of the process, most especially in the context of over-parameterized models (Nagarajan & Kolter, 2019; Zhang et al., 2021). However, it is extremely common to see papers making the incorrect assumption/chal /llaim that the two are equivalent, or that one is special case of the other. Our purpose with this work is to correct these false assumptions, identifying precisely how the two connect.
Note that this is a called a left centroid hecause the minimization is over the first (left-hand) argument. The right centroid can be similarly defined by minimizing over the second argument, turning out to simply Ep(f(x) for any valid & (Banerjee et. al., 2005a), which explains why the Bayes-optimal prediction y Fylz y) for any Bregman divergence.
4

---

Published in Transactions on Machine Learning Research (02/2024)
3 Bias/ Vaarinar is not the same as Approximation/Estinanii
By now it should be evident that these decompositions are related, but are not quite the same thing. Perhaps the most obvious difference is that they are on different quantities the excess risk of an ERM, versus the expected risk of an arbitrary trained model. We now build a bridge between the two, using Bregman divergences to include a wide range of losses. We first define a concept, building on Definition 2, that we will refer to repeatedly in the coming sections: the 'centroid model'.
Definition 3 (Centroid model) For model f dependent random variable D, the centroid model fo is the aggregate model formed by taking the left Bregman centroid prediction at each possible Note that whilst by definition fo E Fall, there no guarantee that fo F.
We observe that the estimation error involves R(ferm), making it random variable dependent D. We take the expectation with respect to D and separate it into two, using the risk of the centroid model.
Definition 4 (Estimation Bias, and Estimation Variance) For Bregman divergence Bø the er- pected eslimation error own be decompposed to expose two lerma: the estimation bias, and estimation variance.
ED ( R()) = ED [(ferm) [R((er))-R((a) + -Rff)
R(F))
(14)
expected estimation
estimation variance
estimation bias
The estimation variance measures the random variations of ferm around the centroid model. The estimation bias measures the systematic difference between the centroid model and the best-in-family model. Using these concepts, we present the relation between the two decompositions.
Theorem (Bias-Varianns Variance in terms of Approximation--stimaatoo Given a Bregman divergence (xx)), the following decomposition of the lias and variance applies.
Eg Bo fo(z))
R(*) R(y")
+ R(fo) R(f*)
(15)
approximation error
estimation hins
bius
Ex
Ep Bo (f
f(x))]
Ep R(f) - - R(ferm)
+ ED R(ferm) - R(fa)
(16)
optimisation error
estimation variance
This confirms the premise of our work. Bias is not approximation error, and variance is not estimation error. It not even the case that one is a special case of the other, as is sometimes stated. The true relation is more subtle. The approximation error is in fact just one component of the bias, and, the estimation error contributes to both bias and variance. The thcorem above is illustrated in Figure 2.
expected risk
optimization error
estimiatio
approximation error
Bayes enor
error
variance
bias
noise
Figure 2: Mustration of Theorem 1. The bias only partly determined by approximation error (i.e. choice of model), while the rest is due expected estimation error (i.e. choice of data). Similarly, variation in data accounts for only part of the variance, and the rest is due to optimisation error (i.e. choice of algorithm).
5

---

Published in Transactions on Machine Learning Research (02/2024)
4 Discussion
A simplistic description of bias and variance would say they are the error 'due to the model' (bias) and the error 'due to the data' (variance). Theorem 1 shows there is more mance to understand. We now discuss the subtleties and implications of these results. For ease of referral we denole: Expp (approximation error), Eest (expected estimation error); Eest()) (estimation bias), and Eest(o) (estimation variance).
4.1 The case of linear least squares
Assune a linear model f(x) x, 3, and a squared loss. The parameters 3 are fit using a dataset {X, y where X is an nxd d matrix, and y is column vector of length n. As before, this training data is realisation of the random variable D. The ridge regression solution is Bx = x -XI--IX'' y where X = 0 is OLS. The best-in-family model f", with F (f(xz) = x B R uses parameters B. which minimise the squared risk, i.c., B_ == arg ming Eæy x g) E. <x -
Eaylayy) Furthermore, due to the unbiasedness of OLS, Eplso] B.. In this sccnario, the varianc dccomposition is,
ED Eny (w x aTBB>' []
Ezy
(v - y w³)²
+ Exr (w' - En [+ 3A1) + En ED (00 Bx - En|æ"
expected risk
noise
blas
variance
(17)
Hastie et al. (2017, Eq 7.14) describe" how the bias term decomposes more finely:
Em (v" Ep(=" BA]DP]
Em (u" - x² 3.) + En (x=B. B. - Ep fa BB))
(18)
Hastie's 'model bias'
Hastie's 'estimation bias'
Though they refer to the first term as 'model bias', it turns out that is exactly equal to the approximation error for a linear model. Similarly, their 'estimation bias', whilst written differently, is exactly the estimation bias we have defined, but for a linear model. These observations are formalized in the following theorem.
Theorem The "model bias/ talissiimation bias' decomposition (Equation 18) is a special case of our bias decomposition (Equation 15) for the specific case of linear model with squared loss.
We also note that, due to the unbiasedness of OLS, we have both Eapt 0 and Eest(b) 0. Thus, for this special case, bias is equal to the approximation error, and variance is equal to (what remains of) the estimation error. The decompositions are (numerically) equivalent in the OLS scenario, but in general they are very different. This is most clear in the general case behaviour of the estimation bias, discussed next.
4.2 The bias is a flawed proxy for model capacity.
Tt is common to assume the bias is an indication of how simple/complex a model is expected to be lower if the model has higher 'capacity: But what is model 'capacity"? If we define as the ability to minimize population risk, then the ultimate measure of model capacity is the approzimation error. We see in Equation 15 that the bias contains exactly this, but also the estimation bias, which gives it some surprssing dynamics. As detailed above, Hastie et al's observations were restricted to the linear case for analytic tractability. The linear model assumption meant that they were unable to observe a critical fact that in the general case, the estimation bias Ee R(fo) R(f*), can take negative values, i.e.
bias = opprooximation error
Testimation bios
(19)
always 2
can be negative
To understand how this can be, we must accept the somewhat non-intuitive idea that the centroid model can be outside the hypothesis class F, and thus we have R(fs) < R(f"). This can be trivially illustrated, with a simple regression stump evaluated by squared loss, in Figure 3.
It is likely that Hastie were the first to observe this, but it commonly known reference for the statement.

---

Published in Transactions on Machine Learning Research (02/2024)
Stump 1
Stump
10
Stump
9
Stump
X
8
x 1.6
x 2
x x
x 2.1
7
6
y 6.1
y y=
y 9.8
0
2
Figure 3: Two regression stumps (red/blue lines), and their centroid model (black line, arithmetic mean). Notice the centroid model outside the hypothesis class, iee. it cannot be represented as a single binary stump. As a result, the centroid model fits the data better than any f E F, and Eest(b) negative.
The possibility of negative values here has significant implications. There are two ways in which bias can be zero. If F contains the Bayes model, then we might have Eapp = (es((b) = 0. But, there is another way. For some > 0, we might have Eapp = e, and (es((h) = -e. In this case, the model family does not have sufficient capacity, since Eapp > And yet, the bias is zero. Hence, the bias is flawed proxy for the true model capacity. To illustrate this, show experiments
synthetic problem. Details in Appendix B.
Figure 4 shows results increasing the depth of decision tree. The left panel shows excess risk, and the bias/vande variance components. We observe the classical bias/variance trade-off, including overfitting, as the depth increases beyond a certain point. is notable that the bias decreases to zero, after depth Does this imply the model is 'unbiased', in the sense that it has sufficient capacity to capture the full data distribution?
Excess risk
Bias
10
Variance
Apprakimation error
0
Estimation Bias
2
12131415
10 13
max_depth
max_depth
Figure 4: Risk components increase the depth of regression tree.
The answer no. decompasition of the bias into two components (right panel) shows that the Eupp is non-zero, i.c. the best possible model cannot achieve zero testing error. The cause of the bias going to zero is that Eest(b) is negaliue, hence the bias is not good proxy for the true model capacity. Similar results are obtained with a k-nn regression (Figure 5), where increasing complexity corresponds to decreasing k.
10
Excess risk
Bias
Variance
Apprakimation error
Estimation Bias
12
11
10
8
7 6 5
3
2
12
11
10
9
8
6
5
4
3
2
n_neighbors
n_neighbors
Figure 5: Risk components as we decrease the number of neighbours in a k-nn.

---

Published in Transactions on Machine Learning Research (02/2024)
We can formally characterise this phenomenon, by studying the geometry of the hypothesis class F. In particular, the set FF dual-conver (Amari, 2008, Equation 32) with respect to Φ, then fo F, and hence estimation bias is guaranteed to be non-negative.
Theorem 3 (Sufficient condition for a non-negative estimation bias.) If the hypothesis class F is dual-conver then the estimation bias is non-negative.
A simple example of a non-dual convex set is the class regression stumps evaluated by squared loss, where fz( = En[f(=)], illustrated in Figure 3. A simple example of dual-convex set is the class of Generalized Linear Models evaluated by their corresponding deviance measure.
Theorem (GLMs have non-negative estimation bias.) For a Breyman divergence with generalor function 6, define F as the set of all GLMs with inverse link [Vø] and natural parameters O Rd. Then, the estimation bias is non-negative.
An example of this would be logistic regression, f(x:) = [vo)- 1/(1 exp(-0"x::)) a:), which results from @(f) = f In f) ln(1 f) and the binary KL is the corresponding Bregman divergence.
4.3 The estimation variance plays a role double descent.
In recent literature, an increasing degree oveo-vvevaaaa wwer-paramnttriiationn has been associated with a 'peaking' trend in the variance (Nakkiran, 2019; Yang et al., 2020), ultimately causing a double descent the risk.
Risk Peaking
Variance Peaking
Error
Sweet Spo
Model Complexity
Figure 6: Illustration of double descent, caused by 'peaking' variance (red line) and monotonically decreas- ing bias (blue line). Image credit Yang et al. (2020).
Such models often fit their training data perfectly (Belkin et al., 2019; Zhang et al., 2021), i.e,, they interpolate the data. If we consider this in the context of Equation 16, we see that:
variance
estimation variance
optimisation error
for interpolating models
i.c., the optimization error is close to zero. This observed 'pcaking' variance must therefore be primarily due to the eslimation variance, Eest(e)- Furthermore, very deep models are likely to be able to fit any function, i.., their approximation error is zero. In these scenarios, the only terms remaining in the expected risk are Eea(()) and Eest(e)- Why such models can push training error zero, even on random labels, and still generalise well, remains an open question for modern machine learning (Zhang et al., 2021). Overall, we believe this warrants further study in the context of deep models.
8

---

Published in Transactions on Machine Learning Research (02/2024)
4.4 New insights into the bias/variance trade-off.
In recent years; the relevance (and even existence) of a trade-off between bias and variance has been de- bated, with voices both against (Neal et al., 2018; Dar et al., 2021) and in favour (Witten, 2020). However with estimation bias and estimation variance, in certain circumstances, we observe that the tradc-off is an indisputable fact. We first note that Eeet(b) + Eest(u) = Eest 2 O. Thus, when one of these quantities is negative, the other is forced to be positive and lower bounded by the magnitude of the negative term. For example, when the estimation bias negative (e.g. Figure 3), it obviously reduces the bias. However this implies that the variance increases, since Enst(o) 2 -Enst(h); to satisfy the constraint. This is not the case for Hastie et al's terms, using linear model / squared loss, since this is (generalized) linear model and its corresponding deviance measure, in Theorem 4. However, negative estimation bias is entirely possible in other scenarios, implying the variance (and indeed overall expected risk) is positive. This is an unavoidable trade-off. Clearly, other components of the bias/ /variancee may mask this behaviour, making it less obvious.
4.5 What if a bias-variance decomposition doesn't hold?
As mentioned earlier, the form of Equation 13 does not hold for all losses, e.g., 0/1 loss. Many authors have proposed alternative 0/1 decompositions, each of which makes compromises and has different properties. The decomposition proposed by (James, 2003) applies for several losses, and links neatly to our work. They limit their commentary to symmetric losses however, their conelusions do apply more generally, as we will see. As in our work, they rely on the notion of c model. For an arbitrary symmetric loss e, they could have defined the centroid in two ways: minimizing over the left or right argument:
fLEPT (a) == arg min ED ((2 f())))
fRIGHT(()) (x)chr(a)):00000 == arg min ED [((f(a))))]
(20)
zEy
=Ey
They chose the right centroid, which unfortunately masks the generality of their conclusions. This can be seen by instead adopting the left centroid, as we did for Bregman divergences. We now describe their framework, but using f = fLEFT- From this point onwards, we assume loss & such that the centroid always exists, but make no assumptions on its uniqueness.
If l was the 0/1 loss, / is the mode of the distribution. For the absolute loss, it is the median value. If l a Bregman divergence, it is the left Bregman centroid, for defined earlier. Using this, we define two terms:
bias-effect =- R(f)- R(y"),
(21)
variance-effect := ED [R()) B(A)
(22)
These quantify the effect on the risk of using one predictor versus another. The bias-effect is the change in risk for the centroid model versus the Bayes model. The variance-effed is the change in risk for a model f versus the centroid model, averaged over the distribution of D. We then have the decomposition:
ED [ = R(y*) + R(Ò
+ -
(23)
expected risk
noise
bins-offect
variance-cffectt
which can be verified by allowing terms on the right to cancel. James (2003) notes that with squared loss, the bias-ellect is equal to the bias, and the variance-ellect is equal to the variance: thus Equation 23 reduces to Geman et al. (1992). They state this relation holds for any symmetric loss, but in fact (as a trivial corollary to Theorem 1) we see holds for any Bregman divergence- which are all asymmetric, except squared loss. Thus, if l is Bregman divergence, Equation 23 reduces to Equation 13. We can relate the terms above to the approximatioon-ssimation decomposition, using the same overall strategy as before.
They refer to this as the 'systematic' part of the predictor, however we retain our terminology semminolgyy/ootation for consistency. 4 For bias, allow R(f*) to cancel on the right of Equuation 15, and for variance, allow R(.erm) cancel in Equation 16.
9

---

Published in Transactions on Machine Learning Research (02/2024)
Proposition 1 (Bias/Variance Effects, in terms of ppproximatiio--ssimatiio For any loss t, assuming a centroid model exists, we have the following decomposilion of the bias-effect and variance-effecl.
R(') - R(y") = R(F) + +R R(F))
(24)
bias-effect
approximation error
estimation bias
En(R(f) R()]
Ep
[(()) A(ferm) ED R(ferm) R(
(25)
varlance-effect
optimisation error
estimation varlance
And the full relation our earlier observations can be illustrated as follows.
approximation error
estimation blas
bias
bias-effect
Equality only when BV decomposition holds
Equality for any loss
variance
variance-effect
optimisation
estimation
error
variance
Figure Relations between several decompositions that we have considered in this work.
As mentioned, for 0/1 loss the centroid is the modal value the predictions. Taking the mode is effectively a weighted majority vote across the distribution of predictions from f. Weighted voting classifiers have been extensively studied in the context of Boosting (Schapire, 2003), where is well-known that a voted combination of weak (half-plane linear) models results non-linear decision boundary. This implies f & F. and thus again it is possible for estimation bias to be negative. Further characterisation of the terms in Figure 7, for the 0/1 loss, or indeed the general case of any loss, would therefore be desirable.
5 Conclusions
We analysed the precise connections between two seminal results that are often conflated: the decomposition, and the ppproxinatiin-estinatte this work was that it had not been explored before-two such foundational ideas, not previously connected. There are of course several excellent sources which do not conflate them, e.g., Györfi et al. (2002), but to the best of our knowledge there no work conparing/contrastimng the decompositions. In a literature review (see Appendix C), we found numerous sources stating the two were equivalent. This is false. The true relation, given by Theorem 1, is more intricate, and yielded interesting novel observations, including links to the phenomenon of double descent in deep learning. We focused Bregman divergences, but also briefly considered the case of more general losses, where a bias-variance decomposition does not hold, e.g. 0/1 loss. In this case the geometry of such losses is not well-understood, leaving several open issues. In all cases, the centroid model turned out to be a key mathematical object in bridging the decompositions. We conjecture that further study this object, and its role in generalisation, may yield yet deeper and interesting insights.
decomposition. Perhaps the most surprising aspect of
Acknowledgements
Funding in direct support of this work: EPSRC EP/N035127/1 (LAMBDA project).
10

---

Published in Transactions on Machine Learning Research (02/2024)
References
Shun-ichi Amari. Information geometry and its applications: Convex function and dually flat manifold. In
LIX Fall Colloquium on Emerging Trends in Visual Computing, pp. 75 102. Springer, 2008.
Francis Bach. Learning theory from first principles. Draft version: Dec 25th, 2023, 2023. URL https:
//www.di wiw.wii.c. ens ftt.-tbach/ttfppbooo. bookk pdf.
Arindam Banerjee, Xin Guo, and Hui Wang. On the optimality of conditional expectation bregman predictor. IEEE Transactions on Information Theory, 51(7):2664-2669, 2005a.
Arindam Banerjee, Srujana Merugu, Inderjit Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with bregman divergences. Journal of machine learning research, 6(10), 2005b.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14:115-133, 1994.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias variance trade-ofT. Proc. National Academy of Sciences, 116(32):15849 15854, 2019.
Léon Bottou. In Hindsight: Doklady Akademii Nauk SSSR, 181(4), 1968, pp. 3 5. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 978-3-642-41136-6
doi: 10.1007/978-44 --1-----2-221111666
URL https:
//doi.orr/// 10.//10.11 11701197-------2-111----
Léon Bottou and Olivier Bousquet. The tradeolls of large scale learning. Advances in neural information processing systems, 20, 2007.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Mathematics, 7(3):200-22 217, 1967.
Chil-Chieh Chen, Masaru Sogabe, Kodai Shiba, Katsuyoshi Sakamoto, and Tomah Sogabe. General vapnik- chervonenkis dimension bounds for quantum circuit learning. Journal of Physics: Complerity, 3(4), 2022.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1 49, 2002.
Yehuda Dar, Vidya Muthukumar, and Richard G Baraniuk. A farewell to the bias-variance tradeoff? an overview of the theory of overparameterized machine learning. ar preprint arXiv:2109.000 09.00355.00.5. 2021.
Hal Daumé. A Course in Machine Learning (2nd printing, Jan 2017). Online, 2017. URL http:///inn info/dl/v0 /0/ 1en1l-v0_9-aal.ppe
Pedro Domingos. unified varianer decomposition. In Proceedings of 17th international conference on machine learning, pp. 231-238. Morgan Kaufmann Stanford, 2000.
Yann Dubois, Tatsunori Hashimoto, and Percy Liang. Evaluating self-supervieed learning via risk decompo- sition. International Conference on Machine Learning, volume 202, 2023.
Jianqing Fan, Cong Ma, and Yiqiao Zhong, A selective overview of deep learning. Statistical science: review journal of the Institute of Mathematical Statistics, 36(2):264, 2021.
Jerome H Frieddan. On bias, variance, 0/1-loss, and the cuuse-of-dimensioonalty. Data mining and knowl- edge discovery, 1:55-77, 1997.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemna. Newral compulation, 4(1):1-56 1992.
Pierre Geurts. Contributions decision free induction: bias/variance tradeoff and time series classification. PhD thesis, University of Liège Belgium, 2002.
László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. distribution theory of nonporametric regression, volume 1. Springer, 2002.
11

---

Published in Transactions on Machine Learning Research (02/2024)
Trevor Hastic and Robert Tibshirani. Generalized Additive Models. Statistical Science, 1(3):297 310, 1986. doi: 10.1214/ss/ 1117///666/ URL https://doi.org:
2214//s/11770136555
Trevor Hastie, Robert Tibshirani, and Jerome H Friedman. The Elements of Stalistical Learning: Data Mining, Inference, and Prediction, volume 12th printing, January 13th 2017. Springer, 2017.
Haury. Feature selection from gene expression data molecular signatures for breast cancer prognosis and gene regulation network inference. Theses, Ecole Nationale Supéricure des Mines de Paris, December 2012. URL https://passter hall sciencc/pastel-00818888
Tom Heskes. Bias/ variancie decompositions for likelihood-based estimators. Neural Compulation, 10(6): 1425 1433, 1998.
Gareth James and Trevor Hastie. Generalizations of the bias/variance decomposition for prediction error. Technical report, Dept. Statistics, Stanford Univ., Stanford, CA, 1997.
Gareth M James. Variance and bias for general loss functions. Machine learning, 51:115-135, 2003.
Tin- Yau Kwok and Dit- Yan Yeung. Use bias term in projection pursuit learning improves approximation and convergence properties. TEFE Transactions on Neural Networks, 7(5):1168-118) 1996.
Jonathan N Lee, George Tucker, Ofir Nachum, Bo Dai, and Emma Brunskill. Oracle inequalities for model selection in offline reinforcement learning, Neural Information Processing Systems, 35:28194 28207, 2022.
Yunwen Lei, Lixin Ding, and Wensheng Zhang, Generalization performance of radial basis function networks. IEEE transactions on neural networks and learning systems, 26(3):551-5644 2014.
Marie H Masson, Stéphane Canu, Yves Grandvalet, and Anders Lynggaard-Jensen. Software sensor design based on empirical data. Ecological Modelling, 120(2-3):131 139, 1999.
Astrid Merckling. Unsupervised Pretraining of State Representations in Rewardless Enwironment. Theses, ISIR, Université Pierre et Maric Curic UMR CNRS 7222, September 2021. URL https://theses hal. science/tel-03562233
Somabha Mukherjee, Rohit Patra, Andrew Johnson, and Hiroshi Morita. Least squares estimation of quasiconvex regression function. Journal of Royal Statisticol Society (B) Statistical Methodology, 2023.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Prectum Nakkiran. More data can hurt for lincar regression: Sample-wisc double descent. arXie preprint a91iv:1912. 07242, 2019.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Seicluna, Simon Lacoste-Julien and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. orXiv preprint arXiv:1810.0855 2018.
Frank Niclsen and Richard Nock. Sided and symmetrized bregman centroids. IEEE transactions on Infor- mation Theory, 5586) 2904, 2009.
Frank Nielsen and Richard Nock. Corrigendum and Addendum to: "Sided and Symmetrized Bregman
centroids" TEFE Transactions Information Theory 55.6 (2009): 2882-2904,, 2020. URL https:// franknielsen
Partha Niyogi. The informational complerity of learning from ezamples. Phl) thesis, Massachusetts Institute Technology, Cambridge, MA, USA, 1995. URL https: //hdl. handle. net//721.1//683
Partha Niyogi and Federico Girosi. On the relationship between generalization error, hypothesis complexity, and sample complexity for radial basis functions. Neural Compulation, 8(4):819 842, 1996.
12

---

Published in Transactions on Machine Learning Research (02/2024)
David Pfam. A Generalized Bias- Variance Decomposition for Bregman Divergences. Technical report, Columbia University, 2013.
Tomaso Poggio, Steve Smale, al. The mathematics of learning: Dealing with data. Notices of the AMS, 50(5):537-544, 2003.
Robert. E Schapire. The boosting approach to machine learning: An overview. Nonlinear estimation and classification, pp. 149 171, 2003.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition. Nauka, Moscow, 1974.
Clrike Von Luxburg and Bernhard Schölkopf. Statistical learning theory: Models, concepts, and results. In Handbook of the History of Logic, volume 10, pp. 651-706. Elsevier, 2011.
Huiyuan Wang and Wei Lin. Nonasymptotie theory for two-layer neural networks: Beyond the bias-variame trade-off. ArXiv preprint, 2023. URL
/2106.///1../////// 04795. pdf.
Shuoyang Wang, Guanqun Cao, Zuofeng Shang, and for the Alzheimer's Disease Neuroimaging Initiative. Estimation of the mean function of functional data via deep neural networks. Stot, 10(1):e393, 2021. doi: https://doi..rg/10...us
Danicla Witten. Twitter thread: The Bias- Variance Trade-Off & 'DOUBLE DESCENT', 2020. URL
https: / /x.
Posted 3.54am, 9th August, 2020.
David H Wolpert. On bias plus variance. Newral Computation, 9(6):1211-1243 1997.
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. In International Conf. on Machine Learning, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Appendix
A Proofs of Theorems
A.1 Proof of Thcorem (Bias-Vate Variance in terms of Approcimatioon-ssiimattoo)
We wish to prove the following statements:
Ex
Bold" fo(z))
(15)-R(y''
+ + R(f))
(26)
bius
approximation
estimation bius
Em
En
Ba Bolla(())
= En [ R(frrm)
+ En (((Serm) - R((a)
(27)
variance
optimisation error
estimation variance
To show Equation 26, note that the R(f*) terms cancel, we just need to prove:
Ex Boly", fo(()) R(fe) -(yy))
(28)
The proof below builds on the Bregman 3-point property (Nielsen & Nock, 2009).
Definition (Bregman three-point identity) The Bregman three-point property states, for any P. q.
Ba(p.r) = (p(p, + (g ( Volg) - Vo(r))
(29)
We then have the following, where we apply the three-point property to y, for with y as the mid-point.
Boly, = (o(y,y") + Boly", fo) + (y--y" voly-) vollo)
(30)
Take the expected value w/r ply xx) and the inner product term vanishes, since y = Eyy Rearranging terms and further taking expectation w/r æ, we recover:
R(fa) R(y")
Ex Bols',,is) [ts]
(31)
which is the desired result, proving Equation 26.
To show Equation 27, we follow a similar pattern. Take the 3-point property for y, f with for as the mid-point.
Bo f) Bo Pa) Bollen - So. volle) vo(f)
(32)
Take the expected value w/r D and the inner product term vanishes, since voll)) ED vo(f).
Rearranging termss and further taking expectation over p(æ), we recover:
Ep [(f) MfAa E. ED B Bol(or
(33)
which is the desired result, completing the theorem.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Special case of Theorem 1 for squared loss. The following presents the special case of squared loss, included for didactic purposes due to its ubiquity and links to the results for linear models. We wish to prove the following statements:
E
(RD[f(z) - -R y = Eapp + Eest(b)
(34)
Ex
ED((f(x)
= Eopt + Eest(e)
(35)
E Ey - Byy [1 = R(y")
(36)
To show Equation 36, we simply note that y² = yu [u]. so the expression is true by definition.
To show Equation 34 we note, as an intermediate step, that:
Eapp + Eest(b) (R(F*) (R(f))((w")) R(v")) + (R(E)))))((())) -
R(ED(A) - R(y").
(37)
We then have the following, again using the definition of y"
R(ED(f) R(y")
Exy (EDlf) u)²1 Emy [(v Bylar [21))]]
Exy (Eolfi) 2yyEDff Eyylal + 23yB [
Ex (Bolfl) -2E |y) E (f())) Eylmly/ + yE [y1
= Ex (Bnlfi) -2E |y] Ep [xx)] + Eylelv]
= E.
- -Enlii-Eelnn1))))
which is the bias, and the desired result.
To show Equation 35, we follow similar pattern. From definitions:
Eopt Eest(o)
ED R(f) R(ferm)
+ ED [R(fer)) R(ED(AI] ( ED [R(f) R(EDIA)]
(38)
We then have the following.
Ep [(()) R(EoIA)]
Ep
Eay
(f y)² - Emz (Eolf) y)
Ep Emy
f2 2yf EED + 2y
Eay
[D] 2y - ED
2y
Eg EDIfa -
E., [ED[( E>(1)
where the final step is the standard definition of variance, giving the desired result.
15

---

Published in Transactions on Machine Learning Research (02/2024)
A.2 Proof of Theorem (Hastic's model bias
estimation bias is special case).
Hastie el al. (2017, Equalion 7.14) observe:
Em
(y" Edl Bx))²]
Ex x0-- 3.)2 + Bz (o B. ED(x Bx))
x
(39)
bias
Hastie's 'model bias'
Hastie's 'estimation bias'
We will show this is special case of our Equation 15, restated here for IR:
Ex
Bolv", fo(w))
R(f)-((()
-(fo-R(F))
(40)
bias
approximation error
estimation bias
We first show Hastie's "model bias" the approximation error of a linear model using squared loss, i.e.
R(y") = Ex
x (..)"
(41)
approximation error (generic form)
Hustic's 'model bius' (squared loss, linear model)
For any Bregman divergence Ba, the approximation error R(f*) R(y") can be written follows.
R(**) R(y") Eay BB (x:).
(42)
i.e the approximation error is equal to the Bregman divergence of y" from f* (x), in expectation over P(wy).
Proof sketch. Use the 3-point theorem in exactly the same mannor as in the proof of Theorem 1, i.c. between y, f with yd as the mid-point:
Boly. fr) = Balu,v")
+)) vol"")
(43)
Then take expectation successively P(ylæ) then P(æ:). The inner product term is zero, since E [v] y² For linear model, (x) x² 8.. Rearrange the remaining terms: using squared loss, we have the result.
The result for estimation bias is proven similarly. For squared loss, Jo Ep [x= Ba], so we will show:
R(jx) -(())
R(J)
En (at 3. ED lx2 BA)
(44)
estimation hins (generic form)
Hastie's estimation (squared loss, model)
Proof sketch. Estimation bias can be written (using the Bregman 3-point theorem) so:
Boly.fo
BolF + Vp(f) -
(45)
We take squared loss and linear model, f(x) BB, then take expectation over P(x, y), and we have,
Emy (1V - ED(x [ = Ezy (1V - x 3-) + Eaay Emyy( B_ Ep(x E B2])
(46)
R(Fa) - R((*) Exy 1x0 (xx B. [x Bx))
(47)
where we note that in Equation 45, the cross term Eay (y x B. (Vs VOSEDE Bal))] 0.
This can be shown as follows. We note that VΦ(2) = 2z, and B, = (2:00 Eayy [zr]].
Emy [y x
x² 8.) (o((=" B.) VO [2 BA1))]
(48)
Eayy
(y x 3.) 2x. T B, وy TT Ba) 2I (ae TTTB, Bu1]
(49)
2E (y (y-z* - Ba) _ Bx 21E (y xt Ba) ED x 3x]
(50)
0
16

---

Published in Transactions on Machine Learning Research (02/2024)
Taking the first term, ignoring the constant we have: x² 3- Emy (y x² Ba) B.)
Ery Iyra"
8 xx="'
(51)
Evyl [g/xc
B.t
E Eu |xxx '1 B.
(52)
Buy Lyxx
Em (xx 11 Emyl [xyy]] Em (2:x2") 1)) 33
(53)
Bay (uae
Eny ( Emn (2000 -Ba (x0001))) B.
(54)
Exy Exylg/x
Baelyve") [lvce")) B.
(55)
O.
(56)
Follow the same steps for the second term, with Ep[0x] place of Sa..
A.3 Proof of Theorem (Sufficient condition for non-negative estimation bias).
To prove Theorem 3, we demonstrate that under a certain condition, fo E F, which implies R()x) 2 R(f*), and therefore R(fa)= R(f*) 2 We use the following definition, due Amari (2008, Equation 32).
Definition 5 (Dual convex set) Let db be striclly convex function. A set F is dually conver with respect to @ iff, for any pair of points f.g E F and for all X E []
(V (())) E
i.e. the set F is dual-convex iff is convex in its dual coordinate representation. An arbitrary set convex iff for any random variable X defined over elements of C, its expectation also in C, Le. E[X] C.
Therefore, for dual convex set F, we have that the point Ep(Vø(f) E F. The primal coordinate representation of this point., (BD(VI)( is also member of F, Le. fo E F,, proving the theorem.
A.4 Proof of Theorem (GLMs have non-negative estimation bias).
We demonstrate that Eaa((h) 0 if f is GLM of particular form. We give two proofs: direct and one that makes use of Theorem 3.
Direct proof. The estimation bias is defined:
Eest(h) = -Rfj)- -R(*).
(57)
This involves the definition of the centroid prediction, which for Bregman divergence is,
fx(x)= = [V)) [Vo]==1<0-- [- (Es [Vo((=)))).
(58)
Given a Bregman divergence with generator o, define F as the class of GLMs with inverse link [Vo] parameterised by 0 E Rd, In this case, each f E F takes the form:
f(x) = [6 (0"T))
(59)
17

---

Published in Transactions on Machine Learning Research (02/2024)
where 0 are the natural parameters. Substituting this into the centroid prediction gives us,
fa(x)) = [Vo] ED Ve (Vol (0" (0"x))))
= [o]] ED [0]* x).
(60)
Since Ep [0] is within the convex hull of the distribution of 0 induced by D, the centroid prediction is the same form of GLM as f(z), for all æ, and therefore the centroid model fo E F. Then, since by definition f* is the risk minimizer in F, we must have that R(fa) R(J"), and therefore Equation 57 is non-negative.
Proof using Theorem 3. To show that the estimation bias is non-negative, it suffices to show that the class of GLMs of a particular form is dually-corvez. We verify that the property of dual-convexity holds. Define F GLMs with inverse link Vø-1
By definition, if F is parameterised by vector as follows: f(x)) V v w))
Let h be the function, expressed in primal coordinates, corresponding to the convex combination of two arbitrary GLMs in their dual coordinates, i.e. h = Vo- (AVo(f) + (1-))V with À E [0, 1], and with f and g two GLMs f = ( x)) and V (5T=) æ). We need to show that E F. But.
h = VØ -1 X)V)())))
Vo (A (1-
=o- + (1- -1--) x)
VΦ + +1 - \)5")a) )z)
which is again GLM in F.
18

---

Published in Transactions on Machine Learning Research (02/2024)
B Experimental details
We summarisc our methodology to generate the illustrative experiments shown in the paper.
Full code is available at attps://giz http///ggttt....tg/ ccwppppofgeviirrrr/oooccccpptttp
We use a syuthetic I-d problem: r [0, 15], and the true label is y = x + s2n) + where is Gaussian noise with zero mean and 3. Training data 100 points, illustrated below.
20
Figure 8: Synthetic problem for experiments.
Since this is regression problem, ely. f(x)) = (y f(x))) and fz(z) == Edlf(=)].
The function class FF is defined as the set of all trained models obtained over 1000 independently sampled datasets, each size n = 100. The best-in-class model the minimum across the T trials:
== arggimin R(fD)
(61)
where the risk R(f)) is approximated by sample of uniformly sampled points at a resolution of 0.001, giving total of 15, 000 test points. To simplify analysis, assume f = ferm.
19

---

Published in Transactions on Machine Learning Research (02/2024)
C Example Literature Conflating the Decompositions
We provide evidence from several sources that the dccompositions are often conflated. This includes recent papers in NeurIPS, ICML, the Journal of Physics, Transactions on Neural Networks, and MIT lecture notes.
C.1 Published work
In popular online lextbook, Daumé (2017, Section 5.9) stales
"The trade-off between estimation error and approzimation error is often called the bias/ hoss/variance trddeooff, where "approzimation ervor" is "bias" and "estimation error" is "variance."
In NeurIPS, Lee et al. (2022) state:
"Model selection is fundamental task in supervised learning and statistical learning theory. Given a sequence of model classes, the gool is to oplimally bolance the approcimation ervor (bias) and estimation error (variance)"
In the Journal of the Royal Statistical Society, Mukherjee et al. (2023) state:
"A bound of this type" [...] "describes the 'bias- variance' or the 'approzimation- coproasiationn-estmaattoro trade-off" off"'offf'' [..] "the "iiss ('approzimation) in (15) is zero and the 'variance' ("estimation') lerm delermines the estimation error"
In the Journal of Physics, Chen et al. (2022) state:
"To achieve low prediction error in supervised learning, the approsinattoo-essimaainn trade- off (also known as the bias-variance trade-off) should be considered"
In the Bulletin of the AMS, Cucker & Smale (2002) (1984 Google Scholar citations, Feb 2024) state
"Then, typically, the approzimation error will decrease when enlarging H, but the sample error will incrense. This latter feature is sometimes called the bias-variance trade-off" [...] "The biiss is the approrimation error and the 'variance' is the sample error."
In Machine Learning Journal, Barron (1994) (1050 Google Scholar citations, Feb 2024) states
one can deal effectivvly with the total risk of the estimation of functions, including both the approcimation error (bias) and the estimation error (variance)"
In IEEE Trans. Neural Networks, Kwok & Yeung (1996) states
"This is however not the case for in the absence of a bias term, " [--] "and thus the approrimation error (i.e., bias) cannot be made as small as desired by trading variance.
In IEEE Trans. Neural Networks, Lei et al. (2014) state
"To see this, we identify two factors determining the model's generulization performance by recalling the following bias-variance decomposition" [..]] "The first term is often called the eslimation ervor, while the second is the approzimation error [24], [28]."
20

---

Published in Transactions on Machine Learning Research (02/2024)
In ISI Stat, Wang et al. (2021) state:
"Hence, we follow the conventional approzimation estimation decomposition (or bias var-inar trade-off) to decompose the empirical norm" "
The next equation they state is the approxination-estmatton decomposition for squared loss. In the Journal of Ecological Modelling, Masson et al. (1999) state:
"The more flerible the model is, the greater ability approach any function, but the more instable the estimation problem from fivile amount of data. This is known as the iia/varriace tradeoff." "
axprozimatton/estmatttn
In PhD thesis, Merckling (2021) states
"The two terms Eapp and Eest constitute the improziination-estinatte tradeoff (a.k.a. bias- variance tradeoff) where high bios is simålar to high opprozimation error known as underfil- ting, and high voriance is similaar to high estimation error known as overfitting." "
Poggio et al. (2003) states:
"The decomposition of equation (12) is indivectly related to the well-known bios and variance decomposition in statistics."
"More generally, however, there is trade-off between minimizing the sample and minimizing the opprocimation error-uile we referred to as the bias-variance problem."
Though technically correct, this is a slightly misleading use of language.
Niyogi & Girosi (1996), also in a 1995 MIT PhD thesis (Niyogi, 1995) state
"As the number of parameters (proportional to n) increases, the bias (which can thought of as analogous the opprorimation error) of the estimator decreases and its variance (which can be thought of as analogous the estimation error) increases for a fired size of the data set. Finding the right bias-variance trade-off is very similar in spirit to finding the trade-off between network complezity and data complexity."
Wang & Lin (2023) states:
"These empirical findings deeply challenge the conventional wisdom that optimal general- izalion should be achieved by trading off bias (or approrimation ervor) and variance (or estimation error)."
In ICML 2023, Dubois et al. (2023)
"In supervised learning, one can get more fine-grained insights using the estima- tion /pproopproiiiioonn (or bias/ vvariance) risk decomposition,
"The estimationnapprrzinnnt /approzimatiinn or the bias/varion variaance decomposition has been very useful for practitioners and theoreticians to focus on specific risk components"
though in the Appendix of the same article they state "the approzimaation-estiiattoo tradeoff (or the related bias-via vias tradeoff)" [sic, including typo]
21

---

Published in Transactions on Machine Learning Research (02/2024)
Fan al. (2021) state:
"We follow the conventional appooiiaaioon-esimaiion decomposition (somelimes, also bias- variance tradeoff)
The next equation they state is the approxinattion-estintttoon decomposition.
In PhD thesis, Haury (2012) states:
Pigure 1.3: Approzimation ervor and eslimalion error. The ervor made when choosing (a modelj can be seen as the sum of bias and variance. The bias refers the approzimation error and the variance the estimation error.
C.2 Online materials conflating the decompositions
At the time of writing this article, all material was available at the URLs below. As these are not archived in perpetuity, we cannot guarantee availability in the future.
New York University:
Slide 30 states Approximation error "bias", and Estimation error "variance", httpp:///aavidrroenbberg. github.ion http:///c...a....cca//////////aa intro-slttrriskdeconp pdf
MIT:
Module 9.520 lecture slides 17-19 the title "Bias-Variance Tradcoff" but proceed to discuss the approxiinatiion-estiinnttoo decomposition.
https://www.it..ddu. htt..e/aa....5///1111/////1.. CCaps//aaassssasaeeeeee SL.pdf
University of Wisconsin:
"This decomposition into stochastic and approzimation errors is similar to the bias-variance tradeoff which arises in classical estimation theory: the approzimation error is like a bias squared term, and the estimation error like voriance term." https://nott ece. wec..wis..o. edt/SLL00/Iecctrre
Reddit Data Science discussion forum:
"A couple people have been confused by the exact terminology. should clarify that bias- variance decomposition is technically different than the spprorimation-estiataie error de- composilion. But they are extremely similar, and in most cases they are mathemati- cally equivalent. In fact, it is useful to think of the approxination-ssiinttie decomp as a sub-case of the bias-variance decomposition, if we make the assumption that our training algorithm expected to output the best model in its hypothesis class. If this assumption can be made, then they become mathematically equivalent most intents and purposes. It's important to note that most modern class machine learning algorithoms and classes satisfy this assumption, they equivalent." https: : httpw//wreee reddit. com/r r aettaacienneess//fffaaaeeeeeee/e
22


Reviews:
[{"review_id": "VLD9HgHKqS", "reviewer": "Reviewer_F9ni", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe topic of the paper is interesting. Both decomposition are widely used across\ndifferent fields, but their connection and difference are not well documented.\n\nThe authors considered a general class of losses instead of focusing on\nspecifics.\n\nWeaknesses:\n\nThe mathematical definitions and notations need improvements. For example, by\n\"the expectation $\\mathbb{E}_{D}$ is over all possible training sets $D$\", do\nyou mean the expectation is taken over the distribution of the training data\n$D$? What is a \"generator function\"? \"D\" is first used to denote a sample but\nused as a random variable in Definition 1.\n\nThe paper is about the estimation/prediction of the response, at least for the\nbias/variance decomposition. The bias/variance decomposition does not apply in\ngeneral to parameter estimation, especially parameters in nonlinear models.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper exams the connect and difference between the two types of\ndecomposition: the Bias/Variance decomposition and the Approximation/Estimation\ndecomposition. The two types of decomposition are defined on different\nquantities related to the loss of estimating/predicting the responses. Some\ntheoretical results are provided to distinguish the two closely related but\ndifferent terms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since the current paper is about the estimation/prediction of the response, it\nis better to update the title to make it more accurate or extend the\ninvestigation to include other types of statistical inferences. Inference on the\nresponse is just one type of statistical inferences.\n\nThe bias/variance decomposition and the Approximation/Estimation are on\ndifferent quantities. It is better to state this more explicitly.\n\nPoisson regression is a model not a divergence. It is better to call it Poisson\nloss, divergence, or something else.\n\nTheorem 1 is indeed trivial and may not be stated as a Theorem.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NTqkkyxwxW", "reviewer": "Reviewer_hLEj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths #\n\nI think that this work would be widely relevant as it connects concepts in two communities. The paper is written clearly and is straightforward to understand. After checking the math, the theoretical results are sound. The authors also provide examples for illustrations.\n\n# Weaknesses #\n\nIt is not currently clear how the results in the paper would be applied in future work. The authors mention the importance of the centroid of the distribution in the conclusion, but do not expand on it. For example, how could the results be helpful for studying generalization theory?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the connection between two related concepts in statistics and machine learning, the bias-variance trade-off and the approximation-estimation decomposition. Both characterize the performance of a model as a function of the model size and thus are sometimes conflated. The authors rigorously characterize the connection between the two for the class of Bregman divergence losses, and make several observations: 1) the bias cannot clearly characterize model capacity, 2) estimation bias can be negative, and 3) the double descent phenomenon seen for deep networks is mostly a result of the estimation variance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Would strengthen the work:\n- It would make the paper more aesthetically pleasing to create the plots using Matplotlib (https://matplotlib.org/stable/)", "broader_impact_concerns": "This work is largely theoretical, so there are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8t9bitaXaq", "reviewer": "Reviewer_hwRR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper does a good job in clarifying misconceptions regarding the two decompositions and provides some useful discussion on their misuse in machine learning.  \n\nWeaknesses:\n\nThe fact that the bias decomposes into approximation error and estimation bias, though less spelled out in the literature, is in fact well known in the statistical machine learning community, and was taught here in our university in introductory statistical learning courses. As the paper mentioned, the widely used textbook ESL discusses this point very clearly under the squared error loss. Some machine learning papers use bias and variance as synonyms for approximation error and estimation error, which differ from their classical meanings in statistics but are usually clear from the context. Similarly, the bias and variance defined in (11) (also, (14) and (15)) cannot be interpreted in the classical sense unless the squared error loss is adopted. Hence, I do not agree with the paper that these connections “have not been previously observed” or “not been explored before.” The proofs of the main results are elementary and straightforward.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper explores the connections and differences between the bias-variance and approximation-estimation decompositions, two fundamental and closely related decompositions in classical statistics and machine learning. In particular, the paper formalizes a generalized bias-variance decomposition under the Bregman divergence loss, and points out that the bias decomposes into approximation error and estimation bias, and hence is not the same as approximation error.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper should not oversell the novelty and priority of the main results. Rather, the discussion should be focused on the new insights and their implications for machine learning theory.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given the assessments of reviewers, I recommend acceptance with minor revisions; details follow.

Please remove claims that this is the first work to analyze the distinction between bias/variance and approximation error/estimation error. There isn't really a reason to make such claims, and it doesn't detract from the work to remove them. Furthermore, there is not compelling evidence presented to support the claim (it would indeed be very difficult to collect such evidence, and I'm not sure I believe the claim myself without making it far more specific).

Along those lines, the paper should be clearer that the main results are focused on Bregman divergences. This should be clear from the abstract. The paper does indeed provide a nice general view of bias/variance/approximation/estimation, but it is not arbitrarily general.

Please edit the abstract (and the rest of the paper) to use more professional language. Things like "spoiler: no they're not" aren't appropriate for formal academic publications.

There are numerous minor mathematical mistakes and imprecise/unclear statements that need to be fixed before this is published. None of these are major errors in the reasoning of the paper, but if the paper claims to be providing a more careful analysis of imprecise claims in the community, it had better be quite precise itself.

- right at the beginning of 2.1: nonstandard notation f: x -> y. One would think f is a function from R^d to R^k given your setting, so should be f:R^d -> R^k
- what is F_all? Not well defined.
- equation 4, 5, 7, etc not well defined; what is arg inf?
    - a general comment here after doing a pass over the whole paper: the paper is generally very imprecise about arg minimizers. Previous work generally avoids these technicalities entirely by just referring to inf R(...), as opposed to attempting to handle the minimizers explicitly, but I suspect that isn't possible everywhere in this paper.
- you could resolve issues re: arginf by assuming there exists a unique minimizer, but you'd need to find and cite conditions for when this is guaranteed from the literature.
- why use y* for a classifier in eq 4? Why not just completely avoid the abuse of notation and use f*_all or something of that sort?
- after eq 5: what is a "sample drawn from a random variable"? I suspect you just mean that S is a realization of n iid draws from P(x,y) but might be wrong. You do not need two separate symbols (S, D) for this.
- there are at least a few things wrong with eq 11; ell is defined as mapping Y x ri(Y) to R+, but the bias term appears to take an element of ri(Y) x Y. Defining y* to be the argmin over a relative interior does not make sense unless the inf is guaranteed to be in the relative interior, and then you can just argmin over the whole set anyway because the boundary ceases to be an issue.
- it is odd that the centroid is used in Eq 11 before it is defined later in Defn1 & 2
- Definition 1 is not well-formed. For example, the argmin is not always guaranteed to exist, and even if it does it may not be unique. There needs to be more conditions on ell, f, and D.
- For Defn 2, please cite a specific result from Nielsen and Nock that guarantees that it is well-formed.
    - there are a few places throughout (e.g., with Amari as well) where long manuscripts / books are cited for a single result. Please provide specific citations of individual results, pages, etc everywhere possible.
- Please confirm that Eq 13 is strictly true, i.e. the LHS and RHS are *always* not equal. Otherwise that inequality is not correct.
- Proposition 1 shouldn't be a proposition; it's just adding and subtracting R(fcirc). No need to have a stated result here.
- I'm not sure why E_est(v) and E_est(b) are defined after Prop 1. They don't appear to be used anywhere. If they only appear in the appendix, define them there near their first usage.
- Similarly, E_app is not defined.
Decision: Accept (poster)