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

Yuxing Peng; Zhiqing Tang; Weijia Jia

cs.DSAug 30, 2026

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

Authors: Yuxing Peng, Zhiqing Tang, Weijia Jia

Organizations: Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, BNU-HKBU United International College, Zhuhai 519087, China

Abstract

Under individual smoothness, known algorithms for nonconvex finite-sum optimization use $O(n+\sqrt nΔL_{\max}/\varepsilon^2)$ incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor $\sqrt n$ in the second term. We prove the matching lower bound $Ω(n+\sqrt nΔL_{\max}/\varepsilon^2)$ for randomized IFO algorithms, allowing component indices and query points to depend on the complete preceding history. Thus PAGE and SPIDER are minimax optimal up to universal constants under individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, prior lower bounds did not capture the correct dependence on $n$ under individual smoothness, and the regime of small $κ$ remained open for randomized IFO algorithms. We prove an $Ω(n+κ_{\max}\sqrt n\log(Δ/\varepsilon))$ lower bound for $κ_{\max}\ge\sqrt n$ , and an $Ω(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt n/κ_{\max})))$ lower bound for $3\leκ_{\max}\le\sqrt n$ . Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of $κ_{\rm ms}=L_{\rm ms}/μ$ . Our lower bounds use dense weak hiding. Each hidden direction is spread across all components, making individual queries weakly informative while preserving the direction in the average. A sufficiently large dimension makes premature activation of future stages unlikely within the query budget. Balancing the cost of revealing a stage against the number of stages permitted by individual smoothness yields the missing $\sqrt n$ factor.

Figures & tables

Nonconvex stationarity
Result	Oracle complexity	Algorithm class	Reference
Upper	$\displaystyle O\!\left(n+\sqrt{n}\,\Delta L_{\rm ms}/\varepsilon^{2}\right)$	PAGE / SPIDER	Fang et al.,2018 ; Li et al.,2021
Lower	$\displaystyle\Omega\!\left(\Delta L_{\max}/\varepsilon^{2}\right)$	randomized methods; arbitrary queries	Emmenegger et al.,2022
Lower	$\displaystyle\Omega\!\left(n+\Delta L_{\max}/\varepsilon^{2}\right)$	linear-span IFO / PIFO	Zhou and Gu,2019 ; Han et al.,2024
New [-2pt] lower	$\displaystyle\boldsymbol{\Omega\!\left(n+\sqrt{n}\,\Delta L_{\max}/\varepsilon^{2}\right)}$	randomized IFO algorithms	Theorem 3.1

Table 1: Finite-sum bounds; lower bounds hold with constant success probability.

Figure 1: Dense weak hiding. (A) A fixed sign table encodes each stage direction; the blue outline marks the row accessed when component

i

is queried, and averaging all rows gives

\rho\Theta^{(j)}

. (B) Below

a

, the link immediately following stage

j

contributes neither value nor gradient. On

\mathcal{E}_{\mathrm{future}}^{c}

, later links remain inactive while stage

j

is current. (C) The product of the row cost per stage and the number of stages is proportional to

g_{n}(\rho)

, which is maximized at

\rho\asymp n^{-1/2}

and yields

\sqrt{n}

Figure 2: Proof dependencies for the main results. Appendices F and G supply the transfers and conventions used by the branches proving the lower and upper bounds.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: One-stage encoding when row indices are selected from the observed history. Column

\ell

of the fixed table encodes

\Theta_{\ell}

. In the stronger protocol used for the information bound, a new component index is chosen before its row is observed, so exchangeability determines the conditional law of the next unseen row.

Figure 4: The completion condition is evaluated on a query fixed from the preceding history. Only afterward can the augmented interaction reveal the completed direction and an initialization row for the next stage.

Figure 5: Weighted PL inequality. The decomposition of the gap by blocks gives nonnegative terms. If every gate is fully open, strong convexity of one block directly controls the gap. Otherwise, the first gate that is not fully open gives the gradient barrier, while

\mathcal{T}(w)

bounds all later contributions. The threshold

b

for full opening is distinct from the completion threshold

a

Figure 6: Why two spatial scales are needed in the small-

\kappa

construction. The short scale

R_{j}

makes the gate locally flat before it opens and thereby hides later stages. Using that same scale for the stage contribution would exceed the

L_{\max}

Hessian budget of a component. The longer scale

W_{j}

, together with the amplitude decay, reduces the nonlinear component curvature to at most

L_{\max}/28

. Averaging contributes the factor

\rho

, and the positive quadratic then gives

\nabla^{2}F_{\rm ts}\succeq\bar{\mu}I

Figure 7: Containment relations for the algorithm and function classes. The lower bounds allow algorithms from the outermost class in panel (A), while the hard instances belong to the innermost class in panel (B). For the function classes, the inclusions use the same numerical smoothness bound

L

Class	Defining regularity	Representative sources
$\mathcal{F}_{\rm ind}^{n}$	$\max_{i}\\|\nabla f_{i}(x)-\nabla f_{i}(y)\\|\leq L_{\max}\\|x-y\\|$	Finite-sum lower bounds and analyses of component gradient updates or stored gradients ( Zhou and Gu, 2019 ; Han et al., 2024 ; Emmenegger et al., 2022 ; Defazio et al., 2014 ; Kavis et al., 2022 ) ; this work.
$\mathcal{F}_{\rm ms}^{n}$	$\bigl(n^{-1}\sum_{i}\\|\nabla f_{i}(x)-\nabla f_{i}(y)\\|^{2}\bigr)^{1/2}\leq L_{\rm ms}\\|x-y\\|$	PAGE and SPIDER ( Fang et al., 2018 ; Li et al., 2021 ) ; Zhou and Gu (2019, Definition 3.2) ; PL lower bounds in Bai et al. (2024) .
$\mathcal{F}_{\rm obj}^{n}$	$\\|\nabla F(x)-\nabla F(y)\\|\leq L_{F}\\|x-y\\|$	Lower bounds for stationary points of the full objective ( Carmon et al., 2020 ; Carmon et al., 2021 ) .

Appendix

Table 2: Definitions and representative analyses for the function classes in Figure 7 .

Oracle Complexity

Oracle complexity studies how many queries to limited-information procedures algorithms need to solve optimization, learning, sampling, and related problems.

See all 30 papers

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
Oct 4, 2026Qihao ZhouMin-Max Optimization Oracle Complexity
Independent Researcher
Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Jun 3, 2026Dongruo ZhouOptimization Convergence Analysis Nonconvex Optimization
Department of Computer Science, Indiana University Bloomington, IN 47408, USA
On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
Oct 14, 2026Yuxuan Xia, Xiao-Tong YuanZeroth-Order Optimization Nonconvex Stochastic Optimization

Oct 4, 2026J/K move · Enter open · S save

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

Qihao Zhou

Independent Researcher

Min-Max Optimization Oracle Complexity

Open paper AskPDF arXiv

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is

\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2})

throughout

κ=L/μ\ge1

, under exact dual initialization and for

0<\varepsilon^2\le c_0LΔ

, where

c_0>0

is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for

κ\ge\sqrt{n}

. For

1\leκ\le\sqrt{n}

, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains

\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2})

with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most

\varepsilon^2

. Under individual smoothness, we also prove

Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2})

for every

κ\ge1

. It matches the polynomial upper rate for a bilinear subclass when

κ\ge n

; the intermediate-condition-number gap remains open.

Abstract

Oracle Complexity

Explore similar work

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization