Weakly Quasar-Convex Optimization

This paper introduces the class of weakly quasar-convex functions, a notion that simultaneously generalizes weak convexity (and hence convexity) and quasar-convexity. We establish the theoretical foundation for this new class by developing its basic calculus, deriving characterizations, and systematically investigating its closure and structural properties. Building on these tools, we analyze the proximal point algorithm for minimizing a weakly quasar-convex function under local quadratic growth, proving Q-linear convergence of the iterates and R-linear convergence of the function values to a global minimizer, with iteration complexity $O(\ln(\varepsilon^{-1}))$; we also give a fully computable, minimizer-free stopping rule via the proximal residual with matching complexity. Finally, we construct a weakly quasar-convex function, satisfying all our standing assumptions, that is neither weakly convex, quasi-convex, star quasi-convex, nor quasar-convex for any modulus, showing that our convergence theory applies to instances outside every prior framework in the literature.

Article

Download

View PDF