{'fraction_non_alphanumeric': 0.03887661722940991, 'fraction_numerical': 0.008299147996213316, 'mean_word_length': 4.468679896462468, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convexity Certificates from Hessians

The Hessian of a differentiable convex function is positive semidefinite. Therefore, checking the Hessian of a given function is a natural approach to certify convexity. However, implementing this approach is not straightforward since it requires a representation of the Hessian that allows its analysis. Here, we implement this approach for a class of functions that is rich enough to support classical machine learning. For this class of functions, it was recently shown how to compute computational graphs of their Hessians. We show how to check these graphs for positive semidefiniteness. We compare our implementation of the Hessian approach with the well-established disciplined convex programming (DCP) approach and prove that the Hessian approach is at least as powerful as the DCP approach for differentiable functions. Furthermore, we show for a state-of-the-art implementation of the DCP approach that, for differentiable functions, the Hessian approach is actually more powerful. That is, it can certify the convexity of a larger class of differentiable functions.

problem class utilizing automatic (symbolic) differentiation. Thus, solvers can also be generated for non-convex problems. However, such solvers usually do not converge to a global optimum but only provide a local optimum. Therefore, to assess the quality of a solution, a convexity certificate calculated from the specification is also of interest to GENO.
For compiling a specification into a solver, GENO employs a matrix calculus [Laue et al., 2018] for computing symbolic derivatives of matrix and tensor expressions. The matrix calculus can also be used to compute second order derivatives, that is, Hessians. A test for convexity can thus be reduced to a test of positive semidefiniteness of the Hessian, which certifies the convexity of a function. This is the approach that we take here. We design an algorithm for certifying positive semidefiniteness of matrix expressions. For certifying convexity, the algorithm is then applied to symbolic Hessians that are computed by a matrix calculus.
We start with a formally defined language of mathematical functions (see the supplementary material for its grammar). For expressions from this language, we generate computational graphs of their Hessians using a matrix calculus and check these graphs for positive semidefinitness. The computational graphs are small since they only contain symbols for parameter vectors and matrices, and not their numerical values. Our algorithm for certifying positive semidefiniteness runs in time linear in the size of the computational graph. It propagates positivity information of subexpressions to the root of the computational graph by using simple rules for positive semidefinite matrices. Non-trivial subexpressions can be certified as convex by matching them to known expression templates. Surprisingly, there is a single template that is powerful enough to certify the convexity of a large class of matrix expressions. Using this template, we show that our Hessian approach covers all differentiable functions with vector input that can be certified as convex by the DCP implementation within CVX. Furthermore, we provide classes of differentiable convex functions that can be certified by our approach, but cannot be certified as convex by CVX.

Related work
In general, certifying that a function is convex is known to be strongly NP-hard [Ahmadi et al., 2013], even when the function is a multivariate polynomial of degree three and the domain is a bounded box [Ahmadi and Hall, 2020]. However, since certifying convexity is such an important issue in optimization and machine learning, there are many convexity proofs for specific problems, see Klibanov [1997] for an example. Unfortunately, these proofs are problem-and often even instancespecific and cannot be generalized. But, there are also generic approaches that we discuss in the following. Most generic approaches are either rule-based or analyze the Hessian.
Rule-based approaches We have already mentioned the disciplined convex programming (DCP) approach taken by CVX Boyd, 2008, 2014;Agrawal et al., 2017], which has been ported from Matlab to other programming languages, like CVXPY [Diamond and Boyd, 2016] for Python, CVX for Julia [Udell et al., 2014], or CVX for R [Fu et al., 2020]. Any convex function that cannot be derived from the atomic convex functions by the DCP rule set cannot be certified as convex by the DCP approach. However, functions that have been certified as convex by other means can be added manually as atomic functions. Hence, over the course of the last few years, many convex functions have been added as atoms, for instance quadratic functions x ⊤ Ax for positive semidefinite matrices A, or the negative entropy function x ⊤ log(x). In our approach, we certify the convexity of these functions automatically. Tawarmalani and Sahinidis [2005] describe a polyhedral branch-and-cut approach for finding a global optimum for non-convex optimization problems. They use rule-based convexity tests for decomposing a non-convex problem into a set of convex problems. Posypkin and Khamisov [2021] use interval arithmetic and a set of rules for determining the convexity of univariate functions, similar to the CVX approach. However, unlike CVX, their approach can only be applied to simple univariate functions. Similarly, Singh and Lucet [2021] analyze univariate piecewise polynomial functions.  summarize and generalize the convexity detection methods described by Schichl and Neumaier [2005] and . Their approach, traversing a function's computational graph and applying composition rules when convexity holds, is again similar to the DCP approach. Camino et al. [2003] use the software package NCAlgebra by Helton and de Oliveira [2000] for computing the Hessian of a function that is defined over matrices. Based on a symbolic Cholesky decomposition, they check the non-negativity of the eigenvalues of the Hessian. If all eigenvalues are non-negative, the Hessian is positive semidefinite and thus implies convexity. However, this approach only works for very simple functions, i.e., only polynomials of matrices and their inverses. In these cases, the Hessian is always a quadratic function for which the symbolic Cholesky decomposition can be computed. This approach works for the function x ⊤ Ax, but not for the negative entropy function x ⊤ log(x).

