The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks

Introduction

Deep learning techniques have been very successful in several domains, like computer vision (Voulodimos et al., 2018), speech recognition (Deng et al., 2013) and natural language processing (Young et al., 2018). In practice, deep neural networks (DNN) learned by optimization algorithms such as gradient descent (GD) and its variants can generalize well to unseen data (Witten & Frank, 2005). However, deep neural networks are non-convex. The non-convex deep neural networks have been found to have large amount of global minima (Choromanska et al., 2015), while only few of them can guarantee satisfactory generalization property (Brutzkus et al., 2018). Explaining why the highly non-convex model trained by a specific algorithm can generalize has become an important open question in deep learning.

Regarding the above question, one plausible explanation is that optimization algorithms implicitly regularize the training process (Neyshabur et al., 2015). That is, the optimization algorithm tends to drive parameters to certain kinds of global minima which generalize well, although no explicit regularization is enforced. Recently, exciting results have been shown for vanilla gradient descent. A remarkable progress is the work (Lyu & Li, 2019), which proves that GD maximizes the margin of homogeneous (non-linear) deep neural networks.

On the other hand, adaptive algorithms such as AdaGrad (Duchi et al., 2011), RMSProp (Hinton et al., 2012), and Adam (Kingma & Ba, 2015) have been in spotlight these years. These algorithms are proposed to improve the convergence rate of GD (or SGD) by using second-order moments of historical gradients as conditioner and have been widely applied in deep learning (Ruder, 2016). Despite the rapid convergence of adaptive methods, numerous works have provided empirical evidence that adaptive methods may suffer from poor generalization performance (Wilson et al., 2017; Luo et al., 2018). Several works try to improve the performance of adaptive optimization algorithms such as AdamW (Loshchilov & Hutter, 2018), AdaBound (Luo et al., 2018), AdaBelief (Zhuang et al., 2020). However, there is little theoretical analysis for generalization of adaptive algorithms. These observations and the research for GD motivate us to study the implicit regularization for adaptive algorithms.

The key factor for the success of adaptive optimization algorithms is to design better conditioners of the gradient. Adagrad adopts the simple average of the squared values of the historical gradients in its conditioner, while RMSProp and Adam improve the simple average to exponential moving average strategy. In this paper, we aim to study the influence of different types of conditioners on convergent direction of parameters trained by adaptive optimization algorithms. Specifically, we work on the homogeneous neural networks (including fully connected or convolutional neural network with ReLU or leaky ReLU activations) with separable data under logistic loss (for binary classification) and cross-entropy (for multi-class classification). For logistic loss, we focus on characterizing the convergent direction of parameters (i.e., $\lim_{t\rightarrow\infty}\frac{w_{t}}{\|w_{t}\|_{2}}$) with respect to the training iteration $t$, which is a key target along this line of researches (Soudry et al., 2018; Gunasekar et al., 2018b; Lyu & Li, 2019).

Our main result is summarized in Theorem 1, which states that RMSProp and Adam (w/m) (a variant of Adam without momentum acceleration)How momentum influence the convergence of an optimization algorithm on non-convex deep neural network is still an open problem. Here, we only study a variant of Adam which sets the momentum parameter as . maximize margin of the neural network (equivalent to the optimum of optimization problem in Eq.(2)) and AdaGrad does not converge to max-margin solution due to the anisotropic $\boldsymbol{h}_{\infty}$.

(Informal) We use $\Phi(\boldsymbol{w},\boldsymbol{x})$ to denote the homogeneous neural network model with parameter $\boldsymbol{w}$ and input $\boldsymbol{x}$. (1) For AdaGrad, any limit point of $w_{t}/\|w_{t}\|_{2}$ is a KKT point of the optimization problem

where $\boldsymbol{h}_{\infty}=\lim_{t\rightarrow\infty}\boldsymbol{h}(t)$ is the limit of the conditioner in AdaGrad. (2) For Adam (w/m) and RMSProp, any limit point of $\boldsymbol{w}(t)/\|\boldsymbol{w}(t)\|_{2}$ is a KKT point of the optimization problem

Theorem 1 indicates the importance of proper design on the conditioner, i.e., adaptive algorithms like Adam (w/m) and RMSProp that adopt exponential weighted average design on conditioner regularize the training to max-margin solution, which has low complexity. Therefore, we can expect good generalization performance for Adam (w/m) and RMSProp. Furthermore, we illustrate that the convergence direction of AdaGrad is sensitive to initialization, which hurts its generalization.

We establish Theorem 1 for both continuous flows of adaptive optimization algorithms and their discrete update rules. The technical contributions to prove Theorem 1 are summarized as follows. (1) We propose adaptive gradient flow, which is a unified framework to deal with adaptive gradients. With the adaptive gradient flow, the analysis of convergent direction is transformed from original parameter space to a normalized parameter space. (2) In the normalized parameter space, we construct surrogate margin for the adaptive algorithms, and with the surrogate margin, we show that the increasing rate of the parameter norm can be bounded by the decreasing rate of logarithmic loss and the loss converges to zero. (3) We prove that any limit direction of the normalized parameter flow is a KKT point of the margin maximization problem in normalized parameter space. Moreover, we prove the convergent direction is unique if the neural network is definable (Kurdyka, 1998). The adaptive gradient flow and surrogate margin are designed for adaptive optimization algorithms, which makes the proof techniques different from that for vanilla GD in (Soudry et al., 2018; Lyu & Li, 2019). (4) We further prove the convergent direction for discrete update rules by characterizing the influence of the learning rate.

Finally, we conduct experiments to observe the margin of homogeneous neural network during training of several adaptive optimization algorithms. For all experiments, the margins are increasing during training and the final margins of RMSProp and Adam (w/m) are larger than that of AdaGrad. We also observe the convergent direction of adaptive optimization algorithms under different realizations of initialization and results show that the convergent direction of AdaGrad is sensitive to initialization. These observations can well support our theoretical findings.

Related Work

Implicit Regularization of First-order Optimization Methods. Soudry et al. (2018) proved that gradient descent on linear logistic regression with separable data converges in the direction of the max $L^{2}$ margin solution of the corresponding hard-margin Support Vector Machine, and motivate a line of works on the implicit regularization of GD on linear model (Nacson et al., 2019b; Ji & Telgarsky, 2019; Li et al., 2019; Xu et al., 2018).

Afterwards, researchers study the implicit regularization of GD on deep neural networks. Ji & Telgarsky (2018); Gunasekar et al. (2018b) studied the deep linear network and Soudry et al. (2018) studied the two-layer neural network with ReLU activation. Nacson et al. (2019a) proved the asymptotic direction is along a KKT point of the $L^{2}$ max-margin problem for homogeneous deep neural networks. Lyu & Li (2019) independently proved similar result for homogeneous neural networks with simplified assumptions. Based on (Lyu & Li, 2019), Ji & Telgarsky (2020) further prove that parameters have only one asymptotic direction.

There are also works considering implicit regularization of other first-order optimization algorithms. Nacson et al. (2019c) worked on Stochastic Gradient Descent for linear logistic regression. Gunasekar et al. (2018a) studied mirror descent and steepest descent on linear model. Arora et al. (2019) proved gradient descent on Neural Tangent Kernel will converge to a global minimum near the initial point.

However, there is little result on the implicit regularization of adaptive optimization methods.

Theoretical Evidence of Generalization of Adaptive Algorithms. Adaptive algorithms have been in spotlight these years and many works empirically observe the generalization behavior of adaptive algorithms (Keskar & Socher, 2017; Reddi et al., 2018; Chen et al., 2018; Luo et al., 2018). In comparison, there are few theoretical justifications. Wilson et al. (2017) constructed a specific linear regression task where adaptive optimization algorithms converge to a solution that incorrectly classifies new data with probability arbitrarily close to half. Zhou et al. (2020) modeled the distribution of stochastic noise in Adam, and showed that SGD tends to converge to flatter local minima. Another viewpoint is to study the convergent direction of adaptive optimization algorithms. To the best of our knowledge, the only work is (Qian & Qian, 2019), which proves the convergent direction of AdaGrad on linear logistic regression. In this paper, we study the convergent direction of adaptive optimization algorithms on deep neural networks which requires different techniques due to the non-convexity of deep networks.

Meanwhile, the correlation between margin and generalization error has also been extended to deep networks. Bartlett et al. (2017) first bound the generalization error of deep neural networks using (spectrally) normalized margin by covering number. In parallel, Neyshabur et al. (2018) adopt normalized margin into the PAC-Bayesian framework and derive generalization bound with different dependency on layer width from (Bartlett et al., 2017). Empirically, Jiang et al. (2019) present a large scale study of different generalization bounds in deep networks, and find there is a significant correlation between generalization error and normalized margin when optimizer is changed. These work support our study on generalization in deep learning through the margin theory.

Preliminaries

In an optimization process, the training set $\boldsymbol{S}$ is fixed. Therefore, without loss of generality, we abbreviate $\mathcal{L}(\boldsymbol{w},\boldsymbol{S})=\mathcal{L}(\boldsymbol{w})$, and $y_{i}\Phi(\boldsymbol{w},\boldsymbol{x}_{i})=q_{i}(\boldsymbol{w})$. In this paper, we consider the exponential loss, i.e., $f(q_{i}(\boldsymbol{w}))=q_{i}(\boldsymbol{w})$, and the logistic loss, i.e., $f(q_{i}(\boldsymbol{w}))=-\log\log(1+e^{-q_{i}(\boldsymbol{w})})$. Both of $f$ are monotonously increasing and have an inverse.

Adaptive optimization algorithms including AdaGrad, RMSProp, Adam are widely used to optimize the loss function in deep learning. The update rules for these adaptive optimization algorithms can be written as In this paper, we only consider no-momentum versions of the algorithms, i.e., the algorithms without momentum acceleration.

where $k=1,2,\cdots$ denotes the iteration index, $\partial^{s}\mathcal{L}(\boldsymbol{w}(k))\in\partial\mathcal{L}(\boldsymbol{w}(k))$, $\eta$ denotes a constant learning rate, $\boldsymbol{h}(k)$ is called the conditioner which adaptively assigns different learning rates for different coordinates. For AdaGrad, $\boldsymbol{h}(k)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\sum_{\tau=0}^{k}\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))^{2}}$ where $\epsilon$ is a positive constant, and $\mathbf{1}_{p}$ is a length-$p$ vector with all components to be $1$. Here, $\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))^{2}=\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))\odot\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))$ and $\odot$ denotes the element-wise product of a vector. Different from AdaGrad, RMSProp adopts exponential weighted average strategy in $\boldsymbol{h}(k)$, i.e., $\boldsymbol{h}(k)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\sum_{\tau=0}^{k}(1-b)b^{k-\tau}\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))^{2}}$. Adam further introduces a bias-correction coefficient $\frac{1}{1-b^{k}}$ and $\boldsymbol{h}(k)^{-1}=\sqrt{\varepsilon\mathbf{1}_{p}+\frac{\sum_{\tau=0}^{k}(1-b)b^{k-\tau}\partial^{s}\mathcal{L}(\boldsymbol{w}(\tau))^{2}}{1-b^{k}}}$. In this paper, we use $\boldsymbol{h}^{A}(k)$, $\boldsymbol{h}^{R}(k)$ and $\boldsymbol{h}^{M}(k)$ to distinguish the term $\boldsymbol{h}(k)$ in AdaGrad, RMSProp and Adam respectively.

Taking $\eta\rightarrow 0$, the continuous time limits (i.e., continuous flow) of the three optimization algorithms are

Our study will start with the continuous version of the two algorithms. Specifically, for the continuous case, we focus on the following scenario.

The empirical loss is defined as $\mathcal{L}(\boldsymbol{w})=\sum_{i=1}^{N}e^{-f(q_{i}(\boldsymbol{w}))}$. The following propositions hold:

(Regularity). For any $i$, $\Phi(\boldsymbol{w},\boldsymbol{x}_{i})$ is locally Lipschitz and admits a chain rule with respect to $\boldsymbol{w}$;

(Homogeneity). There exists $L>0$ such that $\forall\alpha>0$ and $i$, $\Phi(\alpha\boldsymbol{w},\boldsymbol{x}_{i})=\alpha^{L}\Phi(\boldsymbol{w},\boldsymbol{x}_{i})$;

(Separability). There exists a time $t_{0}$ such that $f^{-1}(\log\frac{1}{\mathcal{L}(t_{0})})>0$.

I, II in Assumption 1 holds for a board class of networks allowing for ReLU, max pooling, and convolutional layers; Assumption 1.III holds generally for over-parameterized neural networks, which can achieve complete correct classification in training set.

2 KKT point

We give a brief introduction to KKT conditions and KKT points. For a constrained optimization problem defined as

KKT conditions are necessary conditions for a point $\boldsymbol{w}_{0}$ to be optimal in above problem, which require that there exists non-negative reals $\lambda_{i}$, such that

A weaker notion of KKT condition is $(\varepsilon,\delta)$ KKT condition, which requires left sides of eq. (5) to be respectively smaller than $\varepsilon$ and $\delta$. We will formally define $(\varepsilon,\delta)$ KKT points and give some of their properties in Appendix A.2.

Notations. In this paper, we use $\boldsymbol{o}$, $\mathcal{O}$, $\Theta$, and $\Omega$ to hide the absolute multiplicative factors. Concretely, $f(t)=\boldsymbol{o}(g(t))$ if $\overline{\lim}_{t\rightarrow\infty}\frac{f(t)}{g(t)}=0$; $f(t)=\mathcal{O}(g(t))$ if $\overline{\lim}_{t\rightarrow\infty}\frac{f(t)}{g(t)}<\infty$; $f(t)=\Omega(g(t))$ if $\underline{\lim}_{t\rightarrow\infty}\frac{f(t)}{g(t)}>0$; $f(t)=\Theta(g(t))$ if $f(t)=\Omega(g(t))$ and $f(t)=\mathcal{O}(g(t))$.

Main Results

In this section, we introduce the main results on convergent direction of adaptive optimization algorithms. In Section 4.1, we propose a unified adaptive gradient flow and prove that it converges to KKT point of max-margin problem. In Section 4.2, we apply results for adaptive gradient flow to AdaGrad, RMSProp and Adam (w/m) to get the convergent directions of their continuous flow. In Section 4.3, we prove the convergent directions of the discrete update rules of adaptive optimization algorithms.

Adaptive optimizers such as AdaGrad, RMSProp and Adam can be viewed as adding component-wise conditioner to gradient updates and the limit of the component-wise conditioner may be anisotropic for different components. We first define adaptive gradient flow whose limit of component-wise conditioner is isotropic.

A function $\boldsymbol{v}(t)$ is called to obey an adaptive gradient flow $\mathcal{F}$ with loss $\mathcal{L}$ and component learning rate $\boldsymbol{\beta}(t)$, if it can be written as the following form

Let $\boldsymbol{v}$ obey an adaptive gradient flow $\mathcal{F}$ which satisfies Assumption 1. Let $\bar{\boldsymbol{v}}$ be any limit point of $\{\hat{\boldsymbol{v}}(t)\}_{t=0}^{\infty}$ (where $\hat{\boldsymbol{v}}(t)=\frac{\boldsymbol{v}(t)}{\|\boldsymbol{v}(t)\|}$ ). Then $\bar{\boldsymbol{v}}$ is along the direction of a KKT point of the following $L^{2}$ max-margin problem $(P)$:

Theorem 2 shows that the adaptive gradient flow actually drives the parameters to solutions of $L^{2}$ max-margin problem. We will give the proof skeleton of Theorem 2 in Section 5.

Our result can be extended to the multi-class classification with logistic loss and same assumption as Assumption 1 except that $\Phi(\boldsymbol{w},\boldsymbol{x}_{i})$ is a $C$-dimension vector in multi-class case with $C$ number of classes. The corresponding $L^{2}$ max-margin classification problem is then

