Statistical Learning Theory 10 Universal Approximation 12 Is ERM enough?

Chapter 11 Optimization

We haven’t yet really talked in this course about any optimization algorithms to actually implement our learning algorithms ERM or SRM.

Recall our usual decomposition (1.5)

\underbrace{L_{\mathcal{D}}(\mathcal{A}(Z))-L^{*}}_{\text{excess error}}\leq% \underbrace{L_{\mathcal{D}}(\mathcal{A}(Z))-\inf_{h^{*}\in\mathcal{H}}L_{% \mathcal{D}}(h^{*})}_{\text{estimation error}}+\underbrace{\inf_{h^{*}\in% \mathcal{H}}L_{\mathcal{D}}(h^{*})-L^{*}}_{\text{approximation error}},

and that we’ve often done as in (1.6) that

L_{\mathcal{D}}(\operatorname{ERM}_{\mathcal{H}}(Z))-L_{\mathcal{D}}(h^{*})\\ =\underbrace{L_{\mathcal{D}}(\operatorname{ERM}_{\mathcal{H}}(Z))-L_{Z}(% \operatorname{ERM}_{\mathcal{H}}(Z))}_{\leq\sup_{h}L_{\mathcal{D}}(h)-L_{Z}(h)% }+\underbrace{L_{Z}(\operatorname{ERM}_{\mathcal{H}}(Z))-L_{Z}(h^{*})}_{\leq 0% }+\underbrace{L_{Z}(h^{*})-L_{\mathcal{D}}(h^{*})}_{\text{small by Hoeffding}}.

What about if we try to get the ERM, but we don’t exactly achieve it, instead getting

\mathcal{A}(Z)

? We can then do

L_{\mathcal{D}}(\mathcal{A}(Z))-L_{\mathcal{D}}(h^{*})=\underbrace{L_{\mathcal% {D}}(\mathcal{A}(Z))-L_{Z}(\mathcal{A}(Z))}_{\leq\sup_{h}L_{\mathcal{D}}(h)-L_% {Z}(h)}\\ +\underbrace{L_{Z}(\mathcal{A}(Z))-L_{Z}(\operatorname{ERM}_{\mathcal{H}}(Z))}% _{\text{optimization error}}+\underbrace{L_{Z}(\operatorname{ERM}_{\mathcal{H}% }(Z))-L_{Z}(h^{*})}_{\leq 0}+\underbrace{L_{Z}(h^{*})-L_{\mathcal{D}}(h^{*})}_% {\text{small by Hoeffding}}.

Today we’ll study this optimization error a bit.

By far the most common optimization algorithm used in machine learning is (stochastic) gradient descent and its variants. We’ll cover the foundational ideas, but there is a lot more in this area, and generally, learning theory and optimization are becoming much more integrated. For much much more about optimization, some good resources are graduate courses by Michael Friedlander (CPSC 536M) and Mark Schmidt (CPSC “5XX”, to eventually be offered as an actual class), the books of [BV04, NW06, BUB15], and the survey of [GG23]. Chapter 14 of [SB14] also gives an approachable account of projected stochastic subgradient descent, which generalizes what we’re talking about here.

11.1 Gradient descent

Gradient descent tries to find

\min_{w}f(w)

for some function

f

, such as

L_{Z}(f_{w})

. Here

w

should be some parameter vector, for example the flattened vector of all parameters in a network; most of what we’ll talk about works for

w

in a Hilbert space.

We start at some initial point $w_{0}$ , often either $0$ or a sample from, say, $\mathcal{N}(0,\sigma^{2}I)$ . We then update according to the rule

w_{t+1}=w_{t}-\eta_{t}\nabla f(w_{t});

the scalar

\eta_{t}>0

is known as either the “learning rate” or the “step size,” although note that it’s not actually the size of the step since

\lVert w_{t+1}-w_{t}\rVert=\eta_{t}\lVert\nabla f(w_{t})\rVert

One way to motivate this is to say that we should only “trust” the gradient direction locally, and then should re-check it regularly. Another way is to notice that this update actually minimizes the local quadratic approximation given by ¹¹1If instead of

