Convexity Certificates from Hessians
Authors: Julien Klaus
Niklas Merk
Konstantin Wiedom
Sören Laue
Joachim Giesen
Venue: NeurIPS 2022 Accept (2022)
Keywords: disciplined convex programming
matrix calculus
classical machine learning

Abstract: 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 the Hessian approach is  actually more powerful, that is, it can certify the convexity of a larger class of differentiable functions.

Convexity Certificates from Hessians
Julien Klaus Friedrich Schiller University Jena julien. klaus@uni-jen sesusuni-jjeaacco
Niklas Merk Friedrich Schiller University Jena niklas mww.muni-jeeeeeee
Konstantin Wiedom Friedrich Schiller University Jena konstantin wi eeeeemmnnniiiii careelunnjjea..cmm de
Sören Laue Technical University Kaiserslautern Data Assessment Solutions GmbH laue@cs. uni-kl.de
Joachim Giesen Friedrich Schiller University Jena joachim. joachim.giesenuun giesen@uninnn -innaa..i..aaaaaeaa de
Abstract
The Hessian of differentiable convex function is positive semidefinite. Therefore, checking the Hessian of a given function is natural approach to certify convexity. However, implementing this approach 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 compu- tational graphs of their Hessians. We show how to check these graphs for positive semidefiniteness. We compare 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 the DCP approach for differ- entiable 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 larger class differentiable functions.
Introduction
Convex optimization forms the backbone of classical machine learning. Formulating machine learning problems convex optimization problems is attractive because these problems be solved globally and efficiently. Several optimization frameworks consisting of modeling language and solver exist and are used in machine learning. Two examples of such frameworks are CVX [Grant and Boyd 2014) and GENO [Laue et al. 2019), which take different approaches.
CVX takes formal specification of optimization problem and transforms it into normal form, such as a convex quadratic program (QP) or semidefinite program (SDP). The transformation is only possible if the specified problem is convex. Therefore, convexity test is performed first in CVX. The test is based on a calculus for convex functions called disciplined convex programming (DCP) by Grant al. [2006a], which takes advantage, for example, of the fact that the sum of convex functions convex function are convex again. The convexity calculus requires a set
and the positive scaling of functions, called atoms, whose convexity has to be certified by other means.
GENO also takes the formal specification of an optimization problem but does not transform into standard form. Instead, it uses the specification to generate a solver for the specified problem or
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

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 local optimum. Therefore, to assess the quality of solution, 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 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 matrix calculus.
We start with 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 matrix calculus and check these graphs for positive semidefinitness. The compu- tational 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 single template that is powerful enough to certify the convexity of 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.
2 Related work
In general, certifying that function is convex is known to be strongly NP-hard [Ahmadi 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 example. Unfortunately, these proofs are problem- and often even instance-specific 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 (Grant and Boyd 2008 2014 Agrawal el al. 2017], which has been ported from Matlab to other programming languages, like CVXPY DDiamond and Boyd| 2016]] for Python, CVX for Julia [Udell et al.) 2014]. or CVX for R (Fu 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 T Ax for positive semidefinite matrices A, or the negative entropy function x. (og(z). In our approach, we certify the convexity of these functions automatically.
Tawarmalani and Sahinidis optimum for non-conver optimization problems. They use rule-based convexity tests for decomposing a mononocome coon-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. Fourer er al. [2010) summarize and generalize the convexity detection methods described by [Schichl and
20055 describe polyhedral branch-and-cut approach for finding a global
Neumaier (005) Fourrr and Orban [2110). Their approach, traversing a function's 's computational
graph and applying composition rules when convexity holds, is again similar to the DCP approach.
Hessian based approaches Camino el al. 2003 use the software package NCAlgebra by Helton
and de Oliveira 22000] for computing the Hessian of function that is defined over matrices. Based

---

on symbolic Cholesky decomposition, they check the non-nee 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 funcctin x log(z).
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 been implemented yet.
Other approaches An approach that is neither rule-based nor based on analyzing the Hessian was proposed by Carmon er al. [017]] who established a relationship between the number of iterations needed for minimizing function and its convexity. In general, if 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, one starts close to local minimum, then the function looks locally like 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 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 brief high-level overview of the DCP approach and our implementation of the Hessian approach. Details are provided 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 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 -on-differentiable functions.
DCP approach. The DCP approach comprises rule set and 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 The set of function symbols includes the atoms. Function symbols can be labeled as convex.
On
gi
Figure 1: Abstract expression DAG for the function f. The leaves x; are either variables or constants, all other nodes g, and are abstract function symbols. The root of this sub-DAG is labeled by the function symbol
concave, affine, and monotonously increasing (decreasing). Constants and variables can be labeled as non-negative or non 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 convex.
Hessian approach. The Hessian of twice differentiable function f: R. - IR is a quadratic form H()), that is, for R the Hessian evaluates as (J)v.. The function f is convex if HJ) is positive semidefinite. Here, we assume that we can compute H()) in vectorized form, that is, in standard matrix language that does not make use explicit indices. Our implementation works for formally defined language for representing multivariate functions (see the supplemental material)
3

