TL;DR
This paper expands the reach of zeroth-order (derivative-free) optimization to a much broader class of functions called Subdifferentially Polynomially Bounded (SPB) functions. By proving a new "descent lemma" that accounts for polynomial growth, the authors develop algorithms with adaptive stepsizes that can minimize complex, non-smooth, and non-Lipschitz functions—like those found in neural networks—using only function evaluations.
What Problem Does This Paper Address?
In many real-world scenarios—from tuning hyperparameters to configuring physical experiments—we need to optimize a "black-box" function where we can't calculate a gradient. We only have a zeroth-order oracle: we plug in an input $x$ and get a value $f(x)$.
Existing algorithms for this task usually rely on a massive assumption: Global Lipschitz continuity. Essentially, they assume the function never gets "too steep" anywhere in the entire domain. However, many modern applications, such as training neural networks or robust optimization, involve functions that grow much faster or are non-smooth.
The authors address this gap by introducing and analyzing SPB functions. These functions are locally well-behaved but can become increasingly steep as you move further from the origin, with their "steepness" (subdifferential) bounded by a polynomial of the input's magnitude.
Methods
The researchers utilize Gaussian Smoothing (GS), a technique that transforms a potentially jagged, non-differentiable function into a smooth one by convolving it with a Gaussian kernel.
The key technical contributions include:
- The SPB Descent Lemma: The authors prove a novel version of the classic "descent lemma." In standard optimization, this lemma uses a constant (the Lipschitz constant) to bound how much a function changes. Here, they replace that constant with a polynomial function, allowing for much more aggressive growth.
- Adaptive Stepsize Strategy: Because SPB functions can get steeper as the iterates $x^k$ grow, a fixed stepsize might cause the algorithm to diverge. The authors propose a stepsize that scales inversely with a polynomial of the current iterate's norm ($\|x^k\|$).
- Goldstein Stationarity Link: For non-smooth functions, "gradient = 0" isn't a sufficient condition for a minimum. The authors establish a rigorous mathematical link between the gradient of the smoothed function and the Goldstein subdifferential, providing a way to measure how close the algorithm is to a "stationary point" in non-smooth landscapes.
Datasets
Not discussed in the paper. This is a theoretical optimization paper focused on mathematical proofs, convergence analysis, and algorithmic design. It does not include empirical evaluations on specific datasets or benchmarks.
Key Insights and Ideas
- Broadening the Horizon: The SPB class is remarkably inclusive. it covers all Lipschitz functions, gradient-Lipschitz functions, Hessian-Lipschitz functions, and even specific non-smooth structures common in deep learning (like ReLU-based neural networks).
- Smoothing is Robust: The paper proves that the property of being "polynomially bounded" is preserved under Gaussian smoothing. If your original function is SPB, its smoothed version is also SPB, and so are its derivatives.
- Relative vs. Absolute Measures: Because the iterates can theoretically be unbounded, the authors introduce "relative" optimality measures (rescaled by the polynomial growth) to provide meaningful convergence rates where standard measures might fail.
- Quantifying Non-Smoothness: The connection between the GS gradient and Goldstein stationarity is a "bridge" that allows zeroth-order methods (which "see" a smooth version of the world) to solve problems that are fundamentally "pointy" or non-smooth.
Key Results
- Convex Case: For convex SPB functions, the algorithm achieves a convergence rate of $O(T^{-1/2})$ for a relative optimality measure.
- Non-Convex Case: In the unconstrained non-convex setting, the authors establish iteration complexity bounds for reaching an $\epsilon$-stationary point of the smoothed function.
- Stationarity Complexity: They provide explicit bounds on the number of iterations required to find a $(\delta, \epsilon)$-approximate Goldstein stationary point, which is a significant milestone for derivative-free optimization of non-smooth functions.
Limitations and Future Work
- Parameter Knowledge: The adaptive stepsize requires knowing (or estimating) the degree of the polynomial growth ($m$) and the growth constants ($R_1, R_2$). In a true black-box scenario, these might not be known upfront.
- Theoretical Focus: While the math is rigorous, the paper does not explore the practical performance of these adaptive stepsizes compared to heuristics like "backtracking" or "line search" in zeroth-order settings.
- Stochastic Noise: The current analysis focuses on a deterministic zeroth-order oracle. Extending this to cases where function evaluations are noisy (stochastic zeroth-order optimization) for the full SPB class remains an open challenge.
Summary updated