Minimizing oracle-structured composite functions

Abstract

We consider the problem of minimizing a composite convex function with two different access methods: an oracle, for which we can evaluate the value and gradient, and a structured function, which we access only by solving a convex optimization problem. We are motivated by two associated technological developments. For the oracle, systems like PyTorch or TensorFlow can automatically and efficiently compute gradients, given a computation graph description. For the structured function, systems like CVXPY accept a high level domain specific language description of the problem, and automatically translate it to a standard form for efficient solution. We develop a method that makes minimal assumptions about the two functions, does not require the tuning of algorithm parameters, and works well in practice across a variety of problems. Our algorithm combines a number of well-known ideas, including a low-rank quasi-Newton approximation of curvature, piecewise affine lower bounds from bundle-type methods, and two types of damping to ensure stability. We illustrate the method on stochastic optimization, utility maximization, and risk-averse programming problems, showing that our method is more efficient than standard solvers when the oracle function contains much data.

A Appendix

1.1 A.1 Details of forming $G_k$

We form $G_k$ in (3) by adopting a quasi-Newton update given in Fletcher (2005). The main idea is to divide $G_k$ into two matrices $G_k^{(1)}$ and $G_k^{(2)}$, which are the first $r_1$ and the last $r_2=r-r_1$ columns in $G_k$, respectively, and update them separately into $G_{k+1}^{(1)}$ and $G_{k+1}^{(2)}$. Then $G_{k+1}$ is updated by

$$\begin{aligned} G_{k+1} = \left[ G^{(1)}_{k+1} \quad G^{(2)}_{k+1}\right] . \end{aligned}$$

The detail is as follows. Let $s_k = x^{k+1} - x^k$ and $y_k = \nabla f(x^{k+1}) - \nabla f(x^k)$. From the convexity of f, $s_k^T y_k\ge 0$. Suppose that $s_k^T y_k$ is not too small such that

$$\begin{aligned} s_k^T y_k > \max (\varepsilon _{\mathrm {abs}}, \varepsilon _{\mathrm {rel}}\Vert s_k\Vert _2\Vert y_k\Vert _2), \end{aligned}$$

(39)

where constants $\varepsilon _{\mathrm {abs}}, \varepsilon _{\mathrm {rel}}>0$ are given. Then $r_1$ is chosen as the largest integer in [0, r] such that $G_k^{(1)}$ satisfies

$$\begin{aligned} s_k^Ty_k - \left\| (G_k^{(1)})^Ts_k\right\| _2^2 > \varepsilon _{\mathrm {rel}} \Vert s_k\Vert _2 \left\| y_k - G_k^{(1)}(G_k^{(1)})^Ts_k \right\| _2. \end{aligned}$$

According to (39) the above holds at least for $r_1=0$, in which case $G^{(1)}_k$ degenerates to 0.

Once $r_1$ is obtained, we define $w_k^{(1)} = (G^{(1)}_k)^T s_k$ and $w_k^{(2)} = (G^{(2)}_k)^T s_k$. Then $R_k^{(1)}\in {\mathbf{R}}^{(r_1+1)\times (r_1+1)}$ is the upper triangular factor in the following R-Q decomposition

$$\begin{aligned} R_k^{(1)} Q_k^{(1)} = \left[ \begin{array}{ll} \frac{1}{\sqrt{s_k^T y_k - \Vert w_k^{(1)}\Vert _2^2}} &{} 0_{r_1}^T \\ \frac{-1}{\sqrt{s_k^T y_k - \Vert w_k^{(1)}\Vert _2^2}}w_k^{(1)} &{} I_{r_1} \end{array} \right] \in {\mathbf{R}}^{(r_1+1)\times (r_1+1)}, \end{aligned}$$

and $Q_k^{(2)}\in {\mathbf{R}}^{r_2 \times (r_2 - 1)}$ is a set of orthonormal basis orthogonal to $w_k^{(2)}$. The update is

$$\begin{aligned} G^{(1)}_{k+1} = \left[ y_k \quad G^{(1)}_k \right] R_k^{(1)}, \quad G^{(2)}_{k+1} = G^{(2)}_{k} Q_k^{(2)}. \end{aligned}$$