---

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 and
Rule sets
In this section we show that for twice differentiable function the DCP rule set is implied by set of positivity rules for the Hessian of the function. However, this is not enough to show that the DCP approach is implied by positivity calculus, since this also requires that the atoms used in the DCP approach can certified as convex by the positivity calculus. We discuss CVX's DCP atoms in Section O
The DCP rule set by Grant et al. 2006b comprises the following rules for functions on R":
1. E a;fi is convex if either a; 2 0 and f; is convex, or a; S 0 and f is concave, for all E m).
2. (gi (01199....., 92..... 9m) is convex if is convex and for each & one of the following conditions holds:
(a) is increasing in argument i and 9i is convex.
(b) decreasing in argument and gi is concave.
(c) 9: is affine or constant.
3. f (gg 92..... 9m) is concave if is concave and for each gi one of the following conditions holds:
(a) is increasing in argument i and 9i is concave.
(b) f is decreasing in argument and is convex.
(c) is affine or constant.
4. fgg. 92...., is affine if is affine and each function gi is affine.
Note that products of functions cannot be treated within the DCP framework, that is, expressions of the form fi f2. Even when f1 and fa are known to be affine, nothing can be said about the product.
Here, we only discuss certifying convexity, since concavity of function f can be certified by the convexity of ff. Hence, in the following, we do not consider the DCP Rule We show that the DCP Rules 1 and 2 for twice differentiable functions are implied by positivity rules for their Hessians. DCP Rule that asserts that affine, which a stronger property, can be addressed by adding 0 and M + 0 M to the positivity rules. More specifically, we have the
the rules 0 M = M following proposition.
Proposition 1. For twice differentiable functions, the DCP rule set implied by the following positivity rules for (n x n))matrices:
1. Ifc 0 and M 2 then M
2. Ifc S 0 and M 3 O, then M : 0.
3. If M, > 0 and M2 = 0, then M, + M2 2 0.
4. If M ž 0 and A is an arbitrary (m x n)) matrix, then AMAT > 0.
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 we observe that H H(f) ž if f. is convex, and H(f.) = 0 if f. concave. Hence, by Positivity Rules and 2,
Haasf) a ((H))
for all E [m]] and then by Positivity Rule 3,
m
m
11
anfi = Σ
agHl((A) 0, i=1
1=1

---

which certifies the convexity of Ei= a:fi-
For the remaining DCP Rules 2 and let h be recursively defined as h (gi, 92: ... -mm) The
gradient of at i: can be written as
v(h) 92 ................................ V(gi)
and its Hessian is given
H(h) H2) (m)) V()))(()) Σ 02.... - H(g)).
1==1
For DCP Rule Za we first argue separately that both sums for Hh) are psd. The first sum can be written as GHG, where the columns of G the gradients V(g.). Since the convexity of implies that H() ž 0 it follows from Positivity Rule 4 that the first sum for (h) is psd. For the second sum, we use that iis increasing in its i-th argument, which implies that V(f); Z O, and that the are convex, which implies that (g.) 2 O. Hence. by Positivity Rule I all terms in the second sum are psd, which together with Positivity Rule implies that also the second sum for H (h) is psd. Thus, we can conclude from Positivity Rule that H (h) E O, which certifies the convexity of h. The claims for DCP Rules 2b and follow similarly.
Implementing the Hessian approach
For implementing the Hessian approach, need to compute representation of the Hessian that amenable to analysis. The matrix calculus by Laue ef al. (2018) 2020] computes derivatives of vectorized expressions again in vectorized form without explicit indices. Here, employ computational graphs for the expressions 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 Figures and for examples of normalized expression DAGs.
In the following, we demonstrate our implementation of the Hessian approach using illustrative examples before summarize the algorithm that underlies our implementation of the Hessian approach.
5.1 A generic example
As first generic example we discuss the ordinary least squares regression problem
min [Xw vll min (Xw v) w y),
where X e Rmxnn is data matrix, E R is label vector, and w R" 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 shown in Figure 2 Our implementation of the Hessian approach computes positivity information for each node
label: psd
Rule 1
constant, 22 0
2
Evaluation
label: psd
Rule 4
Figure 2: Illustration of the Hessian approach on the normalized expression DAG for the Hessian of the ordinary least squares loss function.
5

