From the simplex to the sphere: Faster constrained optimization using the Hadamard parametrization.
Published in submitted , 2021
Joint with Qiuwei Li and Wotao Yin.
We show how to convert the problem of minimizing a convex function over the standard probability simplex to that of minimizing a nonconvex function over the unit sphere. We prove the landscape of this nonconvex problem is benign, i.e. every stationary point is either a strict saddle or a global minimizer. We exploit the Riemannian manifold structure of the sphere to propose several new algorithms for this problem. When used in conjunction with line search, our methods achieve a linear rate of convergence for non-degenerate interior points, both in theory and in practice. Extensive numerical experiments compare the performance of our proposed methods to existing methods, highlighting the strengths and weaknesses. We conclude with recommendations for practitioners.