Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
Authors: Kaiwen Zhou
Lai Tian
Anthony Man-Cho So
James Cheng
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Convex optimization
Finding near-stationary points
Variance reduction
Performance estimation problem
Momentum

Abstract: The problem of finding near-stationary points in convex optimization has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future developments.

Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
Anonymous Author(s)
Affiliation
Address
email
Abstract
The problem of finding near-stationary points in convex optimization has not been adequately studied yet, unlike other optimality measures such as the function value. Even the deterministic case, the optimal method (OGM-G, due to Kim and Fessler [33]) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant OGM-G based on the performance estimation problem approach [19]; (2) design a new accelerated SVRG variant that can simultaneously achieve fast rates minimizing both the gradient norm and function value; (3) propose adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis the simplicity and practicality of the new schemes, which could facilitate future developments.
11
13
Introduction
14
15 Classic convex optimization usually focuses providing guarantees for minimizing function value. For this task, the optimal (up to constant factors) Nesterov's accelerated gradient method (NAG) [40, 41] has been known for decades, and there are even methods that can exactly match the lower complexity bounds [30, 17, 55, 18]. the other hand, in general non-convex optimization, near- stationarity is the typical optimality measure, and there has been a flurry of recent research devoted to this topic [25, 26, 23, 28, 21, 60]. Recently there has been growing interest on devising fast schemes for finding ntar-statinnary points in convex optimization [42, 2, 22, 7, 31, 32, 33, 27, 15, 14]. This line research is basically driven by the following facts.
16
17
18
20
22
29
Nesterov [42] studied the problem with a linear constraint: f(x*) = min (f(x) : Ax = b}. where Q is convex set and strongly convex. Assuming that Q and f are simple, we can focus the dual problem p(y") max, (ax) - minzeq (f(x) + {y. b Ax) Clearly, the dual objective <ly) smooth convex. Letting Fy be the unique solution to the inner problem, we have Vo(y)
24
25
26
Auy. Note that f(x,,) f(x") o(y) (y. Vo(y)) x(v") S llyll | Thus, in this problem, the quantity [)V serves as measure of both primal optimality f(x,)- and feasibility 116-Ax,,, which is better than just measuring the function value.
27
28
29
Matrix scaling [50] is convex problem and its goal is to find near-stationary points [4, 9].
Gradient norm readily available, unlike other optimality measures (f(x)- (==")))))=>>)))) ) and ||x - x (]), and is thus usable as stopping criterion. This fact motivates the design of several parameter-free algorithms [43, 39, 27], and their guarantees are established on the gradient norm.
31
33
Designing schemes for minimizing the gradient norm inspire non-convex optimization methods. For example, SARAH [46] was designed for convex finite-sums with gradient-norn mea- sure, but later discovered to be the near-optimal method for non-convex finite-sums [21, 47].
35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Table Finding near-stationary points [Vf(z) S of convex finite-sums.
Algorithm
Complexity
Remark
GD
[33]
O(5)
Regularized NAG*
[7]
O log 2)
OGM-G
[33]
O())
0 + d) memory, optimal in
M-OGM-G
[Section 3.1]
(())
(d) memory, optimal in
L2S
[37]
O(n + K
Loopless variant of SARAH [46]
Regularized Katyusha*
[2]
O((n + x log !)
Requires the knowledge of Ao
R-Acc-SVRG-G*
[Section 5]
O((n log + x
log
Without the knowledge of Ao
GD
[42, 54)
(
NAG NAG + GD
[32] [42]
0 [1733
Regularized NAG*
[42, 27]
O log
NAG + OGM-G
[45]
0 ((7))
+ d) memory, optimal e
NAG + M-OGM-G [Section 3.1]
((55)
(d) memory, optimal in
D
C
Katyusha L.2S
[Appendix E]
O(nlog vn
Acc-SVRG-G
[Section 4]
n2/3 O ,273
O(n !
/ for function at the same time, simple and elegant
Regularized Katyusha*
[2]
O((n + ( log )
Requires the knowledge of Ro
R-Ace-SVRG-G*
[Section
O(nnlog : + / log
Without the knowledge of R Indirect methods (using regularization).
37 Moreover, finding near-stationary points is a harder task than minimizing function value, because
38 NAG has the optimal guarantee for f(x) - f==") but is only suboptimal for minimizing // (xx) I-
39 In this work, we consider the problem min f(x) = Ei= fi(), where each f, is L-smooth and convex. We focus on finding c-stationary point of this objective, i.e., point with / f fx)]l s c. We use X* to denote the set of optimal solutions, which is assumed to be nonempty. There are two the initial point 2n, namely. the Initial (x0) - f(x)) S Ag. and the Initial bounded-Distance Condition (IDC): || x || S Ro for some E X This subtlety results in drastically different best achievable rates studied in [7, 22].
41
different assumptions
Condition (IFC):
43
45
Below we categorize existing algorithmic techniques into three classes (relating to Table 1).
46
"IDC IFC". Nesterov [42] showed that we can combine the guarantees of method minimizing function value under IDC and a method finding near-stationary points under IFC to produce faster one for minimizing gradient norm under IDC. example, NAG produces
47
48
f(*k,) f(x*) 0
LR
[40] and GD produces ff(=,.) O Lif(zo)-f(=")) [33] K₂
K
50
under IFC. Letting xo = IK, and K Ki + K2, by balancing the ratio of Ki and K2, we m. R for "NAG + GD". We point that can use this technique to combine the guarantees of Katyusha [1] and SARAH [46]; see Appendix
obtain the guarantee f=
O
51
52
(ii) Regularization. Nesterov [42] used NAG (strongly convex variant) to solve the regularized objective, and showed that achieves near-optimal complexity (optimal up to logarithmic factors). Inspired by this technique, Allen-Zhu [2] proposed recursive regularization for stochastic approximation algorithms, which also achieves near-optimal complexities [22].
54
55
56
shows that Katyusha+L2S has slightly better dependence on n than Acc-SVRG-G GG It is due to the adoption of n-dependent step size in L2S. As studied in [37], despite having better complexity, r-dependent step size boosts numerical performance only when n extremely large. If practically fast re-independent step size is used 1.2S, Katyusha+I.22 L2S and Ace-SVRG-G have the same complexity. See also Appendix A. We adopt the loopless variant of SARAH in [37], which has refined analysis for general convex objectives.
'Table

---

57
(iii) Direct methods. Due to the lack of insight, existing direct methods are mostly derived or analyzed with the help of computer-aided tools [31, 32, 54, 33]. The computer-aided -ided approach was pioneered by Drori and Teboulle [19], who introduced the performance estimation problem (PEP). The only known optimal method OGM-G [33] was designed based on the PEP approach.
58
59
60
61
62
Observe that since - points must be of the same order for minimizing function value [44]. Thus, under IDC, the lower bound (1 + /²² due to [58]. Under IFC, we can establish an Ω + x²)) lower bound using the techniques in [7, 58]. The main contributions of this work are three algorithmic schemes that improve the practicalities of existing methods as summarized below (highlighted in Table 1).
- f(x)) & [z 2111, the lower bound for finding near-stationary
63
64
86
67
(Section 3) We propose a memory-saving variant of OGM-G for the deterministic case 1). which does not require pre-computed and stored parameter sequence. The derivation of the new variant is inspired by the numerical solution PEP problem.
88
89
(Section 4) We propose new accelerated SVRG [29, 59] variant that can simultaneously achieve fast convergence rates for minimizing both the gradient norm and function value, that is, (n log + x2//3
71
2773 complexity for gradient norm and On 1 + ( complexity for function value. Note that other stochastic approaches in Table do not have this property.
73
74
(Section 5) We propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of Ro or An and achieves near-optimal complexity under IDC or IFC.
78 We put extra efforts to make the proposed schemes as simple and elegant as possible. We believe that the simplicity makes the extensions of the new schemes easier.
77
2 Preliminaries
79 Throughout this paper, we use (::)) and ||-|| denote the inner product and the Euclidean norm, respectively. We let [n]] denote the set {1,2..... n.). E denote the total expectation and E,, denote 81 the expectation with respect to random sample is.- We say that function IR + R is L-mooohh 82 it has L-Lipschitz continuous gradients, i.e..
Vx, y E Rd, [VV(()) - V S L. ||x all
A continuously differentiable f is called p-strongly conver if
Vx, E Rdd f(x) - f(y) - (Vf(w). x v)
11 || v11
2
84 Other equivalent definitions of these two assumptions can be found the textbook [44]. The following is an important consequence of function f being L-smooth and convex:
Yz,y Rd f(x) f()) (Vi(v) v) 2L [1 Vf
(1)
86 We call (1) the interpolation condition at (x, v) following [56]. f is both L-smooth and p-strongly
87 convex, we can define "shifted" function h(()) f(x) - f(x*) $ || - x= 1|² following [63]. can be easily verified that h is (L 4))-mmothh and convex, and thus from (1),
Va,y y E IRd h(x) - h(y) (Vh(y), x y) 2( /Vh(s) - vh(y))
(2)
which is equivalent to the strongly convex interpolation condition discovered in [56].
90 Oracle complexity (or simply complexity) refers the required number of stochastic gradient f.
91 computations to find an e-accurate solution.
3 OGM-G: "Momentum" Reformulation and a Memory-Saving Variant
33 In this section, we focus on the IFC case, i.e., f(x0) - -xxx) S Ag- We use to denote the total iteration number to prevent confusion (in other sections, use K). Proofs in this section are given in
3

---

Algorithm OGM-G: "Momentum" reformulation
Input: initial guess 20 IR: total iteration number N. Initialize: vector to = 0, scalars ON and 0f 02 = 02211 for k = -..... -1
for k ...... N do
2: Uk+1 Uk + T0,01 V (xx)).
3: Fk+1 Ikk f (20) + UUK+1
4: end for
Output: 2N-
95
Appendix B. Recall that OGM-G has the following updates [33], Let yo = To. For = O,..., 1
Ve+1 = Zk 7 v)(w))
(3)
(0x 1)(20++1 -
20x+1 +1 -
#k+1 = Mk++1 +
(yk+1 - 4k) +
20, -1 (y1++1 - xkk);
0% (20k 1)
where } is recursively defined: ON 1 and [0 02 0b
k: == 1...N N-...111
08 Go
20 otherwise.
98
OGM-G was discovered from the numerical solution to an SDP problem and its analysis is to show that the step coefficients in (3) specify a feasible solution the SDP problem. While this analysis is natural for the PEP approach, it is hard to understand how each coefficient affects the rate, especially if wants generalize the scheme. Here provide simple algebraic analysis for OGM-G.
99
100
101
102
We start with reformulation of OGM-G in Algorithm which aims to simplify the proof. We adopt& consistent {0a]: ON and 0% 02 6
....N N - 1, which only costs constant factor.* 4 Interestingly, the reformulated scheme resembles the heavy-ball momentum method [49]. However, it can be shown that Algorithm 1 is not covered by the heavy-ball momentum scheme. Defining B N+1 fx ON O. we provide the one-iteration analysis in the following proposition:
104
105
106
107
Proposition 3.1. In Algorithm 1, the following holds at any iteration & E {O...., N 13
A + BE+1 + Cx+1 + Ex+1 S. A + BR + C + Eg Os+1 (V/(I++1),
N
O: (V(I))) Vf(x))),
(4)
Σ
LA
k++1
108
with Ag
84
3. ([(EN)]((x*) + [V((x))
B - oe ((((x))((<*)) C - 1 [++)(=)) 2L07
109
ER
0111 (V ff(x),
110
Remark 3.1.1. A recent work [15] also conducted an algebraic analysis of OGM-G under potential function framework. Their potential function decrease can be directly obtained from Proposition 3. by summiing up (4). By contrast, our "momentun" vector { naturally merges into the analysis, which significantly simplifies the analysis. Moreover, provides a better interpretation on how OGM-G utilizes the past gradients to achieve acceleration.
111
112
113
115
From (4), we see that only the last two terms do not telescope. Note that the "momentum" vector is weighted sum of the past gradients, i.c., Uk+1 = Σi= L8 (x,). we sum the terms up from
116
117
O....,N N 1, it can be verified that they exactly sum up D. The presence of these special terms prevents OGM-G to have a usual potential function (c.g., those in [6]). Then, by telescoping
118
119
the remaining terms, we obtain the final convergence guarantee.
Theorem 3.1. The output of Algorithm satisfies [f(xx)]]
8LAp (N+2)
120
121 We observe two drawbacks of OGM-G (same as the algorithm description in [15]): (1) it requires storing a pre-computed parameter sequence, which costs O(2) floats; (2) except for the last iterate,
It can be verified that this scheme is equivalent to the original one (3) through U4 (28, 1387 (ye xt).
TTee original guarantee of OGM-G G can be recovered we set 0g -o 207.

---

Algorithm 2 M-OGM-G: Memory-saving OGM-G
Input: initial guess 20 R. total iteration number N. Initialize: vector to = 0.
for k == ....., N do
2: Uk+1 Uk + TQN k+1) M Vf(zk).
12
3: Fk+1 I ffxx) (N-
uk+1-
4: end for
Output: 2N arg min (
[fx)]]
all other iterates are not known to have guarantees. We resolve these issues by proposing another parameterization of Algorithm in the next subsection.
124
125
3.1
Memory-Saving OGM-G
126
A straightforward idea to resolve the aforementioned issues is to generalize Algorithm 1. However, we find rather difficult since the parameters in the analysis rather strict (despite that the proof is already simple). We choose to rely on computer-aided techniques [19]. The derivation of this variant
127
128
129
(Algorithm 2) is based on the following numerical experiment.
130
Numerical experiment. OGM-G was discovered when considering the relaxed PEP problem [33]:
max (soo)..... JER" ((x)) (=")) jeR
interpolation condition (1) at (J2,
h: = O,... N - 1,
(P)
subject to interpolation condition (1) at (IN,
interpolation condition (1) at (#N, Rk),
h: = 0, N - 1,
(w0) [(x)) S Do,
131
where the sequence } is defined as Tk+1 = I2 E V . for
N some step coefficients E IR (NN+)/2 Given N, the step coefficients of OGM-G correspond to a numerical solution to the problem: arg min, (Lagrangian dual of (P)), which is denoted as (HD).
132
133
134
Conceptually, solving problem (HD) would give us the fastest possible step coefficients under the constraints." We expect there be some constant-time slower schemes, which are neglected when
135
136
solving (HD). To identify such schemes, we relax a set of interpolation conditions in problem (P):
1
f(xx) (xxx (VI(z)), xx) 2 2T. [V/(xx)
for k ......N N
and some p O. After this relaxation, solving (HD) will longer give the step coefficients OGM-G. By trying different p and checking the dependence on N, we discover Algorithm 2 when p I Similar our analysis of OGM-G, we provide simple algebraic analysis for the new variant in the following theorem.
138
139
140
141
Theorem 3.2. Define 6x+1
N.....N. N. In Algorithm 2, it holds that (N N--+1XNN K+2NNN BOCINNN4550 K43J, h = O,...,
0R41
12LD0
(5)
2
(N + 2) +3)
k=U
Remark 3.2.1. Algorithm 2 converges optimally on the last iterate (note that 8 2) and the minimum gradient since
144
N
8x41
SLAp (N 2) + +3 -
min kE kE(......))
[[
[f(xz))
1KI
2
-==
K=
Clearly, the parameters of this variant can be computed on the fly and from (5), each iterate has guarantee (although the guarantee degenerates quickly as l + since 1/ = 2( - k)) Moreover, extend the benefits into the IDC case using the ideas in [42] as summarized below. 146
'oweeerr since problem (HD) is non-convex, only obtain approximate solutions.
5

---

Algorithm 3 Acc-SVRG-G: Accelerated SVRG for Gradient minimization
Input: parameters {Tk): {p&], initial guess zo E IRd, total iteration number K.
Initialize: vectors 20 = 20 = zo and scalars ork Loe. Vk and F = -- --11
Tk
1: for = ....... K do
2: yk Tk2k (1 Th) (Tx [āx))
3: #k+1 arg min (r) (ax/2) | z
4: 1r _ f., (Ms) - fia (Tx) + V f((x)), where in is sampled uniformly in [n].
y/k
with probability Pk:
5: Tk+1
with probability 1 - pk-
6: end for
Output (for gradient): Tout is sampled from (Prob( = -x) = 7 k | (0.
--2 (O...... -I1]]
K
Output (for function value): Zk-
148
Corollary 3.2.1 (IDC case). If we first run N/2 iterations of NAG and then continue with N/2
iterations of Algorithm 2, we obtain an output satisfying [VVf(x)) = 0 (
149
4
Accelerated SVRG: Fast Rates for Both Gradient Norm and Objective
150
151
In this section, we focus on the IDC case, i.e. 1 - --'1-" S Rg for some x" E X From the development in the previous section, it is natural to ask whether can the PEP approach to motivate new stochastic schemes. However, due to the exponential growth of the number of possible states (No, .),, we cannot directly adopt this approach. A feasible alternative is first fix an algorithmic framework and a family of potential functions, and then use the potential-based PEP
153
154
155
156
approach in [54]. However, this approach is much more restrictive. For example, it cannot identify special constructions like (4) in OGM-G. Fortunately, as we will see, we can get some inspiration from the recent development of deterministic methods. Proofs in this section are given in Appendix C.
157
158
159
Our proposed scheme is given in Algorithm 3. We adopt the elegant loopless design of SVRG in [34]. Note that the full gradient V f(x) is computed and stored only when ix+1 yk Step 5. We summarize our main technical novelty as follows.
161
162
Main algorithmic novelty. The design of stochastic accelerated methods largely inspired by NAG. To make it clear, by setting n
that Katyusha [1], MiG [61], SSNM [62], Varag [36), VRADA [52], ANITA [38], the acceleration framework in [16] and AC-SA [35, 24) all reduce to one of the following variants of NAG. We say that these methods under the NAG framework.
184
Ty = Th + (1 -T)
Tk = =k + (1 - Th)uk
Zk+1 zµ 09 V f(xx),
Zk+1 2k 04 V f(R)),
M T + Tk )yk-
yk+1 Is 7I6 (x(x))
Auslender and Teboulle [5]
Linear Coupling [64]
See [57, 12] for other variants of NAG. When n 1, Algorithm reduces to the following scheme: 186
yk = T4 + (1 Th) (yk-1 ((nn)))) #R+ = 2/ f((.).
Optimized Gradient Method (OGM) [19, 30]
187 Algorithm reduces to the scheme of OGM when n = (this point is clearer in the formulation of ITEM in [55]). OGM has constant-time faster worst-case rate than NAG, which exactly matches the lower complexity bound established in [17]. In the following proposition, we show that the OGM framework helps conduct tight one-iteration analysis, which gives room for achieving goal.
189

---

171 Proposition 4.1. In Algorithm 3. the following holds at any iteration k 2 0 and Vx* E x
1
Th (f(x++1) f(x*)((==))))) 7
L
|| -x112)
(1 (1-Tx)² E [V
PR
2LT
(6)
ThPp) Th) [f(x)) [(x)) + 2/ [112 1aa=xx111 x0--=11]] 11])
TEPs
172
The terms inside the parentheses form the commonly used potential function of SVRG variants. The 173 additional E|ll V ((xx)]] II' term is created by adopting the OGM framework. In other words, we use the following potential function for Algorithm (ak, bb: Ck O):
174
T = 0g El((a - f(x))] bylE ||
x*]]]
Σ 1=
& [V)())))
We first provide simple parameter choice, which leads to simple and clean analysis.
176
Theorem 4.1 (Single-stage parameter choice). In Algorithm 3, if we choose pk 2. Th k/n+6' then the following holds at the outputs:
3
177
n n (f((o)) - f(x))) +
E | [V
K33
n² ()(()))) ) - ((x*)) + n.nR
E [[((K)] - f(x*)()=))))))))))))) -(x))=0 =0
K2
178 In other words, to guarantee that E [ S Eg and IE [[(Tx))] -f(k)))((xx)) ) S ef, the oracle com-
plexities are Of nu(Lff(zo)- f(x 1)) (mLRo)
2/3 and O (mV (nv) ((=0))((w*)) + vnLRg) respectively.
179
69
From (7), we see that Algorithm 3 achieves fast O 0(gtz) and O (())) rates for minimizing the gradient norm and function value at the same time. However, despite being a simple choice, the oracle complexities are not better than the deterministic methods in Table 1. Below we provide two-stage parameter choice, which inspired by the idea of including a "warm-up phase" [3, 36, 52, 38].
181
183
This theorem corresponds to the reported result in Table 1.
185
Theorem 4.2 (Two-stage parameter choice). In Algorithm 3. let Ph: = max R48 } Th = (k+3))
3
The oracle complexities needed to guarantee E [|| [X S cg and IE [f f(x)) S Ef
o (1 min log
LRo log
(n
2/3
LRR
VnI.Ro
(nmin
2/3 and n mimin log
log n
cg
Eg
es
Vey
187
respectively.
If e is large is very large, the recently proposed ANITA [38] achieves an O(n) complexity, which matches the lower complexity bound (())) in this case [58]. Since ANITA uses the NAG framework, show that similar results can be derived under the OGM framework in the following theorem:
189
191
Theorem 4.3 (Low accuracy parameter choice). In Algorithm 3, let iteration N be the first time
192
Step& 5 updates Tk+1 = yk. If we choose pk 1. Tk iteration N, then the following holds at #N+1
Vn+I
1 and terminate Algorithm 3 at
193
8T,2 and E [[ f(x')=
LR
E [[ 5(vn+1+1)
<
Vn 1 +
81 Rg
In particular, if the required accuracies are low (or n is very large), i.e., eg >
and
5[vR+I+1)
I.n Vn+141 then Algorithm 3 only has an ((n) oracle complexity.
185 Ex 2
196 In the low accuracy region (specified above), the choice in Theorem 4.3 removes the Ollog !) factor in the complexity of Theorem 4.2. We include some numerical justifications of Algorithm 3 in
198 Appendix A. We believe that the potential-based PEP approach in [54] can help us identify better parameter choices of Algorithm which we leave for future work.
7

---

Algorithm 4 R-Acc-SVRG-G
Input: accuracy 6 0, parameters ón I,, 3, 1, initial guess zng IR:
1: for 0,, 2, do
2: Define f (z) = Ei 1 (z), where (x) = fi(Ø) + (6. || zo zoll
3: Initialize vectors 2o = I0 - 20 and set Tas T2x 01, P: CIDC; CIPC according Proposition 5.1.
4: for k = 0, 2,.,2.... do
5:
y/ 2 + Tx) 3x + Tz (ōx(*x 2k) v (ōx)).
6:
1 1 = arg min
g x + (a/2) ||0 - 11 + (f./2) || ykl 1=
7:
1 V v (uk)
V S/ (fx) + V for (āx), where is is sampled uniformly in [n]]
0x+1 yk with probability p:
8:
.t with probability 1 1-p-
9:
if V J [+x) S then output .x. and terminate the algorithm.
10:
if under IDC and (1 + 4)* 2 vCiDe/6, then break the inner loop.
if under IFC and (1 + 6e )* /Crrc/5,, then break the inner loop. end for
11:
12:
13:
01+1 6./B.
14:
end for
5 Near-Optimal Accelerated SVRG with Adaptive Regularization
201
Currently, there is no known stochastic method that directly achieves the optimal rate in e. To get near- optimal rates, the existing strategy is to use carefully designed regularization technique [42, 2] with a method that solves strongly convex problems; see, c.g., [42, 2, 22, 11]. However, the regularization parameter requires the knowledge of Ro or Ao. which significantly limits its practicality.
202
203
204
Inspired by the recently proposed adaptive regularization technique [27], develop near-optimal accelerated SVRG variant (Algorithm 4) that does not require the knowledge of Rg or An. Note that this technique was originally proposed for NAG under the IDC assumption. Our development extends this technique to the stochastic setting, which brings an O(v rate improvement. Moreover, we consider both IFC and IDC cases. Proofs in this section are provided in Appendix D.
206
207
208
209
210
Detailed design. Algorithm 4 has a gguess-and-cheed framework. In the outer loop, we first define the regularized objective f using the current estimate of regularization parameter &, and then we initialize an accelerated SVRG method (the inner loop) to solve the 55-strongly convex fä. If the inner loop breaks at Step 10 or 11, indicating the poor quality of the current estimate 5,, & will be divided by a fixed B. Thus, conceptually, we can adopt any method that solves strongly convex finite-sums at the optimal rate the inner loop. However, since the constructions of Step 10 or 11 require some agorithmm-dependen constants, we have to fix one method as the inner loop.
212
214
215
216
The inner loop we adopted is loopless variant of BS-SVRG [63]. This is because (i) BS-SVRG is the fastest known accelerated SVRG variant (for ill-conditioned problems) and (ii) it has a simple scheme, especially after using the loopless construction [34]. However, its original guarantee is built upon { Clearly, we cannot implement the stopping criterion (Step 9) on fz+))) Interestingly. discover that its sequence ) works perfectly in regularization framework, even if we can
218
220
neither establish convergence on f(ăx) - f(x") nor on || - x= 2 Moreover, we find that the loopless construction significantly simplifies the parameter constraints of BS-SVRG, which originally involves (n)) th-order inequality. We provide the detailed parameter choice as follows:
222
223
224
225
Proposition 5.1 (Parameter choice). In Algorithm 4, we set Tz = a+L+5; -,, Tz 61
a+o
a(1-Te) and
b,L
1 p- n' We a the (unique) positive root of the cubic equation 11 La"p
pla+
(1 61
) =1
a+L+6.
227
and specify CIDC = 1,2 + [=(1-p(a+to] OIFC -T. +
2Lo²p pP(a--)))
Under these choices, we
228 have J. = 0(n / (L166, 1)), CDDC
+ 6,) 6,))). and CIFC = (
NNoe that we maintain the full gradient V (āx) and V (f(x)) = (Zx) - (ā² - 2n). II is due to the special potential function of BS-SVRG (see (27)), which does contain these two terms.
8

---

229
Under the choices of and the above is the optimal choice in our analysis. Then, we can characterize the progress of the inner loop the following proposition:
230
Proposition 5.2 (The inner loop of Algorithm 4). Using the parameters specified in Proposition 5.1,
231
232
after running the inner loop (Step 4-12) of Algorithm for iterations, we can conclude that
233
(i) under IDC, i.e. ||00- x=1 - Ro for some x² E X,,
6g 1
-k
[[
6 +
v VIDC
Ro:
α
(i) under IFC, i.e. f(zo) - f(x*) Do.
234
86 =
E [+)
(256
v Vire
VAo.
235
The above results motivate the design of Step 10 and 11. For example, in the IDC case, when the inner loop breaks at Step 10, using (i) above, we obtain E [IIV f (#x)]ll < 26, Ro. Then, by discussing the relative size of ò, and a certain constant, we can estimate the complexity of Algorithm 4. The same methodology is used for the IFC case.
236
237
239
Theorem 5.1 (IDC case). Denote dexx = <q for some q E (0, 1) and let the outer iteration 2no
240
be the first time 5g S BiDe. The following assertions hold:
241
(i) At outer iteration l, Algorithm terminates with probability at least 9.
(ii) The total expected oracle complexity of the e + 1 outer loops is
LRRo nlog
n..Ro
LRo
log
Eq
eq
eq
222
243
Theorem 5.2 (IFC case). Denote Pic
8Ao for some E (0, 1) and let the outer iteration = E be
244 the first time dg S jipc. The following assertions hold:
(i) At outer iteration f, Algorithm 4 terminates with probability at least (ii) The total expected oracle complexity of the e+ outer loops is
246
((1
VLAo
vnLAo
VLA
nnlo
log
eq
eq
247
Compared with regularized Katyusha in Table 1, the adaptive regularization approach drops the need estimate Ro or Ag the cost of mere log 1 factor in the non-dominant term (if small).
248
6
Discussion
249
250
In this work, we proposed several simple and practical schemes that complement existing works (Table 1). Admittedly, the new schemes currently only limited to the unconstrained Euclidean setting, because our techniques heavily rely on the interpolation conditions (1) and (2). On the other hand, methods such as OGM [30], TM [51] and ITEM [55, 10], which also rely on these conditions, are still not known to have their proximal variants. We list a few future directions as follows.
252
254
255
(1) It is not clear how to naturally connect the parameters of M-OGM-G (Algorithm 2) to OGM-G (Algorithm 1). The parameters of both algorithms seem to be quite restrictive and hardly generalizable
256
due to the special construction in (4). Does there exist an optimal method for minimizing the gradient norm that has proper potential function (at each iteration)?
258
259
( Is this new "momentum" in OGM-G beneficial for training neural nets? Other classic momentum
280
schemes such as NAG [40] or heavy-ball momentum method [49] are extremely effective for this lask [53], and they were also originally proposed for convex objectives.
281
(3) Can directly accelerate SARAH (L2S)? By extending OGM-G? It seems that existing stochastic acceleration techniques fail to accelerate SARAH (or result in poor dependence on n as in [16]).
263
We assume that c small such that max (diie dicc I do for simplicity. this case, > 0. 'If Algorithm 4 does not terminate at outer iteration é. it terminates at the next outer iteration with probability least 1 9/B. That is, it terminates with higher and higher probability. The same goes for the IFC case.

---

References
284
265
[1] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of
266
Machine Learning Research, 18(1):8194 8244, 2017. 2, 6, 26
[2] Z. Allen-Zhu. How to make the gradients small stochastically: Even faster convex and noncon-
268
vex sgd. In Advances in Neural Information Processing Systems, pages 1157-1167, 2018. 1, 2,
8
[3] Z. Allen-Zhu and Y. Yuan. Improved SVRG for Non-Strongly-Convex Sum-of-Non-Convex Objectives. In Proceedings The 33rd International Conference on Machine Learning, pages 1080-1089) 2016.7
271
272
[4] Z. Allen-Zhu, Y. Li, R. M. de Oliveira, and A. Wigderson. Much Faster Algorithms for Matrix Scaling. In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, pages 890-901, 2017. 1
274
[5] A. Auslender and M. Teboulle. Interior gradient and proximal methods for convex and conic optimization. SIAM Journal on Optimization, 16(3):697-725, 2006. 6
277
278
[6] N. Bansal and A. Gupta. Potential-Function Proofs for Gradient Methods. Theory of Computing.
279
I 153) 2019. 4
280
[7] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
281
ii: first-order methods. Mathematical Programming. 185(1-2), 2021. 1, 3
282
[8] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions
283
on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http:
284
//ww.ccsie.eec...... cswe. ntu. atu. tw ht//"cllinnlibsvm 13, 14
285
9
M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu. Matrix Scaling and Balancing via Box Constrained Newton's 's Method and Interior Point Methods. In IEEE 58th Annual Symposium on Foundations of Computer Science, pages 902-913. IEEE, 2017. 1
286
287
288
[10] A. d' Aspremon,, D. Scieur, and A. Taylor. Acceleration methods.
arXiv preprint
289
ar X 09545, 2021. 9
290
[11] D. Davis and D. Drusvyatskiy, Complexity of finding near-stationary points of convex functions stochastically. arXiv preprint arXiv: 1802.08800. 2018. 8
[12] A. Defazio. On the Curved Geometry of Accelerated Optimization. In Advances in Neural
293
Information Processing Systems, volume 32. pages 1764-1773, 2019, 6
294
[13] A. Defazio, F. R. Bach, and Lacoste-Julien. SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. In Advances in Neural Information Processing Systems, pages 1646-1654, 2014. 14
296
297
[14] Diakonikolas and C. Guzmán. Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems. arXiv preprint 2rXiv:2101.
298
299
2021.
300
[15] Diakonikolas and P. Wang. Potential Function- based Framework for Making the Gradients Small in Convex and Min-Max Optimization. arXiv preprint arXiv:2101.12/01, 2021. 1, 4
301
302
[16] D. Driggs, M. J. Ehrhardt, and C.-B. Schönlieb. Accelerating variance-reduced stochastic
303
gradient methods. Mathematical Programming. 2020. doi: 10.1007/110077-000006666 6,
304
[17] Y. Drori. The exact information- based complexity of smooth convex minimization. Journal of
305
Complexity, 39:1-16, 2017. 1,6 6
306
[18] Y. Drori and A. Taylor. On the oracle complexity of smooth strongly convex minimization. arXiv preprint arXiv:2101.0977
307
2021. I
[19] Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization:
309
a novel approach. Mathematical Programming, (45(1-2):551493) 2014. 1, 5, 6
310
[20] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http:://arhhhii
uci edu/ml. 13, 14
312
[21] C. Fang, C. Li, Z. Lin, and T. Zhang. SPIDER: Near-Optimal Non-Convex Optimization via
313
Stochastic Path Integratt Differential Estimator. In Advances in Neural Information Processing Systems, pages 687-697, 2018.
10

---

315
[22] D. Foster. A. Sekhari, O. Shamir. N. Srebro, K. Sridharan, and B. Woodworth. The Complexity of Making the Gradient Small in Stochastic Convex Optimization. In Proceedings of the Thirty- Second Conference on Learning Theory, pages 1319-1345, 2019. 2,
316
317
318
[23] R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition. In Proceedings of The 28th Conference on Learning Theory, pages 797-842, 2015.
318
320
321
[24] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on
322
323
Optimization, 22(4))1 1492, 2012. 6
324
[25] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic
programming. SIAM Journal Optimization, 23(4)) 2013.
326
[26] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic
327
programming. Mathematical Programming, 156(1-2):59-99, 2016. 1
328
[27] M. Ito and M. Fukuda. Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach. Journal of Optimization Theory and Applications, 188(3):770-804 2021. 1,2.8
329
330
(28) C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. Jordan. How to Escape Saddle Points Efficiently. In Proceedings of the 34th International Conference on Machine Learning, pages 1724-1732, 2017.
332
333
[29] R. Johnson and T. Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. In Advances in Neural Information Processing Systems, pages 315-323, 2013. 3, 14
335
396
30 D. Kim and J. A. Fessler. Optimized first-order methods for smooth convex minimization.
Mathematical Programming, 159(1):81-107, 2016. 1, 6,
[3]] D. Kim and J. A. Fessler. Another Look at the Fast Iterative Shrinkage/Threshollinng Algorithm (FISTA). SIAM Journal on Optimization, 28(1):223-253 -200, 2018. 3,3
338
339
[32]
D. Kim and J. A. Fessler. Generalizing the optimized gradient method for smooth convex minimization. SIAM Journal on Optimization, 19(2):1920-1955) 2018. 2,
341
342
[33] D. Kim and A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1):
344
192-219, 2021. 2,2,3,4,
345
[34] D. Kovalev, S. Horváth, and P. Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451-467. PMLR, 2020. 6, 8
347
348
[35] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming. (33(12))365-3977
349
2012. 6
350
[36] G. Lan, Z. Li, and Y. Zhou. A unified variance-reduced accelerated gradient method for
351
convex optimization. In Advances in Neural Information Processing Systems, volume 32, pages 10462-10472, 2019, 6,7
352
353
[37] B. Li, M. Ma, and G. B. Giannakis. On the Convergence of SARAH and Beyond. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages
355
223-233, 2020. 2, 14, 24
356
[38] Z. Li. ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method, arXiv preprint arXiv:2103. 1333, 2021. 6,7
358
[39] Q. Lin and L. Xiao. An Adaptive Accelerated Proximal Gradient Method and its Homotopy Continuation for Sparse Optimization. In Proceedings of the 31th International Conference on Machine Learning, pages 73 81, 2014. 1
359
360
361
[40] Y. Nesterov. A method for solving the convex programming problem with convergence rate ((1/22). In Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983. 1,
382
[41] Y. Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003. 1
364
365
[42] Y. Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, (88):10-11. 2012. 2, 5, 8, 22, 27

---

387
[43] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program-
388
ming, 140(1):125-161, 2013. 1
[44] Y. Nesterov. Lectures on convex optimization. volume 137. Springer, 2018. 3, 18
370
[45] Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky. Primal-dual accelerated gradient
371
methods with small-dimensional relaxation oracle. Optimization Methods and Software, pages
372
1-38, 2020. 2
373
[46] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A Novel Method for Ma- chine Learning Problems Using Stochastic Recursive Gradient. In Proceedings of the 34th International Conference on Machine Learning, pages 2613-2621, 2017. 1,2
375
376
[47] N. H. Pham, L. M. Nguyen, D. T. Phan, and Q. Tran-Dinh. ProXSARAH: An efficient algorith- mic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 2 10):1-48, 2020. 1
377
378
379
[48] J. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. 1998. 14
380
[49]
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964. 4, 9
382
383
[50] U. G. Rothblum and H. Schneider. Scalings of matrices which have prespecified row sums and
384
column sums via optimization. Linear Algebra and its Applications, 1 114:737-764, 1989, I
385
[51] B. V. Scoy, R. A. Freeman, and K. M. Lynch. The Fastest Known Globally Convergent First- Order Method for Minimizing Strongly Convex Functions. IEEE Control Systems Letters, 2(1):
387
49-54, 2017. 9
388
[52] C. Song, Y. Jiang, and Y. Ma. Variance Reduction via Accelerated Dual Averaging for Finite- Sum Optimization. In Advances in Neural Information Processing Systems, volume 33, pages 833-844, 2020. 6,7
389
390
[53] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and
382
momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, pages 1139- 2013. 9
383
394
[54] A. Taylor and F. Bach. Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. In Conference on Learning Theory, pages 2934 2992, 2019. 2,
396
3, 6,
397
[55] A. Taylor and Y. Drori. An optimal gradient method for smooth strongly convex minimization.
398
arXiv preprint arXiv:2 2021. 1, 1,
399
[56] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact
worst-case performance of first-order methods. Mathematical Programming, 161((-2):307-345 2017.
401
402
[57] P. Tseng. On accelerated proximal gradient methods for convex-coneave optimization. https: 2008. Accessed May 1, 2020. 6
403
/ //www. www.miite.. edu/ http:/ddmiittt tetmmiitri//P/Peee httprr///tteegepppee/////e/////e httppsppppsppppeee
404
[58] B. F. Woodworth and N. Srebro. Tight Complexity Bounds for Optimizing Composite Ob-
405
jectives. In Advances in Neural Information Processing Systems, pages 3639-3647, 2016. 3,
406
[59] I. Xiao and T. Zhang. A Proximal Stochastic Gradient Method with Progressive Variance Reduction. SIAM Journal on Optimization, 24(4):2057-2075, 2014. 3, 14
408
409
[60] D. Zhou, Xu, and Q. Gu. Stochastic Nested Variance Reduction for Nonconvex Optimization.
410
Journal of Machine Learning Research, 21:103:1-103:63, 2020.
411
[61] K. Zhou, F. Shang, and J. Cheng. A Simple Stochastic Variance Reduced Algorithm with Fast
Convergence Rates. In Proceedings of the 35th International Conference on Machine Learning, pages 5980-5989, 2018 6
413
[62] K. Zhou,, Q. Ding, F. Shang, J. Cheng, D. Li, and Z.-Q. Luo. Direct Acceleration of SAGA using Sampled Negative Momentum. In Proceedings of the Twenty Second International Conference on Artificial Intelligence and Statisties, pages 1602-1610, 2019. 6
415
416
417
[63] K. Zhou, A. M.-CC So, and J. Cheng. Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates. In Advances in Neural Information Processing Systems, pages 15405-15416, 2020. 3, 8, 22
418
12

---

420
[64] Z. A. Zhu and L. Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. In 8th Innovations in Theoretical Computer Science Conference, volume 67 of LIPlcs, pages 3:1-3:22, 2017. 6
421
Checklist
423
1. For all authors...
425
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
426
contributions and scope? [Yes]
427
(b) Did you describe the limitations of your work? [Yes] See Section
428
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We are
429
not aware of clear negative societal impacts since we focus on developing generic al algorithms for convex optimization.
430
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
432
438
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the introduction.
435
436
(b) Did you include complete proofs of all theoretical results? [Yes]
437
3. If you ran experiments...
438
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
439
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.
441
442
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure
443
444
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix A.
448
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
447
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix A.
448
(b) Did you mention the license of the assets? [Yes] LIBSVM [8] is under the BSD license.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent
obtained from people whose data you're using/curating? [Yes] Details can be found the online dataset repositories [8, 20]. (c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] Details can be found in the online dataset repositories [8. 20].
451
452
453
454
455
5. If you used crowdsourcing or conducted research with human subjects...
456
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals. if applicable? [N/A]
459
480
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
461
13


Reviews:
[{"review_id": "uj0rn9P1d6J", "reviewer": "Reviewer_hnRP", "summary": "The paper introduces three new algorithms for making gradient small in (finite-sum) the convex setting: (1) the first algorithm comes with a new parameter setting for OGM-G, matching the lower bound in the deterministic setting. (2) the second algorithm combines loopless-SVRG with OGM framework (3) the third algorithm is an accelerated SVRG with adaptive regularization, matching the lower bound up to logarithmic terms. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Originality: I believe the ideas and algorithms are original. \n\nClarity: The paper is well organized and easy to read. \n\nSignificance: Finding near-stationary point in convex setting is a critical task and has been explored by many previous work.\n\nComments\n1. My largest concern is the improvement over previous work is incremental. The analysis of OGM-G under a potential function has appears in Diakonikolas and Wang, 2021, although the potential function is not exactly the same. The second algorithm is not optimal in either $n$ or $\\epsilon$ in minimizing the gradient norm. The third algorithm does not improve over regularized Katyusha in the complexity. Although it does not require the knowledge of constant such as $R_0$ it still requires to know $L$.\n\n2.  I think one of the drawbacks of algorithm 2 may be that it still needs to prefix the total iteration $N$. \n\n3. Although the second algorithm can be used to both finding small function value and small gradient norm, it outputs different points based on different criterion (last iterate when using optimal gap and a random iterate when using gradient norm). Is it possible to output a point with both small function value and gradient norm?\n\n4. The paper only provides the experiment for algorithm 3 and the comparisons with the state-of-the-art are missing. Since the complexities of algorithms does not improve over the previous algorithms, it benefits to do experiments to compare the performance. \n\nMinor comments \n\n5. In Remark 3.2.1, the last iterates converge follows directly from Theorem 3.2 with $\\delta_{N+1} = 2$, which directly implies the minimum gradient norm is small.\n\n6. It would be interesting to explore algorithm without regularization to achieve the lower bound with IDC setting. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "a4K6Pz7csQD", "reviewer": "Reviewer_3GpM", "summary": "This paper proposes several optimization algorithms: 1. a memory-saving variant of OGM-G (by the way, could the authors provide the full name of OGM-G?); 2, a new accelerated SVRG (full name?); 3, Near-Optimal Accelerated SVRG with Adaptive Regularization. Analysis of convergence rate is provided.", "questions": "", "limitations": "", "rating": 9, "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": "For the vanilla OGM-G, a reformulation is provided, and the convergence of the norm of gradient with the speed of O(1/N) is derived.\n\nFor the Memory-Saving OGM-G, the convergence rate O(1/N) is obtained for the minimum norm of gradient across the iterations 1, ..., N.\n\nFor accelerated SVRG, in terms of the norm of gradient, convergence rate O(1/N^1.5) is derived; in terms of function value, the convergence rate of O(1/N) is derived. (is K in this section the count N in previous sections? Would it be better to unify the notations?)\n\nFor Near-Optimal Accelerated SVRG with Adaptive Regularization, analysis is done around two initial value conditions, the first is Initial bounded-Function Condition (IFC), i.e., the function value at the initial guess is not too far away from the global minimum; the second condition is Initial bounded-Distance Condition (IDC), i.e, the initial guess is not too far away from one of the global optimizers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: not seen\n\nSocietal Impact: solid improvement of the optimization algorithms discussed, and therefore a better service to different application scenarios.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "LicNT9OKJMB", "reviewer": "Reviewer_ewr9", "summary": "This paper studies efficient methods for finding near-stationary points ($||\\nabla f(x)|| \\le \\epsilon$) of a convex (finite-sum) function. The authors nicely introduce main reasons for the need of such research, and their three main contributions are as follows.\n\nFirst, this paper provides variants of OGM-G that is an optimal method for finding a near-stationary point for a smooth convex function under the initial bounded-function condition (IFC). In specific, Proposition 3.1 complements the complexity of OGM-G (with and without a change of coefficient at the last iteration). In addition, a memory-saving variant of OGM-G was studied, which does not require computing coefficients in advance. \n\nSecond, based on OGM and the loopless SVRG, the authors propose Acc-SVRG-G. With the two-stage parameter choice under the initial bounded-distance condition (IDC), it has fast rates for minimizing both the gradient norm and the function value for the first time. \n\nThird, with adaptive regularization, the Acc-SVRG-G achieves the best existing rates (by the regularized Katyusha) up to a logarithmic factor, in terms of minimizing the gradient norm, under both IDC and IFC. The proposed R-Acc-SVRG-G has advantage over the regularized Katyusha, since it does not require the knowledge of $R_0$ and $\\Delta_0$. ", "questions": "", "limitations": "", "rating": 7, "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": "As stated in the beginning of the abstract, finding near-stationary points of convex optimization has not received attention, although it is fundamentally important. I think this paper nicely fills in the gap. In specific, developing variants of OGM-G is a nice complement to OGM-G, especially Proposition 3.1 and the relaxation of (P). A more interesting contribution of this paper is the development of both Acc-SVRG-G and R-Acc-SVRG-G. The latter achieves the best existing rates up to a logarithmic factor, while not requiring the knowledge of the (usually unavailable) initial constant, which is new and important.\n\nI only have couple of minor comments.\n- line 37: NAG having a suboptimal rate for minimizing the gradient does not seem to be a sufficient reason for saying that finding near-stationary point is a \"harder\" task.\n- line 46: NAG + OGM-G is missing in the \"IDC + IFC\" case, unlike the Katyusha + L2S. Its variant is later mentioned in Corollary 3.2.1, so it would be nice to mention NAG + OGM-G at some point.\n- line 73: I am curious here whether the function value complexity of Acc-SVRG-G is comparable to the best existing complexity.\n- line 118, 254, 258: Note that a very recent paper below (appeared after the submission deadline) found a potential function for OGM-G and its proximal variant.\nJ. Lee, C. Park, E. K. Ryu, ``\"A geometric structure of acceleration and its role in making gradients small fast,'' arXiv:2106.10439.\n- line 123: OGM-G only has a convergence guarantee on the last iterate, and the authors claim that this can be resolved by M-OGM-G. However, Theorem 3.2 with a bound on the weighted sum of all iterates does not fully resolve the issue of OGM-G as I hoped from the line 123. \n- line 135: In footnote 5, shouldn't it be local solutions, rather than approximate solutions?\n- line 143: What do you mean by \"Algorithm 2 converges optimally on the last iterate\"?\n- line 149: It is minor, but it would be nice to have a square in the gradient norm, so that it is consistent with the IFC case.\n- line 177: $f(x_0) - f(x^*)$ -> $\\Delta_0$?\n- line 183: Is there any intuition behind the \"warm-up phase\", besides the two-stage proof in Appendix? This isn't used for R-Acc-SVRG-G. Would it be useful?\n- line 191: Is the analysis for the low accuracy regime meaningful? (I might just being not familiar with such analysis.) Does Acc-SVRG-G with different parameter choice or any other existing method (like Katyusha) have a larger complexity for such regime?\n- line 208: Which rate should I compare here?\n- line 213: I kind of understand that such termination conditions indicate the poor quality of the current estimate $\\delta_t$. Could you explain it in more details?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- In Section 4, since previous section studied OGM-G for finding near-stationary point, I was expecting the Acc-SVRG-G to be built upon (or related to) OGM-G (other than NAG and OGM). Also, while Section 3 mainly assumes IFC (then IDC), Section 4 mainly assumes IDC. Although the resulting analysis is interesting, I found Sections 3 and 4 to be somewhat disconnected. \n\n- The parameters for R-Acc-SVRG-G is relatively complicated, but this seems inevitable.\n\n- A numerical experiment in comparison to L2S, SAG, SVRG in Appendix A looks promising, but it is not sufficient in the eyes of practitioners. The authors did not compare with other algorithms that require fixing the accuracy $\\epsilon$, but still one can compare methods in terms of the number of computational complexity to achieve the accuracy. (Note that I am not asking for further experiments, since the paper is theory-oriented.)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers algorithms to find near stationary points ( $\\| \nabla f(x) \\| \\le \epsilon $ ) for convex finite-sums, as opposed to finding points with small objective value $f(x) - \\min_y f(y) \\le \\epsilon$. They propose three new algorithms.  As one reviewer said during discussion (and seconded by another reviewer), they liked that the proposed M-OGM-G method is produced from a computer-aided method (PEP-style ideas being a new field of optimization), they agree the proof for Acc-SVRG-G is very non-trivial, and also that this problem (of near stationary points) is of interest and has not seen enough attention.

Reviewer 3GpM gave the paper a very high score, but explained more in discussion that this was mainly due to the apparent correctness of the math, and not necessarily to be interpreted as an overall score (in terms of contribution).

The dominant concern of all reviewers (including 3GpM) was that the paper is too incremental. For each of the three algorithms, there are specific improvements, but some of these are slight.  Even the most positive reviewer, 3GpM, was less enthusiastic after reading the author(s) response to reviewer hnRP, as this makes it sound like the improvement is incremental.

Looking at the paper myself, the paper is nicely written, and I like the fact that it reviews recent literature. But it's really a collection of a few small improvements, and I don't think these "sum" up to be equivalent to a major result.  This is nice work, but the end result is just not particularly exciting.  My suggestion is the the authors submit this work, with only minor changes, to a slightly lower tier venue, as I think the work deserves to be published but just not necessarily in a tier-1 venue.
Decision: Reject