---

of the DAG in a bottom-up strategy from the leaves to the root. There are positivity rules that apply the two multiplication nodes of the DAG, namely first Rule for the expression X and then Rule for the expression 2 X X, where it is already known that X X is psd.
Let compare the Hessian approach 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 X w is affine by definition and thus the corresponding multiplication node is labeled affine, similarly the subtraction node for X y is labeled affine, since the addition/subbraction of affine functions is affine again, and the transposition node in (.X w y) is labeled affine, since the transposition preserves this property. However, general nothing can be said about the product of
affine functions, which means that the standard DCP rules are not enough to label the root of the
DAG. Typically, the problem is dealt with by adding new atomic function to the DCP atoms that squares its input.
label:
label: affine
Eva luation
label: affine
label: affine
X
w
Variable
Figure 3: Illustration of the DCP approach the normalized expression DAG for the ordinary least squares loss function.
5.2 Propagating information about subexpressions
second instructive example the univariate function f(x) = x log(z) that neither the Hessian nor the DCP approach can certify convex without information beyond the rules. However, the information required by the Hessian approach is casier to provide on the language level. The Hessian of fx:) is the expression 1/2, which, in general,
undefined O. However, we already know that x E (0, oo), because the domain of the logarithm is the positive reals. exploit positivity
be positive, negative,
This information is enough decide the positivity of the Hessian. Hence, information about the elementary functions that are supported by our formal language. Here are some additional rules
(0) Vz and exp(x:) ar) log(1 + x)), |||||| 2 0.
log(x)
(0)
Let us compare this again to the DCP approach that directly works on the expression x log(z)) Here, the problem is at the root node that multiplies the affine function z with the concave function log( (z). Since, in general, nothing can be said about the product an affine function and a concave function, it is not possible certify the convexity of log(æ) from the DCP rules. Indeed, CVX adds the entropy function -x" log(z) 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
exp(x)
(1 ('xx)x exp(x)
exp(x)
1 exp(x)
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 atom named logistic, probably because the derivative of

---

this function is the logistic function 1/ + exp(-x)). Note that the naming problem does not exist in the Hessian approach.
fourth example is the power function xº. The Hessian of the power function is p(p 1)=²-2 Since we certify the convexity of the power function from its Hessian
p(p - 1) 2 0 for p 2 1 and if p 2m, n N, or ((p 2 1) V (p 0)) (x 0), or ((p = 1) v (p 2k, k E Z)) (z < 0). Furthermore, we can certify the convexity of -r² from its Hessian if (0 < < 1) A (a: 0). That is, the Hessian approach can certify the convexity of power functions from constraints on a and information about the power parameter p, whereas the DCP approach needs atoms for the different
cases.
E [0, 1]
E [0, 1]
E (0, 00)
exp
E [0,
E [max 11, (x)p())) )0)
Figure 4: Propagating positivity information from the leaves to the root of the normalized expression DAG for the Hessian of the logistic function.
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 enough.
5.3 A psd expression template
Our fifth example is the CVX atom log_sum_ee exp that computes log (o((sumeexp(z)) Its Hessian is given, again in vectorized form,
(ixg((x)(<))) - -xp(a))xp(o))//mmmm (ssmexp(t))))uum((x(xs) /sum(exp(xx)).
Both the first and the second term readily certified as pos- itive, but their difference is not, because in general, nothing can be said about the difference of two psd matrices. How- ever, we will show that the Hessian matches the psd expres- sion template from Proposition see also the Figure to the right. The template can be used to certify many expressions convex. Whenever subexpression of larger expression DAG matches the template, we can label the subexpression DAG psd and propagate this information within the larger DAG. Indeed, adding this template to our rule set is powerful enough cover all differentiable CVX atoms with vector input, and thus by Proposition aall differentiable functions with vector input, that be certified convex by the DCP implementation within CVX.
label: psd
diag
sum
Proposition 2. For y E R and E R all matrices of the following form are psd:
diag(y 2 2 O 2))2(())))
/ /sum(2).
7