\frac{1}{2\eta}\lVert w-w_{t}\rVert^{2}

we use

\frac{1}{2}(w-w_{t})\nabla^{2}f(w_{t})\,(w-w_{t})

, i.e. the second-order Taylor expansion, this is called Newton’s method. Each step of Newton’s method often improves your loss much more than gradient descent, but each step is also much more computationally expensive.

g(w)=f(w_{t})+\langle\nabla f(w_{t}),w-w_{t}\rangle+\frac{1}{2\eta}\lVert w-w_% {t}\rVert^{2}.

This approximation is useful in that if

f

\frac{1}{\eta}

-strongly convex, then

g

will be a global lower bound for

f

(proposition C.3). Even if not, though, it’ll be an okay approximation to a lower bound locally, since it’s the first-order Taylor expansion plus a term that says “don’t go too far.’

We repeat this until we decide to stop, after $T$ steps, and then return a result: this might be $w_{T}$ (the “last iterate”), $\bar{w}=\frac{1}{T}\sum_{t=1}^{T}w_{t}$ (the “average iterate”), $w_{\hat{t}}$ for $\hat{t}\in\operatorname*{arg\,min}_{t\in[T]}f(w_{t})$ (the “best iterate”), the best iterate according to a validation set, or some other scheme.

We’ll usually assume for now that

\eta_{t}

is some constant

\eta

, independent of the data, and that we optimize for a fixed number of steps

T

, also chosen independently of the data. In practice, other schemes are probably better; for instance, it’s often better to use a backtracking scheme to adaptively choose

\eta_{t}

, or to otherwise have some kind of learning rate schedule that decreases over time. In practice, we also probably do set some upper bound

T

on the optimization time, but will frequently stop sooner if it seems like we’re done.

11.2 $\beta$ -smooth functions

A common assumption in optimization is that the target function is $\beta$ -smooth:

Definition 11.1.

²²2Note that this is not what analysts mean when they say a “smooth function” (i.e. infinitely differentiable).

We say a function $f$ is $\beta$ -smooth if it is differentiable everywhere, and its gradient $\nabla f$ is $\beta$ -Lipschitz.

Proposition 11.2.

If $f$ is twice-differentiable, it is $\beta$ -smooth iff for all $w$ in the interior of its domain, all eigenvalues of the Hessian of $f$ at $x$ have absolute value at most $\beta$ : $-\beta I\preceq\nabla^{2}f(w)\preceq\beta I$ .³³3The notation $A\succeq 0$ means “is positive-semi-definite”; $A\succeq B$ means that $A-B$ is positive-semi-definite.

Proof.

When $f$ is twice-differentiable and $\beta$ -smooth, we have by Taylor’s theorem that for any vector $\delta$ ,

\nabla f(w+\delta)=\nabla f(w)+\nabla^{2}f(w)\delta+\lVert\delta\rVert^{2}\xi,

where

\xi

is an error vector depending on

\delta

but with

\lVert\xi\rVert\leq C

for some constant

C

. Now, eigendecompose

\nabla^{2}f(w)

into eigenvalues

\lambda_{i}

and corresponding orthonormal eigenvectors

v_{i}

, so we can write

\nabla^{2}f(w)\delta=\sum_{i}\lambda_{i}\langle v_{i},\delta\rangle v_{i}

. Also let

\delta=tv

for some

\lVert v\rVert=1

. Then we have that

\displaystyle\nabla f(w+tv)-\nabla f(w)

\displaystyle=t\sum_{i}\lambda_{i}\langle v_{i},v\rangle v_{i}+t^{2}\xi.

Now suppose that

\nabla f

\beta

-Lipschitz, meaning that the norm of this expression is at most

\beta t

, or equivalently

\left\lVert\sum_{i}\lambda_{i}\langle v_{i},v\rangle v_{i}+t\xi\right\rVert% \leq\beta.

Choosing

v=v_{i}

, this becomes