While Theorem 2 does NOT guarantee direction of parameters converges as $t\rightarrow\infty$, we present a theorem in the end of this section which provides such a guarantee when neural network $\Phi$ is definable with respect to parameters $\boldsymbol{w}$.

Let all assumptions in Theorem 2 hold. Assume further $\Phi(\boldsymbol{w},\boldsymbol{x}_{i})$ is definable with respect to parameter $\boldsymbol{w}$ for any $i\in[N]$. Then direction of parameters $\{\hat{\boldsymbol{v}}(t)\}_{t=0}^{\infty}$ converges.

We defer the formal definition of definable to Appendix C, but point out here that definability allows for linear, ReLU, polynomial activations, max pooling and convolutional layers, and skip connections. Furthermore, for locally Lipschitz definable function, chain rule holds almost everywhere (Lemma 11).

2 Results for Adaptive Algorithms: Continuous Case

In this section, we will prove gradient flow of AdaGrad, RMSProp, and Adam (w/m) can be transferred into adaptive gradient flow. We start from proving convergence of conditioner in AdaGrad and further shows AdaGrad can be reparameterized as an adaptive gradient flow.

For AdaGrad flow defined as eq. (4) with $\boldsymbol{h}(t)=\boldsymbol{h}^{A}(t)$, we have that

$\boldsymbol{h}^{A}(t)$ converges as $t\rightarrow\infty$. Furthermore, $\boldsymbol{h}_{\infty}=\lim_{t\rightarrow\infty}\boldsymbol{h}^{A}(t)$ has no zero component.

Similar properties also hold for RMSProp and Adam (w/m) as the following Theorem .

For RMSProp and Adam flow defined as eq. (4) respectively with $\boldsymbol{h}(t)=\boldsymbol{h}^{R}(t)$ and $\boldsymbol{h}(t)=\boldsymbol{h}^{M}(t)$, we have that, for $I\in\{R,M\}$,

$\boldsymbol{h}^{I}(t)$ converges as $t\rightarrow\infty$. Furthermore, $\lim_{t\rightarrow\infty}\boldsymbol{h}^{I}(t)=\varepsilon^{-\frac{1}{2}}\mathbf{1}_{p}^{T}$.

Both conditioners $\boldsymbol{h}^{R}$ and $\boldsymbol{h}^{M}$ have an exponential decay term $e^{-(t-\tau)(1-b)}$, which drives $\int_{\tau=0}^{t}(1-b)e^{-(1-b)(t-\tau)}\bar{\partial}\mathcal{L}(\boldsymbol{w}(\tau))^{2}d\tau$ to zero, and conditioners to isotropy. The detailed proof requires a more careful analysis in measure than the AdaGrad flow. We defer them to Section B.1.

Combining Theorem 2 with Theorems 4 and 5, one can obtain convergent directions of AdaGrad flow and RMSProp flow by simple parameter substitution of $(P)$.

Let $\boldsymbol{w}$ satisfy AdaGrad flow defined as eq. (4) with $\boldsymbol{h}(t)=\boldsymbol{h}^{A}(t)$. Then, any limit point of $\{\hat{\boldsymbol{w}}(t)\}_{t=0}^{\infty}$ (where $\hat{\boldsymbol{w}}(t)=\frac{\boldsymbol{w}(t)}{\|\boldsymbol{w}(t)\|}$ is normalized parameter) is along the direction of a KKT point of the following optimization problem $(P^{A})$:

Let $\boldsymbol{w}$ satisfy RMSProp or Adam flow defined as eq. (4) respectively with $\boldsymbol{h}(t)=\boldsymbol{h}^{R}(t),\boldsymbol{h}^{M}(t)$. Then, any limit point of $\{\hat{\boldsymbol{w}}(t)\}_{t=0}^{\infty}$ (where $\hat{\boldsymbol{w}}(t)=\frac{\boldsymbol{w}(t)}{\|\boldsymbol{w}(t)\|}$ is normalized parameter) is along the direction of a KKT point of the following optimization problem $(P^{R})$:

Intuitively, $(P^{R})$ is the $L^{2}$ max-margin problem, which means RMSProp flow biases parameters to a local minimum with good generalization property; on the other hand, the target of $(P^{A})$ has a reliance of $\boldsymbol{h}_{\infty}$, which is a constant vector in $(P^{A})$ but can be influenced by the optimization process and initialization, and may further lead to worse generalization. We will discuss the difference between convergent directions of AdaGrad and RMSProp in detail in Section 4.4.

3 Results for Adaptive Algorithms: Discrete Case

In practice, gradient descent methods are employed since calculating exact gradient flow requires huge efforts. In this section, we show same results hold in Theorems 6 and 7 for discrete update rules of adaptive algorithms with slightly different assumptions.

As for the discrete case, two additional assumptions are needed as follows (For brevity, we put the complete assumption to the appendix):

(smooth). For any fixed $x$, $\Phi(\cdot;x)$ is $M$ smooth (i.e., $\Phi$ is twice continuously differentiable with respect to $x$ and all the eigenvalues of the Hessian are within $[-M,M]$);

We make the following explanations for Assumption 2. Assumption 2(I) is needed technically because we need to consider second order Taylor expansion around each point along the training $\{\boldsymbol{w}(k);k=1,\cdots,\}$. Results based on this assumption are the state-of-art in the existing literature of the implicit bias of GD (e.g. ). We put loosening this assumption to future works. Assumption 2(II) guarantees that the second order Taylor expansion is upper bounded and the step size is not too small. With Assumption 2, we have the following theorem:

With Assumptions 1 and Assumption 2, Theorems 6 and Theorems 7 hold respectively for discrete update of AdaGrad and discrete updates of RMSProp and Adam.

We put the proof for Theorem 8 to Appendix D.

4 Discussions

We make some discussions on the results derived in Section 4.2 and 4.3. First, as shown in (Li et al., 2019), the optimization problem $P^{R}$ is equivalent to $L_{2}$ margin maximization problem. Theorems 7 and 6 show that RMSProp and Adam (w/m) converge to max-margin solution, while AdaGrad may drive the parameters to a different direction. The corresponding optimization problem of AdaGrad has a reliance on $\boldsymbol{h}_{\infty}$, which is shown to be sensitive to the optimization path before convergence (shown in Section 6.2), and makes the convergent direction sensitive (we will discuss this in detail in Appendix A.5). Because the normalized margin is used as a complexity norm in generalization literature (i.e., larger normalized margin indicating better generalization performance) (Bartlett & Shawe-Taylor, 1999), our results indicate the superiority on generalization of exponential moving average strategy in the design of the conditioner.

Second, two key factors that guarantee generalization of RMSProp and Adam are exponential weighted average design on the conditioner and the added constant $\epsilon$ in $\boldsymbol{h}(t)$. Our results show the benefit of the two factors: it accelerates the training process at early stage of optimization by adaptively adjusting the learning rate, but it still converges to max-margin solution because the denominator of conditioner tends to constant $\epsilon$ at later stage. Most of previous works explain $\epsilon$ to ensure positivity of $\boldsymbol{h}(t)$. Our results show that $\epsilon$ is important for the convergent direction of the parameters and the generalization ability.

Proof Sketch of Theorem 2

Our surrogate margin can be obtained by replacing $\|\boldsymbol{v}(t)\|$ by $\rho(t)=\|\boldsymbol{\beta}(t)^{-\frac{1}{2}}\odot\boldsymbol{v}(t)\|$ in the smoothed margin in . This allows us to lower bound the derivative of surrogate margin and further lower bound the surrogate margin as Lemma 2, while the derivative of smoothed margin for adaptive gradient flow can not be bounded easily.

2 Convergence of Empirical Loss and Parameters

3 Convergence to KKT point

We start by proving for any $t\geq t_{1}$, $\hat{\boldsymbol{v}}(t)=\frac{\boldsymbol{v}(t)}{\|\boldsymbol{v}(t)\|}$ is an approximate KKT point. Based on the surrogate margin that we construct in Section 5.1, we can further show for normalized $\boldsymbol{v}$ is an approximate KKT point as the following Lemma :