There are some corner cases. If (39) holds and $r_1 = 0$, then $G_{k+1}^{(1)} = y_k / \sqrt{s_k^T y_k}$. If $r_1 = r-1$ or $r_1 = r$, then $G_{k+1}^{(2)}$ vanishes, and $G_{k+1}$ takes the first r columns of $G_{k+1}^{(1)}$.

In cases where (39) does not hold, if $\Vert w_k^{(2)}\Vert _2 > \varepsilon _{\mathrm {abs}}$, then we can still define $G_{k+1}^{(2)}$ in the same way, and $G_{k+1} = \left[ G^{(2)}_{k+1} \quad 0_n\right] .$ Otherwise, $G_{k+1} = G_k$.

It can be easily checked that by the $G_k$ defined as above, the trace of $H_k$ is uniformly upper bounded in k.

The default values for the parameters are $\varepsilon _{\mathrm {abs}}=10^{-8}$ and $\varepsilon _{\mathrm {rel}}=10^{-3}$.

1.2 A.2 Details of computing an optimal subgradient of g

Here we show how to compute a subgradient $q^{k+1} \in \partial g(x^{k+1/2})$ satisfying the optimality conditions in (8), which implies (10). This, in turn, is important because it allows us to compute the stopping criteria described in sect. 2.6.

Since we know the third term on the right-hand side of (8), it suffices to find an optimal subgradient $l_k^{k+1/2} \in \partial l_k(x^{k+1/2})$, which is easier. We start by rewriting the defining problem for $x^{k+1/2}$ in a more useful form. Putting (4) and (7) together, we see that we can alternatively express $x^{k+1/2}$ as the solution to the convex problem

$$\begin{aligned} \begin{array}{ll} \text{ minimize } &{} z + g(x) + \frac{1}{2}(x-x^k)^T (H_k + \lambda _k I) (x-x^k) \\ \text{ subject } \text{ to } &{} z \ge f(x^i) + \nabla f(x^i)^T (x - x^i), \quad \text {for } i=\max \{0, k-M+1\},\ldots ,k, \end{array} \end{aligned}$$

(40)

with variables x and $z \in {\mathbf{R}}$.

The KKT conditions for problem (40), which are necessary and sufficient for the points $(x^{k+1/2}, z^{k+1/2})$ and $\gamma _i, \; i=\max \{0, k-M+1\},\ldots ,k$, to be primal and dual optimal, are

$$\begin{aligned} z^{k+1/2} \ge f(x^i) + \nabla f(x^i)^T (x^{k+1/2} - x^i), \quad&i=\max \{0, k-M+1\},\ldots ,k; \end{aligned}$$

(41)

$$\begin{aligned} \sum _{i=\max \{0, k-M+1\}}^k \gamma _i = 1, \quad \gamma _i \ge 0, \quad&i=\max \{0, k-M+1\},\ldots ,k; \end{aligned}$$

(42)

$$\begin{aligned} z^{k+1/2} > f(x^i) + \nabla f(x^i)^T (x^{k+1/2} - x^i) \implies \gamma _i = 0, \quad&i\in \max \{0, k-M+1\},\ldots ,k; \end{aligned}$$

(43)

$$\begin{aligned} \partial g(x^{k+1/2}) + (H_k + \lambda _k I) v^k + \sum _{i=\max \{0, k-M+1\}}^k \gamma _i \nabla f(x^i) \ni&0. \end{aligned}$$

(44)

Here we used the definition of $v^k$ to simplify the stationarity condition (44).

Now we claim that

$$\begin{aligned} l_k^{k+1/2} = \sum _{i=\max \{0, k-M+1\}}^k \gamma _i \nabla f(x^i) \in \partial l_k(x^{k+1/2}). \end{aligned}$$

To see this, note that (42) says the $\gamma _i$ are nonnegative and sum to one, while (41) and (43) together imply $\gamma _i$ is positive as long as $\nabla f(x^i)$ is active; this satisfies (9), which says the subdifferential $\partial l_k(x^{k+1/2})$ is the convex hull of the active gradients. Therefore, re-arranging (44) gives

$$\begin{aligned} q^{k+1} = - l_k^{k+1/2} - (H_k + \lambda _k I) v^k \in \partial g(x^{k+1/2}), \end{aligned}$$

which shows (10).

1.3 A.3 Proof that undamped steps occur infinitely often

Assume that $\nabla f$ is Lipschitz continuous with constant L. Also, assume $\mu _{\max }\tau _{\min } > 2L / (1-\alpha )$. We show that for any number of iterations $k_0$, there is some $k \ge k_0$ such that $t_k = 1$. This means that there exists a subsequence $(k_{\ell })_{\ell =1}^\infty$ such that $t_{k_{\ell }} = 1$.

To show the result, we first claim that the line search condition (20) is satisfied as soon as

$$\begin{aligned} t_k \le \frac{1-\alpha }{2L} \lambda _k. \end{aligned}$$

(45)

We prove the claim later. Taking the claim as a given for now, the main result follows by deriving a contradiction. To get a contradiction, suppose there exists some number of iterations $k_0$ such that $t_k < 1$ for each $k \ge k_0$. Then, because $t_k$ is the largest number satisfying $t_k=\beta ^j$ ($j \in \text{ N}_0$) and the line search condition, we get that the line search condition does not hold with $t_k=1$, and thus (45) does not hold with $t_k=1$, meaning that $\lambda _k < 2 L / (1-\alpha )$, for each $k \ge k_0$. But from (23), we have $\mu _k = \min \left\{ \gamma _{\mathrm {inc}}^{k-k_0} \mu _{k_0},\mu _{\max }\right\}$, since we assumed $t_k < 1$ for every $k \ge k_0$. Additionally, from (22), we get $\lambda _k \ge \mu _k \tau _{\min }$. So, we now have two cases. Either we have $\lambda _k \ge \mu _{\max } \tau _{\min } > 2L / (1-\alpha )$, which is a contradiction with $\lambda _k < 2 L / (1-\alpha )$. Or we have $\lambda _k \ge \gamma _{\mathrm {inc}}^{k-k_0} \mu _{k_0}\tau _{\min }$, in which case $\gamma _{\mathrm {inc}}^{k-k_0} \mu _{k_0}\tau _{\min }$ grows exponentially in k; this means we must have $\lambda _k \ge 2 L / (1-\alpha )$, for k sufficiently large, which is again a contradiction. This finishes the proof of the main result.

Now we prove the claim. Observe that

$$\begin{aligned} L t_k^2 \Vert v^k\Vert ^2 \le \frac{1-\alpha }{2} \lambda _k t_k \Vert v^k\Vert ^2 \le \frac{1-\alpha }{2} t_k (v^k)^T (H_k +\lambda _k I) v^k, \end{aligned}$$

(46)

where we used (45) to get the first inequality. We now use the following two facts: $\nabla f$ being L-Lipschitz continuous implies that (i) $\phi _k$ is convex in t, and (ii) $\phi _k^\prime$ is $L \Vert v^k \Vert ^2$-Lipschitz in t. By the first fact (convexity), we have

$$\begin{aligned} \phi _k(t_k) \le \phi _k(0) + \phi _k^\prime (t_k) t_k. \end{aligned}$$

Adding and subtracting $\phi _k^\prime (0)$ gives

$$\begin{aligned} \phi _k(t_k) \le \phi _k(0) + \phi _k^\prime (0) t_k + (\phi _k^\prime (t_k) - \phi _k^\prime (0)) t_k. \end{aligned}$$

The second fact (Lipschitz continuity) yields a bound on the third term on the right-hand side,

$$\begin{aligned} \phi _k(t_k) \le \phi _k(0) + \phi _k^\prime (0) t_k + L t_k^2 \Vert v^k\Vert ^2. \end{aligned}$$

(47)

Finally, using (18) and (46) to bound $\phi _k^\prime (0)$ and $L t_k^2 \Vert v^k \Vert _2^2$ in (47) yields (20), which implies the line search condition (20) is satisfied, as claimed.

