Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

Introduction, Definition of “Relative-Smoothness,” and Basic Properties

There are by now very many first-order methods for tackling the optimization problem (1), see for example , , ; virtually all such methods are designed to solve (1) when the gradient of $f(\cdot)$ satisfies a uniform Lipschitz condition on $Q$, namely there exists a constant $L_{f}<\infty$ for which:

One can prove for the standard gradient descent scheme that after $k$ iterations it holds for any $x\in Q$ that:

which is an $O(1/k)$ sublinear rate of convergence , . Furthermore, if $f(\cdot)$ is also uniformly $\mu_{f}$-strongly convex for some $\mu_{f}>0$, namely:

then one can prove linear convergence for the gradient descent scheme, see , , i.e., for any $x\in Q$ we have that:

More general versions of first-order methods are not restricted to the Euclidean ($\|\cdot\|_{2}$) norm, and use a differentiable “prox function” $h(\cdot)$, which is a $1$-strongly convex function on $Q$, to define a Bregman distance:

The standard Primal Gradient Scheme (with Bregman distance), see , has the following update formula:

Notice in (8) by construction that the update requires the capability to solve instances of a subproblem of the general form:

for suitable iteration-specific values of $c$; indeed, (8) is an instance of the subproblem (9) with $c=\tfrac{1}{L_{f}}\nabla f(x^{i})-\nabla h(x^{i})$ at iteration $i$. It is especially important to note that the Primal Gradient Scheme is somewhat meaningless whenever we do not have the capability to efficiently solve (9), a point which we will return to later on. In a typical design and implementation of a first-order method for solving (1), one attempts to specify the norm $\|\cdot\|$ and the strongly convex prox function $h(\cdot)$ in consideration of the shape of the feasible domain $Q$ while also ensuring that the subproblem (9) is efficiently solvable.

Regarding computational guarantees, one can prove for the Primal Gradient Scheme that after $k$ iterations it holds for any $x\in Q$ that:

which is an exact generalization of (4), see , .

Notice that unlike quadratic functions, the second-order terms of the functions in the above examples vary dramatically on $Q$ – and especially as $x\rightarrow\partial Q$ (or as $x$ goes to infinity in $Q$). It therefore becomes unreasonable to use a uniform bound of the form $L_{f}$ to upper-bound second-order information.

Motivated by the above drawbacks in standard first-order methods, we develop a notion of “relative smoothness” and relative strong convexity, relative to a given “reference function” $h(\cdot)$ and which does not require the specification of any particular norm – and indeed $h(\cdot)$ need not be either strictly or strongly convex. Armed with relative smoothness and relative strong convexity, we demonstrate the capability to solve a more general class of differentiable convex optimization problems (without uniform Lipschitz continuous gradients), and we also demonstrate linear convergence results for both a Primal Gradient Scheme and a Dual Averaging Scheme when the function is both relatively smooth and relatively strongly convex.

There is a certain overlap of ideas and results herein with the paper by Bolte, Bauschke, and Teboulle. For starters, the relative smoothness condition definition in the present paper in Definition 1.1 is equivalent to the (LC) condition in except that also requires the reference function $h(\cdot)$ to be essentially smooth and strictly convex, which we do not need in this paper. The main developments in are based on generalizing a key descent lemma and applying this generalization to tackle (additive) composite optimization problems using the primal gradient scheme (called the NoLips Algorithm in ) with associated complexity analysis involving a symmetry measure of the Bregman distance $D_{h}(\cdot,\cdot)$. These results are then illustrated in the application of composite optimization to Poisson inverse problems. While the NoLips Algorithm in is structurally the same as Algorithm 1 herein, they are both instantiations of the standard primal gradient scheme; however, as will be seen in Section 3 here, we do not need any symmetry measure in constructing step-sizes or in the complexity analysis. The paper by Zhou, Liang, and Shen also tackles composite optimization using the standard primal gradient scheme which therein is called PGA-$\cal B$, with a focus on demonstrating equivalence of proximal gradient and proximal point methods more broadly. Here we develop measures of relative smoothness and also relative strong convexity, which can improve the computational guarantees of the primal gradient scheme, see Theorem 3.1. We further present computational guarantees for the dual averaging scheme in Theorem 3.2. In Section 2 we show that many differentiable convex functions are relatively smooth with respect to a correspondingly fairly-simple reference function $h(\cdot)$ that is easy to construct and for which algorithmic computations can be effeciently be performed. In Section 4 we apply our approach to develop a new first-order method for the $D$-optimal design problem, with associated computational complexity analysis. Throughout the current paper, we compare and clarify similarities and differences between our work and in the context of the specific contributions as they arise.

2 Relative Smoothness and Relative Strong Convexity

Let $h(\cdot)$ be any given differentiable convex function (it need not be strongly nor even strictly convex) defined on $Q$. We will henceforth refer to $h(\cdot)$ as the “reference function.” We define “relative smoothness” and “relative strong convexity” of $f(\cdot)$ relative to $h(\cdot)$ using the Bregman distance (7) associated with $h(\cdot)$ as follows.

The following proposition presents equivalent definitions of relative smoothness and relative strong convexity. In the case when both $f(\cdot)$ and $h(\cdot)$ are twice differentiable, parts (a-iii) and (b-iii) of the proposition demonstrate that the above definitions are equivalent to

which is an intuitively simple condition on the Hessian matrices of the two functions.

$f(\cdot)$ is $L$-smooth relative to $h(\cdot)$,

