Power Homotopy for Zeroth-Order Non-Convex Optimizations

Abstract

The existing method of GS-PowerOpt solves the non-convex optimization problem of the form ${\max }_{\mathbf{x}\in {\mathbb{R}}^d}f(\mathbf{x})$ through maximizing a Gaussian-smoothed surrogate $F_{N,\ddot{I}ƒ}(\hat{\mathbf{I}}¼)={\mathbb{E}}_{\mathbf{x}\sim \mathcal{N}(\hat{\mathbf{I}}¼,\ddot{I}{ƒ}^2{I}_d)}[e^{Nf(\mathbf{x})}]$. We analyze the role of the smoothing radius $\ddot{I}ƒ>0$ and identify a limitation of the fixed-$\ddot{I}ƒ$ design used in GS-PowerOpt. Specifically, $\ddot{I}ƒ$ induces an inherent exploration--refinement tradeoff: a larger $\ddot{I}ƒ$ improves global exploration and finite-time surrogate optimization, but may distort the location of the surrogate maximizer; in contrast, a smaller $\ddot{I}ƒ$ 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 $\ddot{I}ƒ$ 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 $\ddot{I}ƒ$ to improve local refinement near the maximizer. We provide theoretical results showing that this decaying schedule improves the exploration--refinement tradeoff of fixed-$\ddot{I}ƒ$ power smoothing. Empirically, GS-PowerHP consistently outperforms the fixed-$\ddot{I}ƒ$ 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.

Topics & keywords