Performance Estimation

A first-order oracle for a differentiable function $f$ has the form $o(x) = (f(x), \nabla f(x))$, where $\nabla f$ is the gradient of $f$.

Let $\mathcal{O}$ be the class of first-order oracles for differentiable convex functions from $\mathbb{R}^n$ to $\mathbb{R}$. The domain of the oracle is $X = \mathbb{R}^n$, and the codomain is $Y = \mathbb{R}\times\mathbb{R}^n$. Given a finite set $S = \{(x_i,(f_i,g_i))\}_{i=1}^m$, the interpolation conditions are that [2]

\[ f_i \geq f_j + g_j^\top (x_i-x_j) \qquad\text{for all $i,j=1,\ldots,m$}.\]

If these conditions hold, then there exists a differentiable convex function $f : \mathbb{R}^n\to\mathbb{R}$ such that $f_i = f(x_i)$ and $g_i = \nabla f(x_i)$ for all $i=1,\ldots,m$.

Consider a set of vectors $x_1,x_2,\ldots,x_m\in\mathbb{R}^n$. Associated with each vector $x_i$, we can define the associated oracle $o_i(x) = x_i^\top x$, which is a linear function from $\mathbb{R}^n$ to $\mathbb{R}$. Evaluating each linear function at each of the vectors yields the scalars $g_{ij} = o_i(x_j) = x_i^\top x_j$. The associated Gram matrix is the symmetric matrix of inner products,

\[ G = \begin{bmatrix} g_{11} & g_{12} & \ldots & g_{1m} \\ g_{21} & g_{22} & \ldots & g_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ g_{m1} & g_{m2} & \ldots & g_{mm} \end{bmatrix}.\]

For any set of vectors $x_1,\ldots,x_m\in\mathbb{R}^n$, the Gram matrix is positive semidefinite. Moreover, any positive semidefinite matrix in $\mathbb{R}^{n\times n}$ is the Gram matrix of a set of $m$ vectors, provided that the dimension $n$ is sufficiently large. In particular, the dimension must be at least the rank of the Gram matrix. In other words, the interpolation conditions for the set of oracles $o_1,\ldots,o_m$ evaluated at the points $x_1,\ldots,x_m$ are

\[ G \succeq 0 \qquad\text{and}\qquad n \geq \text{rank}(G).\]

If the dimension $n$ is larger than the number of vectors $m$, then the rank condition is trivially satisfied. Moreover, the analysis can still be used to construct bounds when this "high dimension" assumption fails, although the analysis may not be tight in that case.

Let $\mathcal{F}$ be the class of differentiable convex functions on $\mathbb{R}^n$, and let $o_f$ be the corresponding first-order oracle. Consider applying gradient descent to an objective function $f\in\mathcal{F}$ with initial condition $x_0\in\mathbb{R}^n$ and constant stepsize $\alpha>0$,

\[ x_{k+1} = x_k - \alpha\,\nabla f(x_k).\]

Suppose we want to analyze the worst-case value of the performance measure $f(x_1) - f_*$, where $f_*\in\mathbb{R}$ is the optimal value. To make the problem bounded, we add the constraint $\|x_0 - x_*\|^2 \leq 1$ on the initial condition, where $x_*\in\mathbb{R}^n$ is an optimal point. This specifies that the initial condition is at most a distance of one from an optimal solution. The performance estimation problem for this setup is

\[ \begin{aligned} \text{maximize} \quad & f(x_1) - f(x_*) \\ \text{subject to} \quad & \|x_0 - x_*\|^2 \leq 1 \\ & \|\nabla f(x_*)\|^2 = 0 \\ & x_1 = x_0 - \alpha\,\nabla f(x_0) \\ & f \in \mathcal{F} \end{aligned}\]

with variables $x_0,x_1,x_*\in\mathbb{R}^n$ and $f : \mathbb{R}^n\to\mathbb{R}$. This problem is both non-convex and infinite dimensional. Replacing the convex function $f\in\mathcal{F}$ with the interpolation conditions for convex functions, the problem is equivalent to