We note that the claim above also implies the following lower bound, which is used in Sect. 3.1. Observe that if $t_k$ indeed satisfies the line search condition, then we can express $t_k = \beta ^j$, where j is the smallest integer such that (45) holds (see Sect. 2.4). Now consider two cases. If $1 \le (1-\alpha ) \lambda _k / (2L)$, then we can simply take $j = 0$, so that $t_k = 1$. On the other hand, if $1 > (1-\alpha ) \lambda _k / (2L)$, then a short calculation shows that $j=\lceil \log _{\beta } ((1-\alpha ) \lambda _k / (2L)) \rceil$, and so $j < 1 + \log _{\beta } ((1-\alpha ) \lambda _k / (2L))$, giving $t_k = \beta ^j > \beta (1-\alpha ) \lambda _k / (2L)$. Therefore, to sum up, we have (45) implies that $t_k$ satisfies the inequalities

$$\begin{aligned} t_k > \beta \min \left\{ 1, \frac{1-\alpha }{2L} \lambda _k \right\} \ge \beta \min \left\{ 1,\frac{1-\alpha }{2L} \mu _{\min }\tau _{\min }\right\} , \end{aligned}$$

(48)

where we also used the fact that $\lambda _k \ge \mu _{\min }\tau _{\min }$.

1.4 A.4 Proof that the limited memory piecewise affine minorant is accurate enough

Assume that $\nabla f$ is Lipschitz continuous with constant L. For the rest of the proof, fix any k such that $t_k = 1$. (From Sect. A.3, it is always possible to find at least one such k.) We will show that for any such k, the limited memory piecewise affine minorant (4) satisfies the bound (29); because our choice of k was arbitrary, the required result will then follow.

For any $l_k^{k+1} \in \partial l_k(x^{k+1})$, note that adding and subtracting $\nabla f(x^k)$ in the left-hand side of (29) easily gives

$$\begin{aligned} \Vert \nabla f(x^{k+1}) - l_k^{k+1} \Vert _2 \le \Vert \nabla f(x^{k+1}) - \nabla f(x^k) \Vert _2 + \Vert \nabla f(x^k) - l_k^{k+1} \Vert _2. \end{aligned}$$

(49)

The Lipschitz continuity of $\nabla f$, in turn, immediately gives a bound for the first term on the right-hand side of (49), i.e., we get

$$\begin{aligned} \Vert \nabla f(x^{k+1}) - l_k^{k+1} \Vert _2&\le L \Vert x^{k+1} - x^k \Vert _2 + \Vert \nabla f(x^k) - l_k^{k+1} \Vert _2 \nonumber \\&\lesssim \Vert v^k \Vert _2 + \Vert \nabla f(x^k) - l_k^{k+1} \Vert _2, \end{aligned}$$

(50)

using the definition of $v^k$.

Therefore, we focus on the second term on the right-hand side of (49). For this term, (9) tells us that for any $l_k^{k+1} \in \partial l_k(x^{k+1})$,

$$\begin{aligned} \Vert \nabla f(x^k) - l_k^{k+1} \Vert _2 \le \max _{j=\max \{0,k-M+1\},\ldots ,k} \Vert \nabla f(x^k) - \nabla f(x^j) \Vert _2, \end{aligned}$$

(51)

because the maximum of a convex function over a convex polytope is attained at one of its vertices. The Lipschitz continuity of $\nabla f$ again shows that, for any $j \in \{ \max \{0,k-M+1\}, \ldots , k \}$,

$$\begin{aligned} \Vert \nabla f(x^k) - \nabla f(x^j) \Vert _2&\le L \Vert x^k - x^j \Vert _2 \\&= L \Vert (x^k - x^{k-1}) + (x^{k-1} - x^{k-2}) + \cdots + (x^{j+2} - x^{j+1}) + (x^{j+1} - x^j) \Vert _2 \\&\le L \sum _{\ell =j}^{k-1} \Vert v^\ell \Vert _2 \\&\lesssim \max _{\ell =j,\ldots ,k-1} \Vert v^\ell \Vert _2. \end{aligned}$$

To get the third line, we used the fact that the sum on the second line telescopes, and applied the triangle inequality. To get the fourth line, we used the fact that the average is less than the max. Putting this last inequality together with (51), we see that

$$\begin{aligned} \Vert \nabla f(x^k) - l_k^{k+1} \Vert _2 \lesssim \max _{j=\max \{0,k-M+1\},\ldots ,k} \Vert v^j \Vert _2, \end{aligned}$$

(52)

for any $l_k^{k+1} \in \partial l_k(x^{k+1})$. Combining (52) and (50) gives (29). This completes the proof of the result.