PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yuxing Peng, Zhiqing Tang, Weijia Jia

arXiv:2609.00045v1cs.DScs.LGmath.OC

TL;DR

The paper asks whether randomized finite-sum IFO complexity gaps persist under individual smoothness and across PL condition numbers. It introduces dense weak hiding to prove matching lower bounds for unrestricted algorithms and shows that Restarted PAGE matches the PL rates under mean-squared smoothness. These results establish tight nonconvex complexity and resolve both PL regimes for κ≥3.

  • Problem

    Prior individual-smoothness lower bounds miss the √n factor in nonconvex IFO complexity, while PL lower bounds leave unrestricted randomized algorithms and the small-κ regime unresolved.

  • Method

    Dense weak hiding uses a fixed sign table, a bounded radial map, and a smooth gate to hide stages from unrestricted IFO queries while preserving the average signal.

  • Results

    The paper proves matching nonconvex lower bounds under individual and mean-squared smoothness and matching PL lower bounds for every κmax ≥3, while Restarted PAGE matches the PL rates.

  • Takeaways & Limitations

    Randomized IFO complexity is minimax-tight under both smoothness models, and the PL transition at √n is resolved by matching lower and upper bounds.

  • Takeaways & Limitations

    The lower bounds assume n exceeds a universal threshold, allow dimension to depend on parameters and budget, and leave fixed dimension, noisy oracles, and κ<3 open.

Abstract

from arXiv · show

Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization has remained open. Known algorithms use $O(n+\sqrt{n}\,ΔL_{\max}/\varepsilon^2)$ calls, while prior lower bounds miss a factor of $\sqrt{n}$. We prove the matching lower bound for randomized IFO algorithms whose component indices and query points may depend on the complete preceding transcript and private randomness. This determines the minimax IFO complexity up to universal constants under both individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, the standard PAGE guarantee is not tight when $κ_{\mathrm{ms}}<\sqrt{n}$. Restarted PAGE attains $O(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt{n}/κ_{\mathrm{ms}})))$ for $1\leqκ_{\mathrm{ms}}\leq\sqrt{n}$, and $O(n+κ_{\mathrm{ms}}\sqrt{n}\log(Δ/\varepsilon))$ for $κ_{\mathrm{ms}}\geq\sqrt{n}$. We prove matching lower bounds under individual smoothness for every $κ_{\max}\geq 3$; the same hard instances also give the mean-squared lower bounds. In the small-$κ_{\max}$ range, their average objective is globally strongly convex. Our lower bounds use dense weak hiding. A fixed sign table spreads each hidden direction across the components. Each queried row carries little information, while the exact row average preserves the full signal after rescaling. A bounded radial map handles arbitrary query points, and a smooth gate makes unopened links invisible to both function values and gradients. Balancing the rows needed to reveal one stage with the number of stages allowed by individual smoothness yields the missing $\sqrt{n}$ factor.

1 INTRODUCTION

The paper closes two complexity gaps: the missing √n factor for randomized IFO algorithms under individual smoothness and the unresolved PL behavior across κ=√n. Dense weak hiding yields matching lower bounds, while Restarted PAGE matches the PL rates under mean-squared smoothness.

  • Nonconvex complexity: O(n + √n ∆Lmax/ε2) is achieved by PAGE and SPIDER under mean-squared smoothness, while earlier individual-smoothness lower bounds miss the √n factor.Individual Lmax-smoothness implies mean-squared smoothness with Lms ≤ Lmax.
  • Dense weak hiding: Dense weak hiding distributes each hidden direction across a fixed sign table, preserves the signal in the finite-sum average, and makes unopened links invisible.A bounded radial map handles arbitrary query points, while a smooth gate removes unopened links from values and gradients.
  • PL complexity: Ω(n + n log(∆/ε)/(1 + log(√n/κmax))) holds for 3 ≤ κmax ≤ √n, while the large-condition-number construction yields the corresponding κmax√n logarithmic regime.In the small-κmax regime, the hard instance’s average objective is globally strongly convex.
  • PL complexity: O(n) per epoch and a Θ(κms/√n) function-gap contraction allow Restarted PAGE to match the lower bounds in both κms regimes.This improves the standard PAGE guarantee when κms < √n under mean-squared smoothness.
  • Nonconvex complexity: Ω(n + √n ∆Lmax/ε2) is the matching nonconvex lower bound for randomized IFO algorithms with unrestricted query selection.The result covers algorithms whose component choices and query points depend on the complete preceding history and private randomness.

