Characterizing Implicit Bias in Terms of Optimization Geometry

Introduction

Implicit bias from the optimization algorithm plays a crucial role in learning deep neural networks as it introduces effective capacity control not directly specified in the objective (Neyshabur et al., 2015b, a; Zhang et al., 2017; Keskar et al., 2016; Wilson et al., 2017; Neyshabur et al., 2017). In overparameterized models where the training objective has many global minima, optimizing using a specific algorithm, such as gradient descent, implicitly biases the solutions to some special global minima. The properties of the learned model, including its generalization performance, are thus crucially influenced by the choice of optimization algorithm used. In neural networks especially, characterizing these special global minima for common algorithms such as stochastic gradient descent (SGD) is essential for understanding what the inductive bias of the learned model is and why such large capacity networks often show remarkably good generalization even in the absence of explicit regularization (Zhang et al., 2017) or early stopping (Hoffer et al., 2017).

Implicit bias from optimization depends on the choice of algorithm, and changing the algorithm, or even changing associated hyperparameter can change the implicit bias. For example, Wilson et al. (2017) showed that for some standard deep learning architectures, variants of SGD algorithm with different choices of momentum and adaptive gradient updates (AdaGrad and Adam) exhibit different biases and thus have different generalization performance; Keskar et al. (2016), Hoffer et al. (2017) and Smith (2018) study how the size of the mini-batches used in SGD influences generalization; and Neyshabur et al. (2015a) compare the bias of path-SGD (steepest descent with respect to a scale invariant path-norm) to standard SGD.

It is therefore important to explicitly relate different optimization algorithms to their implicit biases. Can we precisely characterize which global minima different algorithms converge to? How does this depend on the loss function? What other choices including initialization, step-size, momentum, stochasticity, and adaptivity, does the implicit bias depend on? In this paper, we provide answers to some of these questions for simple linear regression and classification models. While neural networks are certainly more complicated than these simple linear models, the results here provide a segue into understanding such biases for more complex models.

For linear models, we already have an understanding of the implicit bias of gradient descent. For underdetermined least squares objective, gradient descent can be shown to converge to the minimum Euclidean norm solution. Recently, Soudry et al. (2017) studied gradient descent for linear logistic regression. The logistic loss is fundamentally different from the squared loss in that the loss function has no attainable global minima. Gradient descent iterates therefore diverge (the norm goes to infinity), but Soudry et al. showed that they diverge in the direction of the hard margin support vector machine solution, and therefore the decision boundary converges to this maximum margin separator.

Can we extend such characterization to other optimization methods that work under different (non-Euclidean) geometries such as mirror descent with respect to some potential, natural gradient descent with respect to a Riemannian metric, and steepest descent with respect to a generic norm? Can we relate the implicit bias to these geometries?

As we shall see, the answer depends on whether the loss function is similar to a squared loss or to a logistic loss. This difference is captured by two family of losses: (a) loss functions that have a unique finite root, like the squared loss and (b) strictly monotone loss functions where the infimum is unattainable, like the logistic loss. For losses with a unique finite root, we study the limit point of the optimization iterates, $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}$. For monotone losses, we study the limit direction $\bar{w}_{\infty}=\lim_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}$.

In Section 2 we study linear models with loss functions that have unique finite roots. We obtain a robust characterization of the limit point for mirror descent, and discuss how it is independent of step-size and momentum. For natural gradient descent, we show that the step-size does play a role, but get a characterization for infinitesimal step-size. For steepest descent, we show that not only does step-size affects the limit point, but even with infinitesimal step-size, the expected characterization does not hold. The situation is fundamentally different for strictly monotone losses such as the logistic loss (Section 3) where we do get a precise characterization of the limit direction for generic steepest descent. We also study the adaptive gradient descent method (AdaGrad) Duchi et al. (2011) (Section 3.3) and optimization over matrix factorization (Section 4). Recent studies considered the bias of such methods for least squares problems (Wilson et al., 2017; Gunasekar et al., 2017), and here we study these algorithms for monotone loss functions, obtaining a more robust characterization for matrix factorization problems, while concluding that the implicit bias of AdaGrad depends on initial conditions including step-size even for strict monotone losses.

Losses with a Unique Finite Root

Consider gradient descent updates for minimizing $\mathcal{L}(w)$ with step-size sequence $\{\eta_{t}\}_{t}$ and initialization ${w_{(0)}}$,

The same argument also extends for updates with instance-wise stochastic gradients, where we use a stochastic estimate $\widetilde{\nabla}\mathcal{L}({w_{(t)}})$ of the full gradient $\nabla\mathcal{L}({w_{(t)}})$ computed from a random subset of instances $S_{t}\subseteq[N]$,

Moreover, when initialized with ${{w_{(0)}}}=0$, the implicit bias characterization also extends to the following generic momentum and acceleration based updates,

where $\Delta{w_{(t-1)}}={w_{(t)}}-{w_{(t-1)}}$. This includes Nesterov’s acceleration ($\beta_{t}=\gamma_{t}$) (Nesterov, 1983) and Polyak’s heavy ball momentum ($\gamma_{t}=0$) (Polyak, 1964).

For losses with a unique finite root, the implicit bias of gradient descent therefore depends only on the initialization and not on the step-size or momentum or mini-batch size. Can we get such succinct characterization for other optimization algorithms? That is, characterize the bias in terms of the optimization geometry and initialization, but independent of choices of step-sizes, momentum, and stochasticity.

2 Mirror descent

Mirror descent (MD) (Beck and Teboulle, 2003; Nemirovskii and Yudin, 1983) was introduced as a generalization of gradient descent for optimization over geometries beyond the Euclidean geometry of gradient descent. In particular, mirror descent updates are defined for any strongly convex and differentiable potential $\psi$ as

where $D_{\psi}(w,w^{\prime})\!=\!\psi(w)-\psi(w^{\prime})-\left\langle\nabla\psi(w^{\prime}),w-w^{\prime}\right\rangle$ is the Bregman divergence (Bregman, 1967) w.r.t. $\psi$, and $\mathcal{W}$ is some constraint set for parameters $w$.

For a strongly convex potential $\psi$, $\nabla\psi$ is called the link function and is invertible. Hence, the above updates are uniquely defined. Also, $w$ and $\nabla\psi(w)$ are referred as primal and dual variables, respectively.

From eq. (5), we see that rather than the primal iterates ${w_{(t)}}$, it is the dual iterates $\nabla\psi({w_{(t)}})$ that are constrained to the low dimensional data manifold $\nabla\psi({w_{(0)}})+\text{span}(\{x_{n}\}_{n\in[N]})$. The arguments for gradient descent can now be generalized to get the following result.

