This work examines the deep disconnect between existing theoretical analyses of gradientbased algorithms and the practice of training deep neural networks. Specifically, we provide numerical evidence that in largescale neural network training (e.g., ImageNet + ResNet101, and WT103 + TransformerXL models), the neural network’s weights do not converge to stationary points where the gradient of the loss is zero. Remarkably, however, we observe that even though the weights do not converge to stationary points, the progress in minimizing the loss function halts and training loss stabilizes. Inspired by this observation, we propose a new perspective based on ergodic theory of dynamical systems to explain it. Rather than studying the evolution of weights, we study the evolution of the distribution of weights. We prove convergence of the distribution of weights to an approximate invariant measure, thereby explaining how the training loss can stabilize without weights necessarily converging to stationary points. We further discuss how this perspective can better align optimization theory with empirical observations in machine learning practice.
more »
« less
When Expressivity Meets Trainability: Fewer than n Neurons Can Work
Modern neural networks are often quite wide, causing large memory and computation
costs. It is thus of great interest to train a narrower network. However,
training narrow neural nets remains a challenging task. We ask two theoretical
questions: Can narrow networks have as strong expressivity as wide ones? If so,
does the loss function exhibit a benign optimization landscape? In this work, we
provide partially affirmative answers to both questions for 1hiddenlayer networks
with fewer than n (sample size) neurons when the activation is smooth. First, we
prove that as long as the width m>=2n=d (where d is the input dimension), its
expressivity is strong, i.e., there exists at least one global minimizer with zero
training loss. Second, we identify a nice local region with no localmin or saddle
points. Nevertheless, it is not clear whether gradient descent can stay in this nice region.
Third, we consider a constrained optimization formulation where the feasible
region is the nice local region, and prove that every KKT point is a nearly global
minimizer. It is expected that projected gradient methods converge to KKT points
under mild technical conditions, but we leave the rigorous convergence analysis
to future work. Thorough numerical results show that projected gradient methods
on this constrained formulation significantly outperform SGD for training narrow
neural nets.
more »
« less
 Award ID(s):
 1727757
 NSFPAR ID:
 10341621
 Date Published:
 Journal Name:
 Advances in neural information processing systems
 ISSN:
 10495258
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Significant advances have been made recently on training neural networks, where the main challenge is in solving an optimization problem with abundant critical points. However, existing approaches to address this issue crucially rely on a restrictive assumption: the training data is drawn from a Gaussian distribution. In this paper, we provide a novel unified framework to design loss functions with desirable landscape properties for a wide range of general input distributions. On these loss functions, remarkably, stochastic gradient descent theoretically recovers the true parameters with global initializations and empirically outperforms the existing approaches. Our loss function design bridges the notion of score functions with the topic of neural network optimization. Central to our approach is the task of estimating the score function from samples, which is of basic and independent interest to theoretical statistics. Traditional estimation methods (example: kernel based) fail right at the outset; we bring statistical methods of local likelihood to design a novel estimator of score functions, that provably adapts to the local geometry of the unknown density.more » « less

We study the optimization of wide neural networks (NNs) via gradient flow (GF) in setups that allow feature learning while admitting nonasymptotic global convergence guarantees. First, for wide shallow NNs under the meanfield scaling and with a general class of activation functions, we prove that when the input dimension is no less than the size of the training set, the training loss converges to zero at a linear rate under GF. Building upon this analysis, we study a model of wide multilayer NNs whose secondtolast layer is trained via GF, for which we also prove a linearrate convergence of the training loss to zero, but regardless of the input dimension. We also show empirically that, unlike in the Neural Tangent Kernel (NTK) regime, our multilayer model exhibits feature learning and can achieve better generalization performance than its NTK counterpart.more » « less

Recently, researchers observed that gradient descent for deep neural networks operates in an “edgeofstability” (EoS) regime: the sharpness (maximum eigenvalue of the Hessian) is often larger than stability threshold 2/\eta (where \eta is the step size). Despite this, the loss oscillates and converges in the long run, and the sharpness at the end is just slightly below 2/\eta . While many other wellunderstood nonconvex objectives such as matrix factorization or twolayer networks can also converge despite large sharpness, there is often a larger gap between sharpness of the endpoint and 2/\eta . In this paper, we study EoS phenomenon by constructing a simple function that has the same behavior. We give rigorous analysis for its training dynamics in a large local region and explain why the fnal converging point has sharpness close to 2/\eta . Globally we observe that the training dynamics for our example have an interesting bifurcating behavior, which was also observed in the training of neural nets.more » « less

Adversarial training (AT) is a widely recognized defense mechanism to gain the robustness of deep neural networks against adversarial attacks. It is built on minmax optimization (MMO), where the minimizer (i.e., defender) seeks a robust model to minimize the worstcase training loss in the presence of adversarial examples crafted by the maximizer (i.e., attacker). However, the conventional MMO method makes AT hard to scale. Thus, FASTAT (Wong et al., 2020) and other recent algorithms attempt to simplify MMO by replacing its maximization step with the single gradient signbased attack generation step. Although easy to implement, FASTAT lacks theoretical guarantees, and its empirical performance is unsatisfactory due to the issue of robust catastrophic overfitting when training with strong adversaries. In this paper, we advance FASTAT from the fresh perspective of bilevel optimization (BLO). We first show that the commonly used FASTAT is equivalent to using a stochastic gradient algorithm to solve a linearized BLO problem involving a sign operation. However, the discrete nature of the sign operation makes it difficult to understand the algorithm performance. Inspired by BLO, we design and analyze a new set of robust training algorithms termed Fast Bilevel AT (FASTBAT), which effectively defends signbased projected gradient descent (PGD) attacks without using any gradient sign method or explicit robust regularization. In practice, we show our method yields substantial robustness improvements over baselines across multiple models and datasetsmore » « less