Hessian based approaches
Using automatic differentiation for computing Hessians and then certifying convexity was proposed by Nenov et al. [2004]. However, the proposal does not include specific algorithms and has not been implemented yet.
Other approaches An approach that is neither rule-based nor based on analyzing the Hessian was proposed by Carmon et al. [2017], who established a relationship between the number of iterations needed for minimizing a function and its convexity. In general, if a function is convex, convergence rates can be estimated. Hence, if during the minimization process these convergence rates are violated, then one has found a certificate that this function is not convex. However, if convergence rates are satisfied during the optimization process no statement about convexity can be made. In general, if one starts close to a local minimum, then the function looks locally like a convex function to the minimization process, while globally, it does not need to be convex. Instead of looking at the convergence rates, one could modify this approach by computing the Hessian in each iteration and checking its smallest eigenvalue. If it is negative, then non-convexity can be certified. Again, convexity cannot be asserted by such an approach.

The DCP and the Hessian approach
This section gives a brief high-level overview of the DCP approach and our implementation of the Hessian approach. Details are provided in the following sections. The two approaches are algorithmically similar. Both use some a priori information that is propagated through expression DAGs (directed acyclic graphs) for the function or its Hessian, respectively. They differ in the form of the a priori information and in the rules that are used for propagating the information. Noteworthy, in contrast to the Hessian approach, the DCP approach also works for non-differentiable functions.
DCP approach. The DCP approach comprises a rule set and a set of atomic expressions, short atoms, that are already known to be convex. It applies to expressions that are recursively build from functions, constants, and variables. The expressions can be organized in an expression DAG whose inner nodes are function symbols and whose leaves are constants and variables as shown in Figure 1. The set of function symbols includes the atoms. Function symbols can be labeled as convex, concave,   affine, and monotonously increasing (decreasing). Constants and variables can be labeled as nonnegative or non-positive. The DCP rules are used to propagate label information from the leaves to the root of the expression DAG, which represents the whole expression. Therefore, if it is possible to propagate the label convex to the root, then the expression is proven to be convex.
Hessian approach. The Hessian of a twice differentiable function f : R n → R is a quadratic form H(f ), that is, for v ∈ R n the Hessian evaluates as v ⊤ H(f )v. The function f is convex if H(f ) is positive semidefinite. Here, we assume that we can compute H(f ) in vectorized form, that is, in standard matrix language that does not make use of explicit indices. Our implementation works for a formally defined language for representing multivariate functions (see the supplemental material) that allows to compute their Hessians in normalized vectorized form. By representing the Hessian by an expression DAG, the Hessian approach for computing convexity certificates propagates positivity and type information from the leaves of the DAG to the root by using a rule set that we introduce in Sections 4 and 5.

