Convexity Certificates for Symbolic Tensor Expressions

Paul Gerhardt Rump, Niklas Merk, Julien Klaus, Maurice Wenig, Joachim GiesenIJCAI 2024 · OpenReview

Abstract

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.

Introduction

In optimization, convexity is the "gold standard." If a function is convex, any local minimum found is guaranteed to be the global minimum. While many common functions are known to be convex, proving this for new, complex machine learning objectives is often a manual, error-prone chore for researchers.

Existing tools like Disciplined Convex Programming (DCP) automate this by combining "atomic" convex building blocks. However, if a function is not constructed from these specific atoms, the tool fails. A more recent approach, the "symbolic Hessian" method, proves convexity by symbolically calculating the function's second-order derivative (the Hessian) and verifying it is Positive Semidefinite (PSD). Until now, these symbolic tools were limited to scalar or vector inputs. In modern machine learning, objectives often involve matrices or higher-order tensors. Flattening these into vectors destroys the mathematical structure—such as symmetry or block-diagonality—that makes a symbolic proof possible. This research bridges that gap by treating tensors as first-class citizens.

Methodology

The framework introduces a formal tensor language based on an extended version of einsum (Einstein summation) notation, which can describe almost any tensor operation through index manipulation.

The symbolic certification pipeline: from input function to convexity certificate via DAG generation, differentiation, and label propagation.

The process follows a structured pipeline:

  1. Symbolic Differentiation: The system parses a function into a Directed Acyclic Graph (DAG). It then applies automatic symbolic differentiation to derive the Hessian. For a matrix input, this Hessian is a fourth-order tensor.
  2. Simplification and Denesting: Symbolic derivatives often create complex expressions. The system implements rules to "denest" these, collapsing nested operations into single larger ones to prevent non-PSD intermediate steps from blocking the proof.
  3. Label Propagation: This is the core logic engine. The system starts at the "leaves" of the math tree (the inputs) and propagates property labels—such as PSD, Symmetric, or Diagonal—up toward the root. If the root node (the Hessian) can be labeled PSD, the function is certified convex.

Key Results

The resulting tool, "Tenvexity," demonstrates significant power and efficiency across a variety of common machine learning objectives.

Performance and convexity certification results for various complex tensor expressions.
  • Efficiency: Most complex certificates, including Tucker decomposition and log-sum-exp, are generated in 1 to 16 milliseconds.
  • Expressivity: The method is strictly more powerful than vector-based approaches. It can certify functions like trace(ABAB) for symmetric PSD matrices, which standard tools like CVX cannot handle without manually defined atoms.
  • Domain-Specific Convexity: The tool handles functions that are convex only on specific domains (e.g., log(det(A)) for symmetric PSD matrices) by allowing users to annotate input properties which are then propagated through the DAG.

Conclusion

By preserving the tensorial nature of inputs rather than flattening them, this approach simplifies symbolic proofs and works for any dimension. While the system is conservative—failure to certify does not imply non-convexity—it significantly expands the set of automatically verifiable convex functions. Future work may involve automating the transformation of tensorial problems into formats compatible with older solvers and further refining deduction rules.

Summary updated

Abstract

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.
BibTeX
@inproceedings{rump2024convexity,
  author = {Paul Gerhardt Rump and Niklas Merk and Julien Klaus and Maurice Wenig and Joachim Giesen},
  title = {{Convexity Certificates for Symbolic Tensor Expressions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=WTo8vZq5rP},
}
Figure