For any $t_{3}>t_{2}\geq t_{1}$, there exists a $\xi\in[t_{2},t_{3}]$, such that

Combining Lemma 5 and 6, for any convergent direction $\bar{\boldsymbol{v}}$, we can construct a series of $\{t_{i}\}_{i=1}^{\infty}$, such that $\hat{\boldsymbol{v}}(t_{i})$ is $(\varepsilon_{i},\delta_{i})$ KKT point, with $\lim_{i\rightarrow\infty}\hat{\boldsymbol{v}}(t_{i})=\bar{\boldsymbol{v}}$, and $\lim_{i\rightarrow\infty}\varepsilon_{i}=\lim_{i\rightarrow\infty}\delta_{i}=0$. On the other hand, constraints of $(P)$ satisfies Mangasarian-Fromovitz constraint qualification (see Appendix A.2), which ensures that $\bar{\boldsymbol{v}}$ is a KKT point of $(P)$, and completes the proof.

Experiments

In this section, we conduct experiments to verify the theoretical results. We train a homogeneous neural networks using AdaGrad, RMSProp and Adam (w/m) respectively. We adopt the homogeneous 4-layer convolutional neural network used in (Madry et al., 2018) as our model and use MNIST (LeCun, 1998) as the dataset. We use default learning rate on PyTorch platform for all the algorithms and Adam (w/m) adopts the same learning rate as Adam. Because our theory is established for full batch gradient without randomness, we set minibatch size to be $1024$ which is relatively large to mimic the full batch gradient. We put more details on the network structure and the settings of hyper-parameters in Appendix F.1, where we also add standard SGD (with momentum) and Adam to observe influence of momentum.

We plot training accuracy, testing accuracy and training loss in Figure 1(a), 1(b), and 1(c). We also plot the value of the normalized margin during training in Figure 1(d). We have the following observations: (1) The normalized margins of AdaGrad, RMSProp and Adam (w/m) are lower bounded and the final normalized margin of AdaGrad is the lowest. It is consistent with our theoretical results. (2) The training loss of AdaGrad, RMSProp and Adam (w/m) goes to zero and AdaGrad achieves the lower test accuracy (the worse generalization), which shows the superiority of conditioners in RMSProp and Adam (w/m) on generalization. (3) Although our theory does not include momentum version of the algorithms, the normalized margin of SGD and Adam are also lower bounded , which shows potential on extension of our theory to momentum version.

2 Observations on Convergent Direction

We repeat AdaGrad, RMSProp and Adam (w/m) for 100 rounds with different random seeds of initialization. We plot $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ for AdaGrad, RMSProp and Adam in Figure 2 (a), (b) and (c), respectively. We can observe that the $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ in AdaGrad are different for 100 runs and $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ in RMSProp and Adam (w/m) are coincide. It indicates that $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ in AdaGrad is sensitive to initialization. We also plot the value of the margin for the three algorithms under different initialization in Figure 2(d). We can observe that the margin of AdaGrad fluctuates under different initialization, while that for RMSProp and Adam (w/m) are smoother. We further show the relation between $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ and the convergent direction of parameters in Appendix F.3. These results indicate that the convergent direction of AdaGrad is sensitive to initialization, which may hurt its generalization.

Conclusion

In this paper, we study the convergent direction of both continuous and discrete cases of adaptive optimization algorithms on homogeneous deep neural networks. We prove that RMSProp and Adam (w/m) will converge to the KKT points of the $L^{2}$ max-margin problem, while AdaGrad does not. The main technical contribution of this paper is to propose a general framework for analyses of adaptive optimization algorithms’ convergent direction. In future, we will study how optimization techniques such as momentum, weight decay and stochastic noise in optimization algorithm influence the convergent direction.

References

Appendix A Preliminaries

In this section, we provide some definitions and basic lemmas which will be used in the proof. The section is organized as follows: in Subsection A.1, we show general properties which exponential loss and logistic loss share; in Subsection A.2, (approximate) KKT conditions is defined and sufficient conditions of being an approximate KKT point is given; in Subsection A.3, we show how conditioners of AdaGrad, RMSProp, and Adam in continuous flow is formulated; in Subsection A.4, we introduce o-Minimal structure, definable set and definable functions, and show two Kurdyka-Lojasiewicz inequalities; in Subsection A.6, we show some basic definitions from Measure Theory, including measurable set and Lebesgue Integrability.

In this subsection, we provide several properties which both exponential and logistic loss possess. The properties of exponential and logistic loss can be described as the following proposition:

$f^{\prime}(x)x$ is non-decreasing for $x\in(0,\infty)$, and $\lim_{x\rightarrow\infty}f^{\prime}(x)x=\infty$;

There exists a large enough $x_{f}$ and a constant $K\geq 1$ ,such that,

$\forall\theta\in[\frac{1}{2},1),$ $\forall x\in(x_{f},\infty)$, and $\forall y\in f^{-1}(x_{f},\infty)$: $(f^{-1})^{\prime}(x)\leq K(f^{-1})^{\prime}(\theta x)$ and $f^{\prime}(y)\leq Kf^{\prime}(\theta y)$;

For all $y\in[x_{f},\infty)$, $\frac{f(x)}{f^{\prime}(x)}\in[\frac{1}{2K}x,2Kx]$;

For all $x\in[f^{-1}(x_{f}),\infty)$, $\frac{f^{-1}(x)}{(f^{-1})^{\prime}(x)}\in[\frac{1}{2K}x,2Kx]$.

$f(x)=\Theta(x)$ as $x\rightarrow\infty$.

All properties are easy to verify in Proposition 1 and we omit it here. For brevity, we will use $g(x)=f^{-1}(x)$ in the following proofs.

A.2 KKT Condition

Being a KKT point is a first order necessary condition for being an optimal point. We first give the definition of approximate KKT point for general optimization problem $(Q)$.

For any $\varepsilon,\delta>0$, a feasible point of $(Q)$ is an $(\varepsilon,\delta)$-KKT point if there exists $\lambda_{i}\geq 0$, $\mathbf{k}\in{\partial}f(\boldsymbol{x})$, and $\boldsymbol{h}_{i}\in{\partial}g_{i}(\boldsymbol{x})$ for all $i\in[N]$ (we will slightly abuse ${\partial}f(\boldsymbol{x})$ to respresent a element in ${\partial}f(\boldsymbol{x})$) such that

1. $\left\|\boldsymbol{k}+\sum_{i\in[N]}\lambda_{i}\boldsymbol{h}_{i}(\boldsymbol{x})\right\|_{2}\leq\varepsilon$;

2. $\forall i\in[N]:\lambda_{i}g_{i}(\boldsymbol{x})\geq-\delta$.

Specifically, when $\varepsilon=\delta=0$, we call $\boldsymbol{x}$ a KKT point of $(Q)$.

The following Mangasarian-Fromovitz constraint qualification (MFCQ) bridges $(\varepsilon,\delta)$ KKT points with KKT points.

MFCQ guarantees that the limit of approximate KKT point with convergent $\varepsilon$ and $\delta$ is a KKT point.

A.3 How is the Continuous Form of Conditioner Formulated?

In this subsection, we show how conditioners of the continuous case for AdaGrad, RMSProp, Adam (w/m) are derived. Both discrete updates of these optimizers can be written as

where $\partial^{s}\mathcal{L}(\boldsymbol{w}(t))\in\partial\mathcal{L}(\boldsymbol{w}(t))$. For AdaGrad, $\phi(\boldsymbol{m}(t),\partial^{s}\mathcal{L}(\boldsymbol{w}(t)))=\partial^{s}\mathcal{L}(\boldsymbol{w}(t))^{2}$, $\psi(\boldsymbol{m}(t),t)=\boldsymbol{m}(t)$; for RMSProp, $\phi(\boldsymbol{m}(t),\partial^{s}\mathcal{L}(\boldsymbol{w}(t)))=(1-b)(\partial^{s}\mathcal{L}(\boldsymbol{w}(t))^{2}-\boldsymbol{m}(t))$, $\psi(\boldsymbol{m}(t),t)=\boldsymbol{m}(t)$; for Adam (w/m), $\phi(\boldsymbol{m}(t),\partial^{s}\mathcal{L}(\boldsymbol{w}(t)))=(1-b)(\partial^{s}\mathcal{L}(\boldsymbol{w}(t))^{2}-\boldsymbol{m}(t))$, $\psi(\boldsymbol{m}(t),t)=\frac{\boldsymbol{m}(t)}{1-b^{t}}$.