\lVert\lambda_{i}v_{i}+t\xi\rVert=\sqrt{\lambda_{i}^{2}+t\langle\xi,v_{i}% \rangle+t^{2}\lVert\xi\rVert^{2}}\leq\beta

; taking

t\to 0

and noting that while

\xi

can depend on

t

, its norm is bounded for all

t

, this implies that we must have

\lvert\lambda_{i}\rvert\leq\beta

For the other direction, suppose that each

\lvert\lambda_{i}\rvert\leq\beta

. Then, via Cauchy-Schwarz,

\left\lVert\sum_{i}\lambda_{i}\langle v_{i},v\rangle v_{i}\right\rVert^{2}\leq% \sum_{i}\lambda_{i}^{2}\langle v_{i},v\rangle^{2}\leq\sum_{i}\lambda_{i}^{2}% \leq\beta^{2};

thus

\lVert\nabla f(w+tv)-\nabla f(w)-t^{2}\xi\rVert\leq t\beta

. Rewriting this we get

\left\lVert\frac{\nabla f(w+tv)-\nabla f(w)}{t}-t\xi\right\rVert\leq\beta;

taking the limit as

t\to 0

, this becomes that the directional derivative of

\nabla f

w

in the direction

v

has norm at most

\beta

. Integrating along the line from

w

to any

w^{\prime}

, as in the proof of lemma 4.4, thus shows that

\lVert\nabla f(w^{\prime})-\nabla f(w)\rVert\leq\beta\lVert w^{\prime}-w\rVert

as desired. ∎

Proposition 11.3.

Suppose

f

\beta

-smooth. Then for any

w

and

w^{\prime}

such that the line segment from

w

w^{\prime}

is in its domain,

\lvert f(w^{\prime})-f(w)-\langle\nabla f(w),w^{\prime}-w\rangle\rvert\leq% \frac{1}{2}\beta\lVert w-w^{\prime}\rVert^{2}:

its deviation from its tangent planes is upper-bounded by a quadratic.

Proof.

By the Lagrange form of Taylor’s theorem, we have that

f(w^{\prime})=f(w)+\langle\nabla f(w),w^{\prime}-w\rangle+\frac{1}{2}\langle w% ^{\prime}-w,\nabla^{2}f(q)\,(w^{\prime}-w)\rangle

for some

q

on a line segment between

w

and

w^{\prime}

. By proposition 11.2, we know that the eigenvalues of

\nabla^{2}f(q)

all have absolute value at most

\beta

, and thus the absolute value of the last term is at most

\frac{1}{2}\beta\lVert w^{\prime}-w\rVert^{2}

. ∎

Lemma 11.4 (Descent lemma).

Let

w^{+}=w-\eta\nabla f(w)

for a

\beta

-smooth

f

; then

f(w)-f(w^{+})\geq\eta\left(1-\frac{1}{2}\eta\beta\right)\lVert\nabla f(w)% \rVert^{2}.

Thus if

0<\eta<2/\beta

and

\nabla f(w)\neq 0

, we have

f(w^{+})<f(w)

Proof.

By proposition 11.3, we have

	$\displaystyle f(w^{+})$	$\displaystyle\leq f(w)+\langle\nabla f(w),w^{+}-w\rangle+\frac{1}{2}\beta% \lVert w^{+}-w\rVert^{2}$
		$\displaystyle=f(w)-\eta\langle\nabla f(w),\nabla f(w)\rangle+\frac{1}{2}\beta% \lVert-\eta\nabla f(w)\rVert^{2}$
		$\displaystyle=f(w)-\eta\left(1-\frac{1}{2}\eta\beta\right)\lVert\nabla f(w)% \rVert^{2}.$

When

0<\eta<2/\beta

\eta(1-\eta\beta/2)>0

. The claim follows. ∎

So, this means that gradient descent with a small-enough learning rate is a “descent method”: each step decreases the objective, unless

\nabla f(w_{t})=0

for some

t

, in which case

w_{t+1}=w_{t}

and we’re stuck forever. If we never hit such a point, then

f(w_{t})