In particular, if we start at ${{w_{(0)}}}=\operatorname*{\arg\!\min}_{w}\psi(w)$ (so that $\nabla\psi({{w_{(0)}}})=0$), then we get to $w_{\infty}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}\psi(w)$, where recall that $\mathcal{G}=\{w:\forall n,\left\langle w,x_{n}\right\rangle=y_{n}\}$ is the set of global minima for $\mathcal{L}(w)$.

The analysis of Theorem 1 can also be extended for special cases of constrained mirror descent (eq. (4)) when $\mathcal{L}(w)$ is minimized over realizable affine equality constraints.

For example, in exponentiated gradient descent (Kivinen and Warmuth, 1997), which is mirror descent w.r.t $\psi(w)=\sum_{i}w[i]\log{w[i]}-w[i]$, under the explicit simplex constraint $\mathcal{W}=\{w:\sum_{i}w[i]=1\}$, Theorem 1a shows that using uniform initialization ${{w_{(0)}}}=\frac{1}{d}\mathbf{1}$, mirror descent will return the the maximum entropy solution ${w_{\infty}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}\cap\mathcal{W}}\sum_{i}w[i]\log{w[i]}}$.

Let us now consider momentum for mirror descent. There are two possible generalizations of the gradient descent momentum in eq. (3): adding momentum either to primal variables ${w_{(t)}}$, or to dual variables $\nabla\psi({w_{(t)}})$,

where $\Delta z_{(-1)}=\Delta w_{(-1)}=0$, and for $t\geq 1$, $\Delta z_{(t-1)}=\nabla\psi({w_{(t)}})-\nabla\psi({w_{(t-1)}})$ and $\Delta w_{(t-1)}={w_{(t)}}-{w_{(t-1)}}$ are the momentum terms in the primal and dual space, respectively; and $\{\beta_{t}\geq 0,\gamma_{t}\geq 0\}_{t}$ are the momentum parameters.

If we initialize at ${{w_{(0)}}}=\operatorname*{\arg\!\min}_{w}\psi(w)$, then even with dual momentum $\nabla\psi({w_{(t)}})$ continues to remain in the data manifold. This leads to the following extension of Theorem 1.

Under the conditions in Theorem 1, if initialized at ${{w_{(0)}}}=\operatorname*{\arg\!\min}_{w}\psi(w)$, then the mirror descent updates with dual momentum also converge to (6), i.e., for all $\{\eta_{t}\}_{t},\{\beta_{t}\}_{t},\{\gamma_{t}\}_{t}$, if ${w_{(t)}}$ from eq. (7) converges to $w_{\infty}\in\mathcal{G}$, then $w_{\infty}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}\psi(w)$.

Following the same arguments, we can show that Theorem 1–1b also hold when instancewise stochastic gradients defined in eq. (2) are used in place of $\nabla\mathcal{L}({w_{(t)}})$.

Let us now look at primal momentum. For general potentials $\psi$, the dual iterates $\nabla\psi({w_{(t)}})$ from the primal momentum can fall off the data manifold and the additional components influence the final solution. Thus, the specific global minimum that the iterates ${w_{(t)}}$ converge to will depend on the values of momentum parameters $\{\beta_{t},\gamma_{t}\}_{t}$ and step-sizes $\{\eta_{t}\}_{t}$ as demonstrated in the following example.

In Example 2, consider the case where primal momentum is used only in the first step, but $\gamma_{t}=0$ and $\beta_{t}=0$ for all $t\geq 2$. For any $\beta_{1}>0$, there exists $\{\eta_{t}\}_{t}$, such that ${w_{(t)}}$ from (8) converges to a global minimum, but not to $\operatorname*{\arg\!\min}_{w\in\mathcal{G}}\psi(w)$.

3 Natural gradient descent

Natural gradient descent (NGD) was introduced by Amari (1998) as a modification of gradient descent, wherein the updates are chosen to be the steepest descent direction w.r.t a Riemannian metric tensor $H$ that maps $w$ to a positive definite local metric $H(w)$. The updates are given by,

In many instances, the metric tensor $H$ is specified by the Hessian $\nabla^{2}\psi$ of a strongly convex potential $\psi$. For example, when the metric over the Riemannian manifold is the KL divergence between distributions $P_{w}$ and $P_{w^{\prime}}$ parameterized by $w$, the metric tensor is given by $H(w)=\nabla^{2}\psi(P_{w})$, where the potential $\psi$ is the entropy potential over $P_{w}$.

When $H(w)=\nabla\psi^{2}(w)$ for a strongly convex potential $\psi$, as the step-size $\eta$ goes to zero, the iterates ${w_{(t)}}$ from natural gradient descent in eq. (9) and mirror descent w.r.t $\psi$ in eq. (4) converge to each other, and the common dynamics in the limit is given by,

Thus, as the step-sizes are made infinitesimal, the limit point of natural gradient descent $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}$ is also the limit point of mirror descent and hence will be biased towards solutions with minimum divergence to the initialization, i.e., as $\eta\to 0$, $w_{\infty}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}D_{\psi}(w,{w_{(0)}})$.

For general step-sizes $\{\eta_{t}\}$, if the potential $\psi$ is quadratic, $\psi(w)=\nicefrac{{1}}{{2}}\|w\|_{D}^{2}$ for some positive definite $D$, we get linear link functions $\nabla\psi(w)=Dw$ and constant metric tensors $\nabla^{2}\psi(w)=H(w)=D$, and the natural gradient descent updates (9) are the same as the mirror descent (5). Otherwise the updates in eq. (9) is only an approximation of the mirror descent update $\nabla\psi^{-1}(\nabla\psi({w_{(t)}})-\eta_{t}\nabla\mathcal{L}({w_{(t)}}))$.

For natural gradient descent with finite step-size and non-quadratic potentials $\psi$, the characterization in eq. (6) generally does not hold. We can see this as for any initialization ${w_{(0)}}$, a finite $\eta_{1}>0$ will lead to ${w_{(1)}}$ for which the dual variable $\nabla\psi({w_{(1)}})$ is no longer in the data manifold $\text{span}(\{x_{n}\})+\nabla\psi({w_{(0)}})$, and hence will converge to a different global minimum dependent on the step-sizes $\{\eta_{t}\}_{t}$.

