University of Birmingham

Abstract

Matrix-valued optimization tasks arise in many machine learning applications. Often, exploiting non-Euclidean structure can yield algorithms that are computationally superior to standard nonlinear programming methods. In this talk, we consider the problem of optimizing a function on a Riemannian manifold subject to convex constraints. Several classical problems, such as barycenter problems, optimistic likelihoods, and operator scaling, can be formalized in this way. We focus on instances that exhibit additional structure, including geodesic convexity and objectives that are “difference of convex” functions. Leveraging the algebraic properties of geodesically convex functions, we introduce a disciplined programming approach for certifying geodesic convexity, which gives rise to global optimality guarantees for first-order methods. We then discuss a class of efficient, CCCP-style algorithms for unconstraint, geodesically convex “difference of convex” optimization and present global, non-asymptotic convergence results. Finally, we introduce a class of regularizers for constraint problems that induce this desirable structure, significantly expanding the range of problems to which the CCCP approach applies.