must strictly decrease forever.

Suppose

\inf_{w}f(w)\geq a

for some finite

a

, for example

L_{Z}

with a bounded loss. Then we necessarily have

f(w_{t})\to f_{\infty}\geq a

, called the monotone convergence theorem; then since

f(w_{t})-f(w_{t+1})\to 0

, the descent lemma implies

\lVert\nabla f(w_{t})\rVert\to 0

. So, with an

f

bounded below, the objective values converge and the gradients vanish. If the iterates themselves converge, their limit is therefore a stationary point; the iterates might not converge, but they’ll stilly do so in a way where the gradient vanishes. The latter case happens e.g. for logistic regression with separable data: no finite

w

achives zero logistic loss, but we can get closer and closer to zero loss by letting

\lVert w_{t}\rVert\to\infty

but

w_{t}/\lVert w_{t}\rVert\to w^{*}

where

w^{*}

achieves zero training errors (0-1 loss).

For convex functions, any stationary point – one with $\nabla f(w)=0$ – is a global min. This is why convex optimization is nice! But for nonconvex functions, we can only say that it’s a stationary point: it might be a local but non-global minimizer, or a saddle point, or if we’re really unlucky a local max.

11.3 Aside: convex functions

For convex functions in particular (with a slightly smaller learning rate), we can turn the descent lemma into a proof of gradient descent convergence.

Theorem 11.5.

Let

f

be a convex,

\beta

-smooth function. Begin with

w_{0}

and then let

w_{t+1}=w_{t}-\eta\nabla f(w_{t})

, for some

0<\eta\leq 1/\beta

. Let

w^{*}

be any minimizer of

f

, and let

\bar{w}_{S}=\frac{1}{S}\sum_{t=T-S+1}^{T}w_{t}

be the average of the last

S

iterates; particular examples include

\bar{w}_{1}=w_{T}

and

\bar{w}_{T}=\frac{1}{T}\sum_{t=1}^{T}w_{t}

. For any

1\leq S\leq T

, it holds that

f(\bar{w}_{S})-f(w^{*})\leq\frac{1}{2\eta T}\lVert w_{0}-w^{*}\rVert^{2}.

Proof.

We’re going to want to bound the improvement in each step of gradient descent:

f(w_{t})-f(w_{t+1})

. By convexity (in particular, proposition C.3), we have that

f(w_{t})-f(w^{*})\leq\langle w_{t}-w^{*},\nabla f(w_{t})\rangle.

To see what that right-hand side is, we’ll use

\lVert w_{t}-\eta\nabla f(w_{t})-w^{*}\rVert^{2}=\lVert w_{t}-w^{*}\rVert^{2}-% 2\eta\langle w_{t}-w^{*},\nabla f(w_{t})\rangle+\eta^{2}\lVert\nabla f(w_{t})% \rVert^{2},

and rearrange into

f(w_{t})-f(w^{*})\leq\langle w_{t}-w^{*},\nabla f(w_{t})\rangle=\frac{1}{2\eta% }\left[\lVert w_{t}-w^{*}\rVert^{2}-\lVert w_{t+1}-w^{*}\rVert^{2}\right]+% \frac{\eta}{2}\lVert\nabla f(w_{t})\rVert^{2}.

Now we can use the descent lemma to deal with that last term: since

\eta\leq 1/\beta

1-\frac{1}{2}\eta\beta\geq\frac{1}{2}

, and lemma 11.4 becomes

f(w_{t})-f(w_{t+1})\geq\frac{1}{2}\eta\,\lVert\nabla f(w_{t})\rVert^{2}.

We’ve therefore obtained

f(w_{t})-f(w^{*})\leq\frac{1}{2\eta}\left[\lVert w_{t}-w^{*}\rVert^{2}-\lVert w% _{t+1}-w^{*}\rVert^{2}\right]+f(w_{t})-f(w_{t+1}),

which we can simplify to

f(w_{t+1})-f(w^{*})\leq\frac{1}{2\eta}\left[\lVert w_{t}-w^{*}\rVert^{2}-% \lVert w_{t+1}-w^{*}\rVert^{2}\right]