Rule sets
In this section we show that for a twice differentiable function the DCP rule set is implied by a set of positivity rules for the Hessian of the function. However, this is not enough to show that the DCP approach is implied by a positivity calculus, since this also requires that the atoms used in the DCP approach can be certified as convex by the positivity calculus. We discuss CVX's DCP atoms in Section 6.
The DCP rule set by Grant et al. [2006b] comprises the following rules for functions on R n : 2. f (g 1 , g 2 , . . . , g m ) is convex if f is convex and for each g i one of the following conditions holds: (a) f is increasing in argument i and g i is convex. ( is concave if f is concave and for each g i one of the following conditions holds: (a) f is increasing in argument i and g i is concave.
(b) f is decreasing in argument i and g i is convex.
(c) g i is affine or constant.
4. f (g 1 , g 2 , . . . , g m ) is affine if f is affine and each function g i is affine.
Note that products of functions cannot be treated within the DCP framework, that is, expressions of the form f 1 · f 2 . Even when f 1 and f 2 are known to be affine, nothing can be said about the product.
Here, we only discuss certifying convexity, since concavity of a function f can be certified by the convexity of −f . Hence, in the following, we do not consider the DCP Rule 3. We show that the DCP Rules 1 and 2 for twice differentiable functions are implied by positivity rules for their Hessians. DCP Rule 4 that asserts that h is affine, which is a stronger property, can be addressed by adding the rules 0 · M = M · 0 = 0 and M + 0 = M to the positivity rules. More specifically, we have the following proposition.
Proposition 1. For twice differentiable functions, the DCP rule set is implied by the following positivity rules for (n × n)-matrices: 3. If M 1 0 and M 2 0, then M 1 + M 2 0.

If M 0 and A is an arbitrary
Proof. We exploit that a twice differentiable function h is convex if its Hessian H(h) is positive semidefinite (psd) and that it is concave if its Hessian H(h) is negative semidefinite (nsd). For DCP Rule 1, we observe that Hence, by Positivity Rules 1 and 2, , and then by Positivity Rule 3, which certifies the convexity of m i=1 α i f i . For the remaining DCP Rules 2 and 4, let h be recursively defined as h = f (g 1 , g 2 , . . . , g m ). The gradient of h at x can be written as and its Hessian is given as For DCP Rule 2a, we first argue separately that both sums for H(h) are psd. The first sum can be written as GH(f )G ⊤ , where the columns of G are the gradients ∇(g i ).
Since the convexity of f implies that H(f ) 0 it follows from Positivity Rule 4 that the first sum for H(h) is psd. For the second sum, we use that f is increasing in its i-th argument, which implies that ∇(f ) i ≥ 0, and that the g i are convex, which implies that H(g i ) 0. Hence, by Positivity Rule 1 all terms in the second sum are psd, which together with Positivity Rule 3 implies that also the second sum for H(h) is psd. Thus, we can conclude from Positivity Rule 3 that H(h) 0, which certifies the convexity of h. The claims for DCP Rules 2b, 2c and 4 follow similarly.

Implementing the Hessian approach
For implementing the Hessian approach, we need to compute a representation of the Hessian that is amenable to analysis. The matrix calculus by Laue et al. [2018Laue et al. [ , 2020 computes derivatives of vectorized expressions again in vectorized form without explicit indices. Here, we employ computational graphs for the expressions of second derivatives. That is, Hessians, computed by the matrix calculus. We normalize these computational graphs into expression DAGs (directed acyclic graphs) that contain each subexpression exactly once, see In the following, we demonstrate our implementation of the Hessian approach using illustrative examples before we summarize the algorithm that underlies our implementation of the Hessian approach.

A generic example
As a first generic example we discuss the ordinary least squares regression problem where X ∈ R m×n is a data matrix, y ∈ R m is a label vector, and w ∈ R n is the parameter vector that needs to be optimized. Using matrix calculus, the Hessian for the objective function of this problem can be computed in vectorized form as 2 · X ⊤ X. An expression DAG for the Hessian is shown in Figure 2. Our implementation of the Hessian approach computes positivity information for each node of the DAG in a bottom-up strategy from the leaves to the root. There are positivity rules that apply to the two multiplication nodes of the DAG, namely first Rule 4 for the expression X ⊤ X and then Rule 1 for the expression 2 · X ⊤ X, where it is already known that X ⊤ X is psd.
Let us compare the Hessian approach to the DCP approach for certifying the convexity of the ordinary least squares problem. The DAG for the ordinary least squares objective function is shown in Figure 3. The DCP approach traverses this DAG in a bottom-up fashion. Starting from the leaves, the matrix-vector product Xw is affine by definition and thus the corresponding multiplication node is labeled affine, similarly the subtraction node for Xw − y is labeled affine, since the *

Propagating information about subexpressions
A second instructive example is the univariate function f (x) = x log(x) that neither the Hessian nor the DCP approach can certify as convex without information beyond the rules. However, the information required by the Hessian approach is easier to provide on the language level. The Hessian of f (x) is the expression 1/x, which, in general, can be positive, negative, or even undefined at 0. However, we already know that x ∈ (0, ∞), because the domain of the logarithm is the positive reals. This information is enough to decide the positivity of the Hessian. Hence, we can exploit positivity information about the elementary functions that are supported by our formal language. Here are some additional rules and exp(x), arccos(x), log(1 + x), x ≥ 0.
Let us compare this again to the DCP approach that directly works on the expression x log(x). Here, the problem is at the root node that multiplies the affine function x with the concave function log(x).
Since, in general, nothing can be said about the product of an affine function and a concave function, it is not possible to certify the convexity of x log(x) from the DCP rules. Indeed, CVX adds the entropy function −x ⊤ log(x) as an atom that has been certified as concave by other means like analyzing its second order derivative.
Another instructive example is the univariate function log(1 + exp(x)) whose Hessian is The Hessian can be certified positive definite by propagating the known positivity information for the exponential function through the normalized expression DAG for the Hessian, as can be seen in Figure 4. CVX adds this function as an atom named logistic, probably because the derivative of this function is the logistic function 1/(1 + exp(−x)). Note that the naming problem does not exist in the Hessian approach.
A fourth example is the power function x p . The Hessian of the power function is p(p−1)x p−2 . Since p(p−1) ≥ 0 for p ≥ 1 and p ≤ 0 we can certify the convexity of the power function from its Hessian Furthermore, we can certify the convexity of −x p from its Hessian if (0 < p < 1) ∧ (x ≥ 0). That is, the Hessian approach can certify the convexity of power functions from constraints on x and information about the power parameter p, whereas the DCP approach needs atoms for the different cases. In general, the Hessian approach can exploit derived and user provided information about variables, parameters, and, more generally, subexpressions. However, the next example shows that this is not enough.

A psd expression template
Our fifth example is the CVX atom log_sum_exp that computes log sum(exp(x)) . Its Hessian is given, again in vectorized form, as Both the first and the second term are readily certified as positive, but their difference is not, because in general, nothing can be said about the difference of two psd matrices. However, we will show that the Hessian matches the psd expression template from Proposition 2, see also the Figure to the right. The template can be used to certify many expressions as convex. Whenever a subexpression of a larger expression DAG matches the template, we can label the subexpression DAG as psd and propagate this information within the larger DAG. Indeed, adding this template to our rule set is powerful enough to cover all differentiable CVX atoms with vector input, and thus by Proposition 1 all differentiable functions with vector input, that can be certified as convex by the DCP implementation within CVX. Proposition 2. For y ∈ R n and z ∈ R n ≥0 , all matrices of the following form are psd: diag(y ⊙ z ⊙ y) − (y ⊙ z)(y ⊙ z) ⊤ /sum(z).

Proof.
We have to show that v ⊤ Av ≥ 0 for all v ∈ R n for the template matrix A. It turns out that v ⊤ Av is the variance of some random variable. We compute that where var(V y ) is the variance of the random variable V y that takes the value y i v i with probability z i /sum(z) for i ∈ [n].
Note that the Hessian of the CVX atom log_sum_exp matches the template if z is instantiated by exp(x)/sum(exp(x)) and y by vector(1).

Summary of the Hessian approach
Algorithm 1 that implements the Hessian approach combines the individual steps mentioned above. Its input is the Hessian of a given expression computed as a normalized expression DAG. In the algorithm, we encode positivity and negativity information by intervals as follows: for scalar expressions, the interval encodes (a superset of) the domain of the expression, for vector expressions, the interval encodes (a superset of) the domains of all vector entries, and for matrix expression, any interval in [0, ∞) encodes psd information and any interval in (−∞, 0] encodes nsd information. The main work in Algorithm 1 is delegated to the subroutine DETERMINEINTERVAL that is implemented in Algorithm 2. The subroutine recursively processes the normalized expression sub-DAG rooted at some vertex v from the leaves to the node v. The intervals I v at leaf nodes always either encode known or user-provided positivity information about variables or parameters or are set to (−∞, ∞). At any node, the information about the intervals associated with its children is combined, using the psd rule set and standard interval arithmetic, into an interval for the node by the subroutine COMBINEINTERVALS. Exceptions from this rule are multiplication nodes at which Rule 4 might apply and subtraction nodes, where the psd template from Proposition 2 might apply. Therefore, we check at each node if a simple template for Rule 4 or our psd template applies. Matching the templates are simple instances of tree matching problems that are implemented in the subroutine MATCHTEMPLATE. Here, we encode a match with the templates by the interval [0, ∞).

Algorithm 1 Certify convexity of a Hessian
Since the psd expression template and the rules from Proposition 1 only require checking substructures of constant depth (up to depth five for the psd template), the running time of the algorithm is linear in the size of the expression DAG of the Hessian.

Atoms of CVX's implementation of the DCP approach
In addition to the rule set, the DCP approach requires functions (atoms) that are already known to be convex. Here, we show that all twice differentiable atoms with vector input that can be certified as convex by the DCP implementation within CVX can also be certified by our implementation of the Hessian approach. In the next section we provide examples of convex functions that are not certified as convex by CVX, but can be certified by our Hessian approach.
Among CVX's DCP atoms are standard convex univariate functions like exp, neg_log, neg_sqrt, and square that we discuss in the supplemental material. Multivariate DCP atoms in CVX are return COMBINEINTERVALS(I l , I r ) 11: end if 12: end procedure sum(x), that is, the function n i=1 x i , and quadratic forms quad_form(x, A), that is, x ⊤ Ax for a psd matrix A. Both functions are readily certified as convex by their Hessians. A more interesting atom is inv_prod(x) that computes n i=1 x i −1 . In vectorized notation this function can be written as f (x) = 1/exp sum(log(x)) and its vectorized Hessian is given as where vector (1) is the all ones vector, ⊙ and ⊘ denote elementwise multiplication and divison, respectively. It follows from the positivity of f (x) and Positivity Rules 1 and 4 that the first term in the sum for the Hessian is psd, and from the positivity of f (x) and the positivity of the entries of x ⊙ x it follows that also the second term is psd. Hence, the Hessian is psd by Positivity Rule 3, which certifies the convexity of f (x).
CVX also contains four atoms (combinations of the operators sum, log, and exp) that superficially look similar to inv_prod but cannot be certified directly from the positivity calculus. However, for these problems, the Hessian is the difference of two psd matrices that can be matched to the template expression from Proposition 2. We have already discussed the CVX atom log_sum_exp. The three remaining atoms are the harmonic mean, p-norms, and the geometric mean.
Negative harmonic mean The negative harmonic mean neg_harmonic_mean(x) for x ∈ R n + is defined as −n/ n i=1 x −1 i . It can be written in vectorized notation as −1/sum vector(1) ⊘ x) =: f (x).
Its Hessian, which computes to is matched by the psd expression template if both y and z are instantiated by vector(1) ⊘ x. Note that 1/sum(z) in the template becomes −f (x) = 1/sum vector(1) ⊘ x) in the instantiation.
p-norms The p-norm x p = n i=1 |x i | p 1/p of x ∈ R n for p > 1 reads in vectorized notation as sum exp(p · log(s(x) ⊙ x)) 1/p = sum(f (x)) 1/p , where s(x) is the sign vector of x, that is, we have s(x) ⊙ s(x) = s(x) ⊘ s(x) = vector(1). The Hessian of the p-norm can be computed as The Hessian matches the psd expression template if y is instantiated by vector(1) ⊘ x and z by f (x). It also follows that the p-norm is concave for 0 < p < 1, since the negated p-norm is convex for these values of p.
Negative geometric mean The negative geometric mean neg_geo_mean(x, p) is given as where p ∈ R n + is a parameter vector. It reads in vectorized form as f (x) = −exp(sum(p ⊙ log(x))) 1/sum(p) ≤ 0.

Its Hessian
matches the psd expression template if y is instantiated by p and z is instantiated by vector(1) ⊘ x.

Beyond CVX's atoms
There are two main classes of functions that cannot be treated by DCP. The first are products of two non-constant expressions such as x exp(x) for x ≥ 0. The second are compositions that are not following DCP's Rules 2, 3 or 4 such as neg_entr(cosh(x)) = cosh(x) log(cosh(x)), where neg_entr(x) = x log(x) is convex but not increasing, and thus composing it with the convex function cosh(x), DCP Rule 2a does not apply here. Both examples so far do not need the template expression from Proposition 2 to be certified convex by the Hessian approach. This is different for the multivariate function which can be expressed in vectorized form as sum exp(x) log 1 + sum exp(x) .
Its Hessian is the sum of three matrices log 1 + sum(exp(x)) + sum(exp(x)) (1 + sum(exp(x))) 2 · diag(exp(x)) + 2 · exp(x)exp(x) ⊤ 1 + sum(exp(x)) where the last matrix matches the template expression from Proposition 2, up to a positive prefactor if y is instantiated by vector(1) and z by exp(x). The first two matrices can be certified as psd directly from the positivity rules.

Conclusions
We have presented the first generic implementation of the Hessian approach for certifying convexity and shown that it complements the well-established disciplined convex programming approach. Neither approach is better than the other. Both have complementary strengths and weaknesses. The DCP approach also works for non-differentiable functions but needs a new symbol for every new atom, whereas our implementation of the Hessian approach works on a formal language that is close to natural problem formulations in textbooks and rich enough to express many classical machine learning problems, including problems not found in standard libraries like scikit-learn [Pedregosa et al., 2011]. Furthermore, new DCP atoms also need to be certified at some point, and the Hessian approach can be used to certify some of these new atoms.

B Algorithmic details of the Hessian approach
Our implementation of the Hessian approach works on vectorized and normalized expression DAGs (directed acyclic graphs) for Hessians that contain every subexpression exactly once. Our formal input language is vectorized, which means expressions are expressed without indices but not normalized. Using a matrix calculus implementation, we can compute vectorized Hessians that are again not normalized. Therefore, we need to normalize such expressions.
We illustrate the normalization on the expression x*A'*x + exp(x*A'*X), which represents the function xA ⊤ x + exp(xA ⊤ x). First, we parse the expression into a standard expression tree. The expression tree for our example is shown in Figure 6.
Using a common subexpression elimination [Aho et al.: Compilers: Principles, Techniques, and Tools, 2013] we identify the common subexpressions x, x ⊤ , A, Ax, x ⊤ Ax that appear more than once. Rearranging these subexpressions in the expression tree results in the normalized DAG that is shown in Figure 7. Every node in the normalized DAG represents a unique subexpression.
The normalized DAG then serves as the data structure on which the Hessian approach for certifying convexity operates. The Hessian approach traverses the DAG in post-order and attempts to label the nodes (subexpressions) of the DAG . This way, positivity information is propagated from the leaves of the DAG to the root.

