🤖 machine learning

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper proposes a stochastic zeroth-order algorithm with a clipped two-point gradient estimator to solve nonconvex nonsmooth optimization problems under heavy-tailed noise, achieving optimal dimension-dependent complexity and matching the best-known accuracy rates for Goldstein stationary points.

Original authors: Zhuanghua Liu, Luo Luo

Published 2026-05-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhuanghua Liu, Luo Luo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy, and jagged mountain range. This is a common problem in machine learning: finding the best settings for a model to make accurate predictions.

In a perfect world, you would have a map and a compass (gradients) telling you exactly which way is down. But in the real world, especially with complex AI models, you often can't see the slope. You can only poke the ground at two spots and ask, "Is it higher or lower here?" This is called Zeroth-Order Optimization.

Now, imagine the weather in this mountain range is terrible. Instead of a gentle breeze, you are hit by sudden, massive, unpredictable storms (called Heavy-Tailed Noise). These storms are so wild that standard weather forecasts (which assume storms are usually small) fail completely. If you try to navigate using a compass that gets blown off course by these giant storms, you'll never find the bottom.

Here is how the paper "Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise" solves this problem, explained simply:

1. The Problem: The "Stormy" Mountain

The authors are dealing with a specific type of mountain:

Nonconvex: The terrain is full of hills, valleys, and plateaus, not just a smooth bowl.
Nonsmooth: The ground is jagged and rocky, not smooth like glass.
Heavy-Tailed Noise: The "wind" (data noise) that pushes your measurements is unpredictable. Sometimes it's a gentle breeze, but occasionally, it's a hurricane that throws your measurement wildly off. Most previous methods assumed the wind was always gentle, which isn't true in real life.

2. The Solution: The "Clipped" Compass (ZOCOON)

The authors propose a new algorithm called ZOCOON (Zeroth-Order Clipped Online-to-Nonconvex). Think of it as a smart navigation strategy with two main tricks:

Trick A: The "Two-Point Poke"
Since you can't see the slope, the algorithm picks two points very close together and pokes the ground at both. By comparing the height difference, it guesses the direction of the slope. This is the standard way to navigate without a map.

Trick B: The "Storm Shield" (Clipping)
This is the paper's big innovation. When the algorithm calculates the slope using the two pokes, the "hurricane" noise might make the result look like the ground is sloping at a 90-degree angle (which is impossible).

Old methods: Would trust this crazy number and take a giant, disastrous step in the wrong direction.
ZOCOON: Uses a "clipper." It says, "If the slope looks too steep (like a hurricane), I'm going to cap it at a reasonable maximum." It ignores the extreme outliers caused by the noise. It's like wearing a helmet that stops a falling rock from knocking you over; you still feel the impact, but you don't get knocked unconscious.

3. The Goal: Finding the "Good Enough" Spot

Because the mountain is so jagged, finding the perfect bottom is mathematically impossible to prove you've reached. So, the authors aim for a "Goldstein Stationary Point."

Analogy: Instead of finding the single lowest point in the entire world, they look for a spot where, if you look at the ground within a small circle around you, the average slope is flat. It's a "good enough" resting spot where you aren't likely to slide down further.

4. The Results: Why It Works

The paper proves mathematically that ZOCOON works even when the "storms" are huge.

Efficiency: It finds this "good enough" spot just as fast as the best methods do when the weather is calm (no heavy storms).
Robustness: Unlike other methods that might get lost in the chaos of heavy noise, ZOCOON keeps moving steadily because it ignores the crazy outliers.
Real-world Test: The authors tested this on real data sets (like classifying emails or documents). They added artificial "stormy" noise to the data. ZOCOON found the solution faster and more steadily than previous methods, which got confused by the noise.

Summary

Think of this paper as inventing a new way to hike in a hurricane. Previous hikers tried to walk normally and got blown away. This new method (ZOCOON) says, "When the wind blows too hard, we ignore the wind's crazy direction and just keep walking in the most logical direction we can." It allows us to solve complex machine learning problems even when the data is messy and full of extreme outliers.

Technical Summary: Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

Problem Formulation
This paper addresses the unconstrained stochastic optimization problem:
$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$
where the objective function $f$ is nonconvex and nonsmooth, but Lipschitz continuous. The setting is zeroth-order, meaning the algorithm only has access to noisy function evaluations $F(x; \xi)$ rather than gradients.

A critical departure from prior work is the noise assumption. While many existing analyses rely on the bounded variance assumption (second-order moment), this paper operates under a heavy-tailed noise assumption. Specifically, the Lipschitz constant $L(\xi)$ of the stochastic component function satisfies a bounded $p$ -th moment condition:
$\mathbb{E}[L(\xi)^p] \leq L^p$
where $p \in (1, 2]$ . When $p < 2$ , the variance may be unbounded, characterizing heavy-tailed distributions (e.g., Lévy $\alpha$ -stable) commonly observed in real-world machine learning applications like training deep neural networks and reinforcement learning.

Methodology: ZOCOON Algorithm
The authors propose the Zeroth-Order Clipped Online-to-Nonconvex (ZOCOON) algorithm. The method integrates three core components:

Online-to-Nonconvex Conversion Framework: Building on the framework established by Cutkosky et al. [9] and extended by Kornowski and Shamir [25], the algorithm converts an online learning problem into a nonconvex optimization solver. This involves running a sequence of updates over rounds to find a stationary point.
Two-Point Stochastic Gradient Estimator: Since gradients are unavailable, the algorithm uses a zeroth-order estimator based on the smoothed surrogate function $f_{\delta'}(x)$ . For a point $x$ and a random direction $w$ on the unit sphere, the estimator is:
$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$
This provides an unbiased estimate of the gradient of the smoothed function.
Gradient Clipping: To mitigate the impact of heavy-tailed noise, the algorithm incorporates a clipping operator on the gradient estimator. The update step uses $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$ , where $\tau$ is a threshold parameter. This prevents large, noisy gradients from destabilizing the optimization process.

The algorithm operates in epochs with restarts, outputting a uniformly random point from the set of averaged iterates to ensure convergence guarantees.

Key Contributions and Theoretical Results
The paper establishes theoretical guarantees for finding a $(\delta, \epsilon)$ -Goldstein stationary point, a refined notion of approximate stationarity for nonsmooth functions defined via the Goldstein $\delta$ -subdifferential.

Convergence Complexity: The ZOCOON algorithm achieves a $(\delta, \epsilon)$ -Goldstein stationary point with a stochastic zeroth-order oracle complexity of:
$O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$
This result holds both in expectation and with high probability.
Dimension Dependence: The dependence on the dimension $d$ matches the best-known results for stochastic zeroth-order optimization in the convex nonsmooth setting.
Accuracy Dependence: The dependence on accuracy parameters $\delta$ and $\epsilon$ is consistent with the best-known stochastic first-order algorithms for nonconvex nonsmooth problems under heavy-tailed noise.
Smooth Extension: The results naturally extend to the smooth setting. By setting $\delta = \epsilon/H$ (where $H$ is the smoothness constant), the method achieves an $\epsilon$ -stationary point with complexity matching the optimal stochastic first-order methods for smooth nonconvex optimization.

Experimental Validation
Numerical experiments were conducted on nonconvex penalized SVM problems using real-world datasets (a9a, covtype, w8a) with artificially added heavy-tailed noise (Pareto distribution).

Baselines: ZOCOON was compared against GFM [26], GFM+ [5], and ZOO2N [25].
Findings: ZOCOON and ZOO2N converged significantly faster than GFM and GFM+. ZOCOON demonstrated more stable performance than ZOO2N across most datasets, validating the effectiveness of the clipping mechanism in handling heavy-tailed noise.

Significance and Claims
The paper claims to fill a critical gap in the literature: while heavy-tailed noise is prevalent in practice, existing zeroth-order methods for nonconvex nonsmooth optimization were limited to bounded variance assumptions or convex settings.

First of its Kind: ZOCOON is presented as the first efficient stochastic zeroth-order algorithm for nonconvex nonsmooth optimization under heavy-tailed noise.
Optimality: The authors note that the dependence on $L$ , $\delta$ , and $\epsilon$ matches a recently established lower bound for this problem class, suggesting the method is near-optimal regarding accuracy parameters.
Robustness: The work demonstrates that gradient clipping, a technique common in first-order methods, can be successfully adapted to zeroth-order frameworks to handle unbounded variance without sacrificing dimension-dependent complexity.

The paper concludes by acknowledging open questions, specifically whether the dimension dependence is optimal and whether the framework can be extended to constrained optimization problems.