《深度学习最优化》综述论文

Optimization for deep learning: an overview

Ruoyu Sun

∗

April 28, 2020

Abstract

Optimization is a critical component in deep learning. We think optimization for neural net-

works is an interesting topic for theoretical research due to various reasons. First, its tractability

despite non-convexity is an intriguing question, and may greatly expand our understanding of

tractable problems. Second, classical optimization theory is far from enough to explain many

ical results. Third, we review existing research on the global issues of neural network training,

including results on global landscape, mode connectivity, lottery ticket hypothesis and neural

tangent kernel (NTK).

1 Introduction

Optimization has been a critical component of neural network research for a long time. However,

it is not clear at first sight whether neural network problems are good topics for theoretical study,

as they are both too simple and too complicated. On one hand, they are “simple” because typical

neural network problems are just a special instance of a unconstrained continuous optimization

problem (this view is problematic though, as argued later), which is itself a subarea of optimization.

On the other hand, neural network problems are indeed “complicated” because of the composition

topic of theoretical research. First, neural networks may provide us a new class of tractable op-

Department of Industrial and Enterprise Systems Engineering (ISE), and affiliated to Coordinated Science Labo-

ratory and Department of ECE, University of Illinois at Urbana-Champaign, Urbana, IL. Email: ruoyus@illinois.edu.

timization problems beyond convex problems. A somewhat related analogy is the development of

conic optimization: in 1990’s, researchers realized that many seemingly non-convex problems can

actually be reformulated as conic optimization problems (e.g. semi-definite programming) which

are convex problems, thus the boundary of tractability has advanced significantly. Neural network

problems are surely not the worst non-convex optimization problems and their global optima could

explosion/vanishing” due to the concatenation of many layers. Properly chosen initialization and/or

other techniques are needed to train deep neural networks, but not always enough. This poses a

great challenge for theoretical analysis, because what conditions are needed for theoretical analysis

is not very clear. Even proving convergence (to stationary points) of the existing method with the

practically used stepsize seems a difficult task. In addition, some seemingly simple methods like

SGD with cyclical step-size and Adam work very well in practice, and the current theory is far from

explaining their effectiveness. Overall, there is still much space for rigorous convergence analysis

and algorithm design.

Third, although the basic formulation a theoretician has in mind (and the focus of this article)

is an unconstrained problem, neural network is essentially a way to parametrize the optimization

there can be richer optimization theory or algorithmic ingredients that can be developed.

To keep the survey simple, we will focus on the supervised learning problem with feedforward

neural networks. We will not discuss more complicated formulations such as GANs (generative

adversarial networks) and deep reinforcement learning, and do not discuss more complicated ar-

chitecture such as RNN (recurrent neural network), attention and Capsule. In a broader context,

theory for supervised learning contains at least representation, optimization and generalization (see

Section 1.1), and we do not discuss representation and generalization in detail.

This article is written for researchers who are interested in theoretical understanding of opti-

mization for neural networks. Prior knowledge on optimization methods and basic theory will be

very helpful (see, e.g., [23, 189, 30] for preparation). Existing surveys on optimization for deep

accessible for non-theory readers. Simple examples that illustrate the intuition will be provided if

possible, and we will not explain the details of the theorems.

the role of optimization in machine learning, and then discuss how to decompose the theory of

optimization for deep learning.

Representation, optimization and generalization. The goal of supervised learning is to

find a function that approximates the underlying function based on observed samples. The first

step is to find a rich family of functions (such as neural networks) that can represent the desirable

function. The second step is to identify the parameter of the function by minimizing a certain loss

function. The third step is to use the function found in the second step to make predictions on

unseen test data, and the resulting error is called test error. The test error can be decomposed into

representation error, optimization error and generalization error, corresponding to the error caused

by each of the three steps.

is zero).

Decomposition of optimization issues. Optimization issues of deep learning are rather

complicated, and further decomposition is needed. The development of optimization can be divided

into three steps. The first step is to make the algorithm start running and converge to a reasonable

solution such as a stationary point. The second step is to make the algorithm converge as fast as

possible. The third step is to ensure the algorithm converge to a solution with a low objective value

(e.g. global minima). There is an extra step of achieving good test accuracy, but this is beyond the

scope of optimization. In short, we divide the optimization issues into three parts: convergence,

convergence speed and global quality.

Convergence issue: gradient explosion/vanishing

Convergence speed issue

Most works are reviewed in three sections: Section 4, Section 5 and Section 6. Roughly speaking,

each section is mainly motivated by one of the three parts of optimization theory. However, this

partition is not precise as the boundaries between the three parts are blurred. For instance, some

techniques discussed in Section 4 can also improve the convergence rate, and some results in Section

6 address the convergence issue as well as global issues. Another reason of the partition is that

Terminology. The terminology of optimization and deep learning are somewhat different, and in

this article we use them interchangeably. See Table 1 for a comparison of some major terms.

Outline. The structure of the article is as follows. In Section 2, we present the formulation of a

typical neural network optimization problem for supervised learning. In Section 3, we present back

propagation (BP) and discuss the basic convergence results. In Section 4, we discuss neural-net

specific tricks for training a neural network, and some underlying theory. In particular, we discuss

a major challenge called gradient explosion/vanishing, and review main solutions such as careful

initialization and normalization methods. In Section 5, we discuss generic algorithm design which

treats neural networks as generic non-convex optimization problems. In particular, we review SGD

with various learning rate schedules, adaptive gradient methods, large-scale distributed training,

input instance x

word, etc. The output instance y

problem, or an integer-valued vector or scalar such as in a classification problem.

We want the computer to predict y

based on the information of x

, so we want to learn the

function φ to a vector v, we apply φ to each entry of v. Another way to write down the neural

network is to use a recursion formula:

tion: matrix factorization. If there is only one hidden layer of linear neurons and the loss function