Research map / Optimization / Nonconvex and smooth optimization

Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity · 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 RSC-ZO, a two-point zeroth-order method that clips each scalar directional derivative before aggregation, giving high-probability nonconvex stationarity guarantees under weak-L_p sample-gradient noise (possibly infinite variance).

Problem

Stochastic zeroth-order optimization of smooth nonconvex objectives when sample-gradient noise is heavy-tailed and may violate bounded-variance assumptions; existing heavy-tailed ZO theory is mostly convex.

Approach

Clip each two-point scalar directional derivative (not the aggregated gradient vector) before averaging along random directions, and transfer weak-L_p control of the sample-gradient noise to these scalar estimates via shared randomness and a localized concentration argument.

Key results

• On RoBERTa-large with k=512, RSC-ZO (M=1) reaches 83.0 on SNLI vs 74.2 for MeZO; M=4 reaches 76.9 on MNLI and 93.5 on TREC vs MeZO's 67.9 and 83.2.
• Theory gives O~(d^{p/(2(p-1))} eps^{-(3p-2)/(p-1)}) noisy function evaluations with high probability; at p=2 this is O~(d eps^{-4}).
• In a controlled heavy-tailed quadratic (d=100, p=1.5, M=256), scalar clipping reaches the target gradient norm while final-vector clipping plateaus above it.

Surprising findings

• Vector clipping after aggregation preserves gradient direction and gives essentially the same cosine alignment as the raw estimator, so it does not fix the directional error.

Limitations

• Requires sample-wise smoothness and shared randomness across the two function evaluations.
• Theoretical clipping threshold depends on unknown problem constants; experiments use grid search over tau.
• Dimension dependence d remains a bottleneck in high-dimensional problems; experiments limited to RoBERTa-large and a toy quadratic.

Experimental setup

Datasets: SNLI MNLI TREC

Benchmarks: SNLI MNLI TREC

Metrics: test accuracy gradient norm cosine similarity with true gradient

Baselines: MeZO vector clipping after aggregation raw ZO estimator

Builds on: MeZO gradient clipping spherical smoothing vector Bernstein inequality

Closest papers by meaning

• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.92)
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.91)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.91)
• Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.90)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.90)
• Generalization Bounds for Heavy-Tailed SDEs through the Fractional Fokker-Planck Equation (ICML 2024 · similarity 0.89)