or equivalently

f(w_{t})-f(w^{*})\leq\frac{1}{2\eta}\left[\lVert w_{t-1}-w^{*}\rVert^{2}-% \lVert w_{t}-w^{*}\rVert^{2}\right].

This holds for each

t

from

1

T

; let’s then take the average of them all, obtaining

	$\displaystyle\frac{1}{T}\sum_{t=1}^{T}f(w_{t})-f(w^{*})$	$\displaystyle\leq\frac{1}{2\eta T}\sum_{t=1}^{T}\left[\lVert w_{t-1}-w^{}% \rVert^{2}-\lVert w_{t}-w^{}\rVert^{2}\right]$
		$\displaystyle=\frac{1}{2\eta T}\left[\lVert w_{0}-w^{}\rVert^{2}-\lVert w_{1}% -w^{}\rVert^{2}+\lVert w_{1}-w^{}\rVert^{2}-\dots-\lVert w_{T}-w^{}\rVert^{% 2}\right]$
		$\displaystyle=\frac{1}{2\eta T}\left[\lVert w_{0}-w^{}\rVert^{2}-\lVert w_{T}% -w^{}\rVert^{2}\right]$
		$\displaystyle\leq\frac{1}{2\eta T}\lVert w_{0}-w^{*}\rVert^{2}.$

Notice that by the descent lemma,

f(w_{t})

is weakly decreasing; thus

\frac{1}{S}\sum_{t=T-S+1}^{T}f(w_{t})\leq\frac{1}{T}\sum_{t=1}^{T}f(w_{t})\leq f% (w^{*})+\frac{1}{2\eta T}\lVert w_{0}-w^{*}\rVert^{2}.

But by Jensen’s inequality (theorem C.8), since

f

is convex,

f(\bar{w}_{S})=f\left(\frac{1}{S}\sum_{t=T-S+1}^{T}w_{t}\right)\leq\frac{1}{S}% \sum_{t=T-S+1}^{T}f(w_{t}).\qed

Much faster rates are available if

f

is smooth and strongly convex.

11.3.1 Aside: SGD non-convex convergence

The analysis above can be pretty-easily extended to SGD; see e.g. Chapter 14 of [SB14] or the recent survey of [GG23]. It can be generalized further, though more complicatedly, to show that even SGD eventually reaches a stationary point, even for non-convex functions:

Proposition 11.6 (Corollary 1 of [KR23]).

Let $f$ be $\beta$ -smooth, with $\inf_{x}f(x)\geq f^{\inf}>-\infty$ . Let $\hat{g}_{t}\mid x_{t}$ be independent such that $\operatorname*{\mathbb{E}}[\hat{g}_{t}\mid x_{t}]=\nabla f(x_{t})$ and

\operatorname*{\mathbb{E}}[\lVert\hat{g}_{t}\rVert^{2}\mid x_{t}]\leq 2A(f(x_{% t})-f^{\inf})+B\lVert\nabla f(x_{t})\rVert^{2}+C

for some

A,B,C\geq 0

. Fix

\varepsilon>0

, and pick

\eta=\min\left\{\frac{1}{\sqrt{\beta AT}},\frac{1}{\beta B},\frac{\varepsilon}% {2\beta C}\right\}

. Initialize stochastic gradient descent at

x_{0}

, with

\delta_{0}=f(x_{0})-f^{\inf}

, and

x_{t+1}=x_{t}-\eta\hat{g}_{t}

. As long as

T\geq\frac{12\delta_{0}\beta}{\varepsilon^{2}}\max\left\{B,\frac{12\delta_{0}A% }{\varepsilon^{2}},\frac{2C}{\varepsilon^{2}}\right\}

, it holds that

\min_{1\leq t\leq T}\operatorname*{\mathbb{E}}[\lVert\nabla f(x_{t})\rVert]\leq\varepsilon

That is, the best iterate achieves

\varepsilon

-stationarity (in expectation) with

