{"ID":2840710,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.13592","arxiv_id":"2511.13592","title":"Power Homotopy for Zeroth-Order Non-Convex Optimizations","abstract":"We introduce GS-PowerHP, a novel zeroth-order method for non-convex optimization problems of the form $\\max_{x \\in \\mathbb{R}^d} f(x)$. Our approach leverages two key components: a power-transformed Gaussian-smoothed surrogate $F_{N,σ}(μ) = \\mathbb{E}_{x\\sim\\mathcal{N}(μ,σ^2 I_d)}[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 \\varepsilon^{-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.","short_abstract":"We introduce GS-PowerHP, a novel zeroth-order method for non-convex optimization problems of the form $\\max_{x \\in \\mathbb{R}^d} f(x)$. Our approach leverages two key components: a power-transformed Gaussian-smoothed surrogate $F_{N,σ}(μ) = \\mathbb{E}_{x\\sim\\mathcal{N}(μ,σ^2 I_d)}[e^{N f(x)}]$ whose stationary points c...","url_abs":"https://arxiv.org/abs/2511.13592","url_pdf":"https://arxiv.org/pdf/2511.13592v1","authors":"[\"Chen Xu\"]","published":"2025-11-17T16:54:30Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\"]","methods":"[]","has_code":false}