Hom-PGD$^+$: Fast Reparameterized Optimization over Non-convex Ball-Homeomorphic Set

Abstract

We study optimization over non-convex constraint sets that are homeomorphic to a ball, encompassing important problem classes such as star-shaped sets that frequently arise in machine learning and engineering applications. We propose **Hom-PGD$^+$**, a learning-based and projection-efficient first-order method that efficiently solves such problems without requiring expensive projection or optimization oracles. Our approach leverages an invertible neural network (INN) to learn the homeomorphism between the non-convex constraint set and a unit ball, transforming the original problem into an equivalent ball-constrained optimization where projections admit efficient solutions. We establish that Hom-PGD$^+$ achieves an $\mathcal{O}(\epsilon^{-2})$ convergence rate to an ($\epsilon + \mathcal{O}(\sqrt{\epsilon_{\text{inn}}})$)-approximate stationary solution, where $\epsilon_{\text{inn}}$ denotes the homeomorphism learning error. This rate significantly improves upon existing methods for optimization over non-convex sets, while maintaining a per-iteration complexity of only $\mathcal{O}(W)$ for $W$ INN parameters. Extensive experiments, including QCQP, chance-constrained power-system optimization, and non-uniform adversarial attacks, demonstrate that Hom-PGD$^+$ achieves competitive solution quality while delivering speedups of up to one order of magnitude.