acceptodds
Under review as a conference paper at ICLR 2027

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

Abstract

Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization is still open. Known algorithms use calls, but the best lower bounds miss a factor of on the term. We prove the matching lower bound . Thus PAGE and SPIDER are minimax optimal up to universal constants, under both individual and mean-squared smoothness. Unlike earlier bounds for linear-span algorithms, our result applies to the broader class of randomized IFO algorithms, allowing arbitrary choices of component indices and query points based on the complete preceding history. Under the global Polyak–Lojasiewicz (PL) condition, we use a similar idea to obtain an lower bound for large . We also note that existing PL lower bounds have explored only relatively large values of . To fill this gap, we study the regime and obtain a new lower-bound rate, . The new lower bound motivates us to propose Restarted PAGE. Its upper bound matches the new rate for small and recovers the standard PAGE rate for large , so both lower bounds are nearly tight. Our new lower bounds are based on our proposed dense weak hiding construction. By spreading each hidden direction across all components, the construction makes every single IFO query weakly informative while preserving the direction in the full row average. Because unrevealed stages remain inactive even for arbitrary query points, an algorithm must spend many calls to expose a stage before it can make substantial progress. We choose the bias to balance this revelation cost against the number of stages permitted by individual smoothness, and this balance produces the missing factor.

Primary area:
optimization
Keywords:
finite-sum optimization, oracle complexity, lower bounds, nonconvex optimization, Polyak-Lojasiewicz condition, individual smoothness

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_BLoJOpenReview ↗
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
  1. 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.

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

  3. Is the restriction κ ≥ 3 only a limitation of the construction, or do you expect a different optimal rate for 1 ≤ κ < 3?