One can easily observe that eqs. (6) and (7) is a discretization of the following equations:

By solving the above differential equation, we have

Therefore, for RMSProp, the continuous flow is

while for Adam (w/m), the continuous flow is

A.4 o-Minimal Structure and Definable functions

Here we define o-Minimal structure and definable functions which we omit in Theorem 3.

A definable function on above o-Minimal Structure can be defined as follows:

A natural question is: which function is definable? The next Lemma helps to solve this question.

All polynomials are definable, therefore, linear or other polynomial activation is definable;

If both $f(x)$ and $g(x)$ are definable, $\min{f(x),g(x)}$ and $\max{f(x),g(x)}$ are definable, therefore, ReLU activation is definable;

then all $h_{j}$ are definable. Therefore, neural networks with polynomial and ReLU activation, convolutional and max-pooling layers, and skip connections are definable.

An important property for definable function is Kurdyka-Lojasiewicz inequality, which can bound gradient of definable function in a small region. Here we present two Kurdyka-Lojasiewicz inequalities given by (Ji & Telgarsky, 2020):

Given a locally Lipschitz definable function $f$ with an open domain $D\in\{x|\|x\|>1\}$, for any $c$, $\eta>0$, there exists $a>0$ and a definable desingularizing function $\Psi$ on $[0,a)$ (that is, $\Psi(x)\in C^{1}((0,a))\cap C^{0}([0,a))$ with $\Psi(0)=0$), such that,

where $\bar{\partial}f(x)$ is the unique one with the smallest norm in $\partial f(x)$, $\bar{\partial}_{\backslash\backslash}f(x)$ is the projection of $\bar{\partial}f(x)$ to $x$ and $\bar{\partial}_{\perp}f(x)=\bar{\partial}f(x)-\bar{\partial}_{\backslash\backslash}f(x)$ is the remaining term

Given a locally Lipschitz definable function $f$ with an open domain $D\subset\{x|\|x\|>1\}$, for any $\lambda>0$, there exists $a>0$, and a definable desingularizing function $\Psi$ on $[0,a)$ such that

At the end of this subsection, we show that definability actually guarantees that $\Phi$ admits a chain rule, which is formally stated as following:

Therefore, if we are deal with definable neural networks $\Phi$ as in Theorem 3, we no longer need to assume $\Phi$ admits a chain rule which is already guaranteed by lemma 11.

For AdaGrad, $\boldsymbol{h}^{-2}_{\infty}$ is defined as $\varepsilon\mathbf{1}_{p}+\sum_{t=0}^{\infty}\nabla\mathcal{L}(\boldsymbol{w}(t))^{2}$, which is the sum of squared gradients along the trajectory. Intuitively, as the initialization changes, the trajectory changes respectively, and so does the direction of $\boldsymbol{h}_{\infty}$. This intuition can be further verified by Experiment in Section 6.2, where we plot the direction of $\boldsymbol{h}^{-\frac{1}{2}}_{\infty}$ as the initialization changes.

Furthermore, how $\boldsymbol{h}_{\infty}$ influence the max-margin problem can be interpreted as follows: optimizing $\|\boldsymbol{h}_{\infty}^{-\frac{1}{2}}\odot\boldsymbol{w}\|^{2}$ with constraints is equivalent to find the radius $r$ of ellipsoid $\|\boldsymbol{h}_{\infty}^{-\frac{1}{2}}\odot\boldsymbol{w}\|^{2}=r^{2}$ when the ellipsoid is tangent to the feasible set. This intuition is visualized in Figure 3. One can easily observe that as the direction of $\boldsymbol{h}_{\infty}$ changes, the direction of the tangent point changes.

A.6 Basic knowledge from Measure Theory

In this section, we present basic definitions of measurable set, measurable functions and Lebesgue Integrability. These definition involves use of exterior measure and Borel set in Euclidean space, which we omit them here. Readers interested in measure theory can refer to (Stein & Shakarchi, 2009) for details.

Appendix B Proof of Results for Adaptive Algorithms in Continuous Case

This section collects proof of Theorem 2, Theorem 4, Theorem 5, and also contains proof of Theorem 6 and Theorem 7. Organization of this section is as follows: In Subsection B.1, we present proof of Theorems 4 and Theorem 5; in Subsection B.2, we present proof of Theorem 2 based on the proof skeleton in Section 5; in Subsection B.3, we prove Theorem 6 and Theorem 7 based on 2, Theorem 4, Theorem 5; finally, in Subsection B.4, we provide tight convergence rate of loss and parameter norm in adaptive gradient flows.

For AdaGrad flow defined as eq. (4) with $\boldsymbol{h}=\boldsymbol{h}^{A}$,

which leads to a contradictory, since $\mathcal{L}(\boldsymbol{\omega}(0))-\mathcal{L}(\boldsymbol{\omega}(t))$ is upper bounded by $\mathcal{L}(\boldsymbol{\omega}(0))$.

Define $\boldsymbol{h}_{\infty}=\lim_{t\rightarrow\infty}\boldsymbol{h}^{A}(t)$. Then $\boldsymbol{h}_{\infty}$ has no zero elements. Let

by Lemma 12, $\boldsymbol{h}_{\infty}$ has no zero elements.

We then prove eq. (10) by direct calculation.

$\lim_{t\rightarrow\infty}\boldsymbol{\beta}^{A}(t)=1$ can be derived directly by convergence of $\boldsymbol{h}^{A}(t)$, while since

where inequality $(*)$ is due to $\boldsymbol{h}^{A}$ is non-increasing.

B.1.2 Proof of Theorem 5

For RMSProp flow defined as eq. (4) with $\boldsymbol{h}=\boldsymbol{h}^{R}$ , $F_{i}(t)$ is bounded ($i=1,2,\cdots,p$), that is,

When $b=1$, $F_{i}(t)=0$ for all $t$ and $i$, which trivially yields the claim. When $b\neq 1$, we use reduction of absurdity. If there exists an $i$, such that, $\overline{\lim}_{t\rightarrow\infty}F_{i}(t)=\infty$, then $t_{k}\overset{\triangle}{=}\inf\{t:F_{i}(t)\geq k\}<\infty$ holds. Furthermore, since $\mathcal{L}$ is locally Lipschitz with respect to $\boldsymbol{w}$, $g_{i}(t)$ is locally bounded for any $t$, which leads to the absolute continuity of $F_{i}$. Therefore, since $F_{i}(0)=0$, $t_{k}$ monotonously increases.

Similar to Lemma 13, when $b=1$, the claim trivially holds. When $b\neq 1$, by Lemma 13, there exist $M_{i}>0$ $(i=1,2,\cdots,p)$, such that, $F_{i}(t)\leq M_{i}$ for any $t>0$. Therefore,

Therefore, for any positive real $\varepsilon>0$ and a fixed index $i\in[p]$, there exists a time $T$, such that,

Since $\varepsilon$ and $i$ can be picked arbitrarily, the proof is completed. ∎

Similar to the proof of Lemma 9, we can rewrite the RMSProp flow as

For any fixed $i=1,2,\cdots,p$, by Lemma 14,

In the rest of the section, we extend the proof of Theorem 5 from RMSProp to Adam.

Conditioner for Adam is the same as RMSProp, except that Adam will divide a bias-corrected term $1-b^{t}$ for conditioner each step, that is,

Generally, updates of RMSProp and Adam (w/m) can be both expressed as

The proof follows the same routine as proof of Lemma 13, except in this case we have