\operatorname{\mathcal{O}}(1/\varepsilon^{4})

steps. The assumption on

\hat{g}_{t}

is satisfied for example if the

\hat{g}_{t}

have a bounded variance, or if we choose

\hat{g}_{t}

as the gradient of

L_{Z^{\prime}}

for

Z^{\prime}\subseteq Z

chosen randomly and the loss being Lipschitz, or various other settings.

11.4 Are deep networks $\beta$ -smooth?

Is $f(w)=L_{Z}(h_{w})$ for $h_{w}$ a class of deep networks $\beta$ -smooth?

Consider the very simple network

h_{W,v}(x)=\langle v,\sigma(Wx)\rangle,

where

\sigma

is itself

\beta

-smooth. Then the square loss for a single data point is

f(W,v)=(v^{\mathsf{T}}\sigma(Wx)-y)^{2}=v^{\mathsf{T}}\sigma(Wx)\sigma(Wx)^{% \mathsf{T}}v-2y\sigma(Wx)^{\mathsf{T}}v+y^{2},

and we have

	$\displaystyle\nabla_{v}f(W,v)$	$\displaystyle=2(\sigma(Wx)^{\mathsf{T}}v-y)\sigma(Wx)\text{}$ ⁴⁴4If this is unfamiliar, try looking at individual partial derivatives to see that they line up.
	$\displaystyle\nabla_{v}^{2}f(W,v)$	$\displaystyle=2\sigma(Wx)\sigma(Wx)^{\mathsf{T}}.$

The Jacobian with

W

is more annoying, since we’d have to flatten

W

and reshape and stuff. ⁵⁵5Autodiff is nice…. But the overall Hessian of

f

with respect to its input parameters will have

\nabla_{v}^{2}f

as a block in it, and so its largest eigenvalue will depend on

W

: if

\sigma

is the ReLU or something similar, then large values of

W

will result in much larger Hessians. Thus the loss is only going to be fully

\beta

-smooth if you bound the set of possible

W

s, but for any particular parameters it’s going to be “locally” smooth.

Notice that the descent lemma doesn’t actually need a global upper bound on the smoothness, just along the path from $x_{t}$ to $x_{t+1}$ . So, intuitively, we should roughly expect (stochastic) gradient descent to reach a stationary point of the loss as long as $\nabla^{2}f$ doesn’t blow up, i.e. in typical situations as long as none of the parameters blows up. (All of this also requires that $\sigma$ itself be $\beta$ -smooth; ReLU is not.)

Aside: edge of stability

