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

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.

Many real-world optimization problems require finding the best solution within complex, irregularly shaped regions—for example, ensuring power systems operate within safe limits or testing AI robustness. Traditional methods struggle because they repeatedly need to "project" candidate solutions back onto the allowed region, which becomes prohibitively slow for complex shapes. We introduce Hom-PGD$^+$, a method that trains a neural network to learn a smooth transformation between the complex constraint region and a simple ball. This allows us to solve the original difficult problem by working with the simpler ball-shaped region, where projections are trivial, then transforming solutions back. Our method achieves strong theoretical guarantees while running up to ten times faster than existing approaches.