Power Homotopy for Zeroth-Order Non-Convex Optimizations

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.