Consider optimizing $\mathcal{L}(w)$ with squared loss over dataset $\{(x_{1}=,y_{1}=1)\}$ using the natural gradient descent w.r.t. the metric tensor given by $H(w)=\nabla^{2}\psi(w)$, where $\psi(w)=\sum_{i}w[i]\log{w[i]}-w[i]$, and initialization ${{w_{(0)}}}=$. Figure 1(b) shows that NGD with different step-sizes $\eta$ converges to different global minima. For a simple analytical example: take one finite step $\eta_{1}>0$ and then follow the continuous time path in eq. (10).

For almost all $\eta_{1}>0$, $\lim_{t\to\infty}{w_{(t)}}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}D_{\psi}(w,{w_{(1)}})\neq\operatorname*{\arg\!\min}_{w\in\mathcal{G}}D_{\psi}(w,{w_{(0)}})$.

4 Steepest Descent

Gradient descent is also a special case of steepest descent (SD) w.r.t a generic norm $\|.\|$ (Boyd and Vandenberghe, 2004) with updates given by,

The optimality of $\Delta{w_{(t)}}$ in eq. (11) requires $-\nabla{\mathcal{L}}({w_{(t)}})\in\partial\|\Delta{w_{(t)}}\|^{2}$, which is equivalent to,

Generalizing gradient descent, we might expect the limit point $w_{\infty}$ of steepest descent w.r.t an arbitrary norm $\|.\|$ to be the solution closest to initialization in corresponding norm, $\operatorname*{\arg\!\min}_{w\in\mathcal{G}}\|w-{{w_{(0)}}}\|$. This is indeed the case for quadratic norms $\|v\|_{D}=\sqrt{v^{\top}Dv}$ when eq. 11 is equivalent to mirror descent with $\psi(w)=\nicefrac{{1}}{{2}}\|w\|_{D}^{2}$. Unfortunately, this does not hold for general norms.

where $\text{conv}(S)$ denotes the convex hull of the set $S$, and $\{e_{j}\}$ are the standard basis, i.e., when multiple partial derivatives are maximal, we can choose any convex combination of the maximizing coordinates, leading to many possible coordinate descent optimization paths.

5 Summary for losses with a unique finite root

For losses with a unique finite root, we characterized the implicit bias of generic mirror descent algorithm in terms of the potential function and initialization. This characterization extends for momentum in the dual space as well as to natural gradient descent in the limit of infinitesimal step-size. We also saw that the characterization breaks for mirror descent with primal momentum and natural gradient descent with finite step-sizes. Moreover, for steepest descent with general norms, we were unable to get a useful characterization even in the infinitesimal step size limit. In the following section, we will see that for strictly monotone losses, we can get a characterization also for steepest descent.

Strictly Monotone Losses

We look at classification models that fit the training data $\{x_{n},y_{n}\}_{n}$ with linear decision boundaries $f(x)=\left\langle w,x\right\rangle$ with decision rule given by $\widehat{y}(x)=\text{sign}(f(x))$. In many instances of the proofs, we also assume without loss of generality that $y_{n}=1$ for all $n$, since for linear models, the sign of $y_{n}$ can equivalently be absorbed into $x_{n}$.

We again look at unregularized empirical risk minimization objective of the form in eq. (1), but now with strictly monotone losses. When the training data $\{x_{n},y_{n}\}_{n}$ is not linearly separable, the empirical objective $\mathcal{L}(w)$ can have a finite global minimum. However, if the dataset is linearly separable, i.e., $\exists w:\forall n,y_{n}\left\langle w,x_{n}\right\rangle>0$, the empirical loss $\mathcal{L}(w)$ is again ill-posed, and moreover $\mathcal{L}(w)$ does not have any finite minimizer, i.e, $\mathcal{L}(w)\to 0$ only as $\|w\|\to\infty$. Thus, for any sequence $\{{w_{(t)}}\}_{t=0}^{\infty}$, if $\mathcal{L}({w_{(t)}})\to 0$, then ${w_{(t)}}$ necessarily diverges to infinity rather than converge, and hence we cannot talk about $\lim_{t\to\infty}{w_{(t)}}$. Instead, we look at the limit direction $\bar{w}_{\infty}=\lim\limits_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}$ whenever the limit exists. We refer to existence of this limit as convergence in direction. Note that, the limit direction fully specifies the decision rule of the classifier that we care about.

This characterization of the implicit bias is independent of both the step-size as well as the initialization. We already see a fundamentally difference from the implicit bias of gradient descent for losses with a unique finite root (Section 2.1) where the characterization depended on the initialization.

Can we similarly characterize the implicit bias of different algorithms establishing ${w_{(t)}}$ converges in direction and calculating $\bar{w}_{\infty}$? Can we do this even when we could not characterize the limit point $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}$ for losses with unique finite roots? As we will see in the following section, we can indeed answer these questions for steepest descent w.r.t arbitrary norms.

2 Steepest Descent

Recall that for squared loss, the limit point of steepest descent depends on the step-size, and we were unable obtain a useful characterization even for infinitesimal step-size and zero initialization. In contrast, for exponential loss, the following theorem provides a crisp characterization of the limit direction of steepest descent as a maximum margin solution, independent of step-size (as long as it is small enough) and initialization. Let $\|.\|_{\star}$ denote the dual norm of $\|.\|$.

In particular, if there is a unique maximum-$\|.\|$ margin solution $w^{\star}_{\|.\|}=\operatorname*{\arg\!\max}_{w:\|w\|\leq 1}\min_{n}{y_{n}\left\langle w,x_{n}\right\rangle}$, then the limit direction is given by $\bar{w}_{\infty}=\lim\limits_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}=w^{\star}_{\|.\|}$.

Theorem 5 is a generalization of the result of Telgarsky to steepest descent with respect to other norms, and our proof follows the same strategy as Telgarsky. We first prove a generalization of the duality result of Shalev-Shwartz and Singer (2010): if there is a unit norm linear separator that achieves margin $\gamma$, then $\norm{\nabla\mathcal{L}(w)}_{\star}\geq\gamma\mathcal{L}(w)$ for all $w$. By using this lower bound on the dual norm of the gradient, we are able to show that the loss decreases faster than the increase in the norm of the iterates, establishing convergence in a margin maximizing direction.

3 Adaptive Gradient Descent (AdaGrad)

Adaptive gradient methods, such as AdaGrad (Duchi et al., 2011) or Adam (Kingma and Adam, 2015) are very popular for neural network training. We now look at the implicit bias of the basic (diagonal) AdaGrad.