2 RELATED WORK

Prior lower bounds either restrict algorithms to linear-span behavior, assume large condition numbers, or weaken the average signal for unrestricted queries. This paper removes the linear-span restriction and extends matching results across the relevant PL regimes.

  • Nonconvex stationarity: Prior individual-smoothness nonconvex lower bounds give only Ω(n + ∆Lmax/ε2) or Ω(∆Lmax/ε2), missing the √n factor.The missing factor occurs in the term multiplying ∆Lmax/ε2.
  • Nonconvex stationarity: The new lower bound recovers the √n factor without imposing a linear-span restriction.Its information argument handles randomized component choices and query points.
  • PL lower bounds: Earlier PL results either concern deterministic full-gradient methods, require large condition numbers, or provide only an Ω(n) bound across all condition numbers.The small-κ regime remained open for randomized IFO algorithms under individual smoothness.
  • Strongly convex relation: The small-κ hard instance has a globally strongly convex average objective even though its components need not be convex.This establishes the small-κ dependence under individual smoothness with unrestricted query selection.

3 SETTING AND MAIN RESULTS

The paper formalizes exact finite-sum IFO complexity for unrestricted randomized algorithms and proves tight nonconvex and PL rates under individual and mean-squared smoothness. The hard instances satisfy the stated smoothness conditions, with matching upper bounds from PAGE and SPIDER or Restarted PAGE.

  • Scope: The paper allows arbitrary finite ambient dimension, and the hard-instance dimension may depend on problem parameters and oracle budget.All constructed hard components are C∞.
  • Setting: An exact IFO call selects a component and query point, then returns that component’s value and gradient.The algorithm may repeat indices, stop randomly, and return an unqueried point.
  • Setting: Randomized IFO algorithms may choose component indices and query points from private randomness and the complete query-response history, without linear-span restrictions.The minimax formulation ranges over all finite dimensions.
  • Nonconvex stationarity: Ω(n + √n ∆Ls/ε2) is the tight nonconvex IFO complexity under both individual and mean-squared smoothness.PAGE and SPIDER provide the upper bound; the same hard instances establish the lower bound under both models.
  • PL complexity: The PL lower bounds apply under both smoothness models for every κs ≥ 3, with the small-κmax hard instance having a globally strongly convex average objective.The hard instances are individually Lmax-smooth and also satisfy mean-squared smoothness with bound Lmax.

4 DENSE WEAK HIDING

Dense weak hiding distributes each hidden stage direction across a fixed sign table, bounds arbitrary queries through a radial map, and gates unopened links out of values and gradients. Balancing row-revelation cost against the number of smoothness-compatible stages produces the √n factor.

  • Hiding unopened stages: A smooth gate makes unopened links contribute neither function value nor gradient below threshold a.The gate is fully open above b, with G = 1 and G′ = 0.
  • Dense weak hiding: The construction combines the sign table, radial map, and smooth gate to prevent unrestricted queries from activating later stages while preserving the average signal.These ingredients address the need to distribute hidden information across components without weakening the finite-sum average.
  • Encoding hidden directions: A fixed sign table spreads each stage direction across components while its exact row average preserves the direction after rescaling.Each queried row is only weakly biased toward the hidden direction.
  • Controlling arbitrary queries: A bounded radial map converts every query point into an alignment vector in the unit ball.Its derivative bounds do not depend on the ambient dimension, while the induced component bounds scale as O(1/ρ).
  • Complexity tradeoff: √n arises because the row-cost-per-stage times the number of stages is maximized at ρ ≍ n^-1/2.The two branches balance at nρ = ρ^-1, yielding the optimized factor.

