Limits and Challenges in �Deep Learning Optimizers

Sanghyuk Chun

@NAVER AI Lab

Recap: Gradient Descent Algorithm

• Gradient Descent (GD) is a widely-used algorithm to solve “convex optimization”
• GD is known as an algorithm to solve “optimal solution” with O(1/t) convergence rate (t: the number of iterations) if …
• The problem is strictly convex
• The step size (or learning rate) is sufficiently small (usually defined by the Lipschitz condition of the function)

https://towardsdatascience.com/stochastic-gradient-descent-explained-in-real-life-predicting-your-pizzas-cooking-time-b7639d5e6a32

GD algorithm, an example.

• f(x) = 3x⁴ + 2x² + x + 1 (i.e., ∇f(x) = 12x³ + 4x + 1)

​

(optimal solution ≈ -0.21864…)

​

• Let x₀ = 2 then ∇f(2) = 12 * 2³ + 4 * 2 + 1 = 105
• Let the learning rate η = 0.01 then, x₁ = x₀ - η ∇f(x₀) = 2 - 0.01 * 105 = 0.95
• Similarly, x₂ = x₁ - η ∇f(x₁) = 0.95 - 0.01 * 15.0885 = 0.799115
• After a sufficiently large number of iters, x_t will eventually reach at -0.21864

Recap: How to use GD for deep neural networks (DNNs)?

• Goal: Seeking an optimal values for the DNN parameters θ, i.e., DNN weights!
• How? Compute gradients for the current θ_t and update θ by θ_t+1 = θ_t - η ∇f(θ_t)
• … How to compute the gradient for the current θ_t ??
• We don’t know how our f looks like, but we only can compute �the function output values for a given inputs
• Also, the function is defined by “parameters” and “input data”!
• Hence, it becomes:
• θ_t+1 = θ_t - η E_x [ ∇f(θ_t) ]

Recap: Chain rule (“Backpropagation algorithm”) for computing gradients of deep neural networks

Stochastic Gradient Descent (SGD):�Towards a large-scale optimization

• Recap:
• Algorithm: θ_t+1 = θ_t - η E_x [ ∇f(θ_t) ]
• Although we can compute the gradient value of parameters for the given single input data, it does not mean that we can compute the true gradient value for the current parameter θ because…
• The gradient value we have is ∇_θtf(x), not E_x [ ∇f(θ_t) ]
• Stochastic gradient descent (SGD) estimates E_x [ ∇f(θ_t) ] by sampling x from X where x is called as “mini-batch” and | x | is called as “batch-size”.

SGD with an adaptive learning rate

• Recap:
• Algorithm: θ_t+1 = θ_t - η * 1 / |x| * Σ_x ∇f(θ_t)
• How can we set “η”?
• Recap: GD is converged if the step size (or learning rate) is sufficiently small
• Naive approach 1: use a very very very small learning rate (LR)!
• Problem: the convergence will be very very very slow in practice
• Naive approach 2: use a large LR, then “decay” its value!
• Problem: working well in practice, but we have to hand-tune the hyperparameters (decay value, decay scheduling, …)

SGD with an adaptive learning rate

• Slightly better way: use an adaptive learning rate!
• E.g., applying a smaller LR if the norm value || ∇f(θ_t) || becomes very small
• Example: AdaGrad, AdaDelta, ADAM, …
• Problem of adaptive methods: usually working well in many problems, but often performing worse than a well hand-tuned LR scheduling

Deep learning optimization in the wild

• What will happen we combine the core deep modules (e.g., normalization layers) and the chain rule?
• We need a careful learning rate tuning (it should be decayed, but we have to avoid too much fast learning rate decay)
• We need faster optimization technique (remember! Recent large-scale deep learning methods take a lot of resources)
• Sometimes, just finding “a local minimum” is not enough. We are interested in seeking a better local minimum by additional regularizations or different criteria from the “empirical local minimum”

ICLR’21

​

AdamP: Slowing Down the Slowdown for�Momentum Optimizers on Scale-invariant Weights

Byeongho Heo*, Sanghyuk Chun*, Seong Joon Oh, Dongyoon Han,

Sangdoo Yun, Gyuwan Kim, Youngjung Uh, Jung-Woo Ha

Three Secret Recipe of Neural Networks

• Batch normalization (and other normalization techniques)
• Momentum stochastic gradient descent
• Weight decay

Three Secret Recipe of Neural Networks

• Batch normalization (and other normalization techniques)
• Momentum stochastic gradient descent
• Weight decay

Batch Normalization (BN)

• BN is a simple technique to improve the training stability of neural networks

Batch Normalization (BN)

• BN is a simple technique to improve the training stability of neural networks

x1

x2

x3

x4

x5

(x₁ - μ) / σ

μ and σ are sample-mean and sample-variance of the mini-batch samples

* γ + ß (γ and ß are learnable parameters)

Batch Normalization (BN)

• BN is a simple technique to improve the training stability of neural networks

x1

x2

x3

x4

x5

(x₁ - μ) / σ

μ and σ are sample-mean and sample-variance of the mini-batch samples

* γ + ß (γ and ß are learnable parameters)

Widely-used “ResNet” block

BN makes scale-invariant parameters

• Normalization operation makes scale-invariant parameters
• In other words, the output is independent to the scale (or norm value) of the parameter

​

• Formally, where, x is an input and w is the parameter
• Batch normalization (BN) makes scale-invariant parameters as well:

​

BN makes scale-invariant parameters

• Normalization operation makes scale-invariant parameters
• In other words, the output is independent to the scale (or norm value) of the parameter

​

• Formally, where, x is an input and w is the parameter
• Batch normalization (BN) makes scale-invariant parameters as well:

​

​

• ​

BN makes scale-invariant (SI) parameters

• BN makes the parameter right before it scale-invariant

BN makes scale-invariant (SI) parameters

• BN makes the parameter right before it scale-invariant
• 95.5% of ResNet18 and�91.8% of ResNet50 are scale-invariant (SI)

Widely-used “ResNet” block

Gradient descent increases norm of SI parameters w

• Proof:
• Since w is scale-invariant, the gradient of w is perpendicular to w itself (changing the scale of w or || w ||, does not change the final output)
• f(w) = f(c w)
• ∇_w f(w) ⊥ w
• Therefore, the gradient update is always performed on the tangent space of w.�By Pythagorean theorem, || w_t+1 || ² = || w_t ||² + η || ∇_w f(w) ||² (η: step size)^�that implies || w_t+1 || ² ≥ || w_t ||²

Optimizing SI parameters in R^d space is same as optimizing normalized SI parameters in R^d-1 space

• Moreover, the norm of parameter w controls the “effective step size” in �the R^d-1 space (we call this space as “effective parameter space”)

Gradient scale of a normalized, or effective parameter

Proposional to the weight norm || w_t+1 ||

Norm increasement adaptively controls the step size

• Auto-tuning Theorem (Arora et al, 2019)

It implies that GD will converge even with an arbitrary large learning rate for scale-invariant parameters!

Arora, Sanjeev, Zhiyuan Li, and Kaifeng Lyu. "Theoretical analysis of auto rate-tuning by batch normalization." ICLR 2019

Key lemmas for auto-tuning theorem

Three Secret Recipe of Neural Networks

• Batch normalization (and other normalization techniques)
• Momentum stochastic gradient descent
• Weight decay

Momentum SGD

• Momentum SGD is designed to accelerate the convergence of gradient-based optimization by the parameters escape high-curvature regions and cope with small and noisy gradients:

​

• There are many momentum SGD variants�Including AdaGrad, RMSProp, ADAM, …

https://ruder.io/optimizing-gradient-descent/

Momentum SGD makes norm increases much faster

• Recall: GD increases the weight norm of scale invariant parameters (s.i.p.) by Pythagorean theorem:

​

​

• But, if we have momentum, the norm increases are much faster

Momentum makes effective step size rapidly decrease

ß = 0.9

ß = 0.95

ß = 0.99

SGDP & AdamP: a simple projection-based solution

In other words, we remove the radial direction of update step to prevent unintended norm increases by momentum optimizers

w_t

p_t

q_t

Three Secret Recipe of Neural Networks

• Batch normalization (and other normalization techniques)
• Momentum stochastic gradient descent
• Weight decay

Dark magic for NN optimization: weight decay (WD)

• L2 regularization is a standard technique in traditional machine learning tasks

​

• In deep learning optimization, L2 regularization is often called “weight decay”

Dark magic for NN optimization: weight decay (WD)

• L2 regularization is a standard technique in traditional machine learning tasks

​

• In deep learning optimization, L2 regularization is often called “weight decay”

Dark magic for NN optimization: weight decay (WD)