2 comments
AuthorsOpenReview ↗

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\sqrt{n} was indeed already known, both for linear-span algorithms (Theorem 2 of the PAGE paper) and, when n=O(Δ2Lms2/ε4)n=O(\Delta^2 L_{\rm ms}^2/\varepsilon^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)\Omega(n+\Delta L_{\max}/\varepsilon^2) for linear-span algorithms that sample components from a fixed distribution (Han et al., 2024), and only Ω(ΔLmax⁡/ε2)\Omega(\Delta L_{\max}/\varepsilon^2) for arbitrary queries (Emmenegger et al., 2022). Our contribution is therefore the factor n\sqrt{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. κ\kappa-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 κ\kappa-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-κ\kappa regime ends at κmax⁡≍n\kappa_{\max}\asymp n rather than at n\sqrt n. Lower bounds built directly for PL objectives, in turn, give κ\kappa-dependent rates only for large condition numbers, namely κF=LF/μ≳106\kappa_F=L_F/\mu\gtrsim10^6 (Yue et al., 2023) and κms≳105n\kappa_{\rm ms}\gtrsim10^5\sqrt n (Bai et al., 2024), whereas Theorem 3.3 holds for every κ≥1\kappa\ge1 and for unrestricted randomized algorithms, with the range 1<κmax⁡≤n1<\kappa_{\max}\le\sqrt 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/ε2X=\Delta L/\varepsilon^2 for the smoothness constant LL of each bound, our hard instances use the lowest dimension: up to factors logarithmic in nn and XX, our dimension grows at most linearly in XX, 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.

Randomized lower boundDimension of the hard instances
Carmon et al. (2020, Lemma 5)Θ~(X2)\tilde{\Theta}(X^2)
Fang et al. (2018, Theorem 3)Θ~(n2X2)\tilde{\Theta}(n^2X^2)
Emmenegger et al. (2022, Lemma 4.6)Θ~(nX2)\tilde{\Theta}(nX^2)
Ours (equation (75))O~(1+X/n)\tilde{O}(1+X/\sqrt{n})

For Carmon et al. and Emmenegger et al., we obtain these dimensions by substituting their chain lengths T≍XT\asymp X and K≍X/nK\asymp X/n into the dimension conditions of the cited lemmas.

Q3 / W3. 1≤κ<31\le\kappa < 3. Our revised result no longer needs a separate case for κ<3\kappa<3: Theorem 3.3 now proves Ω(n+nlog⁡(Δ/ε)/log⁡(1+n/(κ−1)))\Omega\bigl(n+n\log(\Delta/\varepsilon)/\log(1+\sqrt n/(\kappa-1))\bigr) for every κ≥1\kappa\ge1, with the fraction taken to be zero at κ=1\kappa=1. The restriction κ≥3\kappa\ge3 was only a limitation of the earlier construction, and for κ≥3\kappa\ge3 the new bound equals the rates of the previous version up to constant factors. Near κ=1\kappa=1, however, the rate depends on κ−1\kappa-1 rather than on κ\kappa and decreases to nn as κ↓1\kappa\downarrow1; choosing between gradient descent and capped Restarted PAGE attains it (Section 6.2). At κ=1\kappa=1, one full gradient step suffices, and Lemma D.4 gives the matching Ω(n)\Omega(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,μ,Δ,ε)(L_{\rm ms},\mu,\Delta,\varepsilon) 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\kappa\ge1 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.

Reviewer_BLoJOpenReview ↗

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.

Reviewer_HWH9OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at finite sum problems with n components, under the setting that each component is L-smooth. It closes a n\sqrt{n} gap between the lower and upper bounds on the IFO complexity. For the PL setting some slightly stronger bounds are provided (both lower and upper), depending on condition numbers. The paper introduces a "dense weak hiding" construction for building their lower bounds. The gap closed is meaningful, because it had been identified and known to exist in the literature.

Critical strengths
  • The proof construction is interesting
  • The paper closes a known gap in the finite-sum literature
  • The small kappa lower-bound (PL case) seems to improve on the best known results.
Critical weaknesses
  • Not super critical, but the paper's claims on the PL side should be made in more precise and moderate language, they're a bit overstated.

See for instance [1], that proves essentially the same lower and upper bounds (analyzing prox-svrg and katyusha), in the setting that the average of the n functions is strongly convex; the present paper "extends" that to the PL case, but of course, that's a rather minor extension (it should follow quickly PAGE’s squared-gradient estimate plus a restart schedule). As a result, the authors should not overclaim their work's novelty in the PL case. Contribution 4 needs to be updated as a result.

Please double check claim in the related work: "Under individual smoothness, no lower bound showed any dependence on κ" --- the paper of Han, Xie, Zhang cited in the authors' work contains lower bounds with kappa dependence which also apply to PL functions.

[1] Hannah, Liu, O’Connor, Yin. Breaking the Span Assumption Yields Fast Finite-Sum Minimization. Neurips 2018.

Questions for authors
  • What about a more precise comparison to the theory / bounds that Katyusha has (their bound has a n3/4κn^{3/4}\kappa in it)
  • More broadly, how would you position the PL results more sharply given the existing strongly convex results (at least for lower bounds it is obvious, an SC lower bound is automatically a PL lower bound), but more broadly, because by now the jump from SC to PL is not that big as it used to be in the early days
  • The exposition of the sequential hiding proof needs to be clarified. In particular, the causal order between the information analyzed across lemmas B.4--B.7 are not spelled out
  • In the analysis (especially, in the appendix) there's numerous constants and factors floating around. It seems the authors have made not effort to clean them up or tighten. Can they clean some of those up? It is hard to keep track of so many numbers.
2 comments
AuthorsOpenReview ↗

Response to Reviewer HWH9

Thank you for the review and for pointing us to Hannah et al. (2018).

W1 and Q2. PL claims and positioning. We agree regarding the upper bound. Hannah et al. (2018, Theorem 3) already obtain the small-κ\kappa acceleration for strongly convex averages of nonconvex components, so the revision cites their result in the introduction, Section 2, Table 1, and Section 6.2, and Contribution 4 no longer presents this acceleration as new. Restarted PAGE carries the acceleration over to PL objectives, and together with gradient descent it shows that our lower bound is tight.

The main PL contribution is therefore the lower bound of Theorem 3.3, which holds for every κ≥1\kappa\ge1. It also bears on the question that Hannah et al. leave open: they note that lower bounds for strongly convex averages of nonconvex components are lacking (p. 3 of the NeurIPS version), and their own lower bound (Theorem 2) assumes strongly convex components and oblivious algorithms. For 1<κmax⁡≤n1<\kappa_{\max}\le\sqrt n, our hard instances have a strongly convex average, so our lower bound also holds for this class (Corollary D.3). For κmax⁡≫n\kappa_{\max}\gg\sqrt n, in contrast, Katyusha X solves problems in this class with fewer calls than our PL lower bound, so the bound separates PL finite sums from strongly convex averages of nonconvex components (Q1).

W2. κ\kappa-dependence. We have removed the sentence. Section 2 now notes that strongly convex lower bounds, including the κ\kappa-dependent bounds of Han et al. (2024, Theorems 63 and 66), apply to the PL class. Han et al., however, prove these bounds for a linear-span PIFO class, and under individual smoothness their small-κ\kappa regime ends at κmax⁡≍n\kappa_{\max}\asymp n rather than at n\sqrt n. Lower bounds built directly for PL objectives, in turn, give κ\kappa-dependent rates only for large condition numbers, whereas Theorem 3.3 holds for every κ≥1\kappa\ge1 and for unrestricted randomized algorithms, with the range 1<κmax⁡≤n1<\kappa_{\max}\le\sqrt n covered by our two-scale chain (Section 6.1).

Q1. Katyusha. For strongly convex averages of nonconvex components, Katyusha X uses O((n+n3/4κmax⁡)log⁡(Δ/ε))O\bigl((n+n^{3/4}\sqrt{\kappa_{\max}})\log(\Delta/\varepsilon)\bigr) calls (Allen-Zhu, 2018b, Corollary 4.4). For κmax⁡≫n\kappa_{\max}\gg\sqrt n, our lower bound Ω(κmax⁡nlog⁡(Δ/ε))\Omega(\kappa_{\max}\sqrt n\log(\Delta/\varepsilon)) is larger by a factor of order κmax⁡/n\sqrt{\kappa_{\max}/\sqrt n}, so in this regime PL finite sums are strictly harder than this class (Section 2 and Table 1).

Q3. Causal order. The former results B.4–B.8 are now a single theorem, Theorem B.2. Its proof sets out the interaction and its analysis in five steps, in the order in which information becomes available, and Section 5.2 gives the same timeline in the main text.

Q4. Constants. We have rewritten and shortened Appendices A–C. The start of Appendix A lists the main shared constants, with their values or defining equations and the order in which they are fixed, while other constants are defined where they are first used and one-off factors are written as numbers.

We hope that these revisions, in particular the repositioning of our PL results relative to Hannah et al. (2018) and the rewritten Appendices A–C, address your concerns. If they do, we would be grateful if you would consider raising your score.

Reviewer_HWH9OpenReview ↗

update

Thanks for your clarifications and the positioning. In my opinion the net contribution is still modest, and I find it hard to champion the paper further, and would like to maintain my score.

Reviewer_3Rn4OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers the IFO complexity of 1) nonconvex 2) global PL finite-sum optimization. They prove matching lower bound for nonconvex case and propose Restarted PAGE to establish a new upper bound that matches the known lower bound.

