A Novel Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
Authors: Guangzeng Xie
Luo Luo
Zhihua Zhang
Venue:  (2020)
Keywords: convex optimization
lower bound complexity
proximal incremental first-order oracle

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 $\eps$-suboptimal point in fewer than $\Omega((n+\sqrt{\kappa n})\log(1/\eps))$ iterations, where $\kappa$ 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.

Under review as a conference paper at ICLR 2020
A NOVEL ANALYSIS FRAMEWORK OF LOWER COM- PLEXITY BOUNDS FOR FINITE-SUM OPTIMIZATION
Anonymous authors Paper under double-blind review
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 algo- rithm can not reach an e-suboptimal point in fewer than S2((n + /Kn) log(1/s)) iterations, where the condition number 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 novel construction show the above result, which partitions the tridi- agonal matrix classical examples into n groups to make the problem difficult enough to stochastic algorithms. This construction is friendly the analysis of proximal oracle and also could be used in general convex and average smooth cases naturally.
INTRODUCTION
We consider the minimization of the following optimization problem
min f(x) A fi(m)
(1)
=ER
where the (x) are L-smooth and μ-strongly convex. Accordingly, the condition number is defined as π. L/μ, which is typically larger than n real-world applications. Many machine learning models can be formulated as the above problem such as ridge linear regression, ridge logistic re- gression, smoothed support vector machines, graphical models, etc. This paper focuses on the first order methods for solving Problem (T), which access to the Proximal Incremental First-order Oracle (PIFO) for each individual component, that is,
hy (2, () & Vf(e))
Vf())) prox) (z))
where i E (1,...,m.,,? 0, and the proximal operation is defined
prox (x) = arg min [s(u)) + 27 || 11
We also define the Incremental First-order Oracle (IFO)
g,( A [fi()), ff(
PIFO provides more information than IFO and it would be potentially powerful than IFO in first order optimization algorithms. Our goal is to find an e-suboptimal solution such that
f(t) min f(x) S
mER
by using PIFO or IFO.
There several first-order stochastic algorithms to solve Problem 1I. The key idea lever- age 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)

---

Under review as a conference paper at ICLR 2020
find an E-suboptimal solution in (( (1g(//) IFO calls, while the complexity of the clas- sical Nesterov's acceleration (Nesterov 1983) is (og(///g((/))) Similar results also hold for SAG (Schmidt al., 2017) and SAGA (Defazio et al.) 2014). In fact, there exists celerated stochastic gradient method with v dependency. Defazio (2016) introduced a simple and practical accelerated method called Point SAGA, which reduces the iteration complexity to O((n + VKn) log(1/E)). 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 (017)) proposed the Katyusha momentum to accelerate variance reduction algorithms, which achieves the same iteration complex- ity 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 2al7| Lan and Zhou 2017, /hoo and Gu 2019). Specifically, |Lan and Zhou (2017) showed
that at least ( /Ke) (og() IFO calls" are needed to obtain an e-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++ / log (1/()) for PIFO algorithms, while the known upper bound of the PIFO algorithm Point SAGA [3] is ((n+vKn)) log(1/E)). 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 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 kn log( (l=)) for smooth and strongly-convex fi. which means the existing Point-SAGA (Defazio 2016) has achieved optimal complexity and PIFO can not lead to tighter upper bound than IFO. We provide 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 -Allen-Zhu 2018 Zhou and Gu 2019). and extend our result to non-convex problems (see Appendix().
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 IR
f is convex, for any x. y E R.T it satisfies f(y) 2 f(x) + (Vf(x), xx).
f is u-strongly convex, for any x, E R. it satisfies
f(y) 2 f(x) + (VI(x). y x) 1
f is L-smwoth, for any a. y E T it satisfies ( - VS(2) S L|| yy12.
!SVRG, SAG and SAGA only need to introduce the proximal operation for composite objective, that is. (x gx(x) + h(2).. where h may be non-smooth. Their iterations only depend on IFO when all the fi()) smooth. Hence, we regard these algorithms only require IFO calls in this paper.
LLan and Zhou construction requires f to be u-strongly convex and every fi to be convex, while this paper studies the lower bound with stronger condition that is every fü is j--trongly convex. For the same lower bound complexity, the result with stronger assumptions on the objective functions is stronger.
2

---

Under review as a conference paper at ICLR 2020
Uper Bounds
Previous Lower Bounds
Our Lower Hounds
Si L-smooth and j-strongly convex with (m)
O ((re + v /en) log(? 2))
Q (n /km log())
5 ((n v van) log( +))
Allen-Zhu
2017 IFO
Woodworth and Srebro 2016)
[Theorem 3.1
Detazio 2016), PIFO
PIFO
fi I-smooth and s-strongly convex with K ((n)
O
log (2)
n
log (:)
Ω 2nt ( (log #
log
(- logt # 1
14 log # )
Hannah et al.
2018
Hannah et al.
2018
[Thcorem 3.1
IFO
IFO
PIFO
m logg ) + Allen-Zhu
n.
Ω
a. + (Theorem
fi I-smooth and convex
2017
Woodworth and Srebro
2016)
3.3
11:0
PIFO
PIFO
[fi)= is L-average smooth and is p-strongly convex
n n Vx
log (t)
Ω n2 V (+)
② ( n n v log (1)
AAllenZhhu
2018
Zhou and Gu 2019)
(Theorem 3.5
IFO
IFO
PIFO
[ is L-average smooth and f is convex
11 + 11
Ω
+ n2
V
I
11 + n [Theorem 3.7 PIFO
Allen-Zhu 2018
Zhou and Gu 2019)
IFO
IFO
Table 1: We compare our PIFO lower bounds with existing results 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 (fA Sa Rm + IR, to be L-average smooth if for any x, y E Rm they satisfy
n
Vi((()) - - S 1,2 1|1 - y1
(3)
Remark 2.3. We point out that if each fi is L-smooth, then (fi are L.-average smooth.
2. if (Ji} are L-average smooth, then f(x) = fi(w)) is L-smooth.
We present the formal definition for PIFO algorithm.
Definition 2.4. Consider stochastic optimization algorithm to solve Problem (7). Let a, be the point obtained at time-step i and the algorithm starts with Zn- The algorithm A is said to be PIFO algorithm for any 2 0, we have
E span { (Zo...... Et-1, V (Zu), (x,-11))) prox7;, (zo). ... .prox 7, (II-1)), (4)
where is a random variable supported on [n] and takes P(ir = j) Pj for each > and 1 S I n where 1; =.
Without loss of generality, we assume xo = and pl S P2 < ... < Pr. to simplify our analysis. Otherwise, we can take (f) = fa( + b into consideration. On the other hand, suppose < Ps,, where h is a permutation of [n]. Define (f such that Js, ft. then A takes component fa, in probability ps;: i.e., A takes in probability Ps.-
that Psj Psa
3

---

Under review as a conference paper at ICLR 2020
To demonstrate the construction of adversarial functions, we first introduce the following class of matrices:
1
Bmm,w)= =
E IR mm
Then we define
w +1
-1
2
w), & B(m,w) B(m,w)=
(5)
-1 2
11
The matrix A(m, w) is widely-used in the analysis of lower bounds for convex optimization (Nes-
terov 2013 Agarwal and Bottou, 2015 Lan and Zhou 2017: Carmon et al. 2017 Zhou and Gu
2019)
We now present a decomposition A w) based on Eq. (5)
Denote the 1-th row of the matrix B(m, w) by (m, and let
C, = { 1 S 1 S m, | = i - 1(mod m)}: i= 1,2,
Our construction is based on the following class of functions
r(x; Au, A1, X2 m. w) & Σ ra Au A2, m, w),
where
A1
()) 20112 λa |2e1| Aa(em, x)) for
ra(;;; da de,
1E61
(6)
Σ
(m), seli2 2 Aa |=
for 2,3, ,m..
IEC,
We can determine the smooth and strongly-convex coefficients of r, as follows.
Proposition 2.5. For any \ 0, A2 2 0. w < 22, we have that the r, are (4X1 + 222))
and st-sonoggy convex, and {r. 1 is L' L'vvraee smooth where
[(11 + + L' = 2
We define the subspaces
{& Jmm
k= as
Fx spann (m,; Em-1, Em-k+th for < k S m, for 0.
((0).
The following technical lemma plays crucial role in our proof.
Lemma 2.6. For any do f 0, > 0, A2 2 and x E FR, 0 S m. we have that
Fa+1,
if 1 [mmd n),
Vr:(x; Ao. d1. A2 w. and prox?, (x) E
Fk.
otherwise.
In short, if x F& and let f((z) ræ Ao d1, w)), then there exists only one {1...., n. such that ha( i, could (and only could) provide additional information in FK+1- The "only one" property important to the lower bound analysis first order stochastic optimization algo- rithms (Lan and Zhou, 2017 Zhou and Gu 2019), but these prior constructions only work for IFO rather than PIFO.
Lemma 2.6 implies that 0 will host until algorithm A draws the component fi. Then, for any t < Ti min i, = 1}. we have Φ; E Fo and Φ2, E Fi. The value of Ti can be regarded as can define T₃ to be the smallest integer
the smallest integer such that æ7, could host. Similarly, such that VT, E F₁ could host. We give the formal definition of T3 recursively and connect it to geometrically distributed random variables in the following corollary.
4

---

Under review as a conference paper at ICLR 2020
Corollary 2.7. Let
To 0, and Tę = minft:: t> 1 & (mod n)} for k 2 1.
Then for any h 2 and t < Th, we have at E Fk-1- Moreover, Tr can be written as sum of k independent random variables {Yi)ssskk i.e, T. Σi= Y. where Yi follows geometric distribution with success probability q1 pv where = (mod n), S n.
The basic idea of our analysis is that we guarantee the minimizer of lies in Fm and assure the PIFO algorithm extend the space of span(20.. 21.......... ..)
slowly with increasing. We know that span (Zu, 21, ................................ ITy C F& by Corollary 2.7 Hence, T3 is just the quantity that reflects how span (ann(Zo, (n 21 2,,... Ft verifies. Because Tę can be written as the sum of geometrically distributed needs to introduce
random variables, lower bounds of our construction.
properties of such random variables which derive the
Lemma 2.8. Let {Yi)sisN be independent random variables, and Y; follows a geometric distri- bution with success probability pi. Then
N
N2
16
P
Σ
Y
2
(8)
4( i
9N
From Lemma 2.8] the following result implies how many PIFO calls we need.
Lemma 2.9. If M 1 satisfies min f(x) min f(x) 2 9e and N n(M + 1)/4 then we have
min (xxx) S
min f(x) 2..
MAIN RESULTS
We present the lower bound results for PIFO algorithms and summarize all of results in Table and [
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, M4, n, A such that k. = L/P 2 2, and e/A S 0.5, there exist a dimension = (1+ f log (A/e) and n. L-smooth and p-sstrongyy
convex functions {Ea Rdd + [ such that [(00 f(x'' = A. In order to find & E IRd such that (.)( f(x') ) < e, A needs at least N queries h where
1 ((n+ (rEn)) log (A/E)),
for n =(()),
N 2 n (1=(OR(m/W)) log (A/e)). for K. O(n).
Remark 3.2. In fact, the lower bound Theorem 3. algorithu Point SAGA (Defazio 2016 in p.teremmmmppppeeeeeee perfectly match the upper bound of the PIFO (K) case and match the the upper bound of the IFO algorithu prox-SVRG HHannah et al. 2018 in K (n) case. Hence, the lower bound in Theorem 3.1 is tight, while Woodworth and Srebro (2016) only provided lower bound Q. int//nn log (1/e)) in = (K)) 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 same lower bound for IFO algorithms.
Next give the lower bound when the objective function is strongly-convex. Theorem 3.3. For any PIFO algorithm A and any L, n, B, such that S LB² 1B2/4, there exist a dimension d O
LVLL/(e)) and n L-smooth and convex functions {.fs .dd + R)
such that 1o x² S B. order to find & RRd such that Bf(() [(x*) < e, A needs at least
a+ B B nLje
queries to hy.
Defazio 2016 proves Point SAGA requires O ((n + VRn) log (1/e)) PIFO calls find & such that El xx 1|.. which is identical to the condition Ef(() f(x*) However, it is unnecessary to worry about it because we also establish a PIFO lower bound
El
The-
orem
2 (n
Kn) log (1/e)) for El x I|2 < el|mzo x²1 l|ž in Theorem F11
IIO algorithm is apparently also PIFO algorithm.
5

---

Under review as a conference paper at ICLR 2020
Remark 3.4. The lower bound in Theorem 3.3 is the same the of Woodworth and Srebro's
result. However, our construction only requires the dimension be O 1 B L/ L/(ne), which is much smaller than 1 log
mL.3²
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.
L/u > /3/m (2 + +1), and e/A 0.00327, there exist a dimension d O (n 1/4 VMAV/oloog (A/e)) and n functions {fs: R2 + R where the {fr]i= are L-average smooth and f is p--ttronlyy convex, such that (3:0) - f(xx) A. order to find TRd such that E.f(a)) - f(x') < E, needs at least (nn+n//4 VV: log (A/E) queries to h--
Theorem 3.5. For any PIFO algorithm A and any T,, pb, n, A such that
Remark 3.6. Compared with Zhou and Gu's lower bound 9t (n n/3 VR log (A/=)) for IFO al- gorithms, 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 S LB²/44 there exist dimension O Bn-1/1
T//e) and n functions {fi Rd + R which the (fi)== are
L-average smooth and f is convex, such that 1,00 x=" lla S B. In order find Rd such that x=112
(f(()) f(x") < A needs at least (n+ B/ v L/e queries to hj.
Remark 3.8. The lower bound in Theorem 3.7 is comparable to the one of Zhou and Cuis result, but our construction only requires the dimension be O
1 Bn Bn-1/A VLfE) which is much smaller
than O Bn²/4 VL/E) in Zhou and Gui 2019.
4 CONSTRUCTIONS IN PROOF OF MAIN THEOREMS
We demonstrate the detailed constructions for PIFO lower bounds in this section. All the omitted proof this section can be found Appendix for detailed version.
4.1 STRONGLY CONVEX CASE
The analysis of lower bound complexity for the strongly-convex case depends on the following construction.
/211/111) We define fsc.s R - R as follows
Definition 4.1. For fixed L, μ4, A, let a
2(L - pmn
L- 11 p
fxc =
Σ;
1
(9)
a-1 1 4 2
+11
and
Fsc(x:)
A
Σ 1=1
Jsc.
B m.
2
/ + 2
| 2
2(T. 14/ n1a - 1) (e,, 2.)
4n
Note that the fsc,; are T-smooth and j-strongly convex, and Fsc( (2)))) Fsc (x=" A (see Propo- Appendix for more details). Next we show that the functions [ssc, } are "hard enough" Tor any PIFO algorithm A, and deduce the conclusion of Theorem 3.1
sition E.
Theorem 4.2. Suppose that
A
1)² 2
and 1 2122/111
L/2L/u--
A 95
+ log
+ 1,
a aa+1)

---

Under review as a conference paper at ICLR 2020
where v / algorithm AA needs least N queries to f where
1. In order find æ E m such that EFsc(E) Fse(x') < e, PIFO
1 + Ω
12
log
for 2 2 +
N
n
[togg(ap/ LJ log ())),
for 2 v < < +1
For larger E, we can apply following Lemma.
Lemma 4.3. For any PIFO algorithm A and any L. n, A. such that A/2, there exist L-smooth and p-strongly convex functions {fe + R such that F(xo) - F(x) S A. In order find & E IR such that EF F(x*) < E, needs at least Mi)) queries hp.
As explain in Remark H.1 the lower bound in Lemma same the lower bound in Theorem for
2
In conclusion, we obtain Theorem 3.1
4.2
CONVEX CASE
The analysis of lower bound complexity for non strongly-convex depends the following construction.
Definition 4.4. For fixed L, B, n, we define fc,:
R + R as follows
v/3 BL
L
[c,(æ))= = -r v
0, 0,
(10)
(m
1)3/2' 4
and
v3 2 (m + 1)3/2n2
BI.
Fc(x) & Σ (c) 4n
| [m,
1)
(em x).
Note that the fc,; are L-smooth and convex, and ||00- for more details). Next we show the lower bound for functions fc,, defined above.
x 11 S B (see Proposition G. Appendix
Theorem 4.5. Suppose that
B and 384n
B
1.
24ne
In order to find ã Th. such that -Fc(()) e, Aneeds at least Ω (n+ BV AL
queries
to hipe
To derive Theorem 3.3 we also need the following lemma in the case
B
384n
Lemma 4.6. For any PIFO algorithm and any L, n, B, such that < LB2 /4, there exist L-smooth and convex functions {f: R + R] such that 22o x=1 I B. In order to find à e IR
such that (F F(x*) E, A needy at least ((1)) queries to hp.
It is worth noting that if
B'L 384n
then 2(n) Ω (n + B
Thus combining Theorem 4.5
and Lemma 4.6 we obtain Theorem 3.3
4.3 AVERAGE SMOOTH CASE
Zhou and Gu (219) established lower bounds of IFO complexity under the average smooth assump- tion. Here we demonstrate that our technique can also develop lower bounds PIFO algorithm under this assumption.

---

Under review as a conference paper at ICLR 2020
4.3.1 F IS STRONGLY CONVEX
For fixed ,,, n, we set I. n1 22) n?, and consider (/sc,))== and Fsc defined in
Definition 411
Proposition 4.7. For n 2 2, we have that
(sc(a)) y-sttrongly convex and (/s is -average smooth.
2. 1f 2 22.0 +12+1),, 1), then we have / I' L S V and L/p 2 n/2
Theorem 4.8. Suppose that
L'
A
V2 1
1
22
L +1
A
2 n
+
E
and m 4 (V
log
v2
+
9E
In order to find & E Rn such that EFsc(() Fsc(x*) < E, PIFO algorithm A needs at least
Q ((n (n+ n3/11 v#) log (+) queries to hrse
4.3.2 F CONVEX
For fixed L', B,n,E, we set L L=VVLL and consider {fc.i]/=1 and Fc defined in Definition 4.4 It follows from Proposition 2.5 that [fc is L'aaveage smooth.
Theorem 4.9. Suppose that
V2 L' and m
V18
L'
Bn
1/4
1
768 Vn
12
In order to find & E Rm such that EFc(() Fe(x*) < E, A needs at least Q (n+ Bn3/44 V
queries to F
Similar to Lemma 4.6 also need the following lemma for the
J B²
708 vn
Lemma 4.10. For any PIFO algorithm A and any L, n, B, e such that LB /B/ there exist functions {f+ R + R which is L-average smooth, such that F(x) is convex and I| - 22 S B. In order find & E R such that (F (f) F(x*) ) < E, needs at least 22n) queries to hg.
Similarly, note that if E Theorem
v B"L then I(n) = Ω (n+ 3/3/4 V4 708
V
In summary, we obtain
5 CONCLUSION AND FUTURE WORK
In this paper we have studied lower bound of PIFO algorithm for smooth convex finite-sum optimiza- tion. We have given tight lower bound of PIFO algorithms in the strongly convex case. We have proposed 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 (o, smsmmohhsssss while each f. is (1, -msooohhsesss.
REFERENCES
Alckh Agarwal and Leon Bottou. A lower bound for the optimization of finite sums. In JCML, 2015.
Zeyuan Allen-Zie Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(1):8194 8244, 2017.
8

---

Under review as a conference paper at ICLR 2020
Zeyuan Allen-Zhu. Katyusha X: Practical momentum method for stochastic sum-of-nonconver optimization. In JCML, 2018.
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In NIPS, 2015.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. arXiv preprint IrXiv:/7100 1606, 2017.
Aaron Defazio. A simple practical accelerated method for finite sums. In NIPS, 2016.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julics 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 aath-integrated differential estimator. In NIPS, 2018.
Robert Hannah, Yanli Liu, Daniel Connorr 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 2(1/k2)). 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):33-112,, 2017.
Blake Woodworth and Nathan Srebro. Tight complexity bounds for optimizing composite objec- tives. In NIPS, 2016.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number inde- pendent access of full gradients. In NIPS, 2013.
Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. In ICML, 2019.

---

Under review as a conference paper at ICLR 2020
A COMPARISON OF REQUIRED NUMBER OF DIMENSIONS
Previous Lower Bounds
Our Lower Bounds
#PIFO ! (n + (nrllo(())
#PIFO Ω ((n + viS)) log(
fi is L-smooth and ju-strongly convex
d = O log
d = O (v / log (1))
Woodworth and Srebro 2016
[Theorem 3.1
#PIFO
n2 +
nL.
#PIFO Ω O
mL
fi is L-smooth and convex
d = O
( log
(
Woodworth and Srebro 2016)
[Theorem 3.3]
#IFO (n + 3/4 log (1)
#PIFO Q ((n n Vki log (1)
(iNE=1 L-average smooth and is j--strongly convex
= O (n + n 3/1 te log (2)
d= (n-1/1 log (1
(Zhou and Gu. 2019)
[Theorem 3.5
#IFO 9 12 + 3/4
#PIFO S2 n2 + 1
(fii is L-average smooth and f is convex
d= O
nn
L
d == O n1+ 1/4
11
Zhou and Gu 2019)
[Theorem 3.7
Table 2: We compare our PIFO lower bounds with previous results, including the number of PIFO or IFO calls to obtain e-suboptimal point and the required number of dimensions in corresponding construction.
B COMPARISON WITH EXISTING PROOFS
Recall the adversary function we used is (please see detailed defintion Section
a
r(x; Ao, A2, A2, m, w)
ra; Ao A2, m,
(11)
12
X1 w x A2 11012 n
do (em. x),
A (m,
(12)
n
where
A1
Σ
b) w)
x:
\o m), for = 1, A2 ||
ri(m; d2,
TEC
A1
x
||ا1
for 2, 2......,
IEC
The constructions in previous work Lan and Zhou 2017 Zhou and Gu 2019) for IFO algorithms employ an aggregation of that is,
f(x)
f((x), where fi(x)) = nr(x;),
n
42
E R mm and æ; E I.mh for = 1,..., n.
10

---

Under review as a conference paper at ICLR 2020
The disadvantage of their construction is in that the important property from Lemma 2.6 which 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 (TT) 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 (IT). Moreover, the fact I IR and f R + I provide an intuitive understanding why our construction requires a smaller dimension (see T
The analysis in (Woodworth and Srebro 2016 Lang et al., 2018) considers a very complicated approach to dealing with the proximal operator (completely different from how 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 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 x (()). which is new result.
C DETAILED PROOF FOR SECTION 2
In this section, we use |||] to denote the spectral radius of A. For simplicity, let
-1
1
B == Bm,
E muxm
6,7 is the I-th row of B, and f(()) rx( Ao d1, 22,
Recall that
C. (1: 11:1:15 S m, == ((modn)) ), 1,2, 2..
...,.. ,n.
For sis n, let B, be a submatrix which is formed from rows L; of B, that
B. B[C;)
Then Si can be wriiten
Aa ||01| me(em, x), f((x) X |
where 7)
Ap 7/: 2. 2.
Proof of Proposition 2.5
Note that
(u, B, B,u)
B 2
Σ
(b, u)²
L.C.
Σ Eieci/Amp (2m- - 2 2 (if m E La)
Elech (um-1 1m-1-1)2
< uul2
where the last inequality according to (x+y)² < 2(x=+++²) and 14 -11 2 n 2 2 for
40,4 for
Ci.
Hence, BB B,|| < 2, and
V f()]| = =|2 B, B.+ 212 < 4A1 + 222-
Next, observe that
[v)())- v
= B, 22² - -))l2
11

---

Under review as a conference paper at ICLR 2020
Let
y.
Note that
(um-i- um (m--+)mmmmmm-- em-141), I << m, uuuree,
b,b,
1 = m.
Thus, m $ Ci. then
((2) B, B, + 222
= 2A1 Σ
Um-1 - Um - 22zu
- emm-4+)) +
lE4;
2
Σ
[12)1 - - + 222u))2 (-2X1 (w m411) 222241)3
Σ
(2)2u)²
m-1EC,
m- IEC.
m m-I+1fL
S Σ 8 +2) + 13] (ut + ubt1) + 1211
m-IEE
Similarly, if m E Li, then
(2)) BT B; 222l)
Σ 8 [((1 + 22) + x7] (uf 2241) + 4(Aiw2 ~22) + +42211 11
mR IcL
140
Therefore, we have
1
Vf((x) V)(())1
7
m-1
8 [(1 + A2)2 + XH] (uf + u241) + 4(2)) + 22)
+ +x2 2/
1
16
[(1 )²)² >H] 1 + 423 || 12
where we have used (2\1 + 2²)² < (A1 A2)² + X In summary, we get that ifiissinn is L' average smooth, where
4
L' = 2 [(1 (A1++12)* 12)2 + X3.
Proof of Lemma 2.6 For x E Fx (k: 2 1), we have
b. 0 > k.
b, E Fx for < k.
b Fat1-
Consequently, for * k. b,b, x = (bJ x) b) E Fu, and bab x E FRt
For A: = 0, we have 0, and
(z((2) Apen E Fr. (z)(x) 0 (j 2).
12

---

Under review as a conference paper at ICLR 2020
Moreover, suppose & 2 1, k L.. Since
Vfy(2) = Bi B, + 22g T} em
= 22 Σ bi bia: 222x nmc
LEC,
Hence, ff())) Fkt1 and (z) Fi (j + t).
Now, turn to consider = prox}, (x)). We have
B2 Bj + 2\ ))
1 1) u mm
i.e.,
= (I + 02 Bj BB) B y,
where C1 222+1/7.
2 2/a+1/7
and y = em + a.
Note that
(I + BB BJ. ( Bj.
à and j > 1, we have = 0 and u 0.
If A: 0 and] j we have y Am On this case, Bicm 0, 01 E F1.
For &: 2 1, we know that y E Fx. And observe that 1-- -1' 2 2, then bj by = 0. and conse-
quently BJ is diagonal matrix, so we can assume that 1 I B, = diag(33.1, .. B,,cc,)) Therefore,
Leyl
B b T y
u ciy
where assume that C, "1,,,, 3/11,1
Thus, have prox?, (x) E Fut1 for ls La and prox?, (x) Fi (1.
Proof of Corollary 2.7 Denote
span fü (zo). fi, (x, (z)-1), prox]], (zo). ... prox (x,-1)}
by Mr. We know that æ; E Mr.
Suppose that Mr C FR-1 for some T and let = arg min t: >> T, i = k(mod n).
By Lemma 2.6 for T < < T",
simple induction obtain that span V (#1-1), prox] (#+-1)} C Ft-1
and M, FR-1- Moreover, since in = k( 6(modd)) n), we have
span ( Sip (xT 11, prox fige (ITT C FF
"t'
and My FR.
Following from above statement, is easily to check that for t Thi we have H, M, S Fx-1- Next, note that
PTx - Tk-1 =8)
= IP (iTE-I+1 # k(mod n2),-.. ... - # kc k(mod n), iT__ito k(mod n))
P (iT--1+1 + :..... 2 # R, in--its k²)
(1 -- s11ppe pke
13

---

Under review as a conference paper at ICLR 2020
where k' k(mod n), I R' < So Tx Tk-1 is geometric random variable with success probability pk-
On the other hand. Tj Tk-1 is just dependent ěT -Tg-+t1'' tTy thus for # k. Ti T is independent with Ti. Tk
Therefore,
k T.
Σ (T) T1-1) Σ Y 1=1
where Y, follows a geometric distribution with success probability Pv where /' = /(mod n), 1 1 I n.
Proof of Remark 2.3 If each fi is L-smooth, then for any æ, E In
we have
[V)=)) ( 1.2 | y112.
and consequently,
VS((x)) V - L | - yyl
(13)
(fi)= I-average smooth, then for any x. y E R.m we have
[) - v
n2 Σ
- -V(()))V((())
2
[f((z) - Vf.(s)l
[V( f.(())
$ L æ y112-
Proof of Lemma 2.9
Denote =M [(x) by f For S N, we have
Ef (.) f Elf(zz (x,) - I < TP (N < TM+1)
E min f(x) f < TM-1IP (N < TM41) EFFM
2 9EP (TM+1 > N)
where TM is defined in (7). and the second inequality follows from Corollary 2.7 (if N < TM+1 then 3, E Fas for t < N).
By Corollary 2.7 TM+1 can be written as TM++1 = Σ Y, where (Yihsis are independent random variables, and Y, follows geometric distribution with success probability
(I' =
I(mod nt), 1' < n). Moreover, recalling that p1 S p2 S S Pn. we have Σ qi < M+1
M+1
Therefore, by Lemma 2.8 we have
M+1
(M + 1)n
16
1
P (TM41 N) P
Σ Yi
2 1
4
9(M
1)
9
1=1
Hence, we can conclude that Ef((x))
f* > 9sP (TM41 > NN 26.
14

---

Under review as a conference paper at ICLR 2020
Remark In fact, more strong conclusion hosts:
E
min ISN
[(x:)]
min =ER
f 2
D RESULTS ABOUT SUM OF GEOMETRIC DISTRIBUTED RANDOM VARIABLES
Lemma D.I. Let X1 ~ Geolpi), X2 ~ Gee(p2) be independent random variablex. For any positive integer j. if P1 # p2, then
(xx P2(1 - p1) - -PI(L -p2)"
(14)
P2 P1
and if pt = P2, then
P(X, + = (1 (1-p1)²
(15)
Proof.
P(XI+X2 +
Σ P (1)=-)))( j)
1=1
Σ
(1 - p1) 1'11p1 p2)
122--2+++ + (1 p1)
1=1
1 [-1
p (1-
Σ
+ (1 - pi)
P2
1=1
Thus if - P (X1 P2,
+ X2 > 1)
1 (1) +
- (1-p1}.
For p1 + P2-
(1 - (1-p))² (1 - p2)
P X2 >) P1
+ (1-pp))
p2 P1
P2(1 -p1) p1(11 p2)
p2 p1
Lemma D.2. For x 2 and j 2 2,
1 j-1 <
5-1
(16)
x + j/2
x +++1
Proof. We just need to show that
(x + (x+ (j (j- 1)) S - (x + +112).
that is
(x + 1)3 j(r + -2-1122-0 + j/2) so.
-
j-2
i.c.,
Σ
2
2' 50.
1
Note that for 1 S - 2,
-
j 1 = 11-
2 (2) S o,
2 1
thus inequality (16) hosts for 2 0 and j 2 2.
15

---

Under review as a conference paper at ICLR 2020
Lemma D.3. Let X1 Gco(p1), X2 Geo(p2), Y1, Y2 Geo (2IT22) be independent random
variables with < P1 I P2 I 1. Then for any positive integer j. we have
P(X X2 j) P (Y Y2 j)
Proof. ]f 1, then P + X2 > j) = - P (Y1 + Y2 > j).
pi = P2 = 1, then P PXX X₂ > )) 0= P (11 + Y/2 > j) for j 2
Let j 2 2, and c P1 + +P2 < 2 be a given constant.
We prove that f(1)) _ (X + X2 > j) is a decreasing function.
Employing equation 14 for P1 22 have
((1)) (c p1)(1 p1) -P1(1 + P1 cc)
c-2p1
and
(p1) = -(1 -11-p1) - ((c-p))(1 -1))-1 pi - -C- + pt - -)--1
c-2p1
+ +2 (c - pI)(1 - p1) p1 P11 - cc
(c- -21)2
[o[1- -PI) - j(c p1)(c- (2p1)](1
P1 P1 -
+pilcc 2pt)](1 -cp-1
(c-2p1))
Hence (pi) < 0 is equivalent to
ct1 - pı) j(c (c 2p1)
11+ - J-1
(17)
c(1 + - jpi 2p1)
1 P1
Note that
c(1 p1) - - Pı) 2p1)
c(1 +11+1 P1 - c) + jp1 (c 2p1)
(j 1)c(c 2p1)
c(1 + c) + jpL (c - 2p1)
j-1
1 I+pi-c + j
c-2p1
Denote 1+pi-c
If I 1, then Pı > 0 and x
2 And if > 1, then pı c 1 and
c-2p:
-لتي- = 0.
Rewrite inequality 177 as
1-1 3-1
j-1
x + jjp/c
x +
Recall inequality 16 we have
5-1
j -
j-1
2
I + j/2
+
-pi/c
Consequently, (p) < 0 hosts for P1 < c/2 and
2.
With the fact that pimp1 (p1) = f(c/2) according to equation
15
we have
P(x1 + X₂ > 1) 2 P(i Y2
for any positive integer and P1 & P2 1
16

---

Under review as a conference paper at ICLR 2020
Corollary D.4. Let X1 Geo(p1), X2 Geo((2). Y1,Y2 Geo (2 be independent random variables with < p1 I P2 I L. 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. have
P Z + X1
X2 1) + j).
Proof. With applying Lemma D.3
we have
i-1
( + 11
X2 1)
1=0
Σ P - 1=0
P
Corollary D.5. Let {Xi]igism be independent variables, and X₃ follow a geometric distribution with success probability ps. For any positive integer j. we have
P
Σ X
Σ 2
2P
where (Yilisism are i.i.d. random variables, Y; Geo -== m X1(11 S $ m).
Ps/m), and Y; is independent with
Proof. Let
f(1, P2. PPm) & P
Σ X 23 i=1
Our goal is to minimize ((1,, P2, pP such that Em Pi S<1 By Corollary D.4] we know that
+ 4j
+ +
[p1, P2, Pr. PPss Pm) 2 (pI,P2,
Pm..
2
2
This fact implies that (p1, Pa.... Pm) such that p1 P2 Pm function f.
S/m is minimizer of the
Lemma D.6. Let {Xihsssm be i..dd. random variables, and X, follows a geometric distribution with success probability p. We have
16
P
X;
(18)
4p
9m
Proof. Denote E X; by T. We know that
mm1 p)
Er p
Var(r)
p²
17

---

Under review as a conference paper at ICLR 2020
Hence, we have
3 RT
r >
RT
P
T ET >
1 P
T ET S
2 P
[T ET 2 ET
16Var(T)
2
9(E))²
16m p)
16
9m2
9m
Corollary D.7. Let {Xilisism be independent random variables, and X, follows geometric distribution with success probahility pi- Then
m22
X;
2
m i=
9m
E PROOF OF THEOREM
Proposition E.1. For any 2 2, 2 fsc.s and Fsc in Definition 4.1 satisfy:
1. Jsc. is L-smooth and p-strongly convex.
2. The minimizer of the function Fsc is
2An(a + 1)2
xx" = arg min Fsc(x) m mE
V (I. 1-)))(a-- -1] (1" "mm
,- ,...,, ,
9-1 where q a+1
Moreover, Fsc(x*) -A
3. For 1 < k S m 1. we have
min Fsc(æ) Fsc(x*) 2 Aq² #EFt
(19)
Proof.
1. Just recall Proposition 2.5
2An(a+1)a
2. Denote & V (I 1-(aaaa1->
Let (Fc((x) 0. that is
L 1 A V aa+1/
2
L 1
+
+I
x
{em:
2n
n(a + 1)
w 2
2np L- F
1
1
2 +
2np T-
-1
0
(20)
+
2nn
-1
L- p
2np
+
T v
a+1
18

---

Under review as a conference paper at ICLR 2020
Note that a-1 is root of the equation
2np1
x²
2 +
I, + 1 + =0, 0,
and
2np 1
w² + 1
L - 1 q
2
2n
a - q == -² + (1 +
).
p
Hence, it is easily to check that the solution to Equation (20 is
x² E(d" ,9"
g)
and
L 1
Fsc(x") = 2n(a + 1) <² q²q== -A
3. If x E Fk, 1sk m, then 21 = 22
Im
Let 2m-k+1mm E R and A₁ be last ht rows and columns of the matrix in Equation Then we can rewrite F(x) as
L -
L- 1 ML y Auy n(a + 1)
Fi(yy) & Fsc(2))
Elem: y)
Let (y) that is
2 +
2npr
L
0
2 +
2np T-
-1
0
y
(21)
2np 2 +
L-
-1
1 1+
2np T.-p
a++
By some calculation, the solution to above equation is
h+1 (q-1 q, q², ...
- 4²)²
+ 2
Thus
1- q
1 q
min Fsc(x) = min Fx(y) mEX,
c2
yEX*
2n(a + 1)
1 1 2
+ q 2k+1
and
min Fsc(x) - =sc(xt") = =A(1- =EFr
1- 1-92h
1 2k+1
1 1+
= 29
1 92k+1 2 AR
Proof of Theorem 4.2
Let M
log(9e/A) A)
then we have
2 2logg
arg min Fsc(#)) Fsc(x") > Aq 2M
95,
=EFx
where the first inequality is according to the third property of Proposition H.1
19

---

Under review as a conference paper at ICLR 2020
Following from Lemma 2.9 for .M 2 1 and N (M + 1)n/4, we have
min [F;(();) Fsc(x")) 2 E. KS
Therefore, in order to find ā E Rn such that (E)) - Fsc( < E, A needs at least N queries
h Fsc.
We estimate - log(4) and N in two cases.
1. If T/p 2 n/2 1, then 2 12
+1 2 v2.
Observe that function A(3)
2 is increasing when 3 >> 1. Thus, we have
0
log
1
a h(v2)
log(g)
log
2
a
L/
+1+ h(v2)
v2
L/P
(2- "
+ 1
+ +l(22)
4
L/μ -1
V2
+ + h(v2),
2\
n
and
N = (M + 1)m/4
71
log (9 AA)
+1
4
2
A
IV
log
log(a)
M
72
L/ 4
V2
1((2)
log
2
4
96
nL
A
Ω
+
log
p
2. 1 < L/μ < n/2 + 1, then we have
-log(g) log 1
2(a 1)
log 1
a² -1
14 V 1:/m-1
+1 1
1 (V2 1)n
= log
< log
L/u-1
T./1 -
(V2 - 1/2)m
(2v2 - 1)m
< log
S log
(22)
L/u 1-
L/P
where the first inequality and second inequality follow from T./pu < n/2 and the last
inequality is according to --1 < 2 for x: 2 2.
Note that n 2 2, thus n
< 2 < L/p-T and hence n 2 L/u, i.e. log(mp/ L) 2 0.
Therefore,
n
1
A
N (M 1mm/42
log
8
log(a)
= .
A
log
log L))/
95
20

---

Under review as a conference paper at ICLR 2020
Recalling that assume that 9 S q², thus have
N 8 (
(Toolee)
1
log
A
(- (Tog(()
)
(-21og(a))
n
log(a)
98
Therefore, N Z nn (1pp/(
log (G:)
At last, we must to ensure that 1 2 M < m, that is
1 A)
1 <
m.
(23)
2 log q
Note that lim3-+00
h(3) 0, so
-1/log(1) S a.2. Thus the above conditions are satisfied when
(og(A/(9E))
L/u (2/1u-1 + 1
A =1=0
(v=L log
c )2)
m
2( log ?)
+ 1 4
12
n
log
9E
+
np
and
E <
1 2-11 1
A 9 0 0+11 1
F LOWER BOUND FOR ANOTHER FORM OF SUBOPTIMAL SOLUTION
Defazio 2016 showed that the PIFO algorithm Point SAGA has the convergence result x (g |000 - 12 where q' satisfies 1 log((')) O (n VnL/u)) To match this form of upper bound, we point out that similar result holds for {fsc, Theorem F.1. Suppose that
V2
2
1// 1/ Lip
f 2 2 85 18 V2
and m 2 (12
+1
log 18c
+
71
In order to find &c E Rm such that E || x 112 < E < x= 12 PIFO algorithm A needs at least
Ω
n +
nL log (2) queries to h
Proof. Denote { = / (I- ([-p)](a-1) and M- = (1g(18:) For M < m/2, = n(M + 1)/4 and
2An(a+1)
2 2og
N, we have
E |æx, x x11
||,, xx 11
N < Tart1
P(N < Tar+1)
IV
min
|
111
N < Thst1
P(N Tar+1)
min
| x" 1
M
where TMr+1 defined 7 the second inequality follows from Corollary 2.7 (if N < <T
then x, E FM for / & 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.I
we know that x- E(qT
g)T and
e² q² q 2m++)
xx 112 = ||x"
q²
21

---

Under review as a conference paper at ICLR 2020
Note that if x E FMs then 21 22
Im -M 0, thus
g2( 9 (m
min #CFM
x
x² 62
q (
q²
Imm M
Thus, fort S N and M S m/2, we have
E 2
q 22d
q 2m
xc x= 11
1 g2m
2
2M
18g(
2
2 E,
18
18
where the second inequality is due to
9 2M
2m
9
2M
9 2M
29 2m
+ 9 (mm-f)
1
2m
2
2(1
2m
22
(1 2// 2(m- N5) + 2m)
2(1 2
2
(1 21-n +mm²) 2 O.
2(1 g2m)
Therefore, in order to find á e R such that
B
E, A needs least N queries h
|| x 11
As we have showed in proof of Theorem 4.2 for L/P 2 n/2 + 1, we have
1 L/R F
L/p L/u +1
2
+
2
2
log(a)
and
n 4
n log( (8s)
N =
(M + 1) 2
2 log
C1
n1 +
nn(L/H - 1) log
1
8
18s
Ω
n
nL
log
-
At last, we have to ensure that 1 < M < 2, that is
log 18s)
< m/2
2 log 9
The above conditions satisfied when
m log(1/(18s))
L/u
+ = 0
(VT log
1
+ 1 < 2 1/
+1 1
log
-log
18s
nz
E
and
5 18 9².
Observe that when L/p n/2 + 1, we have 2 v2 and q a=1 2-1
Hence, we just need
v2+1
2
8 -
1
12-1
~ 0.00164.
18
V2+1
22

---

Under review as a conference paper at ICLR 2020
G PROOF OF THEOREM 4.5
Proposition G.1. For any n 2 2, m 2 2, following properties hold:
1. fca is T-smooth and convex.
2. The minimizer of the function Fc
2 (1.2, m)
arg min Fc(ar)
xERm
L
where v3 BL (m+ 1 Moreover, Fe(x*)
mm²
and ||00 x0112 B².
3. For 1 S.k S m, have
5²
min Fc(x) Fc(x²) (m k).
(24)
#EFt
nL
Proof.
1. Just recall Proposition 2.5
2. Denote Ç
//3 2
BL
Let Fc((a) = 0, that is
(m+
1/
L
A(1)
em
2n
7
-1
2
-1
0
(25)
-1
2
-1
2E
Hence, it is easily to check that the solution to Equation
25 is
25
25
xx
L (1.2....,)))
and
Fc(x")= = mm?
nL
Moreover, we have
45a m(m + 1)(2m + 1)
100
x²11
6
4
<
(m + 1)3 B².
3L2
3. By similar calculation above proof, we have
2c
arg min Fc(x) = .1,
#EFt
L
and
kg
min Fe(x)) #EFt
n.T.
Thus
22
min Fc(x)) Fc(x*)
(m k)-
weF,
nL
23

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 4.5 Since E S
B we have m 2 3. Let & = 384n'
v3 BL 2 (m+1)877
For M- m-11
1, we have m M 2 (m + 1)/2, and
2
min Fc(x) - Fc(x") = 52 #EfM
3B2 L m M
(m- M)
nL
4n
(m + 1)3
L L
1
2 95,
8n
(m + 1)²
where the first equation is according to the 3rd property in Proposition G. and the last inequality follows from m B
Similar to the proof of Theorem 4.2
by Lemma 2.9 we have
min (F()) Fe(x") 2 E.
ISN
In other words, in order to find a E Rd such that (f Fc( < A needs at least N queries
hp.
At last, observe that
N (M + 1)m/4=
4
2
n(m 1)
11
B
8
24nE
n
Ω
n B
E
where we have recalled <
B 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 {9thissn 9: : E, where
L -nLBx,
91 (z)
- x²²
2
L
(x)x) 2 =x²
n
I x
G(x) =
Σ g((x)
=
-LBx.
n i=1
2
First observe that
x¹ = arg min G(zz) = B,
zER
G(0) G(x*) LB
and I20 - x=1= = B.
For 1, have dg.(x)
de 1 and prox (0) 0. Thus S, will host till first-order
method A draws the component f1. That is, for L T arg min 1), have 0.
24

---

Under review as a conference paper at ICLR 2020
Hence, for t S 1. have
2p1"
EG(x)) F(x*) 2 E
G(rz) - -((*))
T P
p1
<T)
2p1
2pr
LB P
<
T
2p
Note that 7 follows geometric distribution with success probability p S 1/nn,
and
1
2p1 (1 -p1) .ọ
IP
T
P
T>
2p1
1
2 (1
pı) 2P1 2 (1 1/m) //2
2
where the second inequality follows from h(2) = log(1 log(1-2) =) a decreasing function. 2=
Thus, for S 1
we have
2p1
LB
[G -((=))=F(>")))
F(x*)(x))))) 2
2
4
Thus, in order to find è E R such that (F - F(x*) < E, A needs at least 2p1
2 n/2 = 92 (n)
queries to hg.
Note that {- 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.10
Proof of Lemma 4.3 Let B
22/L.
Then e/A < 1/2 is equivalent to S. LB /4. Note is also ju-ttroglyy convex for any μ I L, and satisfy
that } ) defined in proof of Lemma
4.6
[G(0) - G(x") A. Therefore Lemma 4.3
hosts for the same reason.
Remark H.1. Suppose that
2
:0 /
9
71
1. If 2 n/2 + 1, then we have a 2 / and
+ 1
n + v kn) log
S 2 (n + VKn) log
9=
1
4 (n + VKn)
4//on
O(n) + (1 2/22)a
4
VKn =O(n):
< (n) + V2 - k/n
where the second follows log(1 +x) S x and the last inequality is according
to a 2 /2k/nn n. That
2(n) = S2 ( (e((n++ vnn) log
)
9E (44
A
2. 1f2 L/p < n/2 + 1, then we have
A
+
log
2
log(np/LL
95
I+ logg/(p//L) L)
(2v2
1)n ))
2log
O(n), =0(m),
log(nu/LL)
L/P
25

---

Under review as a conference paper at ICLR 2020
where the second inequality follows (22). That
(1++
A
(2()) S?
1ogg(npp)
log
9:
+
I DETAILED PROOF FOR SECTION 4.3
Proof of Proposition 4.7
1. It is easily to check that Fsc(2) is fu-strongly convex. Following from Proposition 2.5 then {fsc, is L-average smooth, where
+ 11
2
( 11
27
+
+
122
n
2(L2 + 12))
+ 122 L'.
n
2. Clearly, L
n(L/a 11²)
122 S V L
2
Furthermore, according
L'
2 V n
(
1). we have
/
L
3 L
(L
n1
4
11²
n
L
3
1
2 4
1
μ²
2
2
2
n22
112
2
0
8
2
and, L/p> FL n/2 +1.
Proof of Theorem 4.8 over,
By 2nd property of Proposition 4.7
know that L/p 2 n/2 1. More-
2
A
m
+1
log
+
4
n2
9s
L/ F
+1
log
+
1,
n
De
Then, by Theorem 4.2 in order to find & E R such that EFsc(
Fsc(x)) < E, A needs at
least N queries Feee where
nL
N Ω
log
p
n n
nn/I!
Ω
n +
log
L'
A
Ω
3/4
log
1
'By the proof of Thcorem 4.2 larger dimension does not affect the conclusion of the thcorem.
26

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 4.9
Note that
V2
B²
B²L
5
768
VTi
384n'
V18
L'
B
Bn
1/4
V
1.
12
24nE
By Theorem 4.5
in order to find á E I such that EFc(E) - Fo(x*) < E, A needs at least N
queries to Fe. where
nn
n1 + B N = Ω
n1 nVn/2111 n1/21/
Ω
+ B
T!
Ω
n + Bn 3/4
NON-CONVEX CASE
In non-convex case, goal is to find e-approximate stationary point & of our objective function
f, which satisfies
Vf S..
(26)
J.1 PRELIMINARIES
We first introduce a general concept about smoothness. Definition J.1. For any differentiable function f gm++1 + R. we say f is (1, L)mmmoth, for any y E 1 we have
L x 212
1 5 f(y) (Vf()). x 8) S
2
where L > 0,1 E R.
Especially, if f is L-smooth, then it can be checked that f is (-L, -msooohh. If f is (-o, -mmooo,h in order to make the operator prox? valid, set ensure the function
f(u) A f(u) + 2" -| u11
is convex function.
Next, we introduce class of function which original proposed in (Carmon et al. 2017). Let GNC Rm+1 - IR be
1 2
Gxc(a;a,m)
B(m + Va)a Valer, +a T(x)).
1=1
where the non-convex function I' R
1"
x 12 - 1)
[(x) A 120
1 - t dt.
(27)
We need following properties about GNc (æ;; ot m).
27

---

Under review as a conference paper at ICLR 2020
Proposition J.2 (Lemmas 3,4, Carmon et al. (2017)). For any 0 1, it holds that
1. [(=) is (-45 v3 1), (180)-smooth and Gxc(æ;a, m) is (-45(v3 1)a, 4 + 180a)- smooth.
2. Gvc(O; at m) min GNc(2; at) S va/2 10am.
3. For æ which satisfies that I' = 2m+1 = 0, we have
[V 2 a 3/4 ///4
J.2 OUR RESULT
Theorem J.3. For any PIFO algorithm and any L, O, n. A,E such that e² S
ALe there exist a 81648n'
dimension
ALya
+ and n. (-o, L--smooth nonconvex functions {J: Rd - +R such
40824m2
that ((xo
[(x") < A. In order to find & E Rdd such that IE || ((:) < A needs at least
Ω
AL.a
queries to h where set min
(V3+1)no
30L 180
Remark J.4. For n > 180, wehave
ALVa
V3 + T.
v180 )
VnL
12 min VnoT.))
Ω
Ω
min T.
Vna L,
30
Thus, our result is comparable to the one of Zhou and Guys result (their result only related to IFO algorithmss so our result is more strong), but our construction only requires the dimension
be O 1 3 min(L/n, VOL/n)). which is much smaller than O min(L, VnoL.) in (hoo
and Gu 2019
J.3 CONSTRUCTIONS
Consider
= AGxc(z/3;a,, m).
(28)
Similar to our construction we introduced in Section 1, Va) by by and
2
we denote the 1-th row the matrix B(m +
C- (1: :1:15 S m, m 1 i(mod n)), = 1,2, ...
(29)
Let G. spanfer, 62, ,e) k
m. Go {0} and compose F(z; a, m, X, B)
f( = An
Σ
bJ x
|
Anya (e1, + Aa Σ r(x:/3).
2
#
(30)
), =
An
Σ
67
2
m Aa Σ I(x:/3), for 2 2.
2
IEC
Clearly, F( m, A, 1 E fel:; m, 3). Moreover, by Proposition J.2 we have fol- lowing properties about F(x; Ct, m, X, 3) and [f:(w; a, m, X, B
Proposition J.5. For any 0 < a S holds that
1. f1 a. m. X, is
-45(v33 Daa B2
(2n 1800)
smooth.
2. F(O; oz, m. X, min
Flx; a m. X, 8) S M 100m).
3. For & which satisfies that Im = Im++1 = O, we have
3/4 X
Vm 3)112
48
28

---

Under review as a conference paper at ICLR 2020
Similar to Lemma 2.6 similar conclusion hosts for (fi( a, m. X, 1,
-2+1 g
Lemma J.6. For a Fr. O k < m and y < 60 2a'
we have
9k+1, jfk=i- 1(mod n),
Vi(a;; A, B), prox (a:)
gk. otherwise.
Proof. Let G(x) _ Σ T(x;) and (x) the derivative T(x).
First note that (*( so x E Gk, then
(G(x)= (T2)) ("( e gk-
Moreover, for æ E Fo (k: 2 1), we have
67 x = for < m - k,
bi G% for > k,
b E 2k+1-
Consequently, for * m k. b,b, x (b) x)bb E Gk. and b - E 9k+1-
For O, we have 0, and
Vf((x) = An/ E 91,
(z) 0 (j 2 2).
For 1, we suppose that m k E Li- Since
(x) = An
bra+ + Aa VG(x/B) n1e1,
32 LEC
B
where 7) >nnaa/B.m n for j 2
Hence, Vfi()) E Fx41 and (x) E F& i).
Now, we turn to consider prox}, (z).
We have
(z) + (v x) =0,
that is
An
+ 1
Aa
1
bu by
v +
VG(o/B)=
+ xc.
(31)
32
7
3
7
IEC,
Denote
A =
An
Σ
b, bi +
-1, = 8 y = neer + x
8
3
LEC,
then have
Aa VG(u)= = y.
Au
(32)
B
Next, if satisfies
8 > max (1, k}
for j = 1,
(33)
8 >>> k
for j > 1,
29

---

Under review as a conference paper at ICLR 2020
then know that the s-th element of y is 0.
33 and m 8 E Lj. then the s-th and (s + 1)-th elements of Au is ((E 3 3/7)u, u, {u++1) and (-Eu, (5 + 3/7)ua+1) respectively where & An/3. So by Equa-
8 satisfies
tion 32 we have
B Ug E(Us Ux+1) + 120Aa " O.
7
l+u;
a Fuot1 + E(u++1 - Uz) + 120Aa " (u,+1-1) 0.
14
Following from Lemma J.9 for 120Aa That is
(242/2) we have Us = Uo+1
1. if E Cj and satisfies 33 then U, O.
2. if s -s Lyy and satisfies (33 then Us 0.
For which satisfies 33 if m
E Cj and m - 8 + E Ljj, then the s-th element of Au is we have
(3/y u.). Similarly, by Equation (32)
3
120
ug u - 1)
Us +
0. 1 1+ u?
B
Following from Lemma J.8 for 120Ac
(242 2/8
we have Us 0.
Therefore, we can conclude that
1. if satisfies 33 then U1 0.
2. if satisfies 33 and + f,j, then us 0.
Moreover, we have that
1. if k- 0 and 1, then 1, L.j. so 0.
2. if k 0 and > 1, then for 1, we have 8 Lj. 11 0.
3. if k 0, then for 2, we have
satisfies 33
U1 = 0.
4. if l: 0, then for k 1, have 1 le satisfies 33 tl = 0.
5. if
0 and & Lj. then for 1e + 1, we have
& Cj. uk+1 0.
In short,
1. if k 0 and > 1, then E Go-
2. if k 0 and 1, then G1-
& Cj. then E Gk- 4. if k and
3. i and
Lj, then E Gk+1-
Remark J.7, In order make the operator prox7, valid, 7 need to satisfy
V3 1
Xa <
90
60 Ace
So for any valid PIFO call, the condition about 7 in Lemma J.6 must be satisfied.
30

---

Under review as a conference paper at ICLR 2020
Lemma J.8. Suppose that 0 < 22 (2 + 2/2) then is the only real solution to the equation
(= - 2²
2 + X2
0.
(34)
Proof. Since 0 < X2 < (2+ 21, we have
X 4A1(A1
+ A2) < <0,
and consequently, for any 2, (A1 + 22)=² A22 + A1 > 0.
On the other hand, we can rewrite Equation
34 as
(()1 + x2) -2=
A2= + X1) 0.
Clearly, z 0 is the only real solution to Equation 34
Lemma J.9. Suppose that X2 (2+2v2)) and X3 0, then 21 22 is the only real solution to the equation
Aa(21 - =2) + '22 (21 0. I+2
+ λITι
(35)
21 0. 1+22
A1
A3(22 21) + X2
Proof. If 21 = 0, then 22 = O. So let assume that 21 # O. Rewrite the first equation Equation 35 as
\1 As
A2 (21 -
22 1 2
A
21
Note that
V2
2(2
<
2
1 22
Thus, we have
\1
+ A3
A2 1 - V2
22 21
+
A
A3
Similarly, it also holds
A + A
d2 1 - V2
21
A
As
2
22
By < A2 < <2++2/2) we know that A + 1-v2 X2 > 0. Thus
X A3 >2 1 - /2 >
A A3
Since 21/22 > 1 and 22/21
hold at the same time, so we get contradiction.
Following from Lemma J.6 we know following Lemma which is similar to Lemma 2.9
Lemma J.10. If M > 1 satisfies min || [F)())) 2 95 and N = n(M + 1)/4, then we have
min
E V F (x:) l 2
31

---

Under review as a conference paper at ICLR 2020
Theorem J.11. Ser
(v3
1)no
n
a min
1,
30L
180
3888ne2 A
Lax3/2
3 /3nn/L.
ALva
m
40824ng2
Suppose that c² <
ALa
In order to find & E [R=++ such that E [VF())]
PIFO algorithm
81648n
A needs at least Q
ALya
queries hp.
Proof. First, note that f; is (2-oot))smmoth -mooohh where
4 45(v3 1)ad
45(V3 -)L
45(v3 1)L (v3 + 1)no 0,
a 5
g2
3n
3n
30L
1/ (2n + 180a))
L
(2n 1800) S L.
B2
3n
Thus each fi is (-o, -)smmoohh.
Next, observe that
1944na2
38880ne2
F(xo) F(x*) S M(Va/2 100m)
m
La
Lva
1944
38880
A A.
40824
40824
For M = m ---,, -1, we know that
a3/42
2/ X
XL 3/4
min #E9M
[VF())l22
95.
48
4/3nnL
3n
With recalling Lemmal J.10 in order to find & E pm+1 such that E VF < PIFO algorithm needs at least N queries to hy, where
AALaa
N n(M + 1)/4 = nm/4=
82
At last, need to ensure that 2 2. By 8² <
ALa
we have
816188
ALva
ALa
40824ng2 2,
40824ng2
and consequently m 2 2.
32


Reviews:
[{"review_id": "rJxQHktG5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nTo prove the desired lower bound, the paper constructed a group of special loss functions, such that each individual loss depends on only 2 coordinates of the parameter vector (except for the regularization term). By this construction, if the parameter vector is initialized at 0, then the number of non-zero coordinates of it will grow slowly enough so that the parameter vector will stay in some low-dimensional subspace unless a large number of iterations is performed. Using this construction, the authors prove the lower bound for 4 different configurations of optimization problems.\n\nOverall, I think the results are very interesting. Similar ideas (the diagonal matrix used in this paper) have been widely adopted in proving complexity lower bound. The novelty of this paper appears to be that the diagonal matrix is partitioned into n groups to define the individual loss functions. Despite the tight lower bound, the assumption (1) and (2) above seems to be restrictive, but they are necessary for the analysis of this paper. If we allow the optimizer to initialize at a random point, or if the optimizer can adaptively choose the loss function at each iteration based on the parameter trajectory, then the analysis framework no longer applies. This is probably the main limitation of this work.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xPXyAiYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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\n\"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\nthe number of queries needed by an algorithm to guarantee to approximate the minimum.\n\nThe main result is for the case that the summands are mu-strongly convex and L-smooth.  Bounds for this case are often\ngiven in terms of kappa = L/mu.  An upper bound of O( (n + sqrt(kappa n) ) log(1/eps)) is known, and\n[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.\nBut 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].\n\nThe 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.\n\nI 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.\nBut a lower bound for the convex case seems to be stretching this a little far.  \n\nThis seems like a somewhat incremental contribution that would be of interest to a smallish subset of ICLR attendees.\n\n[1] Blake Woodworth and Nathan Srebro. Tight complexity bounds for\noptimizing composite objectives. In NIPS, 2016.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1ezmonaYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary\nThe paper derives a novel lower bound on the complexity of optimizing finite-sum convex functions (under different assumptions) using algorithms that have access to point-wise evaluation of the function, its gradient, and proximal information. \n\n** Overall evaluation\nFinite-sum convex functions are very common in machine learning problems and how the optimization complexity scales with their properties (e.g., condition number) and the number of components (e.g., number of samples in typical ML problems) is a very important question. This paper addresses the question from a lower bound point of view, showing that there is no proximal incremental first-order algorithm that can optimize such functions at an accuracy level of epsilon in less than a term which depends linearly with number of components n and sqrt(k) (k being the condition number). The paper fills an existing gap in the literature and it achieves two very interesting results:\n1- The lower bound now matches an existing upper bound for Point-SAGA, showing that no better algorithm can exist (at least in a worst-case sense). \n2- This result also illustrate that proximal algorithms are not necessarily more powerful than first-order methods that only access the gradient of the function. This is also very interesting, as it was still an open question whether proximal information could possibly give an advantage.\n\nThe paper is also well written, although some elements could be improved:\n1- Def 2.4: the authors consider algorithms where the sampling distribution cannot adapt through iterations. Although this is standard, I am wondering whether adaptivity may buy anything in the performance or whether the lower bound applies to adaptive algorithms as well.\n2- Although similar constructions to create worst-case functions were used before in deriving complexity lower bounds, it would be useful to have an intuition about the specific choice made in eg Eq.5/6 and how this enables the refined analysis presented in the paper.\n3- More in general, I encourage the authors to illustrate how their techniques compare and differ from previous lower bound proofs.\n4- In all theorems, the analysis is done by linking the dimension d to all other parameters of the problem. As pointed out by the authors, the requirements on the dimensionality in the theorems of this paper are milder than previous results. It would be helpful to illustrate how the lower bound would behave when the dimensionality changes and provide an intuition about the specific choice in the theorems", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a lower bound complexity for the convex problems. The reviewers worry about whether the scope of this paper fit in ICLR, the initialization issues, and the novelty and some other problems.
Decision: Reject