• L2 regularization is a standard technique in traditional machine learning tasks

​

• In deep learning optimization, L2 regularization is often called “weight decay”
• Conjectures
• Weight decay (accidentally) controls norm increases
• Careful tuning of weight decay (λ) is a key of performances
• + we conjecture that this is the reason why Adam performs much worse than SGD in very well-tuned tasks, such as ImageNet

Deep learning optimization needs careful WD tuning

Our projection solution can handle norm increases without careful WD tuning

Our projection solution can handle norm increases without careful WD tuning

Conjecture: Adam momentum more drastically increases norm, AdamP can mitigate this issue

Our projection solution can handle norm increases without careful WD tuning

Real-world experiments: 6 tasks and 14 datasets

Image recognition tasks

ImageNet classification accuracies.

MS-COCO object detection mAP.

Image recognition tasks

ImageNet classification accuracies.

MS-COCO object detection mAP.

Adam now works better than SGD with our solution!

AdamP is not only effective to BN, but also to L2 projection

Image retrieval tasks.

f(x) = f(x) / || f(x) ||

AdamP works well in complex minimax optimization tasks

Standard and attacked accuracies of Wide-ResNet trained on CIFAR-10 with PGD-10 attacks.

AdamP works well in complex minimax optimization tasks

ReBias 9-Class ImageNet experiments.

ReBias Biased-MNIST experiments.

Non-image domain results

Language modeling.

Audio classification tasks.

LM uses layer normalization (LN), not BN

ClovaAI/AdamP: Open source for SGDP / AdamP.

from adamp import AdamP, SGDP

​

# Usage is exactly same as torch.optim library!

optimizer = AdamP(lr=0.001, betas=(0.9, 0.999), weight_decay=1e-2)�optimizer = SGDP(lr=0.1, weight_decay=1e-5, momentum=0.9, nesterov=True)

• Easy to use (just replace your Adam to AdamP)
• We recommend using default parameters except the learning rate.
• https://github.com/clovaai/adamp

pip install adamp

Conclusion of SGDP / AdamP.

• Three Secret Recipe of Neural Networks:
• BN (for stable training) makes scale-invariant parameters, that makes monotonically norm increases during training (=> auto-tuning)
• Momentum (for faster convergence) makes the norm increases of s.i.p. much rapidly than we expected (=> auto-tuning may not work well in this setting)
• Weight decay (for regularization) accidentally controls norm increases, and it makes WD is a very sensitive hyperparameter for the final performances
• AdamP: easy to adapt projection-based solution.
• Superior performances in 5 tasks and 13 datasets.
• Open source: https://github.com/clovaai/adamp

Recap: Deep learning optimization in the wild

• What will happen we combine the core deep modules (e.g., normalization layers) and the chain rule?
• Applying normalization + chain rule makes scale-invariant parameters
• We need a careful learning rate tuning (it should be decayed, but we have to avoid too much fast learning rate decay)
• There exists “auto-tune” effects on the scale-invariant parameters

Recap: Deep learning optimization in the wild

• We need faster optimization technique (remember! Recent large-scale deep learning methods take a lot of resources)
• “Momentum” is the key technique to boost up the convergence, but it can harm the auto-tune effect
• We proposed SGDP and AdamP to solve the problem
• Sometimes, just finding “a local minimum” is not enough. We are interested in seeking a better local minimum by additional regularizations or different criteria from the “empirical local minimum”
• A careful “weight decay” tuning is one of the key regularizations, we show that our solution can mitigate the sensitivity of WD

Recap: Deep learning optimization in the wild

• We need faster optimization technique (remember! Recent large-scale deep learning methods take a lot of resources)
• “Momentum” is the key technique to boost up the convergence, but it can harm the auto-tune effect
• We proposed SGDP and AdamP to solve the problem
• Sometimes, just finding “a local minimum” is not enough. We are interested in seeking a better local minimum by additional regularizations or different criteria from the “empirical local minimum”
• A careful “weight decay” tuning is one of the key regularizations, we show that our solution can mitigate the sensitivity of WD

Flatness and Sharpness are also matter

ICLR’17. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima

Flatness and Sharpness are also matter

UAI’18. Averaging Weights Leads to Wider Optima and Better Generalization

Flatness and Domain Generalization

Q&A

​

Thanks for all co-authors and colleagues.

Many slides are borrowed from Byeongho’s slide.