So, if we’re optimizing a deep network with a fixed learning rate $\eta$ , whether the descent lemma applies or not – whether gradient descent is “stable” or not – depends on whether $\eta<\frac{2}{\beta}$ , or more relevantly $\beta<\frac{2}{\eta}$ , for the “local” value of $\beta$ . ⁶⁶6The “local $\beta$ ” might be $>\max(\nabla^{2}f(x_{t}),\nabla^{2}f(x_{t+1})$ : you might go through a sharper point on the way. Consider $f(x)=\lvert x\rvert$ on the reals: $f^{\prime\prime}(x)=0$ for all $x\neq 0$ , but the descent lemma might not apply when you switch signs, since you go through $0$ which has “infinite second derivative.” We can roughly get this local value of $\beta$ by just checking the largest eigenvalue of $\nabla^{2}f(x_{t})$ , and see whether it stays in a “stable” regime or not.

[CKL+21] demonstrated that in fact, optimization typically exhibits “progressive sharpening” where

\beta

increases up to

2/\eta

, then hovers around there on the “edge of stability” (also see [FOX23]). [DNL23] proposed a mechanism for how this happens, based on Taylor expansions of the training process.

11.5 Is a stationary point enough?

One model we can look at is deep linear nets, $f(x)=w_{d}W_{d-1}\cdots W_{2}W_{1}x$ . These are just linear models, but they’re nonconvex and hierarchical and so exhibit some of the same behaviour as regular deep nets. It’s reasonable to expect that, generally speaking, if something doesn’t work on deep linear nets, it won’t work on deep nonlinear nets either.

To see that they’re nonconvex: consider just a depth two model on scalars,

f(x)=vwx

for

v,w\in\mathbb{R}

. Consider square loss with the training set

Z=((1,1))

. Then

L_{Z}(f)=(vw-1)^{2}

, whose minimizers are

\{(v,w):vw=1\}=\{(v,1/v):v\neq 0\}.

But this is not a convex set: it’s a line in

\mathbb{R}^{2}

with the point

(0,0)

cut out of it. The set of minimizers of convex functions must be convex, so therefore

L_{Z}

is not convex.

It turns out that for deep linear nets:

•

Fortunately, all local minima in deep linear nets are global minima ([KAW16, Lv18]).
•

Unfortunately, stationary points can also be saddle points – including potentially “bad” saddles with $\lambda_{\min}(\nabla^{2}f)=0$ even though they’re not local minima. (For example, $x^{3}$ has a saddle point like this at $x=0$ ; they can be even worse in high dimensions.)
•

Fortunately, in general, gradient descent almost surely converges to local minimizers, not saddles (or local maxes) ([LSJ+16]).
•

Unfortunately, doing so can take exponential time ([DJL+17]).
•

Fortunately, this doesn’t happen for deep linear networks, under some conditions ([ACG+19a]).

Unfortunately, there are bad local minima in nonlinear networks. For a very simple example, consider the network $h:\mathbb{R}\to\mathbb{R}$ given by $h(x)=\operatorname{ReLU}(wx)$ , where $w\in\mathbb{R}$ ; use square loss with a single example, $(1,1)$ . Then the loss is

\ell(h_{w},(1,1))=\begin{cases}(w-1)^{2}&w\geq 0\\ 1&w\leq 0\end{cases}.

Any negative input is a (non-strict) local min (since

f(w)\geq f(v)

for all

v

in a neighbourhood of

w

), but it’s not a global min (since

f(1)=0

). Thus, if you start gradient descent with a negative

w

, it’s just stuck. In fact, bad (strict) local minima can appear for almost any activation function ([DLS20]), and with more units, the loss landscape has such points almost all the time.

But, do bad local minima exist for realistic networks, with realistic data? Even if they do, does SGD find them? Moreover, even if I find a good local min of $L_{Z}$ , does that imply I get a good $L_{\mathcal{D}}$ for realistic networks?

	$\displaystyle\frac{1}{T}\sum_{t=1}^{T}f(w_{t})-f(w^{*})$	$\displaystyle\leq\frac{1}{2\eta T}\sum_{t=1}^{T}\left[\lVert w_{t-1}-w^{}% \rVert^{2}-\lVert w_{t}-w^{}\rVert^{2}\right]$
		$\displaystyle=\frac{1}{2\eta T}\left[\lVert w_{0}-w^{}\rVert^{2}-\lVert w_{1}% -w^{}\rVert^{2}+\lVert w_{1}-w^{}\rVert^{2}-\dots-\lVert w_{T}-w^{}\rVert^{% 2}\right]$
		$\displaystyle=\frac{1}{2\eta T}\left[\lVert w_{0}-w^{}\rVert^{2}-\lVert w_{T}% -w^{}\rVert^{2}\right]$
		$\displaystyle\leq\frac{1}{2\eta T}\lVert w_{0}-w^{*}\rVert^{2}.$

Chapter 11 Optimization

11.1 Gradient descent

11.2 β -smooth functions

Definition 11.1.

Proposition 11.2.

Proof.

Proposition 11.3.

Proof.

Lemma 11.4 (Descent lemma).

Proof.

11.3 Aside: convex functions

Theorem 11.5.

Proof.

11.3.1 Aside: SGD non-convex convergence

Proposition 11.6 (Corollary 1 of [KR23]).

11.4 Are deep networks β -smooth?

Aside: edge of stability

11.5 Is a stationary point enough?

11.2 $\beta$ -smooth functions

11.4 Are deep networks $\beta$ -smooth?