Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study

Introduction

One of the great mysteries of contemporary machine learning is the impressive success of unregularized and overparameterized learning algorithms. In detail, current machine learning practice is to train models with far more parameters than samples and let the algorithm fit the data, oftentimes without any type of regularization. In fact, these algorithms are so overcapacitated that they can even memorize and fit random data. Yet, when trained on real-life data, these algorithms show remarkable performance in generalizing to unseen samples (Neyshabur et al. 2015; Zhang et al. 2017).

This phenomenon is often attributed to what is described as the implicit-regularization of an algorithm (Neyshabur et al. 2015). Implicit regularization roughly refers to the learner’s preference to implicitly choosing certain structured solutions as if some explicit regularization term appeared in its objective. As a canonical example, in linear optimization one can show that various forms of gradient descent, an apriori unregularized algorithm, behaves identically as regularized risk minimization penalized with the squared Euclidean norm on the parameters (Shalev-Shwartz et al. 2011).

Understanding implicit regularization poses several interesting challenges. For example: how can we find the implicit bias of a given learning algorithm? what is the rate of convergence towards the biased solution? how (and if) does it govern the generalization of an algorithm? and, when and what types of regularizations can account for and explain the generalization in modern-days machine learning?

Towards answering these questions we revisit a fundamental setting that was extensively studied in recent years: Stochastic Convex Optimization (SCO), focusing on the SGD optimization algorithm. In contrast to most previous work, we do not attempt to identify the implicit bias in specific problems. Instead, we study these questions in the general case, and we construct examples which rule out the existence of potential regularizers in general. To some extent, these constructions demonstrate a behavior that might seem counter-intuitive or contradictory to the implicit-bias point of view.

Besides being a well-studied and well-understood model for learning, an important trait of SCO which makes it suitable for our investigation is that learning cannot in general be performed by naive Empirical Risk Minimization (ERM). In detail, the work of Shalev-Shwartz et al. 2009 showed the existence of SCO instances where naive-ERM fails but regularized-ERM succeeds. Thus, we view SCO as a natural test-bed for exploring the role of regularization and its relation to generalization. Compellingly, the generalization of SGD in SCO is well-established, and we are left with the question of how well can we account for generalization through an investigation of its bias.

We begin with a simple construction which demonstrates that SGD does not have any distribution-independent implicit bias. To show that, we construct a case where SGD does not converge to a Pareto-efficient (not even approximately) solution with respect to the empirical loss and a given regularization penalty. In fact, this result is also true for Gradient Descent over smooth functions. In other words, our construction here involves a distribution supported on a single smooth convex function.

Our result is general and rules out any (reasonable) regularizer from being the implicit bias of SGD in this distribution-independent setting. Since the Euclidean-norm distance is the immediate suspect for the implicit regularization of SGD, the first step towards achieving the result is to rule out that Euclidean norm is the implicit bias of SGD. We thus construct an example of a function with a plateau of minimizers where SGD does not converge to the closest point in Euclidean-norm sense. While the result might not seem surprising, it is the technical engine behind the further constructions we provide. Previous to this work, Suggala et al. 2018 showed that gradient descent with an infinitely small step size (that is, gradient flow), might diverge from the closest point, and we provide a complementary construction combined with a full rigorous analysis for fixed step-size gradient descent.

Having ruled out the possibility of a problem-independent regularizer, we proceed to study the more compelling distribution-dependent implicit regularization. The question here is whether for every distribution over convex functions, we can associate a regularizer $r$ such that SGD tries to (approximately) find a Pareto-efficient solution with respect to $r$ and the empirical loss (notice that we allow the regularizer to depend on the distribution, but not on the specific sample received by SGD.)

We first show that we can rule out the effect of strongly-convex regularizers in the relevant regime of learning (where the dimension and the number of training examples are of roughly the same order). In fact, we rule out a more general class of regularizers that have large range on sets with large diameters. Namely, in any ball with large diameter the regularizer shows preference towards a certain point.

We then continue and demonstrate a distribution where, given an input sample, there is a very large set of possible solutions that share the same empirical loss and the same regularization penalty, and yet, SGD chooses its solution arbitrarily within this set. Here, by “very large” we mean from a learning-theoretical point of view; namely, this set is large enough so that, in general, empirical risk minimization restricted to the set will fail (and yet, it appears that this is exactly what SGD does). In other words, no regularizer $r$ is sufficient for narrowing down the set of possible SGD solutions to the point where non-trivial generalization can be deduced without appealing to other properties of the specific problem.

Several of our constructions are given in high dimension, namely the number of parameters is larger than the number of examples. One could argue that this is the interesting regime, nevertheless it is still worthy to understand the role of implicit bias when the dimension of the problem is smaller than number of examples. Here we cannot rule out the role of implicit bias in a similar fashion to before - namely, due to uniform convergence, any algorithm that is constrained to the unit ball will generalize and this implicit bias is indeed the explanation to that. It is interesting though to understand the existence of specific regularizers (such as, e.g., strongly convex regularizers).

While we do not provide an answer to this question, we make an intermediate step. Our final construction is in a slightly relaxed model, where the instances are non-convex, but the expected loss function is convex. While this result may be limited, because of the non-convexity, we stress that the learning guarantees of SGD are completely applicable to this setting: namely, SGD does learn the problem (as it is convex in expectation). We show that for any strictly quasi-convex regularizer, namely a regularizer that has preference for a single point in any convex regime, the algorithm will not converge to the optimal solution with optimal regularization penalty (even though it converges to a convex domain where seemingly it can improve its parameter choice towards the regularized solution).

2 Related work

Understanding the implicit bias of learning algorithms and its importance in generalization is a central theme in machine learning, and in the study of many classical algorithms (Bühlmann and Yu 2003; Schapire et al. 1998; Wei et al. 2017). Recently, implicit bias has received considerable attention in the past few years. Starting with Neyshabur et al. 2015; Zhang et al. 2017, it was suggested that implicit regularization might explain the success of networks to improve test error by increasing network size beyond what is needed to achieve zero training error. Subsequently, a line of work has focused on identifying implicit regularization in various problems and domains, e.g., linear and non parametric regression (Ali et al. 2019; Raskutti et al. 2014; Wei et al. 2017) matrix factorization (Gunasekar et al. 2017; Arora et al. 2019), linearly separable data (Soudry et al. 2018; Gunasekar et al. 2018b), as well as deep networks (Neyshabur 2017; Neyshabur et al. 2017) and others (Nacson et al. 2019; Nakajima and Sugiyama 2010; Lin et al. 2016; Gunasekar et al. 2018a). Our work here can be seen as an attempt to investigate the limitations of implicit regularization. Most similarly to this work, Suggala et al. 2018 provides an example of a problem where gradient flow does not converge to closest Euclidean solution. Here we focus on the more concrete SGD algorithm with a fixed step size, and give finite-time analysis. We are also able to harness our example to construct further new constructions that rule out a richer class of implicit-type regularization schemes.

This work can also be seen as an attempt towards separation between learnability and regularization. Besides regularization, several other useful notions have been suggested as surrogates of learnability. Most classically, uniform convergence (Blumer et al. 1989) has been shown to be equivalent to learnability in the binary, distribution-independent model of PAC learning (Valiant 1984). As discussed, Shalev-Shwartz et al. 2009 showed that in the stochastic convex setting naive-ERM fails (but not regularized-ERM), hence learnability and uniform convergence are no longer equivalent. The constructions of Shalev-Shwartz et al. 2009 were later substantially strengthened by Feldman 2016. More recently, Nagarajan and Kolter 2019 also provided an example that rules out uniform convergence, perhaps in the strictest sense. Their construction, though, does exhibit tangible implicit regularization, which account to the generalization of the algorithm.

Another useful notion is the stability of a learning algorithm. Stability is very much related to regularization: e.g., regularizing empirical risk minimization with a strongly convex function induces stability (Bousquet and Elisseeff 2002), and smoothness can also be harnessed to argue for stability (Hardt et al. 2016). As such, constructing a convex problem where an algorithm is unstable could also serve as a means to rule out certain types of implicit regularizers. Our examples are in fact stable, and as such, could also be interpreted as a certain weak separation between stability and regularization.

