Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
Year: 2021

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

The problem of finding near-stationary points in convex optimization has not been1 adequately studied yet, unlike other optimality measures such as the function2 value. Even in the deterministic case, the optimal method (OGM-G, due to Kim3 and Fessler [33]) has just been discovered recently. In this work, we conduct a4 systematic study of algorithmic techniques for finding near-stationary points of5 convex finite-sums. Our main contributions are several algorithmic discoveries:6 (1) we discover a memory-saving variant of OGM-G based on the performance7 estimation problem approach [19]; (2) we design a new accelerated SVRG variant8 that can simultaneously achieve fast rates for minimizing both the gradient norm9 and function value; (3) we propose an adaptively regularized accelerated SVRG10 variant, which does not require the knowledge of some unknown initial constants11 and achieves near-optimal complexities. We put an emphasis on the simplicity and12 practicality of the new schemes, which could facilitate future developments.13
1 Introduction14
Classic convex optimization usually focuses on providing guarantees for minimizing function value.15 For this task, the optimal (up to constant factors) Nesterov’s accelerated gradient method (NAG)16 [40, 41] has been known for decades, and there are even methods that can exactly match the lower17 complexity bounds [30, 17, 55, 18]. On the other hand, in general non-convex optimization, near-18 stationarity is the typical optimality measure, and there has been a flurry of recent research devoted to19 this topic [25, 26, 23, 28, 21, 60]. Recently, there has been growing interest on devising fast schemes20 for finding near-stationary points in convex optimization [42, 2, 22, 7, 31, 32, 33, 27, 15, 14]. This21 line of research is basically driven by the following facts.22
• Nesterov [42] studied the problem with a linear constraint: f(x?) = minx∈Q {f(x) : Ax = b},23 whereQ is a convex set and f is strongly convex. Assuming thatQ and f are simple, we can focus24 on the dual problem φ(y?) = maxy{φ(y) , minx∈Q {f(x) + 〈y, b−Ax〉}}. Clearly, the dual25 objective−φ(y) is smooth convex. Letting xy be the unique solution to the inner problem, we have26 ∇φ(y) = b − Axy. Note that f(xy) − f(x?) = φ(y) − 〈y,∇φ(y)〉 − φ(y?) ≤ ‖y‖ ‖∇φ(y)‖ .27 Thus, in this problem, the quantity ‖∇φ(y)‖ serves as a measure of both primal optimality28 f(xy)−f(x?) and feasibility ‖b−Axy‖, which is better than just measuring the function value.29
• Matrix scaling [50] is a convex problem and its goal is to find near-stationary points [4, 9].30 • Gradient norm is readily available, unlike other optimality measures (f(x)−f(x?) and ‖x− x?‖),31 and is thus usable as a stopping criterion. This fact motivates the design of several parameter-free32 algorithms [43, 39, 27], and their guarantees are established on the gradient norm.33
• Designing schemes for minimizing the gradient norm can inspire new non-convex optimization34 methods. For example, SARAH [46] was designed for convex finite-sums with gradient-norm mea-35 sure, but was later discovered to be the near-optimal method for non-convex finite-sums [21, 47].36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Moreover, finding near-stationary points is a harder task than minimizing function value, because37 NAG has the optimal guarantee for f(x)− f(x?) but is only suboptimal for minimizing ‖∇f(x)‖.38 In this work, we consider the problem minx∈Rd f(x) = 1n ∑n i=1 fi(x), where each fi is L-smooth39 and convex. We focus on finding an -stationary point of this objective, i.e., a point with ‖∇f(x)‖ ≤ .40 We use X ? to denote the set of optimal solutions, which is assumed to be nonempty. There are two41 different assumptions on the initial point x0, namely, the Initial bounded-Function Condition (IFC):42 f(x0)− f(x?) ≤ ∆0, and the Initial bounded-Distance Condition (IDC): ‖x0 − x?‖ ≤ R0 for some43 x? ∈ X ?. This subtlety results in drastically different best achievable rates as studied in [7, 22].44 Below we categorize existing algorithmic techniques into three classes (relating to Table 1).45
(i) “IDC + IFC”. Nesterov [42] showed that we can combine the guarantees of a method46 minimizing function value under IDC and a method finding near-stationary points under IFC47 to produce a faster one for minimizing gradient norm under IDC. For example, NAG produces48 f(xK1)− f(x?) = O(
LR20 K21 ) [40] and GD produces ‖∇f(xK2)‖ 2
= O (L(f(x0)−f(x?))
K2
) [33]49
under IFC. Letting x0 = xK1 and K = K1 +K2, by balancing the ratio of K1 and K2, we50 obtain the guarantee ‖∇f(xK)‖2 = O(L 2R20 K3 ) for “NAG + GD”. We point out that we can use51 this technique to combine the guarantees of Katyusha [1] and SARAH2 [46]; see Appendix E.52
(ii) Regularization. Nesterov [42] used NAG (strongly convex variant) to solve the regularized53 objective, and showed that it achieves near-optimal complexity (optimal up to logarithmic54 factors). Inspired by this technique, Allen-Zhu [2] proposed recursive regularization for55 stochastic approximation algorithms, which also achieves near-optimal complexities [22].56
1Table 1 shows that Katyusha+L2S has a slightly better dependence on n than Acc-SVRG-G. It is due to the adoption of n-dependent step size in L2S. As studied in [37], despite having a better complexity, n-dependent step size boosts numerical performance only when n is extremely large. If the practically fast n-independent step size is used for L2S, Katyusha+L2S and Acc-SVRG-G have the same complexity. See also Appendix A.
2We adopt the loopless variant of SARAH in [37], which has a refined analysis for general convex objectives.
(iii) Direct methods. Due to the lack of insight, existing direct methods are mostly derived or57 analyzed with the help of computer-aided tools [31, 32, 54, 33]. The computer-aided approach58 was pioneered by Drori and Teboulle [19], who introduced the performance estimation59 problem (PEP). The only known optimal method OGM-G [33] was designed based on the60 PEP approach.61
Observe that since f(x)− f(x?) ≤ ‖∇f(x)‖ ‖x− x?‖, the lower bound for finding near-stationary62 points must be of the same order as for minimizing function value [44]. Thus, under IDC, the lower63 bound is Ω(n+ √ n ) due to [58]. Under IFC, we can establish an Ω(n+ √ n ) lower bound using64 the techniques in [7, 58]. The main contributions of this work are three new algorithmic schemes that65 improve the practicalities of existing methods as summarized below (highlighted in Table 1).66
• (Section 3) We propose a memory-saving variant of OGM-G for the deterministic case (n = 1),67 which does not require a pre-computed and stored parameter sequence. The derivation of the new68 variant is inspired by the numerical solution to a PEP problem.69
• (Section 4) We propose a new accelerated SVRG [29, 59] variant that can simultaneously70 achieve fast convergence rates for minimizing both the gradient norm and function value, that is,71 O(n log 1 + n2/3 2/3 ) complexity for gradient norm and O(n log 1 + √ n ) complexity for function72 value. Note that other stochastic approaches in Table 1 do not have this property.73 • (Section 5) We propose an adaptively regularized accelerated SVRG variant, which does not74 require the knowledge of R0 or ∆0 and achieves a near-optimal complexity under IDC or IFC.75
We put in extra efforts to make the proposed schemes as simple and elegant as possible. We believe76 that the simplicity makes the extensions of the new schemes easier.77
2 Preliminaries78
Throughout this paper, we use 〈·, ·〉 and ‖·‖ to denote the inner product and the Euclidean norm,79 respectively. We let [n] denote the set {1, 2, . . . , n}, E denote the total expectation and Eik denote80 the expectation with respect to a random sample ik. We say that a function f : Rd → R is L-smooth81 if it has L-Lipschitz continuous gradients, i.e.,82
∀x, y ∈ Rd, ‖∇f(x)−∇f(y)‖ ≤ L ‖x− y‖ .
A continuously differentiable f is called µ-strongly convex if83
∀x, y ∈ Rd, f(x)− f(y)− 〈∇f(y), x− y〉 ≥ µ 2 ‖x− y‖2 .
Other equivalent definitions of these two assumptions can be found in the textbook [44]. The84 following is an important consequence of a function f being L-smooth and convex:85
∀x, y ∈ Rd, f(x)− f(y)− 〈∇f(y), x− y〉 ≥ 1 2L ‖∇f(x)−∇f(y)‖2 . (1)
We call (1) the interpolation condition at (x, y) following [56]. If f is both L-smooth and µ-strongly86 convex, we can define a “shifted” function h(x) = f(x)− f(x?)− µ2 ‖x− x
?‖2 following [63]. It87 can be easily verified that h is (L− µ)-smooth and convex, and thus from (1),88
∀x, y ∈ Rd, h(x)− h(y)− 〈∇h(y), x− y〉 ≥ 1 2(L− µ) ‖∇h(x)−∇h(y)‖2 , (2)
which is equivalent to the strongly convex interpolation condition discovered in [56].89
Oracle complexity (or simply complexity) refers to the required number of stochastic gradient∇fi90 computations to find an -accurate solution.91
3 OGM-G: “Momentum” Reformulation and a Memory-Saving Variant92
In this section, we focus on the IFC case, i.e., f(x0)− f(x?) ≤ ∆0. We use N to denote the total93 iteration number to prevent confusion (in other sections, we use K). Proofs in this section are given in94
Algorithm 1 OGM-G: “Momentum” reformulation
Input: initial guess x0 ∈ Rd, total iteration number N . Initialize: vector v0 = 0, scalars θN = 1 and θ2k − θk = θ2k+1, for k = 0 . . . N − 1.
1: for k = 0, . . . , N − 1 do 2: vk+1 = vk +
1 Lθkθ2k+1 ∇f(xk). 3: xk+1 = xk − 1L∇f(xk)− (2θ 3 k+1 − θ2k+1)vk+1.
4: end for Output: xN .
Appendix B. Recall that OGM-G has the following updates [33]. Let y0 = x0. For k = 0, . . . , N−1,95 96
yk+1 = xk − 1
L ∇f(xk),
xk+1 = yk+1 + (θk − 1)(2θk+1 − 1)
θk(2θk − 1) (yk+1 − yk) + 2θk+1 − 1 2θk − 1
(yk+1 − xk), (3)
where {θk} is recursively defined: θN = 1 and { θ2k − θk = θ2k+1 k = 1 . . . N − 1, θ20 − θ0 = 2θ21 otherwise. 97
OGM-G was discovered from the numerical solution to an SDP problem and its analysis is to show98 that the step coefficients in (3) specify a feasible solution to the SDP problem. While this analysis is99 natural for the PEP approach, it is hard to understand how each coefficient affects the rate, especially100 if one wants to generalize the scheme. Here we provide a simple algebraic analysis for OGM-G.101
We start with a reformulation3 of OGM-G in Algorithm 1, which aims to simplify the proof. We102 adopt a consistent {θk}: θN = 1 and θ2k − θk = θ2k+1, k = 0 . . . N − 1, which only costs a constant103 factor.4 Interestingly, the reformulated scheme resembles the heavy-ball momentum method [49].104 However, it can be shown that Algorithm 1 is not covered by the heavy-ball momentum scheme.105 Defining θ2N+1 = θ 2 N − θN = 0, we provide the one-iteration analysis in the following proposition:106
Proposition 3.1. In Algorithm 1, the following holds at any iteration k ∈ {0, . . . , N − 1} :107 Ak +Bk+1 + Ck+1 + Ek+1 ≤ Ak+1 +Bk + Ck + Ek − θk+1 〈∇f(xk+1), vk+1〉
+ N∑ i=k+1 θi Lθkθ2k+1 〈∇f(xk),∇f(xi)〉, (4)
withAk , 1θ2k (f(xN )−f(x?)− 12L ‖∇f(xN )‖ 2 ),Bk , 1θ2k (f(xk)−f(x?)),Ck , 12Lθ2k ‖∇f(xk)‖ 2,108
Ek , θ2k+1 θk 〈∇f(xk), vk〉.109 Remark 3.1.1. A recent work [15] also conducted an algebraic analysis of OGM-G under a potential110 function framework. Their potential function decrease can be directly obtained from Proposition 3.1111 by summing up (4). By contrast, our “momentum” vector {vk} naturally merges into the analysis,112 which significantly simplifies the analysis. Moreover, it provides a better interpretation on how113 OGM-G utilizes the past gradients to achieve acceleration.114
From (4), we see that only the last two terms do not telescope. Note that the “momentum” vector is a115 weighted sum of the past gradients, i.e., vk+1 = ∑k i=0
1 Lθiθ2i+1 ∇f(xi). If we sum the terms up from116 k = 0, . . . , N − 1, it can be verified that they exactly sum up to 0. The presence of these special117 terms prevents OGM-G to have a usual potential function (e.g., those in [6]). Then, by telescoping118 the remaining terms, we obtain the final convergence guarantee.119
Theorem 3.1. The output of Algorithm 1 satisfies ‖∇f(xN )‖2 ≤ 8L∆0(N+2)2 .120
We observe two drawbacks of OGM-G (same as the algorithm description in [15]): (1) it requires121 storing a pre-computed parameter sequence, which costs O( 1 ) floats; (2) except for the last iterate,122
3It can be verified that this scheme is equivalent to the original one (3) through vk = 1(2θk−1)θ2k (yk − xk). 4The original guarantee of OGM-G can be recovered if we set θ20 − θ0 = 2θ21 .
Algorithm 2 M-OGM-G: Memory-saving OGM-G
Input: initial guess x0 ∈ Rd, total iteration number N . Initialize: vector v0 = 0.
1: for k = 0, . . . , N − 1 do 2: vk+1 = vk + 12 L(N−k+1)(N−k+2)(N−k+3)∇f(xk). 3: xk+1 = xk − 1L∇f(xk)− (N−k)(N−k+1)(N−k+2)
6 vk+1. 4: end for
Output: xN or arg minx∈{x0,...,xN} ‖∇f(x)‖.
all other iterates are not known to have guarantees. We resolve these issues by proposing another123 parameterization of Algorithm 1 in the next subsection.124
3.1 Memory-Saving OGM-G125
A straightforward idea to resolve the aforementioned issues is to generalize Algorithm 1. However,126 we find it rather difficult since the parameters in the analysis are rather strict (despite that the proof is127 already simple). We choose to rely on computer-aided techniques [19]. The derivation of this variant128 (Algorithm 2) is based on the following numerical experiment.129
Numerical experiment. OGM-G was discovered when considering the relaxed PEP problem [33]:130
max ∇f(x0),...,∇f(xN )∈Rd f(x0),...,f(xN ),f(x ?)∈R
‖∇f(xN )‖2
subject to  interpolation condition (1) at (xk, xk+1), k = 0, . . . , N − 1, interpolation condition (1) at (xN , xk), k = 0, . . . , N − 1, interpolation condition (1) at (xN , x?), f(x0)− f(x?) ≤ ∆0,
(P)
where the sequence {xk} is defined as xk+1 = xk − 1L ∑k i=0 hk+1,i∇f(xi), k = 0, . . . , N − 1 for131 some step coefficients h ∈ RN(N+1)/2. Given N , the step coefficients of OGM-G correspond to132 a numerical solution to the problem: arg minh{Lagrangian dual of (P)}, which is denoted as (HD).133 Conceptually, solving problem (HD) would give us the fastest possible step coefficients under the134 constraints.5 We expect there to be some constant-time slower schemes, which are neglected when135 solving (HD). To identify such schemes, we relax a set of interpolation conditions in problem (P):136
f(xN )− f(xk)− 〈∇f(xk), xN − xk〉 ≥ 1
2L ‖∇f(xN )−∇f(xk)‖2 − ρ ‖∇f(xk)‖2 ,
for k = 0, . . . , N − 1 and some ρ > 0. After this relaxation, solving (HD) will no longer give us the137 step coefficients of OGM-G. By trying different ρ and checking the dependence on N , we discover138 Algorithm 2 when ρ = 12L . Similar to our analysis of OGM-G, we provide a simple algebraic analysis139 for the new variant in the following theorem.140
Theorem 3.2. Define δk+1, 12(N−k+1)(N−k+2)(N−k+3) , k = 0, . . . , N . In Algorithm 2, it holds that141 142
N∑ k=0 δk+1 2 ‖∇f(xk)‖2 ≤ 12L∆0 (N + 2)(N + 3) . (5)
Remark 3.2.1. Algorithm 2 converges optimally on the last iterate (note that δN+1 = 2) and the143 minimum gradient since144
min k∈{0,...,N}
‖∇f(xk)‖2 ≤ 1∑N
k=0 δk+1 2 N∑ k=0 δk+1 2 ‖∇f(xk)‖2 ≤ 8L∆0 (N + 2)(N + 3)− 2 .
Clearly, the parameters of this variant can be computed on the fly and from (5), each iterate has a145 guarantee (although the guarantee degenerates quickly as k → 0 since 1/δk+1 = Ω((N − k)3)).146 Moreover, we can extend the benefits into the IDC case using the ideas in [42] as summarized below.147
5However, since problem (HD) is non-convex, we can only obtain approximate solutions.
Algorithm 3 Acc-SVRG-G: Accelerated SVRG for Gradient minimization
Input: parameters {τk}, {pk}, initial guess x0 ∈ Rd, total iteration number K. Initialize: vectors z0 = x̃0 = x0 and scalars αk = Lτk1−τk ,∀k and τ̃ = ∑K−1 k=0 τ −2 k .
1: for k = 0, . . . ,K − 1 do 2: yk = τkzk + (1− τk) ( x̃k − 1L∇f(x̃k) ) .
3: zk+1 = arg minx { 〈Gk, x〉+ (αk/2) ‖x− zk‖2 } .
4: //Gk , ∇fik(yk)−∇fik(x̃k) +∇f(x̃k), where ik is sampled uniformly in [n].
5: x̃k+1 = { yk with probability pk, x̃k with probability 1− pk.
6: end for Output (for gradient): xout is sampled from { Prob{xout = x̃k} = τ−2k τ̃ ∣∣∣ k ∈ {0, . . . ,K − 1}}. Output (for function value): x̃K .
Corollary 3.2.1 (IDC case). If we first run N/2 iterations of NAG and then continue with N/2148 iterations of Algorithm 2, we obtain an output satisfying ‖∇f(xN )‖ = O(LR0N2 ).149
4 Accelerated SVRG: Fast Rates for Both Gradient Norm and Objective150
In this section, we focus on the IDC case, i.e., ‖x0 − x?‖ ≤ R0 for some x? ∈ X ?. From the151 development in the previous section, it is natural to ask whether we can use the PEP approach to152 motivate new stochastic schemes. However, due to the exponential growth of the number of possible153 states (i0, i1, . . .), we cannot directly adopt this approach. A feasible alternative is to first fix an154 algorithmic framework and a family of potential functions, and then use the potential-based PEP155 approach in [54]. However, this approach is much more restrictive. For example, it cannot identify156 special constructions like (4) in OGM-G. Fortunately, as we will see, we can get some inspiration157 from the recent development of deterministic methods. Proofs in this section are given in Appendix C.158
Our proposed scheme is given in Algorithm 3. We adopt the elegant loopless design of SVRG in159 [34]. Note that the full gradient ∇f(x̃k) is computed and stored only when x̃k+1 = yk at Step 5. We160 summarize our main technical novelty as follows.161
Main algorithmic novelty. The design of stochastic accelerated methods is largely inspired by162 NAG. To make it clear, by setting n = 1, we see that Katyusha [1], MiG [61], SSNM [62], Varag [36],163 VRADA [52], ANITA [38], the acceleration framework in [16] and AC-SA [35, 24] all reduce to one164 of the following variants of NAG. We say that these methods are under the NAG framework.165 
xk = τkzk + (1− τk)yk, zk+1 = zk − αk∇f(xk), yk+1 = τkzk+1 + (1− τk)yk.
 xk = τkzk + (1− τk)yk, zk+1 = zk − αk∇f(xk), yk+1 = xk − ηk∇f(xk).
Auslender and Teboulle [5] Linear Coupling [64]
See [57, 12] for other variants of NAG. When n = 1, Algorithm 3 reduces to the following scheme:166 { yk = τkzk + (1− τk) ( yk−1 − 1L∇f(yk−1) ) ,
zk+1 = zk − 1αk∇f(yk).
Optimized Gradient Method (OGM) [19, 30]
Algorithm 3 reduces to the scheme of OGM when n = 1 (this point is clearer in the formulation of167 ITEM in [55]). OGM has a constant-time faster worst-case rate than NAG, which exactly matches168 the lower complexity bound established in [17]. In the following proposition, we show that the OGM169 framework helps us conduct a tight one-iteration analysis, which gives room for achieving our goal.170
Proposition 4.1. In Algorithm 3, the following holds at any iteration k ≥ 0 and ∀x? ∈ X ? :171 ( 1− τk τ2kpk E [f(x̃k+1)− f(x?)] + L 2 E [ ‖zk+1 − x?‖2 ]) + (1− τk)2 2Lτ2k E [ ‖∇f(x̃k)‖2 ] ≤ (
(1− τkpk)(1− τk) τ2kpk E [f(x̃k)− f(x?)] + L 2 E [ ‖zk − x?‖2 ]) .
(6)
The terms inside the parentheses form the commonly used potential function of SVRG variants. The172 additional E[‖∇f(x̃k)‖2] term is created by adopting the OGM framework. In other words, we use173 the following potential function for Algorithm 3 (ak, bk, ck ≥ 0):174
Tk = akE [f(x̃k)− f(x?)] + bkE [ ‖zk − x?‖2 ] + k−1∑ i=0 ciE [ ‖∇f(x̃i)‖2 ] .
We first provide a simple parameter choice, which leads to a simple and clean analysis.175 Theorem 4.1 (Single-stage parameter choice). In Algorithm 3, if we choose pk ≡ 1n , τk = 3 k/n+6 ,176 then the following holds at the outputs:177
E [ ‖∇f(xout)‖2 ] = O
( n3L ( f(x0)− f(x?) ) + n2L2R20
K3
) ,
E [f(x̃K)]− f(x?) = O
( n2 ( f(x0)− f(x?) ) + nLR20
K2
) .
(7)
In other words, to guarantee that E [‖∇f(xout)‖] ≤ g and E [f(x̃K)]− f(x?) ≤ f , the oracle com-178 plexities are O ( n(L(f(x0)−f(x?)))1/3
2/3 g
+ (nLR0) 2/3
2/3 g
) and O ( n √
f(x0)−f(x?) f + √ nLR0√ f
) , respectively.179
From (7), we see that Algorithm 3 achieves fast O( 1K1.5 ) and O( 1 K2 ) rates for minimizing the180 gradient norm and function value at the same time. However, despite being a simple choice, the oracle181 complexities are not better than the deterministic methods in Table 1. Below we provide a two-stage182 parameter choice, which is inspired by the idea of including a “warm-up phase” in [3, 36, 52, 38].183 This theorem corresponds to the reported result in Table 1.184 Theorem 4.2 (Two-stage parameter choice). In Algorithm 3, let pk = max{ 6k+8 , 1 n}, τk = 3 pk(k+8)
.185 The oracle complexities needed to guarantee E [‖∇f(xout)‖] ≤ g and E [f(x̃K)]− f(x?) ≤ f are186
O ( nmin { log
LR0 g , log n
} + (nLR0) 2/3
2/3 g
) and O ( nmin { log
LR20 f , log n
} +
√ nLR0√ f
) ,
respectively.187
If is large or n is very large, the recently proposed ANITA [38] achieves an O(n) complexity, which188 matches the lower complexity bound Ω(n) in this case [58]. Since ANITA uses the NAG framework,189 we show that similar results can be derived under the OGM framework in the following theorem:190 Theorem 4.3 (Low accuracy parameter choice). In Algorithm 3, let iteration N be the first time191 Step 5 updates x̃k+1 = yk. If we choose pk ≡ 1n , τk ≡ 1 − 1√ n+1
and terminate Algorithm 3 at192 iteration N , then the following holds at x̃N+1 :193
E [ ‖∇f(x̃N+1)‖2 ] ≤ 8L
2R20 5( √ n+ 1 + 1) and E [f(x̃N+1)]− f(x?) ≤ LR20√ n+ 1 + 1 .
In particular, if the required accuracies are low (or n is very large), i.e., 2g ≥ 8L2R20 5( √ n+1+1) and194
f ≥ LR 2 0√
n+1+1 , then Algorithm 3 only has an O(n) oracle complexity.195
In the low accuracy region (specified above), the choice in Theorem 4.3 removes the O(log 1 ) factor196 in the complexity of Theorem 4.2. We include some numerical justifications of Algorithm 3 in197 Appendix A. We believe that the potential-based PEP approach in [54] can help us identify better198 parameter choices of Algorithm 3, which we leave for future work.199
Algorithm 4 R-Acc-SVRG-G
Input: accuracy > 0, parameters δ0 = L, β > 1, initial guess x0 ∈ Rd. 1: for t = 0, 1, 2, . . . do 2: Define fδt(x) = (1/n) ∑n i=1 f δt i (x), where f δt i (x) = fi(x) + (δt/2) ‖x− x0‖
2. 3: Initialize vectors z0 = x̃0 = x0 and set τx, τz, α, p, CIDC, CIFC according to Proposition 5.1. 4: for k = 0, 1, 2, . . . do 5: yk = τxzk + (1− τx) x̃k + τz ( δt(x̃k − zk)−∇fδt(x̃k) ) .
6: zk+1 = arg minx {〈 Gδtk , x 〉 + (α/2) ‖x− zk‖2 + (δt/2) ‖x− yk‖2 } .
7: //Gδtk , ∇f δt ik (yk)−∇fδtik (x̃k) +∇f δt(x̃k), where ik is sampled uniformly in [n].
8: x̃k+1 = { yk with probability p, x̃k with probability 1− p.
9: if 6‖∇f(x̃k)‖ ≤ then output x̃k and terminate the algorithm. 10: if under IDC and (1 + δtα ) k ≥ √ CIDC/δt then break the inner loop. 11: if under IFC and (1 + δtα ) k ≥ √ CIFC/2δt then break the inner loop. 12: end for 13: δt+1 = δt/β. 14: end for
5 Near-Optimal Accelerated SVRG with Adaptive Regularization200
Currently, there is no known stochastic method that directly achieves the optimal rate in . To get near-201 optimal rates, the existing strategy is to use a carefully designed regularization technique [42, 2] with202 a method that solves strongly convex problems; see, e.g., [42, 2, 22, 11]. However, the regularization203 parameter requires the knowledge of R0 or ∆0, which significantly limits its practicality.204
Inspired by the recently proposed adaptive regularization technique [27], we develop a near-optimal205 accelerated SVRG variant (Algorithm 4) that does not require the knowledge of R0 or ∆0. Note206 that this technique was originally proposed for NAG under the IDC assumption. Our development207 extends this technique to the stochastic setting, which brings an O( √ n) rate improvement. Moreover,208 we consider both IFC and IDC cases. Proofs in this section are provided in Appendix D.209
Detailed design. Algorithm 4 has a “guess-and-check” framework. In the outer loop, we first210 define the regularized objective fδt using the current estimate of regularization parameter δt, and211 then we initialize an accelerated SVRG method (the inner loop) to solve the δt-strongly convex fδt .212 If the inner loop breaks at Step 10 or 11, indicating the poor quality of the current estimate δt, δt will213 be divided by a fixed β. Thus, conceptually, we can adopt any method that solves strongly convex214 finite-sums at the optimal rate as the inner loop. However, since the constructions of Step 10 or 11215 require some algorithm-dependent constants, we have to fix one method as the inner loop.216
The inner loop we adopted is a loopless variant of BS-SVRG [63]. This is because (i) BS-SVRG is217 the fastest known accelerated SVRG variant (for ill-conditioned problems) and (ii) it has a simple218 scheme, especially after using the loopless construction [34]. However, its original guarantee is built219 upon {zk}. Clearly, we cannot implement the stopping criterion (Step 9) on ‖∇f(zk)‖. Interestingly,220 we discover that its sequence {x̃k} works perfectly in our regularization framework, even if we can221 neither establish convergence on f(x̃k) − f(x?) nor on ‖x̃k − x?‖2.7 Moreover, we find that the222 loopless construction significantly simplifies the parameter constraints of BS-SVRG, which originally223 involves Θ(n)th-order inequality. We provide the detailed parameter choice as follows:224
Proposition 5.1 (Parameter choice). In Algorithm 4, we set τx = α+δtα+L+δt , τz = τx δt − α(1−τx)δtL and225 p = 1n . We set α as the (unique) positive root of the cubic equation ( 1− p(α+δt)α+L+δt ) ( 1 + δtα )2 = 1226
and specify CIDC = L2 + Lα 2p L+(1−p)(α+δt) , CIFC = 2L+ 2Lα2p (L+(1−p)(α+δt))δt . Under these choices, we227 have αδt = O ( n+ √ n(L/δt + 1) ) , CIDC = O ( (L+ δt) 2 ) , and CIFC = O(L).228
6Note that we maintain the full gradient∇fδt(x̃k) and∇f(x̃k) = ∇fδt(x̃k)− δt(x̃k − x0). 7It is due to the special potential function of BS-SVRG (see (27)), which does not contain these two terms.
Under the choices of τx and τz , the α above is the optimal choice in our analysis. Then, we can229 characterize the progress of the inner loop in the following proposition:230 Proposition 5.2 (The inner loop of Algorithm 4). Using the parameters specified in Proposition 5.1,231 after running the inner loop (Step 4-12) of Algorithm 4 for k iterations, we can conclude that232
(i) under IDC, i.e., ‖x0 − x?‖ ≤ R0 for some x? ∈ X ?,233
E [‖∇f(x̃k)‖] ≤ ( δt + ( 1 +
δt α
)−k√ CIDC ) R0,
(ii) under IFC, i.e., f(x0)− f(x?) ≤ ∆0,234
E [‖∇f(x̃k)‖] ≤ (√ 2δt + ( 1 +
δt α
)−k√ CIFC )√ ∆0.
The above results motivate the design of Step 10 and 11. For example, in the IDC case, when the235 inner loop breaks at Step 10, using (i) above, we obtain E [‖∇f(x̃k)‖] ≤ 2δtR0. Then, by discussing236 the relative size of δt and a certain constant, we can estimate the complexity of Algorithm 4. The237 same methodology is used for the IFC case.238 Theorem 5.1 (IDC case). Denote δ?IDC = q 2R0
for some q ∈ (0, 1) and let the outer iteration t = `239 be the first time8 δ` ≤ δ?IDC. The following assertions hold:240
(i) At outer iteration `, Algorithm 4 terminates with probability at least 1− q.9241 (ii) The total expected oracle complexity of the `+ 1 outer loops is242
O (( n log
LR0 q + √ nLR0 q ) log LR0 q ) .
Theorem 5.2 (IFC case). Denote δ?IFC = 2q2 8∆0 for some q ∈ (0, 1) and let the outer iteration t = ` be243 the first time δ` ≤ δ?IFC. The following assertions hold:244 (i) At outer iteration `, Algorithm 4 terminates with probability at least 1− q.245 (ii) The total expected oracle complexity of the `+ 1 outer loops is246
O (( n log
√ L∆0 q + √ nL∆0 q
) log
√ L∆0 q
) .
Compared with regularized Katyusha in Table 1, the adaptive regularization approach drops the need247 to estimate R0 or ∆0 at the cost of a mere log 1 factor in the non-dominant term (if is small).248
6 Discussion249
In this work, we proposed several simple and practical schemes that complement existing works250 (Table 1). Admittedly, the new schemes are currently only limited to the unconstrained Euclidean251 setting, because our techniques heavily rely on the interpolation conditions (1) and (2). On the other252 hand, methods such as OGM [30], TM [51] and ITEM [55, 10], which also rely on these conditions,253 are still not known to have their proximal variants. We list a few future directions as follows.254
(1) It is not clear how to naturally connect the parameters of M-OGM-G (Algorithm 2) to OGM-G255 (Algorithm 1). The parameters of both algorithms seem to be quite restrictive and hardly generalizable256 due to the special construction in (4). Does there exist an optimal method for minimizing the gradient257 norm that has a proper potential function (at each iteration)?258
(2) Is this new “momentum” in OGM-G beneficial for training neural nets? Other classic momentum259 schemes such as NAG [40] or heavy-ball momentum method [49] are extremely effective for this260 task [53], and they were also originally proposed for convex objectives.261
(3) Can we directly accelerate SARAH (L2S)? By extending OGM-G? It seems that existing stochastic262 acceleration techniques fail to accelerate SARAH (or result in poor dependence on n as in [16]).263
8We assume that is small such that max {δ?IDC, δ?IFC} ≤ δ0 = L for simplicity. In this case, ` > 0. 9If Algorithm 4 does not terminate at outer iteration `, it terminates at the next outer iteration with probability
at least 1− q/β. That is, it terminates with higher and higher probability. The same goes for the IFC case.
References264 [1] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of265 Machine Learning Research, 18(1):8194–8244, 2017. 2, 6, 26266
[2] Z. Allen-Zhu. How to make the gradients small stochastically: Even faster convex and noncon-267 vex sgd. In Advances in Neural Information Processing Systems, pages 1157–1167, 2018. 1, 2,268 8269
[3] Z. Allen-Zhu and Y. Yuan. Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex270 Objectives. In Proceedings of The 33rd International Conference on Machine Learning, pages271 1080–1089, 2016. 7272
[4] Z. Allen-Zhu, Y. Li, R. M. de Oliveira, and A. Wigderson. Much Faster Algorithms for Matrix273 Scaling. In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer274 Science, pages 890–901, 2017. 1275
[5] A. Auslender and M. Teboulle. Interior gradient and proximal methods for convex and conic276 optimization. SIAM Journal on Optimization, 16(3):697–725, 2006. 6277
[6] N. Bansal and A. Gupta. Potential-Function Proofs for Gradient Methods. Theory of Computing,278 15(4):1–32, 2019. 4279
[7] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points280 ii: first-order methods. Mathematical Programming, 185(1-2), 2021. 1, 2, 3281
[8] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions282 on Intelligent Systems and Technology, 2:27:1–27:27, 2011. Software available at http:283 //www.csie.ntu.edu.tw/~cjlin/libsvm. 13, 14284
[9] M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu. Matrix Scaling and Balancing via Box285 Constrained Newton’s Method and Interior Point Methods. In IEEE 58th Annual Symposium on286 Foundations of Computer Science, pages 902–913. IEEE, 2017. 1287
[10] A. d’Aspremont, D. Scieur, and A. Taylor. Acceleration methods. arXiv preprint288 arXiv:2101.09545, 2021. 9289
[11] D. Davis and D. Drusvyatskiy. Complexity of finding near-stationary points of convex functions290 stochastically. arXiv preprint arXiv:1802.08556, 2018. 8291
[12] A. Defazio. On the Curved Geometry of Accelerated Optimization. In Advances in Neural292 Information Processing Systems, volume 32, pages 1764–1773, 2019. 6293
[13] A. Defazio, F. R. Bach, and S. Lacoste-Julien. SAGA: A Fast Incremental Gradient Method With294 Support for Non-Strongly Convex Composite Objectives. In Advances in Neural Information295 Processing Systems, pages 1646–1654, 2014. 14296
[14] J. Diakonikolas and C. Guzmán. Complementary Composite Minimization, Small Gradients in297 General Norms, and Applications to Regression Problems. arXiv preprint arXiv:2101.11041,298 2021. 1299
[15] J. Diakonikolas and P. Wang. Potential Function-based Framework for Making the Gradients300 Small in Convex and Min-Max Optimization. arXiv preprint arXiv:2101.12101, 2021. 1, 4301
[16] D. Driggs, M. J. Ehrhardt, and C.-B. Schönlieb. Accelerating variance-reduced stochastic302 gradient methods. Mathematical Programming, 2020. doi: 10.1007/s10107-020-01566-2. 6, 9303
[17] Y. Drori. The exact information-based complexity of smooth convex minimization. Journal of304 Complexity, 39:1–16, 2017. 1, 6305
[18] Y. Drori and A. Taylor. On the oracle complexity of smooth strongly convex minimization.306 arXiv preprint arXiv:2101.09740, 2021. 1307
[19] Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization:308 a novel approach. Mathematical Programming, 145(1-2):451–482, 2014. 1, 3, 5, 6309
[20] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://archive.ics.310 uci.edu/ml. 13, 14311
[21] C. Fang, C. J. Li, Z. Lin, and T. Zhang. SPIDER: Near-Optimal Non-Convex Optimization via312 Stochastic Path-Integrated Differential Estimator. In Advances in Neural Information Processing313 Systems, pages 687–697, 2018. 1314
[22] D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. Woodworth. The Complexity315 of Making the Gradient Small in Stochastic Convex Optimization. In Proceedings of the Thirty-316 Second Conference on Learning Theory, pages 1319–1345, 2019. 1, 2, 8317
[23] R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping From Saddle Points — Online Stochastic318 Gradient for Tensor Decomposition. In Proceedings of The 28th Conference on Learning319 Theory, pages 797–842, 2015. 1320
[24] S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex321 stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on322 Optimization, 22(4):1469–1492, 2012. 6323
[25] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic324 programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013. 1325
[26] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic326 programming. Mathematical Programming, 156(1-2):59–99, 2016. 1327
[27] M. Ito and M. Fukuda. Nearly optimal first-order methods for convex optimization under328 gradient norm measure: An adaptive regularization approach. Journal of Optimization Theory329 and Applications, 188(3):770–804, 2021. 1, 2, 8330
[28] C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan. How to Escape Saddle Points331 Efficiently. In Proceedings of the 34th International Conference on Machine Learning, pages332 1724–1732, 2017. 1333
[29] R. Johnson and T. Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance334 Reduction. In Advances in Neural Information Processing Systems, pages 315–323, 2013. 3, 14335
[30] D. Kim and J. A. Fessler. Optimized first-order methods for smooth convex minimization.336 Mathematical Programming, 159(1):81–107, 2016. 1, 6, 9337
[31] D. Kim and J. A. Fessler. Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm338 (FISTA). SIAM Journal on Optimization, 28(1):223–250, 2018. 1, 3339
[32] D. Kim and J. A. Fessler. Generalizing the optimized gradient method for smooth convex340 minimization. SIAM Journal on Optimization, 28(2):1920–1950, 2018. 1, 2, 3341
[33] D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing the342 gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1):343 192–219, 2021. 1, 2, 3, 4, 5344
[34] D. Kovalev, S. Horváth, and P. Richtárik. Don’t jump through hoops and remove those loops:345 SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, pages346 451–467. PMLR, 2020. 6, 8347
[35] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming,348 133(1-2):365–397, 2012. 6349
[36] G. Lan, Z. Li, and Y. Zhou. A unified variance-reduced accelerated gradient method for350 convex optimization. In Advances in Neural Information Processing Systems, volume 32, pages351 10462–10472, 2019. 6, 7352
[37] B. Li, M. Ma, and G. B. Giannakis. On the Convergence of SARAH and Beyond. In Proceedings353 of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages354 223–233, 2020. 2, 14, 27355
[38] Z. Li. ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method. arXiv356 preprint arXiv:2103.11333, 2021. 6, 7357
[39] Q. Lin and L. Xiao. An Adaptive Accelerated Proximal Gradient Method and its Homotopy358 Continuation for Sparse Optimization. In Proceedings of the 31th International Conference on359 Machine Learning, pages 73–81, 2014. 1360
[40] Y. Nesterov. A method for solving the convex programming problem with convergence rate361 O(1/k2). In Dokl. akad. nauk Sssr, volume 269, pages 543–547, 1983. 1, 2, 9362
[41] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer363 Science & Business Media, 2003. 1364
[42] Y. Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society365 Newsletter, (88):10–11, 2012. 1, 2, 5, 8, 22, 27366
[43] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program-367 ming, 140(1):125–161, 2013. 1368
[44] Y. Nesterov. Lectures on convex optimization, volume 137. Springer, 2018. 3, 18369 [45] Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky. Primal–dual accelerated gradient370 methods with small-dimensional relaxation oracle. Optimization Methods and Software, pages371 1–38, 2020. 2372
[46] L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. SARAH: A Novel Method for Ma-373 chine Learning Problems Using Stochastic Recursive Gradient. In Proceedings of the 34th374 International Conference on Machine Learning, pages 2613–2621, 2017. 1, 2375
[47] N. H. Pham, L. M. Nguyen, D. T. Phan, and Q. Tran-Dinh. ProxSARAH: An efficient algorith-376 mic framework for stochastic composite nonconvex optimization. Journal of Machine Learning377 Research, 21(110):1–48, 2020. 1378
[48] J. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines.379 1998. 14380
[49] B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr381 computational mathematics and mathematical physics, 4(5):1–17, 1964. 4, 9382
[50] U. G. Rothblum and H. Schneider. Scalings of matrices which have prespecified row sums and383 column sums via optimization. Linear Algebra and its Applications, 114:737–764, 1989. 1384
[51] B. V. Scoy, R. A. Freeman, and K. M. Lynch. The Fastest Known Globally Convergent First-385 Order Method for Minimizing Strongly Convex Functions. IEEE Control Systems Letters, 2(1):386 49–54, 2017. 9387
[52] C. Song, Y. Jiang, and Y. Ma. Variance Reduction via Accelerated Dual Averaging for Finite-388 Sum Optimization. In Advances in Neural Information Processing Systems, volume 33, pages389 833–844, 2020. 6, 7390
[53] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and391 momentum in deep learning. In Proceedings of the 30th International Conference on Machine392 Learning, pages 1139–1147, 2013. 9393
[54] A. Taylor and F. Bach. Stochastic first-order methods: non-asymptotic and computer-aided394 analyses via potential functions. In Conference on Learning Theory, pages 2934–2992, 2019. 2,395 3, 6, 7396
[55] A. Taylor and Y. Drori. An optimal gradient method for smooth strongly convex minimization.397 arXiv preprint arXiv:2101.09741, 2021. 1, 6, 9398
[56] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact399 worst-case performance of first-order methods. Mathematical Programming, 161(1-2):307–345,400 2017. 3401
[57] P. Tseng. On accelerated proximal gradient methods for convex-concave optimization. https:402 //www.mit.edu/~dimitrib/PTseng/papers/apgm.pdf, 2008. Accessed May 1, 2020. 6403
[58] B. E. Woodworth and N. Srebro. Tight Complexity Bounds for Optimizing Composite Ob-404 jectives. In Advances in Neural Information Processing Systems, pages 3639–3647, 2016. 3,405 7406
[59] L. Xiao and T. Zhang. A Proximal Stochastic Gradient Method with Progressive Variance407 Reduction. SIAM Journal on Optimization, 24(4):2057–2075, 2014. 3, 14408
[60] D. Zhou, P. Xu, and Q. Gu. Stochastic Nested Variance Reduction for Nonconvex Optimization.409 Journal of Machine Learning Research, 21:103:1–103:63, 2020. 1410
[61] K. Zhou, F. Shang, and J. Cheng. A Simple Stochastic Variance Reduced Algorithm with Fast411 Convergence Rates. In Proceedings of the 35th International Conference on Machine Learning,412 pages 5980–5989, 2018. 6413
[62] K. Zhou, Q. Ding, F. Shang, J. Cheng, D. Li, and Z.-Q. Luo. Direct Acceleration of SAGA using414 Sampled Negative Momentum. In Proceedings of the Twenty Second International Conference415 on Artificial Intelligence and Statistics, pages 1602–1610, 2019. 6416
[63] K. Zhou, A. M.-C. So, and J. Cheng. Boosting First-Order Methods by Shifting Objective: New417 Schemes with Faster Worst-Case Rates. In Advances in Neural Information Processing Systems,418 pages 15405–15416, 2020. 3, 8, 22419
[64] Z. A. Zhu and L. Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror420 Descent. In 8th Innovations in Theoretical Computer Science Conference, volume 67 of LIPIcs,421 pages 3:1–3:22, 2017. 6422
Checklist423
1. For all authors...424 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s425 contributions and scope? [Yes]426 (b) Did you describe the limitations of your work? [Yes] See Section 6.427 (c) Did you discuss any potential negative societal impacts of your work? [N/A] We are428 not aware of clear negative societal impacts since we focus on developing generic429 algorithms for convex optimization.430
(d) Have you read the ethics review guidelines and ensured that your paper conforms to431 them? [Yes]432
2. If you are including theoretical results...433 (a) Did you state the full set of assumptions of all theoretical results? [Yes] See the434 introduction.435 (b) Did you include complete proofs of all theoretical results? [Yes]436
3. If you ran experiments...437 (a) Did you include the code, data, and instructions needed to reproduce the main experi-438 mental results (either in the supplemental material or as a URL)? [Yes]439 (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they440 were chosen)? [Yes] See Appendix A.441 (c) Did you report error bars (e.g., with respect to the random seed after running experi-442 ments multiple times)? [Yes] See Figure 1.443 (d) Did you include the total amount of compute and the type of resources used (e.g., type444 of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix A.445 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...446
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix A.447 (b) Did you mention the license of the assets? [Yes] LIBSVM [8] is under the BSD license.448 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes]449 (d) Did you discuss whether and how consent was obtained from people whose data you’re450 using/curating? [Yes] Details can be found in the online dataset repositories [8, 20].451 (e) Did you discuss whether the data you are using/curating contains personally identifiable452 information or offensive content? [Yes] Details can be found in the online dataset453 repositories [8, 20].454
5. If you used crowdsourcing or conducted research with human subjects...455 (a) Did you include the full text of instructions given to participants and screenshots, if456 applicable? [N/A]457 (b) Did you describe any potential participant risks, with links to Institutional Review458 Board (IRB) approvals, if applicable? [N/A]459 (c) Did you include the estimated hourly wage paid to participants and the total amount460 spent on participant compensation? [N/A]461

Review summaries:
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.  First, 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.   Second, 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.   Third, 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$. 

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.