I think I lack the technical (including information-theoretical) background to fully understand the paper especially the lower bound construction.

Critical strengths

The theoretical results seem substantial, closing the gaps in both nonconvex and global PL finite-sum optimization.

Critical weaknesses

The paper can be too technical. It seems hard to get an intuition of the lower bound.

Questions for authors

None

1 comment
AuthorsOpenReview ↗

Response to Reviewer 3Rn4

Thank you for the review. We agree that the previous version was too technical, and the revision adds intuition before the formal arguments.

In short, each hidden stage is spread over all nn components with a small bias ρ\rho, so a new component reveals little while the average gradient keeps the full direction, and finding a stage takes about min⁡{n,ρ−2}\min\lbrace n,\rho^{-2}\rbrace distinct components. Rescaling the components by 1/ρ1/\rho restores the average signal to unit size but multiplies their curvature by 1/ρ1/\rho, so individual smoothness allows about ρΔLmax⁡/ε2\rho\Delta L_{\max}/\varepsilon^2 stages. The resulting lower bound, about min⁡{nρ,ρ−1}ΔLmax⁡/ε2\min\lbrace n\rho,\rho^{-1}\rbrace\Delta L_{\max}/\varepsilon^2 calls, is largest at ρ≍n−1/2\rho\asymp n^{-1/2}, where it equals nΔLmax⁡/ε2\sqrt{n}\Delta L_{\max}/\varepsilon^2.