5 INFORMATION COST OF REVEALING HIDDEN STAGES

Revealing a hidden stage remains information-limited even when component choices and query points adapt to the full transcript. Smooth gating then forces stages to be completed sequentially, so their costs add.

  • One-stage information bound: Before the row threshold is reached, history-dependent queries cross the gate with probability bounded below one-half.Repeated indices and side information independent of the hidden stage do not improve this bound.
  • One-stage information bound: At ρ ≍ n^-1/2, the mutual information in queried rows implies that revealing one stage requires Ω(n) distinct rows.Repeats add no information, even when indices are selected from previous responses.
  • Sequential revelation: Unopened future links have zero value and gradient contributions, so stages can only be completed in order except on the controlled event E_future.The event accounts for queries or final outputs crossing a future-stage alignment threshold.
  • Sequential revelation: Stage costs add because completing many stages in too few calls would require too many individually unlikely fast completions.A counting argument and Markov’s inequality bound the probability of completing J stages within N calls.

6 DERIVATION OF THE MAIN RATES

The main rates follow by multiplying the optimized per-stage revelation cost by the number of stages allowed by the calibrated smoothness and gap constraints. Two geometrically scaled PL constructions cover small and large condition-number regimes.

  • Nonconvex lower bound: Ω(√n ∆L_max/ε^2) is obtained at ρ ≍ n^-1/2, with an auxiliary quadratic supplying the complementary Ω(n) term.The calibrated construction uses T_ρ ≍ ∆L_maxρ/ε^2 stages and r_ρ = Θ(n) rows per stage.
  • Large κ_max: For large κ_max, one geometric scale serves both the gate and stage contribution, with 1 − r_w ≍ 1/(κ_maxρ).The geometric chain requires 0 < r_w < 1.
  • Small κ_max: For small κ_max, separate gate and contribution scales satisfy R_j ≪ W_j when κ_max ≪ √n.For 3 ≤ κ_max ≤ √n, the scale ratio obeys ϑ ≍ κ_max/√n and the gap decreases geometrically.
  • Global PL verification: The small-κ_max construction has a globally strongly convex average objective, while the large-κ_max construction uses the PL constant.The last gap is left by an unrevealed terminal stage or suffix.
  • Global PL verification: The constructions establish tight lower bounds under individual smoothness across both κ_max regimes, with global PL verified through open blocks and geometric weighting.Global rescaling preserves the condition number.

7 RESTARTED PAGE

Restarted PAGE uses epochs whose length adapts to κ_ms, yielding faster contraction in the small-condition-number regime and longer epochs when κ_ms is large. Its expected IFO cost matches the corresponding lower-bound rates.

  • Epoch schedule: Θ(n) PAGE epochs shrink the gap by q_ep = Θ(κ_ms/√n) when κ_ms < √n.The lower-bound construction motivates this schedule through Ω(n)-call stage revelation and geometric gap reduction.
  • Epoch schedule: For κ_ms ≥ √n, longer epochs are needed to obtain a constant contraction factor.The schedule therefore increases epoch length with κ_ms.
  • Algorithm: Algorithm 1 initializes a full gradient, then updates PAGE estimates using either a refreshed full gradient or an incremental component correction.The refresh probability is p = 1/(n + 1).
  • IFO cost: One epoch costs at most n + 3T IFO calls in expectation.The expected cost bound is stated in Lemma E.1.
  • Guarantee: The two epoch schedules match the PL upper bounds and achieve the stated constant-factor gap contraction.Appendix E proves both the contraction and the exact IFO cost.

8 CONCLUSION AND LIMITATIONS

The paper establishes tight lower bounds under individual smoothness for nonconvex optimization and both PL condition-number regimes. It also identifies open ranges and assumptions limiting the scope of these results.

  • Tight lower bounds hold under individual smoothness for nonconvex optimization and both κmax regimes under PL.
  • Restarted PAGE matches the PL rates, while the small-κmax construction has a globally strongly convex average objective.
  • Open directions include fixed ambient dimension, noisy finite-sum oracles, and the range κ < 3.
  • The lower bounds assume n exceeds a universal threshold.

