Power Homotopy for Zeroth-Order Non-Convex Optimizations

2025/11/17 by Xu, Chen
#65K05 #68T07 #68W40 #90C30 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2511.13592

Abstract

We introduce GS-PowerHP, a novel zeroth-order method for non-convex optimization problems of the form max_{x ∈ ℝ^d} f(x). Our approach leverages two key components: a power-transformed Gaussian-smoothed surrogate F_N,σ(μ) = 𝔼_{x\simN(μ,σ² Id)}[e^{N f(x)}] whose stationary points cluster near the global maximizer x^* of f for sufficiently large N, and an incrementally decaying σ for enhanced data efficiency. Under mild assumptions, we prove convergence in expectation to a small neighborhood of x^* with the iteration complexity of O(d² ε^-2). Empirical results show our approach consistently ranks among the top three across a suite of competing algorithms. Its robustness is underscored by the final experiment on a substantially high-dimensional problem (d=150,528), where it achieved first place on least-likely targeted black-box attacks against images from ImageNet, surpassing all competing methods.

Citations

• Refining Adaptive Zeroth-Order Optimization at Ease
• Global Optimization with A Power-Transformed Objective and Gaussian Smoothing
• Generalization and Robustness of the Tilted Empirical Risk
• Continuation Path Learning for Homotopy Optimization
• Generalizing Gaussian Smoothing for Random Search
• Single Loop Gaussian Homotopy Method for Non-convex Optimization
• On Tilted Losses in Machine Learning: Theory and Applications
• RobustBench: a standardized adversarial robustness benchmark
• Do Adversarially Robust ImageNet Models Transfer Better?
• Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Square Attack: a query-efficient black-box adversarial attack via random search
• On the Convergence of the Iterative Linear Exponential Quadratic Gaussian Algorithm to Stationary Points
• ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box\n Optimization
• Simple Black-box Adversarial Attacks
• Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors
• Towards Evaluating the Robustness of Neural Networks
• The CMA Evolution Strategy: A Tutorial
• Deep Residual Learning for Image Recognition
• On Graduated Optimization for Stochastic Non-Convex Problems
• Universal Convexification via Risk-Aversion
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Gradient-based learning applied to document recognition

Related

• Global Optimization with A Power-Transformed Objective and Gaussian Smoothing
• Single Loop Gaussian Homotopy Method for Non-convex Optimization
• Convergence Analysis of Homotopy-SGD for non-convex optimization
• Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS
• Recent Theoretical Advances in Non-Convex Optimization