The proof is the same as proof of Lemma 14, except that

The proof is the same as proof of Theorem 5 for RMSProp flow, except that

It is worth noting that the current framework of adaptive gradient flow can not cover Adam with a decaying $\varepsilon$ or without $\varepsilon$. It will be interesting to see if the framework can be modified to analyze these optimizers, and we leave this as a future work.

B.2 Proof of Theorem 2

In the beginning, we first prove a basic lemma for normalized margin, i.e., the normalized margin $\gamma$ and normalized gradients are upper bounded:

By the definition of approximate norm $\rho(t)=\|\boldsymbol{\beta}(t)^{-\frac{1}{2}}\odot\boldsymbol{v}(t)\|$ and $\lim_{t\rightarrow\infty}\boldsymbol{\beta}(t)=\mathbf{1}_{p}$, we have that

which leads to $\lim_{t\rightarrow\infty}\frac{\rho(t)}{\|\boldsymbol{v}(t)\|}=1$.

Therefore, the surrogate margin can be bounded as

The derivative of $\rho^{2}$ is as follows:

By taking derivative directly, we have that

where eq. $(*)$ comes from Homogeneity Assumption 1. I.

We first construct time $t_{1}$ as follows: by properties of $\boldsymbol{\beta}(t)$ in Definition 1, there exists some large enough time $t_{1}>t_{0}$, such that for any $t>t_{1}$,

where inequality $(*)$ comes from Cauchy-Schwarz inequality.

Combining the estimation of $A$ and $B$, we then have

which by Lemma 17, the last term is bounded.

Let $\boldsymbol{v}$ obey an adaptive gradient flow which satisfies Assumption 1. Let $t_{1}$ be constructed as Lemma 2. Then, for any $t\geq t_{1}$, define

Then, for any $t\geq t_{1}$, the following inequality holds:

Taking integration to both sides, we have

B.2.3 Verification of KKT Condition

We verify the definition of approximate KKT point directly.

and eq. $(**)$ is because $e^{-x}x\leq e^{-1}$.

Before moving forward, we introduce an equivalent proposition of that $(1-\cos(\boldsymbol{\theta}))$ goes to zero.

Following the same routine, we have $\lim_{i\rightarrow\infty}\left\|\hat{\boldsymbol{v}}(t)-\widehat{\boldsymbol{\beta}(t)^{-\frac{1}{2}}\odot\boldsymbol{v}(t)}\right\|=0$.

(2). $\rho(t)$ satisfies that, for any $t^{2}>t^{1}>t_{1}$,

The proof for (2). is completed by integration.

where $\tau_{0}$ in eq. $(*)$ is in $[t_{1},t]$ and First Mean Value Theorem guarantees its existence.

For any time $t_{3}>t_{2}\geq t_{1}$, there exists a time $\xi\in(t_{2},t_{3})$, such that,

We then prove the second inequality in Lemma 6 to complete the proof of Lemma 6.

Applying Lemma 5 and Lemma 6, we can then prove Theorem 2.

Let $\bar{\boldsymbol{v}}$ be any limit point of series $\{\boldsymbol{v}(t)\}_{t=0}^{\infty}$. We construct a series of approximate KKT point which converges to $\bar{\boldsymbol{v}}$ by induction.

Let $t^{1}=t_{1}$. Now suppose $t^{k-1}$ has been constructed. By Lemma 3 and that $\bar{\boldsymbol{v}}$ is a limit point, there exists $s_{k}>t^{k-1}$ such that, for any $t>s_{k}$

and $\gamma(t^{k})$ converges to a positive number, we further have

is a KKT point of $(P)$, and along the same direction of $\bar{\boldsymbol{v}}$.

B.3 Convergent Direction of AdaGrad, RMSProp and Adam (w/m): proof of Theorems 6 and 7

First of all, we prove Theorem 6 by substitute $\boldsymbol{v}$ in Theorem 2 with $\boldsymbol{h}_{\infty}\odot\boldsymbol{w}$.

Theorem 7 can be obtained in the same way.

The claim holds since $\boldsymbol{v}^{R}$ is just $\boldsymbol{w}$ with a positive scaling factor, $\boldsymbol{v}^{R}$ and $\boldsymbol{w}$ share the same direction.

B.4 Convergence Rate of Empirical Loss and Parameter Norm

In the end of this section, we will give a tight bound for the convergence rate of empirical loss and parameter norm, which is derived by estimating $G(x)$ in Lemma 20. These results will further be used in Appendix C.

Then $G(x)=\Theta(x(\log x)^{\frac{2}{L}-2})$, and $G^{-1}(x)=\Theta(x(\log x)^{2-\frac{2}{L}})$. Consequently,

Since $G(x)$ is monotonously increasing, and $\lim_{x\rightarrow\infty}G(x)=\infty$, we have $x=\Theta\left(G^{-1}(x)(\log G^{-1}(x))^{\frac{2}{L}-2}\right)$, which further leads to $G^{-1}(x)=\Theta(x(\log x)^{2-\frac{2}{L}})$.

Appendix C Proof of Theorem 3

In this section, we will prove that direction of parameters converges, that is, $\lim_{t\rightarrow\infty}\frac{\boldsymbol{v}(t)}{\|\boldsymbol{v}(t)\|}$ exists. Concretely, define the length swept by $\frac{\boldsymbol{v}(t)}{\|\boldsymbol{v}(t)\|}$ as $\zeta(t)$, i.e.,

We will upper bound $\zeta(t)$ in the rest of this section.

If the neural network $\Phi(\boldsymbol{w},\boldsymbol{x})$ is definable with respect to $\boldsymbol{w}$ for any $\boldsymbol{x}$, for any $\boldsymbol{v}$ satisfying the following adaptive gradient flow

The proof of Lemma 25 follows the same routine as that of Lemma 5.2 in (Davis et al., 2020), and we omit it here.

We then define another surrogate margin $\bar{\gamma}$ as

The following Lemma then lower bound the derivative of $\bar{\gamma}$.

To begin with, we calculate the rate of $\boldsymbol{\beta}$ converging to $\mathbf{1}_{p}$. For AdaGrad, given a fixed index $i\in[N]$, we have that,

Similarly, for RMSProp, given a fixed index $i\in[N]$,

We then directly calculate the derivative of $\bar{\gamma}$:

Therefore, there exists a large enough $T$, such that, any $t\geq T$,

The following lemma gives an equivalent proposition of that the curve length $\zeta$ is finite.

There exists $a,\gamma_{0}>0$ and a definable desingularizing function $\Phi$ on $[0,a)$, such that, for large enough $t$,

Case I. $\left\|\bar{\partial}_{\perp}\bar{\gamma}(\boldsymbol{v}(t))\right\|\geq\|\boldsymbol{v}(t)\|^{\frac{L}{4}}\left\|\bar{\partial}_{\backslash\backslash}\bar{\gamma}(\boldsymbol{v}(t))\right\|$.

Applying Lemma 9 to $\gamma_{0}-\bar{\gamma}(\boldsymbol{v})|_{\|\boldsymbol{v}\|>1}$, there exists an $a_{1}>0$ and a definable desingularizing function $\Psi_{1}$, such that if $\|\boldsymbol{v}\|>1$, $\bar{\gamma}(\boldsymbol{v})>\gamma_{0}-a_{1}$, and

Since $\lim_{t\rightarrow\infty}\bar{\gamma}(t)=\gamma_{0}$, and $\lim_{t\rightarrow\infty}\|\boldsymbol{v}(t)\|=\infty$, there exists a large enough time $T_{1}$, such that, for every $t\geq T_{1}$, $\|\boldsymbol{v}(t)\|>1$, and $\bar{\gamma}(t)>\gamma_{0}-a_{1}$.

Therefore, for any $t\geq T_{1}$ which satisfies $\left\|\bar{\partial}_{\perp}\bar{\gamma}(\boldsymbol{v}(t))\right\|\geq\|\boldsymbol{v}(t)\|^{\frac{L}{4}}\left\|\bar{\partial}_{\backslash\backslash}\bar{\gamma}(\boldsymbol{v}(t))\right\|$, we have

