- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the oracle complexity of smooth finite-sum optimization. It introduces a dense weak hiding construction, where information about each hidden direction is spread across all components. Using this construction, the authors establish a nonconvex lower bound matching the PAGE and SPIDER upper bounds under individual smoothness. The result covers randomized algorithms with unrestricted query selection. The paper also establishes matching bounds under the global PL condition for condition numbers at least three and proposes a restart schedule for PAGE that improves the guarantee in the small-condition-number regime.
Critical strengths
The main nonconvex result is substantial. The paper establishes a matching lower bound under individual smoothness while allowing randomized algorithms to choose both component indices and query points adaptively. The combination of the stronger smoothness assumption and the broader algorithm class is the key contribution.
Dense weak hiding is an interesting technical construction. It distributes information across fixed components while preserving the signal in their average, and combines this with smooth gates to enforce sequential progress. The PL results strengthen the contribution by covering both condition-number regimes and providing a matching restart schedule for PAGE.
Critical weaknesses
The positioning relative to existing lower bounds needs greater precision. Theorem 2 of the original PAGE paper already establishes the same nonconvex complexity rate under mean-squared smoothness for linear-span algorithms, but Table 1 lists PAGE only as an upper bound. Including this result would make the new contribution clearer: individual smoothness and unrestricted randomized queries. Also, the statement in Section 2 that previous individual-smoothness lower bounds showed no dependence on κ is too broad. Existing strongly convex lower bounds already provide condition-number dependence, and strong convexity implies PL.
The lower bounds allow the dimension to grow with the problem parameters and query budget. Consequently, they establish worst-case optimality over unrestricted finite dimensions, rather than a matching characterization for a prescribed dimension. The appendix quantifies the required dimension, but fixed-dimensional complexity remains unresolved. This is a scope limitation, not a flaw in the stated results.
The PL characterization remains incomplete for 1 ≤ κ < 3. The upper bound covers this range, while the matching lower bound does not. It would be useful to clarify whether the threshold is only a limitation of the construction or whether different behavior is expected near κ = 1.
The algorithmic contribution is narrower than the lower-bound contribution. Restarted PAGE retains the existing estimator and changes the restart schedule and analysis. Its guarantee also requires suitable smoothness, PL, and initial-gap bounds. The improved rate is useful, but the paper does not establish an adaptive implementation or a practical advantage when these quantities are unknown.
Questions for authors
-
Could you clarify the comparison with Theorem 2 of the PAGE paper, which already gives the matching nonconvex rate under mean-squared smoothness for linear-span algorithms? Please distinguish the contributions of individual smoothness and unrestricted query selection.
-
Section 2 states that previous lower bounds under individual smoothness showed no dependence on κ. How should this statement be understood given the existing strongly convex lower bounds, which also apply to a subclass of PL objectives?
-
Is the restriction κ ≥ 3 only a limitation of the construction, or do you expect a different optimal rate for 1 ≤ κ < 3?
2 comments
remain positive
Thank you for the clarifications and corrections. I think these changes, at least somewhat, address some of the concerns raised. Thus, I keep my positive score and lean towards acceptance.
Response to Reviewer BLoJ
Thank you for the careful review.
Q1 / W1. Theorem 2 of the PAGE paper. Table 1 now lists this result. Under mean-squared smoothness, the factor n was indeed already known, both for linear-span algorithms (Theorem 2 of the PAGE paper) and, when n=O(Δ2Lms2/ε4), for arbitrary queries (Fang et al., 2018, Theorem 3). Under individual smoothness, however, it was missing: earlier randomized lower bounds give Ω(n+ΔLmax/ε2) for linear-span algorithms that sample components from a fixed distribution (Han et al., 2024), and only Ω(ΔLmax/ε2) for arbitrary queries (Emmenegger et al., 2022). Our contribution is therefore the factor n under individual smoothness, which earlier lower bounds lose even for linear-span algorithms, and Theorem 3.1 proves it for randomized algorithms with unrestricted queries and outputs (Introduction, paragraphs 2 and 3; Section 2).
Q2 / W1. κ-dependence in Section 2. We agree that the statement was too broad, and we have removed it. Section 2 now notes that strongly convex lower bounds apply to the PL class, but that the κ-dependent bounds of Han et al. (2024) and Hannah et al. (2018) are proved for restricted algorithm classes, and that under individual smoothness their small-κ regime ends at κmax≍n rather than at n. Lower bounds built directly for PL objectives, in turn, give κ-dependent rates only for large condition numbers, namely κF=LF/μ≳106 (Yue et al., 2023) and κms≳105n (Bai et al., 2024), whereas Theorem 3.3 holds for every κ≥1 and for unrestricted randomized algorithms, with the range 1<κmax≤n covered by our two-scale chain (Section 6.1).
W2. Dimension. This is indeed a limitation, but to our knowledge it is shared by the lower bounds in this line of work. The randomized lower bounds that we compare with and that allow arbitrary queries all use hard instances whose dimension grows with the parameters. The complexity in a fixed dimension therefore remains open for this line of work as a whole, and Section 7 lists it as an open question. In fact, among the nonconvex bounds in the table below, where X=ΔL/ε2 for the smoothness constant L of each bound, our hard instances use the lowest dimension: up to factors logarithmic in n and X, our dimension grows at most linearly in X, while the others grow quadratically. Appendix C fixes our dimension before the algorithm and bounds it in equation (75), and equations (128) and (129) give the dimensions for the PL bounds.
For Carmon et al. and Emmenegger et al., we obtain these dimensions by substituting their chain lengths T≍X and K≍X/n into the dimension conditions of the cited lemmas.
Q3 / W3. 1≤κ<3. Our revised result no longer needs a separate case for κ<3: Theorem 3.3 now proves Ω(n+nlog(Δ/ε)/log(1+n/(κ−1))) for every κ≥1, with the fraction taken to be zero at κ=1. The restriction κ≥3 was only a limitation of the earlier construction, and for κ≥3 the new bound equals the rates of the previous version up to constant factors. Near κ=1, however, the rate depends on κ−1 rather than on κ and decreases to n as κ↓1; choosing between gradient descent and capped Restarted PAGE attains it (Section 6.2). At κ=1, one full gradient step suffices, and Lemma D.4 gives the matching Ω(n).
W4. Algorithmic contribution. We agree and have rewritten Contribution 4 accordingly. Restarted PAGE changes only the restart schedule and the epoch length, and its role, together with gradient descent, is to show that the lower bound of Theorem 3.3 is tight. Section 7 notes that it needs (Lms,μ,Δ,ε) in advance and lists an algorithm without this requirement as an open problem.
We hope that these revisions, in particular Theorem 3.3 for every κ≥1 and the comparison with Theorem 2 of the PAGE paper, address your concerns. If they do, we would be grateful if you would consider raising your score.