Title: A NOVEL ANALYSIS FRAMEWORK OF LOWER COM-PLEXITY BOUNDS FOR FINITE-SUM OPTIMIZATION Anonymous

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.

1. INTRODUCTION:

We consider the minimization of the following optimization problem

EQUATION

where the f i (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,

EQUATION

where i ∈ {1, . . . , n}, γ > 0, and the proximal operation is defined as

prox γ fi (x) = arg min u f i (u) + 1 2γ x -u 2 2 .

We also define the Incremental First-order Oracle (IFO)

g f (x, i, γ) [f i (x), ∇f i (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∈R d 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 f i , 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 : R m → R, • f is convex, if for any x, y ∈ R m it satisfies f (y) ≥ f (x) + ∇f (x), y -x . • f is µ-strongly convex, if for any x, y ∈ R m it satisfies f (y) ≥ f (x) + ∇f (x), y -x + µ 2 x -y 2 2 . • f is L-smooth, if for any x, y ∈ R m it satisfies ∇f (x) -∇f (y) 2 ≤ L x -y 2 .

Upper Bounds Previous Lower Bounds Our Lower Bounds fi is L-smooth and µ-strongly (Defazio, 2016) , PIFO and Srebro, 2016) PIFO Hannah et al., 2018) , IFO Hannah et al., 2018) IFO (Woodworth and Srebro, 2016) PIFO and Gu, 2019) IFO

convex with n = O(κ) O (n + √ κn) log( 1 ε ) (Allen-Zhu, 2017), IFO