---

Proof. We have to show that v' Av 2 0 for all v E IR" for the template matrix A. It turns out that u Au is the variance of some random variable. We compute that
v (diag(y O v) (y O (y o ( /sum(=))u
sum @ v) sum(z (y u))² /sum(z)
sum(2) (smm (( (z/sum(( 2)) (y v) sum((z/sum(2)) o O
sum(2) var(V,) 0,
where var(V,, V2) is the variance of the random variable Vy that takes the value you; with probability 2/ 2/sum(2) for i [m].
Note that the Hessian of the CVX atom sug_sum_ exp matches the template if is instantiated by exp(r)/sum(exp(x)) and y by vector(1).
5.4 Summary of the Hessian approach
Algorithm I that implements the Hessian approach combines the individual steps mentioned above. Its input is the Hessian of given expression computed as 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, oo) encodes psd information and any interval in (-oo, 0] encodes nsd information.
Algorithm Certify convexity of a Hessian
1: + ROOTÖF(DAG)
2: I, +- DETERMINEINTERVAL.CW
3: if 7, S [0. oo) then
4: return true
5: else
6: return false
7:
end if
The main work in Algorithm is delegated to the subroutine DETERMINEINTERVAL that is imple- mented in Algorithm 2 The subroutine recursively processes the normalized expression sub-DAG rooted at some vertex from the leaves to the node The intervals L, at leaf nodes always either encode known or user-provided positivity information about variables or parameters or are set to (-o0, c0). 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 multiplication nodes at which Rule 4 might apply and subtraction nodes, where the psd template from Proposition 2 might apply. Therefore, check at each node if simple template for Rule 4 our psd template applies. Matching the templates are simple instances of tree matching problems that are implemented in the subroutine MATCHTEMMPLATS Here, encode match with the templates by the interval [0, oc).
Since the psd expression template and the rules from Proposition onnl 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 convex by CVX, but can be certified by our Hessian approach.
Among CVX's DCP atoms are standard convex univariate functions like exp, seg_log, neg_ sgrs, and square that we discuss in the supplemental material. Multivariate DCP atoms in CVX are

---

Algorithm 2 Compute the positivity interval for a node v
1: procedure DETERMINEEITERVALL()
2: if v.leaf== true then
3: return I,
4: end if
5: if MATCHTEMMPATEEC)) then
6: return 20)
7: else
8:
4 < DETTERMINENNTEWWAALLLECCCCLUO))
9:
It < DETERMINNENTERALALLAHHCCCUUCO
10: return COMBINEINTERVALSUI.. 4.)
end if
12: end procedure
A), that is, x Ax for psd matrix A. Both functions are readily certified as convex by their Hessians. A more interesting atom is inv (nv-prodxx) that computes (II =²)-² In vectorized notation this function can be written f(x) l/exp(sum(log(x)) and its vectorized Hessian is given
sum( that is, the function E Ti, and quadratic forms
f(x) (vector(1) (vvettor)))) @ x=)T= + diag(vector(f(o)) (x
where vector(1) is the all ones vector, @ and 2 denote elementwise multiplication and divison, respectively. It follows from the positivity of f=) and Positivity Rules 1 and 4 that the first term in the sum for the Hessian is psd, and from the positivity of f(z) and the positivity the entries of x follows that also the second term is psd. Hence, the Hessian is psd by Positivity Rule 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 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_ som_sum_em__ exp. The three remaining atoms are the harmonic mean, p-norms, and the geometric mean.
Negative harmonic mean The negative harmonic neg_ hww.oniccmmamm(? for æ E R is defined as -n 27
It can be written in vectorized notation as
- 11/sum(vector/// Ø x)) f(x).
Its Hessian, which computes
2 f(x)² (diag(vector()) @ (a (roxox)) + f(x) (vector(1) 2 (x (r
is matched by the psd expression template if both and are instantiated by vector(1) Ø Note that 12) in the template becomes -f(x) =1/sum (veetove))or(1) Ø x)) in the instantiation.
p-norms The p-norm ||>|||p-- = (E (2:1)) 1/p
of 1 forp reads in vectorized notation
sum(exp(p- log(s(() O x))) 1/p sum(f()))!/r
where sx) is the sign vector of z, that is, we have s(x) o s(x) = s(x) C s(x) = vector(1). The Hessian of the p-norm can be computed as
(p- 1) (u) (itt
The Hessian matches the psd expression template if is instantiated by vector(1) and by f(x).
also follows that the p-norm concave for 0 < p 1, since the negated p-norm convex for these values of

---

Negative geometric mean
The negative geometric mean neg-geo_mean(2) is given
1/sumip)
II
where RR is parameter vector. It reads in vectorized form
f(z) = eex((summp log(x)))
1/((z)))//summ))) 1/sum(p) I 0.
Its Hessian
f(x) ((0x))v0x) /summ)) /sum(p)² 2 /)/mm())))
matches the psd expression template if y is instantiated by p and instantiated by vector(1) @
7 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 2 0. The second are compositions that are not following DCP's Rules 2, 3 or 4 such neg_entr entpeenrrcchhhfee
cosh(æ) log(cosh(z)), where neg_ reg_entr(r = x log(x) is convex but not increasing, and thus composing it with the convex function cosh(2:). DCP Rule 2a does not apply here. Both examples far do not need the template expression from Proposition to certified convex by the Hessian approach. This is different for the multivariate function
Σ exp(xx)) log 1 exp(x:))
which can be expressed in vectorized form
sum(exp(z)) logoxpp)))oo(1111111111 + sum (exp(())))
Its Hessian is the sum of three matrices
sum(exp(z))
diag(exp(x)) + exp(x)exp(xr)
[oo(( + sum(exp(x))) +
(1 +1+ sum(ep((x)))
1 + sum(exp(x))
+ (1 +1+ (1sum(exp(e)))
sum(exp(x))
(iig((ep((z)) exp(x)exp(a) //sm((((()))(((x
sum sum(exp(z))
where the last matrix matches the template expression from Proposition 2
up positive prefactor is instantiated by vector(1) and 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 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 implementation of the Hessian approach works 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.
This work was supported by the Carl Zeiss Foundation within the project "Interactive Inference" and by the Ministry for Economies, Sciences and Digital Society of Thuringia (TMWWDG) under the framework of the Landesprogramm ProDigital (DigLeben-5575/109)
Acknowledgments
10

---

References
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen P. Boyd. A Rewriting System for Convex Optimization Problems. CoRR, hts/1709.04433 2017.
Amir Ali Ahmadi and Georgina Hall. On the complexity of detecting convexity over a box. Mathe- matical Programming. 182(1):429 443, 2020.
Amir Ali Ahmadi, Alexander Olshevsky, Pablo A. Parrilo, and John N. Tsitsiklis. NP-hardness of deciding convexity of quartic polynomials and related problems. Mathematical Programming, 137(1-2)455-476, 2013.
Juan F. Camino, William Helton, Robert E. Skelton, and Jieping Ye. Matrix inequalities: sym- bolic procedure to determine convexity automatically. Integral Equations and Operator Theory, 46(4):399-454, 2003.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions. In International Conference on Machine Learning (ICML), 2017.
Steven Diamond and Stephen P. Boyd. CVXPY: A Python-Embeddeed Modeling Language for Convex Optimization. Journal of Machine Learning Research, 17:83:1-83.1 2016.
Robert Fourer and Dominique Orban. DrAmpl: meta solver for optimization problem analysis. Computational Management Science, 7(4):437-463, 2010.
Robert Fourer, Chandrakant Maheshwari, Arnold Neumaier, Dominique Orban, and Hermann Schichl. Convexity and Concavity Detection in Computational Graphs: Tree Walks for Convexity Assess- ment. INFORMS Journal on Computing, 22(1):26 43, 2010.
Anqi Fu, Balasubramaniaa Narasimhan, and Stephen Boyd. CVXR: An R Package for Disciplined Convex Optimization. Journal of Statistical Software, 94(1 94(14):1-34 2020.
Michael Grant and Stephen Boyd. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pages 95-110. Springer, 2008.
Michael Grant and Stephen Boyd. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http: / c/w.r////xxr./e www.ecccoccoooooo cvx 2014.
Michael Grant, Stephen Boyd, and Yinyu Ye. Disciplined convex programming. Global Optimiza- fion: From Theory to Implementation, Noncomex Optimization and Its Application Series, pages 155-210. Springer, 2006.
Michael Grant, Stephen Boyd, and Yinyu Ye. Disciplined convex programming. In Global Optimiza- tion: From Theory Implementation, Nonconvex Optimization and its Application Series, pages 155-210. Springer, 2006.
William Helton and Mauricio de Oliveira. The NCAlgebra Suite Version 5.0, 2000.
Michael V. Klibanov. Global convexity in a three-dimensional inverse acoustic problem. SIAM Journal Mathematical Analysis, 1876)1337 1997.
Sören Laue, Matthias Mitterreiter, and Joachim Giesen. Computing Higher Order Derivatives of Matrix and Tensor Expressions. In Neural Information Processing Systems (NeurIPS), pages 2755-2764, 2018.
Sören Laue, Matthias Mitterreiter, and Joachim Giesen. GENO GENeric Optimization for Classical Machine Learning. In Advances Neural Information Processing Systems (NeurIPS), pages 2187-2198, 2019.
Sören Laue, Matthias Mitterreiter, and Joachim Giesen. A Simple and Efficient Tensor Calculus. In Conference Artificial Intelligence (AAAI), pages 4527-4534, 2020.

---

Ivo P. Nenov, Daniel H. Fylstra, and Lubomir V. Kolev. Convexity determination in the Microsoft Excel solver using automatic differentiation techniques. In International Workshop on Automatic Differentiation, 2004.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Mikhail Posypkin and Oleg Khamisov. Automatic Convexity Deduction for Efficient Function's Range Bounding. Mathematics, 9(2):134, 2021.
Hermann Schichl and Amoll Neumaier. Interval Analysis on Directed Acyelic Graphs for Global Optimization. Journal of Global Optimization, 33(4):541-562. 2005.
Shambhavi Singh and Yves Lucet. Linear-Time Convexity Test for Low-Order Piecewise Polynomials. SIAM Journal on Optimization, 31(1):972-99) 2021.
Mohit Tawarmalani and Nikolaos V. Sahinidis. polyhedral branch-and-cn approach to global optimization. Mathematical Programming, 103(2):225-2499 2005.
Madeleine Udell, Karanveer Mohan, David Zeng, Jenny Hong. Steven Diamond, and Stephen Boyd. for Convex optimization in julia. In IEEE Workshop for High Performance Technical Computing in
Dynamic Languages (HPTCDL), pages 18-28, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] These impacts are probably only very indirect.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "s4uPQbDavVA", "reviewer": "Reviewer_yPQf", "summary": "This work presents an implementation of the Hessian approach for certifying the convexity of differential functions. It is argued that it complements the well-established disciplined convex programming (DCP). Some examples are presented to show that the proposed approach can be even more powerful than the DCP approach (e.g., in Section 7).", "questions": "It would be better to clarify the computational properties of the proposal Hessian approach. ", "limitations": "The evaluation of the proposed Hessian approach is relatively limited and not solid. More practical examples will help convince the effectiveness. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper is in general well-written, and the main message is easy to follow. \n+ The analysis is solid and correct, and the unique contributions are highlighted in a good way (unlike a few other Neurips submission I reviewed, which has obvious technical flaws or unclear contributions).\n+ An implementation of the proposed approach is provided on an anonymized website.\n\nWeakness\n- Although well-motivated, it is unclear about the efficiency in terms of computation and storage to use the Hessian approach. Normally, people tend to avoid computing the Hessian explicitly, let alone verifying the positive semidefinitness of the Hessian over the entire domain. It seems like the proposed implementation can only deal with lower-dimensional problems or problems with very simple structures. What is the computational scalability in terms of time and storage?\n- It is not very clear why the Hessian approach is better than the well-established DCP. For one thing, the DCP is more flexible (by simply adding more atoms) and requires less computation (without toughing the complicated Hessian computation). For another thing, the DCP is not just testing convexity, and it can further return a standard convex optimization (in a conic form) for practical computation. It seems that the Hessian approach can only test convexity in a large sense.\n- From a technical-wise perspective, Proposition 1 is just another way to express the DCP rules for differential functions. It is unclear about differences in terms of the computational graphs as DAGs, compared to the DCP way. How do the DAGs work for a standard log det function, i.e. $f(X) = -\\log \\det(X)$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N5uHm5rlzc_", "reviewer": "Reviewer_1deo", "summary": "The authors present a framework to certify the convexity of some functions from their computational graphs. The usual tool to show the convexity of functions is to either show it by hand or use CVX which implements classical rules to know whether some compositions of functions are convex. As pointed out by the authors and as well known by the community, cvx has several limitations. In particular numerous functions need to be added manually as base \"atoms\" (i.e., basic convex functions) to demonstrate the convexity of some more complex functions. Even with these atoms, cvx may not be able to certify the convexity of some functions. The authors propose an alternative set of rules based on certifying the positive definiteness of Hessians through simple algebraic rules plus a few additional ones. The authors chose to present their ideas through several examples and a few propositions rather than a constructive framework. The authors present how their framework can encompass and surpass CVX to certify the convexity of new convex functions. ", "questions": "- What is the definition of a normalized expression DAG? What is a normalized vectorized form?\n- The authors mention a \"language for representing multivariate function (see the supplementary material)\" line 122 in the text. However, I do not see where this language is formally described. If the authors refer to Figure 1, this Figure is simply not understandable: what ['], [.] mean ? What is written in the factor line? The authors may come from a field where these expressions are obvious but if they wish their paper to be read they need to give proper definitions and gentler introductions to their formalism. \n- The proof of Propositions 1 and 3 are rather trivial and could be put in the Appendix in order to give a formal definition of the framework or at least a pseudocode of the algorithm. \n- An example motivated by real applications (such as the modeling of some data with a complex model) would greatly improve the relevance of the paper (though the current framework appears to be already a good tool for it). ", "limitations": "- As the authors mention, the current formalism does not incorporate non-smooth functions which are often used as when using a ReLU or the l1 norm. \n- The authors do not mention that convexity is not necessary to ensure convergence of e.g. first-order algorithms. Non-convex gradient dominating functions can also be optimized efficiently by a first-order method. This unfortunately limits the relevance of the approach for several problems that have been shown to satisfy a gradient dominating property while not convex. ", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The emergence of deep learning networks has diminished the appeal of convex modeling of problems. Yet, in numerous situations, practitioners may develop complex models (as in e.g. Bayesian statistics) where convexity could be a criterion to decide which model to prefer. So though the paper may seem not timely, I believe it can still be a very useful tool for the community. \n- While the rules proposed by the authors appear extremely simple (Proposition 1) and not new, they are able to circumvent the need for all \"patches\" done in CVX (that is adding more and more basic functions). In other words, the framework proposed by the authors appears to be a better path to building a sound framework to prove the convexity of functions. \n- The authors still require a few additional rules such as Proposition 2. But this might be where the paper appears the most interesting: finding as few additional and simple rules as possible to capture numerous cases beyond just adding log-sum-exp as an additional function.\n- Overall, this is an original contribution to a topic that seems to have been often overlooked by either simply using CVX, or just checking the positive definiteness of the Hessian symbolically yet at low scale, or simply discarding the issue by saying that as long as the algorithm converges it could be enough. \n- The available code is user-friendly. \n\nWeaknesses:\nWhile the idea is original and promising, there are several limitations, some can be seen as future directions, some are due in my opinion to the presentation.  \n- The main issue for me is the lack of formalism. While I appreciate the examples, there is no pseudo-code shared to understand the mechanisms of the approach and help peers to build upon it. The approach proposed by the authors may be a very interesting starting point to understanding the completeness/limitations of DAG representations of functions to certify convexity. Yet, without a few more formalism it cannot be built upon. \n- There are also a few definitions that are simply not defined or understandable as detailed in the questions.  \n\nUpdate after having personally explored a bit more frameworks such as JAX from Google:\n- Though again, I would have liked to understand some pseudocode better to help other people build on this idea, I also realized that this could probably easily be implemented as part of homoiconic programming languages such as Julia or JAX. Namely, these languages parse functions in form of expressions which I think are quite similar to what the authors are doing. So I updated my score since I believe this is an original yet simple and really useful tool that the authors developed and that could readily be integrated into some machine learning packages. I would sincerely appreciate it if the authors could add more background (in the appendix with some pseudocode or some generic framework *if possible*), this could have the potential for further research maybe as long as the authors make the effort to help other researchers build on it. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MrjrWQxgI5e", "reviewer": "Reviewer_WYiR", "summary": "The paper implements the Hessian approach for certifying the convexity of functions, which complements the well-established disciplined convex programming approach and works for non-differentiable functions.", "questions": "See the comments above.", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper writing is very good and the presentation is clear.\n- The implementation is based on a formal language that is sufficiently rich to support a large class of problems. The anonymized implementation demo is promising.\n- The fundamentals of the implementation seem to be solid by using computational graphs for Hessians, the rule set and atoms.\n\nI would say I am not an expert on this field, i.e., computational frameworks for convex optimization. My best educated guess is that the paper has a solid background as well as an attractive web demo. I am willing to learn from other reviewers' comments and the rebuttal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept