New Perspective on the Global Convergence of Finite-Sum Optimization
Authors: Lam M. Nguyen
Trang H. Tran
Marten van Dijk
Venue: ICLR 2022 Submitted (2022)
Keywords: non-convex optimization
overparameterized
optimization for deep learning
finite-sum
global minimum

Abstract: Deep neural networks (DNNs) have shown great success in many machine learning tasks. Their training is challenging since the loss surface of the network architecture is generally non-convex, or even non-smooth. How and under what assumptions is guaranteed convergence to a \textit{global} minimum possible? We propose a reformulation of the minimization problem allowing for a new recursive algorithmic framework. By using bounded style assumptions, we prove convergence to an $\varepsilon$-(global) minimum using $\mathcal{\tilde{O}}(1/\varepsilon^2)$ gradient computations. Our theoretical foundation motivates  further study, implementation, and optimization of the new  algorithmic framework and further investigation of its non-standard bounded style assumptions. This new direction broadens our understanding of why and under what circumstances  training of a DNN converges to a global minimum.

Under review as a conference paper at ICLR 2022
NEW PERSPECTIVE ON THE GLOBAL CONVERGENCE OF FINITE-SUM OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks (DNNs) have shown great success in many machine learn- ing tasks. Their training is challenging since the loss surface of the network ar- chitecture is generally non-convex, or even non- mon-hh.oth. How and under what as- sumptions is guaranteed convergence to global minimum possible? We propose a reformulation of the minimization problem allowing for new recursive algo- rithmic framework. By using bounded style assumptions, we prove convergence to an E-(global) minimum using (11/c²) gradient computations. Our theoretical foundation motivates further study, implementation, and optimization the new algorithmic framework and further investigation of its non-standard bounded style assumptions. This new direction broadens our understanding of why and under what circumstances training of DNN converges to global minimum.
INTRODUCTION
In recent years, deep neural networks (DNNs) have shown a great success in many machine learn- ing tasks. However, training these neural networks is challenging since the loss surface of network architecture is generally non-convex, or even non-smooth. Thus, there have been a long-standing question on how optimization algorithms may converge to a global minimum. Many previous work have investigated Gradient Descent algorithm and its stochastic version for over- parameterizee set- ting (Arora et al., 2018; Soudry et al. 2018; AAlenn-Zhn Zhu et al. 2019 Du et al., 2019a| Zou & Gul 2019). Although these works have shown promising convergence results under certain assumptions, there is still a lack of new efficient methods that can guarantee global convergence for machine learning optimization. In this paper, we address this problem using a different perspective. Instead of analyzing the traditional finite-sum formulation, we adopt a new composite formulation that ex- actly depicts the structure of machine learning where a data is used to learn a common classifier.
Representation. Let ((x(), ) be a given training with ((() investigate the following novel representation for deep learning tasks:
R" y E RR
F(w) 1 Σ te (h((((
min WERd
where (1(=;)) Rd R. [n] nn. is the classifier for each input data z01); and 6, R RR, i E [n]], is the loss function corresponding to each output data yt)) Our composite for- mulation I is special case of the finite-sum problem min (F(w) и Σ f(w; i)) where each individual function f (-;;) i) is composition of the loss function di and the classifier h(:;2). This problem covers various important applications in machine learning, including logistic regression and neural networks. The most common approach for the finite-sum problem is using first-order meth- ods such as (stochastic) gradient algorithms and making assumptions on the component functions d() As alternative, our assumption on the classifier (()z).. For the purpose of this work, we first consider convex and Lipschitz-smooth loss functions while the classifiers can be non-convex. Using this representation, we propose new framework followed by two algorithms that guarantee global convergence for the minimization problem.
further investigate the structure of the loss function é; and narrow
Algorithmic Framework. Representation I admits a new perspective. Our key insight is to (A) define 2(0) h(w(()); i), where & is iteration count of the outer loop in our algorithmic framework.

---

Under review as a conference paper at ICLR 2022
Next (B); we want to approximate the change 2; 2/
(1++1 (1)
in terms of step size times the gradient
Vol(=,() - (00, (aeee l==
and (C) we approximate the change h h(w h( in terms of the first order derivative
n!!0 = (aha(w; i) (otb)a((ccleeee w=w(()"
Finally, we combine (A), (B), and (C) to equate the approximations of = h(w(++1); - ;o). This leads to a recurrence on w(t) of the form w(++1) = wlf) - ((0),
(((+1) 2,- and
where x7(9) step size and which involves computing v(()) by solving convex quadratic sub- problem, see the details in Section We explain two methods for approximating solution for the derived subproblem. We show how to approximate the subproblem by transforming into strongly convex problem by adding regularizer which can be solved in closed form. And we show how to use Gradient Descent (GD) on the subproblem to find an approximation e(t) of its solution.
Convergence Analysis. Our analysis introduces non-standard bounded style assumptions. Intu- itively, we assume that our convex and quadratic subproblem has a bounded solution. This allows us to prove total complexity of Ö (+) to find an s-(global) solution that satisfies F(i) P, S s, where F. is the global minimizer F. Our analysis applies to a wide range of applications in machine learning: Our results hold for squared loss and softmax cross-entropy loss and applicable for a range activation functions in DNN as we only assume that the h(:;)) are twice continuously differentiable and their Hessian matrices (second order derivatives) as well their gradients (first order derivatives) are bounded.
Contributions and Outline. Our contributions in this paper can be summarized as follows.
We propose new representation ( for analyzing the machine learning minimization prob- lem. Our formulation utilizes the structure of machine learning tasks where training data set of inputs and outputs is used to learn a common classifier. Related work in Section shows how T is different from the classical finite-sum problem.
Based on the new representation we propose a novel algorithm framework. The algorith- mic framework approximates a solution to a subproblem for which we show two distinct approaches.
For general DNNs and based bounded style assumptions, we prove total complexity of O(3)) ) to find an eglobal) solution that satisfies F F(w) F, S E, where F, is the global minimizer F.
We emphasize that focus is developing a theoretical foundation and that translation to practical implementation with empirical results is for future work. Our theoretical foundation motivates further study, implementation, and optimization of the new algorithmic framework and further investigation of its non-standard bounded style assumptions. This new direction broadens our understanding of why and under what circumstances training of a DNN converges to global minimum.
The rest of this paper is organized as follows. Section 2 discusses related work. Section 3 describes our setting and deep learning representation. Section explains our key insight and derives our Framework [ Section pressenss our algorithms and their global convergence. All technical proofs are deferred to the Appendix.
2 RELATED WORK
Formulation for Machine Learning Problems. The finite-sum problem is one of the most im- portant and fundamental problems in machine learning. Analyzing this model the most popular approach in the machine learning literature and it has been studied intensively throughout the years (Bottou et al. 2018 Reddi et al.) 2016; Duchi et al. 2011b). Our new formulation ① is a spe- cial case of the finite-sum problem, however, is much more complicated than the previous model since it involves the data index both inside the classifiers h(-; i) and the loss functions Φ, For a comparison, previous works only consider common loss function 1(ÿ, y) for the predicted value
2

---

Under review as a conference paper at ICLR 2022
y and output data y Zou et al. 2018 Soudry et al. 2018). Our modified version of loss function o is a natural setting for machine learning. We note that when h(w; i) is the output produced by a model, our goal is to match this output with the corresponding target y(). For that reason, the loss function for each output has a dependence on the output data y and is denoted by d. This fact reflects the natural setting of machine learning where the outputs are designed to fit different targets, and the optimization process depends on both outer function di and inner functions ((;:)) This complication may potentially bring a challenge to theoretical analysis. However, with separate loss functions, we believe this model will help to exploit better the structure of machine learning problems and gain more insights on the neural network architecture.
Other related composite optimization models are also investigated thoroughly in (Lewis & Wright, 2016 Zhang & Xiao 2019: Tran-Dinh et al., 2020). Our model is different from these works as it does not have a common function wrapping outside the finite-sum term, as in (Lewis & Wright
2016). Note that a broad class of variance reduction algorithms (e.g. SAG (Le Roux et al. 20122)
SAGA (Defazio et al., 2014), SVRG (Johnson & Zhang 2013), SARAH (Nguyen et al. (017)) is designed specifically for the finite-sum formulation and is known to have certain benefits over Gra- dient Descent. In addition, the multilevel composite problem considered in (Zhang & Xiao 202T) also covers empirical risk minimization problem. However our formulation does not match their work since our inner function hww;; i) is not an independent expectation over some data distribution, but a specific function that depends on the current data.
Global Convergence for Neural Networks. A recent popular line of research is studying the dy- namics of optimization methods on some specific neural network architectures. There are some early works that show the global convergence of Gradient Descent (GD) for simple lincar network and two-layer network (Brutzkus et al., 2018 Soudryy et al.) 2018 Arora et al., 2019 [u et al. (019b)). Some further works extend these results to deep learning architectures (Allen-Zhu
al. 2019 Du eet al.] 2019a; /Zo & Gul 2019). These theoretical guarantees are generally proved for the case when the last output layer is fixed, which is not standard in practice. A recent work (Nguyen & Mondelli 2020) prove the global convergence for GD when all layers are trained with some initial conditions. However, these results are for neural networks without bias neurons and it unclear how these anal- yses can be extended to handle the bias terms of deep networks with different activations. Our novel framework and algorithms do not exclude learning bias layers as in (Nguyen & Mondelli 2020).
Using a different algorithm. Brutzkus et al. (2018) investigate Stochastic Gradient Descent (SGD) for two-layer networks in a restricted linearly separable data setting. This line of research continues with the works from Ahlen-Zhu et al. (2019): Zou et al. (2018) and later with|Zou & (2119). They justify the global convergence of SGD for deep neural networks for some probability depending on the number of input data and the initialization process.
Over- Paremaaramttri Settings and other Assumptions for Machine Learning. Most of the mod- learning architectures
werr-parameterized, which means that the number of parameters very large and often far more than the number of input data. Some recent works prove the global convergence of Gradient Descent when the number of neurons
extensively large. e.g. (Zou & Gu 2019) requires ((n²) neurons for every hidden layer, and (Nguyen & Mondelli 2020) im- proves this number to 2) If the initial point satisfies some special conditions, then they can show a better dependence of (()). In Allen-Zhu et al. (2019), the authors initialize the weights using a random Gaussian distribution where the variance depends on the dimension of the problem. In non-convex setting, they prove the convergence of SGD using the assumption that the dimension depends inversely on the tolerance e. We will discuss how these over wverpparamttrized settings might be a necessary condition to develop our theory.
Other standard assumptions for machine learning include the bounded gradient assumption Nee- mirovski et al.) 2009. Shalev-Shwartz et al. 2007 Reddi et al., 2016: Tran et al., 2021). It is also common to assume all the iterations of an algorithm stays in bounded domain (Duchi et al. 201 2011a
Levy et al. 2018 Gürbüübalaban et al.] 2019 Reddi et al. 2018 Vaswani et al. 2021). Since we are analyzing new composite formulation, it is understandable that our assumptions may also not be standard. However, we believe that there is strong connection between assumptions and the traditional setting of machine learning. We will discuss this point more clearly in Section 4
3

---

Under review as a conference paper at ICLR 2022
3 BACKGROUND
In this section, we discuss our formulation and notations in detail. Although this paper focuses on deep neural networks, our framework and theoretical analysis are general and applicable for other learning architectures.
Deep Learning Representation. Let {(x(1) HL be a training data set where x E R is training input and ()) E RS is training output. We consider a fully-connected neural network with {0, (........... L}. has n, neurons. We represent layer O-th and L-th
layers, where the 1-th layer, layer as input and output layers, respectively, that is, = d and nu c. For E {1..... ... L}, let w E R"t-1X" and 6(9) E IR where {(W'0), (( represent the parameters of the neural network. A classifier h(w;a) i) is formulated
h(w;)) i) W(4) OL- ( 0
o1 (W 2001 +6")).... ...) + ((1-111) b(4)
where w vee((W(() , w E R is the vectorized weight and {a 1-1 are some activation functions. The most common choices for machine learning are ReLU, sigmoid, hyperbolic tangent and softplus. For j E hy), i(;;), , for each data i [r] respectively. Moreover, we define li = arg min,eR- (x(z), i [n]]
((4)
i): (:;:))
Rd + R denotes the component function of the output
Loss Functions. The well-known loss functions in neural networks for solving classification and regression problems are softmax cross-entropy loss and square loss, respectively:
(Softmax) Cross-Entropy Loss: F(w)= Ei= I (w;; i) with
f(w;; i) -y log(softmax(h((x:)))
(2)
Squared Loss: F(w) En f(w; with
f(w: i) = [1b(ww;) - 112
(3)
We provide some basic definitions in optimization theory to support our theory. Definition 1 (L-smooth). Function &b IRc + IR is Lag-mmothh if there exists a constant L > such that, Vx1, x2 R.
V vo(x2)) S Løll - x2
(4)
Definition (Convex). Function o R- conver V2 12;
x(z1) x(x²) ž (V)(22), x2).
(5)
The following corollary shows the properties of softmax cross-entropy loss (2) and squared loss 3
Corollary 1. For softmax cross-entren cross-entropy loss (2) and squared loss { there exist functions h(::
Rd + R and di I + R such that, for i n)). dz(z) is convex and Ly-smooth with Ls = 1, and
f(w; i) (h(ww, (x(2) =
(6)
NEW ALGORITHM FRAMEWORK
4.1 KEY INSIGHT
We assume f(w; = (h: i)) with ø; convex and Ls-smooth. Our goal is to utilize the con- vexity of the outer function d; In order to simplify notation, we write V=0:(h(w(();) instead of
[=);(=) ==)()())))))) and denote 20") h(w(();) i). Starting from the current weight w(t), would
like find the next point (t+1)) that satisfies the following approximation for all [n]:
((w(++1;;)) 21 (++1) 2(0) a, (')0((2)")) (9: i) a. Vh (9;)).
4

---

Under review as a conference paper at ICLR 2022
We can that this approximation is "noisy" version of gradient descent update for every function 6, simultaneously for all é E [n]. In order to do this, we use the following update
(t+ = w( (*))
where 17()) > O a learning rate and u( is a search direction that helps us approximate equation If the update term y small enough, and if h(:;1) i) has some nice smooth properties, then from basic calculus we have the following approximation:
h(w (t(+))) 1; = h(w!)) - "n ());;) = h(w!);) - (1)0)))))))
(9)
where H! is matrix in Rexd with first-order derivatives. Motivated by approximations ( and we consider the following optimization problem:
(4) arg min
11 |
(n aj
(1) V (h(((((
(10)
HERS
Hence, by solving for the solution v. of problem 10 we able find a search direction for the key approximation This yields our new algorithmic Framework T
see below.
Framework New Algorithm Framework
Initialization: Choose initial point w(() Rd for / = 0, 1, ... , do
Solve for an approximation e(t)) of the solution ( of the problem in 10
11
1, (0) H a. V
Ux
arg min eE
2
Update (++1) = (t) 17 (())
end for
4.2 TECHNICAL ASSUMPTIONS
Assumption 1. The loss function Φ; is convex and Lg-smooth for i E [n]]. Moreover, we assume that it is lower bounded, i.e. inf (b(()) > for E [n]]
We have shown the convexity and smoothness of squared loss and softmax cross-entropy loss in Section 3 The bounded property of o; is required in any algorithm for the well-definedness of (T) Now, in order use the Taylor series approximation, we need the following assumption on the neural network architecture h:
We assume that hı(:;)) is twice continuously disferentiable for all i E [m] (i.e. the second-order partial derivatives of all scalars (x(;;) are continuous for all j E |c] and [n]), and that their Hessian matrices are bounded, that is, there exists G such that for all Rdd i [n] and E [c).
Assumption 2.
(w)((w) = 1 Vuni(ur;i)11 SG.
(11)
where Ju denotes the Jacobian M
Remark (Relation second-order methods). Although our analysis requires assumption the Hessian matrices of h(w;; i), our algorithms do not use any second order information or try to approximate this information. Our theoretical analysis focused the approximation of the clas- sifier and the gradient information, therefore is not related to the second order type algorithms. It is currently unclear how apply second order methody into problem, however, this is interesting research question to expand the scope of this work.
For continuously differentiable function g(v) R B we define the Jacobian J... (g(w)) as the matrix (Qgal (w)
5

---

Under review as a conference paper at ICLR 2022
Assumption 2 allows to apply Taylor approximation of each function hy(;t)) with which prove the following Lemma that bounds the error in equation (9): Lemma 1. Suppose that Assumption 2 holds for the classifier h. Then for all E [n] and S 1 T,
h(w((+1);)) h(w(()) -1)(0)(()); ;) h(w 17 11 (0) + c
(12)
where
H(th (h i))l E Rexd
(13)
defined as the Jacobian matrix of h(w; i) at w(l) and entries 4 j E [c]. of vector c satisfy
[ / (n (110001160
(14)
In order to approximate 7 combined with (9. that is, to make sure the right hand sides of 7 and are close one another, we consider the optimization problem (O):
(+) = arg min 0
In (0 M v- V ; ;))1?
BE 2 n2
The optimal value of problem (10) equal 0 if there exists vector v. satisfying 17 H o(
a: (t) (h(((())); for every i E [n]] Since the solution vs is in E and (h(((((w()) i)) is in RS, this condition is equivalent
linear system with n e constraints and d variables. In the over- parameterized setting where dimension d is sufficiently large (d > n c) and there are no identical data, there exists almost surely vector e that interpolates all the training set, see the Appendix for details.
Let us note that an approximation of (t) serves the search direction for Framework 1 For this reason, the solution e)(() problem (10) plays similar role as a gradient the search direction of (stochastic) gradient descent method. It is standard to assume bounded gradient in the ma- chine learning literature (Nemirovski et al. 2009) Shalev-Shwartz et al. 2007: Reddi et al. 2016))
Motivated by these facts, assume the following Assumption near-optimal bounded solution of (10):
3 which implies the existence of
Assumption 3. We consider pver-puramettriized setting where dimension d is sufficiently large enough to interpolate all the data and the tolerance e, We assume that there exists a bound V
such that for > O and 0 I t < T as in Framework there exists a vector (() with [|ote < V so that
1 H( (1))) at (.((((()))
2
Our Assumption requires a nice dependency on the tolerance e for the gradient matrices H and oz (=(h(((()))) We note that at the starting point f = 0, these matrices may depend on e due to the initialization process and the dependence of d on This setting is similar to previous works,
e.g. Allen-Zhu et al. (2019).
NEW ALGORITHMS AND CONVERGENCE RESULTS
5.1 APPROXIMATING THE SOLUTION USING REGULARIZER
Since problem I0 is convex and quadratic, we consider the following regularized problem:
min vERd
((v)=
11
(9) H v a ( ())(((((
c² (15)
2 ||'1|2 |lulp.
2

---

Under review as a conference paper at ICLR 2022
for small > 0 and t O. is widely known that problem 15
is strongly convex, and has
unique minimizer v reg. The global minimizer satisfies V, (v
We have
V
(v)
10) H
T H;
10 H
V= ;1)) +
T H
T
10 + 121
(0) (1) T (2
Therefore,
Ue
H H('0
+²2
| Σ
(1) a n
V VV
v=dh((((0(000))))
(16)
If g² is small enough, then U. reg is close approximation of the solution first algorithm updates Framework based on this approximation.
( for problem 10
Our
Algorithm Solve for the exact solution of the regularized problem
Initialization: Choose an initial point (0) TR:,, tolerance & > 0; for t = T do
Update the search direction (1)) as the solution v! reg of problem in 15
(()) (1)
reg.
1 Σ
n
H
( H 77 +
1 Σ
1
(1)
i=1
i=1
Update ((++)) (t) (3) (t) end for
The following Lemma shows the relation between the regularized solution v. ry and the optimal solution of the original convex problem ((t)
Lemma 2. For given O, suppose that Assumption 3 hoold for bound V > 0. Then, for iteration
t < T, the optimal solution v! reg of problem (15) satisfies l reg 112 < 2 + Vand
11
In (4)
(1)
(0) (0) rey -a V s )²
(17)
2 n
1=1
we guarantee the global convergence of Algorithm Tand prove our first theorem. Since is currently expensive to solve for the exact solution of problem (15), our algorithm serves theoretical method to obtain the global convergence for the finite-sum minimization.
Based on Lemma
Theorem 1. Let w(t) be generated by Algorithm 1 where we the closed form solution for the search direction. We execute Algorithm 1 for T
outer loops for some constant 3 0. We assume Assumption holds. Suppose that Assumption P holds for G > and Assumption 3 holds for V > O. We set the step size equal rp = De for some D 0 and choose learning rate a = (1+ E)a (t-1)
(1+ =)aa Based on 3, we define a: (0) LL with a E (0, 1)) Let F,
be the global minimizer of F, and h arg minzero (1(=), E [m]. Then
F.] 5 Σ (F)
e Lo (1+
1 Σ
|1 (1(w(())) 13
2(1 21-3a)aa
Y=1
e Th 2 +
[c(4 + (V 2)GD)) e. (18)
8a(1 - 3ax
We note that 3 is a constant for the purpose of choosing the number of iterations T. The analysis can be simplified by choosing 8 = 1 with T - Notice that the common convergence criteria for

---

Under review as a conference paper at ICLR 2022
finding stationary point for non-convex problems is Σ [VF(())) Oe)). This criteria has been widely used in the existing literature for non-convex optimization problems. Our conver- gence criteria + Σx= [F(w)) - F.] S O(s) is slightly different, in order to find global solution for non-convex problems.
Our proof for Theorem is novel and insightful. It is originally motivated by the Gradient Descent update and the convexity of the loss functions di. For this reason may not be a surprise that Algorithm can find an E-global solution after O (2) iterations. However, computing the exact solution in every iteration might extremely challenging, especially when the number of samples is large. Therefore, we present a different approach to this problem in the following section.
5.2 APPROXIMATION USING GRADIENT DESCENT
In this section, we use Gradient Descent (GD) algorithm solve the strongly convex problem (15)
It is well-known that if (xx)) ~ |== is convex for Vz E R", then vb(z) is p--stronlyy convex (see
e.g. Nesterov 2.004). Hence (-( is -trongly convex. For each iteration we use GD to find
search direction u(*) which is sufficiently close to the optimal solution (8) in that
reg
(1000)
(t) reg Se.
(19)
Our Algorithm is described as follows.
Algorithm 2 Solve the regularized problem using Gradient Descent
Initialization: Choose an initial point (0( Rd, tolerance E > 0; for /. = 0, 1........ T 1 do
Use Gradient Descent algorithm to solve Problem 15) and find a solution v(1) that satisfies
|| 56 reg S
Update w(++1) = (t) x((0) end for
Since Algorithm 2 can only approximate solution within some E-preciseness, we need a supple- mental assumption for the analysis of our next Theorem 2
Assumption 4. Let H! be the Jacobian matrix defined in Lemma 1 We assume that there exists some constant H > 0 such that, for i E [n]. e > O, and 0 < t < T as in Algorithm 2
H
10 H
(20)
VE"
Assumption 4 requires mild condition on the bounded Jacobian of h(w;; i), and the upper bound may depend on e. This flexibility allows us to accommodate a good dependence of for the theo- retical analysis. We are now ready present our convergence theorem for Algorithm
Theorem 2. Let wilt) be generated by Algorithm where v(()) satisfies 19p. We execute Algorithm
for T = - outer loops for some constant 3
We assume Assumption / holds. Suppose That Assumption holds for G O, Assumption holds for V O and Assumption holds for
H. > 0. We set the step size equal to (1()) = Ve for some D > 0 and choose learning rate
(0) (1+ e)a (t-1) (t-1)
(1 + s)aa (0)
Based on 3, we define a: (0) a with a (0, Let F.
a
Lo
be the global minimizer of F, and h = arg minseR (1(2), [n]. Then
T-1
è Lg (1+8) +)
Σ (((o0()) -F.]
( -1712..
2(1 - 30
7 1=1
+ 3 (4E 33
D2 c(2 + (V +e2 + + - -2 +V] s.
2a(1 4a)
8

---

Under review as a conference paper at ICLR 2022
Theorem implies Corollary 2 which provides the computational complexity for Algorithm Note that for (Stochastic) Gradient Descent, we derive the complexity in terms of component gradient calculations for the finite-sum problem ( As alternative, for Algorithm [ we compare the number of component gradients in problem 15) Such individual gradient has the following form:
V (obb(o)== H H. n0 a."nn " ve
i) is calculated using automatic differentiation (i.e. backpropagation). Since 2:) is the composition the network structure h(-:;) and loss func- tion (-). this process also computes the Jacobian matrix 11,0) and the gradient V=0, (h((()(((); i)) at specific weight w((), Since matrix- vector multiplication computation is not expensive, the cost for computing the component gradient of problem (5) similar to problem [
In machine learning applications, the gradient of ((:;+)
Corollary 2. Suppose that the conditions in Theorem
hold with 17() DVE for some > 0 and vN
0 < é S N (that is, we set & = E/N), where
N e Le E ()(
7e -22-
n( 2aja8
2a
Then, the total complexity guarantee mino minosegT-(((((0)) S
FF.]
is O
N 20 A
3)
Remark 2. Corollary 2 shows that O (1/E) outer loop iterations are needed in order to reach an
& E-global solution, and it proves that each iteration needs the equivalent of O 21 log())) gradient
computations for computing an approximate solution. In total, Algorithm 2 has total complexity
O ( log( {)) for finding an E-global solution.
For comparison, Stochastic Gradient Descent uses total of ((22) gradient compulations to find stationary point satisfying F S for non-convex problems (Ghadimi & Lan 2013). Gradient Descent has better complexity in terms of i.e. ( such that F
(Nesterov 2004). However, both methods may not be able to reach global solution of ( In order to guarantee global convergence for nonconvex settings, one may resort to use
(PL) inequality (Karimi al. [2016] Gower et al.) [021). This assumption is widely known to be strong, which implies that every stationary point is also global minimizer.
6 FURTHER DISCUSSION AND CONCLUSIONS
This paper presents an alternative composite formulation for solving the finite-sum optimization problem. Our formulation allows new way of exploiting the structure of machine learning prob- lems and the convexity of squared loss and softmax cross entropy loss, and leads to novel algorith- mie framework that guarantees global convergence (when the outer loss functions are convex and Lipschitz-smootie Our analysis is general and be applied to various different learning architec- tures, in particular, our analysis and assumptions match practical neural networks; in recent years, there has been great interest in the structure of deep learning architectures for over pee-pparamteriieed settings (Arora et al.] 2018 Allen-Zhu et al. 2019 Nguyen & Mondelli, (020). Algorithm demon strates gradient method to solve the regularized problem, however, other methods can be applied to our framework (e.g. conjugate gradient descent).
Our theoretical foundation motivates further study, implementation, and optimization of the new algorithmic framework and further investigation of its non-standard bounded style assumptions. Possible research directions include more practical algorithm designs based on our Framework [ and different related methods to solve the regularized problem and approximate the solution. This potentially leads to a new class of efficient algorithms for machine learning problems. This paper presents new perspective to the research community.
9

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
This paper does not contain ethics concerns.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 09-15 Jun 2019. URL http: (Rttttp://ppoceeee http:://prcceedngs...
mlr. press v9w 2hu11h 9a. html
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 244-253, PMLR, 10-15 Jul 2018. URL http:://proceeeeeeeeee
mlr. mir.press wwwsspesssssse.. v80 aaraaaoralaaaa html
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332.
PMLR, 09-15 Jun 2019.
URL http: http://proceedingg mmr. wwwpss/eevv.... http/////arrrall....
html
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018. doi: 10.1137//611000173.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018. TRLLtttps://pperevvee
fform??
[dd=rJ33wxRR
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pp. 1646-1654, 2014.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Pro- ceedings of Machine Learning Research, pp. 1675-1685 PMLR, 09-15 Jun 2019a. URL .m www.lrrpees/v////
http:://proceedings
htm
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations, 2019b. URL
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(11)22111-2159, 201 la. URL
http:/ /ttt:://mmmrr jmlr org. wwwp://gppppa..apee/to swraaprrs/vl22 v12 duchilla.hhhehoooccccc
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and
stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011b.
Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic pro- gramming. SIAM J. Optim., 23(4):2341-2366 2013.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions:
Learning rates, minibatching and interpolation. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 1315-1323. PMLR, 13-15 Apr 2021. URL httpt:://///m. htttps://proceed: ing.. ml www.sresaaaee 30tp:////v10///wrr2222 html]
30/
10

---

Under review as a conference paper at ICLR 2022
M. Gürbüzzalaban,, A. Ozdaglar, and P. A. Parrilo. Convergence rate of incremental gradient and incremental newton methods. SIAM Journal on Optimization, 29(4))2542-25665 2019. doi: 10. 1137/17M1 147846. URL Ctl.ittsss.. https://doi.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 315-323, 2013.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-Lojasiewicz condition. In Paolo Frasconi, Niels Landwehr, Giuseppe Manco, and Jilles Vreeken (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 795 811, Cham, 2016. Springer International Publishing.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponen- tial convergence rate for finite training sets. In NIPS, pp. 2663-2671, 2012.
Kfir Y. Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018 htt.ttss::/ httttpp:://prooceeddngs..s htwprroceeeiiig.....i....e...ee. cc/papper/001//11le b0169350cd35566c 22 Paper. pdf
Adrian S. Lewis and Stephen Wright. A proximal method for composite minimization. Mathe- matical Programming. 158:501-546 2016.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. on Optimization, 19(4)1174-1609, 2009.
Yurii Nesterov. Intruductory lectures convex optimization: a basic course. Applied optimization.
Kluwer Academic Publ., Boston, Dordrecht, London, 2004. ISBN 1-4020-7553-7.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Setrning-Volumme 70, pp. 2613-2621. JMLR. org, 2017.
Quynh N Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11961 1972. Curran Associates, Inc., 2020. URL cc/ htt/papprr2220/F11eee
neurips. 9ec2 Fcc02
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In Maria Florina Balcan and Kilian Q Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceed- ings of Machine Learning Research, pp. 314-323, New York, New York, USA, 20-22 Jun 2016. html
PMLR. httt:t:ts:///oooo
mlr htw.://iii......p.preeeeeee.... wttpppeeesseeeeeeeeeeeee
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL. /tll:ttttt::///peeeeeet
bett/forum2id=ryyu7-
Shai Mhnlev-Shwart.. Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub- -raddend solver for Association for Computing Machinery, 2007. doi: 10.1145//273496.12753 1273598.
URR.httpe http:::://doo..org// wtt.oo///......//.....
1273598
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Mach. Learn, Res., 19(1):2822-281 2878, January 2018. ISSN 1532-4435.
Trang H Tran, Lam M Nguyen, and Quoc Tran-Dinh. Smg: A shuffling gradient-based method with momentum. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10379-10389 PMLR, 18-24 Jul 2021. URL https: http:////cceeeee/..../e /tttas////// v139/t html
mlr., wwt.ppesss////.p.

---

Under review as a conference paper at ICLR 2022
Quoe Tran-Dinh. Nhan Pham, and Lam Nguyen. Stochastic Gauss-Newtor algorithms for noncon- VeX compositional optimization. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 9572-9582. PMLR, 13-18 Jul 2020. URL htttps://proceeeee .gg.ings..mm....m mml. preas/v119/trane di20 html
Sharan Vaswani, Issam Laradji, Frederik Kunstner, Si Yi Meng, Mark Schmidt, and Simon Lacoste- Julien. Adaptive gradient methods converge faster with over-parameterization (but you should do line-search), 2021.
Junyu Zhang and Lin Xiao. stochastic composite gradient method with incremental vari- ance reduction. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL URL/httts::/pproceeedinng www.inng.....ueeeeeee 382255557752223333050002ee233333
neur pttppp.cc///ppprr///////111
pdff
Junyu Zhang and Lin Xiao. Multilevel composite stochastic optimization via nested variance reduc- doi: 10.1137/19M128555) URL
tion. SIAM Journal on Optimization, 31(2)1131-1157, 2021.
https: //doi.://dd....
brrg/1. 1137/1 3M1285457
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence d'Alché-Bar Bue, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural In- formation Processing Systems 32: Annual Conference on Neural Information Process- ing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp- 2053-20663 2019. URL hwkphhtpss//proceed.gg...uuu
1 Abstratt.tttttttttc.cc html
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks, 2018.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A
TABLE OF NOTATIONS
Notation
Meaning
F, Global minimization function of F in
F. = min F(w)
hG
h arg min (z(2), i [n]]
Solution of the convex problem in (10)
minleks 2n - H1 a, 11 v &e (h(w!);;
(t)
An approximation of ( which is used as the search direction Framework
(1)
A vector that satisfies
T1 14 (1)( 11
V & (h ;1))] S 2²
for some > 0 and | 1 V, for some V > 0.
(1)
Us (t)
Solution of the strongly convex problem in (5)
1 n Ea H a, a (h(w((())) ;d)]1 + 1 [|||}
min
B USEFUL RESULTS
The following lemmas provide key tools for our results.
Lemma 3 (Squared loss). Let b E IR and define <(2) 11ll= b112 for E IR.. Then & is conver and Lg-smooth with Le 1.
Lemma 4 (Softmax cross-entropy loss). Let index E [c] and define
((2) = loog Σ exp(2k
za) = log
exp(wx 2)
for (Z1...., ze) RR where wk ek- with e representing the i-th unit vector (containing at the i-th position and O elsewhere). Then & is convex and L -mooohh with Ls 1.
The following lemma is standard result in (Nesterov) 2004).
Lemma ([Nesterov) 2004)). If o is Lmooth and convex, then for Vz E R
|[ < 2Lo(o(2) ((2.)),
(21)
where z, arg ming ((2).
The following useful derivations could be used later in our theoretical analysis. Since Φ; is convex, by Definition 2 we have
di (,((w;))) (.(h(w':)) + Vzdi(=) ==h(wos)) h(w; h(ww))))
(22)
Φi is convex and Lg smooth, then by Lemma
M where h = arg min.er dz(z).
V Vooi())
< 2Ls (or(h(w;;) (b))),
(23)
We compute gradients of f(w; i) in term of de (ww; i))
13

---

Under review as a conference paper at ICLR 2022
Gradient of softmax cross-entropy loss:
(d)((2)
(0)((2)
) )
Vol(z) ==((1;8) =
021
x==((w:)
2ze x=
where for j E [c].
1 + I(y
(z)(()
Ei-1 exp (
(24)
Ōzj ===h(w;))
Eieroliy exp ( (h(ne))) (c
j 1(y(o))
Eisn exp (h(w;i)l (M 1(00)))))))))
Gradient of squared loss:
[o)(2) 2=(mss))))) M(wss)
-h(w;)) - (0)
(25)
C ADDITIONAL DISCUSSION
C.I ABOUT ASSUMPTION 2
We make a formal assumption for the case lo(;;t) closely approximated by k(=;t).
Assumption 5. We assume that for all E [n] there exists some approximations k(w; Rd such that
R
(ky(w;)) - hy( i)1 S E, Vw Idd, i [n]] and [c]:
(26)
where k(:;i) are twice continuously differentiable (i.e. the second-order partial derivatives of all scalars k)(- are continuous for all E [n]),, and that their Hessian matrices are bounded:
[Ma]( = 10 (V i))l S G, Vio E TRdd i E [n]] and j E [c]-
(27)
Assumption 5
alloow prove the following Lemma that bound the error in equation (
Lemma 6. Suppose that Assumption 5 holld for the classifier h. Then all E [m]] and 0 <t< <
we have:
h(w((+1); h(((()) (0)) i) h(w()) (9 10 E
(t)
(28)
where H!! is defined to be the Jacobian matrix of the approximation k(w;; i) w
(w:i)
0kg (ky(w:))
Owa
_1 Jwkkww; ()w
gexd
(29)
(he())) Don
(wa() thos
h==w())
Additionally we have,
1 [0 (1000 22, [c].
(30)
Note that these result recover the when h(=; i) is itself smooth. Hence analyze our algorithms using the result of Lemma which generalizes the result from Lemma
C.2 ABOUT ASSUMPTION
3
In this section, we justify the existence of the search direction in Assumption 3 (almost surely). We argue that there exists a vector ((t) satisfying
11
(1) H1 (000)
2
14

---

Under review as a conference paper at ICLR 2022
It is sufficient to find vector satisfying that
(0)
H1 e o; (h(w()()) i)) for every i E [n].
(1)
Since the solution in Rd and (h i)) is in R this condition is equivalent to linear system with n constraints and d variables. Let A and b be the following stacked matrix and vector:
H
a V V= (h(((())
A
R.de and b
R
(4) V &n ( (+(
then the problem reduce to finding the solution of the equation Av = the over wver-paraeeterized setting where dimension d is sufficiently large (d > c), then rank A there exists almost surely a vector v that interpolates all the training set.
almost surely and
To demonstrate this fact easier, consider simple neural network where the classifier h(w; i) is formulated as
h(w; i) = T (W(L)
where e 1, W(L) E m.mx and W(2) E R w vee( (W(), w(21)) E Rd is the vectorized weight where d = I(m + 1) and is sigmoid activation function.
H1th defined to be the Jacobian matrix of h(w;; i) w(();
H = Ju diw: i) (w0=
@h(w:)) Oan
ah(w:)) Owa
E RRlxd
w=
then
HH())
@h(w::1
ah(w:l
8wg
A (t)
(1(
Rund
H
(h(w:n)
We want to show that has full rank, almost surely. We consider the over-parameteriza setting where the last layer has at least neuron (i.e. | = n and the simple version when 1. We argue that rank of matrix A is greater than or equal to rank of the submatrix created by the weights of the last layer (2) I::
ak(w:1)
Oh(w:1)
aw!a.
B
R
@h(wsn)
Sh (wr))
aw!! (2)
ow?
Note that li(,,v) i) is linear function of the last weight layers (in this simple case W(2) R" and (W(1) (0) TR"),, compute the partial derivatives as follows:
ah(w; i) @W
(W(I) (()); ; e [m].
Hence
(WW() x(0))
B
o (WWL) (00)
Assuming that there no identical data, and a is the sigmoid activation, the set of weights W(1) that make matrix B degenerate has measure zero. Hence B has full rank almost surely, and we have the same conclusion for A. Therefore v of the linear equation Av = b for simple two layers network. Using the same argument, this result can be generalized for larger neural networks where the dimension d is sufficiently large (d > nc).
able prove the almost surely existence of solution
15

---

Under review as a conference paper at ICLR 2022
C.3 INIIIALIZATION EXAMPLE
Our Assumption requires a nice dependency on the tolerance e for the gradient matrices H (0) v,0; (h(w ())) We note that at the starting point t = 0. these matrices may depend on e due the initialization process and the dependence of d on e. In order accommodate the choice of learning rate (7 DV=e in our theorems, in this section we describe network initialization that satisfies ! (0)
and
+t) where the gradient norm VV ( is at most constant order with respect to E. To simplify the problem, we only consider small-dimension data and networks without activation.
θ
About the target vector: We choose Ø; to be the softmax cross-entropy loss. By Lemma (see below), we have that the gradient norm is upper bounded by constant c, where is the output dimension of the problem and is not dependent on è. Note that when we stack all gradients for n data points, then the size of new vector is still not dependent e.
A bout the network architecture: For simplicity, we consider the following classification problem where
The input data is in ?R? There only two data points ,(()). Input data is bounded and non-degenerate (we will clarify this property later).
The output data is (categorical) in I {v = (1, ( = (0, 1)}.
We want to have an over over-paramen parrrametterized setting where the dimension of weight vector is at least
ne = 4. We consider simple network with two layers, no biases and activation functions. Let the number of neurons in the hidden layer be m. The flow of this network is (in) R2 + I - IR² (out). First, we consider the case where m
The first layer has 2 parameters (Wi, W2) and only neuron that outputs 200 wai1 (1) (t) (the subscript is for the coordinate of input data (+))
+
W222
The second layer has 2 parameters (W3, W2). The final output is
h(w, i) [wy (w)(w1)2 (1) + wya wa (w 21 + ( E R²
with [m0,, W2, W3, wa) T R.. This network satisfies that the Hessian matrices of h(w;;) i) bounded. Let Q and b be the following stacked matrix and vector:
H (0)
cb (h(w(()) 1)) V (h)
Q =
E R
4x4 and b=
E ER,,
H
Then we have the following:
V w lwy (w) 2
(1) + 102012
(1) }
w | ( a.
+ 122ar
(2) )
Q = Q(w)= =
(0
=
V [wa (
+ 1222 (2) )]
[wal (wr
(2)
+ waya (2)1 )
W3
w
+ "y (1)
(1)
0
w 1
11)
+ w2z 11)
(2)
(2)
(2)
w
+
w22z
(2)
w 1
+ wy
The determinant of this matrix is a polynomial of the weight w and the input data. Under some mild non-degenerate condition of the input data, we can choose some base point w' that made this matrix invertible (note that if this condition is not satisfied, we can rescale/add a very small noise to the data which is the common procedure in machine learning).
16

---

Under review as a conference paper at ICLR 2022
Hence the system Qu b always has solution. Now consider the following two initializations:
VE w' and note that Q(w) is a linear function of w and (ww") is independent of e. Then the norm of matrix Q(w(o) has the same scale with 1 Ve'
1. We choose to initialize the starting point at w(
2. Instead of choosing m = 1, we consider an over-vvvaaiin over-parameterized network where m & (recall that is the number of neurons in the hidden layer). The hidden layer in this case is:
( + 2,12
w1,1 1
(1) (1) w 1im 21 22m 22
The output layer is:
(1 (4) (2)
w1 1.1
2m W m.
(2)
(w
1
+
Wy 22 ju + +... ...
(1) (6) (2)
[w mi 21 w
(1) (6) (1)
2.m 22
mm
(1) (2)
w 1,2
2m
w m.2
(2)
= (wi,
+
W2
(8) (2)
Jw 12 + (w (1) (8)
1,m Wa 2.m m,
(2)
with
[w] (1)
1,
1, W2 ................................ W2
(1) (1)
(1) (2) (2)
1,1 1,2 ..... m. m Rmm
Hence,
(2)
(2) (1)
(1)
w
w
m
Wi,1
21
2m
w (2) (1)
(2) (1)
m
W
2
0
21
2m.
Q(w)=
(2) (2)
(2) (2)
(2) (2)
1 22
(2)
21
(2)
2m
(2)
0
(2) (2)
(2) (2)
(2)
1
11
w
11222
2 22
Hence, the number of (possibly) non-zero elements each row is 3m
For matrix of rank r, we have ||Al|2 < || S AfllA Since the rank of Q(w) is most
(ne = 4, independent of E), we only need to find the Frobenius norm of Q(w). We have
4
4m
[Q(w)]
90 2
Let qmii and Imaz be the element with smallest/largest magnitude of Q(w). Suppose that (:()) + /B 0, Jmin O and independent of Hence, ve Mmmnn S
(0,0) and choose # such that [[Q(w)]rr S
V22 V2 [-
Hence, [[Q(w)]I o
Therefore this simple network initialization supports the dependence
on for our Assumption We note that similar setting is found in (Allen-Zhu et al. 2019). where authors initialize the weights using a random Gaussian distribution with variance depending on the dimension of the problem. In non-convex setting, they prove the convergence of SGD using the assumption that the number of neurons m depends inversely on the tolerance E.
Lemma 7. For softmax cross-entropy loss, and h(w;;) i) E R., for Vw E IRd and i E [m], we have
Vz
Sc
(31)
Proof. By 24
have for i 1,...;
17

---

Under review as a conference paper at ICLR 2022
For j + ((y()))
06)(x)
2 =
exp (Ih(w; 1) - [k(w;; 8) r(gro)))
2
dxg (==((1;)))
Σ exp ((h(w; a) [/(wr; i) ((ggo))))
exp (lh(w:; 1) - (o: (())))))
2
S 1.
Σ (ofl) exp (Ih(w; i) [h(w:; 1) r(g(o)))
For j = I(y(0)):
(00((z)
2
Σ (f exp (Ph(w;; 1) - [h(w:: M(( 2
dzy 1==((a;))
Ex= exp (Ih(w; 1)ls - [h(w; (gge)))))))
Enyro exp (1h(w; i)ja - [k(w;; (w; (() Ek((() exp ([h(w; 0)), - [n(w; r(g(o)) S 1
Hence, for I,...,n, n,
00.(()
0r, la h(ws)) ) 2
V V=)((1)
= =
Sc.
j=l
This completes the proof.
D PROOFS OF LEMMAS AND COROLLARY
PROOF OF LEMMA 1
Proof. Since i( are twice continuously differentiable for all i E. [n], we have the following
Taylor approximation for each component outputs h-(:;) where j E [c] and i [n]
h)( = hy(w(()) (0))))
1 ())(000;;)) Junh((;; ( 1/2 (T) M ((()))))))))))))))))))))))))))))
(32)
where (i) is the Hessian matrices of h:(: i)at ((()) and (((1) (w + (1 (t) for
some a E [0, 1]. This leads to our desired statement:
((1((+)); i) (() ((())(1)))) h(w(();) - 17 111HH((000) (1(00(00)) + tc(0.
where
1 - (1)0
Mr. (w)(t) (110) (1(1) j E (c).
Hence get the final bound:
(4)
1
(1)
(00) M.M ( (1i1)) (1)00))))))))))))) (609) /
[
2
1110))911101111 ي (1)))
2/
(110)111111111))) j E ld.
18

---

Under review as a conference paper at ICLR 2022
PROOF OF LEMMA 2
Proof. From Assumption
3 we know that there exists 022 so that
11 1 n. ( s
2n
and |100 1 < V. for some V > O. Hence,
1 n
| 11 000 a; (0(
2² ||?!!11
=²² -
=²
(1 マ 1s?
V
Since Uh reg is the optimal solution of the problem in 15 for 0 S <<T, T, we have
11 20 2n
e²
V
1 (1)
Uo - as ( V. Si ;0)] H
I1od 22 S (1 + 2 )6?
2
Therefore, we have 17) and ||u reg
21 s 2 V for st<T.
PROOF OF LEMMA
Proof. 1. We want to show that for any E [0.
6laz) + (1 - a)22) S aσ(21) + (1 ())(2)), V21, 22 IR;
(33)
in order to have the convexity of ø with respect to (see (Nesterov 2004
For any a E [0, 1]. we have for V2 22 E R:
al|=ı - b112 + (1 22 b|l ||a(1) b) + (1-a((2 - D)
= -a - + (1 (1-a) bl1 - a 1| - b12 (1 - 2 - bl1?
2a a) - b, b)
(001-a)]laz - 611 (1-a)al|=2 bll 2a(1 ai]l || bll 1| -
= a - a) (1 bll - -1 - b1) 2 0,
where the first inequality follows according
Seuuch-SShwwaziiee inequality (a, b) S ||l|| |bb|| Hence,
1
a 021 + (1 22 b11a < 2 21 - b12a
(1 a)
2 1| b112.
2
Therefore, 33 implies the convexity of á with respect to 2.
2. We want to show that 3hE > 0 such that
()(21) - vo(22)ll & Løl121 - 22ll, V21, 22 E R..
(34)
Notice that Vo(z) - b. then clearly V21, 22 E RRC
[[V((z)) - v = || - -22l1-
Therefore, 34b implies the syssoothhnsss of á with respect to with Ls 1.
PROOF OF LEMMA
Proof. 1. For Vzi, E Re and < k < c, denote 4s, = exp(w] =1) and uk,2 = exp(wx, x2) and
using Holder inequality
9
1 1 + 1,
bu 5
lax
Σ
bbx
1
where
(35)
p q
1=1
k=
19

---

Under review as a conference paper at ICLR 2022
have
Ø(az) + (1 (1-a):2 2))2) = log
exp(wx ( (a21 + (1 - a)22)) (1-a)22))
= log
a
222
(1-a)
1-a
35
log
Σ
a.d uk11
Σ ki=
uk,2
(1-a) (1-a)((Ta) (1-a)
k=l
c
= a log
Σ exp(u 21)
+(1 a) log
exp i 22)
= +1 (=)(
where the first inequality since log(z) is an increasing function for Var and exp(v) > for Ye E R. Therefore, (33) implies the convexity of ø with respect to 2.
Note that [>>())]] & Lg if and only ((2) La-smooth (see (Nesterov 2004 )) First, we
compute gradient of ((2):
For i + a:
0x(2) exp(2i 2a)
dz Ek=1
expl2x - 2a)
For i a:
Ex kitta exp(2x za)
-E k= exp(2x 2n) +
0z.
Ei= exp(2* - 2a)
Ei=1 exp(2x (2k - 2a)
exp(2; - =aa)
+ Ex exp(2x 2a)
Ei=1 n= exp(2x - 2a)
We then calculate
P+(s)
8. [ddls)
8z dey
Oz.
For i =
02 0²)(2) exp(2; 2x)1>> exp(2k 2a]] exp(2; 2a) exp(2; 2a)
Ōz,0zz
Dii= k= exp(2* ]0]]
expl2s 2a) 1> k= exp(22 2k 20) - -cxp(2 2a)1
Ei= exp(2* 2a)]
For i *
Sb((2) -cxp(2; 20) exp(2; 20)
0z,0z, 1Ei=n exp(2x (2k - )a)]²
Denote that y; = exp(2; - 2a) 2 0, i E [c]. we have:
For i
y: I 1= Us 9:)
02,02,
1= 8k)
For i j:
(P((2)
1y:
02,0z.
20

---

Under review as a conference paper at ICLR 2022
Recall that for matrix A (aes) E Rox:: ||A|| 2 ||A| =ii=1 Ej=1 lats?. We have:
+ 2
dz
EE yk
y
Uk
y11²
Σ (y:2)1)
A=1
jti
1
1x.)² 2y Σ yk- + y
Σ
(21:15)
y1
E yk
V5
yk 2y Σ Us vē
Σ v
Ei=1 yk-)
k=1
Therefore,
82)(2)
[ -
Ozy
1=1
v )(
ykh) 2( 2 vi
yk)
+
1
v
>
k= yz)
i=1
1mml
i=1
1m
s=1
km
k-1 )2
ykh)
km
= 1,
Ei= V/k)
1= yk
where the last inequality holds since
Σ
yk
S
vi
yk),
k=1
i=1
k=
which follows by the application of Holder inequality 35 with p 2, 2, 0g
3/2 and
by yk (Note that y/u 2 0, & E [c). Hence, |V I Ls with Lg = which is equivalent to
La Lassmoothness of Φ.
PROOF OF LEMMA
Proof. Since k( are twice continuously differentiable for all i E [n]. we have the following
Taylor approximation for each component outputs ky(:;) where j E [c] and i E [n]:
ky ky (;;) = ky(w(() (1)))
20 (0 ;)) Jwnk (w: 1w 2
_ (1)))))))) Ma. ( (1))))
1
(36)
where (w)( is the Hessian matrices of by (::t)at a0 and ml() = aw + (1 a)w((+1) for some a E [0, 1].
Shifting this back to the original function (-;()) we have:
hy (w((())));) i) = (w((()+)); i) + (h)(w((+)); - ky(w((+));;))
36
ky(w) :) Junky kukky(;; (w: i) 10 (000 + 1 (1)) Mi (n))))))))))))))))))))))))))))
+ (1)(w(((2));)) ;)) - ky (wo(+)); ;));
= -,(((())))) v) - -J ki (w: 10 (1)) + + (1) Mas (1(1
+ (++(w ())) :)) - Ky (w i)) + (w) (1))) - hy (w)( :))
which leads to our desired statement:
((1()++1) (1) (())))))) )( 17 (1,00 (1)) + c
(
21

---

Under review as a conference paper at ICLR 2022
where
1 2 (1)) (1
(1)(w((tt)))) ky (=((((+))) - -ls(w(0;;),, j E [c].
Hence we get the final bound:
c S 2 (n) (11)) (7 (1)00)
(1 i) ky (w) (k)(w(())) - hy (w())));
2 (1pt) Mi (1) (1)) (1)10 +2,,
(n) 1110)11110011 | ( (1) 2e
/ (,/00)911110333 28, j E ld.
PROOF COROLLARY 1
Proof. The proof of this corollary follows directly by the applications of Lemmas 3 and 4
E TECHNICAL PROOFS FOR THEOREM
Lemma 8. Suppose that Assumption holds for > and Assumption 3 holds for V 0, and
((0) Ue vereg. Consider T8 = for some D > 0 and s > 0. For i E [n] and 0 S < T, we
have
10 1 7 + (V + 2))D2)232.
(37)
Proof.
From 14), for i [m]. E [c]. and for 2 1 T, by Lemma and Lemma 6 we have
1 [
(1
s / (V + 22GGD& 2: <4 + (V + 2)GD3)
where the last inequality follows by the fact 1|10 = pe 2 V of Lemma and v7()) D DVE. Hence,
le 11 = Σ 1 (4 + (V 2))))22
Lemma 9. Let (!) be generated by Algorithm where we use the closed form solution for the 2 outer loops for some constant B
search direction. We execute Algorithm for
assume Assumption 7 holds. Suppose that Assumption holds for G > 0 and Assumption 3 holds for > We set the step size equal to (1) = DV for some D > and choose a learning rate (0) a
for some E (0,3) 1))- For i E [n] and 0 < t < T, we have
a Lo
(1((v(+));0)) 13112 < (1 +1+000000 {)) h; 2(1 - 3a)a (a)a("(o, (e)(u(() - (h
(3e + 2)
+
c(4 + (V 2)
4
+
2
||
(t)
H
(t) (t)
veg a, (0:
(38)
22

---

Under review as a conference paper at ICLR 2022
Proof. Note that we have the optimal solution (1) T. From (12), we have, for E [n]
reg for the optimization problem 15 for 0 S
h(w(+1);)) i) h(w 12 rogi 2)
= -((w(t);)) ;) - .7 (0) H (1) U+ rog +G
(1)
(1)
;)) aj
(1) v Si (h(w(())) +c; (1)
(1) 11101110000 oene
(0
Hence, we have
[1 - 11?11
()( 1) hn 0; V ( -
(1)
(n 1T!"0!'
reg V ;]]]]|?
- 1)((w(;;)))))))))))))))) hī1l 1 (a =
+ |le/"112 + |177" (
(t) reg
a " (ho,((((
2. (h( - h a
(1) V 0 (h ()))
+ 2. (M(w());) c (1)
- 2. ;)) - -hi, 17 (1) H1
U+ reg a V (h(
2. (a, 0 V. (h
())
+ 2 (a, (9) V - (h(w (w (0; i)); 11 H (1)
at a ((w0((()))
reg
- 2. (c n H v/ reg
a V V. (k(w 1)))
where we expand the square term. Now applying Young's s inequalities: (/ e)) s
||]|
+E/22]|1o11
2/2
for 0 and 2 (u, S || + || we have:
[1((u((+1) () hr1??
[1((w();)) (1) h111 +
+ 11 (2) ui me - a " v=ii(h(w(";)))
-2a (1 - h (k(
+ 2 (1l(w((;;) - h1 + 1c 10
E
" [1l(wo(0;) - 11 |n (2) 11 (1) (t)
U4 rog - af V (=
+2(a 002 V 1)) - 2||c 10
+ +2 (1 H
(1) 2i scg
(1)
(1)
V (. (0(w (1))
a,
(1 (1(w(())))
- h; 3(0 10 12 =e ;))l
3+ ||e,") (1) 1|+ 3+ 2 |17/ (0) H1 0
2)
a. vo
20
(4) (o (1( - (b;))
Note that from 23 we get that / ( (0; i)]l1 < 2L -z: -x) Applying this
and using the fact that a
<
T.g
a for some a E (0, }), we are able to derive:
< (1 + 8) ((w((((((())))))))))))))))))))))
(1) h1 112 - 2( 3a (0.
(b.(h(((()))) (x()
35 2
|k(()) 12+
35 2 ||7 H1 (1)(
2z a (1)
(t)
+
E
8
< (1 + ())
- - 2(1 3a
1 (0((((( (x(1)
23

---

Under review as a conference paper at ICLR 2022
35 + 21 4 (4 + (V + 22GGD)) +
38 + 2
110001100000 ufiice ieg == (1)1?
+
where the last inequality follows by Lemma 8
Lemma 10. Let w(t) be generated by Algorithm where we use the closed form solution for the search direction. We execute Algorithm forr T 6 outer loops for some constant / > 0. We assume Assumption SirtommThoiie holds. Suppose that Assumption holds for G > and Assumption hoolds for V > 0. We set the step size equal to r7(0) DV for some D > 0 and choose learning rale
a
(0) (1 + + (-1) (1+ (0) Based on B. we define o;
& with a E (0. 3)-
L.
We have
1 - s
e LoLo1)))
1 (1((v(0);)) - 1,
T t=0
2(1 3a)aB
e L
+
(3e + 2) [c(4 + (V + 2]GGD) +8+ 4V] cc
8a(1 - 3a)
(39)
Proof. Rearranging the terms in Lemma 9 we have
(1++)
6,(h(w(0:0)) -o(h1)) - 2(1 - 3a)
- (1)
| [1( - h3 11²
(1)
a
1
<(3 + 2)c(4 + (V + 2)
8(1 3a)
35 + 2
||1 (1) H
Ue reg a (1 V (h(w (1))1 ;))]1
(t)
2(1 - 3a)
(1)
(1++)
|1 (4; - -h,11² -1);;;
(1+
[tt - h2112
2(1 - 3x)
(1)
a ([+1)
ai
e Lo
+ 801(1
(3e + 2)c(4 + (V + 22)GD²
3()
0 L1
35 + 2 ||
(t)
H (t) (t) reg a: (1 v (0
2a 30)
The last inequality follows because the learning rate satisfies a; (0) = a
S
a and for = Le
Lo
I,..., T = _ for some B > 0
(1) = (1 (1+ (t-1) = (1 (1+E)aa s {1+ 10) = (1 E) B/e a < a
a
L Lo
since (1 2>//> se, O. Moreover, we have
1
L t = 0, ... T - 1.
Taking the average sum from = O,...,T T 1, we have
[o.(h(u(())))) oi())) <
1
(1+
[k( hill?
T t=
2(1 3a)T
a (0)
cd Ls
+
[3E + 2)c(4 + (V + +2GD2'2
Sa (1 - -3a)
8 L
32 + T-1
117 (1) H.
(0) rey
-a, Ve
+ 2a(1 - -3a)
6 T
1=0
@ (1 +
[1/(w h
2(1 - 3a)a3
24

---

Under review as a conference paper at ICLR 2022
e Lo
+
(33 + 2) + (V + 2)GD))
8a (1 30)
9 Lb
38 2 T-1
(t) (0) (9) H re
-a. af (M
+ 2a 1 3a)
6 T
1=
Taking the average sum from i = -.,..,,, we have
T-1 n
(0r(h(((())))
n1
@ La(1+E)
1 Σ
;)) - 1
2(1 3a)a
e Ls
c(3e + 2)e(4 + (V + +2)GD&²
8a(1 30)
e Ln
30 + T T-1 Σ
Σ
117 (2) 11 (0) ((()) 0c
2a(1 - 3())
T
1=0
1=1
17
e Lg +
1 n
(1( ;1) h?ll
2(1 3a )a
71
e La
=33 + 2)c(4 + (V + 22)
8a(1 3a)
L
38 +
+ 2a(11 - 3x)
(2 + V)&?
(40)
Note that
c ())
T 1= n Σ
(()(0)))))))) (b)))
(41)
n
1=0
Therefore, applying
to
we have
T
(ww ;0) ox(
T
t=
@ LL + E)
|1 (0) - 1,
$
2(1 3a)a
e Lo
(3e + 2) [c(4 + (V + +2))D) +8 4V] ..
8a(1 3a)
which is our desired result.
PROOF OF THEOREM I
Proof. We have
F. min
F(w)
min wERd
Σ [(w))
min wER
Σ Silw)
WERd
n1
n
1=1
a
n
1 n
min (f((w)) WoR
(hī))
(42)
11
n
71
1=1
Hence F. 1 Em (x+) 2 0. Therefore
1 T
F.] = 1 T Σ F(w(())
Σ
1
"> [f(w(9;)) -(()))))))))))))111)))))))))))))
F,
1 Σ (n(()t) )
T
T
n
i=1
25

---

Under review as a conference paper at ICLR 2022
T
30
e Lo + +
n
;1) -1
2(1 - a/
n
+ Lo +2)
[c44+ (V +2)GDD) +8+ +V e
80 3a)
F TECHNICAL PROOFS FOR THEOREM 2
Lemma 11. For 0 S T, suppose that Assumption holds for V 2 and v(t) satisfies 19
Then
= 2(=² +V
Proof. From (| ot rogll S Using ||a| - 2||a b112 2||6|| 2 we have
11 21/ v. regl 12 + 2 2
(t)
2s² 4-4+21
where the last inequality follows since || legll < 2 + V for some V > 0n Lemma
Lemma 12. Suppose that Assumption 2 holds for G and Assumption 3 holds for V
0.
Consider (0 = / for some > 0 and & > 0. For i E [m] and tt< T, we have
( 1 < c(2 + (V + ||
(43)
Proof. From 14) for i E [m]. j E [c]. and for 0 < < by Lemma | and Lemma 6 we have
(1) [.
1 ] 10000 2 2s ~ 2 + V + 2)D' + 2 e(2 + (V + +2)GD²
(n
where the last inequality follows by the application Lemma 11 [nand ()()) Dve. Hence,
||e 11 Σ 1=1
2 (V
Lemma 13. Let ((()) be generated by Algorithm where v(t) satisfies (1 We execute Algorithm
2 for T = outer loops for some constant 3 O. We assume Assumption 7 holds. Suppose that
Assumption holds for >> 0, Assumption 3 holds for V > O and Assumption 4 holls for H > O.
We set the step size equal to (p()) DV/e for some D 0 and choose learning rate a (t) I E.
for some (0, 1). For i E [n] and 0 < t < T, we have
(h(w)(++);))) - 1771 < (1+ - =)]l)(((0 - - 2(1 4a)a 10x (h(w (x,)))
-2(1
+ c +3)
(V
+ 4E +3 || (1) H (1) (5)
1 (0 11
(44)
26

---

Under review as a conference paper at ICLR 2022
Proof. Note that wl() is obtained from the optimization problem (55 for 0 I t <<x T. From 9 we have, for i E [n]]
h(w(++1); ;i) = h(w!() - -1) ;),)
= =Mw]l);)) - 11 H (1) (0) + + (t)
=h(wl); :)) 11) (0) H (t) (ult) v - V c0))
- (1) H (1) (1) (1)
reg a; V (b((((())))
Hence, we have
[1((wlet))))) 1ill?
[I(((o(()) (1) h15 11 H (1) (r(t) -a V (h((((
+1(²) -11100 H1(h) U- reg
10 V>di(((o') 1)
a
= -1) - n; 17 ( (v - ) 12 + (a. (k
+ 11c/0 H v. rey
(1) V (h(w((
2. (b:) h n
(v - v kg))
2. (h(wd(;;)) 14 at 19 V. (h(( :1)))
+2 2. -M( ())
-
2. (b(w0);)) M (+) H
(1) (0)
a. V
reg
+2 2. (n H( (v(()) U reg) )
(0)
(1) V. (h(w(()
2. (n) 1 H (0) (v(0) us reg):
+ (1) 0 H ( (u(0) (( ree) 17
H
2 reg
(t)
a, (1)
<=(((((()))
2. (a; (1 (h(w(()
+ (a (h ;1)), (1) H
aj (
reg
- (e (0)
(1) H Vo reg
(1) (0) (1)
a; V (h(w ()))
where we expand the square term. Now applying Young's ' inequalities: 2), w) s ! (=/3)\||o1 for and 2 21 u) < ||0|2 + || we have:
[ - 11112
-1h(ww(0) i) --ii--hh 12 + (17( H (1) (v 0000 (I (
+ +1e!00p2 + 11
11,1110000 11 vit) reg a, V (..(((((w");)))
+ 3 (1 ;)) - 11
E
10 H (v - heyg))
2a; 10 (k(ww))) ()) - h; V (h(w (1))))
3 (1((10 - - 3 1: 101
E
[1((w( 1) - 2
H
U rgg
3
+ 3(m H. (1) (1)()) - v 1 2 + 3(0 (1)
PI ()))
+ 10
3||n u reg - [.
(1+))]l((w())) 2lll + 4( (1) V
+ (4+ 3)
(n)0) H (v(1) = 12 +
3
|1:00
)
+
27

---

Under review as a conference paper at ICLR 2022
4+ 3 2) |1(0) 1 (0 ve - -
20 / (ob (h(w i)) o3 (h:))
Note that from (23) we get that V (h( (w( =])1 & (h(wl)
Applying this
and using the fact that at" S r.g for some a E (0, 4), we are able to derive:
[1 1++1); 1) - 1,
$ (1 E) (1 (1) h 2(1 40)aa 2 (6: (h(wl))))) +v(())]
4. +
|n/ H1 (1) (v(0) u re 112 2
(1)
48 + (4)
4 +3
|,7 (t) 11 Uo reg a t v " 10 1))1
(t)
+
(0)
(1 E) ()) ;1) - h11l2 - 2(1 4a)a;
(1)
| (h(w -))))
48 + 3 D2
H²
| 2 leg 2 +
(t)
48 + 3 (1
E
46 + 3
10 H
(1) (t)
a (h(w (1))|
U4 ieg
(b)
S (1+ + =) h)) - 11 2 4a)a; 1 10, (1)) (b)))
46 + 3
D²H² .6² 48 +3 c2 + (V +2 2)
8 48 +3
||0 (1) H1 (1) rer reg a
(1 V (k(w (0)))
(1 + +1+))l((w())) (1) :)) 11 - 2 - 4aja; (o.(h((();)) (x7)
+ = + 3) [2 c (V 2 2
+3 |,7 (1)
H1
2t ueg at " V a (h(w (0: 1)
where (a) follows by using matrix vector inequality |H < |||||||||| where H E Red and E Rd and Assumption in 20) and 17(t) = DV for some D > 0 and > 0; (b) follows by the
fact that [|v(() u 1o < 2 in 19 and Lemma 12
Lemma 14. Let (t) be generated by Algorithm where u!!) satisfies 19 We execute Algorithm
for T = outer loops for some constant 3 0. We assume Assumption holds. Suppose that Assumption holds for G > 0, Assumption holds for V > 0 and Assumption 4 holds for
H > O.We set the step size equal to rp()) = D E for some D > 0 and choose a learning rate
a
(1) {)
(1 =)+a)a Based on B, we define a (0)
e.
x with a E (0, 4).
We have
1
1
-
(c())
T
71
1=0
Lo
+
-
2(1
4a 1
1=1
8 LA +3)
I + c(2 (V + 2)GD))++ +2 V..8. .8.
(45)
20(1 4a)
Proof. Rearranging the terms in Lemma 13 we have
(1 + $)
1 (0=x))++)); -h, -1,11 (1)
(:(h(w();)) (x(h)) < 2(1 4x)
|| (,(());;) -
a
28

---

Under review as a conference paper at ICLR 2022
1
+
<(4e + 3) [D + +c(2 + (V +5²
+ 2)G
2(1 4a)
[t)
a
+ 2(1 - 4a)
1
45 +3
||, (1)
H Uz reg
(1) (1)
- a 1 <h(( (1))1
(1)
ai
E
(1++0)
(1 e)
[ -h;
[1( n?l??
2(1 4a)
(t)
a (++1)
aj
@
+ 2a(1 - 4a)
EE(EE + 3) D2 + d2 + (V+ + (V+2+2)GG
@ Lo
4 +
1 (1) H Un reg
(1) 11)
a. . (
+ 2a(1 4a)
(46)
The last inequality follows because the learning rate satisfies a; (0) a
S a
and for L =
Lg
to
1, 1,..., T == 8 for some B >>0 0
8 (t) = (1+ + =)aa (1-1) =)a = (1 (1+e)'a < {1+ (0) = (1 + t)/B a
a
Lo S
La
since (1+z) se, > O. Moreover, we have a;
S -
ما
t 0, ...,, 1.
a,
a
Taking the average sum from = O....., T 1, we have
T
- ())(k(((0)0))))
S
1
(1+
[h(w(0);)) - :11
T t=
2(1 4a)T
a; (0)
e Ls
+ 2a(1 4a)
c((e +3)
[D c(2 (V + + 2)
e L
4 T-1
+ 2a(1 - 4a)
E T Σ
In H
Vineg a (M(
e0 L (1 +E)
E: (1; 1) - hī1?
2(1 - 4a)a3
e Lis
+ 2a (1 4a)
544s + 3) D2 + c(2 (V + 2 +2)
e0 Ls
4E + +31 1
T-1 Σ
(1) 0 H
a. a."' (
+ 2a 4a)
6 T
rcg
1=0
Taking the average sum from i = 1,,..,, n, we have
T T
(0)) - ox,)))
1=0
1=1
Lo E)
1 n
Σ |1 ();)) 111l2
2(1 40)
n
i=1
LoD
+ 2a(1 4a)
=(4s + 3) [D2H2 + +c(2+ + (V + + +)GD2)]
e LB
48 +31
1
T
|1 H1 (0 (c) reg
a. [00((((())))
+ 2a(1 40.
T
17
Lo +)
1 Σ
[1(w (0) 2) - h
E.
2(1 4
n i=1
29

---

Under review as a conference paper at ICLR 2022
e La
8(4 + 3) [ +22
2nx(1 4x)
e L$
4 +
(2 + V)&²
(47)
2a 4a.
Note that
1 Σ
T Σ
[w (0:4) (b,))
(48)
T
Therefore, applying (48
to 47 we have
T [1ol1: () - (b())
e L +
Σ
2(1 4a)a3
i=1
è Ls
(4s (4s+3) [D c + (V + +2+2)) +2 + V] -6.
20 4a)
PROOF OF THEOREM 2
Proof. From
42 we have F.
1 ni
Ei= di(h;) 2 0. This leads to
n F.
0011)) )
(l) - P.]=
((o((0;;)) (s(h1)]
n Σ
T
42
(1x - (1+))
T 1=1 11
45
c1L
n
()(w())))) - -1
2(1 31-400)a3
8 Lo
1D2 2 + c( + (V+ + +2)GD2) +2+ E.
2a(1 - 4a)
(49)
PROOF OF COROLLAARY 2
Proof. For each iteration 0 S t < T, we need to find (()) satisfying the following criteria:
[1o(())
(t) rey 2 S E²
for some > 0. Using Gradient Descent we need On log( = O f log(?)) number of
gradient evaluations (Nesterov) 2004). where L and μ e² are the smooth and strongly convex constants, respectively, of V. Let
(v) 1 (t)
H(()) (1) (h ie [m].
(50)
Then, for any v E IR
V V. = (0() (T In H7,") a. V...(h( ;0)]] ie [m].
(51)
30

---

Under review as a conference paper at ICLR 2022
Consider (7())
DVE for some D 0 and O, we have for [n] and 5t <T T
20
(1) H H 1 S (17 |
D²
Hence,
(u)il 1
(b) + for any v E R which implies that L D2 H2 + E² (Nes- D +s" 2²
terov 2004 and j (2n
Therefore, the complexity to find w(t) for each iteration is
D'H log( 2)
Let us choose
<<S S 1. From
we have
Lo
Σ (F( - F.] S
Σ ();) - 1
4a)a8
7e Lo
[D2 + c(2 + (V +3) +2 VJ =8= Ne,
20 4a)
where
N [1- 11-10
[1((w()):)) - -1;ll²
7e Le 2a(1- laj
DD + c(2 (V
+ V
n
1=1
Let E Ne with 0 E s N. Then, we need T
N# for some to guarantee 5
miiogisT-1(F(u00) - F.] s + EE - F.] S 6. Hence, the total complexity is
O
2 (E2/N) (N) log( )
N
31


Reviews:
[{"review_id": "qFQvp2HqIF", "reviewer": "Reviewer_mfHX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths: the paper is fairly clear, and the proposed transformation is certainly a novel way to solve a common class of problems in the machine learning community.\n\nWeaknesses: I'm finding it extremely difficult to evaluate the significance of this work.  I respect that there's value in providing a new perspective on an old problem (with correspondingly different asymptotic bounds on its performance), but unless this proposed method is demonstrably useful at solving a concrete problem, I'm not sure if it's significant enough for ICLR.  Specifically, the version of this paper that I would probably feel good about accepting would kick all of sections 3, 4, and 5 to appendices, would succinctly state Algorithms 1 and 2, and then would spend the rest of the paper evaluating these algorithms on real problems.\n\nAt the same time, I don't want to discourage this kind of work, so I would honestly be satisfied seeing this proposed algorithm applied to _any_ problem, but as it stands, I don't think I can accept.\n\nedit: raising score to 6 after author's updates---still would like to see empirical analysis.", "summary_of_the_paper": "The authors formulate a way to transform finite-sum optimization problems in a proxy strongly convex problem, and prove that it converges to a global minimum in a number of gradient steps that scales inverse quadratically with the tolerance.", "summary_of_the_review": "The authors propose an interesting and novel algorithm for machine learning, but it's unclear how significant it will be.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "g5AzZ3Dj5K", "reviewer": "Reviewer_eoVW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The submitted work presents some interesting result, such as using the composite structure for machine learning loss functions, and approximations approach to determine the descent direction. However, I have some concerns,\n1. The formulation is not new. This is a quite well studied formulation in the optimization community. For instance, the authors can check the work of Lewis and Wright 2016. For their result, non-smooth outer functions can be allowed. So the proposed approach is not novel, and the authors should discuss these existing work.\n2. The obtained complexity result is not strong, as it is in the sense of\n$$\\min_{0 \\leq t\\leq T-1} [F(w^t) - F_*] \\leq \\frac{1}{T} \\sum_t [ F(w^t)-F_* ]  = O(\\epsilon) . $$ Given the good properties of the problem. \n3. It would be great if the authors can provide numerical experiments, to demonstrate the performance of the proposed work.\n\nThe author addressed my concerns fairly, as a result i raised my score by 1 to 6. ", "summary_of_the_paper": "The submitted paper considers a composite formulation of machine learning loss functions, where both the inner and outer functions are required to be smooth. Two algorithms are proposed for the considered formulation, with corresponding convergence results. ", "summary_of_the_review": "The paper provides certain interesting result, however the novelty of the paper and advantage of the proposed algorithm need further justification. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SQ1EC0xrGSW", "reviewer": "Reviewer_HAWj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "*Strengths*: Overall, the paper is well-written, the problem\nis well-motivated, and the background material is sufficient. \n\n*Weaknesses*: Unfortunately, I will have to recommend rejecting\nthis paper due to a critical mathematical error, namely, **the\nconstant $V$ used in the proof of Theorems 1-2 does not have the\nproper dependence on the tolerance $\\varepsilon$**. To elaborate,\nnotice that the stepsize $\\eta^{(t)}$ in Theorems 1-2 is $\\Theta(\\sqrt{\\varepsilon})$\nand that Assumption 3 (essentially) states that $V$ is a scalar where\n$$\n\\|v^{(t)}\\|\\leq V,\\quad\\|\\eta^{(t)}Q^{(t)}v^{(t)}-b^{(t)}\\|={\\cal O}(\\varepsilon),\\quad t\\geq1,\n$$\nfor matrices $Q^{(t)}$ and vectors $\\{v^{(t)}\\}$\nand $\\{b^{(t)}\\}$. Even under the generous assumption that\n$\\{Q^{(t)}\\}$ and $\\{b^{(t)}\\}$ are bounded, the\nassumption that $\\eta^{(t)}=\\Theta(\\sqrt{\\varepsilon})$ must imply\nthat, at the very least, $V=\\Omega(1/\\sqrt{\\varepsilon})$. It then\nfollows the right-hand-side of the bound in equation (18), and similarly in Theorem 2, is no longer $\\Theta(\\varepsilon)$\nbut rather $\\Omega(1)$ due to the $V^{2}\\varepsilon$ term. As a\nconsequence, **the convergence analysis in the paper is no longer\nvalid as it can no longer be shown that $\\min_{s\\leq T}[F(w^{(s)})-F^{*}]=\\Theta(\\varepsilon)$**\n\nBesides the above major issue, I have a few minor issues with some\nof the other material in the paper:\n\n- [p. 4-5] Lemmas 1-2 are classical results and should be replaced\nby citations to avoid giving the impression that these are new contributions.\n- [p. 5, 6, 14] The use of  \"apparently\" in several important\nstatements in this paper implies that these statements have some degree\nof ambiguity to them. This kind of wording should be removed if the\nauthors are making a formal argument, e.g. Appendix C.2, or the authors\nshould be explicit about their lack of knowledge.\n- [p. 6] What is the definition of \"smooth\" in Remark 1? If\nit means continuously differentiable, then clearly $\\|J_{w}(\\nabla_{w}h_{j}(w^{(t)};I))\\|$\ncan be unbounded even if $w^{(t)}$ is bounded, e.g., consider the\nunivariate function $h_{j}(w;i)=w^{3/2}$ on $[0,1]$.\n- *Minor typos*:\n1. [p. 3] ... this paper **focuses** on deep neural networks ...\n2. [p. 9] ... for non-convex **problems** (Ghadimi & Lan, 2013) ...\n3. [p. 14] ... this result can be **generalized** for larger ...\n\nEDIT: The authors have uploaded a revised version of their manuscript that has addressed my main concerns. The only issues that prevent me from assigning a higher score to the paper are: (i) a lack of numerical experiments and (ii) the use of non-standard assumptions (in particular Assumption 3) that are difficult to verify in practice.", "summary_of_the_paper": "This paper presents a new optimization method for finding global minima\nof nonconvex finite sum problems. In particular, the summands are\nfunctions of the form $\\phi_{i}\\circ h$ where $\\phi_{i}$ is convex\nand Lipschitz smooth, while $h$ is nonconvex. Each iteration of the\nmethod consists of solving an auxiliary regularized least squares\n(RLS) problem, followed by a gradient step. Additional analysis is\ngiven for when the RLS problem is solved inexactly. Finally, a claimed\n$\\tilde{O}(\\varepsilon^{-3})$ complexity is established under strong\nboundedness assumptions on various solution sets.", "summary_of_the_review": "Despite being a well-written and well-motivated paper, I have to recommend\nrejection due to a critical mathematical error. However, if this error\ncan be resolved in a revision, then I would be open to increasing\nmy final review score.\n\nEDIT: The authors have uploaded a revised version of their manuscript that has addressed my main concerns. I now \nrecommend a score of 6 for the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CototJ66G5u", "reviewer": "Reviewer_ZKUZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths: the design of the algorithms based on the particular formulation used; the underlying analysis\n\nWeaknesses: While this is a theory oriented paper, the theoretical portion is not strong enough to compensate lack of an experimental study. I am unconvinced about the novelty of the analyses. The authors should provide more convincing arguments that the entire material is unrelated to derivate-free second order algorithms and for example, BFGS.\nRegarding Theorem 1, something is strange with respect to \\beta. If beta is large (goes to infinity), it increases the number of iterations, yet the right-hand-side in (18) goes to infinity. It should be the other way around. \nTo approximately solve (15) or its original version, I wonder why the authors don't consider conjugate gradient descent. It works well for quadratic problems. ", "summary_of_the_paper": "The paper provides a new gradient-based algorithm. The algorithm is based on the observation that a loss function for a single sample can be written as composition of two functions (the logits and the actual loss function). It computes the direction by means of solving a quadratic MSE problem. They provide a convergent analysis of the algorithm (there is a version where the quadratic problem is solved explicitly through a closed form expression and a version where gradient descent is applied to solve the problem approximately). There are no computational experiments. \n\nThe main contributions are in the algorithms themselves and the accompanying analyses. It's unclear how novel are the proof techniques since everything resembles second order algorithms. The authors also claim the actual reformulation to be a novel contribution however such a formulation is straightforward and used in many contexts (some of my lecture slides from years ago show the formulation used by authors as a possible formulation for the overall loss function). Despite of this, the design of the algorithm should get credit. ", "summary_of_the_review": "I give authors credit for the algorithmic development and to a certain degree analyses. They are over-selling the work by using 'novel' too often (in particular in connection with the formulation). The role of \\beta in Theorem 1 makes me worried about the significance of the result. \n\nIn short, this is nice work but not impressive. Addressing some of the weakness would definitely improve the paper. \n\nOther remarks:\nRemark 1: w^t stay in a bounded region: This is often not the case in practice. Gradient clipping is often needed to circumvent this. The reLU issue is addressed in an ad-hoc manner. \nAssumption 3: On the first read, it felt like such a \\hat{v}_aster^t always exists. Then I realized that it is \\hat{v}_aster^t(\\epsilon). The authors should probably emphasize this dependency. \n\nMinor comments: \nThe \"Loss Functions\" subsection should be take out. It's trivial. Definitions 2 and 3 should be removed as it is safe to assume that a reader not knowing these concepts would not encounter this paper (even less being able to understand it). \nNew Algorithmic Framework\nPeriod missing at the end of (7)\nIt is weird to write H (matrix) \\cdot \\eta (scalar) \\cdot v (vector). I suggest \\eta H v\nThe assumptions in Theorem 2 don't have to be repeated. One can simply state \"under the same assumption as in Theorem 1 plus additional assumptions ...\"\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves a global convergence rate of a newly proposed algorithm finite sum problem under some assumptions. While the proposed algorithm provides some interesting ideas to solving the finite sum problem using intermediate proxy solver, the current assumptions are too strong and I'm afraid that this can make the result essentially trivial:

For example, assumption 3 assumes that 
$ H_i * v \approx \nabla_z\phi_i(h(w, x_i))$ for every i. This simply implies that 
$ \|\nabla_w\phi_i(h(w, x_i)) \|_2 $ is as large as $\|\nabla_z\phi_i(h(w, x_i))\|_2^2 $ as long as the norm of v is small, since 
$\nabla_w\phi_i(h(w, x_i)) =  \nabla_z\phi_i(h(w, x_i)) H_i $.



Hence the assumption simply assumes that "If the loss is not small, then the gradient of the objective is not small (using the convexity of $\phi$, so $|\nabla_z\phi_i(h(w, x_i))$ has to be large)" -- This would imply that gradient descent can also work (and arguably having the same convergence rate) under this assumption.  Note that "the smallest movement that can decrease the objective the most" is indeed following gradient descent direction -- So gradient descent would not move the weights more than this algorithm as well. 

Therefore, I am not sure that there is a clear benefit to using this algorithm compared to the standard (stochastic) gradient descent. In particular, I would suggest the authors at least show one example where under the current set of assumptions, gradient descent does not work as efficiently compared to the proposed algorithm -- This will make the proposed algorithm much more justified.
Decision: Reject