Year: 2019

Abstract:
This paper studies the lower bound complexity for the optimization problem whose objective function is the average of n individual smooth convex functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex case, we prove such an algorithm can not reach an ε-suboptimal point in fewer than Ω((n + √ κn) log(1/ε)) iterations, where κ is the condition number of the objective function. This lower bound is tighter than previous results and perfectly matches the upper bound of the existing proximal incremental first-order oracle algorithm Point-SAGA. We develop a novel construction to show the above result, which partitions the tridiagonal matrix of classical examples into n groups to make the problem difficult enough to stochastic algorithms. This construction is friendly to the analysis of proximal oracle and also could be used in general convex and average smooth cases naturally.

√ κn) log(1/ε))
iterations, where κ is the condition number of the objective function. This lower bound is tighter than previous results and perfectly matches the upper bound of the existing proximal incremental first-order oracle algorithm Point-SAGA. We develop a novel construction to show the above result, which partitions the tridiagonal matrix of classical examples into n groups to make the problem difficult enough to stochastic algorithms. This construction is friendly to the analysis of proximal oracle and also could be used in general convex and average smooth cases naturally.
1 INTRODUCTION
We consider the minimization of the following optimization problem
min x∈Rd
f(x) , 1
n n∑ i=1 fi(x), (1)
where the fi(x) are L-smooth and µ-strongly convex. Accordingly, the condition number is defined as κ = L/µ, which is typically larger than n in real-world applications. Many machine learning models can be formulated as the above problem such as ridge linear regression, ridge logistic regression, smoothed support vector machines, graphical models, etc. This paper focuses on the first order methods for solving Problem (1), which access to the Proximal Incremental First-order Oracle (PIFO) for each individual component, that is,
hf (x, i, γ) , [ fi(x),∇fi(x),proxγfi(x) ] , (2)
where i ∈ {1, . . . , n}, γ > 0, and the proximal operation is defined as
proxγfi(x) = arg min u
{ fi(u) + 1
2γ ‖x− u‖22
} .
We also define the Incremental First-order Oracle (IFO)
gf (x, i, γ) , [fi(x),∇fi(x)] .
PIFO provides more information than IFO and it would be potentially more powerful than IFO in first order optimization algorithms. Our goal is to find an ε-suboptimal solution x̂ such that
f(x̂)− min x∈Rd f(x) ≤ ε
by using PIFO or IFO.
There are several first-order stochastic algorithms to solve Problem (1). The key idea to leverage the structure of f is variance reduction which is effective for ill-conditioned problems. For example, SVRG (Zhang et al., 2013; Johnson and Zhang, 2013; Xiao and Zhang, 2014) can
find an ε-suboptimal solution in O((n+κ) log(1/ε)) IFO calls, while the complexity of the classical Nesterov’s acceleration (Nesterov, 1983) is O(n √ κ log(1/ε)). Similar results1 also hold for SAG (Schmidt et al., 2017) and SAGA (Defazio et al., 2014). In fact, there exists an accelerated stochastic gradient method with √ κ dependency. Defazio (2016) introduced a simple and practical accelerated method called Point SAGA, which reduces the iteration complexity to O((n + √ κn) log(1/ε)). The advantage of Point SAGA is in that it has only one parameter to be tuned, but the iteration depends on PIFO rather than IFO. Allen-Zhu (2017) proposed the Katyusha momentum to accelerate variance reduction algorithms, which achieves the same iteration complexity as Point-SAGA but only requires IFO calls.
The lower bound complexities of IFO algorithms for convex optimization have been well studied (Agarwal and Bottou, 2015; Arjevani and Shamir, 2015; Woodworth and Srebro, 2016; Carmon et al., 2017; Lan and Zhou, 2017; Zhou and Gu, 2019). Specifically, Lan and Zhou (2017) showed that at least Ω((n+ √ κn) log(1/ε)) IFO calls2 are needed to obtain an ε-suboptimal solution for some complicated objective functions. This lower bound is optimal because it matches the upper bound complexity of Katyusha (Allen-Zhu, 2017).
It would be interesting whether we can establish a more efficient PIFO algorithm than IFO one. Woodworth and Srebro (2016) provided a lower bound Ω(n+ √ κn log(1/ε)) for PIFO algorithms, while the known upper bound of the PIFO algorithm Point SAGA [3] is O((n+ √ κn) log(1/ε)). The difference of dependency on n implies that the existing theory of PIFO algorithm is not perfect. This gap can not be ignored because the number of components n is typically very large in many machine learning problems. A natural question is can we design a PIFO algorithm whose upper bound complexity matches Woodworth and Srebro’s lower bound, or can we improve the lower bound complexity of PIFO to match the upper bound of Point SAGA. In this paper, we prove the lower bound complexity of PIFO algorithm is Ω((n+ √ κn) log(1/ε)) for smooth and strongly-convex fi, which means the existing Point-SAGA (Defazio, 2016) has achieved optimal complexity and PIFO can not lead to a tighter upper bound than IFO. We provide a novel construction, showing the above result by decomposing the classical tridiagonal matrix (Nesterov, 2013) into n groups. This technique is quite different from the previous lower bound complexity analysis (Agarwal and Bottou, 2015; Woodworth and Srebro, 2016; Lan and Zhou, 2017; Zhou and Gu, 2019). Moreover, it is very friendly to the analysis of proximal operation and easy to follow. We also use this technique to study general convex and average smooth cases (Allen-Zhu, 2018; Zhou and Gu, 2019), and extend our result to non-convex problems (see Appendix J).
2 OUR ANALYSIS FRAMEWORK
In this paper, we consider the Proximal Incremental First-order Oracle (PIFO) algorithm for smooth convex finite-sum optimization. All proofs in this section can be found in Appendices C and D for a detailed version. We analyze the lower bounds of the algorithms when the objective functions are respectively strongly convex, general convex, smooth and average smooth (Zhou and Gu, 2019).
Definition 2.1. For any differentiable function f : Rm → R,
• f is convex, if for any x,y ∈ Rm it satisfies f(y) ≥ f(x) + 〈∇f(x),y − x〉.
• f is µ-strongly convex, if for any x,y ∈ Rm it satisfies
f(y) ≥ f(x) + 〈∇f(x),y − x〉+ µ 2 ‖x− y‖22.
• f is L-smooth, if for any x,y ∈ Rm it satisfies ‖∇f(x)−∇f(y)‖2 ≤ L‖x− y‖2.
1SVRG, SAG and SAGA only need to introduce the proximal operation for composite objective, that is, fi(x) = gi(x) + h(x), where h may be non-smooth. Their iterations only depend on IFO when all the fi(x) are smooth. Hence, we regard these algorithms only require IFO calls in this paper.
2Lan and Zhou’s construction requires f to be µ-strongly convex and every fi to be convex, while this paper studies the lower bound with stronger condition that is every fi is µ-strongly convex. For the same lower bound complexity, the result with stronger assumptions on the objective functions is stronger.
Definition 2.2. We say differentiable functions {fi}ni=1, fi : Rm → R, to be L-average smooth if for any x,y ∈ Rm, they satisfy
1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖22 ≤ L 2 ‖x− y‖22 . (3)
Remark 2.3. We point out that
1. if each fi is L-smooth, then {fi}ni=1 are L-average smooth. 2. if {fi}ni=1 are L-average smooth, then f(x) = 1n ∑n i=1 fi(x) is L-smooth.
We present the formal definition for PIFO algorithm. Definition 2.4. Consider a stochastic optimization algorithm A to solve Problem (1). Let xt be the point obtained at time-step t and the algorithm starts with x0. The algorithmA is said to be a PIFO algorithm if for any t ≥ 0, we have
xt ∈ span { x0, . . . ,xt−1,∇fi1(x0), · · · ,∇fit(xt−1),prox
γ1 fi1 (x0), · · · ,proxγtfit (xt−1) } , (4)
where it is a random variable supported on [n] and takes P(it = j) = pj for each t ≥ 0 and 1 ≤ j ≤ n where ∑n j=1 pj = 1.
Without loss of generality, we assume x0 = 0 and p1 ≤ p2 ≤ · · · ≤ pn to simplify our analysis. Otherwise, we can take {f̂i(x) = fi(x + x0)}ni=1 into consideration. On the other hand, suppose that ps1 ≤ ps2 ≤ · · · ≤ psn where {si}ni=1 is a permutation of [n]. Define {f̃i}ni=1 such that f̃si = fi, then A takes component f̃si in probability psi , i.e., A takes fi in probability psi .
To demonstrate the construction of adversarial functions, we first introduce the following class of matrices:
B(m,ω) =  −1 1 −1 1 . . . . . .
−1 1 ω  ∈ Rm×m. Then we define
A(m,ω) , B(m,ω)>B(m,ω) =  ω2 + 1 −1 −1 2 −1 . . . . . . −1 2 −1
−1 1  . (5) The matrix A(m,ω) is widely-used in the analysis of lower bounds for convex optimization (Nesterov, 2013; Agarwal and Bottou, 2015; Lan and Zhou, 2017; Carmon et al., 2017; Zhou and Gu, 2019). We now present a decomposition of A(m,ω) based on Eq. (5). Denote the l-th row of the matrix B(m,ω) by bl(m,ω)> and let
Li = { l : 1 ≤ l ≤ m, l ≡ i− 1(mod n) } , i = 1, 2, · · · , n.
Our construction is based on the following class of functions
r(x;λ0, λ1, λ2,m, ω) , 1
n n∑ i=1 ri(x;λ0, λ1, λ2,m, ω),
where
ri(x;λ0, λ1, λ2,m, ω) =  λ1 ∑ l∈L1 ∥∥bl(m,ω)>x∥∥22 + λ2 ‖x‖22 − λ0〈em,x〉, for i = 1, λ1 ∑ l∈Li
∥∥bl(m,ω)>x∥∥22 + λ2 ‖x‖22 , for i = 2, 3, · · · , n. (6) We can determine the smooth and strongly-convex coefficients of ri as follows. Proposition 2.5. For any λ1 > 0, λ2 ≥ 0, ω < √ 2, we have that the ri are (4λ1 + 2λ2)-smooth and λ2-strongly convex, and {ri}ni=1 is L′-average smooth where
L′ = 2
√ 4
n [(λ1 + λ2)2 + λ21] + λ 2 2.
We define the subspaces {Fk}mk=0 as Fk = {
span{em, em−1, · · · , em−k+1}, for 1 ≤ k ≤ m, {0}, for k = 0.
The following technical lemma plays a crucial role in our proof. Lemma 2.6. For any λ0 6= 0, λ1 > 0, λ2 ≥ 0 and x ∈ Fk, 0 ≤ k < m, we have that
∇ri(x;λ0, λ1, λ2,m, ω) and proxγri(x) ∈ { Fk+1, if k ≡ i− 1(mod n), Fk, otherwise.
In short, if x ∈ Fk and let fi(x) , ri(x;λ0, λ1, λ2, ω), then there exists only one i ∈ {1, . . . , n} such that hf (x, i, γ) could (and only could) provide additional information in Fk+1. The “only one” property is important to the lower bound analysis for first order stochastic optimization algorithms (Lan and Zhou, 2017; Zhou and Gu, 2019), but these prior constructions only work for IFO rather than PIFO.
Lemma 2.6 implies that xt = 0 will host until algorithm A draws the component f1. Then, for any t < T1 = mint{t : it = 1}, we have xt ∈ F0 and xT1 ∈ F1. The value of T1 can be regarded as the smallest integer such that xT1 could host. Similarly, we can define Tk to be the smallest integer such that xTk ∈ Fk could host. We give the formal definition of Tk recursively and connect it to geometrically distributed random variables in the following corollary.
Corollary 2.7. Let T0 = 0, and Tk = min
t {t : t > Tk−1, it ≡ k (mod n)} for k ≥ 1. (7)
Then for any k ≥ 1 and t < Tk, we have xt ∈ Fk−1. Moreover, Tk can be written as sum of k independent random variables {Yl}1≤l≤k, i.e., Tk = ∑k l=1 Yl, where Yl follows a geometric distribution with success probability ql = pl′ where l′ ≡ l (mod n), 1 ≤ l′ ≤ n.
The basic idea of our analysis is that we guarantee the minimizer of r lies in Fm and assure the PIFO algorithm extend the space of span{x0,x1, . . . ,xt} slowly with t increasing. We know that span{x0,x1, . . . ,xTk} ⊆ Fk by Corollary 2.7. Hence, Tk is just the quantity that reflects how span{x0,x1, . . . ,xt} verifies. Because Tk can be written as the sum of geometrically distributed random variables, we needs to introduce some properties of such random variables which derive the lower bounds of our construction. Lemma 2.8. Let {Yi}1≤i≤N be independent random variables, and Yi follows a geometric distribution with success probability pi. Then
P ( N∑ i=1 Yi > N2 4( ∑N i=1 pi) ) ≥ 1− 16 9N . (8)
From Lemma 2.8, the following result implies how many PIFO calls we need. Lemma 2.9. If M ≥ 1 satisfies minx∈FM f(x) − minx∈Rm f(x) ≥ 9ε and N = n(M + 1)/4, then we have
min t≤N Ef(xt)− min x∈Rm f(x) ≥ ε.
3 MAIN RESULTS
We present the our lower bound results for PIFO algorithms and summarize all of results in Table 1 and 2 . We first start with smooth and strongly convex setting, then consider the general convex and average smooth cases. Theorem 3.1. For any PIFO algorithm A and any L, µ, n,∆, ε such that κ = L/µ ≥ 2, and ε/∆ ≤ 0.5, there exist a dimension d = O ( 1 + √ κ/n log (∆/ε) ) and n L-smooth and µ-strongly convex functions {fi : Rd → R}ni=1 such that f(x0) − f(x∗) = ∆. In order to find x̂ ∈ Rd such that Ef(x̂)− f(x∗) < ε, A needs at least N queries to hf , where
N =
{ Ω ((n+ √ κn) log (∆/ε)) , for n = O(κ),
Ω ( n+ ( n
1+(log(n/κ))+
) log (∆/ε) ) , for κ = O(n).
Remark 3.2. In fact, the lower bound in Theorem 3.1 perfectly match the upper bound of the PIFO algorithm Point SAGA (Defazio, 2016) 3 in n = O(κ) case and match the the upper bound of the IFO algorithm4 prox-SVRG (Hannah et al., 2018) in κ = O(n) case. Hence, the lower bound in Theorem 3.1 is tight, while Woodworth and Srebro (2016) only provided lower bound Ω (n+ √ κn log (1/ε)) in n = O(κ) case. The theorem also shows that the PIFO algorithm can not be more powerful than the IFO algorithm in the worst case, because Hannah et al. (2018) proposed a same lower bound for IFO algorithms.
Next we give the lower bound when the objective function is not strongly-convex. Theorem 3.3. For any PIFO algorithm A and any L, n,B, ε such that ε ≤ LB2/4, there exist a dimension d = O ( 1 +B √ L/(nε) ) and n L-smooth and convex functions {fi : Rd → R}ni=1 such that ‖x0 − x∗‖2 ≤ B. In order to find x̂ ∈ Rd such that Ef(x̂)−f(x∗) < ε,A needs at least Ω ( n+B √ nL/ε ) queries to hf .
3Defazio (2016) proves Point SAGA requires O ((n+ √ κn) log (1/ε)) PIFO calls to find x̂ such that E‖x̂ − x∗‖22 < ε‖x0 − x∗‖22, which is not identical to the condition Ef(x̂) − f(x∗) < ε in Theorem 3.1. However, it is unnecessary to worry about it because we also establish a PIFO lower bound Ω ((n+ √ κn) log (1/ε)) for E‖x̂− x∗‖22 < ε‖x0 − x∗‖22 in Theorem F.1.
4IFO algorithm is apparently also a PIFO algorithm.
Remark 3.4. The lower bound in Theorem 3.3 is the same as the one of Woodworth and Srebro’s result. However, our construction only requires the dimension be O ( 1 +B √ L/(nε) ) , which is
much smaller than O ( L2B4 ε2 log ( nLB2 ε )) in (Woodworth and Srebro, 2016).
Then we extend our results to the weaker assumption: that is, the objective function F is L-average smooth (Zhou and Gu, 2019). We start with the case that F is strongly convex. Theorem 3.5. For any PIFO algorithm A and any L, µ, n,∆, ε such that κ = L/µ ≥√ 3/n ( n 2 + 1 ) , and ε/∆ ≤ 0.00327, there exist a dimension d = O ( n−1/4 √ κ log (∆/ε) ) and n functions {fi : Rd → R}ni=1 where the {fi}ni=1 are L-average smooth and f is µ-strongly convex, such that f(x0)− f(x∗) = ∆. In order to find x̂ ∈ Rd such that Ef(x̂)− f(x∗) < ε, A needs at least Ω (( n+n3/4 √ κ ) log (∆/ε) )
queries to hf . Remark 3.6. Compared with Zhou and Gu’s lower bound Ω ( n+ n3/4 √ κ log (∆/ε) ) for IFO algorithms, Theorem 3.5 shows tighter dependency on n and supports PIFO algorithms additionally.
We also give the lower bound for general convex case under the L-average smooth condition. Theorem 3.7. For any PIFO algorithm A and any L, n,B, ε such that ε ≤ LB2/4, there exist a dimension d = O ( 1 +Bn−1/4 √ L/ε ) and n functions {fi : Rd → R}ni=1 which the {fi}ni=1 are L-average smooth and f is convex, such that ‖x0 − x∗‖2 ≤ B. In order to find x̂ ∈ Rd such that Ef(x̂)− f(x∗) < ε, A needs at least Ω ( n+Bn3/4 √ L/ε ) queries to hf .
Remark 3.8. The lower bound in Theorem 3.7 is comparable to the one of Zhou and Gu’s result, but our construction only requires the dimension beO ( 1 +Bn−1/4 √ L/ε ) , which is much smaller
than O ( n+Bn3/4 √ L/ε ) in (Zhou and Gu, 2019).
4 CONSTRUCTIONS IN PROOF OF MAIN THEOREMS
We demonstrate the detailed constructions for PIFO lower bounds in this section. All the omitted proof in this section can be found in Appendix for a detailed version.
4.1 STRONGLY CONVEX CASE
The analysis of lower bound complexity for the strongly-convex case depends on the following construction.
Definition 4.1. For fixed L, µ,∆, n, let α = √
2(L/µ−1) n + 1. We define fSC,i : R m → R as follows
fSC,i(x) = ri
( x; √ 2(L− µ)n∆
α− 1 , L− µ 4 , µ 2 ,m,
√ 2
α+ 1
) , for 1 ≤ i ≤ n, (9)
and
FSC(x) , 1
n n∑ i=1 fSC,i(x) = L− µ 4n ∥∥∥∥∥B ( m, √ 2 α+ 1 ) x ∥∥∥∥∥ 2
2
+ µ
2 ‖x‖22 − √ 2(L− µ)∆ n(α− 1) 〈em,x〉.
Note that the fSC,i are L-smooth and µ-strongly convex, and FSC(x0)− FSC(x∗) = ∆ (see Proposition E.1 in Appendix for more details). Next we show that the functions {fSC,i}ni=1 are “hard enough” for any PIFO algorithm A, and deduce the conclusion of Theorem 3.1. Theorem 4.2. Suppose that
ε ≤ ∆ 9 ( α− 1 α+ 1 )2 , and m = 1 4 (√ 2 L/µ− 1 n + 1 ) log ( ∆ 9ε ) + 1,
where α = √
2(L/µ−1) n + 1. In order to find x̂ ∈ R m such that EFSC(x̂) − FSC(x∗) < ε, PIFO algorithm A needs at least N queries to hFSC . where
N = Ω (( n+ √ nL µ ) log ( ∆ 9ε )) , for Lµ ≥ n 2 + 1, Ω ( n+ ( n
1+log(nµ/L)
) log (
∆ 9ε )) , for 2 ≤ Lµ < n 2 + 1.
For larger ε, we can apply following Lemma.
Lemma 4.3. For any PIFO algorithm A and any L, µ, n,∆, ε such that ε ≤ ∆/2, there exist n L-smooth and µ-strongly convex functions {fi : R → R}ni=1 such that F (x0) − F (x∗) ≤ ∆. In order to find x̂ ∈ R such that EF (x̂)− F (x∗) < ε, A needs at least Ω(n) queries to hF .
As we explain in Remark H.1, the lower bound in Lemma 4.3 is same as the lower bound in Theorem 4.2 for ε > ∆9 ( α−1 α+1 )2 . In conclusion, we obtain Theorem 3.1.
4.2 CONVEX CASE
The analysis of lower bound complexity for non strongly-convex cases depends on the following construction. Definition 4.4. For fixed L,B, n, we define fC,i : Rm → R as follows
fC,i(x) = ri
( x; √ 3
2
BL (m+ 1)3/2 , L 4 , 0,m, 1
) (10)
and
FC(x) , 1
n n∑ i=1 fC,i(x) = L 4n ‖B(m, 1)x‖22 − √ 3 2
BL
(m+ 1)3/2n 〈em,x〉.
Note that the fC,i are L-smooth and convex, and ‖x0 − x∗‖2 ≤ B (see Proposition G.1 in Appendix for more details). Next we show the lower bound for functions fC,i defined above. Theorem 4.5. Suppose that
ε ≤ B 2L
384n and m =
⌊√ B2L
24nε
⌋ − 1.
In order to find x̂ ∈ Rm such that EFC(x̂)−FC(x∗) < ε,A needs at least Ω ( n+B √ nL ε ) queries to hFC .
To derive Theorem 3.3, we also need the following lemma in the case ε > B 2L
384n .
Lemma 4.6. For any PIFO algorithm A and any L, n,B, ε such that ε ≤ LB2/4, there exist n L-smooth and convex functions {fi : R → R}ni=1 such that |x0 − x∗| ≤ B. In order to find x̂ ∈ R such that EF (x̂)− F (x∗) < ε, A needs at least Ω(n) queries to hF .
It is worth noting that if ε > B 2L 384n , then Ω(n) = Ω ( n+B √ nL ε ) . Thus combining Theorem 4.5 and Lemma 4.6, we obtain Theorem 3.3.
4.3 AVERAGE SMOOTH CASE
Zhou and Gu (2019) established lower bounds of IFO complexity under the average smooth assumption. Here we demonstrate that our technique can also develop lower bounds of PIFO algorithm under this assumption.
4.3.1 F IS STRONGLY CONVEX For fixed L′, µ,∆, n, ε, we set L = √
n(L′2−µ2) 2 − µ2, and consider {fSC,i} n i=1 and FSC defined in
Definition 4.1. Proposition 4.7. For n ≥ 2, we have that
1. FSC(x) is µ-strongly convex and {fSC,i}ni=1 is L′-average smooth.
2. If L ′ µ ≥ √ 3 n ( n 2 + 1), then we have √ n 3L ′ ≤ L ≤ √ n 2L ′ and L/µ ≥ n/2 + 1.
Theorem 4.8. Suppose that
L′ µ ≥ √ 3 n (n 2 + 1 ) , ε ≤ ∆ 9 (√ 2− 1√ 2 + 1 )2 , and m = 1 4 √√ 2 n L′ µ + 1  log(∆ 9ε ) + 1.
In order to find x̂ ∈ Rm such that EFSC(x̂) − FSC(x∗) < ε, PIFO algorithm A needs at least Ω (( n+ n3/4 √ L′
µ
) log (
∆ ε )) queries to hFSC .
4.3.2 F IS CONVEX For fixed L′, B, n, ε, we set L = √
n 2L ′, and consider {fC,i}ni=1 and FC defined in Definition 4.4.
It follows from Proposition 2.5 that {fC,i}ni=1 is L′-average smooth. Theorem 4.9. Suppose that
ε ≤ √ 2
768 B2L′√ n and m =
⌊ 4 √
18
12 Bn−1/4
√ L′
ε
⌋ − 1.
In order to find x̂ ∈ Rm such that EFC(x̂) − FC(x∗) < ε, A needs at least Ω ( n+Bn3/4 √ L′
ε ) queries to hFC . Similar to Lemma 4.6, we also need the following lemma for the case ε > √
2 768 B2L′√ n .
Lemma 4.10. For any PIFO algorithm A and any L, n,B, ε such that ε ≤ LB2/4, there exist n functions {fi : R→ R}ni=1 which is L-average smooth, such that F (x) is convex and ‖x0−x∗‖2 ≤ B. In order to find x̂ ∈ R such that EF (x̂)− F (x∗) < ε, A needs at least Ω(n) queries to hF .
Similarly, note that if ε > √
2 768 B2L′√ n
, then Ω(n) = Ω ( n+Bn3/4 √ L′
ε
) . In summary, we obtain
Theorem 3.7.
5 CONCLUSION AND FUTURE WORK
In this paper we have studied lower bound of PIFO algorithm for smooth convex finite-sum optimization. We have given a tight lower bound of PIFO algorithms in the strongly convex case. We have proposed a novel construction framework that is very useful to the analysis of proximal algorithms. Based on this framework, we can extended our result to non-strongly convex, average smooth and non-convex problems easily (Appendix J). It would be interesting to prove tight lower bounds in more general setting, such as F is of (σ, L)-smoothness while each fi is (l, L)-smoothness.
REFERENCES
Alekh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In ICML, 2015.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(1):8194–8244, 2017.
Zeyuan Allen-Zhu. Katyusha X: Practical momentum method for stochastic sum-of-nonconvex optimization. In ICML, 2018.
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In NIPS, 2015.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. arXiv preprint arXiv:1710.11606, 2017.
Aaron Defazio. A simple practical accelerated method for finite sums. In NIPS, 2016.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In NIPS, 2014.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In NIPS, 2018.
Robert Hannah, Yanli Liu, Daniel O’Connor, and Wotao Yin. Breaking the span assumption yields fast finite-sum minimization. In Advances in Neural Information Processing Systems, pages 2312–2321, 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.
Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. Mathematical programming, pages 1–49, 2017.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/kˆ2). In Dokl. akad. nauk Sssr, volume 269, pages 543–547, 1983.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83–112, 2017.
Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. In NIPS, 2016.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057–2075, 2014.
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent access of full gradients. In NIPS, 2013.
Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. In ICML, 2019.
A COMPARISON OF REQUIRED NUMBER OF DIMENSIONS
B COMPARISON WITH EXISTING PROOFS
Recall the adversary function we used is (please see detailed defintion in Section 2)
r(x;λ0, λ1, λ2,m, ω) , 1
n n∑ i=1 ri(x;λ0, λ1, λ2,m, ω) (11)
= λ1 n x>A(m,ω)x + λ2 ‖x‖22 − λ0 n 〈em,x〉, (12)
where
ri(x;λ0, λ1, λ2,m, ω) =  λ1 ∑ l∈L1 ∥∥bl(m,ω)>x∥∥22 + λ2 ‖x‖22 − λ0〈em,x〉, for i = 1, λ1 ∑ l∈Li
∥∥bl(m,ω)>x∥∥22 + λ2 ‖x‖22 , for i = 2, 3, . . . , n. The constructions in previous work (Lan and Zhou, 2017; Zhou and Gu, 2019) for IFO algorithms employ an aggregation of r , that is,
f(x) , 1
n n∑ i=1 fi(x), where fi(x) = nr(xi),
x =  x1 x2 ... xn  ∈ Rmn, and xi ∈ Rm for i = 1, . . . , n.
The disadvantage of their construction is in that the important property from Lemma 2.6, which we can obtain information of only one extra dimension at each PIFO query, cannot be held. Note that the framework in this paper is the first lower bound analysis that utilize the decomposition form (11), which makes the “only one” property also hold for PIFO query. The previous works only consider the presentation (12) and are unaware of the decomposition (11). Moreover, the fact r : Rm → R and f : Rmn → R provide an intuitive understanding why our construction requires a smaller dimension (see Table 2).
The analysis in (Woodworth and Srebro, 2016; Fang et al., 2018) considers a very complicated approach to dealing with the proximal operator (completely different from how to deal with gradient operator). In contrast, our construction holds “only one” property (Lemma 2.6) both for proximal and gradient operator, which leads the proof is more concise. Our construction more clearly shows that PIFO algorithms are not more powerful than IFO algorithms in the sense of lower complexity bound. We also use our technique to prove the tight lower bound of PIFO algorithm when κ = O(n), which is a new result.
C DETAILED PROOF FOR SECTION 2
In this section, we use ‖A‖ to denote the spectral radius of A. For simplicity, let
B = B(m,ω) =  −1 1 −1 1 . . . . . .
−1 1 ω  ∈ Rm×m, b>l is the l-th row of B, and fi(x) = ri(x;λ0, λ1, λ2,m, ω). Recall that Li = {l : 1 ≤ l ≤ m, l ≡ i− 1(modn)}, i = 1, 2, · · · , n. For 1 ≤ i ≤ n, let Bi be a submatrix which is formed from rows Li of B, that is Bi = B[Li; ]
Then fi can be wriiten as
fi(x) = λ1 ‖Bix‖22 + λ2 ‖x‖ 2 2 − ηi〈em,x〉,
where η1 = λ0, ηi = 0, i ≥ 2.
Proof of Proposition 2.5. Note that
〈u,B>i Biu〉 = ‖Biu‖ 2 2 = ∑ l∈Li (b>l u) 2
=
{∑ l∈Li\{m}(um−l − um−l+1)
2 + ω2u2m (if m ∈ Li)∑ l∈Li(um−l − um−l+1) 2
≤ 2 ‖u‖22 ,
where the last inequality is according to (x+y)2 ≤ 2(x2 +y2), and |l1− l2| ≥ n ≥ 2 for l1, l2 ∈ Li. Hence, ∥∥B>i Bi∥∥ ≤ 2, and∥∥∇2fi(x)∥∥ = ∥∥2λ1B>i Bi + 2λ2I∥∥ ≤ 4λ1 + 2λ2. Next, observe that
‖∇fi(x)−∇fi(y)‖22 = ∥∥(2λ1B>i Bi + 2λ2I)(x− y)∥∥22
Let u = x− y. Note that
blb > l u = { (um−l − um−l+1)(em−l − em−l+1), l < m, ω2u1e1, l = m.
Thus, if m /∈ Li, then∥∥(2λ1B>i Bi + 2λ2I)u∥∥22 =
∥∥∥∥∥2λ1 ∑ l∈Li (um−l − um−l+1)(em−l − em−l+1) + 2λ2u ∥∥∥∥∥ 2
2 = ∑
m−l∈Li
[ (2λ1(ul − ul+1) + 2λ2ul)2 + (−2λ1(ul − ul+1) + 2λ2ul+1)2 ] + ∑ m−l/∈Li m−l+1/∈Li (2λ2ul) 2
≤ ∑
m−l∈Li
8 [ (λ1 + λ2) 2 + λ21 ] (u2l + u 2 l+1) + 4λ 2 2 ‖u‖ 2 2 .
Similarly, if m ∈ Li, then
∥∥(2λ1B>i Bi + 2λ2I)u∥∥22 ≤
∑ m−l∈Li l 6=0 8 [ (λ1 + λ2) 2 + λ21 ] (u2l + u 2 l+1) + 4(λ1ω 2 + λ2) 2u21 + 4λ 2 2 ‖u‖ 2 2 .
Therefore, we have
1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖22
≤ 1 n [ m−1∑ l=1 8 [ (λ1 + λ2) 2 + λ21 ] (u2l + u 2 l+1) + 4(2λ1 + λ2) 2u21 ] + 4λ22 ‖u‖ 2 2 ≤ 16 n [ (λ1 + λ2) 2 + λ21 ] ‖u‖22 + 4λ 2 2 ‖u‖ 2 2 ,
where we have used (2λ1 + λ2)2 ≤ 2 [ (λ1 + λ2) 2 + λ21 ] . In summary, we get that {fi}1≤i≤n is L′-average smooth, where
L′ = 2
√ 4
n [(λ1 + λ2)2 + λ21] + λ 2 2.
Proof of Lemma 2.6. For x ∈ Fk (k ≥ 1), we have
b>l x = 0 for l > k, bl ∈ Fk for l < k, bk ∈ Fk+1.
Consequently, for l 6= k, blb>l x = (b>l x)bl ∈ Fk, and bkb>k x ∈ Fk+1. For k = 0, we have x = 0, and
∇f1(x) = λ0em ∈ F1, ∇fj(x) = 0 (j ≥ 2).
Moreover, we suppose k ≥ 1, k ∈ Li. Since ∇fj(x) = 2λ1B>j Bjx + 2λ2x− ηjem
= 2λ1 ∑ l∈Lj b>l blx + 2λ2x− ηjem.
Hence, ∇fi(x) ∈ Fk+1 and ∇fj(x) ∈ Fk (j 6= i).
Now, we turn to consider u = proxγfj (x). We have( 2λ1B > j Bj + ( 2λ2 + 1
γ
) I ) u = ηjem + 1
γ x,
i.e.,
u = c1(I + c2B > j Bj) −1y,
where c1 = 12λ2+1/γ , c2 = 2λ1 2λ2+1/γ , and y = ηjem + 1γx. Note that
(I + c2B > j Bj) −1 = I −B>j ( 1
c2 I + BjB
> j )−1 Bj .
If k = 0 and j > 1, we have y = 0 and u = 0. If k = 0 and j = 1, we have y = λ0em. On this case, B1em = 0, so u = c1y ∈ F1. For k ≥ 1, we know that y ∈ Fk. And observe that if |l − l′| ≥ 2, then b>l bl′ = 0, and consequently BjB>j is a diagonal matrix, so we can assume that 1 c2 I+BjB > j = diag(βj,1, · · · , βj,|Lj |). Therefore,
u = c1y − c1 |Lj |∑ s=1 βj,sblj,sb > lj,sy,
where we assume that Lj = {lj,1, · · · , lj,|Lj |}. Thus, we have proxγfi(x) ∈ Fk+1 for k ∈ Li and prox γ fj (x) ∈ Fk (j 6= i).
Proof of Corollary 2.7. Denote span{∇fi1(x0), · · · ,∇fit(xt−1),prox
γ1 fi1 (x0), · · · ,proxγtfit (xt−1)}
byMt. We know that xt ∈Mt. Suppose thatMT ⊆ Fk−1 for some T and let T ′ = arg min t : t > T, it ≡ k(mod n). By Lemma 2.6, for T < t < T ′, we can use a simple induction to obtain that
span{∇fit(xt−1),prox γt fit (xt−1)} ⊆ Fk−1 andMt ⊆ Fk−1. Moreover, since iT ′ ≡ k(mod n), we have
span{∇fiT ′ (xT ′−1),prox γT ′ fi T ′ (xT ′−1)} ⊆ Fk andMT ′ ⊆ Fk. Following from above statement, it is easily to check that for t < Tk, we have xt ∈Mt ⊆ Fk−1. Next, note that
P (Tk − Tk−1 = s) = P ( iTk−1+1 6≡ k(mod n), · · · , iTk−1+s−1 6≡ k(mod n), iTk−1+s ≡ k(mod n) ) = P ( iTk−1+1 6= k′, · · · , iTk−1+s−1 6= k′, iTk−1+s = k′
) = (1− pk′)s−1pk′ ,
where k′ ≡ k(mod n), 1 ≤ k′ ≤ n. So Tk − Tk−1 is a geometric random variable with success probability pk′ . On the other hand, Tk − Tk−1 is just dependent on iTk−1+1, · · · , iTk , thus for l 6= k, Tl − Tl−1 is independent with Tk − Tk−1. Therefore,
Tk = k∑ l=1 (Tl − Tl−1) = k∑ i=1 Yl,
where Yl follows a geometric distribution with success probability ql = pl′ where l′ ≡ l(mod n), 1 ≤ l′ ≤ n.
Proof of Remark 2.3. If each fi is L-smooth, then for any x,y ∈ Rm we have
‖∇fi(x)−∇fi(y)‖22 ≤ L 2 ‖x− y‖22 ,
and consequently,
1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖22 ≤ L 2 ‖x− y‖22 . (13)
If {fi}ni=1 is L-average smooth, then for any x,y ∈ Rm we have
‖∇f(x)−∇f(y)‖22 = 1
n2 ∥∥∥∥∥ n∑ i=1 (∇fi(x)−∇fi(y)) ∥∥∥∥∥ 2
2
≤ 1 n2 ( n∑ i=1 ‖∇fi(x)−∇fi(y)‖2 )2
≤ 1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖22 ≤ L2 ‖x− y‖22 .
Proof of Lemma 2.9. Denote minx∈Rm f(x) by f∗. For t ≤ N , we have Ef(xt)− f∗ ≥ E[f(xt)− f∗|N < TM+1]P (N < TM+1)
≥ E[ min x∈FM f(x)− f∗|N < TM+1]P (N < TM+1)
≥ 9εP (TM+1 > N) , where TM+1 is defined in (7), and the second inequality follows from Corollary 2.7 (if N < TM+1, then xt ∈ FM for t ≤ N ).
By Corollary 2.7, TM+1 can be written as TM+1 = ∑M+1 l=1 Yl, where {Yl}1≤l≤M+1 are independent random variables, and Yl follows a geometric distribution with success probability ql = pl′ (l′ ≡ l(mod n), 1 ≤ l′ ≤ n). Moreover, recalling that p1 ≤ p2 ≤ · · · ≤ pn, we have ∑M+1 l=1 ql ≤ M+1 n . Therefore, by Lemma 2.8, we have
P (TM+1 > N) = P ( M+1∑ l=1 Yl > (M + 1)n 4 ) ≥ 1− 16 9(M + 1) ≥ 1 9 ,
Hence, we can conclude that Ef(xN )− f∗ ≥ 9εP (TM+1 > N) ≥ ε.
Remark In fact, a more strong conclusion hosts: E [ min t≤N f(xt) ] − min x∈Rm f(x) ≥ ε.
D RESULTS ABOUT SUM OF GEOMETRIC DISTRIBUTED RANDOM VARIABLES
Lemma D.1. Let X1 ∼ Geo(p1), X2 ∼ Geo(p2) be independent random variables. For any positive integer j, if p1 6= p2, then
P (X1 +X2 > j) = p2(1− p1)j − p1(1− p2)j
p2 − p1 , (14)
and if p1 = p2, then
P (X1 +X2 > j) = jp1(1− p1)j−1 + (1− p1)j . (15)
Proof.
P (X1 +X2 > j) = j∑ l=1 P (X1 = l)P (X2 > j − l) + P (X1 > j)
= j∑ l=1 (1− p1)l−1p1(1− p2)j−l + (1− p1)j
= p1(1− p2)j−1 j∑ l=1 ( 1− p1 1− p2 )l−1 + (1− p1)j
Thus if p1 = p2, P (X1 +X2 > j) = jp1(1− p1)j−1 + (1− p1)j . For p1 6= p2,
P (X1 +X2 > j) = p1 (1− p1)j − (1− p2)j
p2 − p1 + (1− p1)j
= p2(1− p1)j − p1(1− p2)j
p2 − p1 .
Lemma D.2. For x ≥ 0 and j ≥ 2,
1− j − 1 x+ j/2
≤ ( x
x+ 1
)j−1 . (16)
Proof. We just need to show that (x+ 1)j−1(x+ j/2)− (j − 1)(x+ 1)j−1 ≤ xj−1(x+ j/2), that is
(x+ 1)j − j(x+ 1)j−1/2− xj−1(x+ j/2) ≤ 0,
i.e., j−2∑ l=0 [( j l ) − j 2 ( j − 1 l )] xl ≤ 0.
Note that for l ≤ j − 2, ( j
l
) − j
2 ( j − 1 l ) = ( 1− j − l 2 )( j l ) ≤ 0,
thus inequality (16) hosts for x ≥ 0 and j ≥ 2.
Lemma D.3. Let X1 ∼ Geo(p1), X2 ∼ Geo(p2), Y1, Y2 ∼ Geo ( p1+p2
2
) be independent random
variables with 0 < p1 ≤ p2 ≤ 1. Then for any positive integer j, we have
P (X1 +X2 > j) ≥ P (Y1 + Y2 > j) .
Proof. If j = 1, then P (X1 +X2 > j) = 1 = P (Y1 + Y2 > j). If p1 = p2 = 1, then P (X1 +X2 > j) = 0 = P (Y1 + Y2 > j) for j ≥ 2.
Let j ≥ 2, and c , p1 + p2 < 2 be a given constant.
We prove that f(p1) , P (X1 +X2 > j) is a decreasing function.
Employing equation (14), for p1 < c/2, we have
f(p1) = (c− p1)(1− p1)j − p1(1 + p1 − c)j
c− 2p1 ,
and f ′(p1) = −(1− p1)j − j(c− p1)(1− p1)j−1 − (1 + p1 − c)j − jp1(1 + p1 − c)j−1
c− 2p1
+ 2 (c− p1)(1− p1)j − p1(1 + p1 − c)j
(c− 2p1)2
= [c(1− p1)− j(c− p1)(c− 2p1)](1− p1)j−1 − [c(1 + p1 − c) + jp1(c− 2p1)](1 + p1 − c)j−1
(c− 2p1)2 .
Hence f ′(p1) < 0 is equivalent to
c(1− p1)− j(c− p1)(c− 2p1) c(1 + p1 − c) + jp1(c− 2p1) <
( 1 + p1 − c
1− p1
)j−1 . (17)
Note that c(1− p1)− j(c− p1)(c− 2p1) c(1 + p1 − c) + jp1(c− 2p1)
= 1− (j − 1)c(c− 2p1) c(1 + p1 − c) + jp1(c− 2p1) = 1− j − 11+p1−c c−2p1 + j p1 c
Denote x = 1+p1−cc−2p1 . If c ≤ 1, then p1 > 0 and x > 1−c c ≥ 0. And if c > 1, then p1 ≥ c − 1 and x ≥ 1+c−1−c2−c = 0. Rewrite inequality (17) as
1− j − 1 x+ jp1/c <
( x
x+ 1
)j−1 .
Recall inequality (16), we have( x
x+ 1
)j−1 ≥ 1− j − 1
x+ j/2 > 1− j − 1 x+ jp1/c .
Consequently, f ′(p1) < 0 hosts for p1 < c/2 and j ≥ 2. With the fact that limp1→c/2 f(p1) = f(c/2) according to equation (15), we have
P (X1 +X2 > j) ≥ P (Y1 + Y2 > j) .
for any positive integer j and 0 < p1 ≤ p2 ≤ 1.
Corollary D.4. LetX1 ∼ Geo(p1), X2 ∼ Geo(p2), Y1, Y2 ∼ Geo ( p1+p2
2
) be independent random
variables with 0 < p1 ≤ p2 ≤ 1. Suppose Z is a random variable that takes nonnegative integer values, and Z is independent with X1, X2, Y1, Y2. Then for any positive integer j, we have
P (Z +X1 +X2 > j) ≥ P (Z + Y1 + Y2 > j) .
Proof. With applying Lemma D.3, we have
P (Z +X1 +X2 > j) = j−1∑ l=0 P (Z = l)P (X1 +X2 > l − j) + P (Z > j − 1)
≥ j−1∑ l=0 P (Z = l)P (Y1 + Y2 > l − j) + P (Z > j − 1) = P (Z + Y1 + Y2 > j) .
Corollary D.5. Let {Xi}1≤i≤m be independent variables, and Xi follow a geometric distribution with success probability pi. For any positive integer j, we have
P ( m∑ i=1 Xi ≥ j ) ≥ P ( m∑ i=1 Yi ≥ j ) ,
where {Yi}1≤i≤m are i.i.d. random variables, Yi ∼ Geo( ∑m i=1 pi/m), and Yi is independent with Xi′(1 ≤ i′ ≤ m).
Proof. Let
f(p1, p2, · · · , pm) , P ( m∑ i=1 Xi ≥ j ) .
Our goal is to minimize f(p1, p2, · · · , pm) such that ∑m i=1 pi = S < 1. By Corollary D.4, we know that
f(p1, p2, · · · , pi, · · · , pj , · · · , pm) ≥ f(p1, p2, · · · , pi + pj 2 , · · · , pi + pj 2 , · · · , pm).
This fact implies that (p1, p2, · · · , pm) such that p1 = p2 = · · · = pm = S/m is a minimizer of the function f .
Lemma D.6. Let {Xi}1≤i≤m be i.i.d. random variables, and Xi follows a geometric distribution with success probability p. We have
P ( m∑ i=1 Xi > m 4p ) ≥ 1− 16 9m (18)
Proof. Denote ∑m i=1Xi by τ . We know that
Eτ = m
p , Var(τ) = m(1− p) p2 .
Hence, we have
P ( τ > 1 4 Eτ ) = P ( τ − Eτ > −3 4 Eτ )
= 1− P ( τ − Eτ ≤ −3 4 Eτ )
≥ 1− P ( |τ − Eτ | ≥ 3 4 Eτ )
≥ 1− 16Var(τ) 9(Eτ)2 = 1− 16m(1− p) 9m2 ≥ 1− 16 9m .
Corollary D.7. Let {Xi}1≤i≤m be independent random variables, and Xi follows a geometric distribution with success probability pi. Then
P ( m∑ i=1 Xi > m2 4( ∑m i=1 pi) ) ≥ 1− 16 9m .
E PROOF OF THEOREM 4.2
Proposition E.1. For any n ≥ 2, m ≥ 2, fSC,i and FSC in Definition 4.1 satisfy:
1. fSC,i is L-smooth and µ-strongly convex.
2. The minimizer of the function FSC is
x∗ = arg min x∈Rm FSC(x) =
√ 2∆n(α+ 1)2
(L− µ)(α− 1) (qm, qm−1, · · · , q)>,
where q = α−1α+1 . Moreover, FSC(x ∗) = −∆.
3. For 1 ≤ k ≤ m− 1, we have min x∈Fk FSC(x)− FSC(x∗) ≥ ∆q2k. (19)
Proof.
1. Just recall Proposition 2.5. 2. Denote ξ = √ 2∆n(α+1)2
(L−µ)(α−1) .
Let ∇FSC(x) = 0, that is( L− µ
2n A
(√ 2
α+ 1
) + µI ) x =
L− µ n(α+ 1) ξem,
or  ω2 + 1 + 2nµL−µ −1 −1 2 + 2nµL−µ −1 . . . . . .
−1 2 + 2nµL−µ −1 −1 1 + 2nµL−µ
x = 
0 0 ... 0 2ξ α+1
 (20)
Note that q = α−1α+1 is a root of the equation
z2 − ( 2 + 2nµ
L− µ
) z + 1 = 0,
and ω2 + 1 + 2nµ
L− µ =
1 q ,
2 α+ 1 = 1− q = −q2 + (1 + 2nµ L− µ )q.
Hence, it is easily to check that the solution to Equation (20) is
x∗ = ξ(qm, qm−1, · · · , q)>,
and FSC(x
∗) = − L− µ 2n(α+ 1) ξ2q = −∆.
3. If x ∈ Fk, 1 ≤ k < m, then x1 = x2 = · · · = xm−k = 0. Let y = xm−k+1:m ∈ Rk and Ak be last k rows and columns of the matrix in Equation (21). Then we can rewrite F (x) as
Fk(y) , FSC(x) = L− µ
4n y>Aky − L− µ n(α+ 1) ξ〈em,y〉.
Let ∇Fk(y) = 0, that is 2 + 2nµL−µ −1 −1 2 + 2nµL−µ −1 . . . . . . −1 2 + 2nµL−µ −1
−1 1 + 2nµL−µ
y = 
0 0 ... 0 2ξ α+1
 . (21)
By some calculation, the solution to above equation is
ξqk+1 1 + q2k+1 ( q−1 − q, q−2 − q2, · · · , q−k − qk )> .
Thus
min x∈Fk FSC(x) = min y∈Rk
Fk(y) = − L− µ
2n(α+ 1) ξ2q
1− q2k
1 + q2k+1 = ∆
1− q2k
1 + q2k+1 ,
and
min x∈Fk
FSC(x)− FSC(x∗) = ∆ ( 1− 1− q 2k
1 + q2k+1 ) = ∆q2k 1 + q
1 + q2k+1 ≥ ∆q2k.
Proof of Theorem 4.2. Let M = ⌊
log(9ε/∆) 2 log q
⌋ , then we have
arg min x∈FM
FSC(x)− FSC(x∗) ≥ ∆q2M ≥ 9ε,
where the first inequality is according to the third property of Proposition E.1.
Following from Lemma 2.9, for M ≥ 1 and N = (M + 1)n/4, we have min t≤N EFSC(xt)− FSC(x∗) ≥ ε. Therefore, in order to find x̂ ∈ Rm such that EFSC(x̂)− FSC(x∗) < ε, A needs at least N queries to hFSC . We estimate − log(q) and N in two cases.
1. If L/µ ≥ n/2 + 1, then α = √ 2L/µ−1n + 1 ≥ √
2. Observe that function h(β) = 1
log( β+1β−1 ) − β2 is increasing when β > 1. Thus, we have
− 1 log(q) = 1 log ( α+1 α−1 ) ≥ α 2 + h( √ 2)
= 1
2
√ 2 L/µ− 1
n + 1 + h(
√ 2)
≥ √ 2
4
(√ 2 L/µ− 1
n + 1
) + h( √ 2)
≥ 1 2
√ L/µ− 1
n +
√ 2
4 + h( √ 2),
and
N = (M + 1)n/4 = n
4
(⌊ log(9ε/∆)
2 log q
⌋ + 1 ) ≥ n
8
( − 1
log(q)
) log ( ∆
9ε ) ≥ n
8
( 1
2
√ L/µ− 1
n +
√ 2
4 + h( √ 2)
) log ( ∆
9ε
)
= Ω (( n+ √ nL
µ
) log ( ∆
9ε
))
2. If 2 ≤ L/µ < n/2 + 1, then we have − log(q) = log ( α+ 1
α− 1
) = log ( 1 +
2(α− 1) α2 − 1
)
= log 1 + √
2L/µ−1n + 1− 1 L/µ−1 n  ≤ log(1 + (√2− 1)n L/µ− 1 )
≤ log
( ( √
2− 1/2)n L/µ− 1
) ≤ log ( (2 √
2− 1)n L/µ
) , (22)
where the first inequality and second inequality follow from L/µ − 1 < n/2 and the last inequality is according to 1x−1 ≤ 2 x for x ≥ 2. Note that n ≥ 2, thus nn−1 ≤ 2 ≤ n L/µ−1 , and hence n ≥ L/µ, i.e. log(nµ/L) ≥ 0.
Therefore,
N = (M + 1)n/4 ≥ n 8
( − 1
log(q)
) log ( ∆
9ε ) = Ω (( n
1 + log(nµ/L)
) log ( ∆
9ε
)) .
Recalling that we assume that 9ε/∆ ≤ q2, thus we have
N ≥ n 8
( − 1
log(q)
) log ( ∆
9ε
) ≥ n
8
( − 1
log(q)
) (−2 log(q)) = n
4 .
Therefore, N = Ω ( n+ ( n
1+log(nµ/L)
) log (
∆ 9ε
)) .
At last, we must to ensure that 1 ≤M < m, that is
1 ≤ log(9ε/∆) 2 log q < m. (23)
Note that limβ→+∞ h(β) = 0, so −1/ log(q) ≤ α/2. Thus the above conditions are satisfied when
m = log(∆/(9ε)) 2(− log q) + 1 ≤ 1 4
(√ 2 L/µ− 1
n + 1
) log ( ∆
9ε
) + 1 = O (√ L
nµ log
( ∆
ε
)) ,
and
ε ∆ ≤ 1 9 ( α− 1 α+ 1 )2 .
F LOWER BOUND FOR ANOTHER FORM OF SUBOPTIMAL SOLUTION
Defazio (2016) showed that the PIFO algorithm Point SAGA has the convergence result E ‖xt − x∗‖22 ≤ (q′)t ‖x0 − x∗‖2, where q′ satisfies −1/ log(q′) = O ( n+ √ nL/µ ) . To match this form of upper bound, we point out that a similar result holds for {fSC,i}ni=1. Theorem F.1. Suppose that
L µ ≥ n 2 + 1, ε ≤ 1 18 (√ 2− 1√ 2 + 1 )2 , and m = 1 2 (√ 2 L/µ− 1 n + 1 ) log ( 1 18ε ) + 1.
In order to find x̂ ∈ Rm such that E ‖x̂− x∗‖22 < ε ‖x0 − x∗‖ 2 2, PIFO algorithm A needs at least Ω (( n+ √ nL µ ) log ( 1 ε )) queries to hFSC . Proof. Denote ξ = √ 2∆n(α+1)2 (L−µ)(α−1) , and M = ⌊ log(18ε) 2 log q ⌋ . For 1 ≤M ≤ m/2, N = n(M + 1)/4 and t ≤ N , we have
E ‖xt − x∗‖22 ≥ E [ ‖xt − x∗‖22 ∣∣∣∣N < TM+1]P (N < TM+1) ≥ E [ min
x∈FM ‖x− x∗‖22 ∣∣∣∣N < TM+1]P (N < TM+1) ≥ 1
9 min x∈FM ‖x− x∗‖22 .
where TM+1 is defined in (7), the second inequality follows from Corollary 2.7 (if N < TM+1, then xt ∈ FM for t ≤ N ), and the last inequality is established because of our Corollary 2.7 (More detailed explanation refer to our proof of Lemma 2.9). By Proposition E.1, we know that x∗ = ξ(qm, qm−1, · · · , q)>, and
‖x0 − x∗‖22 = ‖x ∗‖22 = ξ
2 q 2 − q2(m+1)
1− q2 .
Note that if x ∈ FM , then x1 = x2 = · · · = xm−M = 0, thus
min x∈FM
‖x− x∗‖22 = ξ 2 m∑ l=m−M q2(m−l+1) = ξ2 q2(M+1) − q2(m+1) 1− q2 .
Thus, for t ≤ N and M ≤ m/2, we have
E ‖xt − x∗‖22 ‖xt − x∗‖22 ≥ 1 9 q2M − q2m 1− q2m
≥ 1 18 q2M = 1 18 q2b log(18ε) 2 log q c ≥ ε,
where the second inequality is due to
q2M − q2m
1− q2m − q
2M 2 = q2M − 2q2m + q2(m+M) 2(1− q2m)
= q2M
2(1− q2m) (1− 2q2(m−M) + q2m)
≥ q 2M
2(1− q2m) (1− 2qm + q2m) ≥ 0.
Therefore, in order to find x̂ ∈ Rm such that E‖x̂−x ∗‖22
‖x0−x∗‖22 < ε, A needs at least N queries to hFSC .
As we have showed in proof of Theorem 4.2, for L/µ ≥ n/2 + 1, we have
1 2
√ 2 L/µ− 1
n + 1 ≥ − 1 log(q) ≥ c1
(√ L/µ− 1
n + 1
) ,
and
N = n 4 (M + 1) ≥ n 4 log(18ε) 2 log q
≥ c1 8
( n+ √ n(L/µ− 1) ) log ( 1
18ε ) = Ω (( n+ √ nL
µ
) log ( 1
ε
)) .
At last, we have to ensure that 1 ≤M ≤ m/2, that is
1 ≤ log(18ε) 2 log q < m/2.
The above conditions are satisfied when
m = log(1/(18ε)) − log q + 1 ≤ 1 2
(√ 2 L/µ− 1
n + 1
) log ( 1
18ε
) + 1 = O (√ L
nµ log
( 1
ε
)) ,
and
ε ≤ 1 18 q2.
Observe that when L/µ ≤ n/2 + 1, we have α ≥ √ 2 and q = α−1α+1 ≥ √ 2−1√ 2+1 . Hence, we just need
ε ≤ 118 (√ 2−1√ 2+1 )2 ≈ 0.00164.
G PROOF OF THEOREM 4.5
Proposition G.1. For any n ≥ 2, m ≥ 2, following properties hold:
1. fC,i is L-smooth and convex.
2. The minimizer of the function FC is
x∗ = arg min x∈Rm
FC(x) = 2ξ L (1, 2, · · · ,m)> ,
where ξ = √
3 2 BL (m+1)3/2
. Moreover, FC(x∗) = −mξ 2 nL and ‖x0 − x ∗‖22 ≤ B2.
3. For 1 ≤ k ≤ m, we have
min x∈Fk
FC(x)− FC(x∗) = ξ2
nL (m− k). (24)
Proof.
1. Just recall Proposition 2.5. 2. Denote ξ = √
3 2 BL (m+1)3/2n . Let ∇FC(x) = 0, that is
L
2n A(1)x =
ξ n em,
or  2 −1 −1 2 −1 . . . . . . −1 2 −1
−1 1
x = 
0 0 ... 0 2ξ L
 . (25)
Hence, it is easily to check that the solution to Equation (25) is
x∗ = 2ξ
L (1, 2, · · · ,m)>,
and
FC(x ∗) = −mξ
2
nL .
Moreover, we have
‖x0 − x∗‖22 = 4ξ2 L2 m(m+ 1)(2m+ 1) 6
≤ 4ξ 2
3L2 (m+ 1)3 = B2.
3. By similar calculation to above proof, we have
arg min x∈Fk
FC(x) = 2ξ
L (1, 2, · · · , k)>,
and
min x∈Fk
FC(x) = − kξ2
nL .
Thus
min x∈Fk
FC(x)− FC(x∗) = ξ2
nL (m− k).
Proof of Theorem 4.5. Since ε ≤ B 2L 384n , we have m ≥ 3. Let ξ = √ 3 2 BL (m+1)3/2 .
For M = ⌊ m−1
2
⌋ ≥ 1, we have m−M ≥ (m+ 1)/2, and
min x∈FM
FC(x)− FC(x∗) = ξ2 nL (m−M) = 3B 2L 4n m−M (m+ 1)3
≥ 3B 2L
8n
1
(m+ 1)2 ≥ 9ε,
where the first equation is according to the 3rd property in Proposition G.1 and the last inequality follows from m+ 1 ≤ B √ L/(24nε).
Similar to the proof of Theorem 4.2, by Lemma 2.9, we have
min t≤N
EFC(xt)− FC(x∗) ≥ ε.
In other words, in order to find x̂ ∈ Rm such that EFC(x̂)−FC(x∗) < ε,A needs at leastN queries to hF .
At last, observe that
N = (M + 1)n/4 = n
4
⌊ m+ 1
2 ⌋ ≥ n(m− 1)
8
≥ n 8
(√ B2L
24nε − 2
)
= Ω ( n+B √ nL
ε
) ,
where we have recalled ε ≤ B 2L
384n in last equation.
H PROOF OF LEMMA 4.3, LEMMA 4.6 AND LEMMA 4.10
Proof of Lemma 4.6. Consider the following functions {gi}1≤i≤n, gi : R→ R, where
g1(x) = L
2 x2 − nLBx,
gi(x) = L
2 x2,
G(x) = 1
n n∑ i=1 gi(x) = L 2 x2 − LBx.
First observe that
x∗ = arg min x∈R G(x) = B,
G(0)−G(x∗) = LB 2
2 ,
and |x0 − x∗| = B.
For i > 1, we have dgi(x)dx |x=0 = 0 and prox γ gi(0) = 0. Thus xt = 0 will host till our first-order method A draws the component f1. That is, for t < T = arg min{t : it = 1}, we have xt = 0.
Hence, for t ≤ 12p1 , we have EG(xt)− F (x∗) ≥ E [ G(xt)−G(x∗) ∣∣∣ 1 2p1 < T ] P ( 1 2p1 < T ) = LB2 2 P ( 1 2p1 < T ) .
Note that T follows a geometric distribution with success probability p1 ≤ 1/n, and P ( T > 1
2p1
) = P ( T > ⌊ 1
2p1
⌋) = (1− p1) ⌊ 1 2p1 ⌋
≥ (1− p1) 1 2p1 ≥ (1− 1/n)n/2 ≥ 1 2 ,
where the second inequality follows from h(z) = log(1−z)2z is a decreasing function. Thus, for t ≤ 12p1 , we have
EG(xt)− F (x∗) ≥ LB2
4 ≥ ε
Thus, in order to find x̂ ∈ R such that EF (x̂) − F (x∗) < ε, A needs at least 12p1 ≥ n/2 = Ω (n) queries to hG.
Proof of Lemma 4.10. Note that {gi}ni=1 defined in proof of Lemma 4.6 is also L-average smooth, so Lemma 4.10 hosts for the same reason. Proof of Lemma 4.3. Let B = √
2∆/L. Then ε/∆ ≤ 1/2 is equivalent to ε ≤ LB2/4. Note that {gi}ni=1 defined in proof of Lemma 4.6 is also µ-strongly convex for any µ ≤ L, and satisfy |G(0)−G(x∗)| = ∆. Therefore Lemma 4.3 hosts for the same reason.
Remark H.1. Suppose that ε
∆ >
1 9 ( α− 1 α+ 1 )2 , α = √ 2 κ− 1 n + 1.
1. If κ ≥ n/2 + 1, then we have α ≥ √
2 and( n+ √ κn ) log
( ∆
9ε
) ≤ 2 ( n+ √ κn ) log ( α+ 1
α− 1 ) ≤ 4 (n+ √ κn)
α− 1 = O(n) + 4
√ κn
(1− √ 2/2)α
≤ O(n) + 4√ 2− 1 √ κn√ κ/n = O(n),
where the second inequality follows from log(1+x) ≤ x and the last inequality is according to α ≥ √ 2κ/n. That is
Ω(n) = Ω (( n+ √ κn ) log ( ∆
9ε
)) .
2. If 2 ≤ L/µ < n/2 + 1, then we have( n
1 + log(nµ/L)
) log ( ∆
9ε
) ≤ (
n
1 + log(nµ/L)
)( 2 log ( α+ 1
α− 1 )) ≤ ( n
1 + log(nµ/L)
)( 2 log ( (2 √
2− 1)n L/µ
)) = O(n),
where the second inequality follows from (22). That is
Ω(n) = Ω
(( n
1 + log(nµ/L)
) log ( ∆
9ε
) + n ) .
I DETAILED PROOF FOR SECTION 4.3
Proof of Proposition 4.7.
1. It is easily to check that FSC(x) is µ-strongly convex. Following from Proposition 2.5, then {fSC,i}ni=1 is L̂-average smooth, where
L̂ = √√√√16 n [( L+ µ 4 )2 + ( L− µ 4 )2] + µ2
=
√ 2(L2 + µ2)
n + µ2 = L′.
2. Clearly, L = √
n(L′2−µ2) 2 − µ2 ≤ √ n 2L ′.
Furthermore, according to L ′ µ ≥ √ 3 n ( n 2 + 1), we have
L2 − n 3 L′2 = n 2 (L′2 − µ2)− µ2 − n 3 L′2
= 1
2 (n 2 + 1 )2 µ2 − n+ 2 2 µ2
=
( n2
8 − 1 2
) µ2 ≥ 0,
and, L/µ ≥ √
n 3L ′/µ ≥ n/2 + 1.
Proof of Theorem 4.8. By 2nd property of Proposition 4.7, we know that L/µ ≥ n/2 + 1. Moreover,
m = 1
4 √√ 2 n L′ µ + 1  log(∆ 9ε ) + 1
≥ 1 4
(√ 2 L/µ− 1
n + 1
) log ( ∆
9ε
) + 1,
Then, by Theorem 4.2 5, in order to find x̂ ∈ Rm such that EFSC(x̂) − FSC(x∗) < ε, A needs at least N queries to hFSC , where
N = Ω (( n+ √ nL
µ
) log ( ∆
ε
))
= Ω n+ √ n √ n/3L′
µ
 log(∆ ε ) = Ω (( n+ n3/4 √ L′
µ
) log ( ∆
ε
)) .
5By the proof of Theorem 4.2, a larger dimension m does not affect the conclusion of the theorem.
Proof of Theorem 4.9. Note that
ε ≤ √ 2
768 B2L′√ n = B2L 384n ,
m =
⌊ 4 √
18
12 Bn−1/4
√ L′
ε
⌋ − 1 = ⌊√ B2L
24nε
⌋ − 1.
By Theorem 4.5, in order to find x̂ ∈ Rm such that EFC(x̂) − FC(x∗) < ε, A needs at least N queries to hFC , where
N = Ω ( n+B √ nL
ε
)
= Ω n+B √ n √ n/2L′
ε  = Ω ( n+Bn3/4 √ L′
ε
) .
J NON-CONVEX CASE
In non-convex case, our goal is to find an ε-approximate stationary point x̂ of our objective function f , which satisfies
‖∇f(x̂)‖2 ≤ ε. (26)
J.1 PRELIMINARIES
We first introduce a general concept about smoothness. Definition J.1. For any differentiable function f : Rm+1 → R, we say f is (l, L)-smooth, if for any x,y ∈ Rm we have
l 2 ‖x− y‖22 ≤ f(x)− f(y)− 〈∇f(y),x− y〉 ≤ L 2 ‖x− y‖22 ,
where L > 0, l ∈ R.
Especially, if f is L-smooth, then it can be checked that f is (−L,L)-smooth. If f is (−σ, L)-smooth, in order to make the operator proxγf valid, we set 1 γ > σ to ensure the function
f̂(u) , f(u) + 1
2γ ‖x− u‖22
is a convex function.
Next, we introduce a class of function which is original proposed in (Carmon et al., 2017). Let GNC : Rm+1 → R be
GNC(x;α,m) = 1
2
∥∥B(m+ 1, 4√α)x∥∥2 2 − √ α〈e1,x〉+ α m∑ i=1 Γ(xi),
where the non-convex function Γ : R→ R is Γ(x) , 120 ∫ x
1
t2(t− 1) 1 + t2 dt. (27)
We need following properties about GNC(x;α,m).
Proposition J.2 (Lemmas 3,4, Carmon et al. (2017)). For any 0 < α ≤ 1, it holds that
1. Γ(x) is (−45( √ 3 − 1), 180)-smooth and GNC(x;α,m) is (−45( √
3 − 1)α, 4 + 180α)smooth.
2. GNC(0;α,m)−minx∈Rm+1 GNC(x;α,m) ≤ √ α/2 + 10αm.
3. For x which satisfies that xm = xm+1 = 0, we have
‖∇GNC(x;α,m)‖2 ≥ α 3/4/4.
J.2 OUR RESULT
Theorem J.3. For any PIFO algorithmA and any L, σ, n,∆, ε such that ε2 ≤ ∆Lα81648n , there exist a dimension d =
⌊ ∆L √ α
40824nε2 ⌋ + 1 and n (−σ, L)-smooth nonconvex functions {fi : Rd → R}ni=1 such
that f(x0) − f(x∗) ≤ ∆. In order to find x̂ ∈ Rd such that E ‖∇f(x̂)‖2 < ε, A needs at least Ω ( ∆L √ α
ε2
) queries to hf , where we set α = min { 1, ( √ 3+1)nσ 30L , n 180 } .
Remark J.4. For n > 180, wehave
Ω
( ∆L √ α
ε2
) = Ω ∆ ε2 min L, √√ 3 + 1 30 √ nσL, √ nL√ 180   = Ω(∆ ε2 min{L, √ nσL} ) .
Thus, our result is comparable to the one of Zhou and Gu’s result (their result only related to IFO algorithms, so our result is more strong), but our construction only requires the dimension be O ( 1 + ∆ε2 min{L/n, √ σL/n} ) , which is much smaller than O ( ∆ ε2 min{L, √ nσL} ) in (Zhou and Gu, 2019).
J.3 CONSTRUCTIONS
Consider
F (x;α,m, λ, β) = λGNC(x/β;α,m). (28)
Similar to our construction we introduced in Section 2, we denote the l-th row of the matrix B(m+ 1, 4 √ α) by bl and
Li = {l : 1 ≤ l ≤ m,m+ 1− l ≡ i(mod n)}, i = 1, 2, · · · , n. (29)
Let Gk = span{e1, e2, · · · , ek}, 1 ≤ k ≤ m, G0 = {0} and compose F (x;α,m, λ, β) to f1(x;α,m, λ, β) = λn 2β2 ∑ l∈Li ∥∥b>l x∥∥22 − λn√αβ 〈e1,x〉+ λα m∑ i=1 Γ(xi/β), fi(x;α,m, λ, β) = λn 2β2 ∑ l∈Li ∥∥b>l x∥∥22 + λα m∑ i=1 Γ(xi/β), for i ≥ 2. (30) Clearly, F (x;α,m, λ, β) = 1n ∑n i=1 fi(x;α,m, λ, β). Moreover, by Proposition J.2, we have following properties about F (x;α,m, λ, β) and {fi(x;α,m, λ, β)}ni=1. Proposition J.5. For any 0 < α ≤ 1, it holds that
1. fi(x;α,m, λ, β) is ( −45( √ 3−1)αλ β2 , (2n+180α)λ β2 ) -smooth. 2. F (0;α,m, λ, β)−minx∈Rm+1 F (x;α,m, λ, β) ≤ λ( √ α/2 + 10αm).
3. For x which satisfies that xm = xm+1 = 0, we have
‖∇F (x;α,m, λ, β)‖2 ≥ α3/4λ
4β .
Similar to Lemma 2.6, similar conclusion hosts for {fi(x;α,m, λ, β)}ni=1. Lemma J.6. For x ∈ Fk, 0 ≤ k < m and γ < √ 2+1 60 β2 λα , we have
∇fi(x;α,m, λ, β),proxγfi(x) ∈ { Gk+1, if k ≡ i− 1(mod n), Gk, otherwise.
Proof. Let G(x) , m∑ i=1 Γ(xi) and Γ′(x) be the derivative of Γ(x). First note that Γ′(0) = 0, so if x ∈ Gk, then
∇G(x) = ( Γ′(x1),Γ ′(x2), · · · ,Γ′(xm) )> ∈ Gk.
Moreover, for x ∈ FG (k ≥ 1), we have
b>l x = 0 for l < m− k, bl ∈ Gk for l > m− k,
bm−k ∈ Gk+1.
Consequently, for l 6= m− k, blb>l x = (b>l x)bl ∈ Gk, and bm−kb>m−kx ∈ Gk+1. For k = 0, we have x = 0, and
∇f1(x) = λn √ α/β e1 ∈ G1,
∇fj(x) = 0 (j ≥ 2).
For k ≥ 1, we suppose that m− k ∈ Li. Since
∇fj(x) = λn
β2 ∑ l∈Lj b>l blx + λα β ∇G(x/β)− ηje1,
where η1 = λn √ α/β, ηj = 0 for j ≥ 2. Hence, ∇fi(x) ∈ Fk+1 and ∇fj(x) ∈ Fk (j 6= i).
Now, we turn to consider v = proxγfj (x).
We have
∇fj(v) + 1
γ (v − x) = 0,
that is λn β2 ∑ l∈Lj b>l bl + 1 γ I v + λα β ∇G(v/β) = ηje1 + 1 γ x. (31)
Denote
A = λn
β ∑ l∈Lj b>l bl + β γ I, u = 1 β v, y = ηje1 + 1 γ x,
then we have
Au + λα
β ∇G(u) = y. (32)
Next, if s satisfies { s > max{1, k} for j = 1, s > k for j > 1,
(33)
then we know that the s-th element of y is 0.
If s satisfies (33) and m − s ∈ Lj , then the s-th and (s + 1)-th elements of Au is ((ξ + β/γ)us − ξus+1) and (−ξus + (ξ + β/γ)us+1) respectively where ξ = λn/β. So by Equation (32), we have  β γ us + ξ(us − us+1) + 120λα β u2s(us−1) 1+u2s = 0.
β γ us+1 + ξ(us+1 − us) + 120λα β u2s+1(us+1−1) 1+u2s+1 = 0.
Following from Lemma J.9, for 120λαβ < (2+2
√ 2)β
γ , we have us = us+1 = 0. That is
1. if m− s ∈ Lj and s satisfies (33), then us = 0.
2. if m− s+ 1 ∈ Lj and s− 1 satisfies (33), then us = 0.
For s which satisfies (33), if m − s 6∈ Lj and m − s + 1 6∈ Lj , then the s-th element of Au is (β/γ us). Similarly, by Equation (32), we have
β γ us + 120λα β u2s(us − 1) 1 + u2s = 0.
Following from Lemma J.8, for 120λαβ < (2+2
√ 2)β γ , we have us = 0.
Therefore, we can conclude that
1. if s− 1 satisfies (33), then us = 0.
2. if s satisfies (33) and m− s+ 1 6∈ Lj , then us = 0.
Moreover, we have that
1. if k = 0 and j = 1, then m− 1,m− 2 6∈ Lj , so u2 = 0.
2. if k = 0 and j > 1, then for s = 1, we have m− s+ 1 6∈ Lj , so u1 = 0.
3. if k = 0, then for s > 2, we have s− 1 > 1 satisfies (33), so us = 0.
4. if k > 0, then for s > k + 1, we have s− 1 > k satisfies (33), so us = 0.
5. if k > 0 and m− k 6∈ Lj , then for s = k + 1, we have m− s+ 1 6∈ Lj , so uk+1 = 0.
In short,
1. if k = 0 and j > 1, then u ∈ G0.
2. if k = 0 and j = 1, then u ∈ G1.
3. if k > 1 and m− k 6∈ Lj , then u ∈ Gk.
4. if k > 1 and m− k ∈ Lj , then u ∈ Gk+1.
Remark J.7. In order to make the operator proxγfi valid, γ need to satisfy
γ <
√ 3 + 1
90
β2 λα <
√ 2 + 1
60
β2 λα .
So for any valid PIFO call, the condition about γ in Lemma J.6 must be satisfied.
Lemma J.8. Suppose that 0 < λ2 < (2 + 2 √
2)λ1, then z = 0 is the only real solution to the equation
λ1z + λ2 z2(z − 1)
1 + z2 = 0. (34)
Proof. Since 0 < λ2 < (2 + 2 √ 2)λ1, we have
λ22 − 4λ1(λ1 + λ2) < 0,
and consequently, for any z, (λ1 + λ2)z2 − λ2z + λ1 > 0. On the other hand, we can rewrite Equation (34) as
z ( (λ1 + λ2)z 2 − λ2z + λ1 ) = 0.
Clearly, z = 0 is the only real solution to Equation (34).
Lemma J.9. Suppose that 0 < λ2 < (2 + 2 √
2)λ1 and λ3 > 0, then z1 = z2 = 0 is the only real solution to the equation λ1z1 + λ3(z1 − z2) + λ2 z21(z1−1) 1+z21 = 0.
λ1z2 + λ3(z2 − z1) + λ2 z 2 2(z2−1) 1+z22
= 0. (35)
Proof. If z1 = 0, then z2 = 0. So let assume that z1z2 6= 0. Rewrite the first equation of Equation (35) as
λ1 + λ3 λ3 + λ2 λ3 z1(z1 − 1) 1 + z21 = z2 z1
Note that
1− √ 2
2 ≤ z(z − 1) 1 + z2 .
Thus, we have
λ1 + λ3 λ3 + λ2 λ3
1− √ 2
2 ≤ z2 z1 .
Similarly, it also holds
λ1 + λ3 λ3 + λ2 λ3
1− √ 2
2 ≤ z1 z2 .
By 0 < λ2 < (2 + 2 √ 2)λ1, we know that λ1 + 1− √ 2 2 λ2 > 0. Thus
λ1 + λ3 λ3 + λ2 λ3
1− √ 2
2 > 1.
Since z1/z2 > 1 and z2/z1 > 1 can not hold at the same time, so we get a contradiction.
Following from Lemma J.6, we know following Lemma which is similar to Lemma 2.9.
Lemma J.10. If M ≥ 1 satisfies minx∈GM ‖∇F (x)‖2 ≥ 9ε and N = n(M + 1)/4, then we have
min t≤N E ‖∇F (xt)‖2 ≥ ε.
Theorem J.11. Set
α = min { 1, ( √ 3 + 1)nσ
30L , n 180
} ,
λ = 3888nε2
Lα3/2 , β = √ 3λn/L,
m =
⌊ ∆L √ α
40824nε2 ⌋ Suppose that ε2 ≤ ∆Lα81648n . In order to find x̂ ∈ R
m+1 such that E ‖∇F (x̂)‖2 < ε, PIFO algorithm A needs at least Ω
( ∆L √ α
ε2
) queries to hF .
Proof. First, note that fi is (−l1, l2)-smooth, where
l1 = 45( √
3− 1)αλ β2
= 45( √
3− 1)L 3n
α ≤ 45( √
3− 1)L 3n
( √ 3 + 1)nσ
30L = σ,
l2 = (2n+ 180α)λ
β2 =
L
3n (2n+ 180α) ≤ L.
Thus each fi is (−σ, L)-smooth. Next, observe that
F (x0)− F (x∗) ≤ λ( √ α/2 + 10αm) = 1944nε2
Lα +
38880nε2
L √ α m
≤ 1944 40824 ∆ + 38880 40824 ∆ = ∆.
For M = m− 1, we know that
min x∈GM
‖∇F (x)‖2 ≥ α3/4λ
4β =
α3/4λ 4 √ 3λn/L =
√ λL
3n
α3/4
4 = 9ε.
With recalling Lemma J.10, in order to find x̂ ∈ Rm+1 such that E ‖∇F (x̂)‖2 < ε, PIFO algorithm A needs at least N queries to hF , where
N = n(M + 1)/4 = nm/4 = Ω
( ∆L √ α
ε2
) .
At last, we need to ensure that m ≥ 2. By ε2 ≤ ∆Lα81648n , we have
∆L √ α
40824nε2 ≥ ∆Lα 40824nε2 ≥ 2,
and consequently m ≥ 2.

Review summaries:
The authors prove lower bounds on the number of queries required for optimizing sums of convex functions.  They consider more powerful queries than the usual queries that provide function evaluation/gradient pairs for chosen summands.  As was done in [1] (which is cited in the submission), in this work algorithms can also get the answer to a

This paper proves a better complexity lower bound for stochastic PIFO optimizers on the problem of finite-sum minimization. The paper assumes that the objective function is the sum of n individual loss functions. It further assumes that (1) the optimizer initializes at a fixed point, and (2) at each iteration, it randomly and independently selects one loss function to update the parameter vector.