AdaGrad updates described above correspond to a pre-conditioned gradient descent, where the pre-conditioning matrix $\mathbf{G}_{(t)}$ adapts across iterations. It was observed by Wilson et al. (2017) that for neural networks with squared loss, adaptive methods tend to degrade generalization performance in comparison to non-adaptive methods (e.g., SGD with momentum), even when both methods are used to train the network until convergence to a global minimum of training loss. This suggests that adaptivity does indeed affect the implicit bias. For squared loss, by inspection the updates in eq. (13), we do not expect to get a characterization of the limit point $w_{\infty}$ that is independent of the step-sizes.

However, we might hope that, like for steepest descent, the situation might be different for strictly monotone losses, where the asymptotic behavior could potentially nullify the initial conditions. Examining the updates in eq. (13), we can see that the robustness to initialization and initial updates depend on whether the matrices $\mathbf{G}_{(t)}$ diverge or converge: if $\mathbf{G}_{(t)}$ diverges, then we expect the asymptotic effects to dominate, but if it is bounded, then the limit direction will depend on the initial conditions.

Unfortunately, the following theorem shows that, the components of $\mathbf{G}_{(t)}$ matrix are bounded, and hence even for strict monotone losses, the initial conditions ${{w_{(0)}}},\mathbf{G}_{\left(0\right)}$ and step-size $\eta$ will have a non-vanishing contribution to the asymptotic behavior of $\mathbf{G}_{(t)}$ and hence to the limit direction $\bar{w}_{\infty}=\lim\limits_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}$, whenever it exists. In other words, the implicit bias of AdaGrad does indeed depend on initialization and step-size.

Gradient descent on the factorized parameterization

Gunasekar et al. (2017) noted that, the optimization problem in eq. (16) over factorization $W\!=\!UV^{\top}\!$ can be cast as a special case of optimization over p.s.d. matrices with unconstrained symmetric factorization $W\!=\!UU^{\top}$:

Specifically, in terms of both the objective as well as gradient descent updates, a problem instance of eq. (16) is equivalent to a problem instance of eq. (17) with larger data matrices $\widetilde{X}_{n}=\left[\begin{smallmatrix}0&X_{n}\\ X_{n}^{\top}&0\end{smallmatrix}\right]$ and loss optimized over larger p.s.d. matrix of the form $\widetilde{U}\widetilde{U}^{\top}=\left[\begin{smallmatrix}A_{1}&W\\ W^{\top}&A_{2}\end{smallmatrix}\right]$, where $W=UV^{\top}$ corresponds to the optimization variables in the original problem instance of eq. (16) and $A_{1}$ and $A_{2}$ some p.s.d matrices that are irrelevant for the objective.

with corresponding updates in ${W_{(t)}}={U_{(t)}}{U_{(t)}}^{\top}$ given by,

For squared loss, Gunasekar et al. (2017) showed that the implicit bias of iterates in eq. (19) crucially depended on both the initialization ${U_{(0)}}$ as well as the step-size $\eta$. Gunasekar et al. conjectured, and provided theoretical and empirical evidence that gradient descent on the factorization converges to the minimum nuclear norm global minimum, but only if the initialization is infinitesimally close to zero and the step-sizes are infinitesimally small. Li et al. (2017), later proved the conjecture under additional assumption that the measurements $X_{n}$ satisfy certain restricted isometry property (RIP).

In the case of squared loss, it is evident that for finite step-sizes and finite initialization, the implicit bias towards the minimum nuclear norm global minima is not exact. In practice, not only do we need $\eta>0$, but we also cannot initialize very close to zero since zero is a saddle point for eq. (17). The natural question motivated by the results in Section 3 is: for strictly monotone losses, can we get a characterization of the implicit bias of gradient descent for the factorized objective in eq. (17) that is more robust to initialization and step-size?

In the following theorem, we again see that the characterization of the implicit bias of gradient descent for factorized objective is more robust in the case of strict monotone losses.

Any global minimum $U^{*}$ of eq. (20) corresponds to predictor $W^{*}$ that minimizes the nuclear norm $\|.\|_{*}$ of linear p.s.d. classifier with margin constraints,

Additionally, in the absence of rank constraints on $U$, all second order stationary points of eq. (20) are global minima for the problem. More general, we expect a stronger result that $\bar{W}_{\infty}=\bar{U}_{\infty}\bar{U}_{\infty}^{\top}$, which is also the limit direction of ${W_{(t)}}$, is a minimizer of eq. (21). Showing a stronger result that ${W_{(t)}}$ indeed converges in direction to $W^{*}$ is of interest for future work.

Here we note that convergence of ${U_{(t)}}$ in direction is necessary for the characterization of implicit bias to be relevant, but in Theorem 7, we require stronger conditions that the gradients $\nabla\mathcal{L}({W_{(t)}})$ also converge in direction. Relaxing this condition is of interest for future work.

Let us look at exponential loss when ${W_{(t)}}$ converges in direction to, say $\bar{W}_{\infty}$. Then $\bar{W}_{\infty}$ can be expressed as ${W_{(t)}}=\bar{W}_{\infty}g(t)+\rho(t)$ for some scalar $g(t)\to\infty$ and $\frac{\rho(t)}{g(t)}\to 0$. Consequently, the gradients $\nabla\mathcal{L}({W_{(t)}})=\sum_{n}\text{e}^{-g(t)y_{n}\left\langle W_{\infty},X_{n}\right\rangle}e^{-y_{n}\left\langle\rho(t),X_{n}\right\rangle}\,y_{n}X_{n}$ will asymptotically be dominated by linear combinations of examples $X_{n}$ that have the smallest distance to the decision boundary, i.e., the support vectors of $\bar{W}_{\infty}$. This behavior can be used to show optimality of $\bar{U}_{\infty}$ such that $\bar{W}_{\infty}=\bar{U}_{\infty}\bar{U}_{\infty}^{\top}$ to the first order stationary points of the maximum margin problem in eq. 20.

This idea formalized in the following lemma, which is of interest beyond the results in this paper.