$Lh(\cdot)-f(\cdot)$ is a convex function on $Q$,

$f(\cdot)$ is $\mu$-strongly convex relative to $h(\cdot)$,

$f(\cdot)-\mu h(\cdot)$ is a convex function on $Q$,

The first part of Proposition 1.1 is almost equivalent to Proposition 1 of .

Proof: For $x\in Q$ define $\phi(x):=Lh(x)-f(x)$. Using (11) and (7) it follows that (a-i) holds if and only if $\phi(x)\geq\phi(y)+\langle\nabla\phi(y),x-y\rangle$ for all $x,y\in Q$, which is equivalent to the convexity of $\phi(\cdot)=Lh(\cdot)-f(\cdot)$ from Theorem 2.1.2 of , thus showing that (a-i) $\Leftrightarrow$ (a-ii). It follows from Theorem 2.1.3 of applied to $\phi(\cdot)$ that $\phi(\cdot)$ is convex if and only if $\langle\nabla\phi(x)-\nabla\phi(y),x-y\rangle\geq 0$ for all $x,y\in Q$, which shows that (a-ii) $\Leftrightarrow$ (a-iv). If $f(\cdot)$ and $h(\cdot)$ are twice differentiable, then it follows from Theorem 2.1.4 of that (a-ii) $\Leftrightarrow$ (a-iii).

Similar proofs can be applied for part (b).∎

For notational convenience, let us denote by $f(\cdot)\preceq h(\cdot)$ that $h(\cdot)-f(\cdot)$ is a convex function, whereby this also means $f(\cdot)$ is $1$-smooth with respect to $h(\cdot)$ from Proposition 1.1. Similarly $f(\cdot)\succeq h(\cdot)$ means $f(\cdot)-h(\cdot)$ is a convex function and so $f(\cdot)$ is $1$-strongly convex with respect to $h(\cdot)$. (In the case when both $f(\cdot)$ and $h(\cdot)$ are twice differentiable, the relation “$\cdot\succeq\cdot$” on two functions is consistent with the Löwner partial order on the Hessians of these two functions from Propositon 1.1.) Then the condition that $f(\cdot)$ is $L$-smooth with respect to $h(\cdot)$ is equivalent to $f(\cdot)\preceq Lh(\cdot)$; similarly the condition that $f(\cdot)$ is $\mu$-strongly convex with respect to $h(\cdot)$ is equivalent to $f(\cdot)\succeq\mu h(\cdot)$. In addition, relative-smoothness and relative strong convexity are each transitive, so that $f(\cdot)\preceq g(\cdot)$ and $g(\cdot)\preceq h(\cdot)$ implies that $f(\cdot)\preceq h(\cdot)$.

We can also work with sums and linear transformations of relatively smooth and/or relatively strongly convex functions, as the next proposition states.

If $f_{1}(\cdot)\preceq L_{1}h(\cdot)$ and $f_{2}(\cdot)\preceq L_{2}h_{2}(\cdot)$, then for all $\alpha,\beta\geq 0$ it holds that $f(\cdot):=\alpha f_{1}(\cdot)+\beta f_{2}(\cdot)\preceq h(\cdot):=\alpha L_{1}h_{1}(\cdot)+\beta L_{2}h_{2}(\cdot)$.

If $f_{1}(\cdot)\succeq\mu_{1}h_{1}(\cdot)$ and $f_{2}(\cdot)\succeq\mu_{2}h_{2}(\cdot)$, then for all $\alpha,\beta\geq 0$ it holds that $f(\cdot):=\alpha f_{1}(\cdot)+\beta f_{2}(\cdot)\succeq h(\cdot):=\alpha\mu_{1}h_{1}(\cdot)+\beta\mu_{2}h_{2}(\cdot)$.

If $f(\cdot)\preceq h(\cdot)$, and $A$ is a linear transformation of appropriate dimension, then $\phi_{f}(x):=f(Ax)\preceq\phi_{h}(x):=h(Ax)$.

If $f(\cdot)\succeq h(\cdot)$, and $A$ is a linear transformation of appropriate dimension, then $\phi_{f}(x):=f(Ax)\succeq\phi_{h}(x):=h(Ax)$.

Proof: The proofs of the first two arguments follow directly from the definitions of relative smoothness and relative strong convexity in Definitions 1.1 and 1.2. The proofs of the last two arguments follow from the equivalent definition (a-iv) and (b-iv) in Proposition 1.1.∎

3 Constructive Algorithmic Set-up

Let us now discuss criteria for choosing the reference function $h(\cdot)$ in the context of computational schemes for solving the optimization problem (1). To be concrete, consider a simple Primal Gradient Scheme as shown in Algorithm 1. Note that this scheme is essentially as described in the update formula (8), except that the uniform smoothness constant $L_{f}$ is replaced by the relative smoothness parameter $L$ of $f(\cdot)$ with respect to the reference function $h(\cdot)$ as defined in Definition 1.1, and the only formal requirement for $h(\cdot)$ is that the pair $(f(\cdot),h(\cdot))$ must satisfy the conditions of Definition 1.1.

In order to efficiently execute the update step in Algorithm 1 we also require of $h(\cdot)$ that the subproblem (9) is efficiently solvable for any given $c$. In summary, to solve the optimization problem (1) using Algorithm 1, we need to specify a reference function $h(\cdot)$ that has the following two properties:

$f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ on $Q$, and

the subproblem (9) always has a solution, and the solution is efficiently computable.