AI USE STATEMENT

The paper’s supporting material separates proof dependencies and defines the shared constructions and calculus used by the lower-bound arguments. These ingredients include a smooth gate, fixed encoding table, bounded radial map, and local derivative bounds.

  • During preparation, the authors used large language model assistants for brainstorming, proof-draft review, and manuscript editing, while verifying the final manuscript.
  • The proof-dependency diagram separates shared lower-bound arguments from the nonconvex, PL, and Restarted PAGE branches.
  • The shared lower-bound construction uses a smooth threshold gate, fixed encoding table, and bounded radial map.
  • The gate is flat below its threshold, so unopened links contribute neither function value nor gradient.
  • The encoding table is sampled before interaction, with component rows whose exact average preserves the hidden direction’s signal.
  • The bounded radial map keeps alignment vectors in the unit ball and supports the derivative bounds used in the hard constructions.

B.1 ONE-STAGE INFORMATION BOUND

The one-stage information bound analyzes how adaptively selected rows reveal a hidden direction. Exchangeability limits information from unseen rows, and the resulting row lower bound feeds the multi-stage nonconvex complexity lower bound.

  • Encoding table: Each encoding-table column contains a fixed number of signs determined by the hidden coordinate, uniformly permuted across rows and sampled once before interaction.
  • One-stage protocol: The stronger information protocol reveals each complete encoding row after an adaptively chosen component index, with repeated rows adding no new information.
  • Optimized bias: At the optimized bias ρ = Θ(n^-1/2), revealing a stage requires Ω(n) distinct rows.
  • Information bound: Conditional exchangeability makes every newly selected unseen row uniformly distributed among the remaining rows.
  • Information bound: The mutual information in the first r distinct rows is bounded by O(Drρ^2), and data processing converts this into a bound on early alignment.
  • Nonconvex lower bound: The resulting multi-stage construction yields an Ω(√n ΔLmax/ε^2) lower bound when the optimized stage count is at least two.

C.5 THE LINEAR SAMPLE-SIZE TERM

When the optimized multi-stage construction has fewer than two stages, an auxiliary quadratic supplies the linear-sample-size term. Combining this coarse regime with the multi-stage regime establishes the full bound.

  • When T < 2, an auxiliary quadratic gives the full lower bound.
  • The optimized-bias condition T ≥ 2 is equivalent, up to universal constants, to the regime where the second complexity term is at least a constant multiple of n.
  • The auxiliary quadratic uses dimension D0 = 4 and remains within the required dimension bound.
  • Combining the two regimes proves the fixed-budget claim in Theorem 3.1.

D PROOFS FOR THE GLOBAL PL BOUNDS

The proofs establish global PL lower bounds across both condition-number regimes using weighted and two-scale chains, with dense hiding preserving stage independence and individual smoothness. The resulting constructions yield matching bounds, including the small-κ regime where the average objective is strongly convex.

  • Global lower-bound framework: Every κmax ≥ 3 is covered by individually Lmax-smooth hard instances, and the same lower bounds extend to the mean-squared class.The weighted and two-scale constructions cover large and small condition-number regimes, respectively.
  • Global lower-bound framework: Geometric stage scales prevent the PL constant from shrinking with chain length by making the first unfinished stage control later contributions.Equal scales would let the remaining contribution grow with the number of unfinished stages.
  • Dense weak hiding: The shared encoding uses fixed sign tables, row-wise component terms, and smooth gates whose zero value and derivative hide unopened links.The row average recovers the hidden direction exactly, while gates distinguish completion threshold a from full-opening threshold b.
  • Weighted chain: The weighted chain decomposes the gap into nonnegative block terms: fully open blocks use strong convexity, while the first incompletely open gate supplies a gradient barrier.The remaining weighted contributions are bounded so the first unfinished stage controls the global PL argument.
  • Assembly across regimes: The assembled lower bounds cover the small-κmax regime, the bounded transition, and the large-κmax regime, with an auxiliary quadratic supplying the additive O(n) case.The two-scale chain establishes the small regime and transition, while the weighted chain handles sufficiently large κmax.
  • Two-scale chain: The two-scale chain is individually Lmax-smooth, and its average is globally strongly convex when 3 ≤κmax ≤√n.Separating gate and contribution scales permits hiding later stages without exceeding component curvature budgets.

