Power Homotopy for Zeroth-Order Non-Convex Optimizations

arXiv:2511.13592v2 Announce Type: replace-cross Abstract: The existing method of GS-PowerOpt solves the non-convex optimization problem of the form max_{oldsymbol{x} in R^d} f(oldsymbol{x}) through maximizing a Gaussian-smoothed surrogate F_{N,sigma}(oldsymbol{mu}) = E_{oldsymbol{x}simN(oldsymbol{mu},sigma^2 I_d)}[e^{N f(oldsymbol{x})}]. We analyze the role of the smoothing radius sigma>0 and identify a limitation of the fixed-sigma design used in GS-PowerOpt. Specifically, sigma induces an inherent exploration--refinement tradeoff: a larger sigma improves global exploration and finite-time surrogate optimization, but may distort the location of the surrogate maximizer; in contrast, a smaller sigma 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 sigma 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 sigma to improve local refinement near the maximizer. We provide theoretical results showing that this decaying schedule improves the exploration--refinement tradeoff of fixed-sigma power smoothing. Empirically, GS-PowerHP consistently outperforms the fixed-sigma 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.

Source: arXiv cs.LG | 2026-07-16