Ω n + √ κn log( 1 ε ) (Woodworth

Ω (n + √ κn) log( 1 ε ) [Theorem 3.1] PIFO fi is L-smooth and µ-strongly convex with κ = O(n) O n+ n 1+(log( n κ )) + log 1 ε (

Ω n+ n 1+(log( n κ )) + log 1 ε (

Ω n+ n 1+(log( n κ )) + log 1 ε [Theorem 3.1] PIFO fi is L-smooth and convex O n log( 1 ε ) + nL ε (Allen-Zhu, 2017) IFO Ω n + nL ε

Ω n + nL ε [Theorem 3.3] PIFO {fi} n i=1 is L-average smooth and f is µ-strongly convex O n + n 3 4 √ κ log 1 ε (Allen-Zhu, 2018) IFO Ω n + n 3 4 √ κ log 1 ε (Zhou

Ω n + n 3 4 √ κ log 1 ε [Theorem 3.5] PIFO {fi} n i=1 is L-average smooth and f is convex O n + n 3 4 L ε (Allen-Zhu, 2018) IFO Ω n + n 3 4

L ε (Zhou and Gu, 2019) IFO

Ω n + n 3 4 L ε [Theorem 3.7] PIFO

Table 1 : We compare our PIFO lower bounds with existing results of IFO or PIFO algorithms, where κ = L/µ. Note that the call of PIFO could obtain more information than IFO. Hence, any PIFO lower bound also can be regarded as an IFO lower bound, not vice versa.

Definition 2.2. We say differentiable functions {f i } n i=1 , f i : R m → R, to be L-average smooth if for any x, y ∈ R m , they satisfy

1 n n i=1 ∇f i (x) -∇f i (y) 2 2 ≤ L 2 x -y 2 2 .

(3)

Remark 2.3. We point out that

1. if each f i is L-smooth, then {f i } n i=1 are L-average smooth. 2. if {f i } n i=1 are L-average smooth, then f (x) = 1 n n i=1 f i (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 x t be the point obtained at time-step t and the algorithm starts with x 0 . The algorithm A is said to be a PIFO algorithm if for any t ≥ 0, we have

EQUATION

)

where i t is a random variable supported on [n] and takes P(i t = j) = p j for each t ≥ 0 and 1 ≤ j ≤ n where n j=1 p j = 1.

Without loss of generality, we assume x 0 = 0 and p 1 ≤ p 2 ≤ • • • ≤ p n to simplify our analysis. Otherwise, we can take { fi (x) = f i (x + x 0 )} n i=1 into consideration. On the other hand, suppose that

p s1 ≤ p s2 ≤ • • • ≤ p sn where {s i } n i=1 is a permutation of [n]. Define { fi } n i=1 such that fsi = f i , then A takes component fsi in probability p si , i.e., A takes f i in probability p si .

To demonstrate the construction of adversarial functions, we first introduce the following class of matrices:

B(m, ω) =      -1 1 -1 1 . . . . . . -1 1 ω      ∈ R m×m .

Then we define:

EQUATION

)

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 b l (m, ω) and let

EQUATION

We can determine the smooth and strongly-convex coefficients of r i as follows.

Proposition 2.5. For any λ 1 > 0, λ 2 ≥ 0, ω < √ 2, we have that the r i are (4λ 1 + 2λ 2 )-smooth and λ 2 -strongly convex, and {r i } n i=1 is L -average smooth where

L = 2 4 n [(λ 1 + λ 2 ) 2 + λ 2 1 ] + λ 2 2 .

We define the subspaces {F k } m k=0 as

F k = span{e m , e m-1 , • • • , e m-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 = 0, λ 1 > 0, λ 2 ≥ 0 and x ∈ F k , 0 ≤ k < m, we have that

∇r i (x; λ 0 , λ 1 , λ 2 , m, ω) and prox γ ri (x) ∈ F k+1 , if k ≡ i -1(mod n), F k , otherwise.

In short, if x ∈ F k and let f i (x) r i (x; λ 0 , λ 1 , λ 2 , ω), then there exists only one i ∈ {1, . . . , n} such that h f (x, i, γ) could (and only could) provide additional information in F k+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 x t = 0 will host until algorithm A draws the component f 1 . Then, for any t < T 1 = min t {t : i t = 1}, we have x t ∈ F 0 and x T1 ∈ F 1 . The value of T 1 can be regarded as the smallest integer such that x T1 could host. Similarly, we can define T k to be the smallest integer such that x T k ∈ F k could host. We give the formal definition of T k recursively and connect it to geometrically distributed random variables in the following corollary.

Corollary 2.7. Let T 0 = 0, and T k = min

EQUATION

Then for any k ≥ 1 and t < T k , we have x t ∈ F k-1 . Moreover, T k can be written as sum of k independent random variables {Y l } 1≤l≤k , i.e., T k = k l=1 Y l , where Y l follows a geometric distribution with success probability q l = p l where l ≡ l (mod n), 1 ≤ l ≤ n.

The basic idea of our analysis is that we guarantee the minimizer of r lies in F m and assure the PIFO algorithm extend the space of span{x 0 , x 1 , . . . , x t } slowly with t increasing. We know that span{x 0 , x 1 , . . . , x T k } ⊆ F k by Corollary 2.7. Hence, T k is just the quantity that reflects how span{x 0 , x 1 , . . . , x t } verifies. Because T k 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 {Y i } 1≤i≤N be independent random variables, and Y i follows a geometric distribution with success probability p i . Then

EQUATION

From Lemma 2.8, the following result implies how many PIFO calls we need. Lemma 2.9.

If M ≥ 1 satisfies min x∈F M f (x) -min x∈R m f (x) ≥ 9ε and N = n(M + 1)/4, then we have min t≤N Ef (x t ) -min x∈R m 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 {f i : R d → R} n i=1 such that f (x 0 ) -f (x * ) = ∆. In order to find x ∈ R d such that Ef ( x) -f (x * ) < ε, A needs at least N queries to h f , 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 ε ≤ LB 2 /4, there exist a dimension d = O 1 + B L/(nε) and n L-smooth and convex functions {f

i : R d → R} n i=1 such that x 0 -x * 2 ≤ B. In order to find x ∈ R d such that Ef ( x) -f (x * ) < ε, A needs at least Ω n+B nL/ε queries to h f .

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 L 2 B 4 ε 2 log nLB 2 ε

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 {f i : R d → R} n i=1 where the {f i } n i=1 are L-average smooth and f is µ-strongly convex, such that f (x 0 ) -f (x * ) = ∆. In order to find x ∈ R d such that Ef ( x) -f (x * ) < ε, A needs at least Ω n+n 3/4 √ κ log (∆/ε) queries to h f .

Remark 3.6. Compared with Zhou and Gu's lower bound Ω n + n 3/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 ε ≤ LB 2 /4, there exist a

dimension d = O 1 + Bn -1/4 L/ε and n functions {f i : R d → R} n i=1 which the {f i } n i=1 are L-average smooth and f is convex, such that x 0 -x * 2 ≤ B. In order to find x ∈ R d such that Ef ( x) -f (x * ) < ε, A needs at least Ω n + Bn 3/4 L/ε queries to h f .

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 be O 1 + Bn -1/4 L/ε , which is much smaller than O n + Bn 3/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.

EQUATION

and

F SC (x) 1 n n i=1 f SC,i (x) = L -µ 4n B m, 2 α + 1 x 2 2 + µ 2 x 2 2 - 2(L -µ)∆ n(α -1) e m , x .

Note that the f SC,i are L-smooth and µ-strongly convex, and

F SC (x 0 ) -F SC (x * ) = ∆ (see Propo- sition E.

1 in Appendix for more details). Next we show that the functions {f SC,i } n i=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 EF SC ( x) -F SC (x * ) < ε, PIFO algorithm A needs at least N queries to h FSC . 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

{f i : R → R} n i=1 such that F (x 0 ) -F (x * ) ≤ ∆. In order to find x ∈ R such that EF (x) -F (x * ) < ε, A needs at least Ω(n) queries to h F .

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 f C,i : R m → R as follows

EQUATION

and

F C (x) 1 n n i=1 f C,i (x) = L 4n B(m, 1)x 2 2 - √ 3 2 BL (m + 1) 3/2 n e m , x .

Note that the f C,i are L-smooth and convex, and x 0 -x * 2 ≤ B (see Proposition G.1 in Appendix for more details). Next we show the lower bound for functions f C,i defined above.

Theorem 4.5. Suppose that

ε ≤ B 2 L 384n and m = B 2 L 24nε -1. In order to find x ∈ R m such that EF C ( x)-F C (x * ) < ε, A needs at least Ω n + B nL ε queries to h FC .

To derive Theorem 3.3, we also need the following lemma in the case ε > B 2 L 384n . Lemma 4.6. For any PIFO algorithm A and any L, n, B, ε such that ε ≤ LB 2 /4, there exist n L-smooth and convex functions {f

i : R → R} n i=1 such that |x 0 -x * | ≤ B. In order to find x ∈ R such that EF (x) -F (x * ) < ε, A needs at least Ω(n) queries to h F . It is worth noting that if ε > B 2 L 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 {f SC,i } n i=1 and F SC defined in Definition 4.1. Proposition 4.7. For n ≥ 2, we have that

1. F SC (x) is µ-strongly convex and {f SC,i } n i=1 is L -average smooth. 2. If L µ ≥ 3 n ( n 2 + 1), then we have n 3 L ≤ L ≤ n 2 L 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 ∈ R m such that EF SC ( x) -F SC (x * ) < ε, PIFO algorithm A needs at least

Ω n + n 3/4 L µ log ∆ ε queries to h FSC . 4.3.2 F IS CONVEX

For fixed L , B, n, ε, we set L = n 2 L , and consider {f C,i } n i=1 and F C defined in Definition 4.4. It follows from Proposition 2.5 that {f C,i } n i=1 is L -average smooth. Theorem 4.9. Suppose that

ε ≤ √ 2 768 B 2 L √ n and m = 4 √ 18 12 Bn -1/4 L ε -1. In order to find x ∈ R m such that EF C ( x) -F C (x * ) < ε, A needs at least Ω n + Bn 3/4 L ε queries to h FC .

Similar to Lemma 4.6, we also need the following lemma for the case ε >

√ 2 768 B 2 L √ n .

Lemma 4.10. For any PIFO algorithm A and any L, n, B, ε such that ε ≤ LB 2 /4, there exist n functions {f i : R → R} n i=1 which is L-average smooth, such that F (x) is convex and

x 0 -x * 2 ≤ B. In order to find x ∈ R such that EF (x) -F (x * ) < ε, A needs at least Ω(n) queries to h F . Similarly, note that if ε > √ 2 768 B 2 L √ n , then Ω(n) = Ω n + Bn 3/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 f i is (l, L)-smoothness.

A COMPARISON OF REQUIRED NUMBER OF DIMENSIONS Previous Lower Bounds:

Our Lower Bounds  and Srebro, 2016 ) and Srebro, 2016 ) and Gu, 2019 ) (Zhou and Gu, 2019 ) 

f i is L-smooth and µ-strongly convex #PIFO = Ω n + √ κn log( 1 ε ) d = O κn ε log 5 1 ε (Woodworth

#PIFO = Ω (n + √ κn) log( 1 ε ) d = O κ n log 1 ε [Theorem 3.1] f i is L-smooth and convex #PIFO = Ω n + nL ε d = O L 2 ε 2 log 1 ε (Woodworth

#PIFO = Ω n + nL ε d = O 1 + L nε [Theorem 3.3] {f i } n i=1 is L-average smooth and f is µ-strongly convex #IFO = Ω n + n 3/4 √ κ log 1 ε d = O n + n 3/4 √ κ log 1 ε (Zhou

#PIFO = Ω n + n 3/4 √ κ log 1 ε d = O n -1/4 √ κ log 1 ε [Theorem 3.5] {f i } n i=1 is L-average smooth and f is convex #IFO = Ω n + n 3/4 L ε d = O n + n 3/4 L ε

#PIFO = Ω n + n 3/4 L ε d = O 1 + n -1/4 L ε [Theorem 3.7]

B COMPARISON WITH EXISTING PROOFS:

Recall the adversary function we used is (please see detailed defintion in Section 2)

EQUATION

where

ri(x; λ0, λ1, λ2, m, ω) =      λ1 l∈L 1 b l (m, ω) x 2 2 + λ2 x 2 2 -λ0 em, x , for i = 1, λ1 l∈L i b l (m, ω) x 2 2 + λ2 x 2 2 , 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 f i (x), where f i (x) = nr(x i ), x =     x 1 x 2 . . . x n     ∈ R mn , and x i ∈ R m 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 : R m → R and f : R mn → 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 ω      ∈ R m×m , b l is the l-th row of B, and f i (x) = r i (x; λ 0 , λ 1 , λ 2 , m, ω).

Recall that:

L i = {l : 1 ≤ l ≤ m, l ≡ i -1(modn)}, i = 1, 2, • • • , n. For 1 ≤ i ≤ n, let B i be a submatrix which is formed from rows L i of B, that is B i = B[L i ; ]

Then f i can be wriiten as

f i (x) = λ 1 B i x 2 2 + λ 2 x 2 2 -η i e m , x , where η 1 = λ 0 , η i = 0, i ≥ 2. Proof of Proposition 2.5. Note that u, B i B i u = B i u 2 2 = l∈Li (b l u) 2 = l∈Li\{m} (u m-l -u m-l+1 ) 2 + ω 2 u 2 m (if m ∈ L i ) l∈Li (u m-l -u m-l+1 ) 2 ≤ 2 u 2 2 ,

where the last inequality is according to (x+y) 2 ≤ 2(x 2 +y 2 ), and

|l 1 -l 2 | ≥ n ≥ 2 for l 1 , l 2 ∈ L i . Hence, B i B i ≤ 2, and ∇ 2 f i (x) = 2λ 1 B i B i + 2λ 2 I ≤ 4λ 1 + 2λ 2 . Next, observe that ∇f i (x) -∇f i (y) 2 2 = (2λ 1 B i B i + 2λ 2 I)(x -y) 2 2 Let u = x -y. Note that b l b l u = (u m-l -u m-l+1 )(e m-l -e m-l+1 ), l < m, ω 2 u 1 e 1 , l = m.

Thus, if m / ∈ L i , then

(2λ 1 B i B i + 2λ 2 I)u 2 2 = 2λ 1 l∈Li (u m-l -u m-l+1 )(e m-l -e m-l+1 ) + 2λ 2 u 2 2 = m-l∈Li (2λ 1 (u l -u l+1 ) + 2λ 2 u l ) 2 + (-2λ 1 (u l -u l+1 ) + 2λ 2 u l+1 ) 2 + m-l / ∈Li m-l+1 / ∈Li (2λ 2 u l ) 2 ≤ m-l∈Li 8 (λ 1 + λ 2 ) 2 + λ 2 1 (u 2 l + u 2 l+1 ) + 4λ 2 2 u 2 2 .

Similarly, if m ∈ L i , then

(2λ 1 B i B i + 2λ 2 I)u 2 2 ≤ m-l∈Li l =0 8 (λ 1 + λ 2 ) 2 + λ 2 1 (u 2 l + u 2 l+1 ) + 4(λ 1 ω 2 + λ 2 ) 2 u 2 1 + 4λ 2 2 u 2 2 .

Therefore, we have

1 n n i=1 ∇f i (x) -∇f i (y) 2 2 ≤ 1 n m-1 l=1 8 (λ 1 + λ 2 ) 2 + λ 2 1 (u 2 l + u 2 l+1 ) + 4(2λ 1 + λ 2 ) 2 u 2 1 + 4λ 2 2 u 2 2 ≤ 16 n (λ 1 + λ 2 ) 2 + λ 2 1 u 2 2 + 4λ 2 2 u 2 2 ,

where we have used

(2λ 1 + λ 2 ) 2 ≤ 2 (λ 1 + λ 2 ) 2 + λ 2 1 .

In summary, we get that {f i } 1≤i≤n is L -average smooth, where

L = 2 4 n [(λ 1 + λ 2 ) 2 + λ 2 1 ] + λ 2 2 .

Proof of Lemma 2.6. For x ∈ F k (k ≥ 1), we have

b l x = 0 for l > k, b l ∈ F k for l < k, b k ∈ F k+1 . Consequently, for l = k, b l b l x = (b l x)b l ∈ F k , and b k b k x ∈ F k+1 .

For k = 0, we have x = 0, and

∇f 1 (x) = λ 0 e m ∈ F 1 , ∇f j (x) = 0 (j ≥ 2).

Moreover, we suppose k ≥ 1, k ∈ L i . Since

∇f j (x) = 2λ 1 B j B j x + 2λ 2 x -η j e m = 2λ 1 l∈Lj b l b l x + 2λ 2 x -η j e m .

Hence, ∇f i (x) ∈ F k+1 and ∇f j (x) ∈ F k (j = i).

Now, we turn to consider u = prox γ fj (x). We have

2λ 1 B j B j + 2λ 2 + 1 γ I u = η j e m + 1 γ x, i.e., u = c 1 (I + c 2 B j B j ) -1 y,

where

c 1 = 1 2λ2+1/γ , c 2 = 2λ1 2λ2+1/γ

, and y = η j e m + 1 γ x. Note that

(I + c 2 B j B j ) -1 = I -B j 1 c 2 I + B j B j -1 B j .

If k = 0 and j > 1, we have y = 0 and u = 0.

If k = 0 and j = 1, we have y = λ 0 e m . On this case, B 1 e m = 0, so u = c 1 y ∈ F 1 .

For k ≥ 1, we know that y ∈ F k . And observe that if |l -l | ≥ 2, then b l b l = 0, and consequently B j B j is a diagonal matrix, so we can assume that

1 c2 I +B j B j = diag(β j,1 , • • • , β j,|Lj | ). Therefore, u = c 1 y -c 1 |Lj | s=1 β j,s b lj,s b lj,s y,

where we assume that L j = {l j,1 , • • • , l j,|Lj | }.

Thus, we have prox γ fi (x) ∈ F k+1 for k ∈ L i and prox γ fj (x) ∈ F k (j = i).

Proof of Corollary 2.7. Denote

span{∇f i1 (x 0 ), • • • , ∇f it (x t-1 ), prox γ1 fi 1 (x 0 ), • • • , prox γt fi t (x t-1 )} by M t . We know that x t ∈ M t .

Suppose that M T ⊆ F k-1 for some T and let T = arg min t : t > T, i t ≡ k(mod n).

By Lemma 2.6, for T < t < T , we can use a simple induction to obtain that span{∇f it (x t-1 ), prox γt fi t

(x t-1 )} ⊆ F k-1 and M t ⊆ F k-1 . Moreover, since i T ≡ k(mod n), we have span{∇f i T (x T -1 ), prox γ T fi T (x T -1 )} ⊆ F k and M T ⊆ F k .

Following from above statement, it is easily to check that for t < T k , we have

x t ∈ M t ⊆ F k-1 .

Next, note that

P (T k -T k-1 = s) = P i T k-1 +1 ≡ k(mod n), • • • , i T k-1 +s-1 ≡ k(mod n), i T k-1 +s ≡ k(mod n) = P i T k-1 +1 = k , • • • , i T k-1 +s-1 = k , i T k-1 +s = k = (1 -p k ) s-1 p k ,

where k ≡ k(mod n), 1 ≤ k ≤ n. So T k -T k-1 is a geometric random variable with success probability p k .

On the other hand,

T k -T k-1 is just dependent on i T k-1 +1 , • • • , i T k , thus for l = k, T l -T l-1 is independent with T k -T k-1 .

Therefore,

T k = k l=1 (T l -T l-1 ) = k i=1 Y l ,

where Y l follows a geometric distribution with success probability q l = p l where l ≡ l(mod n), 1 ≤ l ≤ n.

Proof of Remark 2.3. If each f i is L-smooth, then for any x, y ∈ R m we have

∇f i (x) -∇f i (y) 2 2 ≤ L 2 x -y 2 2

, and consequently,

EQUATION

) If {f i } n i=1 is L-average smooth, then for any x, y ∈ R m we have ∇f (x) -∇f (y) 2 2 = 1 n 2 n i=1 (∇f i (x) -∇f i (y)) 2 2 ≤ 1 n 2 n i=1 ∇f i (x) -∇f i (y) 2 2 ≤ 1 n n i=1 ∇f i (x) -∇f i (y) 2 2 ≤ L 2 x -y 2 2 .

