Convexity Certificates for Symbolic Tensor Expressions

Convexity Certificates for Symbolic Tensor Expressions

Paul G. Rump, Niklas Merk, Julien Klaus, Maurice Wenig, Joachim Giesen

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 1953-1960. https://doi.org/10.24963/ijcai.2024/216

Knowing that a function is convex ensures that any local minimum is also a global minimum. Here, we implement an approach to certify the convexity of twice-differentiable functions by certifying that their second-order derivative is positive semidefinite. Both the computation of the second-order derivative and the certification of positive semidefiniteness are done symbolically. Previous implementations of this approach assume that the function to be minimized takes scalar or vector inputs, meaning that the second-order derivative is at most a matrix. However, the input of many machine learning problems is naturally given in the form of matrices or higher order tensors, in which case the second-order derivative becomes a tensor of at least fourth order. The familiar linear algebra notations and known rules for determining whether a matrix is positive semidefinite are not sufficient to deal with these higher order expressions. Here, we present a formal language for tensor expressions that allows us to generalize semidefiniteness to higher-order tensors and thereby certify the convexity of a broader set of functions.
Keywords:
Constraint Satisfaction and Optimization: CSO: Solvers and tools
Machine Learning: ML: Optimization
Machine Learning: ML: Symbolic methods