Convexity Certificates from Hessians (Supplementary Material)

The formal language for mathematical expressions to which our certification algorithm is applied is specified by the grammar depicted in Figure 1. The language is rich enough to cover all the examples in the main paper and this supplement. In this grammar, number is a placeholder for an arbitrary floating point number, variable is a placeholder for variable names starting with a Latin character and function is a placeholder for the supported elementary differentiable functions like exp,log and sum. Here, is used for transposition and a preceding . Here are some examples from the language (the fist example uses a transposition and the fifth and seventh example use elementwise operations): 2-norm Xw y 2: (X*w-y)'*(X*w-y) logistic log(1+exp(x)): log(1+exp(x)) 1 quadratic x2: x^2 relative entropy xlog(x/y): x*log(x/y), x>0, y>0 logistic regression Our implementation of the Hessian approach works on vectorized and normalized expression DAGs (directed acyclic graphs) for Hessians that contain every subexpression exactly once.