Proof of Lemma 2.9. Denote min x∈R m f (x) by f * . For t ≤ N , we have

Ef (x t ) -f * ≥ E[f (x t ) -f * |N < T M +1 ]P (N < T M +1 ) ≥ E[ min x∈F M f (x) -f * |N < T M +1 ]P (N < T M +1 ) ≥ 9εP (T M +1 > N ) ,

where T M +1 is defined in (7), and the second inequality follows from Corollary 2.7 (if

N < T M +1 , then x t ∈ F M for t ≤ N ).

By Corollary 2.7, T M +1 can be written as

T M +1 = M +1

l=1 Y l , where {Y l } 1≤l≤M +1 are independent random variables, and Y l follows a geometric distribution with success probability

q l = p l (l ≡ l(mod n), 1 ≤ l ≤ n). Moreover, recalling that p 1 ≤ p 2 ≤ • • • ≤ p n , we have M +1 l=1 q l ≤ M +1

n . Therefore, by Lemma 2.8, we have

P (T M +1 > N ) = P M +1 l=1 Y l > (M + 1)n 4 ≥ 1 - 16 9(M + 1) ≥ 1 9 , Hence, we can conclude that Ef (x N ) -f * ≥ 9εP (T M +1 > N ) ≥ ε.

Remark In fact, a more strong conclusion hosts:

