CS Paper Radar

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

Yuxing Peng, Zhiqing Tang, Weijia Jia

cs.DS cs.LGmath.OC ·submitted 2026-08-30 02:47 UTC · v3
theoryhighly cited

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.

Comment
56 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG math.OC ·2026-10-04 ·Qihao Zhou
theoryhighly cited similarity 0.66
Abstract · 30 pages, 2 figures, 2 tables

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.

0.33

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

cs.LG math.OC ·2026-10-04 ·Qihao Zhou
theory similarity 0.65
Abstract · 21 pages, 1 figure, 2 tables

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point $y$ and a certificate $g\in G(y)$ with $(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon$ using $\mathcal{O}(n+\sqrt{n}LR/\varepsilon)$ expected component evaluations and resolvent evaluations. It removes the additive $n\log n$ cost of restarting a variance-reduced solver at every regularization stage by switching to a centered stochastic proximal iteration at regularization strength $L/\sqrt{n}$. Carrying an operator estimate between the remaining stages limits their total cost to $\mathcal{O}(n)$. A matching $Ω(n+\sqrt{n}LR/\varepsilon)$ lower bound holds for randomized linear-span component-oracle algorithms with adaptive stopping and expected query budgets. Thus, for $0<\varepsilon\le LR/2$, our method attains the optimal worst-case expected component complexity in this oracle model, up to universal constants.

0.39

Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums

cs.DS math.OC ·2026-11-04 ·Qihao Zhou
theory similarity 0.64
Abstract · 30 pages, 2 tables

We study the component-oracle complexity of finding approximate local minima of nonconvex finite sums under mean-squared averaged smoothness with parameter $L$ and a $ρ$-Lipschitz average Hessian. Each query returns the value, gradient, and one Hessian-vector product of a component. We show that the complexity in the high-accuracy regime $\varepsilon\le c_0L^2/(nρ)$ is $\tildeΘ(n^{3/4}L^{1/2}ρ^{1/4}Δ\varepsilon^{-7/4})$ for a sufficiently large initial gap $Δ$. We attain the upper bound by adapting the inverse solver and eigenvector routine of FastCubic to averaged smoothness. Our lower bound assigns the bridge edges of a nested chain to random components; a replicated spectral construction gives the same bound for unrestricted randomized algorithms. Under individual smoothness, a factor of $n^{1/4}$ remains for $\varepsilon\le cL^2/(n^2ρ)$, up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses $\tilde O(n+\sqrt{n}LΔ\varepsilon^{-2})$ queries and matches a lower bound from dense weak hiding.

0.42

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

cs.LG math.OC ·2026-09-20 ·Guy Kornowski
theoryhighly cited similarity 0.63
Abstract · 13 pages

We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.

0.54

On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

cs.LG ·2026-11-03 ·Yuxing Peng, Zhiqing Tang, Weijia Jia
similarity 0.63
Abstract · 50 pages, including appendices and references. Lean 4 formalization of the lower bounds in the ancillary files

Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $κ$, started from a point with primal gap at most $Δ$ and joint gradient norm at most $\sqrt{2LΔ}$. For $\varepsilon^2/(LΔ)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+κ)$, including initialization. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.

0.23

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

cs.LG math.OC ·2026-09-25 ·Qihao Zhou
theory similarity 0.62
Abstract · 20 pages

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $μ$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $σ\ge\varepsilon$, the worst-case complexity of zero-respecting algorithms is $Θ(κLGσ^2\varepsilon^{-4})$ in the stated accuracy regime, where $κ=L/μ$, $G$ bounds the initial primal-dual gap, and $σ^2$ bounds the variance of a general unbiased first-order oracle. The lower bound is realized on a smooth problem class with a bounded dual box. Our construction routes each link of a nonconvex zero-chain through a dual gradient of magnitude proportional to $\varepsilon/\sqrtκ$, while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $Ω(LΔ(\sqrtκ\varepsilon^{-2}+κσ^2\varepsilon^{-4}))$ after combination with the known deterministic bound, where $Δ$ bounds the initial primal function gap.

0.44

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

cs.LG math.OC ·2026-10-09 ·Sebastian Pokutta
theory similarity 0.62
Abstract

Recent results [arXiv:2602.04378, arXiv:2602.22608] have established worst-case objective-error lower bounds of order $1/T^2$ after $T$ linear minimization oracle (LMO) calls, matching the upper bound [arXiv:1406.1305] in its dependence on $T$ and thereby resolving a long-standing open question. Upon close inspection, however, both lower bounds are somewhat brittle. The first [arXiv:2602.04378] applies only to the standard Frank--Wolfe algorithm, and, as we show, its prescribed slow exact-line-search trajectories can amplify sufficiently small initialization errors exponentially, corresponding to roughly one additional bit of initialization accuracy per iteration. The second [arXiv:2602.22608] obtains lower bounds for any deterministic LMO-based first-order method via a resisting oracle that adversarially adapts to the queries of the algorithm. In both cases it is conceivable that randomization may circumvent these lower bounds; in particular, neither establishes a lower bound for unrestricted randomized first-order LMO methods. We close this gap by proving an $Ω(L\operatorname{diam}(S)^2/T^2)$ distributional lower bound for randomized first-order linear minimization oracle methods over strongly convex sets. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We further show that the same error threshold holds with probability at least $3/4$ and yields a stopping-time tail bound.

0.17

Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

cs.LG math.OCstat.ML ·2026-10-17 ·Qihao Zhou, Shanshui Niu
similarity 0.62
Abstract · 23 pages, 2 figures, 1 table

We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.

0.11