# Power Homotopy for Zeroth-Order Non-Convex Optimizations

arXiv: https://arxiv.org/abs/2511.13592 · HTML: https://mlsanity.com/paper/2511.13592/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 17 Nov 2025.

## Builds on (most cited first, 23 of 23)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Square Attack: a query-efficient black-box adversarial attack via random search](https://mlsanity.com/paper/1912.00049/) (2019)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [RobustBench: a standardized adversarial robustness benchmark](https://mlsanity.com/paper/2010.09670/) (2020)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Do Adversarially Robust ImageNet Models Transfer Better?](https://mlsanity.com/paper/2007.08489/) (2020)
- [Simple Black-box Adversarial Attacks](https://mlsanity.com/paper/1905.07121/) (2019)
- [Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors](https://mlsanity.com/paper/1807.07978/) (2018)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [Single Loop Gaussian Homotopy Method for Non-convex Optimization](https://mlsanity.com/paper/2203.05717/) (2022)
- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Refining Adaptive Zeroth-Order Optimization at Ease](https://mlsanity.com/paper/2502.01014/) (2025)
- [Universal Convexification via Risk-Aversion](https://mlsanity.com/paper/1406.0554/) (2014)
- [On the Convergence of the Iterative Linear Exponential Quadratic Gaussian Algorithm to Stationary Points](https://mlsanity.com/paper/1910.08221/) (2019)
- [Generalization and Robustness of the Tilted Empirical Risk](https://mlsanity.com/paper/2409.19431/) (2024)
- [Global Optimization with A Power-Transformed Objective and Gaussian Smoothing](https://mlsanity.com/paper/2412.05204/) (2024)

## Built on by (most cited first, 1 of 1)

- [Progressive Power Homotopy for Non-convex Optimization](https://mlsanity.com/paper/2601.15915/) (2026)

## Abstract (arXiv)

The existing method of GS-PowerOpt solves the non-convex optimization problem of the form max_boldsymbolx ∈ ℝd f(boldsymbolx) through maximizing a Gaussian-smoothed surrogate FN,σ(boldsymbolμ) = mathbbE_boldsymbolx~N(boldsymbolμ,σ2 Id)[e^N f(boldsymbolx)]. We analyze the role of the smoothing radius σ>0 and identify a limitation of the fixed-σ design used in GS-PowerOpt. Specifically, σ induces an inherent exploration--refinement tradeoff: a larger σ improves global exploration and finite-time surrogate optimization, but may distort the location of the surrogate maximizer; in contrast, a smaller σ better preserves local structure but can weaken gradient signals away from high-value regions. To address this limitation, we propose GS-PowerHP, a power-smoothed homotopy method with an incrementally decaying σ schedule. The proposed mechanism uses larger smoothing radii in early iterations to maintain informative gradient signals when the iterate is far from high-value regions, and gradually decreases σ to improve local refinement near the maximizer. We provide theoretical results showing that this decaying schedule improves the exploration--refinement tradeoff of fixed-σ power smoothing. Empirically, GS-PowerHP consistently outperforms the fixed-σ baseline and exhibits robust performance across different optimization tasks, including adversarial attacks on ImageNet (d=150,528), where it substantially improves over other smoothing-based zeroth-order methods.