Allerton Conference on Communication, Control, and Computing

Abstract

Matrix-valued optimization tasks, including those involving symmetric positive definite (SPD) matrices, arise in a wide range of applications in machine learning, data science and statistics. Classically, such problems are solved via constrained Euclidean optimization, where the domain is viewed as a Euclidean space and the structure of the matrices (e.g., positive definiteness) enters as constraints. More recently, geometric approaches that leverage parametrizations of the problem as unconstrained tasks on the corresponding matrix manifold have been proposed. While they exhibit algorithmic benefits in many settings, they cannot directly handle additional constraints, such of constrained Riemannian optimization methods, notably, Riemannian Frank-Wolfe and Projected Gradient Descent. However, both algorithms require potentially expensive subroutines that can introduce computational bottlenecks in practise. To mitigate these shortcomings, we propose a structured regularization approach based on symmetric gauge functions. On the example of computing optimistic likelihoods, we show that the regularizer preserves crucial structure in the objective, including geodesic convexity. This allows for solving the regularized problem with a fast unconstrained method with global optimality certificate. We demonstrate the effectiveness of our approach in numerical experiments and through theoretical analysis.