Newton-type methods for non-convex optimization under inexact Hessian information

Abstract

We consider variants of trust-region and adaptive cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under certain condition on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve $\varepsilon$-approximate second-order optimality which have been shown to be tight. Our Hessian approximation condition offers a range of advantages as compared with the prior works and allows for direct construction of the approximate Hessian with a priori guarantees through various techniques, including randomized sampling methods. In this light, we consider the canonical problem of finite-sum minimization, provide appropriate uniform and non-uniform sub-sampling strategies to construct such Hessian approximations, and obtain optimal iteration complexity for the corresponding sub-sampled trust-region and adaptive cubic regularization methods.

Appendices

Appendix A: Intrinsic dimension and improving the sampling complexity (24)

We can still improve the sampling complexity (24) by considering the intrinsic dimension of the matrix $\mathbf {A}^{T} |\mathbf {B}| \mathbf {A}$. Recall that for a SPSD matrix $\mathbf {A}\in {\mathbb {R}}^{d \times d}$, the intrinsic dimension is defined as $t(A) = \text {tr}(\mathbf {A})/\Vert \mathbf {A}\Vert$, where $\text {tr}(\mathbf {A})$ is the trace of $\mathbf {A}$. The intrinsic dimension can be regarded as a measure for the number of dimensions where $\mathbf {A}$ has a significant spectrum. It is easy to see that $1 \le t(\mathbf {A}) \le \text {rank}(\mathbf {A}) \le d$; see [59] for more details. Now let $t = \text {tr}(\mathbf {A}^{T} |\mathbf {B}| \mathbf {A})/\Vert \mathbf {A}^{T} |\mathbf {B}| \mathbf {A}\Vert$ be the intrinsic dimension of the SPSD matrix $\mathbf {A}^{T} |\mathbf {B}| \mathbf {A}$. We have the following improved sampling complexity result:

Lemma 18

(Complexity of non-uniform sampling: intrinsic dimension) The result of Lemma 17 holds with (24) replaced with

$$\begin{aligned} |{\mathscr {S}}| \ge \frac{16 \widehat{K}^2}{3\varepsilon ^2}\log \frac{8t}{\delta }, \end{aligned}$$

(26)

where $t = \text {tr}(\mathbf {A}^{T} |\mathbf {B}| \mathbf {A})/\Vert \mathbf {A}^{T} |\mathbf {B}| \mathbf {A}\Vert \le d$ is the intrinsic dimension of the matrix $\mathbf {A}^{T} |\mathbf {B}| \mathbf {A}$.

Proof

It is easy to see that $\text {Var}(\mathbf {X}) = {\mathbb {E}}(\mathbf {X}^{2}) = \sum _{j=1}^{|{\mathscr {S}}|} {\mathbb {E}}(\mathbf {X}_{j}^{2}) \preceq |{\mathscr {S}}| c \mathbf {A}^{T} |\mathbf {B}| \mathbf {A}$, where $\mathbf {X}$ and c are given in the proof of Lemma 17. For $\mathbf {H}_{j} = \frac{b_{i}}{p_{i}} \mathbf {a}_{i} \mathbf {a}_{i}^{T}$, we have

$$\begin{aligned} \lambda _{\max }(\mathbf {X}_{j})&\le \Vert \mathbf {X}_{j}\Vert = \Vert \frac{b_{i}}{p_{i}} \mathbf {a}_{i} \mathbf {a}_{i}^{T} - \mathbf {A}^{T} \mathbf {B}\mathbf {A}\Vert = \left\| \left( \frac{1-p_{i}}{p_{i}}\right) b_{i} \mathbf {a}_{i} \mathbf {a}_{i}^{T} - \sum _{j \ne i} b_{j} \mathbf {a}_{j} \mathbf {a}_{j}^{T} \right\| \\&\le \left( \frac{1-p_{i}}{p_{i}}\right) |b_{i}| \Vert \mathbf {a}_{i}\Vert ^{2} + \sum _{j \ne i} |b_{j}| \Vert \mathbf {a}_{j}\Vert ^{2} \\&= \left( 1-p_{i}\right) \sum _{i=1}^{n} |b_{j}| \Vert \mathbf {a}_{j}\Vert ^{2} + \sum _{j \ne i} |b_{j}| \Vert \mathbf {a}_{j}\Vert ^{2} \\&= 2 \sum _{j \ne i} |b_{j}| \Vert \mathbf {a}_{j}\Vert ^{2} \le 2 \sum _{i = 1}^{n} |b_{j}| \Vert \mathbf {a}_{j}\Vert ^{2} = 2 c. \end{aligned}$$