In Section 2 we will see how this can be done for several useful classes of problems that are not otherwise solvable by traditional first-order methods that require uniform Lipschitz continuity of the gradient. In Section 3 we analyze the computational guarantees associated with the Primal Gradient Scheme (Algorithm 1) as well as a Dual Averaging Scheme. In Section 4, we apply the computational guarantees of Section 3 to the $D$-optimal design problem.

Examples of Relatively Smooth Optimization Problems

Here we show several classes of optimization problems (1) for which one can easily construct a reference function $h(\cdot)$ with the two properties mentioned above, namely (i) $f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ for an easily determined value $L$, and (ii) the subproblem (9) is efficiently solvable.

Then the following proposition states that $f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ for an easily computable value $L$. This implies that no matter how fast the Hessian of $f(\cdot)$ grows as $\|x\|_{2}\rightarrow\infty$, $f(\cdot)$ can still be smooth relative to the simple reference function $h(\cdot)$, even though $\nabla f(\cdot)$ need not exhibit uniform Lipschitz continuity.

Suppose $f(\cdot)$ is twice differentiable and satisfies $\|\nabla^{2}f(x)\|\leq p_{r}(\|x\|_{2})$ where $p_{r}(\alpha)$ is an $r$-degree polynomial of $\alpha$. Let $L$ be such that $p_{r}(\alpha)\leq L(1+\alpha^{r})$ for $\alpha\geq 0$. Then $f(\cdot)$ is $L$-smooth relative to $h(x)=\frac{1}{r+2}\|x\|_{2}^{r+2}+\frac{1}{2}\|x\|_{2}^{2}$.

Proof: It follows from elementary rules of differentiation that

and so $f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ by part (iii) of Proposition 1.1. ∎

Suppose $p_{r}(\alpha)=\sum_{i=0}^{r}a_{i}\alpha^{i}$. In Proposition 2.1, one simple way to set $L$ is to use $L=\sum_{i=0}^{r}|a_{i}|$. Then

whereby $p_{r}(\alpha)\leq\max\{L,L\alpha^{r}\}\leq L(1+\alpha^{r})$ for $\alpha\geq 0$.

Solving the subproblem (9). Let us see how we can solve the subproblem (9) for this class of optimization problems. The subproblem (9) can be written as

and the first-order optimality conditions are simply:

whereby $x=-\theta c$ for some $\theta\geq 0$, and it remains to simply determine the value of the nonnegative scalar $\theta$. If $c=0$, then $x=0$ satisfies the optimality conditions. For $c\neq 0$, notice from above that $\theta$ must satisfy:

which is a univariate polynomial in $\theta$ with a unique positive root. For $r=1,2,3$, this root can be computed in closed form. Otherwise, the root can be computed (up to machine precision) using any scalar root-finding method.

We can incorporate in problem (15) a simple set constraint $x\in Q$ provided that we can easily compute the Euclidean projection on $Q$. In the case when $h(\cdot)$ is a convex function of $\|x\|_{2}^{2}$, the subproblem (9) can be converted to a $1$-dimensional convex optimization problem, see Appendix A.1 for details.

which is $2$-degree polynomial in $\|x\|_{2}$ with coefficients $a_{0}=3\|A\|^{2}\|b\|_{2}^{2}+\|C\|^{2}$, $a_{1}=6\|A\|^{3}\|b\|_{2}$, and $a_{2}=3\|A\|^{4}$. Therefore following Remark 2.1 it suffices to set

which is $2$-degree polynomial in $\|x\|_{2}$ with coefficients $a_{0}=3\|A\|^{2}\|b\|_{2}^{2}+\|C\|^{2}$, $a_{1}=6\|A\|^{3}\|b\|_{2}$, and $a_{2}=3\|E\|^{4}+3\|A\|^{4}$. Therefore following Remark 2.1 it suffices to set

(where the last matrix inequality follows since $\|x\|_{2}^{2}I\succeq xx^{T}$), and thus $f(x)$ is $\mu$-strongly convex relative to $h(x)$.

In place of the simple reference function $h(\cdot)$ in (13) one can instead consider a “re-centered” version of the form:

where the “center” value $x^{c}$ is suitably chosen to align $f(\cdot)$ with $h(\cdot)$ and possibly attain better values of $L$ and $\mu$. Note that introducing the given center value $x^{c}$ does not increase the difficulty of solving the subproblem (9). We illustrate this idea with a simple univariate example. Suppose that our objective function is $f(x)=x^{4}-4x^{3}+7x^{2}-5x+3$. From the results in Section 2.1 we know we can use the reference function $h_{1}(x):=\tfrac{1}{4}x^{4}+\tfrac{1}{2}x^{2}$. We can also translate $x$ by the center point $x^{c}:=1$ and use the reference function $h_{2}(x):=\tfrac{1}{4}(x-1)^{4}+\tfrac{1}{2}(x-1)^{2}$. Straightforward calculation yields values of $L=L_{1}=9+\sqrt{73}\approx 17.5440$ for $h_{1}(\cdot)$ and $L=L_{2}=4$ for $h_{2}(\cdot)$, whereby $h_{2}(\cdot)$ yields a better value of $L$ than $h_{1}(\cdot)$ for this example.

2 D𝐷D-Optimal Design Problem

where the first and the second matrix inequality above each follows from the fact that $C\preceq X^{-1}$ and the Hadamard product of two symmetric positive semidefinite matrices is also a symmetric positive semidefinite matrix. The result then follows using property (a-iii) of Proposition 1.1. ∎

Solving the subproblem (9). Let us see how we can solve the subproblem (9) for $Q$ and $h(\cdot)$ given above. The subproblem (9) can be written as

and the first-order optimality conditions are simply:

for some scalar multiplier $\theta$. Given $\theta$, it then follows that $x_{j}=1/(c_{j}+\theta)$ for $j=1,\ldots,n$, and it remains to simply determine the value of the scalar $\theta$. Now notice that $\theta$ must satisfy:

for some $\theta$ in the interval ${\cal F}:=(-\min_{j}\{c_{j}\},\infty)$. Notice that $d(\cdot)$ is strictly decreasing on ${\cal F}$, and $d(\theta)\rightarrow+\infty$ as $\theta\searrow-\min_{j}\{c_{j}\}$ and $d(\theta)\rightarrow-1$ as $\theta\rightarrow\infty$, whereby (18) has a unique solution in ${\cal F}$. Furthermore, as suggested by results in Ye or , one can use Newton’s method (or any other suitable scalar solution-finding method) to efficiently compute the solution of (18) (up to machine precision) on the interval ${\cal F}$ .

3 Generalized Volumetric Function Optimization

For a given integer parameter $p>0$, let us also study optimization on the simplex of the following generalization of the volumetric barrier function:

Proof: By elementary calculus, the gradient of $f_{p}(\cdot)$ is

where the first inequality follows from the fact that the Hadamard product of two symmetric positive semidefinite matrices is also a symmetric positive semidefinite matrix and $C$ is a positive semidefinite matrix, and the first equation follows since $X$ is itself a diagonal matrix. The result then follows by property (iii) of Proposition 1.1. ∎

Solving the subproblem (9). Using $h(x)=-\sum_{j=1}^{n}\ln(x_{j})$, the subproblem (9) here is identical to that for the $D$-optimal design problem, since the reference function $h(\cdot)$ and the feasible domain $Q$ are the same. Therefore the methodology discussed in Section 2.2 applies here as well.

Then the following proposition states that $f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ for an easily computable value $L$. This implies that no matter how fast $\nabla f(x)$ grows as $x$ approaches the open boundary of the region $(0,u]^{n}$, $f(\cdot)$ is smooth relative to the simple reference function $h(\cdot)$, even though $\nabla f(\cdot)$ need not exhibit uniform Lipschitz continuity on $Q$.

Suppose $f(\cdot)$ is twice differentiable on $Q$ and satisfies $\|\nabla^{2}f(x)\|\leq q_{s}\left(\sum_{i=1}^{n}\frac{1}{x_{i}}\right)$ where $q_{s}(\alpha)$ is an $s$-degree polynomial in $\alpha$. Let $L$ be such that $q_{s}(\alpha)\leq L\alpha^{s}$ for all $\alpha\geq\tfrac{n}{u}$. Then $f(\cdot)$ is $L$-smooth relative to $h(x)=\frac{u^{3}}{2(s+1)}(\sum_{i=1}^{n}\frac{1}{x_{i}})^{s+1}$.

where the second matrix inequality uses $u\geq x_{i}$ and the third matrix inequality is due to $\sum_{i=1}^{n}\tfrac{1}{x_{i}}\geq\sum_{i=1}^{n}\tfrac{1}{u}=\tfrac{n}{u}$. Therefore $f(\cdot)$ is $L$-smooth relative to $h(\cdot)$ by part (iii) of Proposition 1.1.∎

Suppose $q_{s}(\alpha)=\sum_{i=0}^{s}a_{i}\alpha^{i}$. In Proposition 2.4, one simple way to set $L$ is to use $L=\sum_{i=0}^{s}|a_{i}|\left(\tfrac{u}{n}\right)^{i-s}$. This implies for $\alpha\geq\tfrac{n}{u}$ that

Solving the subproblem (9). Let us see how we can solve the subproblem (9) for this class of optimization problems. After rescaling $c$ by $u^{3}/2$, the subproblem (9) can be equivalently written as

Let $\theta=\left(\sum_{i=1}^{n}\frac{1}{x_{i}}\right)^{s}$, then the optimality conditions for (23) can be written as:

for $i=1,\ldots,n$. For a given $\theta>0$, define $x_{i}(\theta)$ using the above rule (24), and it remains to simply determine the value of the positive scalar $\theta$ in the interval ${\cal F}:=[\left(\frac{n}{u}\right)^{s},\infty)$ that satisfies

Notice that $d(\cdot)$ is strictly increasing on ${\cal F}$, and $d\left(\left(\frac{n}{u}\right)^{s}\right)\leq 0$ (since $x_{i}(\theta)\leq u$ for any $\theta$) and $d(\theta)\rightarrow\infty$ as $\theta\rightarrow\infty$. Therefore (25) has a unique solution in ${\cal F}$, which can be solved with high accuracy using any suitable root-finding method, for example binary search combined with $1$-dimensional Newton’s method.

In a sense, there are basically two ways that a twice-differentiable convex function can fail to have a uniformly Lipschitz gradient: (i) when the Hessian grows without limit as $\|x\|\rightarrow\infty$, and/or (ii) when the Hessian grows without limit as $x\rightarrow x^{0}\in\partial Q$. Section 2.1 has provided a mechanism for constructing a reference function $h(\cdot)$ for case (i) when the growth is polynomial, and Section 2.4 has provided such a mechanism for case (ii) when the growth is polynomial. By utilizing the additivity and linear transformation properties of relative smoothness in Proposition 1.2, it should be possible to construct suitable reference functions for many convex functions of interest.

Computational Analysis for the Primal Gradient Scheme and the Dual Averaging Scheme

In this section we present computational guarantees for two algorithms: the Primal Gradient Scheme (Algorithm 1) as well as a Dual Averaging Scheme (Algorithm 2).

Our main result for the Primal Gradient Scheme is the following sublinear and linear convergence bounds.

Consider the Primal Gradient Scheme (Algorithm 1). If $f(\cdot)$ is $L$-smooth and $\mu$-strongly convex relative to $h(\cdot)$ for some $L>0$ and $\mu\geq 0$, then for all $k\geq 1$ and $x\in Q$, sequence $\{f(x^{k})\}$ is monotonically decreasing, and the following inequality holds:

where, in the case when $\mu=0$, the middle expression is defined in the limit as $\mu\rightarrow 0^{+}$. ∎

The first inequality in (26) shows linear convergence when $\mu>0$; indeed, in this case it holds that

(This inequality holds trivially for $k=1$, and induction on $k$ establishes the result for $k\geq 2$.) Furthermore, when $k$ is large the $-1$ term in the denominator of the left-hand side can be ignored which yields the asymptotic bound $\mu\left(1-\tfrac{\mu}{L}\right)^{k}D_{h}(x,x^{0})$. The second inequality in (26) shows an $O(1/k)$ sublinear convergence rate. In particular, the convergence rate in (26) is $\frac{L}{k}D_{h}(x,x^{0})$ when $\mu=0$.

Note that Algorithm 1 herein and the NoLips algorithm in as well as algorithm PGA-$\cal B$ in are structurally identical (they are all instantiations of the primal gradient methodology). However, the step-size rule in as well as the complexity analysis in depends on a symmetry measure of $D_{h}(\cdot,\cdot)$, namely $\alpha:=\min_{x,y\neq x}D_{h}(x,y)/D_{h}(y,x)$, whereas there is no such dependence here. The instantiation of Algorithm 1 in uses a smaller “step-size” of $(1+\alpha)/2L$ as opposed to $1/L$ in the update computation in Algorithm 1 (since it must always hold that $\alpha\leq 1$), and proves a computational guarantee of $f(x^{k})-f(x)\leq\frac{2L}{(1+\alpha)k}D_{h}(x,x^{0})$. The bound in Theorem 3.1 is better than this symmetry-based bound, but only by a multiplicative constant factor $(1+\alpha)/2$ when $\mu=0$; it is of course far better (linear convergence rather than sublinear convergence) when $\mu>0$.

The proof of the bound in Theorem 3.1 relies on the following standard Three-Point Property:

(Three-Point Property of Tseng ) Let $\phi(x)$ be a convex function, and let $D_{h}(\cdot,\cdot)$ be the Bregman distance for $h(\cdot)$. For a given vector $z$, let

Proof of Theorem 3.1: Define a parameter sequence

where the second equality “$(\cdot)$” follows from elementary geometric series’ analysis, and holds only when $\mu>0$. In particular, $C_{k}=\frac{1}{k}$ if $\mu=0$. For any $x\in Q$ and $i\geq 1$ we have:

where the first inequality follows from the definition of $L$-smoothness relative to $h(\cdot)$, the second inequality is due to the Three-Point Property with $\phi(x)=\tfrac{1}{L}\left\langle\nabla f(x^{i-1}),x-x^{i-1}\right\rangle$ and $z=x^{i-1}$, $z^{+}=x^{i}$, and the last inequality uses the $\mu$-strong convexity of $f(\cdot)$ relative to $h(\cdot)$, which implies $\langle\nabla f(x^{i-1}),x-x^{i-1}\rangle\leq f(x)-f(x^{i-1})-\mu D_{h}(x,x^{i-1})$. Substituting $x=x^{i-1}$ in (28) shows in particular that $f(x^{i})\leq f(x^{i-1})$ which proves monotonicity of the sequence $\{f(x^{i})\}$.

It then follows using induction and (28) that

Using the monotonicity of $f(x^{i})$ and the nonnegativity of $D_{h}(x,x^{k})$, this implies that

The proof of the second inequality in (26) follows by noting that $\left(1+\frac{\mu}{L-\mu}\right)^{k}\geq 1+\frac{k\mu}{L-\mu}$. ∎

2 Dual Averaging Scheme and Analysis

Another algorithm for solving our optimization problem (1) is the Dual Averaging Scheme , which we present here in Algorithm 2. Somewhat akin to the Primal Gradient Scheme, the update step in the Dual Averaging Scheme also requires the solution of a subproblem exactly of the form (9). Notice that we need the coefficient $\mu$ of strong convexity in order to implement Algorithm 2, in contrast to the Primal Gradient Scheme (Algorithm 1). One can always conservatively set $\mu\leftarrow 0$ in Algorithm 2 if no reasonable lower bound on best value of $\mu$ is known.

We have the following result regarding computational guarantees for the Dual Averaging Scheme.

Consider the Dual Averaging Scheme (Algorithm 2). If $f(\cdot)$ is $L$-smooth and $\mu$-strongly convex relative to $h(\cdot)$ with $L>\mu$, then for all $k\geq 1$ and $x\in Q$, the following inequality holds:

where in the case $\mu=0$, the middle expression is defined as the limits as $\mu\to 0^{+}$.

Similar to the result in Theorem 3.1, the first inequality in (32) shows linear convergence when $\mu>0$, since

this follows using identical logic as in (27).

Proof of Theorem 3.2: Define $\psi_{k}(x):=h(x)+\sum\limits_{i=0}^{k-1}a_{i+1}\left(f(x^{i})+\langle\nabla f(x^{i}),x-x^{i}\rangle+\mu D_{h}(x,x^{i})\right)$ for $k\geq 0$ and $\psi_{k}^{*}:=\min\limits_{x\in Q}\psi_{k}(x)$, whereby $x^{k}=\operatorname*{arg\,min}_{x\in Q}\psi_{k}(x)$ and $\psi_{k}(x^{k})=\psi_{k}^{*}$. It follows from the definition of relative strongly convexity (Definition 1.2) that for any $x\in Q$:

for all $k\geq 0$, and where the second equality “$(\cdot)$” above follows from elementary geometric series’ analysis and holds only when $\mu>0$; note that $A_{k}=\frac{k}{L}$ when $\mu=0$.

The function $\psi_{k}(\cdot)$ is a sum of a linear function and the reference function $h(\cdot)$ multiplied by the coefficient $1+\mu A_{k}$. Therefore $(1+\mu A_{k})h(\cdot)$ and $\psi_{k}(\cdot)$ define the same Bregman distance, whereby for any $x\in Q$ it holds that:

where the last inequality utilizes $\psi_{k}(x^{k})=\psi_{k}^{*}$ as well as the first order optimality condition of $x^{k}=\operatorname*{arg\,min}_{x\in Q}\psi_{k}(x)$. Therefore:

where the last inequality uses (35) with $x=x^{k+1}$. Taking into account that $\mu+\frac{1}{a_{k+1}}(1+\mu A_{k})=\frac{1+\mu A_{k+1}}{a_{k+1}}=\frac{1}{a_{k+1}}\left(\frac{L}{L-\mu}\right)^{k+1}=L$, and using the relative smoothness of $f(\cdot)$ (Definition 1.1), we obtain:

where the second inequality is from (34). The proof is completed by rearranging (36) and taking the minimum over $i$. ∎

3 On Optimization Problems with a Composite Function

Sometimes we are interested in solving the composite optimization problem :

under the same assumptions on $f(\cdot)$ and $Q$ as in (1), but now the objective function includes another function $P(\cdot)$ that is assumed to be convex but not necessarily differentiable, and for which the following subproblem is efficiently solvable:

for any given $c$. Under this assumption it is straightforward to show that Algorithm 1 naturally extends to cover the case of the composite optimization problem (37) (see and ) and that the computational guarantee in Theorem 3.1 extends to composite optimization as well. (Indeed, when $\mu=0$ this extension is implied in principle from .) It turns out that one can actually view composite optimization as working with the objective function $\bar{f}(\cdot)$ that is $1$-smooth relative to the reference function $\bar{h}(\cdot):=Lh(\cdot)+P(\cdot)$. However, the definition of the reference function $h(\cdot)$ has been premised on $h(\cdot)$ being differentiable on $Q$, which might not hold for $\bar{h}(\cdot)$ as just defined. This can all be taken care of by a suitable modification of the theory, see Appendix A.2 for details.

4 Questions: Accelerated Methods, Conjugate Duality, Choosing the Reference Function

We have shown here in Section 3 that the computational guarantees of two standard first-order methods for smooth optimization – the Primal Gradient Scheme and the Dual Averaging Scheme – extend in precise ways to the case when $f(\cdot)$ is $L$-smooth relative to the reference function $h(\cdot)$. The proof techniques used here suggest that very many other first-order algorithms for smooth optimization should extend similarly with analogous computational guarantees. However, we have not been able to extend any accelerated methods, i.e., methods that attain an $O(1/k^{2})$ convergence guarantee such as , , , to the relatively smooth case. One avenue for further research is to answer the question whether one can develop computational guarantees for an accelerated method in the case when $f(\cdot)$ is $L$-smooth relative to the reference function $h(\cdot)$?

Another question that arises concerns conjugate (duality) theory for the setting of relatively smooth convex functions. One simple result in conjugate duality theory is that when $f(\cdot)$ is $L$-smooth (relative to $h(\cdot):=\tfrac{1}{2}\|\cdot\|^{2}$) the conjugate function $f^{*}(\cdot)$ is $1/L$-strongly convex (relative to $h^{*}(\cdot):=\tfrac{1}{2}\|\cdot\|_{*}^{2}$), see . Is there a way to develop a more general conjugate duality theory that yields an analogous result when $f(\cdot)$ is $L$-smooth relative to a general convex function $h(\cdot)$?

A third question is how can we choose the reference function $h(\cdot)$ in order to lower the value of the bounds in Theorems 3.1 and 3.2? Several ways to think about this question are discussed in Appendix A.3.

D𝐷D-Optimal Design Revisited: Computational Guarantees using the Primal Gradient or Dual Averaging Scheme

Let us now apply the computational guarantees for the Primal Gradient Scheme (Theorem 3.1) and the Dual Averaging Scheme (Theorem 3.2) to the $D$-optimal design optimization problem (16) discussed in Section 2.2. Recall from the exposition in Section 2.2 that $Q=\Delta_{n}$ and $f(x)=-\ln\det(HXH^{T})$ is $1$-smooth relative to the logarithmic barrier function

and that the subproblem (9) is efficiently solvable. The following theorem presents a computational guarantee for using the Primal Gradient Scheme to approximately solve the $D$-optimal design optimization problem (16).

Consider using the Primal Gradient Scheme (Algorithm 1) with the reference function (39) to solve the $D$-optimal design problem (16) using the initial point $x^{0}=\frac{1}{n}e$, and suppose that $\varepsilon\leq f(x^{0})-f^{*}$. If

Proof: Let $\delta=\frac{\varepsilon}{2(f(x^{0})-f^{*})}$. Then $\delta\leq\frac{1}{2}$ since $\varepsilon\leq f(x^{0})-f^{*}$. Let $\hat{x}:=(1-\delta)x^{*}+\delta x^{0}$. It follows from the convexity of $f(\cdot)$ that

where the second equality uses $\nabla h(x^{0})=-n\cdot e$ which then implies $\langle\nabla h(x^{0}),\hat{x}-x^{0}\rangle=0$, and the inequality follows since $\hat{x}\geq(\delta/n)e$. Therefore, for $k$ satisfying the inequality in the statement of the theorem, we have:

where the first inequality follows from Theorem 3.1 using $x=\hat{x}$, as well as (40), the second inequality is from (41) and the definition of $\delta$, and the third inequality follows since $k\geq[2n\ln(1/\delta)]/\varepsilon$. ∎

For the Dual Averaging Scheme (Algorithm 2), one obtains the identical bound as in Theorem 4.1. This is proved by following virtually the same logic as above, except we use Theorem 3.2 which bounds the smallest optimality gap using $h(x)-h(x^{0})$ instead of $D_{h}(x,x^{0})$. However, it follows from (41) that these two quantities are the same in this case. Also, in the case of the Dual Averaging Scheme, the relevant final quantity of interest is $\min_{i=1,\ldots,k}f(x^{i})-f^{*}$ instead of $f(x^{k})-f^{*}$.

It is instructive to compare the computational guarantees in Theorem 4.1/Remark 4.1 to those of the Frank-Wolfe method applied to $D$-optimal design (first analyzed by Khachiyan and re-evaluated in based in part on work by Yildirim ). Table 1 shows such a comparison, where absolute constants have been suppressed in order to highlight the dependencies on particular quantities of interest. The second column of Table 1 compares the iteration bound of the methods using the starting point $x^{0}=(1/n)e$, where we emphasize that $\varepsilon$ is the target optimality gap for the $D$-optimal design problem. While it follows from observations in that $f(x^{0})-f^{*}\leq m\ln(n/m)$ for $x^{0}=(1/n)e$, we do not show this in Table 1, as we wish to highlight where the dependence on the initial iterate arises. Examining the first column of Table 1, note that the number of iterations of the Primal Gradient Scheme (or Dual Averaging Scheme) can be less than that of the Frank-Wolfe method, especially when $\varepsilon$ is not too small and when $n\ll m^{2}$. However, as the second column of Table 1 shows, the Frank-Wolfe method requires only $mn$ operations per iteration in the worst – i.e., dense matrix – case, as it does a rank-$1$ update of a matrix inverse in the computation of $\nabla f(x^{k})$), whereas the Primal Gradient Scheme (or Dual Averaging Scheme) requires $m^{2}n$ operations per iteration in the dense case (it must re-compute a matrix inverse in order to work with $\nabla f(x^{k})$). Therefore the total bound on operations of the Frank-Wolfe method (shown in the last column of Table 1) is superior.

The bound for the Frank-Wolfe method applied to the $D$-optimal design problem is based on analysis that is uniquely designed for evaluating the $D$-optimal design problem, and is not part of the general theory for the Frank-Wolfe method (that we are aware of). Even though the Primal Gradient Scheme and the Dual Averaging Scheme have inferior computational guarantees to the Frank-Wolfe method applied to the $D$-optimal design problem, they are the first (that we are aware of) first-order methods for which one has a general theory (Theorems 3.1 and 3.2) that can be meaningfully applied to yield computational guarantees for the $D$-optimal design problem. We hope that this analysis will spur further interest in developing improved algorithms for $D$-optimal design and its dual problem – the minimum volume enclosing ellipsoid problem.

Acknowledgement

The authors are grateful to the three referees for their comprehensive efforts and their suggestions on ways to improve the readability of the paper.

Appendix A Appendix

whose domain we denote by ${\cal D}^{*}$. Since $g(\cdot)$ is a convex function, we know from conjugacy theory that $g(y)=\sup_{t\in D^{*}}\{ty-g^{*}(t)\}$. Therefore (43) becomes

where the second equality above holds whenever the min and the sup operators can be exchanged (which is akin to strong duality). Notice that $\min_{x\in Q}\{\langle c,x\rangle+t\|x\|_{2}^{2}\}$ is a Euclidean projection problem. Therefore the subproblem (9) becomes a $1$-dimensional concave maximization problem if the Euclidean projection problem can be easily solved and one can conveniently form and work with the univariate convex conjugate function $g^{*}(\cdot)$.

A.2 Extension to Composite Optimization

Here we discuss some details of the extension of the ideas and results of this paper to composite optimization as described in Section 3.3, using the definitions $\bar{f}(\cdot):=f(\cdot)+P(\cdot)$, and $\bar{h}(\cdot)=Lh(\cdot)+P(\cdot)$ as defined in Section 3.3. Note that $\bar{f}(\cdot)$ and $\bar{h}(\cdot)$ are not necessarily differentiable on $Q$ since they include the function $P(\cdot)$. However, we can use the equivalent condition from (a-ii) of Proposition 1.1 to define relative smoothness. Let us now show how convergence results for the Primal Gradient Scheme still hold in this more general setting using an extension of the proof of Theorem 3.1.

Let $g_{P}(x)\in\partial P(x)$ be a specific subgradient of $P(\cdot)$ at $x$, and we will use the same subgradient of $P(\cdot)$ at $x$ when constructing a subgradient of $\bar{f}(\cdot)$ and/or $\bar{h}(\cdot)$, namely $g_{\bar{f}}(x):=\nabla f(x)+g_{P}(x)$ and $g_{\bar{h}}(x):=L\nabla h(x)+g_{P}(x)$. Then Algorithm 1 has the following update:

where in the third equality above the term involving $g_{P}(x^{i})$ arising in $\partial\bar{f}(x^{i})$ cancels out the corresponding term involving $g_{P}(x^{i})$ arising in $\partial\bar{h}(x^{i})$ as part of the expansion of $D_{\bar{h}}(x,x^{i})$. There is therefore no actual need to compute $g_{P}(x^{i})\in\partial P(x^{i})$ in the update. Indeed, this update (44) corresponds exactly to the update in the NoLips algorithm (up to the step-size) and the PGA-$\cal B$ algorithm in (up to the step-size) for composite optimization.

The proof of the computational guarantee in Theorem 3.1 can be generalized directly to the composite optimization setting as follows. Let us denote

Notice that $x^{i+1}=\arg\min_{x\in Q}s_{i}(x)$; therefore from the first-order optimality conditions there is a subgradient $g_{s_{i}}(x^{i+1})\in\partial s_{i}(x^{i+1})$ for which $\langle g_{s_{i}}(x^{i+1}),x-x^{i+1}\rangle\geq 0$ for all $x\in Q$. From the additivity property of subgradients, we can write $g_{s_{i}}(x^{i+1})=\nabla f(x^{i})+L\nabla h(x^{i+1})-L\nabla h(x^{i})+\bar{g}$ for some $\bar{g}\in\partial P(x^{i+1})$, and let us assign $g_{P}(x^{i+1}):=\bar{g}=g_{s_{i}}(x^{i+1})-\nabla f(x^{i})-L\nabla h(x^{i+1})+L\nabla h(x^{i})$, which then is used to define the subgradient $g_{\bar{f}}(x^{i+1})$, $g_{\bar{h}}(x^{i+1})$, and the Bregman distance $D_{\bar{h}}(x,x^{i+1})$ in the proof. Recall that the Primal Gradient Scheme does not rely on the choice of subgradient of $P(x^{i+1})$, thus the choice of $g_{P}(x^{i+1})$ is only used in the proof and it is well-defined.

Utilizing the above method for specifying the subgradients of $P(\cdot)$ at each of the iterates $x^{i}$ of the Primal Gradient Scheme, we can prove the following more specialized form of the Three Point Property which we can use in the proof of Theorem 3.1 for the setting composite optimization.

For any $x\in Q$, we have for any $i\geq 0$,

Proof: Notice that $s_{i}(x)-\bar{h}(x)=f(x^{i})+\langle\nabla f(x^{i})-L\nabla h(x^{i}),x-x^{i}\rangle-Lh(x^{i})$ and so is a linear function of $x$, whereby it holds that

where the inequality follows from the choice of $g_{s_{i}}(x^{i+1})$. Rearranging the above and recalling the definition of $s_{i}(x)$ then completes the proof.∎

The proof of Theorem 3.1 in the setting of composite optimization follows directly by replacing $h(\cdot)$, $\nabla h(\cdot)$, $f(\cdot)$ and $\nabla f(\cdot)$ by $\bar{h}(\cdot)$, $g_{\bar{h}}(\cdot)$, $\bar{f}(\cdot)$ and $g_{\bar{f}}(\cdot)$, respectively, and utilizing (45) to deduce the second inequality in (28).

A.3 Criteria for choosing the reference function h​(⋅)ℎ⋅h(\cdot)

One natural question is how can we choose $h(\cdot)$ in order to lower the value of the bound in Theorem 3.1? Let us consider the simple case when $f(\cdot)$ is twice differentiable and is not strongly convex, namely $\mu=0$, and $f(\cdot)$ attains its optimum at some point $x^{*}$. Then the convergence bound (26) can be re-written as:

There is a trade-off between how small the Hessian $\nabla^{2}(Lh-f)(y)$ is and how hard it will be to solve the subproblem (9). If we choose $Lh(\cdot)=f(\cdot)$, the Hessian of the gap function is , but solving the subproblem (9) is as hard as solving the original problem (1). On the other hand, in standard gradient descent we use $h(\cdot)=\tfrac{1}{2}\|\cdot\|_{2}^{2}$ in which case the subproblem (9) can be easily solved, while the Hessian of the gap function can be huge – thus implying a poorer convergence bound. There are a number of ways to try to manage this trade-off. For example, in gradient descent with preconditioning we can use $h(\cdot)=\tfrac{1}{2}\|\cdot\|_{B}^{2}:=\sqrt{\langle\cdot,B\cdot\rangle}$, where $B$ is a computationally-friendly positive definite matrix – typically a diagonal matrix. The criteria for designing $B$ usually involves (i) ensuring that solving equations with $B$ is easy (so that the subproblem (9) can be easily solved), and (ii) $B$ is “close to” the Hessian of $f(\cdot)$ (so that the Hessian of the gap function is small).

References