For almost all linearly separable datasets $\{x_{n},y_{n}\}_{n=1}^{N}$, consider any sequence ${w_{(t)}}$ that minimizes $\mathcal{L}(w)$ in eq. (1) with exponential loss, i.e., $\mathcal{L}({w_{(t)}})\to 0$. If ${w_{(t)}}$ converges in direction to a strictly separating predictor, i.e., $\bar{w}_{\infty}=\lim\limits_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}$ exists with $\min_{n}y_{n}\left\langle\bar{w}_{\infty},x_{n}\right\rangle>0$, then for every accumulation point $z_{\infty}$ of \Big{\{}\frac{-\nabla\mathcal{L}({w_{(t)}})}{\norm{\nabla\mathcal{L}({w_{(t)}})}}\Big{\}}_{t}, $\exists\{\alpha_{n}\geq 0\}_{n\in S}\text{ s.t., }z_{\infty}=\sum\limits_{n\in S}\alpha_{n}y_{n}x_{n},$ where $S=\{n:y_{n}\left\langle\bar{w}_{\infty},x_{n}\right\rangle=\min_{n}y_{n}\left\langle\bar{w}_{\infty},x_{n}\right\rangle\}$ are the indices of the data points with smallest margin to $\bar{w}_{\infty}$.

Summary

We studied the implicit bias of different optimization algorithms for two families of losses, losses with a unique finite root and strict monotone losses, where the biases are fundamentally different. In the case of losses with a unique finite root, we have a simple characterization of the limit point $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}$ for mirror descent. But for this family of losses, such a succinct characterization does not extend to steepest descent with respect to general norms. On the other hand, for strict monotone losses, we noticed that the initial updates of the algorithm, including initialization and initial step-sizes are nullified when we analyze the asymptotic limit direction $\bar{w}_{\infty}=\lim\limits_{t\to\infty}\frac{{w_{(t)}}}{\|{w_{(t)}}\|}$. We show that for steepest descent, the limit direction is a maximum margin separator within the unit ball of the corresponding norm. We also looked at other optimization algorithms for strictly monotone losses. For matrix factorization, we again get a more robust characterization that relates the limit direction to the maximum margin separator with unit nuclear norm. This again, in contrast to squared loss Gunasekar et al. (2017), is independent of the initialization and step-size. However, for AdaGrad, we show that even for strict monotone losses, the limit direction $\bar{w}_{\infty}$ could depend on the initial conditions.

In our results, we characterize the implicit bias for linear models as minimum norm (potential) or maximum margin solutions. These are indeed very special among all the solutions that fit the training data, and in particular, their generalization performance can in turn be understood from standard analyses Bartlett and Mendelson (2003).

Going forward, for more complicated non-linear models, especially neural networks, further work is required in order to get a more complete understanding of the implicit bias. The preliminary result for matrix factorization provides us tools to attempt extensions to multi-layer linear models, and eventually to non-linear networks. Even for linear models, the question of what is the implicit bias is when $\mathcal{L}(w)$ is optimized with explicitly constraints $w\in\mathcal{W}$ is an open problem. We believe similar characterizations can be obtained when there are multiple feasible solutions with $\mathcal{L}(w)=0$. We also believe, the results for single outputs considered in this paper can also be extended for multi-output loss functions.

Finally, we would like a more fine grained analysis connecting the iterates ${w_{(t)}}$ along the optimization path of various algorithms to the regularization path, $\widehat{w}(c)=\operatorname*{\arg\!\min}_{\mathcal{R}(w)\leq c}\mathcal{L}(w)$, where an explicit regularization is added to the optimization objective. In particular, our positive characterizations show that the optimization and regularization paths meet at the limit of $t\to\infty$ and $c\to\infty$, respectively. It would be desirable to further understand the relations between the entire optimization and regularization paths, which will help us understand the non-asymptotic effects from early stopping.

Acknowledgments

The authors are grateful to M.S. Nacson, Y. Carmon, and the anonymous ICML reviewers for helpful comments on the manuscript. The research was supported in part by NSF IIS award 1302662. The work of DS was supported by the Taub Foundation.

References

A Losses with a unique finite root

For a strongly convex potential $\psi$, denote the global optimum with minimum Bregman divergence $D_{\psi}(.,{{w_{(0)}}})$ to the initialization ${{w_{(0)}}}$ as

where recall that $D_{\psi}(w,{{w_{(0)}}})=\psi(w)-\psi({{w_{(0)}}})-\left\langle\nabla\psi({{w_{(0)}}}),w-{{w_{(0)}}}\right\rangle$.

The KKT optimality conditions for (23) are as follows,

Recall Theorem 1–1b from Section 2.2. See 1 See 1a See 1b See 1

Generic mirror descent: Theorem 1 Recall the updates of mirror descent: $\nabla\psi({w_{(t+1)}})-\nabla\psi({w_{(t)}})=-\eta_{t}\nabla\mathcal{L}({w_{(t)}})$ Using telescoping sum, we have,

where the last inclusion follows as $\forall t^{\prime},-\eta_{t^{\prime}}\nabla\mathcal{L}({w_{(t^{\prime})}})\in\mathcal{P}_{\mathcal{X}}$ from (22).

Thus, for all $t$, ${w_{(t)}}$ from mirror descent updates in eq. (5) always satisfy the stationarity condition of eq. (24). Additionally, if ${w_{(t)}}$ converges to a global minimum, then $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}\in\mathcal{G}=\{w:\forall n,\left\langle w,x_{n}\right\rangle=y_{n}\}$ also satisfies the primal feasibility condition in eq. (24). Combining the above arguments, we have that if $\mathcal{L}(w_{\infty})=0$, then $w_{\infty}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}D_{\psi}(w,{{w_{(0)}}})$.

The KKT optimality conditions for (26) are as follows,

To show that the limit point of mirror descent updates in eq. (4) satisfy the above KKT conditions, we first note that the updates are equivalently computed as follows,

Let $g_{j}$ for $j=1,2,\ldots,d^{\prime}$ denote the rows of $G$. From the optimality conditions of eq. (28), we get that

Again, primal feasibility is satisfied whenever ${w_{(t)}}\to\mathcal{G}$ since mirror descent iterates are always feasible points ${w_{(t)}}\in\mathcal{W}$. The stationarity condition follows from using eq. (29) with same arguments of the unconstrained case.

Claim: If $\nabla\psi({w_{(0)}})=0$, then for all updates of the form (30) satisfies $\nabla\psi({w_{(t)}})\in\mathcal{P}_{\mathcal{X}}$ —this can be easily proved by induction: (a) for $t=0$, $\nabla\psi({w_{(0)}})=0\in\mathcal{P}_{\mathcal{X}}$; (b) let $\forall t^{\prime}\leq t$, $\nabla\psi({w_{(t^{\prime})}})\in\mathcal{P}_{\mathcal{X}}$, (c) then using the inductive assumption and eq. (22), we have $\nabla\psi({w_{(t+1)}})=\sum_{t^{\prime}\leq t}\widetilde{\beta}_{t^{\prime}}\nabla\psi({w_{(t^{\prime})}})+\widetilde{\gamma}_{t^{\prime}}\nabla\mathcal{L}(\widetilde{w}_{(t^{\prime})})\in\mathcal{P}_{\mathcal{X}}$.

A.2 Proofs of propositions in Section 2

For entropy potential $\psi(w)=\sum_{i}w[i]\log{w[i]}-w[i]$, we have $\nabla\psi(w)=\log{w}$ (where the $\log$ is taken elementwise), and initialization ${w_{(0)}}=$ satisfies $\nabla\psi({w_{(0)}})=0$ which is the optimality condition for $\min_{w}\psi(w)$.

Proof of Proposition 2a: we use primal momentum with $\beta_{1}>0$ only in the first step, and $\forall t\geq 2$, $\beta_{t}=\gamma_{t}=0$. We get the following initial updates

Since $\forall t\geq 2$, $\beta_{t}=\gamma_{t}=0$, we first note that for $t>2$, the updates merely follow the path of standard MD initialized at $\nabla\psi({w_{(2)}})$ for a convex loss function. This implies the following:

for appropriate choice of $\{\eta_{t}\}_{t\geq 2}$ (given by convergence analysis of mirror descent for convex functions), we can get $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}\in\mathcal{G}$, and

from eq. (25), $w_{\infty}$ satisfies $\nabla\psi(w_{\infty})-\nabla\psi({w_{(2)}})\in\mathcal{P}_{\mathcal{X}}\Rightarrow\nabla\psi(w_{\infty})\in\nabla\psi({w_{(2)}})+\mathcal{P}_{\mathcal{X}}$.

Since $w_{\infty}$ satisfies primal feasibility, from stationarity condition in eq. (24), we have

We show that this is not the case for any $\beta_{1}>0$ and any $\gamma_{1}\geq 0$. Recall that $\Delta{w_{(-1)}}=0$, $\nabla\psi({w_{(0)}})=0$ and $\nabla\psi(w)=\log{w}$. Working through the steps in eq. (8), for scalars $r_{0}=\eta_{0}(y_{1}-\left\langle{w_{(0)}},x_{1}\right\rangle)$ and $\widetilde{r}_{1}=\eta_{t}(y_{1}-\left\langle{w_{(1)}}+\gamma_{1}\Delta{w_{(0)}},x_{1}\right\rangle)$, and any $\beta_{1}>0$, we have:

$\nabla\psi({w_{(1)}})=r_{0}x_{1}\implies{w_{(1)}}=\exp(r_{0}x_{1})$, and

$\nabla\psi({w_{(2)}})=\nabla\psi((1+\beta_{1}){w_{(1)}})+\widetilde{r}_{1}x_{1}=\log{(1+\beta_{1})}+r_{0}x_{1}+\widetilde{r}_{1}x_{1}\in\log{(1+\beta_{1})}+\mathcal{P}_{\mathcal{X}}\notin\mathcal{P}_{\mathcal{X}}$. $\Box$

Proof of Proposition 3a: The arguments are similar to the proof of Proposition 2a. In Example 3, we again use a finite $\eta_{1}>0$ to get ${w_{(1)}}$ and then follow the NGD using infinitesimal $\eta$ initialized at ${w_{(1)}}$.

We know that for infinitesimal step-size, the NGD path starting at ${w_{(1)}}$ follows the corresponding infinitesimal MD path on a convex problem and hence from eq. (25), the NGD updates for this example converges to a global minimum $w_{\infty}=\lim_{t\to\infty}{w_{(t)}}\in\mathcal{G}$, that satisfies $\nabla\psi(w_{\infty})-\nabla\psi({w_{(1)}})\in\mathcal{P}_{\mathcal{X}}\Rightarrow\nabla\psi(w_{\infty})\in\nabla\psi({w_{(1)}})+\mathcal{P}_{\mathcal{X}}$.

From stationarity condition in (24), $w_{\infty}=w^{*}_{\psi}=\operatorname*{\arg\!\min}_{w\in\mathcal{G}}\psi(w)$ if and only if $\nabla\psi({w_{(1)}})\in\mathcal{P}_{\mathcal{X}}$.

For natural gradient descent, ${w_{(1)}}={w_{(0)}}-\eta_{1}\nabla^{2}\psi({w_{(0)}})^{-1}\nabla\mathcal{L}({w_{(0)}})=[1+\eta_{1}r_{0},1+2\eta_{1}r_{0}]$, where $r_{0}=\eta_{0}(y_{1}-\left\langle{w_{(0)}},x_{1}\right\rangle)$. We then have \nabla\psi({w_{(1)}})\in\mathcal{P}_{\mathcal{X}}\Leftrightarrow 2\nabla\psi({w_{(1)}})-\nabla\psi({w_{(1)}})=0\Leftrightarrow 2\log{({w_{(1)}})}-\log{({w_{(1)}})}=0\Leftrightarrow\log{\big{(}1+\frac{\eta_{1}^{2}r^{2}_{0}}{1+2\eta_{1}r_{0}}\big{)}}=0.

For any $\eta_{1}$ such that $\frac{\eta_{1}^{2}r^{2}_{0}}{1+2\eta_{1}r_{0}}\neq 0$, we get a contradiction. $\Box$

B Steepest descent for strictly monotone losses

We prove Theorem 5 in this section. See 5 The proof is divided into three subsections

Generalized duality lemma: we show that for all norms and all $w$, $\norm{\nabla\mathcal{L}(w)}_{\star}\geq\gamma\mathcal{L}(w)$.

Properties of $\nabla\mathcal{L}({w_{(t)}})$ and $\mathcal{L}({w_{(t)}})$ for steepest descent: we prove two lemmata that show some useful properties of $\nabla\mathcal{L}({w_{(t)}})$ and $\mathcal{L}({w_{(t)}})$.

Remaining steps in the proof: putting together above lemmata to prove Theorem 5.

The following lemma is a standard result in convex analysis.

We define the $\norm{\cdot}$- maximum margin as,

For any norm $\|.\|$, the following duality holds:

Let ${\mathbf{1}_{E}}$ denote the indicator function which takes value if $E$ is satisfied and $\infty$ otherwise.

Define $f(r)={\mathbf{1}_{r\in\Delta_{N-1}}}$ and $g(z)=\norm{z}_{\star}$, so that

The conjugates are $f^{*}(y)=\max_{r\in\Delta_{N-1}}\left\langle y,r\right\rangle=\max_{n=1}^{N}\left\langle y,e_{n}\right\rangle$, and $g^{*}(w)={\mathbf{1}_{\norm{w}\leq 1}}$. The LHS of Lemma 9 is

