Research map / Optimization / Nonconvex and smooth optimization

Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Proximal finite-sum methods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a proximal preconditioned gradient framework (anisotropic proximal gradient with spectral reference functions) that extends Muon/Scion to composite nonconvex constraints, with stochastic convergence under heavy-tailed noise and STORM variance reduction.

Problem

Stochastic spectral/sign-type gradient methods (Muon, Scion) are analyzed mostly for unconstrained problems; constrained or nonconvex-regularized settings and heavy-tailed noise are poorly understood.

Approach

A proximal anisotropic preconditioned gradient step with a strongly convex reference function phi whose dual gradient gives a nonlinear preconditioner (matrix sign approximation); the backward step is an anisotropic prox allowing nonconvex indicator constraints (spectral sphere, Stiefel), with a new stationarity gap D_{phi*}(grad f, -subgrad g) and analysis under heavy-tailed noise.</218>

Key results

• Deterministic sufficient decrease F(x^{k+1}) <= F(x^k) - gamma*G(x^k) with gap G vanishing sublinearly, giving min gap <= (F(x^0)-F*)/(gamma K).
• Stochastic heavy-tailed (p in (1,2]) rate of O(K^{-min{1/4,(p-1)/(2p)}}) for averaged gap.
• STORM variant achieves tilde-O(K^{-1/3}) averaged gap under bounded variance, improving on the heavy-tailed rate at the cost of one extra sample per iteration.

Surprising findings

• Naive Euclidean proximal steps can have fixed points that are not stationary points of the original problem, unless the reference function has special structure.

Limitations

• Analysis does not yield convergence rates for standard stationarity measures; only the custom gap is bounded.
• Stochastic analysis assumes bounded domain of reference function and Lipschitz smooth f.
• Stochastic gradient estimates lead to bias from nonlinear preconditioning, so the plain stochastic estimate is not analyzed.

Experimental setup

Metrics: stationarity gap gradient norm

Baselines: Muon Scion

Builds on: Muon Scion anisotropic proximal gradient STORM

Closest papers by meaning

• Phases of Muon: When Muon Eclipses SignSGD (NeurIPS 2026 · similarity 0.87)
• Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.86)
• Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.86)
• Intrinsic Muon: Spectral Optimization on Riemannian Matrix Manifolds (NeurIPS 2026 · similarity 0.86)
• Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.85)
• Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients? (NeurIPS 2026 · similarity 0.85)