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.
** Summary
The 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. 
** Overall evaluation
Finite-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:
1- 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). 
2- 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.
The paper is also well written, although some elements could be improved:
1- 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.
2- 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.
3- More in general, I encourage the authors to illustrate how their techniques compare and differ from previous lower bound proofs.
4- 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