E RESTARTED PAGE UPPER BOUND

Restarted PAGE improves PL optimization by using full-gradient restarts and regime-dependent epoch lengths, achieving matching rates under mean-squared smoothness.

  • Small condition numbers: Θ(log(Δ/ε)/[1 + log(√n/κ_max)]) stages suffice in the small-condition-number regime because each hidden stage costs Ω(n) calls and shrinks the gap by Θ((κ_max/√n)^2).This gives the sharper restarted rate below the √n transition.
  • Epoch contraction: O(n) expected IFO calls per epoch yield a PAGE contraction of Θ(κ_ms/√n) when the epoch length is Θ(n).The epoch begins with an exact full gradient; refresh and difference updates keep expected update cost bounded.
  • Guarantee: Restarted PAGE returns an expected gap at most ε under global μ-PL and mean-squared smoothness, with the guarantee extended to 1 ≤ κ_ms < 3.The proof uses repeated epoch conditioning and an expected epoch contraction.
  • Large condition numbers: O(n + κ_ms√n log(Δ/ε)) applies when κ_ms ≥ √n, where the standard PAGE schedule has a fixed contraction factor.Here the optimized epoch length is Θ(κ_ms√n), and the additive one-epoch cost is absorbed under ε ≤ cΔ.

F.3 APPLICATIONS TO UPPER AND LOWER BOUNDS

The appendix converts fixed-budget and expected-budget guarantees while formalizing randomized IFO algorithms and the smoothness classes used by the main theorems.

  • Upper bounds: 1 − δ success probability follows by applying Restarted PAGE at target δε/2 and capping its expected call count.For fixed δ, the adjustment changes log(Δ/ε) only by an additive constant.
  • Lower bounds: The resulting fixed-budget lower bounds imply the expected nonconvex and PL lower bounds after constant-factor truncation and target rescaling.The conclusions are identified with Theorems 3.1 and 3.3.
  • IFO model: Randomized IFO algorithms may choose repeated component indices, arbitrary query points, randomized stopping times, and unqueried outputs based on the full transcript.The formal filtration makes each query measurable with respect to preceding history and private randomness.
  • Theorem scope: The new upper bounds use κ_ms, while the lower bounds use κ_max and remain valid for mean-squared smoothness because the hard instances are individually smooth.The PL lower bound covers every κ_max ≥ 3, and the small-κ_max hard instances have a globally strongly convex average objective.

G.2 ASSUMPTIONS ON THE FUNCTION CLASSES

The appendix distinguishes individual and mean-squared smoothness, shows why componentwise substitutions can fail, and verifies that the dense chain retains comparable smoothness under both assumptions.

  • Counterexamples: Mean-squared smoothness does not imply three componentwise inequalities at the same numerical constant: uniform component bounds, co-coercivity, and separate-reference-point bounds.Proposition G.1 establishes convex quadratic counterexamples for all three claims.
  • Counterexamples: √n larger component Lipschitz constants can coexist with mean-squared smoothness constant ℓ, invalidating sampled-component descent or self-bounding substitutions.A one-nonzero-component quadratic realizes this separation exactly.
  • Counterexamples: L ≥ √n ℓ is required in the displayed Bregman-type bound for the counterexample family, despite mean-squared constant ℓ.The right-hand side with the smaller substituted constant is only ℓ^2/√n.
  • Counterexamples: Mean-squared smoothness controls components at one common pair (z, w), not estimates pairing each component with its own reference point ϕ_i.This distinction explains the failure of the separate-reference-point inequality.
  • Dense-chain verification: L_ms = Θ(L_max) for the dense chain, independently of n, D, and T.The upper bound follows from individual smoothness, while the lower bound is obtained from a Hessian witness after scaling.
Loading 2609.00045v1…