where $(a)$ follows from central symmetry of $\{w:\|w\|\leq 1\}$, and $(b)$ from definition of maximum $\|.\|$-margin in eq. (32).

Using weak duality (Lemma 9) on eqs. (35) and (36), we have $\forall r,\;{\|X^{\top}r\|_{\star}}\geq\gamma{\|r\|_{1}}$. Finally, recalling that for exponential loss $r_{n}(w)=\exp(-w^{\top}x_{n})$, $\mathcal{L}(w)=\norm{r(w)}_{1}$ and $\nabla\mathcal{L}(w)=X^{\top}r(w)$, we have $\forall w$, $\norm{\nabla\mathcal{L}(w)}_{\star}\geq\gamma\mathcal{L}(w).$ ∎

Recall the steepest descent updates in eqs. (11) and (12) :

$\sum_{t=0}^{\infty}\eta_{t}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}^{2}\leq\infty$, and hence $\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}\to 0$.

Iterates ${w_{(t)}}$ converge to a global minima $\mathcal{L}({w_{(t)}})\to 0$, and hence $\forall n$ $\left\langle{w_{(t)}},x_{n}\right\rangle\to\infty$.

$\sum_{t=0}^{\infty}\eta_{t}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}=\infty.$

Proof of $(A)$: We have that $\norm{x_{n}}_{\star}\leq B$ for all $n$. Recall that $r_{n}(w)=\exp(-\left\langle w,x_{n}\right\rangle)\geq 0$, $\mathcal{L}(w)=\sum_{n}r_{n}(w)$, and $\nabla\mathcal{L}(w)=\sum_{n}r_{n}(w)x_{n}$. Thus, for all $v$, we have

Using Taylor’s reminder theorem for the convex loss $\mathcal{L}$, we have

where $(a)$ follows from eq. (38) and from the condition on update direction in eq. (37); $(b)$ follows as $\eta_{t}\Delta{w_{(t)}}$ is a descent step and along with convexity of $\mathcal{L}(w)$ we have $\sup_{\beta\in(0,1)}\mathcal{L}\left({w_{(t)}}+\beta\eta_{t}\Delta{w_{(t)}}\right)\leq\mathcal{L}({w_{(t)}})$; and $(c)$ follows as $\eta_{t}\leq\frac{1}{B^{2}\mathcal{L}({w_{(t)}})}$ from the assumption and also using $\|\Delta{w_{(t)}}\|=\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}$ from eq. 37.

Thus, ${\mathcal{L}({w_{(t)}})-\mathcal{L}({w_{(t+1)}})}\geq\frac{\eta_{t}}{2}\left\|\nabla\mathcal{L}({w_{(t)}})\right\|^{2}_{\star}$, which implies

where the final inequality follows as $\mathcal{L}({w_{(0)}})<\infty$ and $\mathcal{L}({w_{(t)}})\geq 0$ $\forall t$.

In the continuous time limit of $\eta\to 0$, $(A)$ is equivalently expressed as $\int_{0}^{t}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}^{2}<\infty$. Thus, we have $\lim_{t\to\infty}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}=0$—both for any finite $\eta_{t}>0$ as well as in the continuous time limit of $\eta\to 0$.

Since $\lim_{t\to\infty}v^{\top}\nabla\mathcal{L}({w_{(t)}})=0$, it must be that $\forall n,\;\exp(-\left\langle{w_{(t)}},x_{n}\right\rangle)\to 0$, and thus $\norm{{w_{(t)}}}\to\infty.$

where we used $\|\Delta{w_{(t)}}\|=\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}$ from (37). This gives us $\sum_{t=0}^{\infty}\eta_{t}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}=\infty$ in $(C)$.∎

We next show that under the conditions of Theorem 5, $\mathcal{L}(w_{(t)})$ forms a decreasing sequence, and hence satisfies the assumption in Lemma 11.

If step-sizes $\eta_{t}$ satisfy $\eta_{t}=\frac{c_{t}}{B^{2}\mathcal{L}(w_{t})}$ for $c_{t}\leq\sqrt{2}$ , then $\mathcal{L}(w_{(t+1)})\leq\mathcal{L}(w_{(t)})$.

From the Taylor expansion of $\mathcal{L}\left(w\right)$ in eq. (39), we have

where $(a)$ follows from convexity of $\mathcal{L}$.

We want to show that $\mathcal{L}(w_{(t+1)})\leq\mathcal{L}(w_{(t)})$. Let us assume the contrary that $\mathcal{L}(w_{(t+1)})>\mathcal{L}(w_{(t)})$.

where $(a)$ follows from the contradictory assumption and $(b)$ follows as $\eta_{t}\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}^{2}\geq 0$.

where in $(a)$ we used $\norm{\nabla\mathcal{L}(w_{t})}_{\star}=\norm{\sum_{n}\exp(w_{t}^{T}x_{n})x_{n}}_{\star}\leq B\mathcal{L}(w_{t})$ from triangle inequality and $\left(\frac{\eta_{t}B^{2}\mathcal{L}(w_{t+1})}{2}-1\right)\geq 0$ from eq. (43), $(b)$ follows from using $\eta_{t}\leq\frac{c_{t}}{B^{2}\mathcal{L}(w_{t})}$ for some $0<c_{t}\leq\sqrt{2}$, and $(c)$ follows as for $0<c_{t}\leq\sqrt{2}$, $\frac{1-c_{t}}{1-0.5c_{t}^{2}}\leq 1$. This shows $\mathcal{L}(w_{t+1})\leq\mathcal{L}(w_{t})$ which is a contradiction. ∎

B.3 Remaining steps in the proof of Theorem 5

The steepest descent updates in eq. (37) can be equivalently written as:

From eq . 39, using $\gamma_{t}=\|\nabla\mathcal{L}({w_{(t)}})\|_{\star}=\|\Delta{w_{(t)}}\|$, we have that

where we get $(a)$ by using $(1+x)\leq\exp(x)$, and $(b)$ using recursion.

Step 1: Lower bound the unnormalized margin: From eq. (45), we have,

Step 2: Upper bound $\boldsymbol{\norm{w_{(t+1)}}}$: Using $\|\Delta{w_{(u)}}\|=\|\nabla\mathcal{L}({w_{(u)}})\|_{\star}=\gamma_{u}$, we have,

Step 3: Lower bound on normalized margin: Combining eqs. (47) and (48)$\forall n\in[N]$, we have that