In the revision, paragraph 3 of the introduction explains why earlier constructions lose n\sqrt n and how dense weak hiding recovers it, Section 4 (with Figure 1) derives the tradeoff above, and Section 5 explains the information argument, first for one stage and then across stages. Each appendix starts with an overview, Figure 2 shows the proof dependencies, and the start of Appendix A lists the main constants shared across the lower-bound proofs.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

Thank you all for the reviews. We summarize the main changes in the revised PDF below; the individual replies give the details.

  1. PL for every κ≥1\kappa\ge1. The previous version required κ≥3\kappa\ge3, whereas Theorem 3.3 now proves Ω(n+nlog⁡(Δ/ε)/log⁡(1+n/(κ−1)))\Omega\bigl(n+n\log(\Delta/\varepsilon)/\log(1+\sqrt n/(\kappa-1))\bigr) for every condition number κ≥1\kappa\ge1 (κmax⁡\kappa_{\max} or κms\kappa_{\rm ms}), with the fraction taken to be zero at κ=1\kappa=1. Since choosing between gradient descent and capped Restarted PAGE matches this bound, the bound is tight.
  2. Positioning. For nonconvex finite sums under individual smoothness, the best previous lower bound, Ω(n+ΔLmax⁡/ε2)\Omega(n+\Delta L_{\max}/\varepsilon^2), holds only for a restricted linear-span class (Han et al., 2024), whereas Theorem 3.1 proves Ω(n+nΔLmax⁡/ε2)\Omega(n+\sqrt{n}\Delta L_{\max}/\varepsilon^2) without any linear-span restriction. Table 1 now also lists Fang et al. (2018, Theorem 3) and Theorem 2 of the PAGE paper in its nonconvex part, as well as Hannah et al. (2018, Theorem 3) and Katyusha X in its PL part, and we have rewritten the introduction, Section 2, and Contribution 4 accordingly.
  3. Intuition. Paragraph 3 of the introduction now explains why earlier constructions lose the factor n\sqrt{n} and how dense weak hiding recovers it, and Sections 4 (with Figure 1) and 5 explain the construction and the information argument before the formal proofs.
  4. Appendices. We have rewritten and shortened Appendices A–C. Each appendix now starts with an overview, Figure 2 shows how the proofs depend on each other, and the start of Appendix A lists the main shared constants.
  5. Lean. To help readers check our main result, the updated supplementary material contains a Lean 4 formalization of Theorem 3.1, the lower bound Ω(n+nΔLmax⁡/ε2)\Omega(n+\sqrt{n}\Delta L_{\max}/\varepsilon^2) for randomized IFO algorithms under individual smoothness. The formalization follows the revised Appendices A–C, builds with no sorry, and uses only Lean's standard axioms.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.