Preliminaries

The goal of the learner, given a sample $S=\{z_{1},\ldots,z_{T}\}$ of $T$ i.i.d. examples from the distribution $D$, is to return a parameter vector $\mathbf{w}_{S}$ such that

for a desired target accuracy $\epsilon>0$. (The sample size $T$ may be determined based on $\epsilon$.)

We make the following assumptions throughout. We will generally assume that the functions $f$ are also $O(1)$-Lipschitz. Specifically, in all our constructions we will have $\|\nabla_{\mathbf{w}}f(w,z)\|\leq 23$ for all values of $z$ and $\mathbf{w}\in\mathcal{W}$. We will mostly be concerned with the case that $\mathcal{W}$ is a bounded unit ball of radius $r$ around $0$. For concreteness we will mostly take $r=5$. This is just for convenience and clearly our results apply to any constant radius ball. Since our main focus in this paper is on impossibility results, fixing the Lipschitz constant and the diameter does not harm the generality of the setup.

We will also discuss strongly-convex functions (or regularizers): we say that a convex function is $\lambda$-strongly convex if for any $\mathbf{w}_{1},\mathbf{w}_{2}\in\mathcal{W}$ we have: $f(\mathbf{w}_{1})\geq f(\mathbf{w}_{2})+\nabla f(\mathbf{w}_{2})^{\top}(\mathbf{w}_{1}-\mathbf{w}_{2})+\lambda\|\mathbf{w}_{1}-\mathbf{w}_{2}\|^{2}$.

2 Gradient Descent and Stochastic Gradient Descent

The main focus of this paper is the well-known Stochastic Gradient Descent (SGD) algorithm. Given a sample $S=\{z_{1},\ldots,z_{T}\}$ and a step-size parameter $\eta>0$, SGD initializes at $\textbf{w}^{(1)}=\textbf{0}$ and performs iterations:

where $\Pi_{W}(w)$ is defined to be the projection of $w$ over the convex set $W$. The standard SGD analysis guarantees the following (see, e.g., Shalev-Shwartz and Ben-David 2014):

Let $B,\rho>0$. Le $\mathcal{W}=\{w:\|w\|\leq B\}$, and assume that $F(\cdot)$ is convex and $\|\nabla f(w,z)\|\leq\rho$ for all $z$ and $w\in W$. Suppose that SGD is run for $T$ iterations on the sample $S=\{z_{1},\ldots,z_{T}\}$ with step size $\eta=\sqrt{B^{2}/(\rho^{2}T)}$. Then,

where here $\mathbf{w}^{\star}\in\arg\min_{\mathbf{w}:\|\mathbf{w}\|\leq B}F(\mathbf{w})$.

We will also discuss in this paper the procedure of Gradient Descent (GD). Given an objective function $F$ GD obtains the following update steps:

In our context, given a sample $S=\{z_{1},\ldots,z_{T}\}$, the gradient descent algorithm takes steps using the full gradient with respect to the empirical loss defined as follows $F_{S}(\mathbf{w})=\frac{1}{T}\sum_{t=1}^{T}f(\mathbf{w},z_{t})$. We will then write in shorthand $\mathbf{w}_{S}$ for $\mathbf{w}_{F_{S}}$

While the above version of SGD is perhaps the most standard one, there are other variants that can be considered. For example, it is common to consider, instead of a fixed step-size, a decaying step-size (where $\eta$ may depend on $t$), as well as taking the last SGD iterate rather than the average iterate. We focus on the version in Eq. 2 for several reasons. First, taking the last iterate is not always justified and attains suboptimal rates (see Shamir and Zhang 2013). Second, the algorithm in Eq. 2 is also the more challenging variant to argue about, in the sense that averaging and taking small fixed step size induces bias towards initialization, and as such, is more strongly regularized (and indeed, the constructions we provide here can be readily modified to address a decaying step-size or the last iterate. In fact, the proofs will be significantly simpler; for example, in the proof overview we actually consider the last iterate for simplicity.) Another variant to consider is unprojected gradient descent. Convergence bounds can be derived for this variant that depend on the norm of the benchmark solution (Shalev-Shwartz and Ben-David 2014; Shalev-Shwartz et al. 2011). Again, we note that in all of our constructions we pick domain large enough so that projections in fact don’t take place.

Nevertheless, it could be an interesting future work to derive a natural variant of SGD whose implicit regularization properties induce the desired generalization guarantees.

3 Regularized (Structural) Risk Minimization

Another well studied approach to perform learning is through regularization, Regularized Empirical Risk Minimization (ERM) solves the following minimization problem:

Regularization

We next discuss the different classes of regularizers we will consider in this paper. While some of the results we provide make little to no assumptions on the regularizers, sometimes we would like to add further structure and rule out specific classes as the implicit bias of SGD, in other cases we would like to formally explain in what sense we might assume that the regularizer does not allow a comprehensive explanation of the implicit bias.

Most generally, a regularizer is any function $r:\mathcal{W}\to\real_{+}$. We will however make the following basic assumptions on the regularizers, to avoid degenerate cases:

$\min_{\mathbf{w}\in\mathcal{W}}r(\mathbf{w})=0$

$r$ is non-constant at $\mathcal{W}\backslash\{0\}$;

$r$ is upper semi-continuous; namely, for every point $\mathbf{w}\in\mathcal{W}$ and every $\epsilon_{0}>0$ there exists a neighborhood $B_{\delta_{0}}(\mathbf{w})=\{\mathbf{u}:\|\mathbf{w}-\mathbf{u}\|<\delta_{0}\}$ for which $r(\mathbf{u})>r(\mathbf{w})-\epsilon_{0}$ if $\mathbf{u}\in B_{\delta_{0}}(\mathbf{w})$.

Any regularizer that satisfies these properties will be said to be an admissible regularizer (or shortly, a regularizer). The first assumption above is only for normalization. For the second assumption, the algorithms we will consider are all initialized at zero and may prefer the zero solution if it is a minimizer of the empirical error. But we are mostly concerned with the implicit bias in more involved cases then that.

The last assumption is perhaps somewhat strongest, but it is intended to rule out pathological examples. For example, one could consider a regularizer $r$ which is $0$ on almost all points, but is $1$ on the negligible, dense, set of real numbers that SGD would never reach. One could argue that $r$ is an implicit bias of SGD. However, this does not capture our intuition of a regularizer. Thus, we add an assumption that a point penalized by the regularizer should also be penalized under small perturbations.

While some of the results we will present are given for general (admissible) regularizers, it is natural and expected to study more structured classes of regularizers and ask if they induce the generalization properties of a certain algorithm. One natural family of such regularizers is the class of $\lambda$-strongly-convex functions, which we will also assume are $1$-Lipschitz. As discussed in length, many of the prominent generalization results are provided in the context of strongly convex regularizers (Bousquet and Elisseeff 2002; Shalev-Shwartz et al. 2009).

Strongly-convex regularizers come with a very natural property which allows us to rule out such regularizers on certain problems: a strongly convex function always attains a unique minimizer on any convex set. As such we can always identify if the output of an algorithm minimizes (approximately) the strongly-convex regularizer, by comparing the output to the minimizer of the regularizer over the given empirical risk.

2 General (Admissible) Regularizers

Studying implicit bias that does not stem from a strongly convex regularizer is no less important; however, it becomes much more subtle to rule out the latter. Once the regularizer is allowed to have non-unique minima we should be more careful in stating what we mean when we say it does not explain generalization. In fact, almost any plausible algorithm can be said to be implicitly biased on any given distribution. For example, the fact that the regularizer is constrained to the unit ball is a form of algorithmic bias—but as was shown by Shalev-Shwartz et al. 2009, it cannot explain generalization in the SCO setting.

Towards clarifying what we mean by “explain generalization”, let us consider the following: given a regularizer $r$ and an algorithm $\mathcal{A}$ that outputs a solution $\mathcal{A}(S)$ on a sample $S$, define the set of “competitive” solutions