Hence, if $\varepsilon |{\mathscr {S}}| \ge \sqrt{|{\mathscr {S}}| c \Vert \mathbf {A}^{T} |\mathbf {B}| \mathbf {A}\Vert } + 2 c/3$, we can apply Matrix Bernstein using the intrinsic dimension [59, Theorem 7.7.1] to get for $\varepsilon \le 1/2$

$$\begin{aligned} \Pr \left( \lambda _{\max }(\mathbf {X}) \ge \varepsilon |{\mathscr {S}}| \right)&\le 4 t \exp \left\{ \frac{-\varepsilon ^2 |{\mathscr {S}}|}{2 c \Vert \mathbf {A}^{T} |\mathbf {B}| \mathbf {A}\Vert + 4 c \varepsilon /3}\right\} \le 4 t \exp \left\{ \frac{-3 \varepsilon ^2 |{\mathscr {S}}|}{16 c^{2}}\right\} . \end{aligned}$$

Applying the same bound for $\mathbf {Y}_{j} = - \mathbf {X}_{j}$ and $\mathbf {Y}= \sum _{j=1}^{s} \mathbf {Y}_{j}$, followed by the union bound, we get the desired result. $\square$

Appendix B: Computation of Approximate Negative Curvature Direction

Throughout our analysis, we assume that, if a sufficiently negative curvature exists, i.e., $\lambda _{\min }(\mathbf {H}) \le -\varepsilon _{H}$ for some $\varepsilon _{H} \in (0,1)$, we can approximately compute the corresponding negative curvature direction vector $\mathbf {u}$, i.e., $\langle \mathbf {u}, \mathbf {H}\mathbf {u}\rangle \le - \nu \varepsilon _{H} \Vert \mathbf {u}\Vert ^{2}$, for some $\nu \in (0,1)$. We note that this can be done efficiently by applying a variety of methods such as Lanczos [38] or shift-and-invert [25] on the SPSD matrix ${\tilde{\mathbf {H}}} = K_{H} - \mathbf {H}$. These methods only employ matrix vector products and, hence, are suitable for large scale problems. More specifically, with any $\kappa \in (0,1)$, these methods using ${\mathscr {O}}(\log (d/\delta )\sqrt{K_{H}/\kappa })$ matrix-vector products and with probability $1-\delta$, yield a vector $\mathbf {u}$ satisfying $K_{H}\Vert \mathbf {u}\Vert ^{2} - \langle \mathbf {u}, \mathbf {H}\mathbf {u}\rangle = \langle \mathbf {u}, {\tilde{\mathbf {H}}} \mathbf {u}\rangle \ge \kappa \lambda _{\min }({\tilde{\mathbf {H}}}) \Vert \mathbf {u}\Vert ^{2} = \kappa (K_{H} - \lambda _{\min }(\mathbf {H})) \Vert \mathbf {u}\Vert ^{2}$. Rearranging, we obtain $\langle \mathbf {u}, \mathbf {H}\mathbf {u}\rangle \le (1-\kappa ) K_{H} \Vert \mathbf {u}\Vert ^{2} + \kappa \lambda _{\min }(\mathbf {H}) \Vert \mathbf {u}\Vert ^{2}$. Setting $1 > \nu = 2\kappa \ge (2 K_{H})/(2 K_{H} + \varepsilon _{H})$, gives $\langle \mathbf {u}, \mathbf {H}\mathbf {u}\rangle \le -\nu \varepsilon _{H} \Vert \mathbf {u}\Vert ^{2}$.