From the duality Lemma 10, we have $\gamma_{u}=\|\nabla\mathcal{L}({w_{(u)}})\|_{\star}\geq\gamma\mathcal{L}({w_{(u)}})$. Hence, $\sum_{u\leq t}\frac{\eta_{u}\gamma_{u}^{2}}{\mathcal{L}({w_{(u)}})}\geq\gamma\sum_{u\leq t}\eta_{u}\gamma_{u}$ and further using $\sum_{u\leq t}\eta_{u}\gamma_{u}\to\infty$ from Lemma 11, we have

For any bounded $\eta\leq\eta_{+}$, ${\sum_{u\leq t}\frac{\eta_{u}^{2}B^{2}\gamma_{u}^{2}}{2}}\leq\frac{\eta_{+}B^{2}}{2}\sum_{u\leq t}\eta_{u}\gamma_{u}^{2}<\infty$ (from Lemma 11). Along with using $\|{w_{(t)}}\|\to\infty$ from Lemma 11, we get $\frac{\sum_{u\leq t}\frac{\eta_{u}^{2}B^{2}\gamma_{u}^{2}}{2}+\log\mathcal{L}({w_{(0)}})}{\|{w_{(t+1)}}\|}\to 0$.

Using the above bounds in (50), we get $\lim_{t\to\infty}\frac{w_{(t+1)}^{\top}x_{n}}{\norm{w_{(t+1)}}}\geq\gamma:=\max_{w}\frac{w^{\top}x_{n}}{\norm{w}}$ $\Box$

C Adagrad

Let $\mathcal{L}\left(w\right)=\sum_{n=1}^{N}\exp\left(-w^{\top}x_{n}\right)$, $\left\|\cdot\right\|_{t}$ be some $w_{\left(t\right)}$-dependent norm, and $\left\|\cdot\right\|_{t,*}$ be its dual, and assume that and $\forall t:\,\left\|x_{n}\right\|_{t,*}\leq 1$. We examine the following adaptive steepest descent update sequence w.r.t adaptive norm $\left\|\cdot\right\|_{t}$:

where $\left\|\nabla\mathcal{L}\left(w_{\left(t\right)}\right)\right\|_{t,*}\triangleq\gamma_{t}$ and $p_{\left(t\right)}$ is the normalized update satisfying $\left\|p_{\left(t\right)}\right\|_{t}=1$ and $p_{\left(t\right)}^{\top}\nabla\mathcal{L}\left(w_{\left(t\right)}\right)=\left\|\nabla\mathcal{L}\left(w_{\left(t\right)}\right)\right\|_{t,*}$.

For these adaptive steepest descent updates, for any initialization, ${{w_{(0)}}}$ such that $\eta\mathcal{L}\left({{w_{(0)}}}\right)<1$, if ${w_{(t)}}$ minimizes $\mathcal{L}$, i.e., $\mathcal{L}({w_{(t)}})\to 0$, then we have $\sum_{u=0}^{\infty}\gamma_{t}^{2}<\infty$.

First we note that since $\left\|x_{n}\right\|_{t,*}\leq 1$ and $\left\|p_{\left(t\right)}\right\|_{t}=1$.

Additionally, following the arguments of Lemma 12, we can show that $-\eta\gamma_{t}p_{\left(t\right)}$ for $\eta\leq\frac{1}{\mathcal{L}({w_{(0)}})}$ is a descent direction, hence from convexity of $\mathcal{L}$, we have

From the Taylor expansion of $\mathcal{L}\left(w\right)$

Substituting eq. (52) and (53) into eq. 54, we find

where $(a)$ follows from assumption that $\eta\leq\frac{1}{\mathcal{L}({w_{(0)}})}\leq\frac{1}{\mathcal{L}({w_{(t)}})}$.

Summing over the last equation, we get that $\frac{\eta}{2}\sum_{u=1}^{t}\gamma_{u}^{2}\leq\mathcal{L}\left(w_{\left(0\right)}\right)-\mathcal{L}\left(w_{\left(t\right)}\right)<\infty.$ ∎

Recall the AdaGrad update $w_{\left(t+1\right)}=w_{\left(t\right)}-\eta\mathbf{G}_{\left(t\right)}^{-1/2}\nabla\mathcal{L}\left(w_{\left(t\right)}\right)$, where $\mathbf{G}_{\left(t\right)}$ is a diagonal matrix such that

We now prove the Theorem 6. Recall the statement, See 6

First, we note that AdaGrad is a special case of the adaptive steepest descent algorithm described in Lemma 13 with respect the norm $\left\|v\right\|_{t}=\left\|\mathbf{G}_{\left(t\right)}^{1/2}v\right\|_{2}$. Here the dual norm $\left\|v\right\|_{t,*}=\left\|\mathbf{G}_{\left(t\right)}^{-1/2}v\right\|_{2}$.

Also from the definition of $\mathbf{G}_{\left(t\right)}$, we have that $\mathbf{G}_{\left(t\right)}^{-1}[i,i]$ is monotonically decreasing for all $t$, and thus $\left\|\mathbf{G}_{\left(t\right)}^{-1/2}x_{n}\right\|_{2}\leq\left\|\mathbf{G}_{\left(0\right)}^{-1/2}x_{n}\right\|_{2}\leq 1$, and so we can apply Lemma 13. This implies that

D Gradient descent on factorized parameterization

Here for almost all $\{x_{n},y_{n}\}$ means that with probability $1$ over the dataset $\{x_{n},y_{n}\}$ such that the signed features $y_{n}x_{n}$ are drawn independently from a distribution that is absolutely continuous w.r.t the $d$ dimensional Lebesgue measure.

Without loss of generality assume $\forall n,y_{n}=1$, else the sign of $y$ can be absorbed into $x$ as $x_{n}\leftarrow y_{n}x_{n}$.

We have that $\lim_{t\to\infty}\mathcal{L}({w_{(t)}})=0$ for strictly monotone loss over separable data, this implies asymptotically ${w_{(t)}}$ satisfies $X{w_{(t)}}>0,\|{w_{(t)}}\|\to\infty$.

Denote the asymptotic margin of $x_{n}$ as $\bar{\gamma}_{n}:=\left\langle x_{n},\bar{w}_{\infty}\right\rangle$. Additionally, we define the following:

Let $S:=\{n:\left\langle x_{n},\bar{w}_{\infty}\right\rangle=\gamma\}$ denote the indices of support vectors of $\bar{w}_{\infty}$.