For shorthand, we will also use the notation $K_{S,r}(\mathcal{A})$ instead of $K_{S,r}(\mathcal{A}(S))$.

In words, $K_{S,r}(\mathcal{A})$ is the set of solutions that are comparable with (or better than) the output of $\mathcal{A}$, with respect to both the empirical loss and the regularization penalty. For example, consider a regularized ERM, as in Eq. 5, then $K_{S,r}(\mathcal{A})$ depicts all minimizers of Eq. 5 with comparable regularization penalty. For example, with a strongly-convex regularizer $r$ one can observe that the set $K_{S,r}(\mathcal{A})$ is in fact a set of a single unique solution.

More generally, if a regularizer $r$ is said to be the implicit bias of an algorithm $\mathcal{A}$, and as such it explains the generalization of the algorithm, it is expected that the set $K_{S,r}(\mathcal{A})$ would be “small” in the sense that choosing an arbitrary solution from it should provide principled guarantees. If we cannot attain such guarantees without further investigation of the problem and algorithm, we argue that the regularizer does not provide a comprehensive explanation of generalization. This motivates the following definition for studying more general regularizers than, say, strongly convex ones:

Note that the statistical complexity of the set $K$ is measured with respect to an arbitrary distribution $D$ over convex functions: this captures our requirement that the set $K_{S,r}(\mathcal{A})$ should explain generalization, without further investigation of the problem. In other words, it could be that for a correct choice of a regularizer, on a specific problem, all the models in $K_{S,r}(\mathcal{A})$ will generalize. However, what we want is to ensure that the generalization does not stem from any further structure in the problem that is not captured by the regularizer. Thus, we require that this set will be “simple” in the sense that on any arbitrary distribution over convex functions we can choose an arbitrary solution that minimizes the empirical risk.

Results

We start with the natural question, whether there is some distribution independent implicit regularization being promoted by SGD. As a warm-up we begin by ruling out the existence of a distribution-independent strongly convex regularizer that plays the role of the implicit bias of SGD. This family of regularizers is already very interesting, and has been studied extensively in the literature of stochastic convex optimization (Bousquet and Elisseeff 2002; Shalev-Shwartz et al. 2009).

Let $\mathcal{W}=\{\mathbf{w}:\|\mathbf{w}\|\leq 5\}$. For every $1$-Lipschitz and $\lambda$-strongly convex $r$, there is a distribution $D_{r}$ over $1$-Lipschitz and $1$-smooth functions over $\mathcal{W}$, and $\mathbf{w}_{r}\in\mathcal{W}$ such that, with probability $1$, SGD with any step size $1/T^{2}<\eta<1$ over an input sample $S$ of size $T=\Omega(1/(\lambda\eta))$ outputs $\mathbf{w}_{S}$ such that:

In words, for any strongly convex regularizer there exists an instance problem where SGD chooses a solution that is sub-optimal in terms of both empirical error, and regularization penalty.

The last result can be extended to general (admissible) regularizers. Here, the rate of divergence from a Pareto optimal solution depends on the structure of the regularizer $r$. This dependence of the divergence-rate on the regularizer $r$ is unavoidable. Indeed if we consider a regularizer $r$ such that $r\approx 0$, it is not hard to be convinced that it would take SGD longer to become $r$-suboptimal.

Let $\mathcal{W}=\{\mathbf{w}:\|\mathbf{w}\|\leq 5\}$. For every admissible regularizer $r$, there are constants $c_{r}>0$, a distribution $D_{r}$ (over $1$-Lipschitz and $1$-smooth convex functions), and $\mathbf{w}_{r}\in\mathcal{W}$ such that, with probability $1$ over the input sample $S$, SGD with any step size $1/T^{2}<\eta<1$ and sample size $T_{r}=\Omega_{r}(1/\eta)$ outputs $\mathbf{w}_{S}$ such that:

The $\Omega_{r}(\cdot)$ notation hides constant that may depend on the regularizer $r$. The dependence on the regularizer is expected here, as we would need a very strong level of accuracy if we want to rule out a nearly-constant regularizer, for example.

2 Distribution-Dependent Implicit Regularization

Having ruled out a class of implicit regularizers in the distribution-independent model, we next move on to discuss the possibility of distribution dependent regularizers.

For every $T\geq 1$, a constant $C>2$ and dimension $d>T/10$: there exists a distribution $D$ over $1$-Lipschitz convex functions over $\mathcal{W}=\{\mathbf{w}:\|\mathbf{w}\|\leq 1\}\subseteq\real^{d}$, such that if we run SGD with learning rate $1/T^{2}<\eta\leq C/\sqrt{T}$ over a sample set of size $T$, then for any $1$-Lipschitz, $\lambda$-strongly convex regularizer $r$, with probability $0.1$ over the sample, SGD outputs $\mathbf{w}_{S}$ for which there is $\mathbf{w}^{\star}\in\mathcal{W}$, such that

Utilizing a construction of a statistically complex set due to Feldman 2016, we can also obtain the following result:

For every $T\geq 1$, a constant $C>2$ and dimension $d\geq T/10^{5}$: there exists a distribution $D$ over convex $1$-Lipschitz functions over $\mathcal{W}=\{\mathbf{w}:\|\mathbf{w}\|\leq 1\}\subseteq\real^{d}$, such that if we run SGD with stepsize $1/T^{2}<\eta\leq C/\sqrt{T}$ over a sample set of size $T$, then for any regularizer $r$ we have that with probability at least $1/10$ over the sample, the set $K_{S,r}(\mathbf{w}_{S})$ is $\left(2T,10^{-5}\frac{T\eta^{2}}{C}\right)$-statistically complex.

In words, Theorem 4 asserts that for a certain given distribution $D$ the output of SGD cannot be interpreted as coming from a “small” structured family of solutions that would generalize regardless of other specialized properties of the particular learning problem.

The requirement that $T\leq O(d)$ is tight. Note that for a sample $S$ of order $T=O(d/\epsilon^{2})$, by a standard covering argument, we can show that the set $K_{S,r}(\mathcal{W})$ is not $(2T,\epsilon)$ statistically complex (see, for example, Theorem 5 of Shalev-Shwartz et al. 2009). In particular, since $K_{S,r}(\mathbf{w}_{S})\subseteq\mathcal{K}_{S,r}(\mathcal{W})$ we obtain an upper bound of the statistical complexity of the given set.

3 Implicit Bias in Constant Dimension

In the results above we provided constructions in spaces with more parameters than samples. We next discuss the case $d\ll T$, which is interesting for certain contexts.

Regarding Theorem 4, we again point out that such a result cannot hold in the aforementioned regime. Indeed, in this case uniform convergence over the unit-ball applies. In that sense, restricting an algorithm to choose a solution in the unit ball provides an inductive bias that provides generalization guarantees. But what about Theorem 3? It is interesting to know if one can rule out regularizers that are not benign like the unit ball. We treat a set $K$ as a regularizer by identifying $K$ with a regularizer $r$ such that $r(\mathbf{w})=1$ if $\mathbf{w}\notin K$ and $0$ otherwise. We do not know the answer to this question and we leave it as an open problem. Nevertheless, we can provide the following intermediate result in a slightly more relaxed setting, where the instances may be non-convex, (and in fact non-Lipschitzian) but the expected loss function is indeed convex, and at each iteration the learner observes a bounded gradient $\|\nabla f(\mathbf{w},z)\|\leq 1$ Thus, SGD’s learning guarantee still apply.

We will state the next result for a slightly larger class of regularizers than merely convex regularizers. Recall that a function $f$ is called quasi-convex if $f(\lambda x+(1-\lambda)y)\leq\max\{f(x),f(y)\}$ for every $0\leq\lambda\leq 1$ and $x,y\in\mathcal{K}$, and strictly quasi-convex if $f(\lambda x+(1-\lambda)y)<\max\{f(x),f(y)\}$.

Constructions

Here we give a high level description of the constructions as well as the proofs of the main results. We note that for simplicity of exposition, the following description refers to the last iterate, but our full proofs refers to Eq. 2 (i.e., the algorithm that outputs $\mathbf{w}_{S}=\frac{1}{T}\sum_{t=1}^{T}\textbf{w}^{(t)}$) .

Our constructions build upon the following class of functions in 2. Let $A$ be a set of the form $\{(\alpha,\theta):0\leq\alpha\leq b\}$, where $\theta,b$ are parameters of the set and $\Sigma$ is a PSD matrix. We then consider the function $f_{A,\Sigma}$ defined as follows:

One can observe that these functions are convex, and further the gradient of $f_{A,\Sigma}$ at point $\mathbf{w}$ will equal

We start by showing how we can construct a function (of the type in Eq. 7) that does not converge to minimal norm solution. Let us take a concrete case where

We will suppress dependence on $A$ and $\Sigma$, and simply write $f$. The main observation is that the trajectory of $f$ is characterized by two phases.

At the first phase the closest point to $\textbf{w}^{(t)}$ (with respect to the $\Sigma$-norm) is at the boundary of $A$ (i.e $\alpha=0$). At this phase, $\textbf{w}^{(t)}$ can be seen to move “towards” the center of the interval, namely $w^{(t)}_{1}$ is increasing (see Eq. 8). At the end of this phase, $w^{(t)}_{1}$, is sufficiently large irrespective of the step size $\eta>0$. The second phase, starts when $\textbf{e}_{2}\equiv(\begin{smallmatrix}0\\ 1\end{smallmatrix})$ stops being the closest point, and the closest point to $\textbf{w}^{(t)}$ is at the interior of the interval. One can show that at this phase, the gradient moves upward hence $w^{(t)}_{1}$ does not decrease and overall the trajectory will converge to a point away from $\textbf{e}_{2}$: the Euclidean closest minimizer to $0$.

To see that when $\mathbf{v}(\mathbf{w})$ is at the interior of $A$ then $\nabla f(\mathbf{w})\propto\textbf{e}_{1}$, consider the following scalar function $g(a)=(\mathbf{w}-(a,1))^{\top}\Sigma(\mathbf{w}-(a,1)).$ Our assumption is that $g$ attains its minimum at $0<v_{1}$. Taking the derivative at $v_{1}$ and equating to $0$ (because the minimum is attained at the interior), we can see that $g^{\prime}(v_{1})=(\mathbf{w}-(v_{1},1))^{\top}\Sigma\textbf{e}_{1}=0.$ Hence, $\nabla f(\mathbf{w})=(\mathbf{w}-v(\mathbf{w}))\Sigma\perp\textbf{e}_{1}$. We depicted here the trajectory of GD without the projection step, however one can observe that throughout, the algorithm never escapes the $2$-ball, hence projections are indeed never implemented. The trajectory of $\textbf{w}^{(t)}$ is illustrated in Fig. 1 (green line).

The construction above is the heart of most of our results. Let us illustrate how it rules out a strongly convex regularizer (in the distribution-independent setting) and attain Theorem 1.

The key property of strongly-convex regularizers is that in any convex set they have a unique minimum. Moreover, two far away points cannot simultaneously attain close-to-minimal value. This is in fact the only property we will use. Thus, our result can in fact be extended to any regularizer that is a “tie-breaker”—namely, it always prefers a single unique solution amongst a class of possible solutions with large diameter.

The construction above will allow us to generate two instances of convex learning problems, where SGD converges to two far away points. The first instance is the standard Euclidean distance. Namely, we take a function $f_{1}$ of the form in Eq. 7, with $\Sigma$ the identity and $A$ with boundaries $(-\infty,\infty)$. In this case, SGD is biased towards the nearest solution $\textbf{e}_{2}=(0,1)$. The second instance, $f_{2}$, is the construction above where SGD is biased towards another point on the interval (see Figs. 2(b), 2(c) and 2(d)).

Now both points are global minima, for both $f_{1}$ and $f_{2}$, hence if SGD is implicitly biased towards solutions with minimum regularization penalty $r$, we must have that $r(\textbf{e}_{2})=r(\mathbf{v})$, where $\mathbf{v}$ is the choice of SGD when it observes $f_{2}$. However, if $r$ is strongly convex, because $\|\textbf{e}_{2}-\mathbf{v}\|=\Theta(1)$, there has to be a point on the interval between them that attain a strictly lesser regularization penalty, moreover it also attains minimal loss value. This contradicts the existence of such an $r$.

Our second result (Theorem 2) rules out the existence of any distribution-independent regularizer. In contrast with the strongly-convex case we can not give uniform bounds that depend on parameters of strong convexity. As such, the rates depend on the regularizer.

But the construction here is similar. We basically start with the assumption that there are two points $\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ with different regularization penalty, and we want to construct two functions $f_{1},f_{2}$ that maps $\mathbf{w}_{1},\mathbf{w}_{2}$ to the same empirical loss. It might seem that through a simple linear transformation that maps, say, $\mathbf{w}_{1}$ to $\textbf{e}_{2}$ and $\mathbf{w}_{2}$ to $\mathbf{v}$ we can reduce this case to the case above. However, there is some subtlety since gradient descent is not invariant to linear transformations. We note though that it can be turned to an affine invariant optimization algorithm (Koren and Livni 2017).

Towards this, we extend the construction above by constructing a more general example, where we can tune the point of convergence of SGD to any point on the interval between $\mathbf{v}$ and $\textbf{e}_{2}$. This allows us to avoid scaling, and use only rotations (which SGD is invariant to) in order to reduce the problem to the former case. This is done by changing the set $A$ from allowing $0\leq\alpha<\infty$ and $\theta=1$, to adding a second boundary condition on the right and also scaling $\theta$. In Fig. 2 we illustrate how changing the boundary condition changes the trajectory.

2 Distribution-Dependent Implicit Bias

We next discuss our second sets of results that argue about distribution-dependent regularization. Here we want to study if, for a given distribution, the set of solutions on which SGD converges has some meaningful structure on which we can argue why it generalizes.

Note that so far, our problem instances considered only a single function and the results were applicable to GD also. Here, though, in the distribution dependent setting such an example cannot work. Indeed, given a single function as an instance problem, SGD behaves deterministically and the solution it chooses is a unique solution which trivially generalizes.

We next discuss our argument that rules out a strongly convex regularizer, even if it may depend on the distribution at hand. We again utilize the property that a strongly convex regularizer obtains approximately minimum solutions only on a small diameter around the unique minimum.

Our strategy is as follows: assume that there are two samples $S_{1}$ and $S_{2}$ such that, when SGD observes $S_{1}$ it converges to $\mathbf{w}_{1}$ and when it observes $S_{2}$ it converges to $\mathbf{w}_{2}$. However, assume also that $\|\mathbf{w}_{1}-\mathbf{w}_{2}\|=\Theta(1)$, and that the empirical loss of $\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ is comparable, on both samples: namely $F_{S_{1}}(\mathbf{w}_{1})=F_{S_{2}}(\mathbf{w}_{1})$, and similarly with $\mathbf{w}_{2}.$

In the case above, as we argued in the distribution-independent case, clearly the algorithm failed to choose the minimizer of the regularization penalty, in at least one of the realization $S_{1}$ or $S_{2}$. So if $S_{1}$ and $S_{2}$ are equally likely, we obtain that with probability half (conditioned on the event that we saw $S_{1}$ or $S_{2}$) the algorithm failed to minimize $r$. Now, if the probability to observe one of such couple of samples $S_{1},S_{2}$ is positive, then we obtain the desired result.

To generate this setting, we rely on the following auxiliary construction in 2. We construct two functions such that, if SGD observes the first function, at the first iteration, then the gradient points upward and right. But if SGD observes the second function, at the first iteration, then the gradient points upward. This ensures that in each case SGD will move towards a different solution. If the size of the gradient is constant then the gap between the two iterations will be $\Theta(\eta)$.

We will also construct the examples in such a way that both points enter a regime where all points obtain the same empirical loss on both functions. This construction can in fact be done using piece-wise linear functions and it is illustrated in Fig. 3. We also give the formal statement here:

For every constant $0<c<1$, there are two $1$-Lipschitz functions $f(\mathbf{w};\pm 1)$ over 2 such that if $\mathbf{v}_{1}=-\nabla f(0;1)$ and $\mathbf{v}_{-1}=-\nabla f(0;-1)$ and $c<\frac{1}{2}\eta<1$ then $\|\mathbf{v}_{1}-\mathbf{v}_{-1}\|\geq 1/4$ and $f(\eta\mathbf{v}_{1};z)=f(\eta\mathbf{v}_{-1};z)$ for any $z\in\{-1,1\}$.

We next utilize the above construction to generate the problem in d. Note that the construction above generates a problem where SGD will converge to two different solutions with distance $\eta$ but same empirical loss (after one step). Indeed, we just need to randomly pick one of these functions.

We next want to amplify the distance. To do that, we consider $d=\Omega(T)$ Cartesian copies of 2. Then at each example, we show one of the functions above, at one of the products. Assuming enough coordinates were seen only once (which is going to happen w.h.p.), the variance on each sub-plane will be $\eta^{2}$: if we have $\Theta(T)$ such coordinates, the overall variance is going to be $\Theta(T\eta^{2})$ which ensures that we will converge to far away solutions on different realizations of the problem, if $\eta=\Theta(1/\sqrt{T})$.

Next, we derive Theorem 4 which addresses implicit regularization in a much broader setting. As discussed, here we cannot rule out the existence of an implicit bias; indeed, some form of an implicit bias always exists. We attempt, though, to understand how the implicit bias can explain generalization.

The result shows that for any regularizer: the set $K_{S,r}(\mathbf{w}_{S})$ which is the set of comparable solutions to the one outputted by SGD, given the empirical loss and regularization penalty, can be large up to the fact that choosing an arbitrary solution from this set can, in principle, lead to over-fitting (over general convex problems). Thus, to argue that the algorithm did generalize, further structure in the problem needs to be taken into account. And this is true for any regularizer.

Our construction is similar to the previous case in Theorem 3 up to some modification. Therefore, let us show that in the construction above $K_{S,r}$ will be $(T/6,\Theta(1))$-statistically complex. This is less than what we actually desire. We, in fact, observed $T$ examples and not $T/6$. Indeed, in the construction above, we showed that if we project the output of SGD to the observed coordinates, we obtain a solution of the form $(\mathbf{v}_{\pm 1},\mathbf{v}_{\pm 1},\cdots,\mathbf{v}_{\pm 1})\in(\real^{2})^{T}$, where $\mathbf{v}_{1},\mathbf{v}_{-1}$ are as in Lemma 1. By projecting this set, it can be seen to be a copy of (up to some rescaling) the normalized unit cube $\mathcal{M}=\{\pm\eta,\pm\eta,\cdots,\pm\eta\}\in\real^{T}$. This is true since $\|\eta\mathbf{v}_{1}-\eta\mathbf{v}_{-1}\|=\Theta(\eta)$.

Here, we rely on a construction by Feldman 2016. In order to show that uniform convergence is not equivalent to learnability in the convex optimization setting, Feldman showed (in our terminology) that the set $\mathcal{M}\in\real^{T}$ is $(T/6,1/4)$ statistically complex, if $\eta=\Theta(1/\sqrt{T})$.

As discussed, this is less than what we want, as we actually want a set that is at least $(T,\Theta(1))$ statistically complex. To tackle this, on each iteration we show the learner a loss function over multiple pairs of coordinates. Namely, if in the example above we drew at each iteration $f(\mathbf{w};z)$ where $z\sim D$, now in each iteration we show the algorithm $\frac{1}{k}\sum_{i=1}^{k}f(\mathbf{w};z_{i})$, where $z_{i}$ are i.i.d. This will reduce the step-size on each coordinate a little bit but if $k$ is constant we will still present a constant loss. On the other hand, now projecting on observed coordinates, SGD will converge to a solution in $(\mathbf{v}_{\pm 1},\mathbf{v}_{\pm 1},\ldots,\mathbf{v}_{\pm 1})\in(\real^{2})^{\Theta(kT)}.$ Thus we only need a constant $k>6$ so that the algorithm will converge to a $(T,\Theta(1))$-statistically complex set.

3 Implicit Bias in Constant Dimension

We next provide a construction in 2 that again rules out a class of regularizers, in particular strongly convex regularizers (and more generally, strictly quasi-convex regularizers).

In a similar fashion to previous constructions, we make SGD choose from a set of solutions, that exhibit comparable empirical loss. While the dimension of previous constructions depended on $T$, this construction does not. However, for the construction we relax the assumption that $f(\mathbf{w};z)$ are convex, but $F$ remains convex. Note that the learning guarantees of SGD are completely applicable to this setting.

Our construction relies on a 2-dimensional square, centered at the origin. Inside the square, SGD makes a simple 2-dimensional random walk, while when it exits from the square, it continues to perform a random walk in just one dimension (denoted as $y$), while the other coordinate (denoted as $x$) remains the same. As a result, the optimizer of $F_{S}$ is independent of $w_{x}$.

We study the event that $\mathbf{w}$ will stay inside the square for enough iterations to ensure that the variance of $w_{x}$ will be larger than some constant, but eventually $\mathbf{w}$ exit from the square to make $F_{S}$ independent of $w_{x}$. This will result with a set of solutions that share the same empirical error and also SGD can converge to each one of them.

References

Appendix A Technical Background

A key technical tool in the proof of Theorem 4 is a construction by Feldman, Feldman 2016, of a statistically complex set in d. While Feldman’s construction is not the first to show that the sample complexity of an ERM algorithm may scale with the dimension, it greatly improved over previous construction Shalev-Shwartz et al. 2009, and showed that the dependence may be linear in the dimension.

We will exploit here Feldman’s set in order to construct an example where SGD essentially picks arbitrarily an element from a statistically complex set, akin to ERM, and we will need the following statement due to Feldman

Let $\mathcal{W}_{d}=\{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\}^{d}.$ There exists a distribution $D$ over $1$-Lipschitz convex functions such that given a sample $|S|<d/6$ drawn i.i.d from $D$ then w.p. $1/2$ (over the sample $S$) there exists $\mathbf{w}\in\mathcal{W}_{d}$ such that

We will need a slightly stronger version of the theorem which is an immediate corollary

Let $A\subseteq\mathcal{W}_{d}$, such that $|A|\geq 2^{d-1}$, then $A$ is $(d/6,1/4)$-statistically complex.

For two vectors $\mathbf{v}\in\{-1,1\}^{d}$ and an element $\mathbf{w}\in\mathcal{W}_{d}$ let $\mathbf{v}*\mathbf{w}\in\mathcal{W}_{d}$ be the pointwise product between $\mathbf{w}$ and $\mathbf{v}$, i.e.

Let $D$ be the distribution from Theorem 6 and consider a distribution where we draw uniformly an elements $\mathbf{v}\in\{-1,1\}^{d}$ and a sample $S$ of size d/6 i.i.d from $D$. One can show that with probability $|A|/(2^{d+1})$ we have that there exists an elements $\mathbf{w}\in A$ such that

In particular, there exists a $\mathbf{v}$ such that with probability $\frac{|A|}{2^{d+1}}$, Eqs. 11 and 12 holds for some $\mathbf{w}\in A$ over the random sample $S$. Thus, we can define a convex Lipschitz mapping parameterized by $\mathbf{z}$ such that

From the above discussion if we draw $z\sim D$ we can see that this distribution demonstrates that $A$ is (d/6,1/4)-statistically complex

A.2 Berry-Esseen Theorem

A very important and valuable tool for analysing the behavior of random walks that we will use is the well-known Berry-Esseen Theorem, discovered independently in Berry 1941; Esseen 1942.

where $C_{\textrm{BE}}<1$ is an absolute constant, and $\Phi(a)$ is the CDF of a unit variate zero-mean Gaussian random variable.

For a bound $C_{\textrm{BE}}<1$ of the absolute constant see, for example, van Beek 1972. We will need the following technical Lemma which is derived via Theorem 7:

Let $k\geq 0$, and assume $T>2\cdot k$. If $X_{t}$ is a random variables such that

where $\textrm{erf}(a)=\Phi(a)-\Phi(-a)$ is the error function.

First, we lower bound $\sum_{i\in I}\sigma_{i}^{2}$, and obtain that:

Appendix B Proofs: Distribution Independent Regularizers

As discussed, the main technical gadget behind our distribution-independent-regularization results is a construction of a convex function on which GD does not converge to the minimal norm solution:

Let $\mathcal{W}=\{\mathbf{w}:\|\mathbf{w}\|<5\}$. For every $0<\theta_{2}\leq 1$, and $0<\theta_{1}\leq 0.025\,\theta_{2}$, there exists a a non-negative, convex, $1$–smooth, and $1$–Lipschitz function $F=F_{\theta_{1},\theta_{2}}$ such that, if we run GD (as defined in Eq. 4) with step size $0<\eta<1$ over $F$ then GD outputs $\mathbf{w}_{F}$ that satisfies the following

In words, even though $(0,\theta_{2})$ and $(\theta_{1},\theta_{2})$ are both minimizers of $F$, GD converges closer to the latter despite it having the larger norm (that is, despite being farther away from the initial point—recall that we assume here that GD is initialized at the origin).

The proof of Theorem 8 is provided at the end of this section and we continue with the proof of Theorem 1.

For every regularizer $r$ we will choose a distribution $D$ that is concentrated on a single function $F$ (dependent on $r$). Note that in this case, the iterates of SGD are completely equivalent to the iterates of GD with input function $F$. That is, Theorem 1 in fact holds even for deterministic GD, and we continue with the analysis assuming we run GD over a fixed function $F$.

We now proceed to choose the function $F$ for a given $\lambda$-strongly convex regularization $r$. Denote $\textbf{e}_{2}=(0,1)$ and $\mathbf{c}=(0.024,1)$. Consider the set $[\textbf{e}_{2},\mathbf{c}]=\{\alpha\textbf{e}_{2}+(1-\alpha)\mathbf{c}:0\leq\alpha\leq 1\}$, and let

We now want to choose function $F\geq 0$ such that $F(\textbf{e}_{2})=F(\mathbf{c})=F(\mathbf{w}^{*})=0$ and that $\mathbf{w}_{F}$, the output of GD over $F$, will satisfy the following:

$\|\mathbf{w}^{*}-\mathbf{w}_{F}\|>0.01;$.

If $\Pi(\mathbf{w}_{F})$ is the projection of $\mathbf{w}_{F}$ on $[\textbf{e}_{2},\mathbf{c}]$ then $\|\mathbf{w}_{F}-\Pi(\mathbf{w}_{F})\|\leq 1/(\eta T).$

This will conclude the proof. Indeed, by strong convexity:

and for $\eta=\Omega(1/\lambda T)$ we would get $r(\mathbf{w}_{S})-r(\mathbf{w}^{*})\geq\Theta(\lambda)$ as claimed.

We now demonstrate how to choose an appropriate $F$. We will consider two possible cases: $\|\mathbf{w}^{*}-\textbf{e}_{2}\|\geq 0.012$, or $\|\mathbf{w}^{*}-\mathbf{c}\|\geq 0.012$.

First assume that $\|\mathbf{w}^{*}-\textbf{e}_{2}\|>0.012$. We then choose

which can be seen to be $1$-smooth and $1$ Lipschitz on $\mathcal{W}$. A simple analysis of the update step shows that for $\eta<1$, we have that $\mathbf{w}^{(t+1)}=\sum_{i=0}^{t-1}(1-\frac{\eta}{2640})^{i}\frac{\eta}{2640}\textbf{e}_{2}$. Hence,

Next we assume that $\|\mathbf{w}^{*}-\mathbf{c}\|>0.012$. We now apply Theorem 8 with $\theta_{1}=0.024$ and $\theta_{2}=1$ and consider $F=F_{\theta_{1},\theta_{2}}$ as in the theorem’s statement. Then, we have that $\|\mathbf{w}_{F}-\mathbf{c}\|<\frac{120}{\eta T}$, and we obtain as before that $\|\mathbf{w}_{F}-\Pi(\mathbf{w}_{F})\|\leq\frac{2640}{\eta T}$ and that $\|\mathbf{w}^{*}-\mathbf{w}_{F}\|>0.01$, as required.∎

B.2 Proof of Theorem 8

It will be more convenient to construct a function $F$ that is convex, $4$-smooth and $22$-Lipschitz such that if we run GD with step-size $0<\eta<1/3$ over $F$ then GD outputs $\mathbf{w}_{F}$ that satisfies Eq. 14 and

Then, by re-scaling $F\to\frac{1}{22}F$, and observing that running GD on $F$ with step size $\eta/22$ is equivalent to running GD on $\frac{1}{22}F$ with stepsize $\eta$, we obtain the desired result.

Next, we construct $F$. For $0\leq\theta_{2}\leq 1$ and $0\leq\theta_{1}\leq 0.025\cdot\theta_{2}$ let us define the set: $A_{\theta_{1},\theta_{2}}=\{(\alpha,\theta_{2}):0\leq\alpha\leq\theta_{1}\}$. In turn, we define the function $F=F_{\theta_{1},\theta_{2}}(\mathbf{w})$ to be:

We start with showing that $F$ is indeed convex, $4$-smooth and $22$-Lipschitz as required (As discussed at the beginning, then we obtain the desired result by rescaling).

It is a standard fact that a function of the above form is indeed convex (see, e.g., Example 3.1 in Boyd and Vandenberghe 2004). We will next show that $F$ is also $4$-smooth and $22$-Lipschitz. first, one can show that from Eq. 15), that the gradient is given by

where we denote $\mathbf{v}(\mathbf{w})=\arg\min_{v\in A_{\theta_{1},\theta_{2}}}(\mathbf{w}-\mathbf{v})^{\top}\Sigma(\mathbf{w}-\mathbf{v})$. Next, observe that for any $\mathbf{w},\mathbf{w}^{\prime}$ we have $\|\mathbf{v}(\mathbf{w})-\mathbf{v}(\mathbf{w}^{\prime})\|^{2}\leq(\mathbf{w}-\mathbf{w}^{\prime})^{\top}\Sigma(\mathbf{w}-\mathbf{w}^{\prime})\leq\tfrac{3}{2}\|\mathbf{w}-\mathbf{w}^{\prime}\|^{2}$ as $\mathbf{v}(\mathbf{w})$ is the projection of $\mathbf{w}$ onto $A_{\theta_{1},\theta_{2}}$ with respect to the norm $\|x\|^{2}=x^{\top}\Sigma x$, and since projections are contracting distances. Then,

Also, since $\mathbf{v}(0)=(0,\theta_{2})$. We obtain that $\|\nabla F(0)\|\leq\theta_{2}\frac{\sqrt{5}}{2}$. Thus from smoothness we also get that for any $\mathbf{w}\in\mathcal{W}$, we have that $\|\nabla F(\mathbf{w})\|\leq\frac{\sqrt{5}}{2}+20\leq 22$. This proves that indeed $F$ is convex, $4$-smooth and $22$-Lipschitz.

To next prove the statement, we begin with the following analysis for trajectory of GD over the function $F_{\theta_{1},\theta_{2}}$.

Let $\mathbf{w}^{(1)},...,\mathbf{w}^{(T)}$ be the sequence defined by running unprojected GD (i.e., with $\mathcal{W}=\real^{d}$) over $F$ with step size $\eta\leq\frac{1}{3}$, starting from $\mathbf{w}^{(1)}=0$ for $T$ iterations. Then there exist $\frac{1}{2\eta}\leq t_{0}\leq\frac{3}{\eta},t_{0}\leq t_{1}\leq t_{0}+\frac{7}{\eta}$ s.t.:

Lemma 3 is the most technical part of the proof, and follows a careful step-by-step analysis of the trajectory of GD over the function $F$; we defer its proof to later in this section and proceed with the proof of Theorem 8. We also complement the proof with a “proof by picture” and a schematic description of the trajectory in Fig. 4

We next set out to show that if we run GD on $F$ with any step-size $0<\eta<1/3$, then

and $F(0,\theta_{2})=F(\theta_{1},\theta_{2})=0$. Then, as discussed at the beginning the result follows by rescaling $F$ to obtain a $1$-Lipschitz and smooth function $F$.

We thus proceed with the proof. The fact that $F(0,\theta_{2})=F(\theta_{1},\theta_{2})=0$ is immediate from definitions.

Next, we bound the sizes $\|\xi_{0}\|,\|\xi_{1}\|,\|\mathbf{w}^{(t)}\|$ for the setting depicted in Lemma 3. In particular when $\mathcal{W}=\real^{d}$ and no projection steps occur. One can easily observe that $\|\xi_{1}\|,\|\xi_{0}\|<1.5$. Following the trajectory path of $\mathbf{w}^{(t)}$, provided in Lemma 3, we can also provide a bound on $\mathbf{w}^{(t)}$:

if $t\leq t_{0}$ we have that $\|\mathbf{w}^{(t)}\|<\|\xi_{0}\|\leq 1$;

if $t_{0}\leq t\leq t_{1}$, then $\|\mathbf{w}^{(t)}\|\leq\|\mathbf{w}^{(t_{0})}\|+\theta_{2}\leq 2$;

and if $t\geq t_{1}$ we have that $\|\mathbf{w}^{(t)}\|\leq\|\mathbf{w}^{(t_{1})}\|+\|\xi_{1}\|<5$.

Taken together we have that $\|\mathbf{w}^{(t)}\|<5$. As such, one can show that for any set $\mathcal{W}$, not necessarily $\mathcal{W}=\real^{d}$, as long as $\{\mathbf{w}:\|\mathbf{w}\|\leq 5\}\subseteq\mathcal{W}$ then Lemma 3 holds. Indeed, in any such case running GD or GD without projection is completely equivalent.

Finally, by simple calculation we can show that the singular values of $\Sigma$ are $3/2$ and $1/2$. Hence,

where $\|\cdot\|$ denotes the spectral (operator) norm. We are now ready to show that $\mathbf{w}_{F}$ converges to $\xi_{1}$:

Computing $\mathbf{v}(\mathbf{w})$, and from Eq. 16 we obtain the following expressions for the gradient

We thus obtain two boundary conditions that governs the behavior of the trajectory:

Given $\eta$, we claim that Lemma 3 holds if we let $t_{0}$ denote the first iterate such that $\mathbf{w}^{(t_{0})}$ violates Eq. 22, when running GD, and if $t_{1}$ denotes the first iterate for which $\mathbf{w}^{(t)}$ satisfies Eq. 23. We will split the proof into 3 parts, according to GD’s trajectory, i.e. $t\leq t_{0},t_{0}<t\leq t_{1},t>t_{1}$.

There exists $\frac{1}{2\eta}\leq t_{0}\leq\frac{3}{\eta}$ such that $\mathbf{w}^{(t_{0})}$ is the first iterate that violates Eq. 22. Further, for any $t\leq t_{0}$, $\textbf{w}^{(t)}$ can be calculated by Eq. 17. And finally, $0.03\theta_{2}\leq w_{1}^{(t_{0})}$.

First note that $\mathbf{w}^{(1)}$ satisfies Eq. 22, hence $t_{0}\geq 1$. Now, following the calculation of the derivative provided in, Eq. 21 we obtain the update step $\mathbf{w}^{(t+1)}=\mathbf{w}^{(t)}-\eta\Sigma(\textbf{w}^{(t)}-\xi_{0})$ which we can rewrite as

By induction one can show that for $2\leq t\leq t_{0}$:

This shows that for any $t\leq t_{0}$, $\mathbf{w}^{(t)}$ can be calculated by Eq. 17. We proceed with the proof to show that $\frac{1}{2\eta}\leq t_{0}\leq\frac{3}{\eta}$. Considering the singular value decomposition of $\Sigma$ one can show that:

Plugging this in Eq. 25, we obtain that for any $t\leq t_{0}$:

To obtain the lower bound on $t_{0}$ observe that $t_{0}$ satisfies:

Plugging Eq. 27 and dividing by $\theta_{2}/2$ we obtain that:

which for $\eta<1/3$, can be rewritten as:

Next we provide an upper bound for $t_{0}$. Again, for every $t<t_{0}$ Eq. 22 is satisfied, which, as we already saw (recall Eq. 28) means that for every $t<t_{0}$:

Using the inequality $(1+2/n)^{n}\geq 3$, we obtain

In particular for $t\geq\frac{2}{\eta}+1$ Eq. 29 is violated and hence $t_{0}\leq\frac{3}{\eta}$.

Finally, we provide a lower bound for $w_{1}^{(t_{0})}$. Namely, we want to show that $w_{1}^{(t_{0})}\geq 0.04\theta_{2}$. First, by rearranging terms at Eq. 28 we obtain that $t_{0}$ is sufficiently large so that $\left(1-\frac{\eta}{2}\right)^{t_{0}-1}\geq 3\left(1-\frac{3\eta}{2}\right)^{t_{0}-1}$. Again applying the formula for $\mathbf{w}^{(t_{0})}$ in Eq. 27 we have that:

This concludes the analysis of the first phase of the trajectory. ∎

We next move on to the case $t_{0}\leq t\leq t_{1}$.

Let $t_{0}\leq t\leq t_{1}$. Then $\textbf{w}^{(t)}$ can be calculated by Eq. 18. Moreover $t_{1}\leq t_{0}+\frac{7}{\eta}$.

We again apply the calculation of the derivative provided in Eq. 21 at $t_{0}\leq t\leq t_{1}$ and obtain :

Note that this proves that $w_{1}^{(t)}=w_{1}^{(t_{0})}$. For $w_{2}^{(t)}$, we have that

which leads by induction to the following:

This shows that for any $t_{0}\leq t\leq t_{1}$ Eq. 18 holds.

We next bound $t_{1}$. Recall that $t_{1}$ is defined to be the first iterate for which Eq. 23 is satisfied. Let us show that for any $t$ s.t $t_{0}+\frac{7}{\eta}<t$ holds, Eq. 23 is satisfied and hence $t_{1}\leq t_{0}+7/\eta$. Equivalently we will show that for $t>t_{0}+7/\eta$, the following equation holds:

Next assume that $t\geq t_{0}+\frac{7}{\eta}$, then

We now move to the last phase of the trajectory. ∎

Let $t\geq t_{1}$, then $\textbf{w}^{(t)}$ can be calculated by Eq. 19.

Let $t\geq t_{1}$ be such that Eq. 23 holds. Then again, we consider the formula of the derivative $\nabla F(\mathbf{w})$ (see Eq. 21) and have that

We obtain the following recursive formula for $t$ if Eq. 23 holds for all $t_{1}\leq t^{\prime}\leq t$:

This shows that $\mathbf{w}^{(t)}$ can be calculated via Eq. 19. It remains thus to show that for any $t\geq t_{1}$, Eq. 23 always holds. We prove this by induction. Note that for the base case, this follows from the definition of $t_{1}$. We can thus assume by induction hypothesis that $\textbf{w}^{(t)}$ satisfies Eq. 33, and we want to prove that

We will denote also $\mathbf{v}=\left(\begin{smallmatrix}1\\ 1/2\end{smallmatrix}\right)$ Then using Eq. 26 and Eq. 33 we have that

where the last inequality is true since $\alpha_{t}\leq\beta_{t}$ for $\eta<1/3$ and we also have that $\mathbf{w}^{(t_{1})}_{2}<\theta_{2}$. This concludes the proof of Lemma 3. ∎

B.3 Proof of Theorem 2

For a vector $\mathbf{w}\in\mathcal{W}\subseteq\real^{2}$ let us denote by $\mathbf{w}^{\perp}:=(w_{2},-w_{1})$. In particular, we have that $\mathbf{w}^{\top}\mathbf{w}^{\perp}=0$ and $\|\mathbf{w}\|=\|\mathbf{w}^{\perp}\|$. Our proof relies on the following claim which we prove at the end of this section.