Case II. $\left\|\bar{\partial}_{\perp}\bar{\gamma}(\boldsymbol{v}(t))\right\|<\|\boldsymbol{v}(t)\|^{\frac{L}{4}}\left\|\bar{\partial}_{\backslash\backslash}\bar{\gamma}(\boldsymbol{v}(t))\right\|$.

Applying Lemma 10 to $\gamma_{0}-\bar{\gamma}(\boldsymbol{v})|_{\|\boldsymbol{v}\|>1}$, we have that there exists an $a_{2}>0$ and a desingularizing function on $[0,a_{2})$, such that if $\boldsymbol{v}>1$, and $\bar{\gamma}(\boldsymbol{v})>\gamma_{0}-a_{2}$, then

combining eqs. (18) and (19), we have that

Concluding Case I. and Case II., for any $t\geq\max\{T_{1},T_{2}\}$, and $\Psi(x)=\max\{4\Psi_{1}(x),$ $\frac{2(B_{1}+Lg\left(\log\frac{1}{Ne^{-f(0)}}\right))\max\left\{1,\frac{4}{L}\right\}}{LC_{1}}\Psi_{2}(x)\}$, we have that

Appendix D Proof for the Discrete Case

We prove the result for AdaGrad and experiential loss, with the result for RMSProp and logistic loss follows exactly as the continuous case. We slightly change the order of four stages in the flow: First, in Section D.1, we prove that the conditioner has a limit with no zero entry; secondly, in Section D.2, we prove that the empirical loss converges to zero; then, in Section D.3, we construct a further smoothed approximate margin, and prove it has a lower bound; finally, in Section D.4, we prove that every limit point of AdaGrad is along some KKT point of optimization problem $(P^{A})$ defined in Theorem 6.

Before the proof, we give a formal definition of the learning rate bound $C(t)$ in Assumption 2: let $M$ be the smooth constant in Assumption 2. I. Then, $C(t)=\max\{\min_{i}\{\boldsymbol{h}^{A}_{i}(t)^{-1}\}/M,1,\frac{C^{2}_{1}}{2LNe^{-1}}\}$, where $C_{0}$ will be clear below. By the monotony of $\boldsymbol{h}^{A}_{i}(t)$, apparently $C(t)$ is non-decreasing. Now we can prove $\sum_{t=1}^{\infty}\partial^{s}\mathcal{L}(\boldsymbol{w}(t))^{2}<\infty$.

Suppose $\mathcal{L}$ is $M$ smooth with respect to $\boldsymbol{w}$. Then, for $\{\partial^{s}\mathcal{L}(\boldsymbol{w}(t))\}_{t=1}^{\infty}$ updated by AdaGrad (eq. (3)), $\sum_{t=1}^{\infty}\partial^{s}\mathcal{L}(\boldsymbol{w}(t))^{2}<\infty$.

Thus, since $\sum_{t=1}^{\infty}a_{t}$ share the same convergent behavior with $\sum_{t=1}^{\infty}\frac{a_{t}}{\sum_{\tau=1}^{t}a_{\tau}}$ ($a_{t}\geq 0$), by similar routine of Lemma 12, the proof is completed. ∎

Therefore, $\boldsymbol{h}_{\infty}\overset{\triangle}{=}\lim_{t\rightarrow\infty}\boldsymbol{h}^{A}(t)$ has no zero entry. We can then define a discrete version of adaptive gradient flow as

and $\boldsymbol{\beta}(t)$ decreases component-wisely to $\mathbf{1}_{p}$.

By Lemma 28, for any $t\geq t_{0}$, $\mathcal{L}(\boldsymbol{w}(t))\leq\mathcal{L}(\boldsymbol{w}(t_{0}))<N$. Therefore, there exists a positive real constant $C_{0}$ only depending on $\mathcal{L}(\boldsymbol{w}(t_{0}))$, such that, $\|\boldsymbol{w}(t)\|\geq C_{0}$. Furthermore, since $\boldsymbol{h}_{\infty}^{-\frac{1}{2}}\geq\boldsymbol{h}(t_{0})^{-\frac{1}{2}}$, $\|\boldsymbol{v}(t)\|\geq C_{0}\max_{i}\{\boldsymbol{h}_{i}(t_{0})^{-\frac{1}{2}}\}$. Define $C_{1}=C_{0}\max_{i}\{\boldsymbol{h}_{i}(t_{0})^{-\frac{1}{2}}\}$, which only depends on $\mathcal{L}(\boldsymbol{w}(t_{0}))$ and $\partial^{s}\mathcal{L}(\boldsymbol{w}(t))$ $(t\leq t_{0})$.

Moreover, similar to approximate flow, there exists a time $t_{1}$, such that, for any time $t\geq t_{1}$,

D.2 Convergence of Empirical Loss

The change of $\|\boldsymbol{v}(t)\|$ can be calculated as

By the convexity of $\log\log\frac{1}{x}$ (when $x$ is small) and $-\log x$,

By Lemma 32, for any integer time $t\geq t_{0}$

D.3 Convergence of surrogate margin

There exists a large enough time $t_{2}\geq t_{1}$, such that, for any $t\geq t_{2}$,

The proposition is obvious since $\log^{i}(\frac{1}{x})=\mathbf{o}(x)$, $\forall i$ as $x\rightarrow 0$. ∎

Then, we define a further surrogate margin $\hat{\gamma}$ of the discrete case as following:

where $\rho(t)$ is defined as $\|\boldsymbol{\beta}^{-\frac{1}{2}}(t)\odot\boldsymbol{v}(t)\|$, and $\Phi(x)$ is defined as

The following properties hold for $\hat{\gamma}$.

As beginning, we verify the existence of $\Phi$. Actually, when $x$ is small enough, $\frac{1+2(1+\lambda(x)/L)\mu(x)}{x\log\frac{1}{x}}$ decreases, and $\lim_{x\rightarrow 0}\frac{1+2(1+\lambda(x)/L)\mu(x)}{x\log\frac{1}{x}}=\infty$. Therefore, there exists a small enough $\varepsilon$, such that, for any $w<\varepsilon$,

which is integrable as $w\rightarrow 0$. Concretely, for any $x<\varepsilon$,

Therefore, for a series $\{\boldsymbol{v}_{i}\}_{i=1}^{\infty}$ satisfying $\lim_{i\rightarrow\infty}\|\boldsymbol{v}_{i}\|=\infty$,

The next lemma characterizes the behavior of surrogate margin $\hat{\gamma}(t)$.

For positive integer time $t\geq t_{2}$, $\hat{\gamma}(t)\geq e^{-\frac{1}{2}}\hat{\gamma}(t_{2})$.

On the other hand, since $\boldsymbol{\beta}^{-\frac{1}{2}}$ is non-decreasing,

$\|\boldsymbol{\beta}^{-\frac{1}{2}}(t)\odot\boldsymbol{v}(t+1)\|^{2}-\|\boldsymbol{\beta}^{-\frac{1}{2}}(t)\odot\boldsymbol{v}(t)\|^{2}$ can also be upper bounded as follows:

Taking the estimation eq. (24) back to eq. (23), we have

Similar to the flow case, we can then prove the convergence of $\hat{\gamma}$.

There exists a positive real $\hat{\gamma}_{\infty}$, such that

we have that $\hat{\gamma}(t)\Pi_{i=1}^{p}\frac{1}{\boldsymbol{\beta}^{\frac{1}{2}}_{i}(t)}$ monotonously increases. Furthermore, since $\hat{\gamma}(t)<\gamma(t)$ is bounded, so does $\hat{\gamma}(t)\Pi_{i=1}^{p}\frac{1}{\boldsymbol{\beta}^{\frac{1}{2}}_{i}(t)}$. Therefore, $\hat{\gamma}(t)\Pi_{i=1}^{p}\frac{1}{\boldsymbol{\beta}^{\frac{1}{2}}_{i}(t)}$ converges to a positive real. Since $\lim_{t\rightarrow\infty}\Pi_{i=1}^{p}\frac{1}{\boldsymbol{\beta}^{\frac{1}{2}}_{i}(t)}=1$, the proof is completed. ∎

