Global Convergence of SGD For Logistic Loss on Two Layer Neural Nets
Authors: Pulkit Gopalani
Samyak Jha
Anirbit Mukherjee
Venue: Accepted by TMLR ()

Abstract: In this note, we demonstrate a first-of-its-kind provable convergence of SGD to the global minima of appropriately regularized logistic empirical risk of depth $2$ nets -- for arbitrary data with any number of gates with adequately smooth and bounded activations, like sigmoid and tanh, and for a class of distributions from which the initial weight is sampled. We also prove an exponentially fast convergence rate for continuous time SGD that also applies to smooth unbounded activations like SoftPlus. Our key idea is to show that the logistic loss function on any size neural net can be Frobenius norm regularized by a width-independent parameter such that the regularized loss is a ``Villani function'' -- and thus be able to build on recent progress with analyzing SGD on such objectives.

Global Convergence of SGD For Logistic Loss on Two Layer Neural Nets
Pulkit Gopalani
gopalani@umich.com edu
Computer Science and Engineering University of Michigan, Ann Arbor
Samyak Tha
samyakjiaa@iitb..cm
Deportment Mathematics Indian Institute of Technology, Bombay
Anirbit Mukherjee
aubbil.mukkcrreeennnnsseeee....
Department of Computer Science The University of Manchester
Reviewed on OpenReview: https: // openreview. net/ pet//forne forum? id- 9TqAUBB6CC
Abstract
In this note, we demonstrate first-of-its-kind provable convergence of SGD the global minima of appropriately regularized logistic empirical risk of depth 2 nets for arbitrary data with any number of gates with adequately smooth and bounded activations, like sigmoid and tanh, and for a class of distributions from which the initial weight is sampled. We also prove an exponentially fast convergence rate for continuous time SGD that also applies to smooth unbounded activations like SoftPlus. Our key idea to show that the logistic loss function on any size neural net can be Frobenius norm regularized by a bidth-inddepnnden parameter such that the regularized loss is a "Villani function" and thus be able to build recent progress with analyzing SGD such objectives.
1 Introduction
Modern developments in artificial intelligence have been significantly been driven by the rise of deep-learning, The highly innovative engincers who have ushered this A.I. revolution have developed a vast array houris- ties that work get. the neural net to perform "human like" lasks. Most. such successes, can mathematically be seen to be solving the function optimization/"rie minimization" question, minneN (eee[[[(n, =)] where members of N are continuous functions representable by neural nets and & V Support(D) called "loss function" and the algorithm only has sample access to the distribution D. The successful neural experiments can be seen as suggesting that there are many available choices of f, N & D for which highly accurate solutions to this seemingly extremely difficult question can be easily found. This is a profound mathematical mystery of our times
[0, oo) is
This work is about developing our understanding of some of the most ubiquitous methods of training nets. In particular, we shed light on how regularization can aid the analysis and help prove convergence to global min- ima for stochastic gradient methods for neural nets in hitherto unexplored and realistic parameter regimes.
In the last. few years, there has been a surge in the literature on provable training of various kinds of neural nets in certain regimes of their widths or depths, or for very specifically structured data, like noisily realizable labels. Motivated by the abundance of experimental studies has often been surmised that Stochastie Gradient Descent (SGD) on neural net losses with proper initialization and learning rate converges low-complexity solution, one that generalizes when it exists (Zhang et al., 2018).
But, the best of our knowledge convergence result for any stochastic training algorithm applied to the logistic loss for even depth nets (one layer of activations with any kind of non con-linearity), without either

---

assumption the width the data, has remained elusive so far. We recall that this is the most common way to train classifiers facing binary class labelled data.
In this work, we not only take a step towards addressing the above question in the theory of neural networks but we also do so while keeping to a standard algorithm, the Stochastic Gradient Descent (SGD). In light of the above, our key message can be summarily stated as follows,
Theorem 1.1 (Informal Statement of Lemma 3.3). If the initial weights are sampled from an appropriate class of distributions, then for nets with single layer of sigmoid or tanh gates -for arbitrary data and size of the net SGD on appropriately regularized logistic loss, while using constant steps of size O()), will converge. in ! steps to weights at which the expected regularized loss would be c-close to its global minimum.
We note that the threshold amount of regularization needed in the above would be independent of the width of the nets. Further, this threshold would be shown to scale s.t it can either naturally turn out to be proportionately small if the norms of the training data are small or can be made arbitrarily small by choosing outer layer weights to be small. Our above result. is made possible by the crucial observation informally stated in the following lemma which infact holds for more general nets than what is encompassed by the above theorem,
Lemma 1.2. It possible to add a constand amount of Frobenius norm regulurization on the weights, to the logistic loss on depth-2 nets with activations like SoftPlus, sigmoid and tanh gates s.t with no assumptions on the data or the size of the net, the regularized loss would be a Villani function.
Since our result stated above does not require any assumptions on the data, or the neural net width, we posit that this significantly improves on previous work in this direction. To the best of our knowledge, similar convergence guarantees in the existing literature either require some minimum neural net width growing w.r.t. inverse accuracy and the training set size (NTK regime (Chizat et al., 2018; Du et al., 2018b)), infinite width (Mean Field regime (Chizat & Bach, 2018; Chizat, 2022; Mei et al., 2018)) or other assumptions on the data when the width is parametric (c.g. realizable data, (Ge et al., 2019; Zhou et al., 2021)).
In contrast to all these, we show that with appropriate f2 regularization, SGD on logistic loss on 2 layer sigmoid tanh nets converges to the global infimum of the loss. Our critical observation towards this proof is that the above standard losses 2-layer nets for broad class of activation functions function". Our proof get completed by leveraging the relevant results in Shi el al. (2020).
"Villani
Organization In Section 2 we shall give a literature review of existing proofs about guaranteed training of neural nets. In Section 3 we present our primary results - in particular Lemma 3.3 which uses special initialization of the weights to show the global convergence of SGD on regularized logistic loss with #l labelled data and and for gates like sigmoid and tanh. Additionally, in Theorem 3.5 we also point out that for our architecture, if using the SoftPlus activation, we can show that the underlying SDE converges in expectation to the global minimizer in linear time. In Section 4, we give a brief overview of the methods in Shi et al. (2020) and further details are given in Appendix D. In Scction 3.2 we discuss some experiments with synthetic data, which show that there exist nets trained on the loss function considered such that they have high binary classification accuracy near the critical value of the regularizer considered for the proof. Further experiments with MNIST demonstrating similar phenomenon are given in Appendix E. We end in Scction 6 with a discussion of varions open questions that our work motivates. In Appendices A to C one can find the calculations needed in the main theorems' proofs.
2 Related Work
Firstly, we note that in recent times major advances have been made about understanding the statistical properties doing binary classification by neural nets. In Zhou & Huo (2023), the authors consider (=1} labelled data distributed as a Gaussian Mixture Model and the labels satisfying a Tsybakov-type noise conditions with the noise exponent being q. The authors obtain that with probability 1- 5 of sampling data, the difference between the population risk of the empirical risk minimizer and the Bayes' optimal
2

---

risk is upperbounded by Cg { (logn)*(?) T where Cg.d is some constant depending on q and data dimension d. To appreciate this, we note that earlier in Shen et al. (2022), similar bounds for CNNs with logistic loss were obtained. However, unlike the result in Shen et al. (2022), the excess risk bound obtained in Zhou & Huo (2023) for the hinge loss doesn't blow up with respect to the increasing smoothness of the minimizer of the risk over all measurable functions.
In the setting of finite-width neural nets trained on logistic loss for binary classification (Chatterji et al., 2021), it can be shown that if one has (a) small initial loss (poly (#), where n is the number of training data) and (b) 'smoothly approxinately ReLU activation function', then the loss converges al a rate of ( over steps of gradient descent. But to ensure the smallness of the initial loss, this result needs to assume large width which scales polylogarithmically with inverse of the confidence parameter. In that limited sense this can be seen to be belonging to the larger framework of proofs at asymptotically wide nets which we review as follows.
Review of the NTK Approach To Provable Neural Training: One of the most popular parameter zones for theory of provable training of nets has been the so so-called "NTK" (Neural Tangent Kernel) regime -hheee the width is a high degrec polynomial in the training set size and inverse accuracy (a somewhat unrealistic regime) and the net's last layer weights are scaled inversely with width as the width goes to infinity. (Du et al., 2018a; Su & Yang, 2019; Allen-Zhu et al., 2019b; Du & Lee, 2018; Allen-Zhu et al., 2019a; Arora et al., 2019b; Li et al., 2019; Arora et al., 2019a; Chizat et al., 2018; Du et al., 2018b). The core insight in this line of work can be summarized as follows: for large enough width, SGD with certain inilializalions converges lo a function that fits the data perfectly, with minimum norm in the RKHS defined by the neural tangent kernel- which gets specified entirely by the initialization (which is such that the initial output is of order onc). A key feature of this regime is that the net's matrices do not travel outside a constant radius ball around the starting point a property that is often not true for realistic neural net training scenarios.
In particular, for the case of depth nets with similarly smooth gates as we focus on in Song et al. (2021) global convergence of gradient descent was shown using number of gates scaling sub-quadratically in the number of data- which, to the best of our knowledge, is the smallest known width requirement for such convergence in classification setup. On the other hand, for the special case of training depth 2 nets with ReLU gates on cross-entropy loss for doing binary classification, in Ji & Telgarsky (2020) it was shown that one needs to blow up the width only poly-logarithmically with target accuracy to get global convergence for SGD.
Review of the Mean-Field Approach To Provable Neural Net Training: In a separate direction of attempls lowards provable training of neural nets, works like Chizat & Bach (2018) showed that a Wasserstein gradient flow limit of the dynamics of discrete time algorithms on shallow nets, converges to a global optimizer if the convergence of the flow is assumed. We note that such an assumption very non-trivial because the dynamics being analyzed in this setup is in infinite dimensions a space of probability measures on the parameters of the net. Similar kind of non asymptotic convergence results in this so so-called 'mean- field regime' were also obtained. et al., 2018; Fang et al., 2021; Chizat & Bach, 2018; Nguyen & Pham, 2020; Sirignano & Spiliopoulos, 2022; Ren & Wang, 2022). The key idea in the mean-field regime is to replace the original problem of neural training which is a non-convex optimization problem in finite dimensions by a convex optimization problem in infinite dimensions - that of probability measures over the space of weights. The mean field analysis necessarily require the probability measures (whose dynamics is being studied) to be absolutely-continge
and thus de facto it only applies to nets in the limit of them being infinitely wide.
We note that the results in the NTK regime hold without regularization while many cases the mcan-field results need it. (Mei et al., 2018; Chizat, 2022; Tzen & Raginsky, 2020).
In the next subsection we shall give a brief overview of some of the attempts that have been made to get provable deep-learning at parametric width.
Need And Attempts To Go Beyond Large Width Limits of Nets The essential proximity of the NTK regime to kernel methods and it being less powerful than finite nets has been established from multiple points of view. (Allen-Zhu & Li, 2019; Wei et al., 2019).
3

---

In He & Su (2020), the authors had given a very visibly poignant way to see that the NTK limit is not accurate representation of a lot of the usual deep-learning scenarios. Their idea was to define a notion of "local elasticity" when doing a SGD update on the weights using a data say æ, it measures the fractional change in the value of the net at a point x' as compared to I. It's casy to see that this is a constant function for linear regression as is what happens at the NTK limit (Theorem 2.1 Lee et al. (2019)). But it has been shown in Dan et al. (2021) that this local-clasticity function indeed has non-trivial time-dynamics (particularly during the early stages of training) when a moderately large neural net is trained on logistic loss.
Specific to 2epth-2 nets as we consider here there is a stream of literature where analytical methods have been honed to this setup to gel good convergence results without width restrictions while making other structural assumptions about the data or the net. Janzamin et al. (2015) was one of the earliest breakthroughs in this direction and for the restricted setting of rcalizable labels they could provably get arbitrarily close to the global minima. For non-realizable labels they could achieve the same while assuming a large width but in all cases they needed access to the score function of the data distribution which is a computationally hard quantity to know. In a more recent development, Awasthi et al. (2021) have improved over the above to include ReLU gates while being restricted to the setup of realizable data and its marginal distribution being Gaussian.
One of the first proofs of gradient based algorithms doing neural training for depth-2 nets appeared in Zhong et al. (2017). In Ge et al. (2019) convergence was proven for training depth-2 ReLU nets for data being sampled from symmetric distribution and the training labels being generated using 'ground truth' neural net of the same architecture as being trained the so-called "Teacher Student" setup. For similar distributional setups, some of the current authors had in Karmakar et al. (2020) identified classes of depth-2 ReLU nets where they could prove linear-time convergence of training - and they also gave guarantees in the presence of a label poisoning attack. The authors in Zhou et al. (2021) consider another Teacher-Student Student setup of training depth 2 nets with absolute value activations. Tn this work, authors can get convergence in poly(d, (d, )) time, in a very restricted setup of assuming Gaussian data, initial loss being small enough, and the teacher neurons being norm bounded and 'well-spaarated (in angle magnitude). Cheridito et al. (2022) get width independent convergence bounds for Gradient Descent (GD) with ReLU nets, however at the significant cost of having the restrictions of being only an asymptotic guarantee and assuming an affine target function and one dimensional input data. While being restricted to the Gaussian data and the realizable setting for the labels, an intriguing result in Chen et al. (2021) showed that fully poly-time learning of arbitrary depth ReLU nets is possible if one is in the "black-box query model".
Related Work on Provable Training of Neural Networks Using Regularization Using a regular- izer is quite common in deep-learning practice and in recent times a number of works have appeared which have established some of these benefits rigorously. In particular, Wei et al. (2019) show that for a specific classification task (noisy-Xo -ORR definable in any dimension d, no NTK based layer neural net can succeed in learning the distribution with low generalization error in old2 samples, while in O(d) samples one can train the neural net using taabennissty-norrn regularization. Nakkiran et al. (2021) show that for a specific optimal value of the lg- regularizer the double descent phenomenon can be avoided for linear nets and that similar tuning is possible even for real world nets.
In the seminal work Raginsky et al. (2017), it was pointed out that one can add regularization to a gradient Lipschitz loss and make it satisfy the dissipativity condition so that Stochastic Gradient Langevin Dynamics (SGLD) provably converges to its global minima. But SGLD is seldom used in practice, and to the best of our knowledge it remains unclear if the observation in Raginsky et al. (2017) can be used to infer the same about SGD. Also it remains open if there exists neural net losses which satisfy all the assumptions needed in the above result. We note that the convergence time Raginsky et al. (2017) for SGLD is (2) using an O (e*) learning rate, while in our Theorem 3.3 SGD converges in expectation to the global infimumm of the regularized neural loss in time, (+) using a (e) step-length.
In summary, to the best of our knowledge, it has remained an unresolved challenge to show convergence of SGD for logistic loss on any neural architecture with a constant number of gates while not constraining the distribution of the data to specific functional form. In this work, we exploit the use of some regularization
4

---

to be able to resolve this optimization puzzle in key result, Lemma 3.3 and in our experiments show that the regularization needed may not harm downstream classificntion performance. Thus we take step towards bridging this important lacuna in the existing theory of stochastic optimization for neural nets in general.
3
Setup and Main Results
We start with defining the neural net architecture, the loss function and the algorithm for which we will prove our convergence results.
Definition 1 (Constant Step-Size SGD On Depth-2 Nets). Let, R (applied elementwise for vector valued inputs) be atleast once differentiable activation function. Corresponding to it, consider the width p, depth neural nets with fized outer layer weights a E R and trainable weights W e Rexd as,
Fd f(æ; a. W) = a (Wo)
Them, corresponding to given set of binary training dala (æi, Vs) E IRd (+1, -1), with |æxil2 S Br, i I....,n define the individual data logistic losses ((W = log( [ t v.fi(W)). Then for any X 0 let the regularized logistäc empirical risk be,
1 Σ [ ni
L(W)
(3.1)
Correspondingly, consider SGD with step-size as,
W - Σ (w+ sAW*
ic
where Bg is randomly sampled mini-batch of size b.
Definition 2 (Properties of the Activation o). Let the a used in Definition be bounded s.l. (o(x)) Ba, C Lipsshchit and I'g smooth. Further assume that 3 a constant vector e and positive constants Ba, MD and M' s.t (0)= = c and Vx (2)o0()))= MD. M
In the framework of Shi et al. (2020), the required step-length for convergence of the above SGD and the corresponding measure of the rate of convergence of the loss depend on the gradient Lipschitz smoothness and the Poincaré constant of the Gibbs's measure the loss function, respectively. Hence, towards stating the final results, in terms of the above constants we can now quantify these as follows,
Lemma 3.1 (for Classification with Logistic Loss). In the selup of binary classification contained in Definition 3.1, and the definition MD and L as given in Definition 2 above, there exists constant de MoLB2la12 s.t AX> de and s 0 the Gibbs measure exp exp((22 corresponding constant Xg-
(-2() 2f. satisfies Poincaré type inequality with the
Moreover, if the activation satisfies the conditions of Definition then 3gLip (f.) 0 such that the empirical loss is gLip (L) smooth and we can bound the smoothness coefficient of the empirical loss as,
gLip(L) s vpl / +
2 |ell, + la Bo
My
(3.2)
4
4
The precise form of the Poincaré-type inequalities used above is detailed in Theorem 4.1.

---

Theorem 3.2 (Bounds on Error for Arbitrary Initialization.). We continue in the setup of lo- gislic loss from Definitions and 2 and Lemma 3.1. For any 8 O, define the probabilily measure exp (- 2 Z. being the normalization factor. Then, T and desired accuracy > 0, 3 constunts A(L), B(T,L) and C(s, L) 8. if the above SGD execuled at a conslant step-size
Ns = exp
(e, == min gLip(i)) (A(L) B(T))
with the weights W initialized from any distribution with p.d.f Pinitial T (,2()))) and then, the ervor the end of having taken T. SGD steps con bounded as,
EL(W*)- - inf L(W) set C(s", Pinitialll - Me p t Ara W
where
|Pinttill - Mor 11x = (ax (Pinitial()) - Mer) )² H dx)
measures the "gap' between the initial distribution and the stationary distribution
Lemma 3.3 (Global Convergence of SGD on Sigmoid and Tanh Neural Nets of 2 Layers for Any Width and Any Data for Binary Classification With Logistic Loss). We continue in the setup of logistic loss from Definitions 1 and 2 and Lemma 3.1. For any 8 > O, define the probabilily measure
n1 , exp _2(WW) ) Zo being the normalization factor. Then, v T O, and desired accuracy, 0, 3 constants A(L), B(T,L) and C(s,L) s.t if the above SGD is executed at constant step-size
(5 min (gLip(L) 2 (A(L) B(T, L))
with the weights WO initialized from a distribution with p.d.f Pinitial E L2 n,- and | - M1 1l, S - -e then, in expectation, the regularized empirical risk of the net, L would converge to its global infonum, with the rate of convergence given as,
L) I)
BL(W#) inf L(W) W
The proof of Theorem 3.2 is given in Section 5 and the proof of Lemma. 3.1 can be read off from the caleulations done part of the proof of Theorem 3.2. Lemma 3.3 can be obtained along the same lines Theorem 3.2 as follows.
Similar to Theorem 3.2, we consider SGD executed at a constant step size s= $ and as earlier this constant is defined in terms of the constants A(L), BTT, C(s, L.. Further, invoke the condition, that consider the initial weights of the SGD being sampled from an initial distribution with p.d.f Pinitial such that,
CA.T
| M1s 1s
C(s L)
Then for == T ; combining the above into Theorem from Shi et al. (2020) (as was also used to get the guarantee of Theorem 3.2) we get the guarantee in Lemina 3.3,
Bi(W*)- inf i(W) +C(s', i) Pinitial Hor w Arank o W
2 2

---

We make a few quick remarks about the nature of the above guarantees, Firstly, we note that the "time horizon" " T above is a free parameter which in turn parameterizes the choice of the step-size and the initial weight distribution. Choosing a larger 7' makes the constraints on the initial weight distribution weaker at the cost of making the step-size smaller and the required number of SGD steps larger. But for any value of T, the above theorem guarantees that SGD, initialized from weights sampled from a certain class of distributions, converges in expectation to the global minima of the regularized empirical loss for our nets for any data and width, in time O(t) using learning rate of (()).
Secondly, we note that the phenomenon of a lower bound on the regularization parameter being needed for certain nice learning theoretic property to emerge has been seen in kernel settings too. (Yang et al., 2017).
Also, to put into context the emergence of a critical value of the regularizer for nets as in the above theorem, we recall the standard result, that there exists optimal value of the fz-regularizer at which the excess risk of the similarly penalized linear regression becomes dimension free (Proposition 3.8, Bach (2022)). However, we recall that the quantities required for computing this "optimal" regularizer are not knowable while training and hence it is not practically implementable. Thus, we see that for binary classification, one can define a notion of an "optimal" regularizer and it remains open to investigate if such a similar threshold of regularization also exists for nets. Our above theorem can be seen as step that direction.
Thirdly, we note that the lowerbounds on training time of neural nets proven in works like Goel et al. (2020) do not apply here since these are proven for SQ algorithms and SGD is not of this type.
Finally, note that the threshold values of regularization computed above, de do not explicitly depend on the training data or the neural architecture, consistent with observations in Anthony & Bartlett (2009); Zhang et al. (2021). It depends on the activation and scales with the norm of the input data and the outer layer of weights.
For intuition, suppose in the binary classification setting we set the outer layer weights s.t we have |a||2 B, 1. This leads to Ae= MpL, For the sigmoid activation, (z)), by caleulations as above would get, de in this case (say 2 to be this results in,
g² Since 3 1 is the most widely used sctting for the above sigmoid activation,
32
s 0.03125
(3.3)
3.1 Global Convergence of Continuous Time SGD on Nets with SoftPlus Gates
In, Shi et al. (2020) the authors had established that, if the loss L is gradient Lipschitz, then over any fixed time horizon T > O, as s + 0, the dynamics of the SGD in Definition 1 is arbitrarily well approximated (in expectation) by the unique global solution that exists for the Stochastic Differential Equation (SDE),
(f) dt VsdB(t)
(SGD-SDE)
(3.4)
where Bt) is the standard Brownian motion. The SGD convergence proven in the last section critically uses this mapping to a SDE. In Shi al. (2020) it was further pointed out that if we only want to get non-asymplotie convergence rate for the continuous time dynamics, the smoothness of the loss function is not needed and only the Villani condition suffices. In this short section we shall exploit this to show convergence of continuous time SGD on L. with the activation function being the unbounded 'SoftPlus! Also, in contrast to the guarantee about SGD in the previous subsection here we shall see that the SDE converges exponentially faster ie al a linear rale.
Definition 3 (SoftPlus activation). For G > 0, x E R, define the SoftPlus activation function
SoftPlusg(2) 1 log, (1 exx((x)))
Remark.
Note that lim SoftPlus = ReLU(x). Also note that for f(x) = SoftPlusg(z).. f(x)= = 0z()) (sigmoid function defoned above) and hence [f (z)) MD for MD = and f(x: is I.- Lipschitz for I
7

---

Recall the following fact that proven as part of Lemma 3.1,
Lemma 3.4. There exists constant d MDLB
V X A. & the Gibbs' measure ) Ze being the normalization factor, satisfies Poincaré-type type inequality with the cor-
2
H. 1 exp (0pp(()))) a responding constant X
Theorem 3.5 (Continuous Time SGD Converges to Global Minima of SoftPlus Nets in Linear Time). We consider the SDE as given in Equation 4.1 on Frobenius norm regularized logistic empirical loss on depth-2 neural nets as specified in Equation 8.1, while using oxx) SoftPlus for 3 0, the regularization threshold being s.t X > de MpLB Jali and with the weights Wo being initialized from distribution with p.d.f Pinitial (t,
2
Then, for any S L(S,L) and C(s, L), increasing function of 8, s.t for any step size 0 min 20(3.T] S} and for t2 1 h, log 20(e, [ommen we have that,
BL(W(()) - mi L(w) ( sc. W
Proof. The PlutPlus function Lipschitz, hence using the same analysis in (Section 5), can claim that for X re the loss function in Definition 1 with SoftPlus activations is a Villani function (and hence confining, by definition).
Then, from Proposition 3.1 of Shi et al. (2020) it follows that, C(s, L): an increasing function of s, that satisfies,
BL(W.(() -EI C(s, (), [) M A..t
From Proposition 3.2 of Shi et al. (2020) it follows that, for any S> O, for sE (0,5), G(S, i.) that quantifies the excess risk the stationary point of the SDE as,
((W() min L G(S, W
Combining the above, the final result claimed follows as in Corollary 3.3 in Shi al. (2020).
3.2
An Experimental Demonstration of the Maintenance of Classification Accuracy At Various Regularizations at Different Widths
For further illustration of the ramifications of the novel convergence thcorems shown above, in here we present some experimental studies of doing binary classification by training depth 2 sigmoid activated nets with the regularized loss considered in the above convergence proofs. And will be using the normalizations that correspond to the theoretically needed threshold value of the regularizer being X 0.03125 (Equation 3.3).
We sampled the data from clearly separable dataset with margin data vectors in d-dimensions were sampled as a n x d normally distributed matrix whereby after sampling each row vector was normalized to have unit norm. The data whose last coordinale were > 0.2 were assigned label +1 and where the last coordinate was < -0.2 was assigned label -1 and the rest of the data were discarded. In our experimental setting, we fixed to = 10. The data were split into being 20% test data and the rest used for training.
Then we simulate SGD based training on the above data for multiple neural nets at various values of À in [0, Ac] and for neural net widths p. The step-length in the experiments constant across all widths and lambda, across all settings.
The elements of the (trainable) weight Matrix Wo of dimension px were initialized from a standard normal distribution, ie W, ~ ~O, Ipxa). Likewise, the elements of the (fixed) outer layer a, of dimension p were sampled (0, Tıxp) and then normalized.
8

---

For all experimental settings the neural networks were trained for 500 epochs, and with maini-batch size of 256. At the end of training we measured the test accuracy of classification as the downstream metric of measuring the goodness of training.
As shown in the experimental graph (Figure 1), we demonstrate examples of nets trained on regularized logistic loss showing remarkable accuracy for regularization s d even though the model was not been exposed the 0- criteria during training.
The code for the experiments can be found at this Colaboratory File.
Accuracy dfferent nicth (ot, regalarter (1)
10
pa 1120
0.800
0035
0.330
0.95
0.20
0.25
0,330
Figure Test Accuracy across various widths p and regularizer À
Thus we have demonstrated that the threshold amount of regularization that was needed for the proof of convergence may not at all harm the downstream performance metric of classification.
For further insights, the reader are detailed. These experiments showcase that the regularized loss function considered in the aforestated theorems can be trained via. SGD to achieve remarkable classification performance on real data too.
Appendix E, where additional experiments the MNIST dataset
4 Overview of Shi et al. (2020)
In Section 5, will give the proof for our Theorem 3.2. As relevant background for the proof, in here we shall give a brief overview of the framework in Shi et al. (2020), which can be summarized as follows suppose one wants to minimize the function L(W) == Σt (WW,, where i indexes the training data, W is in the parameter space (the optimization space) of the loss function and İ, is the loss evaluated the 8th -dtaaapoi... On this objective, a constant step-size mini-batch implementation of the Stochastic Gradient Descent (SGD) consists of doing the following iterates, W W & E. (WFs, where the sum is over a mini-batch (a randomly sampled subset the training data) of size b and s is the fixed step-length. In, Shi et al. (2020) the authors established that over any fixed time horizon T > O, as + 0, the dynamics of this SGD is arbitrarily well approximated (in expectation) by the Stochastic Differential Equation (SDE),
(SGD SDE)
(4.1)
where B(t) is the standard Brownian motion. We recall that the Markov semigroup operator P, for stochastic process X₁ and its infinitesimal generator L are given as, P.f(x) = E[f(X)) Xo = = and CJ = limmro R.f-L
Invoking the Forward Kolmogorov equation a,f = LT one obtains the following Fokker Planck Smoluchowski PDE governing the evolution of the donsity of the SDE,
0p: (Vp.. vī) p. Ap.
(FPS)
(4.2)
at.
2
9

---

Further, under appropriate conditions on L the above implies that the density Ps(t) converges exponentially last to the Gibbs' measure corresponding to the objective function ie the distribution with p.d.f
(W)
Z, exp
(4.3)
where Zg is the normalization factor. The sufficient conditions on L that were shown to be needed to achieve this "mixing" and to know rale for it, are that of L be a "Villani Function" defined below,
Definition 4 (Villani Function (Villani (2009); Shi et al. (2020)))- A map f F: R is called Villani function if it satisfies the following conditions,
1. fe C0
2. |a [(x) +o0
J exp (-2((a) dx V
4. lim (-Af(x)= + [Vf(()))))= + +o0 V
Further, any f that satisfies conditions 1 is said to be "confining"
From Lemma 5.2 Shi al. (2020), the empirical the population risk, L, being confining is sufficient for the FPS PDE (equation 4.2) evolve the density of SGD-SDE (equation 4.1) to the said Gibbs' measure.
But, to get non-asymptotic guarantees of convergence we need Poincaré-type inequality to be satisfied (as defined below) by the aforementioned Gibbs' measure Pa. A sufficient condition for this Poincaré-type inequality to be satisfied is if a confining loss function L also satisfied the last condition in definition 4 (and is consequently a Villani function).
for the SDE (Corollary 3.3, Shi et al. (2020)),
Theorem 4.1 (Poincaré-type Inequality (Shi et al. (2020))). Given a f : Bd + R which is Villani Function (Definition 4), for any given s O, define a measure with the density, p₂(x)) z, e is normalization factor. Then this (normalized) Gibbs' measure μs satisfies Poincere-type type inequality i.e a D > 0 (determined by f) s.t 4h C (IR") we have,
( (-2
where Z,
Var pa [h]
2A. E. [Ivh
The reader can see Appendix D) for a more detailed sketch of the key proof in Shi et al. (2020) about why this SGD-SDE considered above mixes to a Gibbs's distribution for objectives being the Villani function
The approach of Shi et al. (2020) has certain key interesting differences from many other contemporary uses of SDEs to prove the convergence of discrete time stochastic algorithms. Instead focusing on the convergence of parameter iterates W+ they consider the dynamics the expected error i. B[L(W**),, for Ż being the empirical or the population risk. This leads a transparent argument for the convergence of [[](( to inf T. T(W), by leveraging standard results which help pass from convergence guarantees the SDE to convergence of the SGD.
We note that Shi et al. (2020) achieve this conversion of guarantees from SDE to SGD by additionally assuming gradient smoothness of and we would show that this assumption holds for the natural neural net loss functions that we consider.
5 Proof of Theorem 3.2
Proof. Note that L being confining function can be easily read off from Definition 4. Further, as shown in Appendix A, the following inequalities hold,
10

---

[W) (xx Ml | - W|] M MD (1 [ ||لaل|ella
2
2
AwwL s M + |all2 [B, ||a|| (1c|2 + LB2 ))) (M/ xd]
(5.1)
Combining the above two incqualitics we can conchude that, functions 91, 92: 93 such that,
[ -ww.://Awww22004.00 W g2 8) B3(,))
where in particular,
91 (1,8)) = 2 2A I. 2
Hence we can conclude that for A> >= 2M a 2 vs> 0, 1 L Ww diverges ||W] +00; since gi (A, s) > O. The key aspect of the above analysis being that the bound on Aww does not depend on [W]] Thus we have, that the following limit holds,
( (L - Awwl)=+o =00
lim +00
for the range of X as given in the theorem, hence proving that is Villani function.
Towards getting an estimate of the step-length as given in the theorem statement, we also show in Appendix B that the loss function is gradient Liipschtz with the smoothness coefficient being upperbounded as,
gLip(L) s vpl MB +
2 |ell2 + ||all Bo
M Mb
4
4
Now can invoke Theorem 3 (Part 1), Shi et al. (2020) with appropriate choice of given in the theorem statement to gel the result given in Theorem 3.2. In Appendix C one can find discussion of the computation of the specific constants involved in the expression for the suggested step-length s". j
6 Conclusion
To the best of our knowledge, in this work, we have shown the first proof of convergence of SGD to the global minima of logistic loss on a neural net whilst not making any assumptions about the data or the width of the net. Our result relied on the convergence of discrete-time algorithms like SGD to their contimuous time counterpart (SDEs) a theme that has lately been an active field of rescarch.
We recall that Ji Telgarsky (2020) among the most related works to this as shares with us the same SGD algorithm, primary loss function, neural architecture, and data labels. Their proof exploits specific properties of the (leaky) ReLU like positively homogeneous activation function and is limited to asymptotically wide networks. In contrast, our convergence result (Lemmn 3.3) applies to activation functions like tanh and sigmoid not covered by them and most importantly accommodates arbitrary data and network widths. But to achieve these flexibilities we needed to exploit a parametric (in data norm and last layer norm) amount of regularization and impose certain constraints on the distribution from which the initial weights are sampled.
By juxtaposing these two results, multiple intriguing rescarch directions for the immediate future are revealed which can significantly advance our understanding of the provable training of neural networks. Specifically, advocate for further investigation into reformulating the constraints on the initial weight distribution in more intuitive terms. It could also be promising to explore whether natural weight initialization schemes adhere to the sufficient criteria we require. We also point out that experiments suggest that convergence as we prove can happen at lower values of regularization (possibly in a data-dependent way) and hence that suggests trying for tighter analysis to show that neural losses can be Villani functions.
We posit that trying to reproduce our Theorem 3.3 using a direct analysis of the dynamics of SGD could be fruitful venture leading to interesting insights. Our results also motivate new direction of pursuit in
11

---

deep-learning theory, centered around understanding the nature of the Poincaré constant of Gibbs' measures induced by neural net losses.
Our experiments further demonstrated that there exists neural nets and binary class labelled data such that optimizing on our provably good smooth loss functions also does highly accurale classification. This motivates a fascinating direction of future pursuit about the phenomenon of classification calibration or Bayes consistency icc be able to analytically identify cascs where convergence guarantoes as given here could be extended to guarantees on the classification error.
Lastly, given the new method of proving neural training by SGD that has been initiated in this work, it naturally begets the question if these proof techniques could also resolve similar mysteries for more exotic loss functions and neural architeclures that are in use.
References
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advonces in Newral Information Processing Systems, pp. 9015-9025, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advonces in neural information processing systems, pp. 6155 6166, 2019a.
Zeyuan Alu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242 242-252, 2019b.
Martin Anthony and Peter I. Bartlett. Neural network learning: Theoretical foundations, 2009.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and generalization for overparameterizee two-layer neural networks. In International Conference on Machine Learning, pp. 322 332, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Newral Information Processing Systems, pp. 8139 8148, 2019b.
Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. Efficient algorithms for learning depth-2 neu- ral networks with general relu activations. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 13485 13496. Curran Associates, Inc., 2021. URL https://proceedngg.eett www.rips.cccppper//2..0 Paeeerappppp...
Francis Bach. Learning Theory from First Principles. 2022.
Niladri S Chatterji, Philip M Long, and Peter Bartlett. When does gradient descent with logistic loss interpolate using deep networks with smoothed relu activations? In Conference Learning Theory, pp. 927 1027. PMLR, 2021.
Sitan Chen, Adam R Klivans, and Raghu Meka. Efficiently learning any one hidden layer relu network from queries, 2021. URL https:/ //atsi arxiv. wwtpxivv.rr///e abs/2111 04727.
Patrick Cheridito, Armulf Jentzen, and Florian Rossmannek. Gradient descent provably escapes saddle points in the training of shallow relu networks, 2022. URL https://arxiv.org/aaaaa wrggabs/22000
Lénaïe Chizat. Mean-field langevin dynamics Exponential convergence and annealing. Transactions Machine Learning Research, 2022. URL http:///ppppppeeeeeeeeeeeoooo//p het/
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport In Advonces in neural information processing systems, pp. 3036-3046, 2018.
12

---

Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2018. doi: 10.44550/ARXXTV1111200000 URL
07956.
Soham Dan, Phanideep Gampa, and Amirbit Mukherjee. Investigating the locality of neural network training dynamics, 2021. URL. https: http:///wwww..ooaa//////////////
Simon Du and Jason Lee. On the power of over-paramet in neural networks with quadratic activation. In International Conference on Machine Learning, pp. 1329-1338, 2018.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks, 2018a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks, 2018b. URL https://arxiv.. http:::///rri.oorrr////111111110 02/000000001000
L.C. Evans. Partial Differential Equations. Graduate studies in mathematics. American Mathematical Society, 2010. ISBN 9780821849743, URL https://books. google. co. wtt.o/ooss.ddddooooeeeee.eeeeee. EJrCQC.
Cong Fang, Jason Lee, Pengkun Yang. and Tong Zhang. Modcling from features: a mcan-field framework for over-parameterizeed deep neural networks. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 1887 1936. PMLR, 15 19 Aug 2021. URL https: https://proceeddngg.. mlr preess/1144ffagg// html.
Rong Ge, Rohith Kuditipudi, Zhize Lá, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. In International Conference on Learning Representations, 2019. URL forum?id-Hixiper
net/
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pD. 3587 3596. PMLR, 13 18 Jul 2020, URL https://proceeddee press/v119/gs goa000 html.
mlr.
Hangfeng He and Weijie Su. The local elasticity of neural networks. In International Conference on Learning Representations, 2020. URL https: attps://openreviier http://wwwwwee.rourr/eeeee net:/torum/id--tx/W.......
Majid Janzamin, Hanie Sedghi, and Anima Anaudkumar. Beating the perils non-convexity: Guaranteed training of neural networks using tensor methods, 2015. URL https://arxiv: http:///awwwwwoo////////esee//// /106 08473.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2020. URL https://openreviex.. httpp////pppprereeee.eee/////a//
Sayar Karmakar, Anirbit Mukherjee, and Theodore Papamarkou. Depth-2 neural networks under a data- poisoning attack, 2020. URL
http:/wwww.rgg/////....... 01699.
Jaehoon Lee, Lechao Xiso, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint arXit:1911.00800 2019.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115((3):17765 E7671, 2018. doi: 10.1073/pmas.10057911. URL https://ww: htt////wwwppas....////////// pnas. porg/doi/abbe 1ttp//100..77/paass. http://pnna..8865911155555 1806579115.
Prectum Nakkiran, Prayaag Venkat, Sham M. Kakado, and Tengyu Ma. Optimal regularization can mit- igate double descent. In International Conference on Learning Representations, 2021. URL https:
13

---

Phan-Minh Nguyen and Huy Tuan Pham. A rigorous framework for the mean field limit of multilayer neural networks. CoRR, abs/2001.11443, 2020. URL
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1674 1703. PMLR, 07 10 Jul 2017. URL https://proceeddin mlr http:/ceeiiii.......pra/a////rre pptsss/66/raginskyyllll htmm.
Zhenjie Ren and Songbo Wang. Entropic fictitious play for mean field optimization problem, 2022. URL
https://arxing
Guohao Shen, Yuling Jiao, Yuanyuan Lin, and Jian Huang. Approximation with cnns in sobolev space: with applications to classification. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (ods.), Advances in Neural Information Processing Systems, volume 35, pp. 2876-2888. Cur- ran Associates, Inc., 2022. URL https: http://prreeein....e.eeee neurips http:///cccpppp....ff///////e//p fttp////////pee/22///eeeeee 36600eaf774422f10651ff7988680000 Papel--aa------a Conferencee pdf.
Bin Shi, Weijie J. Su, and Michael I. Jordan. On learning rates and schrödinger operators. 2020. doi: 000.://or.......0/50000//2000000
URL
Justin A. Sirignano and Konstantinos Spiliopoulos. Mean field analysis of deep neural networks. Math. Oper. /287/moor 2020.
Res., 47(1):120-155) 152, 2022. doi: 10. 2008://m0r.220011111 URL 1118.
Chaehwan Song, Ali Ramezani-Kebrya Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Sub- quadratic overparamettrrizaion for shallow neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL attps://openreriew..r wwt.:/orormidd-/hhhheeee
Lili Su and Pengkun Yang. On lcarning per-paramettrized neural networks: A functional approximation perspective. In Advances in Neural Information Processing Systems, pp. 2637-2646, 2019.
Belinda Tzen and Maxim Raginsky. A mean-field theory of lazy training in two-layer neural nets: entropic regularization and controlled mekean-vlasov dynamics. CoRR, abs/2002.01987, 2020. URL https:// arxiv. arziv.orgg/ab//202.0112 01980
Cédric Villani. Hypocoercivity. 2009.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimiza- tion of neural nets vs their induced kernel. Tn Advances in Neural Information Processing Systems, pp. 9709 9721, 2019.
Yun Yang, Mert Pilanci, and Martin J. Wainwright. Randomized sketches for kernels: Fast and optimal nonparametric regression. The Annals of Statistics, 45(3):901 1023, 2017. doi: 10.1214/16-A0S147.
URL https://doi. http::///oooooo//..// org/10..//..... wtt./..../////........... 12141111-111
Chiyuan Zhang, Qianli Liao, Alexander Rakhlin, Brando Miranda, Noah Golowich, and Tomaso Poggio. Theory of deep learning iib: Optimization properties of sgd, 2018. URL https://arxiv wwwg//////////////
02254.
Lin Zhang, Ling Feng, Kan Chen, and Choy Heng Lai. Edge of chaos as a guiding principle for modern .09437.
neural network training, 2021. URL
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartleut, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks, 2017. URL https://arxiv.. wttp://wwwwrrabb//o.oooo
Mo Zhou, Rong Ge, and Chi Jin. local convergence theory for mildly over-parameteriinn two-layer neural network. In Mikhail Belkin and Samory Kpotufe (ods.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4577-4632, PMLR, 15-19 Aug 2021. URL https:// https::/proceeediiiiii /pppee/e//cocec//n...... mlr. wwtppp//ee////ooe/eeee .tml.. htt.eeedddiiaa......ee//s///e/ee
14

---

Tian-Yi Yi Zhou and Xiaoming Huo. Classification of data generated by gaussian mixture models using deep relu worworks. Xiv preprint or Xxxx:238800800000 2023.
A Towards Establishing the Villani condition for the Empirical Logistic Loss
We start with the lollowing observation,
Lemma A.1. Letting w, denote the juh row of W we have,
Vw, Se (W) = ajo' (wfx.) x
In the following, [|] for matrix W denotes its spectral or operator norm. We recall that the regularized logistic loss for training the given neural net on data IB = {<),,,))) is,
A Iw] 1 E L.)) Rx = Σ (yt f(x;a f()=)a))))
L(W)
2
Explicitly stated, the SGD iterates with step-length s > that we analyze on the above loss are,
Wh+ W
Σ vi (WW))
B
W
$ Σ (
(1: f(x;; a, Wh)) (wr sAW*
b BB
=(1 (1-ss)
Σ (Ui=f(az;)) Wh)) Vwef(z;a, W*)]
b
We also note the following observation,
Lemma A.2.
1 Ifi(W)
1 (eti(WW) S
(A.1)
Proof-
eln(w))
1 ++ens((W) I+ I+el) (+)))(
Consider the function g(2)
e² Toges 2 e 00)
1 s(0) = 2' g((z) (1+ct)25 4
Hence, we have
((z)-9(0) = S(² g((2)s S =l_²
4
Therefore,
1 2 g(2) 4
(A.2)
15

---

Lower-boundigg the Norm of the Gradient of the Empirical Logistical Loss Recall that we are using the following empirical loss function,
L (W) - +
(A.3)
where ((2) = log (1 + e)*) is the logistic loss function. It follows that,
1 Σ Vw, (W)
ll (s)f (W) Xwj
(A.4)
Thercfore,
V Lw,
Σ
2
1 ++ pthh(W) Vw, (W) Xwo
Yi
i-1
And that implics,
Vw, = = -2 \wwy.
1/i ehf((W) Vw, Fw,[(WW
y/
Ve, ff (W)
enfi(w)
2 2
Σ
n2
eu.t(WW) (w)J((W)
yi
1=1
(A.5)
1
Vw,fi (W)l
2 >171w,112 22 22/w;12
1 ew..(W)
lazllo'
1 2A 21/w;12
212
E IM
1 eBif((W)
In the last line above we have invoked Lemma A.1. Now invoking Lemma A.2 and recalling the definition of MD and Bg in the above, we can claim that,
1 R n 1
+ Iff (A(WW)
L L (W)
X²1 2312,
|aa (LBzl
W|, [ /lcl2)
2 x w 1 2A1 2Nlw,|alo,|MDDl
4
Summing the above over all and using Cauchy-Schward inequality, Σラ-1 [wy 12 1aal s W FF |a] [lll s W we get,
and
[W)) x2 ABalBMDBBL
- W/ Mal pall B 1 |alg [0|||||2
(A.6)
Analyzing the Laplacian of the Empirical Logistic Loss
We begin with observing that,
1 a L' (v.J. v ve (W)) + xd =l
Vw, (V (Vw, [W)))
Vws w)
1 Ee (yif. (W)) Dw (w)) Ad
'" (W(
1-1
16

---

In above we have defined, Aw,f= Vww (Vw, f) We recall that, (2) o² Further by invoking Lemma A.I, the definition of MD and B3 have,
(I+e=)z to, show in Lemma A.2.
e" (y.f: (W)) (w) (W))
72 Σ w. / (W) |
n
2 ( ax,)
(A.7)
n F=
M BBBl
Recalling the definition of Mn we have,
n Σ 1-1
(yefi (W)) y, (W)
Σ
1
[W)(
y. of (W)
11 1-
2
4
(A.8)
2 + ||||
B2Mbllal2
4
And hence,
2 12+|cl
||a|l
[W] IF
BaMb MaBalll Ad
Vw,- (V L (W))l
(A.9)
4
4
Summing over all j, we get,
2 (2 ||c||
|al LBl W
MB 1al
AwL (W) s Σ Vay (V., L (W))] sp
B M
Xd
(A.10)
Bounding the Gradient Lipschitzness Coefficient of the Empirical Logistic Loss Towards the upcoming computation, we define the following function,
B
g1 (W) = V., ,.,L L= - Ee (inSi V. (. Aw,
(B.1)
Consoquently, corresponding to two values of the weight matrix W1 and W2, we obtain that,
[gj (W2) 93 2
1 Vi (L' (yifi (W2)) Fw - (y:ft ( f + Aw2, A2a2,
1 Σ ys (e' (()f((W)) (W:)) (W₂) ee' (yif: V (W;)) + +1Aw22, A201
(B.2)
<
B, aall2 Σ le
o' (w) (JAfi (W1) (W) Dia2 Xwo
In the last line above we have invoked Lemma A.1 and the fact that ii E {1,-1) for I....,n. n. Hence, the problem simplifies finding the Lipschitz constant of ll (y.f (W)) dw]Jx. Define hy as follows:
he hw Vus, (L' (ViJe (W)) o (wo).r::
(B.3)
17

---

hha(W)
V (e' (W)
lanl" (y.fe (W) d' (w) (w)
( (wff())) /" (v)
aa (yifi (W)
x;
o (
( ai + | (vifi (W)) o" aw)a
3B
((((W)
1x=1
o" (w) 2o x
4
2
4
MM
2 |cl|
Mb vp Lprod
4
where in the second term the vp factor comes in from using Cauchy-Schwarz inequality. We concatenate these functions along the indices k= 1.2,.... to get
h(W) = Vw [f(e a, W) (w][)))
And hence,
[h(W) $ VpLprod
Therefore, the Lipschitz constant of l' (y:f. (W) o (w) is:
|a MaBlMBBBv /P
2 |c|2
|aal| Be
M MD
4
Hence the Lipschitz constant of gj (W) is
a B
2++ |cll
aa 2
Bg
M Mb 1|bllaa
Proceeding in the case of h (W) above, concatenate the above gradients gj w.r.t the index j in vector form (of dimension pd) to get the following pd-dimensional gradient vector of the empirical loss,
VwL g(W) = [g (W), (V))g((W). (WW)........
and the Lipschitz constant of g and hence the gradient Lipschitz constant for L to be bounded as,
gLip(L) vbl vp 1pla|240 MB
2 |cl2
||al2 Br
MbBap+2)
Thus we get the expression as required in the proof in Section
C Defining the Constants C(ss, L) and X, of Theorem 3.2
Invoking Theorem from Shi et al. (2020) with a "time horizon" parameter T> 0, ʃ L, the convergence
guarantee for running k steps of SGD at a step-size 8 as given in Theorem 3.2 for k E (0,7) and (0, 1/)L can given as,
Bi(W**)
inf inn
B(T, i))s C(s, D) Ms Me -e
(C.1)
where A, B, C. are constants as mentioned in Shi al. (2020). In particular, the C therein was defined follows
Cls, = (S (L(W)
min I(W))² (W) dw) 1/2
W
2L( with Z, being the normalization factor.
for sta(W (W) being the Gibbs" measure, No (W(W)
Z, exp
18

---

For determining As, Shi et al. (2020) consider the function V.(W) /vi| Aİ. Let Ro.s > be large enough such that V.
(V)W) > for |W|| F 2 Ro For Rg Ro Shi et al. (2020) define e(Rs)
(R.) inf(V.(W) : |W| p R3}
where Rs is assumed large enough such that Swm du, 2 1/2. For BR, as the ball of radius Rg centered at origin in Rexd, Shi et al. (2020) define
(w) | M. (o)
R.
Using the Poincaré inequality in bounded domain (Evans (2010), Theorem 1, Chapter 5.8], Shi et al. (2020) define the constant C(R,) to be s.t the the following holds vh E C (RR),
Sw Rdd.,,n C(R.) S || Ms,n. dps, (Srezoee h hdps,
Then the key quantity X, occurring in the aforementioned convergence guarantec for SGD was shown to be,
A 1 3s winfwe V.(W)) (R.))
2(C((R,) 36 (R,))
D Further Details of The Key Idea in Shi et al. (2020) About the Convergence of the SGD-SDE (Equation 4.1)
In this appendix outline the steps of the key proof in Shi et al. (2020) which prove that that solution W.(!) of the SGD-SDE (Equation 4.1) has well-controlled bound the error it makes at any time in terms of how far away it is from the global infimum of the objective function Σ.
Theorem D.1 (MMii)) Theorem of Shi et al. (2020)). If is both confining and Villani, 3Y2 O for any > 0 ("leurning rale") ") s.l for a cerlain functions e(s; L) > 0 which is striclly increasing in s and D(s, W. p) 2 where the initial distribution, we have expotential convergence of the expected eacess risk as,
Ri() inf ((z) (() D(s, W, WPp)e-Aa
Towards outlining the proof of the above we will denote E[L(W. = Bw.., i(W), where μ4 is as given in equation 4.3 This is justified by the following convergence theorem which we count as the first of the main steps to be taken to prove Theorem D.1.
Step
Theorem D.2 (Lemma 5.2 in Shi et al. (2020)). If L satisfies the confining condition and if the initial u. then the unique solution p.(t) C¹ ([0,o0) L2 (2((1) of the F.P.S
distribution of the S.D.E is p E [²(2) differential equation (4.2) of the S.D.E, dW, -vi(V. dt /sdW converges in I2().) to the Gibbs' p.
invariant distribulion us.
Now we note the following decomposition of error that is considered in Theorem D.1.
Bi(W.(1)) - inf [((=) (FLL(W.)))-B(((((())))) + (B]] (B) in))
Next bound each of the terms in the RHS above via the following two theorems.
19

---

Step II
Theorem D.3 (Proposition 3.1 of Shi et al. (2020)). For L being confining and Villand and for any
$> 0 SYE > 0 s.t we have function C(s, > 0 (an increasing function in s) s.t Vt 2 0 we have,
-1p--- Hell
Step III
Theorem D.4 (Proposition 3.2 of Shi et al. (2020)). The excess risk at stationarity E(s) is s.t for all $ 0 and e S], BA(S, L) s.t,
{(s) [[(( A(S,
Combining the above two theorems (in Step II and Step III respectively) we are led to the key upperbound stated in Theorem D.1, with an appropriate definition of the D) function therein.
E Experimental Demonstration of Maintenance of Classification Accuracy on MNIST Dataset
For further illustration, we present experimental studies performing binary classífication between pairs of digits from the MNIST dataset by training depth-2, sigmoid activated nets and regularized with the cocfficient being at the threshold where the loss was proven to become a Villani function.
We do the binary classification experiments on the digit pairs (0, 1) and (2, In our experiments, the elements of the trainable weight matrix Wo (of dimension 12 784) initialized from the standard normal distribution and so is the fixed outer layer of dimensions 1 x 12 which was then rescaled by the largest data norm for the value of X to be given in equation 3.3.
Cavalication Accuratia
3398
Deto
3.50
4.40
Sol Data
40ch
Figure 2: Batch Size = 3000, X d 0.03125 and the net being trained has 12 sigmoid gates
Experiment on Digits and 7 This the experiment shown in Figure 2, In this case the model was trained for 100 epochs with mini-batch size of 3000. We measured the test accuracy of classification the downstream metric of measuring the goodness of training and at the end of training, achieved accuracy of 84%.
Experiment on Digits 0 and 1 This is the experiment shown in Figure 3. Here the model was trained for 100 epochs with mini-batch size of 3000. We measured the test accuracy of classification the downst ream metric of measuring the goodness of training and at the end of training, we achieved x 90% accuracy
Thus we have experimentally demonstrated that the threshold amount of regularization that was needed for the proof of convergence may not at all harm the downstream performance metric of classification for even real data. In both the cases above we demonstrated examples of nets being trained on logistic loss for regularization parameter being À A₂ and achieving good accuracy on the classification metric even though the model not exposed to the 0- criteria during training.
20

---

Cauaircation Actusoos
0.59
fin Onto
0700
3.42
0.70
Yoa Date
Figure 3: Batch Size 3000, X = A. 0.03125 and the net being trained has 12 sigmoid gates.
Codes for these experiments can be found at this link for the (2, 7) classification experiment and at this link for the (0, 1) classification experiment
21


Reviews:
[{"review_id": "A0Igj3GcdL", "reviewer": "Reviewer_qMSF", "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": "The paper considers an interesting problem and is very well written. The proofs are clear and easy to follow and seem to be correct as far as I checked. Since I am not an expert in this area, I have one question for the authors.\n\n1. The theoretical results of this paper seem to be very dependent on the paper Shi et al. (2020). I hope the authors could introduce this paper Shi et al. (2020) in more details including its background and main results. I also hope the authors could discuss about the main inovation of your paper compared to Shi et al. (2020).\n\n2. It seems that the norm $\\left\\|| \\cdot \\right\\||_{\\mu_s^{-1}}$ is not defined in the paper.", "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 global convergence of SGD for logistic loss on two layer neural nets. Authors show a provable convergence of SGD to the global minima with regularization and logistic loss. Authors also prove an exponentially fast convergence rates for continuous time SGD with SoftPlus activation function. An experiment is conducted for different regularizers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The norm should be given explicitly when it is applied. It will be great if the authors can make some discussion on the question I listed above.", "broader_impact_concerns": "I have no concerns on the broader impact of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wDS75n3QvK", "reviewer": "Reviewer_Aimc", "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": "I am not quite sure about the results of this work. First of all, there are many typos and nonstandard punctuation in the manuscript. The references are also not in the correct style. \n\nBeside the heavy reliance on the results of Shi et al, (2020), I think the main weakness of this work is its reliance on the almost always incorrect SDE in equation (4), where the noise is assumed to be a full-rank isotropic Gaussian -- which then implies the Gibbs measure, which is also what this work heavily relies on. While this type of noise does correspond to that of SGLD, it does not equal minibatch SGD.\n\nThe invariant measure of SGD is far from the gibbs measure, and the noise in the SDE is both parameter dependent (often called the multiplicative noise) and low-rank. In fact, it is very easy to run into loss functions in deep learning for which the SDE in Eq. (4) diverges, whereas actual SGD is convergent. This means that SGD is not really \"arbitrarily well approximated\" by Eq (4). I think that the authors ought to compare and discuss the results in this work: https://arxiv.org/abs/2308.06671\n\nWhile the results of the authors might be interesting per se, I do not think they are relevant regarding minibatch SGD. The authors need to rewrite their claims to match their actual contribution", "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 paper claims to prove the convergence of two layer nets to the global minimum under SGD", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness", "broader_impact_concerns": "fine", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vuGh7vOrYt", "reviewer": "Reviewer_tgay", "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:\nThe analysis can accommodate any width and input distribution.\n\n# Weaknesses:\n* While the manuscript provides a good summary of its proof technique, in its current form, there might not be a lot of new aspects to learn from it. Specifically, the arguments mostly directly follow those of Shi et al., 2020, and the main contribution seems to be verifying that a certain Villani condition holds in the investigated setting through standard calculations.\n\n* The dependence of $\\lambda_s$ on $s$ is not known. As a result, we cannot obtain a convergence rate, and in particular, it is not clear without additional discussion on $\\lambda_s$ whether the claimed convergence rate of $O(1/\\epsilon)$ is correct, since $s$ itself depends on $\\epsilon$.\n\n* It is not theoretically clear if the regime of regularization $\\lambda$ chosen in the manuscript is sufficiently small to allow good classification performance. The authors have verified this experimentally, although in an arguably simple setting where linear predictors also achieve 100% accuracy.\n\n* It is not discussed whether standard (Gaussian) initialization methods can achieve $\\rho_\\mathrm{initial} \\in L^2(1/\\mu_{s^*})$, as such a condition might require a relatively fast tail decay for small $s^*$. Furthermore, dimension dependencies are hidden in the bounds.\n\n* There is some room for improving the writing of the paper, with examples provided below.", "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 paper studies the problem of training a two-layer neural network with SGD on the logistic loss function. By relating the SGD dynamics in the small step-size regime to the limiting SDE and verifying that the objective potential satisfies a Poincar\\'e inequality, a local convergence result for SGD is established which is independent of the width of the network and the input distribution.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "I believe that the current version of the manuscript might not be ready for publication, and would suggest the following:\n\n## Major Comments:\n* I am not sure if the $O(1/\\epsilon)$ convergence rate is correct if $\\lambda_s$ can depend on $s = O(\\epsilon)$. It would be a very interesting contribution to provide explicit estimates for $\\lambda_s$, hence achieving explicit convergence rates, especially in a setting where the optimization problem is still non-convex. Such a contribution would also distinguish this work from Shi et al., 2020 at a technical level.\n\n* It would greatly help if the authors could add a discussion on why or why not standard (Gaussian) initializations are able to achieve the initialization requirement of Theorem 3.2 / Lemma 3.3.\n\n* Another interesting contribution would be to show that for some data distributions, the amount of regularization $\\lambda$ required does not hurt performance. Such a result (theoretical or experimental) would be more interesting if the distribution is such that there is a gap between the performance of linear models and neural networks.\n\n## Minor Comments:\nThere is some room for improving the writing style of the manuscript, for example:\n* It is not clear why Theorem 3.2 is stated as a theorem and the closely related Lemma 3.3 which has a broader result is stated as a lemma. It might make more sense to present Lemma 3.3 as a Theorem and Theorem 3.2 as its corollary.\n\n* The introduced mini-batch size is never used in the rest of the paper.\n\n* Lemma 3.1 seems a bit out of place and perhaps the readers would need additional context to understand what is the significance of this lemma (hence appearing right before presenting the main theorem) and its relation to the main results.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In light of the evaluation policy of TMLR (technical correctness and relevance), the paper meets the acceptance criteria. However, there is room for improvement, particularly, the limitation of the work should be clearly stated. Therefore, we recommend the acceptance with minor revisions provided that the authors clarify limitation (see below) and fix typos and citation format (e.g.,"... when it exists Zhang et al. (2018)." should be "...when it exists (Zhang et al., 2018”). 

The major concern is a lack of discussion about the strength of regularization. Usually, the regularization coefficient $\lambda$ should be chosen to be small depending on the problem setup (e.g., the number of examples) to achieve a small population error. However, the required condition on $\lambda$ could restrict choosing a small value. Moreover, the condition imposed on the initial distribution is also strong. Given the existing study that demonstrates the learnability of two-layer networks trained with SGD on the logistic loss (e.g., [Ji and Telgarsky (2020)]) under a reasonable condition, the obtained result in the paper appears to be rather restrictive.
Decision: Accept (poster)