Power Homotopy for Zeroth-Order Non-Convex Optimizations

Technical Summary: Power Homotopy for Zeroth-Order Non-Convex Optimizations

Problem Statement
The paper addresses the challenge of zeroth-order (ZO) optimization for non-convex problems, where the objective function $f: \mathbb{R}^d \to \mathbb{R}$ must be maximized without access to its gradients. While existing methods like GS-PowerOpt utilize power-transformed Gaussian smoothing to locate global optima, they rely on a fixed smoothing radius $\sigma$. The authors identify a fundamental limitation in this fixed-$\sigma$ design: an inherent trade-off between global exploration and local refinement. A large $\sigma$ facilitates global exploration and accelerates surrogate optimization but distorts the location of the surrogate maximizer; conversely, a small $\sigma$ preserves local geometry but yields weak gradient signals when the iterate is far from high-value regions.

Methodology: GS-PowerHP
To resolve this trade-off, the authors propose GS-PowerHP (Power-Transformed Gaussian Homotopy), a single-loop zeroth-order algorithm that integrates power transformation with a principled decaying smoothing radius schedule.

1. Objective Transformation: The method targets the surrogate objective:
   $$F_{N,\sigma}(\mu) := \mathbb{E}_{x \sim \mathcal{N}(\mu, \sigma^2 I_d)}[e^{N f(x)}]$$
   where $N$ is a power parameter and $\sigma$ is the smoothing radius.
2. Decaying Schedule: Unlike GS-PowerOpt, which uses a fixed $\sigma$, GS-PowerHP updates the smoothing radius at each iteration $t$ according to:
   $$\sigma_{t+1} = \sigma_0 \beta^{t+1} + b$$
   where $\beta \in (0, 1)$ is a decay factor and $b > 0$ is a lower bound.
3. Update Rule: The algorithm performs a stochastic gradient ascent step:
   $$\mu_{t+1} = \mu_t + \alpha_t \hat{\nabla} F_{N,\sigma_{t+1}}(\mu_t)$$
   The gradient estimator is computed using $K$ samples drawn from $\mathcal{N}(\mu_t, \sigma_{t+1}^2 I_d)$.
4. Mechanism: The strategy begins with a larger $\sigma$ to maintain informative gradient signals during global exploration (when $\mu_t$ is far from the optimum) and gradually decreases $\sigma$ to improve local refinement as the iterate approaches the maximizer.

Key Contributions

1. Theoretical Insight: The authors provide a formal analysis identifying the exploration-refinement trade-off inherent in the fixed-$\sigma$ mechanism of GS-PowerOpt. They demonstrate that iteration complexity scales inversely with $\sigma^2$ (favoring larger $\sigma$), while the alignment between the surrogate maximizer and the true global maximizer improves as $\sigma \to 0$ (favoring smaller $\sigma$).
2. Algorithmic Innovation: GS-PowerHP is the first zeroth-order method to explicitly combine power transformation with an incremental $\sigma$-decaying mechanism.
3. Convergence Guarantees: The paper establishes theoretical convergence results (Corollaries 1 and 3). It proves that under mild assumptions, GS-PowerHP converges in expectation to an arbitrarily small neighborhood of the global maximizer. The finite-time convergence rate to first-order stationarity is shown to be $O((d^2 \epsilon^{-1} b^{-2})^{\frac{2}{1-2\gamma}})$, validating that the decaying schedule allows for faster initial progress while ensuring local accuracy in the limit.
4. Empirical Superiority: Extensive experiments demonstrate that GS-PowerHP consistently outperforms fixed-$\sigma$ baselines (including GS-PowerOpt) and other smoothing-based ZO methods (such as ZOSGD, ZO-AdaMM, and ZOSLGH) across various tasks.

Experimental Results
The authors evaluated GS-PowerHP on:

• Benchmark Functions: Maximization of Ackley and Rastrigin functions in $d=100$ dimensions. GS-PowerHP achieved the highest fitness values among smoothing-based methods and required fewer iterations to converge compared to GS-PowerOpt.
• Adversarial Attacks (Black-Box): The method was tested on least-likely targeted attacks against classifiers for MNIST, CIFAR-10, and ImageNet.
  • On ImageNet ($d=150,528$), GS-PowerHP achieved a 78% success rate, a substantial improvement over GS-PowerOpt (47%) and ZOSLGHd (67%), while maintaining comparable perturbation sizes and image similarity.
  • On MNIST and CIFAR-10, it achieved 100% success rates with smaller perturbation norms than competing smoothing-based algorithms.
• Ablation Studies: Experiments on synthetic objectives and targeted attacks confirmed that the decaying-$\sigma$ mechanism is the primary driver of performance gains, allowing the algorithm to balance exploration and refinement more effectively than fixed-$\sigma$ variants.

Significance and Claims
The paper claims that GS-PowerHP represents a significant advancement in zeroth-order non-convex optimization by treating the smoothing radius as an adaptive computational resource rather than a static hyperparameter. The authors assert that this approach solves the structural tension between exploration and accuracy found in previous power-smoothing methods.

The significance of the work is highlighted by its robust performance in extremely high-dimensional settings (e.g., ImageNet attacks), where it outperforms existing smoothing-based methods and offers a computationally lighter alternative to covariance-adaptation methods like CMA-ES (which requires maintaining a full covariance matrix). The authors conclude that the combination of power transformation and homotopy-style decay provides both strong theoretical convergence guarantees and superior empirical results for challenging black-box optimization tasks.