Progressive Power Homotopy for Non-convex Optimization

Chen Xu · 2026

Read Progressive Power Homotopy for Non-convex Optimization by Chen Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15915.txt.

Introduction

Chen Xu proposes a first-order method for hard optimization in a 2026 arXiv paper. The problem class is nonconvex optimization. The objective averages a function over data drawn from a distribution. Such problems sit under most machine learning training. Nonconvex landscapes have many traps: local minima and saddle points. First-order methods use only gradients, so they scale well. His method is Progressive Power Homotopy, or Prog-PowerHP.

Homotopy methods solve a hard problem by morphing an easy one into it. The progressive power idea shapes that morphing. A well-built path can steer gradients past traps. Training large models is a costly search through such terrain. Any first-order method with better navigation earns attention from practitioners and theorists alike.

Catalog record

CREATORChen Xu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15915

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Progressive Power Homotopy for Non-convex Optimization Chen Xu Abstract We propose a novel first-order method for nonconvex optimization of the form max 𝒘 ∈ ℝ d ⁡ 𝔼 𝒙 ∼ 𝒟 ​ [ f 𝒘 ​ ( 𝒙 ) ] \max_{\bm{w}\in\mathbb{R}^{d}}\mathbb{E}_{\bm{x}\sim\mathcal{D}}[f_{\bm{w}}(\bm{x})] , termed Progressive Power Homotopy (Prog-PowerHP). The method applies stochastic gradient ascent to a surrogate objective obtained by first performing a power transformation and then Gaussian smoothing, F N , σ ​ ( 𝝁 ) := 𝔼 𝒘 ∼ 𝒩 ⁡ ( 𝝁 , σ 2 ​ I d ) , 𝒙 ∼ 𝒟 ​ [ e N ​ f w ​ ( 𝒙 ) ] F_{N,\sigma}(\bm{\mu}):=\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{\mu},\sigma^{2}I_{d}),\bm{x}\sim\mathcal{D}}[e^{Nf_{w}(\bm{x})}] , while progressively increasing the power parameter N N and decreasing the smoothing scale σ \sigma along the optimization trajectory. We prove that, under mild regularity conditions, Prog-PowerHP converges to a small neighborhood of the global optimum with an iteration complexity scaling nearly as O ⁡ ( d 2 ​ ε − 2 ) O(d^{2}\varepsilon^{-2}) . Empirically, Prog-PowerHP demonstrates clear advantages in phase retrieval when the samples-to-dimension ratio approaches the information-theoretic limit, and in training two-layer neural networks in under-parameterized regimes. These results suggest that Prog-PowerHP is particularly effective for navigating cluttered nonconvex landscapes where standard first-order methods struggle. Keywords : Power-transform. Gaussion Smoothing, Homotopy for Optimizations, Stochastic Gradient Optimization 1 Introduction In this work we aim to solve the following stochastic optimization problem \max_{\bm{w}\in\mathbb{R}^{d}}G(\bm{w}):=\mathbb{E}_{\bm{x}\sim\mathcal{D}}[f_{\bm{w}}(\bm{x})], (1) where \mathcal{D} is a known distribution, f is a known fitness function with accessible derivatives, and the objective G has a unique global maximum point \bm{w}^{*} and possibly multiple local maximums. If \bm{x} represents data and f_{\bm{w}} equals negative of the individual loss function associated with a model with \bm{w} being parameters, then ( 1 ) becomes the loss-minimization problem for model training in machine learning. The most popular methods for the loss-minimization problem are sample-based gradient methods, such as the full-batch gradient descent (GD), stochastic gradient ascent (SGD, [ 5 ] ), and Adaptive Moment Estimation (Adam, [ 17 ] ). While the full-batch GD is guaranteed to approach the stationary points of any sample estimate of G(\bm{w}) under an appropriate learning schedule, it may get stuck near shallow local minima and saddle points. The randomness introduced by mini-batch selection helps SGD mitigate this issue and boosts performances. While the performance of SGD significantly depends on the learning rate schedule, Adam is less susceptible and converges much faster. However, these optimizers are still often trapped near local optimums. Hence, the optimization problem of locating the global optimum still remains open, which is crucial for training under-parameterized models. A well-accepted explanation on SGD’s ability to escape from narrow local minimums is that the mini-batch selection randomness makes SGD actually optimize the smoothed objective \mathbb{E}_{\bm{w}}[G(\bm{w})] of G(\bm{w}) , which eliminates the narrow local minimums [ 18 ] . This relates to the smoothing technique ( [ 27 ] ) used by another type of popular derivative-free non-convex optimization methods—homotopy for optimization (e.g., [ 26 , 14 ] ). Its standard version solves the deterministic problem \min_{\bm{w}}h(\bm{w}) by minimizing the Gaussian-smoothed surrogate H_{\sigma}(\bm{\mu}):=\mathbb{E}_{\bm{\varepsilon}\sim\mathcal{N}(\bm{0},I_{d})}[h(\mu+\sigma\bm{\varepsilon})] . Specifically, it incrementally decreases \sigma in an outer loop, and optimizes the surrogate in the inner loop under the current \sigma value, taking the solution found in the previous inner loop as the initial candidate for the current inner loop. Homotopy works because the smoothing technique removes sharp local minimums and the decreasing- \sigma mechanism drags the global optimum of the surrogate towards that of the original objective h(\bm{w}) under certain conditions ( [ 14 ] ). Traditional homotopy methods are often hindered by the inefficiency of their double-loop structure and a notorious sensitivity to the \sigma -decay schedule, which is notoriously difficult to tune. To address these challenges, recent research has pivoted toward more time-efficient single-loop mechanisms and strategies to minimize the displacement of the optimum caused by the smoothing process. For instance, the Single-Loop Gaussian Homotopy (SLGH) algorithm [ 16 ] introduces an automated \sigma -decay mechanism. GS-PowerOpt [ 40 ] utilizes a power transformation prior to Gaussian smoothing to effectively reduce the distance between the pre- and post-smoothed optima, while GS-PowerHP [ 42 ] integrates both the power transformation and a \sigma -decaying schedule. Despite these advancements, significant gaps remain for solving ( 1 ): SLGH lacks guarantees beyond convergence to a standard local optimum, while GS-PowerOpt and GS-PowerHP are restricted to zeroth-order, deterministic settings. In this paper, we introduce Progressive Power Homotopy (Prog-PowerHP), a novel smoothing-based framework designed to solve the stochastic optimization problem defined in ( 1 ). It offers several critical advantages over existing optimization frameworks. Compared with the standard first-order methods of SGD and Adam and the homotopy method of SLGH, which are frequently susceptible to local optima, our method provides a rigorous theoretical pathway to approximating the global optimum under mild conditions (see Corollary 3 ). By utilizing a single-loop structure, it bypasses the excessive computational overhead and complex sub-problem convergence requirements of traditional double-loop homotopy. Compared with GS-PowerOpt and GS-PowerHP, our algorithm is designed for the stochastic optimization problem and adopts a gradually increasing power for better performance. A key innovation of our approach is the progressive power mechanism, which dynamically increases the power transformation as the smoothing parameter diminishes, effectively refining the search space and prioritizing deeper basins of attraction as the landscape’s fine-grained features emerge. Contribution. The primary contributions of this work are three-fold. To the best of our knowledge, this is the first work to combine homotopy continuation with a progressive power-transformation of the objective for stochastic first-order optimization. Second, we establish the theoretical foundations of this approach by providing a comprehensive convergence analysis for Prog-PowerHP in the stochastic setting. Third, through extensive empirical evaluation on two-layer ReLU networks and phase retrieval, we demonstrate the algorithm’s superior landscape navigation capabilities. Our results show that in under-parameterized and limited-sample regimes—where standard optimizers consistently settle into higher-loss spurious minima—Prog-PowerHP achieves significantly higher approximation efficiency by locating deeper, more optimal local basins. Related Work. There are existing studies that also exponentially transform the loss. For example, in tilted empirical risk minimization, this technique is used to serve multiple purposes, such as to decrease the influence of sample outliers and to improve model generalizations ( [ 20 , 1 ] ). In the field of safe reinforcement learning, this technique is used to emphasize the worst-case scenarios ( [ 8 , 9 , 10 ] ). The main difference between these works and ours is, they treat the transformed objective as a risk-sensitive criterion, intentionally redefining optimality to emphasize tail performance, robustness, or safety. In contrast, our work uses a Gaussian-smoothed power-transformed objective purely as an optimization surrogate, designed to preserve the maximizer of the original fitness while improving concentration and optimization geometry. Our method is also fundamentally distinct from existing homotopy-based approaches. Unlike gradient-based standard homotopy methods [ 14 ] and SLGH [ 16 ] , our approach employs a power-transformation mechanism. Moreover, in contrast to GS-PowerOpt [ 40 ] , GS-PowerHP [ 41 ] , and the path-learning homotopy method [ 21 ] —all of which are developed for deterministic optimization—our framework is tailored to stochastic first-order optimization, where gradient noise and limited sample

Read the complete text