E min t≤N f (x t ) -min x∈R m f (x) ≥ ε.

D RESULTS ABOUT SUM OF GEOMETRIC DISTRIBUTED RANDOM VARIABLES:

Lemma D.1. Let X 1 ∼ Geo(p 1 ), X 2 ∼ Geo(p 2 ) be independent random variables. For any positive integer j, if p 1 = p 2 , then

EQUATION

and if p 1 = p 2 , then

EQUATION

Proof.

P (X 1 + X 2 > j) = j l=1 P (X 1 = l) P (X 2 > j -l) + P (X 1 > j) = j l=1 (1 -p 1 ) l-1 p 1 (1 -p 2 ) j-l + (1 -p 1 ) j = p 1 (1 -p 2 ) j-1 j l=1 1 -p 1 1 -p 2 l-1 + (1 -p 1 ) j Thus if p 1 = p 2 , P (X 1 + X 2 > j) = jp 1 (1 -p 1 ) j-1 + (1 -p 1 ) j .

For

EQUATION

)

Proof. We just need to show that

(x + 1) j-1 (x + j/2) -(j -1)(x + 1) j-1 ≤ x j-1 (x + j/2),

that is

(x + 1) j -j(x + 1) j-1 /2 -x j-1 (x + j/2) ≤ 0, i.e., j-2 l=0 j l - j 2 j -1 l x l ≤ 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 X 1 ∼ Geo(p 1 ), X 2 ∼ Geo(p 2 ), Y 1 , Y 2 ∼ Geo p1+p2

2 be independent random variables with 0 < p 1 ≤ p 2 ≤ 1. Then for any positive integer j, we have

P (X 1 + X 2 > j) ≥ P (Y 1 + Y 2 > j) . Proof. If j = 1, then P (X 1 + X 2 > j) = 1 = P (Y 1 + Y 2 > j). If p 1 = p 2 = 1, then P (X 1 + X 2 > j) = 0 = P (Y 1 + Y 2 > j) for j ≥ 2.

Let j ≥ 2, and c p 1 + p 2 < 2 be a given constant.

We prove that f (p 1 ) P (X 1 + X 2 > j) is a decreasing function.

Employing equation ( 14), for p 1 < c/2, we have

EQUATION

EQUATION

) Note that c(1 -p 1 ) -j(c -p 1 )(c -2p 1 ) c(1 + p 1 -c) + jp 1 (c -2p 1 ) = 1 - (j -1)c(c -2p 1 ) c(1 + p 1 -c) + jp 1 (c -2p 1 ) = 1 - j -1 1+p1-c c-2p1 + j p1 c Denote x = 1+p1-c c-2p1 . If c ≤ 1, then p 1 > 0 and x > 1-c c ≥ 0. And if c > 1, then p 1 ≥ c -1 and x ≥ 1+c-1-c 2-c = 0. Rewrite inequality (17) as 1 - j -1 x + jp 1 /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 + jp 1 /c .

Consequently, f (p 1 ) < 0 hosts for p 1 < c/2 and j ≥ 2.

With the fact that lim p1→c/2 f (p 1 ) = f (c/2) according to equation ( 15), we have

P (X 1 + X 2 > j) ≥ P (Y 1 + Y 2 > j) .

for any positive integer j and 0 < p 1 ≤ p 2 ≤ 1.

Corollary D.4. Let X 1 ∼ Geo(p 1 ), X 2 ∼ Geo(p 2 ), Y 1 , Y 2 ∼ Geo p1+p2

2 be independent random variables with 0 < p 1 ≤ p 2 ≤ 1. Suppose Z is a random variable that takes nonnegative integer values, and Z is independent with X 1 , X 2 , Y 1 , Y 2 . Then for any positive integer j, we have

P (Z + X 1 + X 2 > j) ≥ P (Z + Y 1 + Y 2 > j) .

Proof. With applying Lemma D.3, we have

P (Z + X 1 + X 2 > j) = j-1 l=0 P (Z = l) P (X 1 + X 2 > l -j) + P (Z > j -1) ≥ j-1 l=0 P (Z = l) P (Y 1 + Y 2 > l -j) + P (Z > j -1) = P (Z + Y 1 + Y 2 > j) .

Corollary D.5. Let {X i } 1≤i≤m be independent variables, and X i follow a geometric distribution with success probability p i . For any positive integer j, we have

P m i=1 X i ≥ j ≥ P m i=1 Y i ≥ j , where {Y i } 1≤i≤m are i.i.d. random variables, Y i ∼ Geo( m i=1 p i /m), and Y i is independent with X i (1 ≤ i ≤ m). Proof. Let f (p 1 , p 2 , • • • , p m ) P m i=1 X i ≥ j . Our goal is to minimize f (p 1 , p 2 , • • • , p m ) such that m i=1 p i = S < 1. By Corollary D.4, we know that f (p 1 , p 2 , • • • , p i , • • • , p j , • • • , p m ) ≥ f (p 1 , p 2 , • • • , p i + p j 2 , • • • , p i + p j 2 , • • • , p m ).

This fact implies that

(p 1 , p 2 , • • • , p m ) such that p 1 = p 2 = • • • = p m = S/m is a minimizer of the function f .

Lemma D.6. Let {X i } 1≤i≤m be i.i.d. random variables, and X i follows a geometric distribution with success probability p. We have

EQUATION

Proof. Denote m i=1 X i by τ . We know that

Eτ = m p , Var(τ ) = m(1 -p) p 2 .

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) 9m 2 ≥ 1 - 16 9m .