Let $r$ be an admissible regularizer over 2. There are two points $\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ in the unit ball such that for some $-0.005\|\mathbf{w}_{1}\|<\delta<0.005\|\mathbf{w}_{1}\|$ we have

and $r(\mathbf{w}_{1})\neq r(\mathbf{w}_{2}).$

Let $\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ be as in 8.4. First, because GD is invariant to rotations, we can assume w.l.o.g that $\mathbf{w}_{1}=\|\mathbf{w}_{1}\|\cdot\textbf{e}_{2}$, and hence $\mathbf{w}_{2}=(1,\delta)\|\mathbf{w}_{1}\|$. We now set $c_{r}=\frac{1}{2}|r(\mathbf{w}_{1})-r(\mathbf{w}_{2})|$. To choose $T_{r},D_{r}$ and $\mathbf{w}_{r}$ we now look at two cases: if $r(\mathbf{w}_{1})>r(\mathbf{w}_{2})$ and if $r(\mathbf{w}_{1})<r(\mathbf{w}_{2})$.

First suppose $r(\mathbf{w}_{1})>r(\mathbf{w}_{2})$. By upper-semicontinuity there exists a neighborhood $\delta_{1}$ such that for every $\mathbf{w}$ s.t. $\|\mathbf{w}-\mathbf{w}_{1}\|<\delta_{1}$, satisfies $r(\mathbf{w})>r(\mathbf{w}_{2})+c_{r}$. We thus set $T_{r}=\frac{2640}{\eta\delta_{1}}$, and $\mathbf{w}_{r}=\mathbf{w}_{2}$. We are left with choosing $D_{r}$. Note that in this case, the regularizer prefers a point with large Euclidean norm over a point with smaller Euclidean norm. Thus, to show it is not the implicit bias of SGD we only need to construct a distribution that is biased towards smaller Euclidean norms: Indeed, consider the set $[\mathbf{w}_{1},\mathbf{w}_{2}]=\{\alpha\mathbf{w}_{1}+(1-\alpha)\mathbf{w}_{2}:0\leq\alpha\leq 1\}$ we set

Our distribution $D_{r}$ is defined to choose $f$ w.p. $1$. Having defined $T_{r},c_{r},\mathbf{w}_{r}$ and $D_{r}$ we now set out to prove the result. A simple analysis of the update step of SGD shows that for $\eta<1$ we have for every $\textbf{w}^{(t)}$ that $\mathbf{w}^{(t+1)}=\sum_{i=0}^{t-1}(1-\frac{\eta}{2640})^{i}\frac{\eta}{2640}\mathbf{w}_{1}$. Hence,

By property of $\delta_{1}$ we have that $r(\mathbf{w}_{S})>r(\mathbf{w}_{2})+c_{r}$. But because $\mathbf{w}_{2}$ is optimal (i.e. attain zero on $f$), we also have $F_{S}(\mathbf{w}_{S})>F(\mathbf{w}_{r})$. This proves the case $r(\mathbf{w}_{1})>r(\mathbf{w}_{2})$.

Next, assume that $r(\mathbf{w}_{1})<r(\mathbf{w}_{2})$. As before we have a neighborhood $\delta_{2}$ such that if $\|\mathbf{w}-\mathbf{w}_{2}\|<\delta_{2}$ then we are guaranteed that $r(\mathbf{w})>r(\mathbf{w}_{1})+c_{r}$. We choose then $T_{r}=\frac{1}{\delta_{2}\eta}$ and $\mathbf{w}_{r}=\mathbf{w}_{1}$. To define $D_{r}$, we now use the function $F_{\theta_{1},\theta_{2}}$ from Theorem 8. We assume w.l.o.g that $\delta>0$, if this is not the case we can use that function $F_{\theta_{1},\theta_{2}}(\mathbf{w})=F_{\theta_{1},\theta_{2}}(-\mathbf{w})$. Let us set $\theta_{2}=\|\mathbf{w}_{1}\|$ and $\theta_{1}=|\delta|\|\mathbf{w}_{1}\|<0.05\theta_{2}$. Again, we consider a deterministic distribution $D_{r}$ that chooses $F_{\theta_{1},\theta_{2}}$ w.p. $1$. Recall that we assume that $\mathbf{w}_{1}=\|\mathbf{w}_{1}\|\textbf{e}_{2}$, hence $\mathbf{w}_{1}=(0,\theta_{2})$ and $\mathbf{w}_{2}=(\theta_{1},\theta_{2})$. Hence, by Theorem 8, if we run over a sample of size $T_{r}>\frac{1}{\delta_{2}\eta}$, we obtain that

In particular $r(\mathbf{w}_{S})>r(\mathbf{w}_{1})+c_{r}$. But again $F_{S}(\mathbf{w}_{S})\geq F(\mathbf{w}_{1})$, because $\mathbf{w}_{1}$ is optimal.∎

First, let us assume that there are $\mathbf{u},\mathbf{v}$ such that $\|\mathbf{u}\|_{2},\|\mathbf{v}\|_{2}=a$ and $r(\mathbf{u})\neq r(\mathbf{v})$ (at the end we will show that for admissible regularizer we always have such two points). We will also assume that $\|\mathbf{u}-\mathbf{v}\|_{2}\leq 10^{-9}\cdot a^{2}$. If this was not the case we can cover the sphere $\{\mathbf{w}:\|\mathbf{w}\|_{2}=a\}$ with balls with radius $10^{-9}\cdot a^{2}$, and have a constant function at every ball, concluding that $r$ is constant on the sphere (which contradicts our assumption). Next, we also assume that $|u_{2}|>\frac{1}{2}a$, (either $|u_{1}|>\frac{1}{2}a$ or $|u_{2}|>\frac{1}{2}a$, and the proof is similar in both cases so we will analyse only the later case). Then, since $u_{1}^{2}+u_{2}^{2}=v_{1}^{2}+v_{2}^{2}=a^{2}$, one can show that

So, by choosing $\delta=\frac{u_{1}-v_{1}}{v_{2}+u_{2}}=\frac{v_{2}-u_{2}}{u_{1}+v_{1}}$ we have that:

Using the first equality we can show that $u_{1}-\delta u_{2}=v_{1}+\delta v_{2}$ Similarly we can show that $u_{2}+\delta u_{1}=v_{2}-\delta v_{1}.$ Taken together we obtain that

In particular $r(\mathbf{u}+\delta\mathbf{u}^{\perp})=r(\mathbf{v}-\delta\mathbf{v}^{\perp})$. Since $r(\mathbf{u})\neq r(\mathbf{v})$, we either have $r(\mathbf{u})\neq r(\mathbf{u}+\delta\mathbf{u}^{\perp})$, or $r(\mathbf{v})\neq r(\mathbf{v}-\delta\mathbf{v}^{\perp})$. In the former case we choose $\mathbf{w}_{1}=\mathbf{u}$, whereas in the latter case we choose $\mathbf{w}_{1}=\mathbf{v}$.

Finally, so far we assume we can find two points on a sphere with different regularization penalty. Next, we assume that on every sphere $r$ is constant. Assume also to the contrary that for every $-0.0025\|\mathbf{w}\|<\delta<0.0025\|\mathbf{w}\|$:

It is not hard to show that in this case $r$ is constant everywhere except maybe $0$, making it in-admissible. ∎

Appendix C Proofs II: Distribution Dependent Regularization

We start this section by proving the existence of the auxiliary construction in Lemma 1.

See 1 Before we continue with the proof, notice the following immediate corollary of Lemma 1:

For every constants $c,\rho>0$, there is a distribution $D$ over a pair of convex functions $\{f(\mathbf{w};1),f(\mathbf{w};-1)\}$, such that $f(\mathbf{w};z)$ is a $\rho$-Lipschitz convex function in 2 and, for every $c<\eta<1$ denote $\mathbf{v}_{z,\eta}=-\eta\nabla f(0;z).$ Then the following holds: