Limitation of Characterizing Implicit Regularization by Data-independent Functions
Authors: Leyang Zhang
Zhi-Qin John Xu
Tao Luo
Yaoyu Zhang
Venue: Accepted by TMLR ()

Abstract: In recent years, understanding the implicit regularization of neural networks (NNs) has become a central task in deep learning theory. However, implicit regularization is itself not completely defined and well understood. In this work, we attempt to mathematically define and study implicit regularization. Importantly, we explore the limitations of a common approach to characterizing implicit regularization using data-independent functions. We propose two dynamical mechanisms, i.e., Two-point and One-point Overlapping mechanisms, based on which we provide two recipes for producing classes of one-hidden-neuron NNs that provably cannot be fully characterized by a type of or all data-independent functions. Following the previous works, our results further emphasize the profound data dependency of implicit regularization in general, inspiring us to study in detail the data dependency of NN implicit regularization in the future.

Published in Transactions on Machine Learning Research (10/2023)
Limitation of Characterizing Implicit Regularization by Data- independent Functions
Leyang Zhang
leyong:2@illnooisedd
Deportment of Mathematics, College of Liberal Arts Sciences University of Ilinois- Urbana Champaign
Zhi-Qin John Xu
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC Shanghai Jiao Tong University
Tao Luo'
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC Shanghai Jiao Tong University
CMA-Shanghai, Shanghai Artificial Intelligence Laboratory
Yaoyu Zhang
thgy-sttu@sstu.eddu.cm
School of Mathematical Sciences, Institute of Natural Sciences, MOE-LSC Shanghai Jiao Tong University
Shanghas Center for Brain Science and Brain- Inspired Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= 140kSqm0uy
Abstract
In recent years, understanding the implicit regularization of neural networks (NNs) has become a central lask in deep learning theory. However, implicit regularization is itself not completely defined and well understood. this work, we attempt to mathematically define and study implicit regularization. Importantly, we explore the limitations of common approach to characterizing implicit regularization using data-independent functions. We propose two dynamical mechanisms, i.e., Two-point and One-point Overlapping mechanisms, based which we provide two recipes for producing classes of one-hidden--neuee NNs that provably cannot be fully characterized by a type of or all data- inttedindeeendent functions. Following the previous works, our results further emphasize the profound data dependency of implicit regularization in general, inspiring us to study in detail the data dependency of NN implicit regularization in the future.
1 Introduction
One of the greatest mysteries of neural networks (NNs) is their ability to generalize well without any explicit regularization even when they are heavily overparametrized (Breiman 1995 Zhang et al. 2017]. For conventional machine learning algorithms,, without a regularization term, heavily overparameterized models easily overfit the data. However, for NNs, it has been empirically observed that, with proper initialization, their training trajectorics are implicitly biased towards well-generalized solutions. Such wrainingiinduced regularization effect is commonly referred to implicit regularization and is central issue for the deep learning theory.
Currently, our theoretical understanding of implicit regularization is very limited. To help us understand NNs better, we make a further step to explore the following basic theoretical questions about implicit
Corresponding Author 1 "Correspondigg Author

---

Published in Transactions on Machine Learning Research (10/2023)
regularization: (i) How to define implicit regularization mathematically; (ii) What is the relation between implicit regularization and conventional explicit regularization; (iii) How to characterize implicit regularization. Questions (ii) and (iii) are closely related in the sense that if implicit and explicit regularization are equivalent, then we may expect to find an explicit regularization function to fully characterize any implicit rogularization. In this work, we specifically address the relation between implicit regularization and a widely considered class of explicit aeggllariaationnrglaaaaaaa converted to whether there always exists a data-independent function G over the parameter space whose value exactly quantifies the preference of certain training process. For overparameterized linear models, specific nonlinear models and also NNs in the NTK regime, such a data-independent function G can be exactly derived, detailly introduced in Section 2 like matrix lactorization, stochastic convex optimization and one-neuron ReLU NN, implicit regularization cannot be explained by norms, strongly convex functions and iata-indeeendent functions (Razin & Cohen
by a data-independent function. In our study, this problem is
On the other hand, it has been proved that, for specific problems
2020 Dauber ct al. 2020 Vardi & Shamir 2021
In our work, we lake further step to propose two types of global nonlinear dynamical mechanisms beyond the description of various inteeeindeenndntt functions (see Section 5). Importantly, we provide two general recipes, NNs that
i.c., Two-point and One-point Overlapping Recipes, for producing familics of one-hidden-neune realize these two dynamical mechanisms, respectively. We also prove that their implicit regularizations cannot be fully characterized by any data-independent functions. Based on these results, we believe such mechanisms commonly exist in the training dynamics of general NNs; in other words, the implicit regularization of NNs is in general data-dependent. Our contribution in this work is summarized as follows.
(a) We give a mathematical definition of regularization, and define implicil and explicit regularization accordingly (Section 4.1
(b) We attempt to find the nature of implicit regularization, focusing on gradient descent. Tn particular, we propose two general dynamical mechanisms, i.e., Two-point and One-point Overlapping mechanisms, which put stringent constraints or even make it impossible to fully characterize implicit regularization by data-independent functions (Section 5
(c) Following the two mechanisms, we present Two-point and One-point Overlapping Recipes. The examples they produce include rich classes of one-hidddennneuron NNs which realize one (or both) of these two mechanisms (Section G). Then we show that One-point Overlapping Recipe can be extended to two-layer NNs with multiple neurons, meanwhile discuss the idea to generalize both recipes to multi-layer NNs and multi-sample loss functions.
(d) Specifically, we give examples concerning one-hiddeen-neuron NNs with Sigmoid and Softplus activa- tions. Experiments on such examples are also used to support our results.
(c) Based on (Vardi & Shamir 2021), ), we further emphasize the importance of data-dependence of implicit regularization in general, which should be carefully studied for NNs in the future.
2 Related Works
In recent years, many works have studied the implicit regularization Kukačka et al., 2017) for various problems. Progress has been achieved for many of them, e.g., matrix/tensor factorization, deep linear neural networks, NNs in the NTK regime, lincar and nonlinear models, and general nonlincar deep NNs. We recapitulate some of these works as follows.
For general non-linear NNs, empirical studies suggest that NNs have implicit regularization towards low-complexity function during training process (Arpit et al. 2017 Kalimeris et al. 2019 Goldt et al. 2020 Jin et al.) 2020). For example, the frequency principle (Xu et al., 2019 2020 Rahaman el al. 2019 Zhang et al. 2021 Xu et al. 2022) quantifies the implicit regularization of "simple solution" " by showing that NNs learn the data from low to high frequency, i.c., implicit low-frequency rogularization. The deep frequency principle qualitatively explains why deep learning can be faster by empirically showing that the effective farget function for deeper hidden layer biases towards lower frequency during the trainin (Xu & Zhou
2

---

Published in Transactions on Machine Learning Research (10/2023)
2021). However, such httr-coopleettty/oo--tooee to be characterized by an exact function in general. Only several special cases are studied, for example, the models linear w.r.t. trainable parameters, models linear w.r.t. both trainable parameters and inputs, and those with certain homogencous propertics.
regularization of general deep non-linear models is hard
Various studies have been done for the first kind of NNs, i.e., NNs that are linear w.r.t. trainable parameters but are non-linear w.r.t. the input. For example, NNs in the linear regime are studied by Luo al. (2021) and the NTK regime is studied by Jacot et al. (018). By considering functions in the phase domain, it has also been shown that gradient descent ( (GD) for the training of such NNs often picks a low- www-frquency function from multiple solutions (Zhang et al. 2021 Luo et al. 2020), and such behavior can be exactly formulated by a data-inneeenndet function. Another characterization of implicit regularization for NNs in the linear regime, presented in Zhang et al. (2000) and Mei et al. (2019), uses norm difference between the initial and learned parameters or between the initial and learned NN outputs. Finally, Chizat & Bach (2020) shows that infinitely wide two-layer neural networks in the linear regime with homogencous activations can be fully characterized as a max-margin classifier in certain situations.
The study of the second kind of model, i.e, those linear w.r.t. both trainable parameters and inputs, yields a series of results as well. One of the focues is deep linear NN. The implicit regularization due to depth in deep linear NNs are quantitatively studied and exploited; these include biasing Lowards simple functions to improve the generalization (Gissin et al.] 2019) and accelerating the training by providing a regularization that can be approximated by a momentum with adaptive learning rates to accelerate the gradient descent (GD) (Arora et al.) 2018). For others, Soudry et al. (2018) shows that GD takes the linearly fully-connected networks to solutions with implicit regularization of max-margin, while Gunasekar et al. (2018a) shows that GD takes linear convolutional networks to linear solutions with another penalty in the frequency domain. Besides, deep matrix factorization by deep linear networks with GD induces nuclear norm minimization of
the learned matrix, leading to an implicit low-rank regularization Gunasekar et al. 2018b Arora et al. 2019 Chou ct al., 2020).
As far as we know, only specific and limited models of the third kind, i.e., the homogeneous ones, have been studied. For example, Woodworth et al. (2020) studies simple homogeneous models for which the implicit bias of training with gradient descent can be exactly derived a function of the scale of the initialization.
While there are fruitful progress in explicitly characterizing the implicit regularization of (at least partially) linear models, explicitly characterizing the implicit regularization in the training of general non-linear models is more new, and encounters much difficulty. Therefore, with a focus on NNs, another line of works considers const.ructing counter-examples that provably cannot. be characterized explicitly by specific types of funct ions like norms, strongly convex functions or more general data-independent functions (Razin & Cohen 2020
Dauber et al. 2020 Vardi & Shamir 2021 We list some of them below.
Razin& & Cohen 2020 proved that, under some conditions, the matrix completion task performed by deep linear NN, when trained by gradient descent with mcan square error, can converge to an infimum, but there is no minimum, that is, this infiruum cannot be obtained. Thus, in this example the implicit bias of the deep linear NN can not be described by any norm. Another kind of example, given by Dauber et al. (2020), is based on stochastic convex optinization. More recently, Vardi & Shamir (2021) makes a step closer to general nonlincar NNs by providing examples of gradient flows for onc-neuron ReLU NNs which converge to global minima. Based on zero-initialivation and the manually-assige derivative of ReL.U at. O, they show that the training of such networks cannot be described by any useful inta-independent functions, in other words, the training depends largely on data.
Compared to these previous attempts, our work, with a focus on (non-linear) NNs, makes a step further in characterizing the implicit biases. Importantly, we analyze the reason behind the failure in using data- independent functions to explicitly characterize implicit regularization in network training, presenting general mechanisms (Section 5.1 mechanism) and corresponding example construction recipes (Section 5.1 1p. Our examples are all based on the recipes (see Section 5.2 and 5.3 which generate diverse and rich classes of one-hidden layer NNs. These are more systematic and universal compared to the existing ones we know, such as NNs in NTK regime, or those employing a specific type of activation (e.g., ReLU). Third, we follow the usual set-up of NN training, always considering over-parametrized networks (the number of parameters
3

---

Published in Transactions on Machine Learning Research (10/2023)
exceeds the number of samples). Therefore, due to the generality and close relation to application, results highlight profound data-dependency of NN implicit regularization and provide valuable insight for advancing the study in this area. Overall, our results emphasize the profound data-dependency of implicit regularization in NNs. This aspect warrants thorough exploration in future studies, given its relevance and potential impact on practical applications.
3 Preliminaries
We begin with definitions and notations we will use frequently throughout our discussion below. We start with activation functions and models.
Definition 3.1. 0 :: R is real-valued function which we call on activation function. Its reciprocal is denoted by (provided that erists), i.e., ((x) 1 when (xx + O.
a(o)
In this definition, no smoothness requirements are imposed on a (or Ø), however, in our One-point Overlapping Recipe, we further require that a is contimuously differentiable.
Definition 3.2. model is porametrized function g : RM parameter of g and the input of g- Thus, for each 0 E R.M have function g(0.-) RRd TK and the training of 9 modifics O.
M x I2 + R. For any (0, RM R is the
We will often consider a one-neuron network. In this case g has the form g(0, a) = a x). where = (a, w) x Rd its parameter and we write wTx x = (w, the inner product of w and æ on Rd.
Then we define our dataset and loss function for training a model.
Definition 3.3. A dalaset is denoted by S = {( M.) i E I} E Rd x IR for given index set I. A loss function (with respect to a given dataset S) is denoted by Ls L):
An example of Ls
Lg(0) L(O,5) = (00T yp:
S = (ax, y) S x
x IR
where 0 = w) w) E R1+d If Lg has a minimum, we further denote the set of its global minima by Ms- For example, min L.s = then Ms = (0). In our discussion about implicit regularization below, we will focus on the scenarios (see 4.1 in which training dynamics converge to global minima. Such focus is common in the study of implicit regularization, for example, Vardi & Shamir (2021). In general Ms depends S, and shall see in the next few sections that the failure of characterizing implicit regularization by data-independent function is closely related to the strong dependence of Ms on S.
Finally, we will write y for parametrization of a curve as well as its image. More notations will be introduced in the later sections.
4 Regularization
In conventional machine learning problems, regularization is often realized by adding a specific term the loss function, namely explicit regularization, help solve most ill-posed problems. In contrast, one of the magics of NNs is that, aforementioned, its training often finds good solution, as if it does the regularization "implicitly" (Zhang et al., 2017). To make the future study of explicit and implicit regularization more systematic and unified, we revisit the notion of regularization in this section. Mathematical formulation of general regularization is provided, which goes beyond the scope of gradient flow (GF) or gradient descent (GD). Based on this, we define implicit regularization and explicit regularization accordingly. Finally, we consider implicit regularization of GF for a loss function and discuss two types of characterization of them, both involving data-inde indeeededdenddnt functions (see Example (b) in Section 4.1 These characterizations will be our focus in the rest part of the paper.
4

---

Published in Transactions on Machine Learning Research (10/2023)
4.1 Revisiting Regularization
We begin by defining the regularization in a general sense as mapping between collections of algorithms. Let IRM x I2 + I be model as before. We say A is method if it maps an arbitrary dataset S to a subset A(S) of RRM. We call A(S) the solution set of A.
Definition 4.1 (Regularization). Let A, be two collections of methods that find solutions to the parameters of (().-). regularization (from A to A') just any map : A A', i.e,, R assigns a method in A to some R(A) A'.
The effect of this assignment is that R implicitly relates the solution set of A to that of R(A), provided that both exist. Also note that while this definition emphasizes the mathematical essence of regularization in general, the mapping (R) itself could be difficult to determine; instead, the study of it in practice may focus more on understanding the properties such mappings between specific collections of methods. Examples of such are implicit and explicit regularizations.
For implicit regularizations, we focus methods that find the global minima of loss function Ls, for any given dataset S. Let Amin be one of such methods, namely
Amia (S) (0 E R Ls(0") mingega (0) L)s
We also define A to be a collection of methods Amin finding the global minima of Lg. The implicit regularization (For GF) will then be a mapping associating each Amin to a gradient flow R.M. These notations will be used throughout the discussion below.
Definition 4.2 (implicit regularization for GF). Let T. be loss function (Definition 3.3 gradient flow (GF) of Ls starting at Oo by AGF namely, AGP is defined by
Denote the
{ ((1)) VoLs(()) 0(0)) O..
(1)
Then regularization R A = {Amin Amin finds the global minima of Ls} - {AGFE. Ou E RR is called an implicil regulorization of GF for L, or simply, an implicil regularization, for L.
For example, we can consider the gradient flows on the loss landscape of linear model, i.e., {AGF.O : 0o E R²} is the collection of gradient flows with respect to the loss function
L(O,S) Σ 0 wi? 0 DERMM < M.
== {Aa, 0o E RM} where cach As, finds the point in I. I-) which has the shortest distance to og. Then we obtain map R: A {ACF.e. po 0y E R by R(As,) AGF.e
For the sample S = b.) we require that (æI,..., xn) has full rank. Let A=
To motivate the study of implicit regularization, then give the following definition of explicit regularization. We will also focus on methods that find global minima (but may not be those for L). Definition 4.3 (explicit regularization). Let L be the loss function as before. Given collection A' of methods such that for any A' E A', any given dataset S and any 0, E A'(S), we have
Js(0 A') min As)
(2)
BERM
for some function Js R.M x A' - [-00, o0) related to L. An explicit regularization for L is regularization (L.e,, map) RA : A A'. Here A = (Amin).
Examples.
(a) Let Js(0,A') A') I(0,))+++ (0,AA)) for any given H M 4' + R. This is just the form of many commonly used explicit regularization in machine learning. For example, consider H(e, A') := ||0]), H(0, A') ||0||, more generally H(0, A') |0|,, 1.
5

---

Published in Transactions on Machine Learning Research (10/2023)
(b) Consider as before A' (A Oo R² Because each AGF.e. A.F,0, is just GF in RM, it is determined by lo This means we obtain a map G: TRM RM IR such that for any 0g E Acr.0,
G 0o) min G(e, 0o)
aEMg
The construction of is possible in a trivial way: we may find some c, E R with d' > c, then set G(0% 00) for any Oo IR and any 0g E A and G(O", 0) d otherwise. In certain situation, we make G behave much better. For example, if the gradient flows
the loss landscape of
linear regression problem, we may simply set G(0", = 0 0| for all (0", 0) RRM x RRM.
Also notice that neither H nor G depends on S. In such cases we will say R is characterized by dala-independenl funclion H (or G).
4.2
Characterization of Implicit Regularization
A direct approach to understand the implicit regularization R is to look at the value of certain data- independent function G over Mg to determine the element chosen (or preferred) by R. Depending on the amount of information about R provided by G, classify the following two types of characterization of R by G.
Definition 4.4. G: x RRM + R if for any S and any 0, E RM, the operation
We say that implicit regularization for L is characterized by dala-independent function
argminge.M G( 0
is well defined, i.c., 0 erists and is unique. Here o, 0 are the initial value and long-term limit of the GF for L, respectively.
Definition 4.5. We say that the implicit regularization for L characterized by data iuta-independent function G: GMR R + R in the weak sense for any S and any Og E RRM
min G(e,0u) = G( 0o). OEMs
(4)
where 0, 0j are the initial value and long-term limát of the GF for L, respectively.
It not difficult to see that if an implicit regularization is characterized by a data-independent function G. then G characterizes it in the weak sense. In other words, Definition 4.4 is stronger than Definition
4.5 Moreover, note that a constant function G on R.M x R characterizes any implicit regularization for L in the weak sense. Thus, every implicit regularization for L can be characterized in the weak sense, however, what are interesting are those non-trivial ones. Conversely, if for some implicit regularization R, the only data-independent functions characterizing it in the weak sense are constant ones, then R cannot characterizod by data-independent function.
5 Overlapping Mechanisms and Examples
Let R. be an implicit regularization of GF for loss function L. By our definitions above, the study of R. in essence is to trace the families of training trajectories of GF. In this section, we focus on the characterization of implicit regularization of GF for T. by a data-independent function G, proposing dynamical mechanisms that put stringent constraints on G or even make data-independent characterization impossible. These are the Two-point Overlapping Mechanism (Lemma 5.1] and One-point Overlapping Mechanism (Lemma 5.2), both of which can realized by one-hidden-nente neuron NNs with common activation functions. This will be shown by two numerical examples (in Section 5.2 and 5.3 using Sigmoid and Softplus, respectively. Furthermore, they serve prototypes of our Two-point and One-point overlapping Recipes.
5.1 Overlapping Mechanisms
Lemma 5.1 (Two-point Overlapping Mechanism). Fix O, RM Let be an inder set and {Stheer be collection of datasets. For each E I, let Of Mss, denote the long-term limit of the GF for S.) starting

---

Published in Transactions on Machine Learning Research (10/2023)
at Ou. Suppose that for any i E I, there is some j Iv{i} such that 0 # 03 and (0,, 03) s Mss n.Ms; (see Figure 1 for an ezample). Then the following resulls hold.
(a) The implicit regularization for L cannot be characterized by any data-independent function G RM x I2M + R.
(b) Any data-indent data-independent function G that characterizes the implicit regularization for L in the weak sense is constanl on (ir
(c) Any continuous iale-innependent function E C(RM x R that characlerizes the implicil regular- ization for L in the weak sense is constant on the closure of {0;)er
Proof. See the proof of Lemma in Appendix.
Lemma 5.2 (One-point Overlapping Mechanism). Fir Po 0% e ERM Let {r be M trajectories of GF -i(t)) for L from Oo to 0ū, such that lim, 7(0] exist for all and the limits are linearly independent. If the implicit regularization for I. is characterized by data- inte-inndeenneent function G E C2h (TRM x RR.) in the weak sense, then VG(,, 0o)le; = O, where the derivative is taken with respect to the forst entry of G. (see Figure 2
for an example)
Proof. See the proof of Lemma A.2 in Appendix.
The One-point Overlapping Mochanism puts stringent constraint G. If this mechanism is further strengthened such that trajectories starting from Op with different data S can overlap at any point in a neighbourhood of 0,, then the corresponding implicit regularization cannot be characterized by any data- independent function. This strengthened mechanism can be realized for special cases in experiment, and we will try to provide a general recipe for this mechanism in our future works.
Two-point Overlapping Mechanism (Lemma 5.1), which works for arbitrary function G R R- + R, is the heart of Two-point Overlapping Recipes. It will be used to prove Theorem 6.1 One-point Overlapping
Mechanism (Lemma 5.2 on the other hand, is more specific in that it requires G to be continuous. It is the
heart of the One-point Overlapping Recipe and it will be used to prove Theorem 6.2
In the following subsections, we provide concrete examples of one-biddeen-neuron NNs with common activation functions that can realize each of the above mechanisms. These two specific examples further inspire our general recipes in Section for producing rich classes of one-hidden-neuron NNs.
5.2 Example for Two-point Overlapping Mechanism
In this example, we consider the one-biidden--neuron NN with Sigmoid activation, i.e.
S(0, x)) ((w,
(w, a) IR?.
1 c war
and one-sample lg loss
(e) = L(0, ((), =1(0,xx) y
5= ((x v)) E R..
(0) is curve in R². Indeed, f(0. y is Notice that for any S, the global minimum of Ls is 0 and Lg (0} equivalent to
y + ty
so that a is a function of w E R.. Therefore, as illustrated in Figure 1 by properly choosing two singleton datasets S₁ = (21,81) and S₂ = (æ2, V2), we may obtain two sets of global minima for L(,SS) and L(:, S2), respectively, which intersoct at two points. Then, assigning each of these two points as long-time limit (for trajectory of GF) denoted by 07 and 0ž respectively, we "trace back" the trajectories to obtain two curves in the stable manifolds of Ms, Ms,, respectively. Then select. a point Og in their intersection. By this
7

---

Published in Transactions on Machine Learning Research (10/2023)
procedure, we find 0,. two datasets S1 and S2 and two gradient trajectories 7/. "2 converging to two points in Ms, nMs, required by the Two-point Overlapping Mechanism (Figure
Thus, the implicit regularization for can only be characterized by data-independent function G R R² 4 R the weak sense, because we must have G( 0b) = G 0o) = minge.s, G(0, 0o). Clearly, of and 0 cannot be differentiated without information from data by any data-independent function G. Therefore, as the GF trajectories differentiate 0j and 02, the corresponding implicit regularization must be data-dependent.
0
2
72
0
M Ms²
0
Ms
0
1
2
W
Figure 1: Two-point Overlapping Mechanism realized by a one-neuron-hiddeen NN with Sigmoid activation. Tracing back of gradient trajectories 71. finds Og. This procedure inspires our Two-point Overlapping Recipe. We choose the initial point On = (0.922, 2.868). The sample for (i) the blue lines is (æ1, M1) = (1, 1); (ii) the orange lines is (22, = (12.307, 1.400).
5.3 Example for One-point Overlapping Mechanism
In this example, we consider another one-hidden-neuron NN with Softplus activation, i.e.
1(0,z) [w, a, log(1 + exx)
and the one-sample &a loss. Notice that if (wx) then f(w, -a, x) = which means (w, -a) E (0) for S = {zz - ao (rw)}, } for any I E R. Therefore, as illustrated in Figure 2 we first choose an initial point 0g = (Wo, a.). Then we use the onc-element dataset = ((x, - (xrw))) with various æ, by which we obtain distinct trajectorics of GF from 0g to 0 (wo, -ag), cach one converging 0* from different diroctions. Figure 2 we show both the trajectories (dashed line) and MMs's (solid line), i.e., the sets of global minima of L, which clearly exhibits the One- point Overlapping Mechanism.
Thus, if the implicit regularization for L is characterized by data lata-independent function G E C¹ (R2 x + R in the weak sense, then VG 00)lo- = 0, where the Kerivatives are taken with respect to the first entry of G.
6 Overlapping Recipes
In this section, we realize the overlapping mechanisms in Section 5 by providing two general recipes which produce rich classes of one-hidden-layer NNs, none of which can be (fully) characterized by a type of, or all Rata-independent functions. These recipes are exactly inspired by our numerical examples above; in fact, they be viewed generalizations of them.
8

---

Published in Transactions on Machine Learning Research (10/2023)
0.99
0o
3.8
a
-1.01
0
-0.4
0.0
0.4
0.8
W
Figure 2: One One-point Overlapping Mechanism realized by an one-neuron-hidden NN with Softplus activation. The dashod lines are gradient trajectories and the solid lines are Ms L {0} for different singleton datasets S [(x, 3)}. We choose initial value Og (wo, oo) (0.3, 1). Then 0" (wn, -an) (0.3, -1). The dataset.
for (i) blue lines is (x, y) (0,6) 6, 6a-a (0.6((06 (ii) orange lines is (x, y) (1.0, - ( (iii) brown lines is (x (1.4, (0.0((14wo)) (iv) grey lines is (z, v) (1.8, -apo (1.8wo))

---

Published in Transactions on Machine Learning Research (10/2023)
6.1 Two-point Overlapping Recipe (Part A)
Our Two-point Overlapping Recipe produces one-hidden- networks which realizes the Two-point Overlapping Mechanism (Lemma 5.1.. It works by selecting common initial value On for two gradient trajectories with respect to S1, S2, which converge to two points 0f, 02 E Mss n.s respectively. In this procedure, the choice of 0, and 0f are (almost) arbitrary and one of the datasets (S) or S2) can be chosen (almost) arbitrarily. Moreover, using this construction procedure, we can make o E C (R) for any m E [0, oo] and with other nice propertics (monotonicity, periodicity, ctc.).
The following procedure constructs a and finds Oo: 07, 0zz and S2. For any E RM,, define Pa : RM spanfh} be the orthogonal projection from RM onto span
(a) Find Wo. ag with wo # O. Find 0 (wi a)) with w wo, St (1) with æ1 # 0, and 01 R + R such that the trajectory of GF for L(O, S1) = |00 (aff un 11 starting at Og converges to 0f as t + co, and L( 51) = 0.
(b) Let Ei = (1) (R) 0) C.R
(c) Find some w such that oं ww & E1 J (0), and if is the line segment connecting wo and ws then * (wwj) & (I), where h w up.
(d) Find some ab and re-define 0r (if necessary) at (xfwz) such that aga0 2 0 and ajo (xf = y1 Let E E1 U
(0) Find 22 E span - wo) \ M0} with supf x2 -1|| = Fn < min (PPP( |Ph (1mg))]
(f) Define 02 RR + and y2, such that i) 02 02 w) o (x) whenever x E Ei, ii) am) w/) = y2: and fii) the trajectory y = (%w 7a) of GF for S2) starting at 0g converges 02 as t oc. Let a 02
Remark 6.1. In Corollary A.1 we show that step (a) and (f) are well-established. This is achieved by
Proposition A.1 which, based on the exponential function e" shows that given S {(x, y)} S Rd and two points o, 0 Rd+1 there is R + R such that the GF of Ls(a, w) |aa w)) y/ starting from Ou converges to l" However, note that the choice of exponential function is just for the simplicity of proof; in general we could prove by using many other functions.
6.2 Two-point Overlapping Recipe (Part B)
The Two-point Overlapping Recipe (Part A) gives one-hiidden--neurnn networks that make it impossible to characterize the implicit regularization for by any nata-independ function G. In fact, we can repeat the construction steps in Scction 6.1 to obtain countably many datasets ] and countably many long-term limits of gradient trajectories (0% j such that if the implicit regularization for L is characterized by a data-independent function G in the weak sense, then G must be constant on {0 O 0h E NJ. The detailed procedure is given below. As in Section 6.1 this procedure can also give a a of any degree of smoothness and with nice properties (monotonicity, periodicity, etc.).
The construction is described as follows. For n =1 1, do the steps (a), (b) to obtain O. fi, an and Ej. For n 2 2, do the following steps.
(a) Find some E {l...., n 1} and w M- such that wFw; & En- (0), and if I is the line segment connecting we and wx then 0 * Pa (wx) ) & Px(l), where h = w. un-
(b) Find some at and re-define Jn-1 (if necessary) at {कf w such that a; z and 1n w yk. Let En-1 En-1 U {2श w.).
(c) Find n E sp - (oo)((0) with sup(|=.|\~+]] E Pn-1) min min((Pa(unf)) (Pa (wo))) (Pa (
10

---

Published in Transactions on Machine Learning Research (10/2023)
(d) Define On R R and Yn: such that on on (n whenever 2 w En- ii) "I (aa(ar)) (1 (m Yn, iii) the trajectory y= (Tw, Ta) of GF for T(,, Sn) starting at Og converges to 0% as t + 20. Let En : En-1 U x Tw.
Finally, after doing this for countably many times, we have defined a function doe on part of the real line. Now extend de to the whole real line. Let the extension be our activation function d.
A simple induction argument shows that G must be constant on (0= 0 = 0% n E NJ. Indeed, suppose we have proved that
(5) By construction above, 0 E Ms, for some S k S n, whence G(f 0o) - G( 0o). Similarly, 0% Ms whence G( 0u) I G( 0n). It follows that G( 0u) G( Bu), completing the induction step.
G 0b) = G( 0o) = -.. G 0o)
In Two-point Overlapping Recipe, we only find countably many points on which G is constant. One may ask we can find uncountably many such points. This is usually not true at least when M = 2 (so d d= 1). In fact, for most (we a) E R²² and most (zo, IR2, there neighborhood of (zo, yo) such that for So {(ro, }o J. for any S {(x, v)} - U, we cannot have
Lg (0 n S. (0)) 2
and
(w, (e E (0 (0) L
simultaneously (|E) denotes the cardinality a set E.). Since each such U contains a rational number and since Q is countable and dense in IR, it follows that we can find at most countably many points on which G is constant. Moreover, this shows that the Two-point Overlapping Mechanism and the construction of our recipe above both utilizes the global property of the aclivation A formal explanation of it is given in the following proposition. Recall that when L[(a, w), (x. v)) = 0, a = v/o(xw) =: yō(ww).
Proposition 6.1 (Two-point Overlapping Recipe is global when M = 2). Let E R. Fix a point (0o. Wo) E R with yo + O. Let F IR? + R, F(), = ((zw) o (zzP) - ā (z))) We have
(a) Suppose that [F(p, x 2 Clp - w| - vol" for some C > 0 and r, E N near (w, zo)- Then for sufficiently small > 0, if 0 < x - xol < 6, y F O and yō (xw) = (Now), there is no E such
that < 1p - w| < and yō (xp) = (zō())))
(b) Suppose that ā E C and ((xw), H' (fow) # 0. Also suppose
1
o' (((ww)
a" (xoux) o' o'(Inw)
*
(6)
w
ā (xoo)
Then for sufficiently small 8 > 0, 0 1x - vul 8, y f and yō (oō(saw, there is no p E R. such that. 0 < lp- w| < 8 and yā(x)) yoō (oā()))) If, however, (p)) = 0 for p near w or DF(w,)) x) for near Io, then is power function near zow, i.e., oxx) Czd for some C, d E RR when is sufficiently close to row.
Proof. See the proof of Proposition A.2 in Appendix.
Remark 6.2. We do not prove the case for M > 2, but we believe that this result also holds for M > 2. Namely, for most (w, a) E dd+1 and Sn = (x0, }o]} S IRd+1 there is neighborhood U of (Øo, yo) such that for any S = {xx })} C U, we cannot simultaneously have
L (0) n L5 (OH) 2
and
(w, E (0) n n (0)
11

---

Published in Transactions on Machine Learning Research (10/2023)
Corollary 6.1 below indicates that Proposition 6.1 holds in general. Since we deal with neural networks, this corollary focuses commonly-seen activation functions, including piecewise monomials, exponential activation, the Sigmoid activation and the Gaussian function.
Corollary 6.1. Following the notations in Proposition 6.1 all the results below hold.
(a) Any a and w, To o such that a power function on neighborhood of nyw (this includes ReLU and PReLU and Heaviside) salisfies F near x0).
(b) For any analytic activation a and any 2o, E R such that the zero locus of the function F(p, = ō (xw))(xmP) ö (xp)ā ( satisfies
Fo = ( up EU : œo
for some neighborhood U C I2 of (w, (w, can find sufficiently small ô > 0 such that if 0 < Iz zol < 8, # O and yō(zw) = yoδ (zow), there is no E R with 0 < lp w| < and yā(zp) = yoō (cop).
(c) If a = e² or o = c=
then for any zo E RR, we can find a sufficiently small > 0 such that if < - - sol < 8, y + and yo = yoō (zow), there is no p IR with < ly w| and
(xp))) (
(d) Let w > O. Iʃ a Ite-r, for any E (-oo, such that if 0 < xx zol < 8, # 0 and yo (á(w) = you (xow), there is no E R with 0 < lp wl < 6 and (xp) = yoō (xup).
00); we can find sufficienlly small 5 > 0
Proof. See the proof of Corollary A.2 in Appendix.
6.3 One-point Overlapping Recipe
Clearly, Section 6.1 and 6.2 are not the only ways to negate the possibility that any one-hidden-neeuro network can be characterized by data-independent function G. We present another way below, called One-point Overlapping Recipe, which considers C'l functions satisfying G(p.q) G(p q, 0) for p. E RM; one such G can be the Euclidean norm on M In this recipe, the choice of datasets are (almost) arbitrary, and we only require that a is differentiable, non-negative and strictly increasing on R.
This recipe described as follows.
(a) Find any a IR R+ such that o' > 0.
(b) For each E N, find any On = (Wn, an) with on + O. Select datasets Sn, (Rn,k: oa Wn)). such that the vectors
a (
.sksd
on (2: (ITT wr)
(In,k)i'" ." (In,k)a
are linearly independent in Rdd.
(c) Repeat step (b) until we find enough 0, 's with different values of an (w,, can be arbitrary), as well as corresponding Sn., for each E N.
In (c), the word "enough" depends on the property of G we would like to obtain. For example, in Lemma 6.2 we show that by carefully selecting one On and distinet datasets we can show that VG q) = 0 for
some p, q E M while in Theorem 6.2 we show that by carefully selecting countably many such points and datasots, we can show that VG(p.q) = 0 on an affine subspace of RM R.
The following two lemmas guarantee the validity of One-point Overlapping Recipe.
12

---

Published in Transactions on Machine Learning Research (10/2023)
Lemma 6.1. Suppose that 0 and o' 0 on R. For any dataset S {(,, RR R and any 0. (Wo, (o), the Irajectory of GF for S) has a long-term limit 0 Ms.
Remark 6.3. This lemma is also used to construct concrete examples using the construction in Section 6.2
Moreover, the same result holds for o < 0 and o' < O, because L(Ø) = lao(wx) y = |a( (ux-))(xx)- - (-y)}²
Proof. See the proof of Lemma in Appendix.
Lemma 6.2. Let o: R + R+ be differentiable and striclly increasing. Then
(a) Suppose that M = 2. If the implicit regularization for L is characterized by data-independent function E C. in the weak sense, then there are some du. 0 E R2 such that VG(,, 0o):; = 0, where the derivalives are laken with respect to the first entry of G.
(b)
The result in (a) also holds for general M2 2.
Proof. See the proof of Lemma in Appendix.
6.4 Main Theorems
In this subsection, summarize our examples based on the Two-point and One-point Overlapping recipes. Complete proof of the results are given in Appendix. Both theorems consider the following class of functions
GM (G e (R RM, G(p. q) G(p q: 0)).
Theorem 6.1. Based on the Two-point Overlapping Recipe, we have
(a) For any k E N, we can construct an activation a E C² following Section 6.1 such that the implicit regularizalion for L cannol be characlerized by any dala-inddependen fanction G R. x R + R.
(b) Following Section 6.2. for any k E N we can find an activation E C such that if the implicit regularization for L is characterized by data-independen function G E C* (IB x RM) in the weak sense, then G 0)) is constant on an open set of TR. M for some 0n E R.M.
(c) Following Section 6.2, for any l E N we can find an activation a E O having the property that if the implicit regularization for L is characterized by data iuto-independent function G E G in the weak sense, then G is constant.
Proof. See the proofs of Theorem 6.1 (a) Theorem 6.1 (b) and Thcorem 6.1 (c) Appendix.
Theorem 6.2. Let a : R be differentiable and strielly increasing. Based on the One-point Overlapping Recipe, we have
(a) cannot be characterized by any strongly conver data- dala-independent function G C' x RR
(b) If the implicil regalarization for L is charuclerized by a dala- dala-independenl function G E GM in the weak sense, then G(.,0) 0) is constant on a line RM for any given O.
Proof. See the proof of Theorem 6.2 in Appendix.
Corollary 6.2 (Onc-point Overlapping Recipe for Two-layer NNs). Fix m, d E N. Consider the two-lager neural network g(0, x) = Ene ago æ), where 0 = (wx, a E R(d+1)m and the corresponding loss function
L(0, (z, v)) = (9 x) yl
Σ Coowwy x)
Suppose that a :R + R is differentiable and strictly increasing. Based on One-point Overlapping Recipe, we have
13

---

Published in Transactions on Machine Learning Research (10/2023)
(a) L cannot be characterized by any strongly conver data- cata-independent function G ('((4)) p(d+1)m).
(b) If the implicit regularization for L is charucterized by a data-independent function E 9M in the weak sense, then for any 0 IRm G(,,0) is constant on the set {(0, Pk pk) Ph E R..
Proof. See the proof of Corollary 6.2 in Appendix.
7 Conclusions and Discussion
7.1 Generalization of Overlapping Recipes
In this part we briefly discuss the generalization of our One-point Overlapping and Two-point Overlapping recipes (as well corresponding mechanisms). We discuss the potential for our recipes work for two-layer (fully-connected) NNs with multiple neurons with one-sample dataset, or even for more general models and loss functions.
Let's start with the Two-point Overlapping Recipe. Indeed, for this recipe, very few restrictions are put on the structure of the network or the loss functions; so in particular can be generalized to a much larger set of models. To see this, consider a o-dependent model 9 = Jr : R Rd + R and lgg (0,x) -12.. The key of Two-point Overlapping Recipe is "construct" the model g by "constructing" a, meanwhile taking the advantage that convergent GF uses only partial information of a. By looking at this recipe for one-neuron models (Section 6.1 and/or 6.2 to make the Two-point Overlapping Recipe work for fo we basically need to
L(O, (z,y)) L. (0, (x, v))
(a) Find 0f, some dataset S₁ and some such that the GF for Lo, (1, starting at 0g converges to or, and L., (07, =.
(b) Find 0 such that for (02, S1) y, namely, Lo, Si) 0.
(c) Find another dataset S2 and so that Grg gr, (0) S2) y, and the GF for (t converges to 0g.
(d) Finally define by appropriately "concatenating" σ and 02.
Note that here we do not require that SI, S2 must be singletons. As long as the system over-parametrized, these requirements are easy to satisfy, not only because they set few restrictions the choice the activations, the samples, and the parameters we choose, but also because the requirements are loosely related to each other, c.g., requirement (b) does not have much to do with requirement (a).
The One-point Overlapping Recipe deals with the relationship between the partial derivatives of the loss function, so naturally depends more on the structure of both the model and the loss function. We have shown that this recipe works for two-layer fully connected NNs well. Unfortunately, currently we do not know how to generalize it to NNs with more layers, and/or to multi-sampt loss functions. What know is: to make it work we basically need to
(a) Find two distinct points point Oo, Oj E R and some datasets St...,,
(b) For each j < M, the GF by for Ls, starting at 0g converges to 0ü-
(c) For each 1 < j < M, y has limiting direction, i.e., lim (0 linearly independent.
exists; moreover, these directions
[y]]]]
With such information conclude that VG(, (o); 0o; as in Lemma 6.2
14

---

Published in Transactions on Machine Learning Research (10/2023)
7.2 Conclusion
In this work, we provide mathematical definitions of regularization, implicit regularization, and explicit regularization. We specify two levels of charactorization of implicit regularization using a data-independent function G, i.e, (full) characterization and characterization in the weak sense. We delve into the nature of implicit regularization and address its challenges by proposing two general dynamical mechanisms, i.e., Two-point and One-point Overlapping mechanisms. These mechanisms make implicit regularization difficult to characterize or even impossible to characterize using data-independent functions. Additionally, we give numerical examples that realize these mechanisms with one-hiidee-neuronn NNs with Sigmoid or Softplus activations. These examples further inspire our development of Two -oo-poinn and One-point Overlapping recipes that produce rich classes of oue-hiddee--neuro worksrks which realize these two mechanisms respectively. Last but not least, We show that our Two-point Overlapping Recipe depends on the global property of activation functions.
One strength of our work is that proposed two mechanisms explaining why characterizing implicit regularization using date-independent functions often fails, and we have recipes that serve as general guidelines for the construction of examples. This systematic approach yiclds rich classes of common one- hidden-neuron NNs. Furthermore, as we have discussed before, our recipes and mechanisms have the potential to be extended to two-layer NNs with multiple neurons, or even more general models. In comparison, the existing examples mainly focus on more specific cases (e.g., specific set-up specific kind of activations). The generality of our recipes thus suggests that it is generally difficult to characterize implicit regularization by dala-independent functions, if not impossible.
On the other hand, our work does not fully explain the implicit regularization in NNs. For example, we do not know whether all the implicit regularization of NNs fall into one of our recipes and/or mechanisms. Neither are we clear about the practical implication of it. In particular, whether a data-dependent implicit regularization could help the generalization of DNNs remains an open problem for the future research.
While an implicit regularization is generally dala-dependent, partial information about it may still be obtained by a data-independent function. Further studies should be conducted to mathematically determine details of such partial information. Besides, one may alternatively look for mcaningful] data-dependent functions to characterize an implicit regularization. Since the non-equivalence bet ween implicit and explicit regularization seem to depend on the global property of an activation function, one may also consider characterizing the training dynamics by a set of functions.
Acknowledgments
This work is sponsored by the National Key R&D Program of China Grant No. 2022YFA1008200 (Z. X., T. L.., Y. Z.), the National Natural Science Foundation of China Grant No. 12101402 (Y. Z.), No. 62002221 (Z. X.), No. 12101401 (T. L.), the Lingang Laboratory Grant No.LG-QS-202202-41 (Y. Z.), Shanghai Municipal of Science and Technology Project Grant No. 20JC1419500 (Y. Z.), Shanghai Municipal Science and Technology Key Project No. 22JC1401500 2021SHZDZX0102.
(T. L.), Shanghai Municipal of Science and Technology Major Project No.
References
Sanjeev Arora, N Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparametcrization. In 35th International Conference on Machine Learning, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 02:7413-7424, 2019.
OOne trivial data-dependent characterization define C(O,, 0) = 10 (0, where is the training data and 0" (0gg S) the long-term limit the trajectory GF for L.., 8) starting at 9o provided that it exists. See also Vardi & Shamir 2021: for other trivial forms.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. International Conference on Machine Learning, 2017.
Leo Breiman. Reflections after refereeing papers for NIPS. The Mathematics of Generalization, XX:11 15, 1995.
Lenaic Chizat and Francis Bach, Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
Hung-Hsu Chou, Carsten Gieshoff, Johannes Maly, and Holger Rauhut. Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank. arXiv preprint ar arXiw:2011.3377 2020.
Assaf Dauber, Meir Feder, Tomer Koren, and Roi Livni. Can implicit bias explain generalization? stochastic convex optimization as a case study. arXic preprint NKN:20033061522 2020.
Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. In International Conference on Learning Representations, 2019.
Scbastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10(4):041014, 2020.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Newral Information Processing Systems,
2018a.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-10. IEEE, 2018b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571 8580, 2018.
Pengzhan Jin, Lu Lu, Yifa Tang, and George Em Karniadakis. Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness. Neural Networks, 130:85-99, 2020.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD on neural networks learns functions of increasing complexity. Advances in Newral Information Processing Systems, 32:3496-3506, 2019.
Jan Kukačka, Vladimir Golkov, and Daniel Cremers. Regularization for deep learning: A laxonomy. arXic preprint Xrxi::1710. 106666, 2017.
Tao Luo, Zheng Ma, Zhi-Qin John Xu, and Yaoyu Zhang. On the exact computation of linear frequency principle dynamics and its generalization. arXie preprint Xrxiv:2010.00 08153, 2020.
Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang. Phase diagram for two-layer relu neural networks at infinito-width limit. Journal of Machine Learning Research, 22:1-47, 2021.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pp. 2388-2464. PMLR, 2019.
Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of deep neural networks. International Conference Machine Learning, 2019.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint arXi::2005.003:
2020.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasckar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822 2878, 2018.
16

---

Published in Transactions on Machine Learning Research (10/2023)
Gal Vardi and Ohad Shamir. Implicit regularization in relu networks with the square loss. In Conference Learning Theory, pp. 4224-4258. PML.R 2021.
Blake Woodworth, Suriya Gunasckar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference Learning Theory, pp. 3635-3673. PMLR, 2020.
Zhi-Qin J Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior deep neural network in frequency domain. International Conference on Neural Information Processing, pp. 264,274, 2019.
Zhi-Qin John Xu and Hanxu Zhou. Deep frequency principle towards understanding why deeper learning is faster. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. Communicalions in Computalional Physics, 28(5):1746-1700 1767, 2020.
Zhi-Qhn John Xu, Yaoyu Zhang, and Tao Luo. Overview frequency principle/spectral bias in deep learning. arXiv preprint Xrx::22001. 07395, 2022.
Chiyuan Zhang, Samy Bengio, Mortiz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations, 2017.
Yaoyu Zhang, Zhi-Qin John Xu, Tao Luo, and Zhong Ma. A type of generalization error induced by initialization in deep neural networks. In Mathemalical and Scienlifie Machine Learning, pp. 144-164. PMLR, 2020.
Yaoyu Zhang, Tao Luo, Zheng Ma, and Zhi Qin John Xu. A linear frequency principle model to understand the absence of overfitting in neural networks. Chinese Physics Letters, 38(3):038701, 2021.
17

---

Published in Transactions on Machine Learning Research (10/2023)
A Appendix
Lemma A.1 (Lemma 5.1 Fiz do E TRM. Let I be an inder set and (8thee be collection of datasets. For each i E I, let 0 E Ms. denole the long-lerm limit of the GF for L(:,i)) starting al On- Suppose that for any i I, there is some j E F such that 0 + 03 and {0; 03} C Ms. Ms, (see Figure for on example). Then the following results hold.
(a) The implicit regularization for L cannot be characterized by any data- dota-independent function G RM x XRM- +R
(b) Any data-inden inta-indeepndent function G that characterizes the implicit regularization for L in the weak sense is constant on {6; hes
(c) Any continuous data-indl aata-independent function G C(R M RR) that characterizes the implicit regular- izalion for L in the weak sense is conslant on the closure of {0; hirr
Proof.
(a) Suppose that the implicit regularization for L is characterized by data-independent function + R. Since 0 E MMs \(o}} for some j E I, we must have G: R x R M
G 0o) > G(6).00)
(8)
Similarly, since 0j E Ms. \0;), we must have
G(0), 0o) > 0007,00)
(9)
But then
G 0,) < G((), 0o) G( 00).
(10)
which is absurd.
(b) Argue the same way as (a), we can see that for any E I, there some j # such that G(O3, 0o) G(O 0o). The desired result follows immediately.
(c) Clear from (b).
Lemma A.2 (Lemma 5.2). Pir Oo, 0 MR Let (m be M trajectories of GF for L from Oo to 0g such
that lim (e(t)
Ha(e]] crist for all and the limits are knearly independent. If the implicit regularization for L is
characterized by data-indepent independent function G E C (RM BB in the weak sense, then VG(, 0o)lo; = 0, where the derivative is taken with respect to the first entry of G.
Proof. Note that any % is eventually orthogonal to a null set of L, containing 0" The rest are clear.
Proposition A.1. Let o(x) e and O, = (wo, ao) E RR with wo # O. For any dataset S the trajectory of GF for S) starting at 0, converges as t - oc. Conversely, for any 0" = (w",,a)) such that a" # ag, there is a dataset S such that the trajectory of GF for L(-,S) starting at Oo converges to 0 as + co.
Proof. Fix any S = (x) E R- x R. We have L(O,S) lae 3l2 Thus,
à 20ae00uu =)
(11)
w -2(ae 1) v)
Thus,
-2(ae y) w -2(a0=² y) "F wo.
(12)
18

---

Published in Transactions on Machine Learning Research (10/2023)
If aee" y + 0, we clearly have F,ad Wyg Otherwise, à tb; 0, we still have σ,ad dbç Integrating on both sides of the equation, we see that
L ddj(u)du - -z // a(u)ā(u)du,
(13)
which yields wt(t) = w,(0) + (a'(t) 2d) 24. Equivalently,
2
a² ag
w(1) w(()
(14)
Thus, {(w((), ((t)) : E [0, (o)} is part of a parabola. This means as -- xc, either w(t)),(t) both diverge, or both of them converge. Suppose that (²) + 00 as + co. Then there some N N such that for any + oc as t - which is contradiction. It follows t> N we have x (t) > O. Whence a(t)e" w(t) "w(t) that lim w(l) and lime-soo a(l) exist.
Conversely, 0r = (w",a", with a' * ao. Set
(w- wo). y = a² e"w""
(15)
a*
dg
By proof above, the trajectory of GF for L(,, (x, v)) has long-tern limit. Since L(0", = 0 and since w" = w0)) + _ x, this limit is (w",a) aa) = 0"
Corollary A.1. Based on Proposition A.1 we have the following results.
(a) There erist some On, 0j, S and os such that slep (a) in Two-poinl Overlopping Recipe (Parl A) (Section 6.1 holds.
(b) There exist some 02 (a) and y2 such that step (f) in Two-point Overlapping Recipe (Part A) (Section
6.1 holds.
Proof.
(a) Fix any 0, (wo, ag) with wo and any 0 with wi wo (this is the requirement of the recipe) and dn # 0 (this is the requirement. of equation (15)). Find any 07 = (wi, such that (5) holds. The result follows immediately from Proposition A.1
(b) Use equation 15 to find a dataset $2 = {(02, W2)) such that the trajectory of GF for l Fn 2 starting at On converges to (w:, az) as t + co. Note that we must have 22 E span ww; - wo Also, since the sign of az is the same as that of on, Tw is the line segment l connecting wo and wg. Therefore, we can set y22 = iu2 and define d2 R - IR such that o2(=I w) = 61(2 w) whenever x w É1 and (2 w) = "F for w E 1. Since Pa $ Ph(l), where h w wo, it follows that we can re-define at {x3 wij such that (1az(x} w = y2-
Remark. While our construction is based on the exponential activation function (zz) = it can be based any other activation function that satisfies: there are datasets S1, S2 such that the trajectories of GF for starting at O, converges to distinct 01, 0z, respectively. For example, as we show in Section the Sigmoid function is one candidate.
S1), L(, L(,
We now give the proof of our main theorems.
19

---

Published in Transactions on Machine Learning Research (10/2023)
Proof of Theorem 6.1 (a). Suppose that the implicit regularization for L is characterized by data- independent function G RR R.M + IR. The Two-point Overlapping Recipe (Part A) guarantees that 0f E Mss) {02} and 02 E Ms. \ {01}. Applying Lemma 5.1 to the set
(0,005)
(16)
we conclude that the implicit regularization for L cannot be characterized by any data-independent function G: x R + RR. It remains to show that a can be made as smooth as we want. To do this, let 02 be of Ch when restricted to En U 2 Twe Extend 02 to a C* function on the whole R. Since a = 02 in Two-point Overlapping Recipe (Part A), a E C...
Proof of Theorem 6.1 (b). Follow the Two-point Overlapping Recipe (Part A) to obtain 01, 02 Go: 0 02. S1 and S2. For simplicity, may further require that the construction is based on Proposition A.1 and corollary A.1 and a² + O, 0500 2 0.
Find a small enough r > 0 such that for any 0r = (w"", aa)) E B(0 r), we have i) 0g + 0", ii) 0 (w(wf) & (I),), where / is the line segment connecting wo and wx and h = w- - -w and iii) a" * 0. Geometrically and intuitively, r)) is an open ball lying either above or below the w-plane, and does not contain Og Now find countable, dense subset (0% (wi, , of r(0 such that for any distinct i,j 3, zF w + æTwz.
For n 2 3, choose sufficiently large I, such that step (c) in Two-point Overlapping Recipe (Part B) holds. Then use equation (15 to find a dataset S,, = (ă Fn) such that the trajectory 7 (Tw., 7a,) of GF for Since the sign of az equals du, Yw. is the line segment connecting wo and un Set yv = Dn- Define on R - lK such that on (xx" w) = 1 un) whenever nh w E En- and on (2,T,w ex for w Yw.. Since (ww & Ph(Ye,), where h = w wo, we can re-define on at {ar[w]] such that anan("
lac* 1v starting at Ou converges to 0% t
Note that En- is the union of finitely many disjoint compact sets. Thus, after doing countably many times, we can obtain a 0o0 defined on union of disjoint compact sets. Thus, by our proof A in Appendix, we can extend the xo from this union of compact sets to be a C* function on R. Since a = 0.c by our recipe, a E C*
Now our construction forces any dala-independent G R R.M - R that characterizes the implicit. regularization for L in the weak sense to be constant on {0:]m=.. Thus, if G is continuous, is constant on the closure of it, whose interior contains r).
Remark. Our choice of _ near wo not mandatory. Actually, we can let a(w) h( w) for any h R +R satisfying
(a) For any dataset S the trajectory of GF for L(, starting at 0g converges to (*( as t - 00.
(b) The correspondence - (S) is a local continuous injection.
(c). Do the construction in the proof of Theorem 6.1 (b) repeatedly, each time fixing some 0, and then finding 0 and [5 carefully such that the closure of (e 0 0 n E N is the translation of a "2 -ant of R&M that does not contain 0z- This shows that G(A,0) = G(l + fg 0)) for all f in some 2a-ant of TMM Choose different Og and/or 0 to show that ((,,0) must be constant on each -ant of M whence G(.,0) 0) is constant. Since G(p.q) = G(p - q, 0), G must be constant on R x R
Proof of Theorem 6.1
Lemma A.3 (Lemma 6.1 Suppose that O and a' > 0 on RR For any somple S ((x, v)} C R R and any O, (Wo, ao), the trajectory of GF for L(, starting at On has a long-term limit 0ī E EMs.
We define the j-th 2M -nnt of R be the closure of the set consisting of 0 R such that the sign the i-th component. of 0 equals 2js- - 1, where j (0))2-
20

---

Published in Transactions on Machine Learning Research (10/2023)
Proof. Note that the trajectory of the GF is characterized by
= ((la)(ww)))))))) - ()
(17)
di 2 ((ao(ww)) (zw))
with the initial value w(0) - wo and a()) uo- Multiplying the two equations, we see that
((o y) (oo' (zw))a -2(a)( v))o((rr))
(18)
If x = 0, L( = =(0o))) y1². In this case, the trajectory of GF for L(-5) clearly convergos. Now suppose
that x + O. If ao (xw) f y, then
ad vo (aw)
(19)
zo' (rw)
If (()))())()) = y, then a(l) r0( 0, so 19 also holds. Integrating on both sides of
19
we see that
there is some strictly monotonic function h (depends on x) such that
2 (1) 0 = Mw((t)) h(wo))
(20)
Thus, =(t)=
= h- (h(wo) + a2(()/2 2) and thus the first equation in 17
becomes
= - (ao -1 (h(w)) + a² (t)/2 ag/2)) - y) oxc -1 (h(w)) + d
(21)
Define ((s) = so (xh -1 (h(ww) + x2 - 2)) - y. Tf = = h(ww)) - og/2 then
s²
8²
52
(s()) xh 1
+
+ so
rh -1
+
x(h
b
+
2
2
2
(22)
82
82
82
xh xh~1
+ 2
xh xh-1
+
x(h-
+
2
2
Since strictly increasing when x > and strictly decreasing when x < 0, x(h (((h-1)(6 (s2/2 /2 + 2) is always positive. Thus, sz (2 + 5² 12222x(( (= 22/2) O. Moreover,
xh-1 (252 +22)) o((sh) (
lim lim
(23)
where the right side of the inequality is positive. It follows Φ' is bounded below and thus lim d(a) = to0, so @ has a unique zero ag- This the point to which the a-component of the GF converges; morcover, if wi- h (--((((w)))) + ag² /2 o2/2), then (uj, aj) lies in (:, This completes the proof.
Lemma A.4 (Lemma 6.2 Let o R R+ be differentiable and strictly increasing. Then
(a) Suppose that M = 2. If the implicit regularization for L is characterized by data-independent function G E C³ in the weak sense, then there are some Oo, 0 E R2 such that (G(:00o)le, =0, where the derivatives are taken with respect to the first entry of G.
(b) The result in (a) also holds for general M 2
Proof.
(a) By Lemma 6.1 since and o' > 0, for any dataset S = {(x S)} C R with + and any 0. = (wo, ag), the trajectory of GF for L(,,S) has long-term limit 0 (wā. ab) E L (;) Now, if dg o 0 and S (x, (xo(())))) since
I((On, S) ( - (-ana 4(an0 (rwn)) 0,
(24)
21

---

Published in Transactions on Machine Learning Research (10/2023)
the continuity of ao(w)) y ensures that aj au- Thus, aj -du- Then h(wh) = h(wo)) + a /2 a² 2= h(wo))
(25)
Because h is monotonic, we have w = wy- Thus, 0 (wo. aa)) Morcover,
a(l) (())
a(rw)
lim
lim
e 0 axo (æw))
(26)
o (xwa)
agz0o' (zw))
a(t) Suppose that lim wie Integrating both sides with respect to 2, we can see that there are some non-zero constants A, E R such that
for all R. Then since o' + on R, k + and thus o (arwa)
a(ww)) auk
(og(A)))))))) = agk
log Br).
(27)
Thus,
((rw)) (Bx) (Bx) 1/ak
(28)
A
which implics that is monomial; but then o(0) 0, contradiction. Thus, there must be two 21,22 I such that
o (
σ (22ws)
(29)
4 o' (x)
(1220)
Therefore, by Lemma 5.2
VG((,0o)lo; O.
(30)
(b) Let x * O and let fæ/|2z |z|, bi.... bM- be an orthonormal basis of RM For any parameter (w.zz/ + EMIT w;b,, a):
L(O,)) (ax ( w) y/² |ao 8/2
(31)
Therefore by (a), the trajectory GF for I(, starting at On = (wo, an) with do * 0 ends at a
distinct point Oī = (wi. -ai), and the partial dcrivative Gi., 6g) with respect to x //|=]| and a vanish.
By letting x be the multiples of each the standard basis of AM we can see that Vo),; =
Proof of Theorem 6.2.
(a) Suppose that G E CRM ( is strongly convex. For any Oo, VC(. Oo)le = 0 for at most one 0 E RM,, Fix wy E R M-1 and E RV(0). Since a are strictly positive, Lemma 6.2 says that VG(, (wo; ao))
= 0. By choosing two different values ag, we can see that there are two points at which VG(. 0p) = 0. Thus, G not strongly convex.
(b) Fix wy E RM and do E RV(0). By Lemma 6.2 VG(, (wo, (m)))((m -0) = 0: equivalently, VG(, (0. -2g) = for all ag * Since VG(. is continuous, (G((-0)) = 0. It follows that for any TRM G(- 0) must be constant on the set ((0,p) p) R).
E
Proof of Corollary 0.2
22

---

Published in Transactions on Machine Learning Research (10/2023)
(a) Due to the structure of 9 can apply Lemma 6.1 and 6.2 to each pair (wk, ag). The idea is to fix
any 0n- = (wos: dok k= and any æ E IRd such that the components of * 0 for all 1 I I S d, and g(O,, x) + 0 and 2k=1 (alo'(""wwoo o O. Set S == (æ, -e.--(00. x)). Since L(Oo. S) > 0, the GF for starting at Og is not constant.
For each < k S m we have
θT.
ãz (t) =
(0,5) 2(g(0, x) ( wx((t)
da:
0L
tb% (t)
(0, -((g(0, x) 3)0' oo'((')) (=Twx (a)
Own
This means for any 1 S l: and any 1 Sssd. d,
âx (t)xx)x(t) = (un (4)
x1o0( (x)
By the proof of Lemma 6.2
(sce Lemma A.4 there is some strictly monotonic h depending only
ær and or such that 1 f h(w)(()) h(wa (0)). Thus, applying the proof of Lemına 6.2
we can see that lim an (t)
and lim, wa (t) wor for each k. Moreover, since æt 0
lim dx(()
g x)
10000 (t)
2t Σ k= aok (woL::)
Again, argue in the same way as in Lemma A.4 we conclude that by choosing different æ, 0., G(;, (Was, (=1))=1) Ow, Gi,, (Wok- Gok aox) )==))=)> vanish at (Wos. -0x))==1 for cach S j S m.
Now argue in the same way as in Theorem 6.2 by choosing two different initial points. Then the derivative G vanishes at two points, whence G cannot be strongly convex.
(b) Fix Wol,..., Wom and choose different 0o1...., 00m Since G GMs, VG(, 0)ko, (kk, 20.x 0 for almost all (ao1, aom) E IR.. Thus, for any E (d+m))m G(., () must be constant on the set {(0. pb) : Ple R).
Proposition A.2 (Proposition 6.1 Let E R. Fix a point (I0. yo) R.2 with yo + Let F RR. R, F(p,z)= = (zr)) ( We have
(a) Suppose that [F x 2 Clp w zol" for some C 0 and k near (w, vo). Then for sufficiently small 5 > 0, if < x zol 8, y + 0 and yō (xw) (xyww, there is no R such
that 0 < 1p w| < 8 and (áp)) (no(x)))
(b) Suppose that ō E C and (xow), o' (row) + Also suppose
1
0' (xow)
a" (x(ow) 5 )'(nww
x0
# 0.
(32)
ō (sow)
Then for sufficiently small 8 > 0, 0 1x xul 6, y + and yō(ww) yo there is no p E RR such that 0 < 1p w| < 8 and yā(xp) yoō (xoP)) If, however, DF 2n) = 0 for p or DF(w, x) for near Io, then is power function near wow, i.e., axx) Czd for some C,d E I, when is sufficiently close to xow.
Proof.
(a) Let g(p) = (xp) and go(p) = yoō (ZoP). Suppose that the values of g and coincide at w,p. Then we have
yō (rw) (nō(ro));
(33)
yō ( = (no())
23

---

Published in Transactions on Machine Learning Research (10/2023)
Equivalently, whenever y + 0 and yo + 0,
ā ( ā (zz)) = F(p, 2:) =
(34)
Now by hypothesis, there is some o, > 0 such that for any (p, E IR2 with [F(p, .) 2 Olp
(w, mo)l x < 6,
w -|| zol" > O. But this is equivalent to saying that for sufficiently small 8 > 0,
0 < | - zol < 6, y # O and (zw) = yoō (xow), there is no p E R such that 0 < 1p- w| < 8 and
(σp))) = (zop).
(b) Fix w * 0. Note that
F(p,2) x) = ((zw)o(zop) - ((z))
= [ā(a)e) + 8' (x)w) rn)w + o(r - xo)]0(app)
- [o(zap) + (xoo)) - o/z o mn)o
(35)
=d'
5' ooo
olx zo) (ō(zop) - (()w)) 5' (zop))) + 20)(p w))
(x
It suffices to show that o' o
d' (2op)) aip w) for all p sufficiently near w. Then we can find some C > 0 such that | ( - 5' 0'(zo)) 2 Clp w| and
o((x-an)) w)) & Cl - rollp wl/2. Then
C Ir rollp w/. 2
F((p. x) 2 | no lp w|C o(xx zo)(p w)) 2
(36)
when sufficiently close to xg and p sufficiently close to w. Thus, by (a) there some 8 >> 0 such
that for small enough >> 0, if < x zol 6, y A 0 and yā(xw) = (o there is no p R such that 0 < lp- w| < ō and (xp)) (oop)) Since ā C22 when o' (xow)) o" (xow) o 0, this is equivalent to proving
5' dmoo)) w ((op))
d'(wow) p a(vww) = 2(p -ww w)
(37)
for all near w. Note that we have
o' (x(p)) ('(xow)
('(oo) + + =="(zow)ro( - w) olp - w)
('(20w)
(38)
d" (xow)
Tolp - w) + o(p - ww
8¹ (xow)
and
(xoP)
W P +1
((xow) + a(zow)ao(P w) + o(p w)
p (zow)
p
((sOw)
1 8'(row)
P
+1
(( xg
w) + o(p w)
(39)
p
ō' (row)
Zo w) + o(p w).
p
(xow)
Thus, the left side of 37 becomes
8' (zop)
(xop)
8" (row)
8' d'(xww ]
20 +
((zw)) 2o
(p - w) + olp - w).
(40)
8 (((wow
(xow)
oe wx)
By hypothesis, there some and some
C > such that for any p E (w 8, w + +6),
o' (xow) 8 (a(w))))
20
((ow)
(<(ww)
2c.
(41)
p
This proves
37 which in turn completes the first part of proof.
24

---

Published in Transactions on Machine Learning Research (10/2023)
Now assume that D)) 0 for near zo- Thus, there is neighborhood U of zo which OF Öp (w,x) = zgō (xww) (xow) - o .r' (Iw)) vanishes. Because zo + 0 and by hypoth-
esis, o' (xow) + 0, we can make this U so small that 0 $ U and d'(ww) + 0 for U. This means
d'(ww)
20ō (oo'(row)) 1
(42)
(aw)
Arguing in the same way the proof of Lemma 6.2 can that there are non-zero constants A, B such that
log(A)(zw)) = Too (xrww) log( Br).
(43)
o (row))
Therefore o, and thus o, is a power function. Similarly, when (F = 0 for near w, we can integrate and deduce that a is a power function near w.
Corollary A.2 (Corollary 6.1 Following the notations in Proposition 6.1 all the resulls below hold.
(a) Any a and w, ro such that a power function on neighborhood of xow (this includes ReLU and PReLU and Heoviside) satisfies F = near zu).
(b) For any analytic activation a and any xo, w R. such that the zero locus of the function F(,, ö (xw)) ( (xqw) satisfies
F- = U(p x) E E w EU: xo}
for some neighborhood U S. IR. of (w, we can find sufficiently small 5 > 0 such that if 0 < Iz zol < 5, + O and yo (xw) = yoδ (zow), there is no p R with 0 < Ip w| < and
yō (xp) = (xop)-
If (c)
e² or e then for any so IR, we can fond a sufficiently small ō 0 such that if 0 < I zol < 8, y # O and (aw) yoō (xow)) there is p R with < lp w| and
yō (xp) = v
(d) Let w > O. If I+e-r; for any Do (-o0, w- o0), we can find sufficiently small such that i < xx
xol < 8, y + 0 and yā(ww) (oo(x)), there is no E R with 0 < Ip wl < 8 and (xp) = (xupp)))
Proof.
(a) Note that a is a power function near w if and only if ā is. Therefore, suppose that (xx) = x for some q E I, then for any px sufficiently close to (zo, (z),w),
F(p, x) = (zo)) - (ro)) = 0.
(b) Apply Lojasiewicz distance inequality to F2 on U. Denote & = (p. E R2 : p =p= w) and
le == <)) E IR.2 zo). Since (F22-1 = (0), there are some C, > such that for (p,z) U sufficiently close to zg), we have
[r xx) 2 Cdist ((,,)), F ( (0))*
Cdist ((p, x)), F (0)
C Cmin ((p, 2), f1)² dist (p. (p..)),e)))
C min - xm | lp - w |)}
2 C/ xo -0 w|
This shows that the assumption in Proposition 6.1 (a) is satisfied, the desired result follows.
25

---

Published in Transactions on Machine Learning Research (10/2023)
(c) Note that both ex and e e-=² are (real) analytic functions. We will prove by applying the result in (b). For ((x) = e,; when F(p,x) O we must have
2u =e e =epe 20
which gives zu + zup xp row, i.c., (or zo)(o w) 0. Thus, either p 20. Similarly, for oxx) = =² when F(p, x)) we must have
= =² +'
Thus, x2w? + xzpp² = =2²p² + zzw² which gives (x² - =p)(p² -z/ w²) 0 and this holds when x² 2 or w² pp. Thus, for (p,x) sufficiently close to (w, (o), must have
p w.
The proof above shows that either for o(x) = ex or o(x) =e="" we can find some neighborhood S I²² of xg) such that
(0) nu ((p, EU :p= w/ u EU x== mo)-
Therefore, the desired result follows from (b).
(d) (xx) = 1 1 t Let == Fow.. Therefore,
d'(u)
(u)
= 1 1te=2
(44)
d'(u)
Let denote the root of 1 Ite-z. desired result follows from Proposition
Since E (1, (1, it follows that when u E (-o0, 1) U (2, oo), the
6.1
26


Reviews:
[{"review_id": "KMvrxUB2QD", "reviewer": "Reviewer_rC1y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* The paper tackles an important problem of relevance to the community and can advance our understanding of neural networks. \n* Despite being closely related to previous work, I found the paper brings sufficient novelty and new insights. \n* The formal definitions that the reasoning is built on make sense. \n* The paper is clearly written and well structured. It is easy to read, and I found the simulation particularly clarifying. \n\nWeaknesses: \n* One part that is unclear to me is the definition of the set $\\mathcal{M}_S$. The way the authors describe it suggests that is contains the global minima of the loss on a dataset $S$.  Further, the described mechanisms suggest that implicit regularization selects a minima from this set. However, there is no obvious reason for me why implicit regularization shouldn't bias the loss and therefore lead to a different set of minima (e.g. see \"ON THE ORIGIN OF IMPLICIT REGULARIZATION IN STOCHASTIC GRADIENT DESCENT\" , S. L. Smith et al. 2021). \n* Related to this, the paper could be make clearer by some practical examples on implicit regularization (settings where in plays a role, some insights on its origins, ...). This can help clarify and test the validity of the definition that the authors propose. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper propose a study of implicit regularization of neural network. More precisely, the authors question the data dependence of this type of regularization. Their main contributions are the following: \n* A clear mathematical definition of regularization, that encompasses both implicit and explicit regularization. \n* Building on these definitions, two dynamical mechanisms and derived \"Recipes\" to produce rich classes of 1-hidden-layer networks for which it is impossible to fully characterize implicit regularization with data-independent functions. \n\nThis works builds on previous studies (the most closely related being Vardi & Shamir 2021) and generalize their findings to a broader class of 1-hidden-layer networks. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Building on the previous rubric: \n* Can the author provide examples for implicit regularization, similarly to what they proposed for the explicit category? \n* Can the authors comment on or precise the definition on the set of minima they're study is working with? \n* (Less important and slightly beyond the scope of this work) It would be really impactful if the authors can provide some comments or insights on how to generalize their study to multi-layer networks. ", "broader_impact_concerns": "N/A ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ko3U7Y6G49", "reviewer": "Reviewer_qUML", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- This paper provided formal definition of explicit regularization and implicit regularization (for a gradient flow), and ways to characterize them with data independent functions.\n- It provided two mechanism and associated recipes that allows construction of examples with non-linear neural networks to demonstrate that there are implicit regularizations that are impossible to be fully characterized with data independent function.\n\nWeakness\n\n- The observation that there exist implicit regularizations that cannot be fully characterized by data independent function is important. However, the existence of such examples does not necessarily imply that all (or many) of the implicit regularization of neural networks that are trained in real world data fall in the same category as well. It would be great to have some more discussions regarding this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the limitation of characterizing implicit regularization by data independent functions. How does overparameterized neural networks find solutions that generalize well has been a central topic in deep learning theory. One common perspective is to argue via the implicit regularization of the underlying training algorithm (e.g. SGD). This paper contribute to this topic by showing that there are many implicit regularizations that cannot be described as data independent functions. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bUtUnLp18g", "reviewer": "Reviewer_RN8d", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.** \n\n- The general problem of understanding implicit regularization is important.\n- The manuscript is for the most part well-written and provides good intuition for the authors' construction.\n- The findings are validated by numerical experiments.\n\n**Weaknesses.**\n\n- My main concern is about the claims on the contributions of this work.  The authors stated that their results \"signify the profound data dependency of implicit regularization in general\", but this broad message can already be found in Vardi & Sharmi (2021), and the improvements in the main theorems of this work (relaxing the requirements on the activation) appear somewhat technical.\n\n- While the manuscript contains additional, intermediate results (contribution 2 above) that may be of independent interest, the construction appears to be fairly restrictive (e.g., the resulted training set always contains a single sample), so it is unclear if the constructions are indeed more broadly useful, beyond for the proof of the present results.\n\n- There are also some clarity issues which are easily fixable; see below for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies implicit regularization of gradient flow learning in NN models.  The authors \n\n1. provided formal definitions for implicit and explicit regularization,\n2. proposed two mechanisms that make any data-independent characterization for implicit regularization impossible, and a recipe to construct examples that realize one or both of the mechanisms,\n3. showed that across a wider range of single-hidden-layer NN models, the implicit regularization effect cannot be precisely characterized by data-independent regularization.  \n\nThe results improved upon a previous work (Vardi & Sharmi, 2021) that studied ReLU NNs, primarily by allowing for more general activation functions.  ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most importantly, it would be helpful to provide further discussion that justifies the contribution claims, e.g., how the present results may inspire the study of the data dependency of implicit regularization (in a way that past works do not).\n\nThere are also a few minor issues:\n\n- Definition 4.2, 4.3: you may want to clarify if $\\mathcal{A}$ continues to be defined as above Defn. 4.2, or switch to a different notation to avoid confusion.\n- Example (b) below Defn 4.3: $G$ is not formally defined. \n- You may want to clarify if $\\mathcal{M}_S$ can contain local minima, or if the limit of any GF is always assumed to be a global minima; otherwise statements like Eq. 3 cannot be valid.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xE1kXx6dbc", "reviewer": "Reviewer_ZwaV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n1. The paper is well-structured and provides a clear and detailed explanation of the concepts. The authors' approach to characterizing implicit regularization using data-independent functions is novel and provides a new perspective on understanding the behavior of deep learning models. The proposed overlapping mechanisms and the corresponding examples are insightful and help to illustrate the authors' arguments effectively.\n\n2. The authors provide a mathematical definition and study of implicit regularization, which is a central issue in deep learning theory. This contrast the prior literatures, where the implict regualrization is mostly not well-defined or not rigorous.\n\n3. The authors propose two dynamical mechanisms and provide two recipes for creating classes of one-hidden-neuron NNs that cannot be fully characterized by a type of or all data-independent functions.\n\n4. The paper makes a contribution by highlighting the profound data dependency of implicit regularization in general. It may inspire future studies on the data dependency of NN implicit regularization.\n\n# Weakness\n\n1. The constructions only work for neural networks with only one hidden neuron and it's unclear how can it  generalize to the general neural networks that are closer to the one used in pratice. Thus the results in the paper may not fully represent the complexity and diversity of real-world neural networks.\n\n2. Additionally, the theoretical results only work for continuously differentiable activation function such as sigmoid and softplus, and it's unclear how can we generalize the results to neural networks with activation functions like ReLU.\n\n3. It's not so surprising that the implicit regularization may dependent on the data, especially given the observation that neurla networks can fit the data with random labels perfectly (e.g., Zhang et al., 2017). Therefore, it's unclear to me how the results in the paper can foster our understanding on the implict regualrization even after read this paper.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a thorough investigation on the notion of implicit regularization in neural networks trained using gradient descent. The authors propose two dynamic mechanisms, namely the Two-point Overlapping Mechanism and the One-point Overlapping Mechanism, which they claim can impose strict limitations on the function that characterizes implicit regularization, or potentially render such characterization infeasible. The authors also present specific instances of neural networks with a single hidden neuron and widely used activation functions that can demonstrate each of these mechanisms. Additionally, the authors provide a collection of guidelines for generating diverse categories of one-hidden-neuron neural networks capable of implementing these mechanisms. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide a discussion on 1) how can we genralize the results to neurla networks with more than one hidden neuron; 2) how can we extend the results to neural networks with ReLU activation.\n\n2. Discuss the practical implications of their findings in more detail.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers generally agreed that the manuscript deals with a timely and important topic, is well-written, and delivers novel contributions.  Several comments were raised regarding relevance to practical neural networks, significance over past work (in particular Vardi & Shamir 2021) and certain technical details.  These comments were largely addressed, and in my opinion the paper in its current form is almost ready for publication.  The only point I would further clarify is that by reviewer rC1y about the set M_S comprising global minima.  From my experience in the area assuming convergence to global minima in studying implicit regularization is quite common; I recommend the authors add a short emphasis of this.  Overall the paper is a worthy addition to TMLR.
Decision: Accept (poster)