D.4 Verification of KKT point

Similar to the flow case, we have the following construction of $(\varepsilon,\delta)$ KKT point. The proof is exactly the same as Lemma 5, and we omit it here.

We still need a lemma to bound the change of the direction of $\boldsymbol{\beta}^{-\frac{1}{2}}\odot\boldsymbol{v}$.

where eq. $(*)$ can be derived in the same way as Lemma 6;

We then prove that $\sum_{\tau=t_{2}}^{\infty}\log\frac{\|\boldsymbol{\beta}^{-\frac{1}{2}}(\tau)\odot\boldsymbol{v}(\tau+1)\|}{\rho(\tau)}=\infty$.

The sum of $\log\frac{\|\boldsymbol{\beta}^{-\frac{1}{2}}(\tau)\odot\boldsymbol{v}(\tau+1)\|}{\rho(\tau)}$ diverges, that is, $\sum_{\tau=t_{2}}^{\infty}\log\frac{\|\boldsymbol{\beta}^{-\frac{1}{2}}(\tau)\odot\boldsymbol{v}(\tau+1)\|}{\rho(\tau)}=\infty$.

The proof is completed since $\lim_{t\rightarrow\infty}\rho(t)=\infty$ and $\log\Pi_{i=1}^{p}\frac{1}{\boldsymbol{\beta}^{-\frac{1}{2}}_{i}(t)}$ is bounded. ∎

Let $\bar{\boldsymbol{v}}$ be any limit point of $\{\boldsymbol{v}(t)\}_{t=1}^{\infty}$. Then $\bar{\boldsymbol{v}}$ is a KKT point of optimization problem $(P)$.

Let $t^{1}$ be any integer time larger than $t_{2}$. We construct a sequence $\{t^{i}\}_{i=1}^{\infty}$ by iteration. Suppose $t^{1},\cdots,t^{k-1}$ have been constructed. Let $s^{k}>t^{k-1}$ be a large enough time which satisfies

Therefore, similar to the gradient flow case, we then have the following theorem.

Let $\bar{\boldsymbol{w}}$ be any limit point of $\{\hat{\boldsymbol{w}}(t)\}$. Then $\bar{\boldsymbol{w}}$ is along the direction of a KKT point of the following optimization problem.

Appendix E Proof of Multi-class Classification with Logistic Loss

In this section, we prove the result for multi-class classification with logistic loss mentioned in Remark 1. Concretely, the dataset for this case can be represented as $\{(\boldsymbol{x}_{i},y_{i})\}_{i=1}^{N}$, where $y_{i}\in[C]$ represents the class $\boldsymbol{x}_{i}$ belongs to. Unlike the binary classification case, neural network $\boldsymbol{\Phi}$ outputs a $C$-dimension vector as scores for $C$ classes, and we use $\boldsymbol{\Phi}(\boldsymbol{w},\boldsymbol{x}_{i})_{j}$ as the $j$-th component of $\boldsymbol{\Phi}(\boldsymbol{w},\boldsymbol{x}_{i})$. The empirical loss can then be represented as

Let $\boldsymbol{v}$ satisfy an adaptive gradient flow $\mathcal{F}$ which satisfies Assumption 1. Let $\bar{\boldsymbol{v}}$ be any limit point of $\{\hat{\boldsymbol{v}}(t)\}_{t=0}^{\infty}$ (where $\hat{\boldsymbol{v}}(t)=\frac{\boldsymbol{v}(t)}{\|\boldsymbol{v}(t)\|}$ is normalized parameter). Then $\bar{\boldsymbol{v}}$ is along the direction of a KKT point of the following $L^{2}$ max-margin problem $(P)$:

Proof of Theorem 14 differs from that of Theorem 2 only by Lemma 18, Lemma 19, and the construction of $\lambda_{i}$ in Lemma 21. We show modifications respectively.

By definition of empirical loss (eq. (26)),

Combining eqs. (27) and (28), the proof is completed.

Secondly, we calculate derivative of surrogate norm $\rho$ under multi-class classification setting.

The derivative of $\rho^{2}$ is as follows:

while other parts of the proof follows exact the same as Lemma 19.

Finally, we provide construction of $\lambda_{i}$ similar to Lemma 21. The proof follows the same routine as Lemma 21 and we omit it here.

Appendix F Experiment Details

In this section, we provide detailed explanation of experiments showed in Section 6 https://github.com/bhwangfy/ICML-2021-Adaptive-Bias. This section is divided into two parts according to Section 6: in Section F.1, we provide details of structure of neural network we use and hyper-parameters. We also further plot two additional experiments of Adam and SGD to show the influence of momentum; in Section F.3, we show construction of dataset in Section 6.2 and choose of hyper-parameters. We also show how direction of $\boldsymbol{h}_{\infty}^{-\frac{1}{2}}$ influence convergent direction of parameters.

We use the $4$-layer convolutional neural network adopted by (Madry et al., 2018) as our model to conduct multi-class classification on MNIST (LeCun, 1998). Concretely, this convolutional neural network can be expressed in order as convolutional layer with $32$ channel and filter size $5\times 5$, max-pool layer with kernel size $2$ and stride $2$, convolutional layer with $64$ channel and filter size $3\times 3$, max-pool with kernel size $2$, fully connected layer with width $1024$, and fully connected layer with width $10$. In order to guarantee this neural network is homogeneous, we further set bias in all layers to be zero. We use default method in Pytorch to initialize the neural network.

As for hyper-parameters, we set learning rate of AdaGrad to be the default value in Pytorch; while for RMSProp, we set learning rate and decay parameter $b$ as $0.001$ and $0.9$, which is suggested by (Hinton et al., 2012) and used as a default value in Tensorflow; for Adam, we set the learning rate to $0.0001$ as default value in Pytorch, and $b$ to be the same as RMSProp.

F.1.2 Influence of Momentum

We plot convergent behaviors for SGDm and Adam in this section. Figure 4 shows that adding momentum term will NOT keep normalized margin from lower bounded, which indicates our theory might be extended to gradient based optimization methods with momentum. Specifically, for SGD, we use learning rate $0.1$ and momentum parameter $0.9$; for Adam, we use the same setting as Adam (w/m) with momentum parameter $0.9$.

F.2 Influence of ε𝜀\varepsilon

We compare the generalization behaviors of RMSProp with different $\varepsilon$ selected in Figure 5. It is observed that as $\varepsilon$ decreases, normalized margin gets smaller and the generalization error gets larger, which indicates the importance of $\varepsilon$ on the generalization behavior. When $\varepsilon$ is completed removed (i.e., is set to ), the training does not converge. Therefore, we do not include the results for $\varepsilon=0$ here.

F.3 Experiment on Two Layer MLP

where $\boldsymbol{\varepsilon}_{i}$ ($i=1,2,3,\cdots,100$) are random variables sampled uniformly and i.i.d. from $[-0.6,0.6]\times[-0.6,0.6]$. We visualize the dataset in Figure 6(a).

We then run SGD, AdaGrad, RMSProp (and Adam (w/m)) respectively with learning rates $\eta=0.1$, while Weight-decay hyper-parameter $b$ is set to be $0.9$. For each round, we train the model for $5000$ epochs to ensure that training accuracy achieves $100\%$ (see Figure 6(c) for details); while for each optimizer, we conduct $100$ rounds of experiments with random initialization, Convergent directions of square root of inverse conditioners $\boldsymbol{h}_{\infty}^{-\frac{1}{2}}$ are plotted in Figures 6(d), 6(e), and 6(f). Since $\boldsymbol{h}_{\infty}^{-\frac{1}{2}}$ occurs in optimization target in $(P^{A})$, different direction of $\boldsymbol{h}_{\infty}^{-\frac{1}{2}}$ may lead to different convergent direction of parameters, which further indicates convergent direction of parameters in AdaGrad can be vulnerable to random initialization.