C CVX atoms
Due to space constraints, we could not discuss all differentiable CVX atoms in the main paper. Here, we show that also the remaining atoms can be certified as convex by our implementation of the Hessian approach. We start with standard univariate functions before we discuss the remaining multivariate functions. : Normalized expression DAG after common subexpression elimination of the subexpressions x*A'*x + exp(x*A'*X). The leaves of the DAG are the nodes labeled by the variable x and the parameter matrix A, respectively. The root of the tree is the right most node (labeled by +) and represents the whole expression.
Univariate functions. CVX's univariate DCP atoms are standard convex univariate functions like exp, neg_log, neg_sqrt, and square. For certifying these atoms as convex, the Hessian approach makes use of the information that exp(x) > 0, that log(x) implies x > 0, and that √ x implies x ≥ 0. This works analogously for the atom log1p(x) = log(1 + x). We have already discussed power functions and the negative entropy function neg_entr in the examples (see main paper). The atom inv_pos that encodes the function 1/x for x > 0 can be certified as convex from its Hessian by using the constraint x > 0.
Remaining multivariate functions. The only remaining twice differentiable multivariate functions are sum(x) = n i=1 x i and sum_squares(x) = n i=1 x 2 i , which are straightforwardly verified by the Hessian approach.
Exceptions. Similar, and related to the negative entropy function, are the relative entropy (rel_entropy) x log(x/y) and the Kullback-Leibler divergence (kl_div) x log(x/y) − x + y for y > 0. Together with the atom quad_over_lin(x, y) = n i=1 x 2 i /y for y > 0, these are the only twice differentiable atoms not tractable with our approach, as they cannot be expressed with a single vector input.