\[ \begin{aligned} \text{maximize} \quad & f_1 - f_* \\ \text{subject to} \quad & \|x_0 - x_*\|^2 \leq 1 \\ & \|g_*\|^2 = 0 \\ & x_1 = x_0 - \alpha\,g_0 \\ & f_0 \geq f_1 + g_1^\top (x_0 - x_1) \\ & f_1 \geq f_0 + g_0^\top (x_1 - x_0) \\ & f_0 \geq f_* + g_*^\top (x_0 - x_*) \\ & f_* \geq f_0 + g_0^\top (x_* - x_0) \\ & f_1 \geq f_* + g_*^\top (x_1 - x_*) \\ & f_* \geq f_1 + g_1^\top (x_* - x_1) \end{aligned}\]

with variables $x_0,x_1,x_*,g_0,g_1,g_*\in\mathbb{R}^n$ and $f_0,f_1,f_*\in\mathbb{R}$. The problem is now finite dimensional but still non-convex. By interpreting the transposed vectors as linear functions and replacing these linear functions (and their inputs) with the interpolation conditions on their Gram matrix, the problem is equivalent to

\[ \begin{aligned} \text{maximize} \quad & f_1 - f_* \\ \text{subject to} \quad & G_{x_0 x_0} - G_{x_0 x_*} - G_{x_* x_0} + G_{x_* x_*} \leq 1 \\ & G_{x_* x_*} = 0 \\ & x_1 = x_0 - \alpha\,g_0 \\ & f_0 \geq f_1 + G_{g_1 x_0} - G_{g_1 x_1} \\ & f_1 \geq f_0 + G_{g_0 x_1} - G_{g_0 x_0} \\ & f_0 \geq f_* + G_{g_* x_0} - G_{g_* x_*} \\ & f_* \geq f_0 + G_{g_0 x_*} - G_{g_0 x_0} \\ & f_1 \geq f_* + G_{g_* x_1} - G_{g_* x_*} \\ & f_* \geq f_1 + G_{g_1 x_*} - G_{g_1 x_1} \\ & G = G^\top \succeq 0 \\ & \text{rank}(G) \leq n \end{aligned}\]

with variables

\[ G = \begin{bmatrix} G_{x_0 x_0} & G_{x_0 x_1} & G_{x_0 x_*} & G_{x_0 g_0} & G_{x_0 g_1} & G_{x_0 g_*} \\ G_{x_1 x_0} & G_{x_1 x_1} & G_{x_1 x_*} & G_{x_1 g_0} & G_{x_1 g_1} & G_{x_1 g_*} \\ G_{x_* x_0} & G_{x_* x_1} & G_{x_* x_*} & G_{x_* g_0} & G_{x_* g_1} & G_{x_* g_*} \\ G_{g_0 x_0} & G_{g_0 x_1} & G_{g_0 x_*} & G_{g_0 g_0} & G_{g_0 g_1} & G_{g_0 g_*} \\ G_{g_1 x_0} & G_{g_1 x_1} & G_{g_1 x_*} & G_{g_1 g_0} & G_{g_1 g_1} & G_{g_1 g_*} \\ G_{g_* x_0} & G_{g_* x_1} & G_{g_* x_*} & G_{g_* g_0} & G_{g_* g_1} & G_{g_* g_*} \end{bmatrix} \in \mathbb{R}^{6\times 6}\]

and

\[ F = \begin{bmatrix} f_0 \\ f_1 \\ f_* \end{bmatrix} \in \mathbb{R}^3.\]

This is a semidefinite program when $n \geq 6$, as the rank constraint is vacuous in that case. Also, the problem can be simplified since the constraint $G_{x_* x_*} = 0$ along with $G\succeq 0$ implies that the corresponding row and column of the Gram matrix must be zero and therefore could be removed from the optimization problem. The Gram matrix is then in $\mathbb{R}^{5\times 5}$, in which case the rank constraint is vacuous if $n\geq 5$.