Corollary D.7. Let {X i } 1≤i≤m be independent random variables, and X i follows a geometric distribution with success probability p i . Then

P m i=1 X i > m 2 4( m i=1 p i ) ≥ 1 - 16 9m .

E PROOF OF THEOREM 4.2

Proposition E.1. For any n ≥ 2, m ≥ 2, f SC,i and F SC in Definition 4.1 satisfy:

1. f SC,i is L-smooth and µ-strongly convex.

2. The minimizer of the function F SC is

x * = arg min x∈R m F SC (x) = 2∆n(α + 1) 2 (L -µ)(α -1) (q m , q m-1 , • • • , q) ,

where q = α-1 α+1 . Moreover,

EQUATION

)

Proof.

1. Just recall Proposition 2.5.

EQUATION

Note that q = α-1 α+1 is a root of the equation

z 2 -2 + 2nµ L -µ z + 1 = 0,

and

ω 2 + 1 + 2nµ L -µ = 1 q , 2 α + 1 = 1 -q = -q 2 + (1 + 2nµ L -µ )q.

Hence, it is easily to check that the solution to Equation ( 20) is

x * = ξ(q m , q m-1 , • • • , q) ,

and

F SC (x * ) = - L -µ 2n(α + 1) ξ 2 q = -∆. 3. If x ∈ F k , 1 ≤ k < m, then x 1 = x 2 = • • • = x m-k = 0.

Let y = x m-k+1:m ∈ R k and A k be last k rows and columns of the matrix in Equation ( 21). Then we can rewrite F (x) as

EQUATION

)

By some calculation, the solution to above equation is

EQUATION

min x∈F k F SC (x) -F SC (x * ) = ∆ 1 - 1 -q 2k 1 + q 2k+1 = ∆q 2k 1 + q 1 + q 2k+1 ≥ ∆q 2k .

Proof of Theorem 4.2. Let M = log(9ε/∆) 2 log q , then we have

arg min x∈F M F SC (x) -F SC (x * ) ≥ ∆q 2M ≥ 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 EF SC (x t ) -F SC (x * ) ≥ ε.

Therefore, in order to find x ∈ R m such that EF SC ( x) -F SC (x * ) < ε, A needs at least N queries to h FSC .

We estimate -log(q) and N in two cases.

1. If L/µ ≥ n/2 + 1, then α = 2 L/µ-1 n + 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

EQUATION

where the first inequality and second inequality follow from L/µ -1 < n/2 and the last inequality is according to 1

x-1 ≤ 2 x for x ≥ 2. Note that n ≥ 2, thus n n-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ε/∆ ≤ q 2 , 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

EQUATION

Note that lim β→+∞ h(β) = 0, so -1/ log(q) ≤ α/2. Thus the above conditions are satisfied when

EQUATION

ε ∆ ≤ 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 x t -x * 2 2 ≤ (q ) t x 0 -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 {f SC,i } n i=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 ∈ R m such that E x -x * 2 2 < ε x 0 -x * 2 2 , PIFO algorithm A needs at least Ω n + nL µ log 1 ε queries to h FSC . 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 x t -x * 2 2 ≥ E x t -x * 2 2 N < T M +1 P (N < T M +1 ) ≥ E min x∈F M x -x * 2 2 N < T M +1 P (N < T M +1 ) ≥ 1 9 min x∈F M x -x * 2 2 .

where T M +1 is defined in (7), the second inequality follows from Corollary 2.7 (if N < T M +1 , then x t ∈ F M 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 * = ξ(q m , q m-1 , • • • , q) , and

x 0 -x * 2 2 = x * 2 2 = ξ 2 q 2 -q 2(m+1) 1 -q 2 . Note that if x ∈ F M , then x 1 = x 2 = • • • = x m-M = 0, thus min x∈F M x -x * 2 2 = ξ 2 m l=m-M q 2(m-l+1) = ξ 2 q 2(M +1) -q 2(m+1) 1 -q 2 .

Thus, for t ≤ N and M ≤ m/2, we have

E x t -x * 2 2 x t -x * 2 2 ≥ 1 9 q 2M -q 2m 1 -q 2m ≥ 1 18 q 2M = 1 18 q 2 log(18ε) 2 log q ≥ ε,

where the second inequality is due to

q 2M -q 2m 1 -q 2m - q 2M 2 = q 2M -2q 2m + q 2(m+M ) 2(1 -q 2m ) = q 2M 2(1 -q 2m ) (1 -2q 2(m-M ) + q 2m ) ≥ q 2M 2(1 -q 2m ) (1 -2q m + q 2m ) ≥ 0.

Therefore, in order to find x ∈ R m such that

E x-x * 2 2 x0-x * 2 2 < ε, A needs at least N queries to h FSC .

As we have showed in proof of Theorem 4.2, for L/µ ≥ n/2 + 1, we have

EQUATION

N = n 4 (M + 1) ≥ n 4 log(18ε) 2 log q ≥ c 1 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 q 2 .

Observe that when L/µ ≤ n/2 + 1, we have α ≥ √ 2 and q = α-1 α+1 ≥

√ 2-1 √ 2+1 . Hence, we just need ε ≤ 1 18 √ 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. f C,i is L-smooth and convex.

2. The minimizer of the function F C is

EQUATION

Proof.

1. Just recall Proposition 2.5.

EQUATION

)

Hence, it is easily to check that the solution to Equation ( 25) is

x * = 2ξ L (1, 2, • • • , m) ,

and

F C (x * ) = - mξ 2 nL .

Moreover, we have

x 0 -x * 2 2 = 4ξ 2 L 2 m(m + 1)(2m + 1) 6 ≤ 4ξ 2 3L 2 (m + 1) 3 = B 2 .

3. By similar calculation to above proof, we have arg min

x∈F k F C (x) = 2ξ L (1, 2, • • • , k) ,

and

min x∈F k F C (x) = - kξ 2 nL .

Thus

min x∈F k F C (x) -F C (x * ) = ξ 2 nL (m -k).

Proof of Theorem 4.5.

Since ε ≤ B 2 L 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∈F M F C (x) -F C (x * ) = ξ 2 nL (m -M ) = 3B 2 4n m -M (m + 1) 3 ≥ 3B 2 L 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 EF C (x t ) -F C (x * ) ≥ ε.

In other words, in order to find x ∈ R m such that EF C ( x)-F C (x * ) < ε, A needs at least N queries to h F .

At last, observe that

N = (M + 1)n/4 = n 4 m + 1 2 ≥ n(m -1) 8 ≥ n 8 B 2 L 24nε -2 = Ω n + B nL ε ,

where we have recalled ε ≤ B 2 L 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 {g i } 1≤i≤n , g i : R → R, where

g 1 (x) = L 2 x 2 -nLBx, g i (x) = L 2 x 2 , G(x) = 1 n n i=1 g i (x) = L 2 x 2 -LBx.

First observe that

x * = arg min x∈R G(x) = B, G(0) -G(x * ) = LB 2 2 ,

and |x 0 -x * | = B.

For i > 1, we have dgi(x) dx | x=0 = 0 and prox γ gi (0) = 0. Thus x t = 0 will host till our first-order method A draws the component f 1 . That is, for t < T = arg min{t : i t = 1}, we have x t = 0.

Hence, for t ≤ 1 2p1 , we have

EG(x t ) -F (x * ) ≥ E G(x t ) -G(x * ) 1 2p 1 < T P 1 2p 1 < T = LB 2 2 P 1 2p 1 < T .

Note that T follows a geometric distribution with success probability p 1 ≤ 1/n, and

P T > 1 2p 1 = P T > 1 2p 1 = (1 -p 1 ) 1 2p 1 ≥ (1 -p 1 ) 1 2p 1 ≥ (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 ≤ 1 2p1 , we have

EG(x t ) -F (x * ) ≥ LB 2 4 ≥ ε Thus, in order to find x ∈ R such that EF (x) -F (x * ) < ε, A needs at least 1 2p1 ≥ n/2 = Ω (n) queries to h G .

Proof of Lemma 4.10. Note that {g i } n i=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 ε ≤ LB 2 /4. Note that {g i } n

i=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),

Proof of Theorem 4.9. Note that

ε ≤ √ 2 768 B 2 L √ n = B 2 L 384n , m = 4 √ 18 12 Bn -1/4 L ε -1 = B 2 L 24nε -1.

By Theorem 4.5, in order to find x ∈ R m such that EF C ( x) -F C (x * ) < ε, A needs at least N queries to h FC , where

N = Ω n + B nL ε = Ω   n + B n n/2L ε   = Ω n + Bn 3/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

EQUATION

J.1 PRELIMINARIES

We first introduce a general concept about smoothness. Definition J.1. For any differentiable function f : R m+1 → R, we say f is (l, L)-smooth, if for any x, y ∈ R m we have

l 2 x -y 2 2 ≤ f (x) -f (y) -∇f (y), x -y ≤ L 2 x -y 2 2 ,

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 2 2

is a convex function.

Next, we introduce a class of function which is original proposed in (Carmon et al., 2017) . Let G NC : R m+1 → R be

G NC (x; α, m) = 1 2 B(m + 1, 4 √ α)x 2 2 - √ α e 1 , x + α m i=1 Γ(x i ),

where the non-convex function Γ : R → R is

EQUATION

We need following properties about G NC (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 G NC (x; α, m) is (-45( √ 3 -1)α, 4 + 180α)- smooth. 2. G NC (0; α, m) -min x∈R m+1 G NC (x; α, m) ≤ √ α/2 + 10αm.

3. For x which satisfies that x m = x m+1 = 0, we have ∇G NC (x; α, m) 2 ≥ α 3/4 /4.

J.2 OUR RESULT:

Theorem J.3. For any PIFO algorithm A and any L, σ, n, ∆, ε such that ε 2 ≤ ∆Lα 81648n , there exist a

dimension d = ∆L √ α 40824nε 2 + 1 and n (-σ, L)-smooth nonconvex functions {f i : R d → R} n i=1 such that f (x 0 ) -f (x * ) ≤ ∆. In order to find x ∈ R d such that E ∇f ( x) 2 < ε, A needs at least Ω ∆L √ α ε 2 queries to h f , 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 (Zhou and Gu, 2019) .

1 + ∆ ε 2 min{L/n, σL/n} , which is much smaller than O ∆ ε 2 min{L, √ nσL} in

EQUATION

Similar to our construction we introduced in Section 2, we denote the l-th row of the matrix B(m + 1, 4 √ α) by b l and

EQUATION

EQUATION

)

Clearly, F (x; α, m, λ, β) = 1 n n i=1 f i (x; α, m, λ, β). Moreover, by Proposition J.2, we have following properties about F (x; α, m, λ, β) and {f i (x; α, m, λ, β)} n i=1 . Proposition J.5. For any 0 < α ≤ 1, it holds that 1. f i (x; α, m, λ, β) is -45( √ 3-1)αλ β 2

, (2n+180α)λ β 2 -smooth.

2. F (0; α, m, λ, β) -min x∈R m+1 F (x; α, m, λ, β) ≤ λ( √ α/2 + 10αm).

3. For x which satisfies that x m = x m+1 = 0, we have ∇F (x; α, m, λ, β) 2 ≥ α 3/4 λ 4β .

Similar to Lemma 2.6, similar conclusion hosts for {f i (x; α, m, λ, β)} n i=1 . Lemma J.6. For x ∈ F k , 0 ≤ k < m and γ < For k = 0, we have x = 0, and ∇f 1 (x) = λn √ α/β e 1 ∈ G 1 , ∇f j (x) = 0 (j ≥ 2).

For k ≥ 1, we suppose that m -k ∈ L i . Since where η 1 = λn √ α/β, η j = 0 for j ≥ 2. Hence, ∇f i (x) ∈ F k+1 and ∇f j (x) ∈ F k (j = i). Now, we turn to consider v = prox γ fj (x).

We have 

EQUATION

Lemma J.8. Suppose that 0 < λ 2 < (2 + 2 √ 2)λ 1 , then z = 0 is the only real solution to the equation

EQUATION

Proof. Since 0 < λ 2 < (2 + 2 √ 2)λ 1 , we have

λ 2 2 -4λ 1 (λ 1 + λ 2 ) < 0,

and consequently, for any z, (λ 1 + λ 2 )z 2 -λ 2 z + λ 1 > 0.

On the other hand, we can rewrite Equation (34) as

z (λ 1 + λ 2 )z 2 -λ 2 z + λ 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 z 1 = z 2 = 0 is the only real solution to the equation

EQUATION

Proof. If z 1 = 0, then z 2 = 0. So let assume that z 1 z 2 = Rewrite the first equation of Equation ( 35) as

λ 1 + λ 3 λ 3 + λ 2 λ 3 z 1 (z 1 -1) 1 + z 2 1 = z 2 z 1 Note that 1 - √ 2 2 ≤ z(z -1) 1 + z 2 .

Thus, we have

λ 1 + λ 3 λ 3 + λ 2 λ 3 1 - √ 2 2 ≤ z 2 z 1 .

Similarly, it also holds

λ 1 + λ 3 λ 3 + λ 2 λ 3 1 - √ 2 2 ≤ z 1 z 2 .

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 z 1 /z 2 > 1 and z 2 /z 1 > 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. 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 h F .

Proof. First, note that f i is (-l 1 , l 2 )-smooth, where

l 1 = 45( √ 3 -1)αλ β 2 = 45( √ 3 -1)L 3n α ≤ 45( √ 3 -1)L 3n ( √ 3 + 1)nσ 30L = σ, l 2 = (2n + 180α)λ β 2 = L 3n (2n + 180α) ≤ L.

Thus each f i is (-σ, L)-smooth.

Next, observe that With recalling Lemma J.10, in order to find x ∈ R m+1 such that E ∇F ( x) 2 < ε, PIFO algorithm A needs at least N queries to h F , where

F (x 0 ) -F (x * ) ≤ λ( √ α/2 + 10αm) = 1944nε 2 Lα + 38880nε 2 L √

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.

:

SVRG, 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.

Lan 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.

Defazio (2016) proves Point SAGA requires O ((n + √ κn) log (1/ε)) PIFO calls to find x such that E xx * 2 2 < ε x0 -x * 2 2, 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 xx * 2 2 < ε x0 -x * 2 2 in Theorem F.1.

4 IFO algorithm is apparently also a PIFO algorithm.

By the proof of Theorem 4.2, a larger dimension m does not affect the conclusion of the theorem.

Figures and Tables:

∇f i (x; α, m, λ, β), prox γ fi (x) ∈ G k+1 , if k ≡ i -1(mod n), G k , otherwise. Proof. Let G(x) m i=1Γ(x i ) and Γ (x) be the derivative of Γ(x).

note that Γ (0) = 0, so if x ∈ G k , then∇G(x) = Γ (x 1 ), Γ (x 2 ), • • • , Γ (x m ) ∈ G k . Moreover, for x ∈ F G (k ≥ 1), we have b l x = 0 for l < m -k, b l ∈ G k for l > m -k, b m-k ∈ G k+1 . Consequently, for l = m -k, b l b l x = (b l x)b l ∈ G k , and b m-k b m-k x ∈ G k+1 .

β) -η j e 1 ,

s satisfies s > max{1, k} for j = 1, s > k for j > 1,

Lemma J.10. If M ≥ 1 satisfies min x∈G M ∇F (x) 2 ≥ 9ε and N = n(M + 1)/4, then we havemin t≤N E ∇F (x t ) 2 ≥ ε.



Table content: <table/>

Peer review (iclr2020):
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 *prox query* solving a regularized optimization problem for the chosen summand at the chosen point. For different classes of functions obtained through smoothness and (strong) convexity constraints, the lower bounds are on the number of queries needed by an algorithm to guarantee to approximate the minimum. The main result is for the case that the summands are mu-strongly convex and L-smooth. Bounds for this case are often given in terms of kappa = L/mu. An upper bound of O( (n + sqrt(kappa n) ) log(1/eps)) is known, and [1] had proved a lower bound of Omega( n + sqrt(kappa n) log(1/eps)), which matches the second term of the upper bound, but leaves a log-factor gap for the first. This paper proves an Omega( (n + sqrt(kappa n) ) log(1/eps)) lower bound, but for a restricted class of algorithms that fix a probability distribution over the summands ahead of time, and randomize by repeatedly sampling independently at random from this fixed distribution. The iterates of the algorithm are also constrained to be in the span of the answers to previous queries. Thus, this new result is incomparable in strength with the result in [1]. Also, the authors of this paper mention early in the paper that kappa is often large relative to n. But even if kappa is on the same order as n, the second term of the upper bound dominates the first, and is matched by the lower bound in [1]. The authors point to some new techniques in their analysis. I can see some new elements, but my knowledge of the previous work in this area is not deep enough to evaluate technical novelty very well. I have some question about the extent to which this work is in scope for ICLR. An argument could go that since stochastic gradient methods are so important to deep learning, study of the foundations and limitations of those methods is in scope. But a lower bound for the convex case seems to be stretching this a little far. This seems like a somewhat incremental contribution that would be of interest to a smallish subset of ICLR attendees. [1] Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objectives. In NIPS, 2016.