D More examples of convex functions not covered by CVX
In the last section we saw that the expression template derived in the main paper suffices to certify all twice differentiable atoms with vector input of CVX. Here, we collect a few more examples of convex functions that can be certified by the Hessian approach using the expression template but are not feasible for DCP.
The following examples need a restriction of the domain by the user.
Here are some univariate functions which can be classified by the Hessian approach once the domain is restricted: (1) f (x) = x a exp(x) for 0 < a < 1 and x ≥ 1 or a < 0 and x > 0. Note that for a ≥ 1, x a exp(x) can be expressed as 1 a a (xexp(x/a)) a with the atom xexp(x) = x · exp(x).

D.3 Generalized psd expression template
To support even more convex functions, we can generalize the expression template as shown in Figure 8.
Proof. We can use the template expression from Proposition 2 (main text) to show that the above expression is also psd. To do so, we split the first summand of diag(y ⊙ z ⊙ y) − (y ⊙ z)(y ⊙ z) ⊤ /sum(z) , and note that the resulting first two summands are diagonal matrices with non-negative entries, hence psd, and the last summand was shown to be psd in Proposition 2 (main text). In addition, the template allows a scaling and non-negative shifting of the sum operation. Those additional nodes are considered in the template matching algorithm. Starting with the / node, the algorithm checks if there is a * node. If true, it checks for a child a which is greater or equal to 1 and a + child. If there is no * node, the algorithm checks if there is a + node, if true, it checks for the sum and a non-negative child b and continues as usual. Note that the scaling and shifting are optional. If there is neither a * nor a + node, the algorithm nevertheless finds a sum node if the template matches.