Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization

## Abstract

Abstract We propose the Random Subspace Homogenized Trust Region (RSHTR) method,
which efficiently solves high-dimensional non-convex optimization
problems by identifying descent directions within randomly selected
subspaces. RSHTR provides the strongest theoretical guarantees among random
subspace algorithms for non-convex optimization, achieving an ε 𝜀 \varepsilon italic_ε -approximate first-order stationary point in O ⁢ ( ε − 3 / 2 ) 𝑂 superscript 𝜀 3 2 O(\varepsilon^{-3/2}) italic_O ( italic_ε start_POSTSUPERSCRIPT - 3 / 2 end_POSTSUPERSCRIPT ) iterations and converging locally at a linear
rate. Furthermore, under rank-deficient conditions, RSHTR satisfies ε 𝜀 \varepsilon italic_ε -approximate
second-order necessary condition in O ⁢ ( ε − 3 / 2 ) 𝑂 superscript 𝜀 3 2 O(\varepsilon^{-3/2}) italic_O ( italic_ε start_POSTSUPERSCRIPT - 3 / 2 end_POSTSUPERSCRIPT ) iterations and
exhibits a local quadratic convergence.

## 1 Introduction

We consider unconstrained non-convex optimization problems as follows.

$$ $\displaystyle\min_{x\in\mathbb{R}^{n}}f(x),$ (1.0.1) $$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a possibly non-convex $C^{2}$ function
and bounded below. Non-convex optimization problems are often encountered in
real-world applications, such as training deep neural networks, and they are
often high-dimensional in recent years. Therefore, there is a growing need
for non-convex optimization algorithms with low complexity relative to
dimensionality.

Dimension reduction using random projection, where the function $f$ is restricted
at each iteration to a subspace $P^{\top}\mathbb{R}^{s}$ with the use of a random
matrix $P\in\mathbb{R}^{s\times n}$, is referred to as random subspace
method. It has contributed to improving computational speed in convex optimization
algorithm [, , , , ]
and also in non-convex optimization algorithms [, , , , , , , ].
However, research on random subspace methods for non-convex optimization problems
still lacks theoretical analyses for local convergence and guarantees of second-order
necessary conditions, despite many studies providing theoretical analyses of
global convergence to a first-order stationary point.

Several papers [, ] investigate subspace cubic regularization algorithm.
It can be noticed that [] achieves the current best global convergence
rate for a random subspace method of $O(\varepsilon^{-3/2})$ for a non-convex
function. Although it guarantees the convergence to a second-order
stationary point under some strong assumptions on the condition number and
the rank of the Hessian around that point, it does not discuss local convergence
rates. In contrast, the study by [] proves that a subspace variant
of the Newton method achieves linear local convergence in general and super-linear
local convergence under the assumption that the Hessian at the local optimum
is rank deficient. However, the global convergence rate is limited to $O(\varepsilon^{-2})$, and they only guarantee the convergence to a first-order stationary
point. Other random subspace algorithms for non-convex optimization include []
and []. These algorithms converge to first-order
stationary points with $O(\varepsilon^{-2})$, and the local convergence rates
are not studied.

Trust region methods are known to be fast and stable with excellent theoretical
guarantees. This paper proposes a random subspace method based on a trust-region
method recently developed in []. There are several reasons for this
choice. In [], the theoretical analysis of the trust region method
simplifies the trust region subproblem by treating it as a basic minimum eigenvalue
problem. This approach contrasts with the intricate design of update rules
in the trust region method, and makes the theoretical analysis of dimension reduction
using the random subspace method more concise. Furthermore, the results provided
by [] include a global convergence rate of $O(\varepsilon^{-3/2})$
and local quadratic convergence, ensuring that the output solutions meet
second-order necessary conditions. Consequently, we can anticipate favorable
outcomes regarding theoretical guarantees after dimension reduction.

##### Contribution

We propose a new random subspace method, Random Subspace Homogenized Trust Region
(RSHTR), which efficiently solves high-dimensional non-convex optimization
problems by identifying descent directions within randomly selected
subspaces. RSHTR does not need to compute the projected Hessian,
$P\nabla^{2}f(x)P^{\top}\in\mathbb{R}^{s\times s}$, making our algorithm more
advantageous than other second-order methods numerically. It also has
excellent theoretical properties as in Table 1:
more concretely, 1) convergence to an $\varepsilon$–approximate first-order
stationary point with a global convergence rate of $O(\varepsilon^{-3/2})$
and guarantees local linear convergence,
2) convergence to a second-order stationary point under the assumption that
the Hessian at the point is rank-deficient or under the same assumption as
[].
3) Local quadratic convergence under the assumption that the Hessian is rank-defficient.

**Table 1: Comparison of algorithms. The SOSC column indicates whether the convergence point satisfies the second-order stationary condition $\nabla^{2}f(x_{k})\geq\Omega(-\sqrt{\varepsilon})$. The ${\dagger}$ represents the condition that the Hessian at the local optimum is rank deficient. The ✓✓indicates that in addition to the same assumption with the previous work in ✓, this property holds under another assumption as well.**
| Methods | Comp/iter | Global | Local | SOSC | Implementable |
| --- | --- | --- | --- | --- | --- |
| [] | Quadratic Prog. (QP) | $O(\varepsilon^{-2})$ |  |  | ✓ |
| [] | Subspace gradient | $O(\varepsilon^{-2})$ | linear |  | ✓ |
| [] | Sub. grad. finite diff.<br>$+$orthogonalize | $O(\varepsilon^{-2})$ | linear |  | ✓ |
| [] | Cubic. reg. Trust region QP | $O(\varepsilon^{-3/2})$ |  | ✓ |  |
| [] | Solve eq. | $O(\varepsilon^{-2})$ | superlinear^† |  | ✓ |
| [] | Compute Polling set | $O(\varepsilon^{-2})$ |  |  | ✓ |
| Ours | Min eigenvalue | $O(\varepsilon^{-3/2})$ | quadratic^† | ✓✓ | ✓ |

This rank-deficient assumption includes cases commonly observed in recent machine
learning optimization problems. Indeed, the structure of the Hessian in neural
networks has been studied both theoretically and experimentally, revealing
that it often possesses a low-rank structure
[, , , ].
Thus, our theoretical guarantee is considered important from a practical
perspective.

## 2 Preliminaries

### 2.1 Notations

In this paper, we denote by $f$ the objective function defined in an $n$-dimensional
space. We denote by $s<n$ the dimension of the subspace onto which we project.
We define $I$ as the identity matrix. We call a matrix $P\in\mathbb{R}^{s\times n}$, where each element follows an independent normal distribution
$\mathcal{N}(0,1/s)$, a random Gaussian matrix. We refer to the projection
performed by a random Gaussian matrix as a random projection. Random Gaussian
matrices are sampled independently at each step, and we denote by
$P_{k}\in\mathbb{R}^{s\times n}$ the sampled matrix at iteration $k$. We denote
by $x_{k}$ the current iterate returned by the algorithm at iteration $k$.
We also use $g_{k}$ and $H_{k}$ to denote the gradient vector
$\nabla f(x_{k})$ and the Hessian matrix $\nabla^{2}f(x_{k})$ at the $k$-th
iteration, respectively. The tilde symbol denotes the subspace counterpart
of the corresponding variable. We define by $\tilde{f}_{k}$ the function $f$
restricted to the subspace $P_{k}^{\top}\mathbb{R}^{s}$, that is, $\forall u\in\mathbb{R}^{s}$, $\tilde{f}_{k}(u)=f(x_{k}+P_{k}^{\top}u)$.

$B(x,R)$ is defined as $B(x,R)=\left\{y\in\mathbb{R}^{n}\mid\|y-x\|\leq R\right\}$. We define an $\varepsilon$–approximate first-order stationary
point ($\varepsilon$–FOSP) as a point $x$ that satisfies
$\|\nabla f(x)\|\leq\varepsilon$. We also define an $\varepsilon$–approximate
second-order stationary point ($\varepsilon$–SOSP) as a point $x$ that satisfies
$\lambda_{\min}(\nabla^{2}f(x))\geq-\sqrt{\varepsilon}$.

### 2.2 Random projections

In this section, we discuss two properties of random projections. The first
property is that random projections approximately preserve norms with high
probability. Formally, the following lemma holds:

###### Lemma 2.1 (Lemma 5.3.2 in [ 39 ] ) .

Let
$P\in\mathbb{R}^{s\times n}$ be a random Gaussian matrix and $C$ be
an absolute constant. Then, for any $x\in\mathbb{R}^{n}$ and any
$\xi\in(0,1)$, the following inequality holds with probability at least
$1-2\exp\left(-C\xi^{2}s\right)$:

$$ $\left(1-\xi\right)\left\|x\right\|\leq\left\|Px\right\|\leq\left(1+\xi\right) \left\|x\right\|.$ (2.2.1) $$

The second property is described by the following lemma, which states that
$P^{\top}$ is an approximate isometry with high probability.

###### Lemma 2.2 (Theorem 4.5.1 in [ 39 ] ) .

Let $P\in\mathbb{R}^{s\times n}$ be
a random Gaussian matrix and $\mathcal{C}$ be an absolute constant. The following
inequality holds with probability at least $1-2\exp(-s)$:

$$ $\forall y\in\mathbb{R}^{s},\quad\left(\sqrt{\frac{n}{s}}-\mathcal{C}\right)\|y \|\leq\left\|P^{\top}y\right\|\leq\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right) \|y\|.$ (2.2.2) $$

###### Lemma 2.1 (Lemma 5.3.2 in [ 39 ] ) .

###### Lemma 2.2 (Theorem 4.5.1 in [ 39 ] ) .

## 3 Proposed method

In this section, we introduce Random Subspace Homogenized Trust Region (RSHTR),
which is an algorithm that reduces the dimension of the subproblems solved
in a homogeneous second-order descent method (HSODM) []. Before proposing our method, we briefly describe HSODM
(see Appendix A for the details).

One of the exciting points of HSODM [] is eigenvalue computations that solve trust region subproblems (TRSs). The TRS is a subproblem constructed and
solved in each iteration of the trust region method, but TRS itself is interesting
as a nonconvex optimization problem whose exact solution can be found in polynomial
time. Various solution methods have been proposed for TRS so far, and due to
the improvement in eigenvalue computation, solving the TRS with eigenvalue
computation has recently attracted much attention (see, e.g.,
[, ]). HSODM is a method that incorporates the idea of
homogenization into TRS and solves it by eigenvalue computation in the trust
region method. That is, in HSODM [],
TRSs are solved by eigenvalue computations. Our random subspace method inherits the feature of HSODM.

### 3.1 RSHTR

In RSHTR, we employ HSODM on $\tilde{f}_{k}$, the function restricted to a subspace.
The gradient and Hessian matrix used in RSHTR can therefore be written as

$$ $\displaystyle\tilde{g}_{k}$ $\displaystyle=P_{k}g_{k},$ (3.1.1) $\displaystyle\tilde{H}_{k}$ $\displaystyle=P_{k}H_{k}P_{k}^{\top}.$ (3.1.2) $$

Using these quantities, and based on [], the subproblem we need to
solve at each iteration can be written as:

$$ $\displaystyle\min_{\|[\tilde{v};t]\|\leq 1}\begin{bmatrix}\tilde{v}\\ t\end{bmatrix}^{\top}\begin{bmatrix}\tilde{H}_{k}&\tilde{g}_{k}\\ \tilde{g}_{k}^{\top}&-\delta\\ \end{bmatrix}\begin{bmatrix}\tilde{v}\\ t\end{bmatrix},$ (3.1.3) $$

where $\delta\geq 0$ is a parameter appropriately selected to meet the
desired accuracy. The relation between $\delta$ and the accuracy will be shown
in Section 4. Similar to the subproblem solved
in [], (3.1.3) can also be regarded as a
problem of finding the leftmost eigenvector of a matrix. Hence, (3.1.3)
is solved using eigenvalue solvers, such as the randomized Lanczos algorithm
[]. The random projection decreases the subproblem
dimension from $n+1$ to $s+1$. Therefore, in contrast to HSODM, RSHTR
allows for other eigensolvers beyond the Lanczos method.

Using the solution of (3.1.3) denoted by $[\tilde{v}_{k},t_{k}]$, we can approximate the solution of the full-space subproblem by
$[P_{k}^{\top}\tilde{v}_{k},t_{k}]$. We then define the descent direction $d_{k}$
as(^1^11It might seem to be more natural to describe $|t_{k}|>\nu$ instead of $t_{k}\neq 0$ as in HSODM (see Algorithm 2) for pure random subspace variant of HSODM. However, in the fixed-radius strategy, on which we focus (see (3.1.9)), even if we obtain theoretical guarantees for any $\nu\in(0,1/2)$, the results do not depend on $\nu$. Therefore, for simplicity and clarity, we discuss the case with $\nu\to+0$. Theoretical guarantees regarding a general $\nu$ are provided in Appendix B.)

$$ $\displaystyle d_{k}=\left\{\begin{array}[]{ll}{P_{k}^{\top}\tilde{v}_{k}}/{t_{ k}},&\mathrm{if}\ t_{k}\neq 0\\ P_{k}^{\top}\tilde{v}_{k},&\mathrm{otherwise}\end{array}\right..$ (3.1.6) $$

Similar to HSODM, the algorithm updates the iterate according to the
following rule:

$$ $\displaystyle x_{k+1}=\left\{\begin{array}[]{ll}x_{k}+\eta_{k}d_{k},&\mathrm{ if}\ \mathopen{}\left\|d_{k}\mathclose{}\right\|>\Delta\\ x_{k}+d_{k},&\mathrm{if}\ \mathopen{}\left\|d_{k}\mathclose{}\right\|\leq \Delta\end{array}\right..$ (3.1.9) $$

In RSHTR, the step size selection is fixed to $\eta_{k}=\Delta/\|d_{k}\|$,
and we do not address line search strategy.
However, it should be noted that it is also possible to give theoretical guarantees
when we adopt a usual line search strategy in RSHTR to compute $\eta_{k}$.

If the condition $\|d_{k}\|\leq\Delta$ is satisfied, the algorithm can
either
1) terminate and output $x_{k+1}$, thereby obtaining an
$\varepsilon$–FOSP, or
2)
reset $\delta=0$, fix the update rule to $x_{k+1}=x_{k}+d_{k}$ and continue, thereby achieving local linear convergence.
These steps are shown in Algorithm 1. The procedure
generate_random_gaussian_matrix($s,n$) specifies sampling an $s\times n$ random Gaussian matrix and solve_subproblem
in Line 6 indicates that (3.1.3) is solved by
eigenvalue computation.

Figure: Algorithm 1 RSHTR: Random Subspace Homogenized Trust Region Method

### 3.2 Computational complexity per iteration

We also discuss the computational cost per iteration in Algorithm
1. The main cost involving $P_{k}$ and $P_{k}^{\top}$ is dominated
by the computation of $P_{k}H_{k}P_{k}^{\top}v$ for a vector $v$ in Line 6 of
Algorithm 1. Indeed, we notice that it is not needed to compute
the whole matrix $P_{k}H_{k}P_{k}^{\top}$ in order to solve the subproblem (3.1.3)
by the Lanczos algorithm. This can be done by computing the Hessian-vector product
$\nabla^{2}\tilde{f}_{k}(0)v$ where we recall that $\tilde{f}_{k}(u)=f(x_{k}+P_{k}^{\top}u)$. We know ([, Lemma 2]) that only

$$ $O\left(\min\left(s,C^{\prime}\log(s)\sqrt{{\|\tilde{H_{k}}\|}/{\varepsilon^{ \prime}}}\right)\right)$ $$

iterations of the randomized Lanczos algorithm are necessary to solve (3.1.3)
to an accuracy of $\varepsilon^{\prime}$.

## 4 Theoretical analysis

In this section, we analyze the global and local convergence properties of RSHTR.
First, we show that RSHTR converges, with high probability, to an $\varepsilon$–FOSP in at most $O(\varepsilon^{-3/2})$ iterations. Secondly, we prove that, under some conditions, the algorithm actually converges to an $\varepsilon$–SOSP.
Lastly, we investigate local convergence: we prove local linear convergence and
local quadratic convergence under a rank deficiency condition. Note that the
analysis in this section is inspired by [].

We make the following assumption.

###### Assumption 1 .

$f$ has $L$-Lipschitz continuous gradient and $M$-Lipschitz
continuous Hessian, that is, for all $x,y\in\mathbb{R}^{n}$,

$$ $\displaystyle\|\nabla f(x)-\nabla f(y)\|$ $\displaystyle\leq L\|x-y\|,$ (4.0.1) $\displaystyle\left\|\nabla^{2}f(x)-\nabla^{2}f(y)\right\|$ $\displaystyle\leq M\|x-y\|.$ (4.0.2) $$

To prove the global convergence property, we first state that, when $\|d_{k}\|>\Delta$ holds, the objective function value decreases sufficiently at each iteration.

###### Lemma 4.1 .

Suppose that Assumption 1 holds.
If $\|d_{k}\|>\Delta$, then

$$ $\displaystyle f(x_{k+1})-f(x_{k})\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}} \Delta^{2}\delta+\frac{M}{6}\Delta^{3}$ (4.0.3) $$

with probability at least $1-2\exp(-s)$.

The following lemma shows that if the descent direction once get small enough, norm of the gradient in the subsequent iteration is bounded using $\delta$ and $\Delta$.

###### Lemma 4.2 .

Suppose that Assumption 1
holds. If $\|d_{k}\|\leq\Delta\leq\frac{1}{2\sqrt{2}}$, then we have

$$ $\displaystyle\|g_{k+1}\|\leq\frac{M}{2}\Delta^{2}+\frac{1}{\sqrt{n/s}-\mathcal {C}}\left(2\delta\Delta+16\Delta^{3}\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C} \right)^{2}L+\delta\right)\right)$ (4.0.4) $$

with probability at least
$1-4\exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$.

Next, we show a lower bound on the minimum eigenvalue of the Hessian.

###### Lemma 4.3 .

Suppose that Assumption 1 holds.
If $\|d_{k}\|\leq\Delta\leq\frac{1}{2\sqrt{2}}$, then we have

$$ $\tilde{H}_{k+1}\succeq-\left[8\Delta^{2}\left(\left(\sqrt{\frac{n}{s}}+ \mathcal{C}\right)^{2}L+\delta\right)+\delta+M\Delta\right]I.$ (4.0.5) $$

with probability at least $1-2\exp\left(-\frac{C}{4}s\right)-2\exp\left(-s\right)$.

Although Lemma 4.3 does not directly provide a lower
bound on the eigenvalues of $H_{k+1}$, it is proportional to the bound in Lemma 4.3 under certain conditions. We later discuss the topic in Section 4.2.

###### Assumption 1 .

###### Lemma 4.1 .

###### Lemma 4.2 .

###### Lemma 4.3 .

### 4.1 Global convergence to an ε 𝜀 \varepsilon italic_ε –FOSP

We now prove that our algorithm converges to an $\varepsilon$–FOSP under a
general assumption.

###### Theorem 4.1 (Global convergence to an $\varepsilon$ –FOSP) .

Suppose that Assumption 1
holds. Let

$$ $0<\varepsilon\leq\frac{M^{2}}{8},\quad\delta=\left(\sqrt{\frac{n}{s}}+\mathcal {C}\right)^{2}\sqrt{\varepsilon},\quad\nu\in(0,1/2)\quad\text{and}\quad\Delta= \frac{\sqrt{\varepsilon}}{M}.$ (4.1.1) $$

Then RSHTR converges to an $\varepsilon$–FOSP in at most
$O\left(\varepsilon^{-3/2}\right)$ iterations with probability at
least

$$ $1-4\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+2)\exp\left(-s\right),$ (4.1.2) $$

where
$U_{\varepsilon}:=\lfloor 3M^{2}\left(f(x_{0})-\inf_{x\in\mathbb{R}^{n}}f(x)
\right)\varepsilon^{-3/2}\rfloor+1.$

Theorem 4.1 leads to the following corollary on
the probability bound.

###### Corollary 4.1 .

If $s=\Omega(\log n)$, then the probability bound (4.1.2)
is in the order of $1-o(1)$.

###### Proof.

Let us define $s=c\log n$ for some constant $c>0$. Then (4.1.2)
is rewritten as

$$ $\displaystyle 1-4n^{-Cc/4}-(2U_{\varepsilon}+2)n^{-c}.$ (4.1.3) $$

The negative terms tend to 0 0 as $n$ tends to infinity. The proof is
completed.
∎

###### Remark 1 .

As mentioned in Section 3.1, these results (essentially Lemma 4.1) can also be demonstrated for any $\nu\in(0,1/2)$. Refer to Appendix B for the proof.

###### Theorem 4.1 (Global convergence to an ε 𝜀 \varepsilon italic_ε –FOSP) .

###### Corollary 4.1 .

###### Proof.

###### Remark 1 .

### 4.2 Global convergence to an ε 𝜀 \varepsilon italic_ε –SOSP

The previous section demonstrated that RSHTR globally
converges to an $\varepsilon$–FOSP. In this section, we show that the convergence
point $x^{*}$ is also an $\varepsilon$–SOSP under one of two possible
assumptions about the Hessian at the point, one of which is presented in [].
For clarity and brevity, we move the result under the assumption from []
in Appendix C.5 while focusing on the more practical one in this section.

###### Assumption 2 .

Let $r=\mathrm{rank}(\nabla^{2}f(x^{*}))$,
where $x^{*}$ is the output of RSHTR. We assume that $r\leq s$.

We guarantee that RSHTR converges to an $\varepsilon$–SOSP when the Hessian
at $x^{*}$, denoted by $H^{*}$, in Theorem 4.2,
is rank deficient. Before proceeding to the theorem, we show in Lemma 4.4
that the lower bound of the minimum eigenvalue of $H^{*}$ is proportional to
the lower bound of the minimum eigenvalue of
$\tilde{H}^{*}:=P^{*}H^{*}P^{*\top}$ or non-negative with high probability.

###### Lemma 4.4 .

Let $\bar{C}$ and
$\bar{c}$ be absolute constants. If Assumption 2
holds, then for all $\zeta>0$, the following inequality holds with
probability at least $1-(\bar{C}\zeta)^{s-r+1}-e^{-\bar{c}s}$.

$$ $\lambda_{\mathrm{min}}(H^{*})\geq\frac{1}{\zeta^{2}(\sqrt{s}-\sqrt{r-1})^{2}} \min\left\{\lambda_{\mathrm{min}}\left(P^{*}H^{*}P^{*\top}\right),0\right\}$ (4.2.1) $$

Using this lemma, we can show the following theorem.

###### Theorem 4.2 (Global convergence to an $\varepsilon$ –SOSP under rank deficiency) .

Suppose that Assumptions 1
and 2 hold. Set $\varepsilon,\delta,\nu\text{
and }\Delta$ as in Theorem 4.1, i.e.,

$$ $0<\varepsilon\leq\frac{M^{2}}{8},\quad\delta=\left(\sqrt{\frac{n}{s}}+\mathcal {C}\right)^{2}\sqrt{\varepsilon},\quad\nu\in(0,1/2)\quad\text{and}\quad\Delta= \frac{\sqrt{\varepsilon}}{M}.$ (4.2.2) $$

Then, for some constant $\bar{c}$, RSHTR converges to an $\varepsilon$–SOSP
in at most $O(\varepsilon^{-3/2})$ iterations with probability at least

$$ $\displaystyle 1-6\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+4)\exp\left( -s\right)-\exp\left({-s+r-1}\right)-\exp({-\bar{c}s}),$ (4.2.3) $$

where $U_{\varepsilon}:=\lfloor 3M^{2}\left(f(x_{0})-\inf_{x\in\mathbb{R}^{n}}f\right
)\varepsilon^{-3/2}\rfloor+1$.

###### Assumption 2 .

###### Lemma 4.4 .

###### Theorem 4.2 (Global convergence to an ε 𝜀 \varepsilon italic_ε –SOSP under rank deficiency) .

### 4.3 Local linear convergence

In this section, we discuss the local convergence of RSHTR to a point
$\bar{x}$. Here we consider the case when we continue to run Algorithm
1 after $\|d_{k}\|\leq\Delta$ is satisfied, by setting $\delta=0$ and global_mode $=$ True.
We consider a standard assumption for local convergence analysis.

###### Assumption 3 .

Assume that RSHTR converges to a strict
local optimum $\bar{x}$ such that $\nabla f(\bar{x})=0,\nabla^{2}f(\bar{x})\succ 0$. Formally, there exists $\bar{R}>0$ and $\mu>0$ such that

$$ $\displaystyle\forall x\in B(\bar{x},\bar{R}),\nabla^{2}f(x)\succeq\mu I.$ (4.3.1) $$

We first discuss the special case, $x_{k}=\bar{x}$, which is equivalent to $g_{k}=0$ by convexity from Assumption 3.

###### Lemma 4.5 .

Suppose that Assumption 3
holds. If $g_{k}=0$, then $x_{k+1}=x_{k}$ almost surely.

Lemma 4.5 states that the iterates do not move away
from $\bar{x}$ once it is reached. Since staying at $\bar{x}$ achieves any local
convergence rate, we ignore this case.

Let us now discuss the local convergence.

###### Theorem 4.3 (Local linear convergence) .

Suppose Assumptions 1
and  3 hold. Then, for $k$ large enough

$$ $\displaystyle\left\|x_{k+1}-\bar{x}\right\|_{\bar{H}}\leq\sqrt{1-\frac{\mu}{4 \lambda_{\max}(\bar{H})(\sqrt{n/s}+\mathcal{C})^{2}}}\left\|x_{k}-\bar{x} \right\|_{\bar{H}}$ (4.3.2) $$

with probability at least $1-6\exp\left(-s\right)$.

###### Remark 2 .

As mentioned earlier, the trust region method closely resembles Newton’s method in a sufficiently small neighborhood of the local minimum $\bar{x}$. Consequently, we expect that the impossibility of achieving local superlinear convergence in general can be shown, similar to []. While this analysis is not conducted in this study, it is a potential area for future investigation.

###### Assumption 3 .

###### Lemma 4.5 .

###### Theorem 4.3 (Local linear convergence) .

###### Remark 2 .

### 4.4 Local convergence for strongly convex f 𝑓 f italic_f in its effective
subspace

In this section, we analyze the local convergence of RSHTR when the Hessian of
the objective function is rank-deficient:
$\mathrm{rank}(\nabla^{2}f(x))\leq s$. As in the previous section, we
analyze the scenario where $\delta$ and global_mode are reset to
0 0 and True respectively, and iterations
continue. Note that strong convexity requires a full-rank Hessian and is not
compatible with rank-deficiency. To address this, we consider objective
functions that satisfy strong convexity on a subspace that is effective in
terms of curvature. This allows us to handle both rank deficiency and strong
convexity simultaneously.

###### Assumption 4 .

We suppose that $f$
is a low effective function; that is, we assume that there exists an
orthogonal projection matrix $\Pi\in\mathbb{R}^{n}$ such that:

$$ $\displaystyle f(x)=f(\Pi x).$ (4.4.1) $$

Moreover, we assume that $f$ is strongly convex in its effective
subspace. In other words, $l(y)=f(R^{\top}y)$ is strongly convex, where
the columns of $R$ form orthogonal basis of $\mathrm{Im}(\Pi)$.

To measure the distance within the effective subspace, we introduce the following
semi-norm.

###### Definition 4.1 .

The semi-norm $\|\cdot\|_{\Pi}$ on $\mathbb{R}^{n}$ is defined as

$$ $\|x\|_{\Pi}=\sqrt{\left\|x^{\top}\Pi x\right\|}=\left\|Rx\right\|.$ (4.4.2) $$

###### Theorem 4.4 .

Suppose Assumptions 1
and 4 hold. For
sufficiently large $k$, the following inequality holds with probability at
least $1-4\exp\left(-\frac{C}{4}s\right)$:

$$ $\displaystyle\|x_{k+1}-\bar{x}\|_{\Pi}\leq\frac{4M_{l}\|R\|}{\gamma}\|x_{k}- \bar{x}\|_{\Pi}^{2},$ (4.4.3) $$

where $M_{l}$ is the Lipschitz constant of the Hessian of $l(\cdot)$.

Theorem 4.4 leads to quadratic convergence
of $f(x_{k})-f(\bar{x})$ from the following.

###### Theorem 4.5 .

Suppose Assumptions 1 and
4 hold. For
sufficiently large $k$, the following inequality holds with probability at
least $1-4\exp\left(-\frac{C}{4}s\right)$:

$$ $\displaystyle\left\|f(x_{k+1})-f(\bar{x})\right\|\leq\frac{8L_{l}M_{l}^{2}\|R \|^{2}}{\gamma^{2}\rho^{2}}\|f(x_{k})-f(\bar{x})\|^{2}.$ (4.4.4) $$

where $L_{l}$ and $M_{l}$ are, respectively, the Lipschitz constants of
the gradient and Hessian of $l(\cdot)$.

###### Assumption 4 .

###### Definition 4.1 .

###### Theorem 4.4 .

###### Theorem 4.5 .

## 5 Numerical experiments

In this section, we show numerical experiments for RSHTR. The environment in
which the numerical experiments were performed is as follows:
CPU: Intel(R) Xeon(R) CPU E5-2697 v2 @ 2.70GHz,
GPU: NVIDIA RTX A5000, RAM: 32 GB.

To compare our algorithm to existing methods, we implemented our method,
HSODM [], RSRN [], Gradient Descent (GD), and Random
Subspace Gradient Descent (RSGD) []. We used
backtracking line search in all algorithms to determine the step size.
For all the algorithms utilizing random subspace method, the subspace dimension $s$ is set to $100$.

###### Remark 3 .

As with HSODM [], we can benefit from the acceleration using
the Hessian-vector product in RSHTR. The matrix-vector product required by
RSHTR is $\tilde{v}\to\tilde{H}_{k}\tilde{v}$, and Hessian-vector product
$v\to H_{k}v$ can be utilized by determining the order of operations. Specifically,
by setting the priority of operations to
$\tilde{H}_{k}\tilde{v}=P_{k}(H_{k}(P_{k}^{\top}\tilde{v}))$, the computational complexity
of $\tilde{v}\to\tilde{H}_{k}\tilde{v}$ can be reduced to the maximum
of
$O(sn)$ and the computational complexity of Hessian-vector product.

To check the behavior of our algorithm, we use a rank-deficient variant of
the Rosenbrock function [], logistic regression, softmax
regression, classification with deep neural network, and matrix
factorization, described in Appendix D. We also use
a few datasets for each task. Here, we present only the results for the
Rosenbrock function, softmax regression, classification with deep neural
network, and Matrix factorization experiments.

In the following paragraphs, we denote the number of data points by $N$, the number of classes in the classification task by $K$ and the dimensionality of the data (i.e., the number of features) by $d$. The details of the dataset we used are provided in Appendix D.

###### Remark 3 .

##### Rank-deficient Rosenbrock function

To illustrate the theoretical properties proved in this paper, we first present
the numerical results obtained on a rank-deficient Rosenbrock function

$$ $\min_{x\in\mathbb{R}^{n}}\quad R(A^{\top}Ax),$ (5.0.1) $$

where we have

$$ $\displaystyle A\in\mathbb{R}^{r\times n},\quad r<n,\quad R(x)=\sum_{i=1}^{n-1} 100(x_{i+1}-x_{i}^{2})^{2}+(x_{i}-1)^{2}$ (5.0.2) $$

and the parameters were set as $n=10000$ and $r=50$.
By using a rank $r$ matrix $A^{\top}A$, we make sure that the intrinsic
dimension of the problem, $r$, is much lower than the ambient dimension $n$.
Here, Assumptions 1,2, and
4 are satisfied. Hence,
we expect, by Theorem 4.5,
4.4 and
4.2, that our algorithm shows some
superlinear convergence towards an SOSP. The results of the numerical
experiment are shown in Figure 1. We can see from the results
that our method converges superlinearly towards a solution as expected. Also,
our method can compute an iterate of RSHTR faster than an iterate of the subspace
Newton method (RSRN) (c.f. Section 3.2), which is confirmed
by these results.

##### Logistic regression

$$ $\displaystyle\min_{w\in\mathbb{R}^{d}}$ $\displaystyle\quad-\sum_{i=1}^{N}\log(1+\exp(-\tilde{y}_{i}w^{\top}x_{i}))$ (5.0.3) $$

where $(x_{i},\tilde{y}_{i})\in\mathbb{R}^{d}\times\{-1,1\}$ is the $i$-th data and its label.
The problem dimension $n$ is calculated as $n=d+1$. The results are shown in Figure 1, 1 and 1 for Internet Advertisements dataset [] $(n=1,558)$, news20 dataset [] $(n=10,001)$ and RCV1 dataset [] $(n=10,001)$ respectively.
The figure shows that our method outperforms other methods across all phases.

##### Softmax regression

$$ $\min_{w_{1},\dots,w_{K}\in\mathbb{R}^{K}}-\sum_{i=1}^{N}\sum_{j=1}^{K}\mathbb{ I}[y_{i}=k]\log\left(\frac{\exp(w_{k}^{\top}x_{i})}{\sum_{k=1}^{K}\exp(w_{k}^{ \top}x_{i})}\right),$ $$

where $(x_{i},y_{i})\in\mathbb{R}^{d}\times\{1,\dots,K\}$ is $i$-th data and its label.
The problem dimension $n$ is calculated as $n=(d+1)K$.
The results
are shown in Figure 1 for news20 dataset []
$(n=200,020)$ and in Figure 1 for SCOTUS
dataset [] $(n=130,013)$.
The figure shows that our method outperforms other methods across almost all phases.

##### Matrix factorization (MF)

The matrix factorization problem is formulated as

$$ $\displaystyle\min_{U\in\mathbb{R}^{n_{U}\times k},V\in\mathbb{R}^{k\times n_{V }}}\left\|UV-R\right\|_{F}^{2},$ (5.0.4) $$

where $R\in\mathbb{R}^{n_{U}\times n_{V}}$ and $\left\|\cdot\right\|_{F}^{2}$ denotes the
squared Frobenius norm. The masked version of the problem introduces a mask matrix
$X\in\mathbb{\{}0,1\}^{n_{U}\times n_{V}}$ to handle missing entries in $R$.

$$ $\displaystyle\min_{U\in\mathbb{R}^{n_{U}\times k},V\in\mathbb{R}^{k\times n_{V }}}\left\|(UV-R)\odot X\right\|_{F}^{2},$ (5.0.5) $$

where $X_{ij}=1$ if $R_{ij}$ is not null and $X_{ij}=0$ otherwise and the symbol $\odot$ denotes element-wise
multiplication.
The problem dimension is calculated as $n=(n_{U}+n_{V})k.$
We use MovieLens 100k datasets [] $(n=131,250)$. The results are shown in Figure
1 and
1.
Initially, RSGD decreases the fastest, which is likely due to its advantage of not computing the Hessian. However, our method soon surpasses RSGD.

##### Classification with deep neural networks

Minimizing cross entropy loss of classification task using neural networks is formulated as

$$ $\min_{w\in\mathbb{R}^{n}}-\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{K}\mathbb{I}[y_ {i}=j]\log\left(\frac{\exp(\phi_{w}^{j}(x_{i}))}{\sum_{k=1}^{K}\exp(\phi_{w}^{ k}(x_{i}))}\right)$ (5.0.6) $$

where

- •
$n$ is the number of learnable parameters
- •
$(x_{i},y_{i})\in\mathbb{R}^{d}\times\{1,\dots,K\}$ is $i$-th data and its label.
- •
$\phi_{w}(x_{i})=(\phi_{w}^{1}(x_{i}),\dots,\phi_{w}^{K}(x_{i}))$ represents the neural network’s output, which is the predicted probability distribution over the classes for the input sample $x_{i}$ given the weights $w$.

We used a 16-layer fully connected
neural network as a classifier (see Appendix D.4 for the details of model architecture). The results are shown in Figure 1 for MNIST dataset [] $(n=123,818)$ and Figure 1 for CIFAR-10 dataset [] $(n=416,682)$.

Our method shows an early decrease
in the function value, suggesting the ability to effectively escape from
regions with small gradients by exploiting the Hessian information. Although the norm of the gradient starts small and eventually increases, considering
that the function value continues to decrease even in the final phase, this behavior
likely arises from lack of execution time. We expect the gradient norm to
converge with sufficient runtime.

Figure: (a) Rank-def Rosenbrock (dim=10,000)
Refer to caption: x1.png

In all the experiments presented, our algorithm outperforms existing methods.
This can be attributed to the algorithm’s second-order nature, the homogenization
of the subproblem, and the utilization of random subspace techniques. As discussed
in the introduction, the rank-deficient assumptions (Assumptions 2
and 4) reflect scenarios
commonly encountered in modern machine learning optimization problems. Consequently,
our method is well-suited to applying Theorems
4.5 and
4.2.

## 6 Limitation and future work

One limitation of our paper is that the results about the
convergence to an SOSP, as well as the quadratic local convergence result, are
only valid if the Hessian is rank deficient and if the subspace dimension $s$
is chosen high enough. Also, the parameter $\delta$ is fixed once and for all
at the beginning of the algorithm (and set to 0 0 when $\|d_{k}\|$ is small
enough). In some future work, it would be interesting to develop an adaptive
version of this algorithm where the parameter $\delta>0$ adapts to the current
iterate. Recently, authors of HSODM [] have been vigorously using the
idea of HSODM to develop various variants of HSODM [],
application to stochastic optimization [], and generalization of
the trust-region method []. We would like to investigate
whether our random subspace method can be developed in the same way.

## Appendix A Existing work: HSODM

Homogeneous Second-Order Descent Method (HSODM) proposed by [] is a type of trust region method, which globally converges to an $\varepsilon$–SOSP at a rate of $O(\varepsilon^{-3/2})$ and locally converges at a quadratic rate. The algorithm determines the descent direction based on the solution of the eigenvalue problem obtained by homogenizing the trust region subproblem. The algorithm procedure is described below.

At each iteration, HSODM minimizes the homogenized quadratic model. In other
words, it solves the following subproblem:

$$ $\displaystyle\min_{\|[v;t]\|\leq 1}\begin{bmatrix}v\\ t\end{bmatrix}^{\top}\begin{bmatrix}H_{k}&g_{k}\\ g_{k}^{\top}&-\delta\\ \end{bmatrix}\begin{bmatrix}v\\ t\end{bmatrix}$ (A.0.1) $$

where $\delta\geq 0$ is a parameter appropriately determined according to the required accuracy. (A.0.1) can be regarded as a problem of finding the leftmost eigenvector of a matrix. Hence, the randomized Lanczos algorithm [] can be utilized to solve (A.0.1).
The solution of (A.0.1) is denoted by $[v_{k};t_{k}]$. Using this
solution, HSODM calculates the direction as follows:

$$ $\displaystyle d_{k}^{\text{F}}=\left\{\begin{array}[]{ll}{v_{k}}/{t_{k}},& \mathrm{if}\ \mathopen{}\left|t_{k}\mathclose{}\right|{>\nu}\\ \mathrm{sign}(-g_{k}^{\top}v_{k})v_{k},&\mathrm{if}\ \mathopen{}\left|t_{k} \mathclose{}\right|{\leq\nu}\end{array}\right.$ (A.0.4) $$

where $\nu\in(0,1/2)$ is an arbitrary parameter.

Then, the algorithm updates the iterates according to the following rule:

$$ $\displaystyle x_{k+1}=\left\{\begin{array}[]{ll}x_{k}+\eta_{k}d_{k},&\mathrm{ if}\ \mathopen{}\left\|d_{k}^{\text{F}}\mathclose{}\right\|>\Delta\\ x_{k}+d_{k},&\mathrm{if}\ \mathopen{}\left\|d_{k}^{\text{F}}\mathclose{}\right \|\leq\Delta\end{array}\right.$ (A.0.7) $$

Here, $\eta_{k}$ denotes the step size, and $\Delta\in[0,\sqrt{2}/2]$ is
a parameter set to the appropriate value to achieve the desired accuracy. If
the first condition $\|d_{k}^{\text{F}}\|>\Delta$ is met, the step size
can be either set to $\eta_{k}=\Delta/\|d_{k}^{\text{F}}\|$ or
determined by a line search. If the second condition $\|d_{k}^{\text{F}}\|>\Delta$ is satisfied, this algorithm can either terminate and output
$x_{k+1}$, thereby obtaining an $\varepsilon$–SOSP, or reset both $\delta$ and
$\nu$ to 0 0 and continue, thereby achieving local quadratic convergence. These
steps are shown in Algorithm 2.

Figure: Algorithm 2 Homogeneous Second-Order Descent Method (HSODM) []

## Appendix B Pure random subspace variant of HSODM

Unlike the pure random subspace variant of HSODM, RSHTR excludes the parameter $\nu$ that is present in HSODM. The reason of this exclusion is that our theoretical analysis in the fixed-radius strategy, which we focus on, does not depend on $\nu$. Therefore, for clarity, we discussed it under $\nu\to+0$. In this section, we discuss that similar theoretical guarantees can be provided for any $\nu\in(0,1/2)$ as in the case of $\nu\to+0$.

Figure: Algorithm 3 Pure random subspace variant of HSODM

First, we consider the case where $|t_{k}|<\nu$. In this case, $d_{k}$ is given
by $d_{k}=P_{k}^{\top}\tilde{v}_{k}$.

###### Lemma B.1 .

Suppose that Assumption 1 holds. Let
$\nu\in(0,1/2),d_{k}=P_{k}^{\top}\tilde{v}_{k}$ and
$\eta_{k}=\Delta/\|d_{k}\|$. If $|t_{k}|<\nu,g_{k}\neq 0$ and $\|d_{k}\|>\Delta$ , then we have

$$ $f(x_{k+1})-f(x_{k})\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2} \delta+\frac{M}{6}\Delta^{3}$ (B.0.1) $$

with probability at least $1-2\exp(-s)$.

###### Proof.

By Corollary C.1, we have

$$ $\displaystyle\tilde{v}_{k}^{\top}\tilde{H}_{k}\tilde{v}_{k}$ $\displaystyle=-\theta_{k}\|\tilde{v}_{k}\|^{2}-t_{k}\tilde{v}_{k}^{\top}\tilde {g}_{k}$ (B.0.2) $\displaystyle\tilde{v}_{k}^{\top}\tilde{g}_{k}$ $\displaystyle=t_{k}(\delta-\theta_{k}).$ (B.0.3) $$

Since we almost surely have $\delta<\theta_{k}$ from Lemma C.1,
it follows that

$$ $\displaystyle\mathrm{sign}(-\tilde{g}_{k}^{\top}\tilde{v}_{k})=\mathrm{sign}(t _{k})\quad\mathrm{(a.s.)}$ (B.0.4) $$

Therefore we obtain

$$ $\displaystyle d_{k}^{\top}H_{k}d_{k}$ $\displaystyle=\tilde{v}_{k}^{\top}\tilde{H}_{k}\tilde{v}_{k}\quad(\text{by definition of }d_{k})$ (B.0.5) $\displaystyle=-\theta_{k}\|\tilde{v}_{k}\|^{2}-t_{k}\tilde{v}_{k}^{\top}\tilde {g}_{k}\quad\text{(by \eqref{eq:vHv_sub_nu})}$ (B.0.6) $\displaystyle=-\theta_{k}\|\tilde{v}_{k}\|^{2}-t_{k}^{2}(\delta-\theta)\quad \text{(by \eqref{eq:vg_sub_nu})}$ (B.0.7) $\displaystyle g_{k}^{\top}d_{k}$ $\displaystyle=\mathrm{sign}(-\tilde{g}_{k}^{\top}\tilde{v}_{k})\tilde{g}_{k}^{ \top}\tilde{v}_{k}\quad(\text{by definition of }d_{k})$ (B.0.8) $\displaystyle=\mathrm{sign}(-\tilde{g}_{k}^{\top}\tilde{v}_{k})t_{k}(\delta- \theta_{k})\quad(\text{by \eqref{eq:vg_sub_nu}})$ (B.0.9) $\displaystyle=|t_{k}|(\delta-\theta_{k})\quad(\text{by \eqref{eq:sign_t_k}})$ (B.0.10) $$

Since $\|d_{k}\|>\Delta$, it follows that
$\eta_{k}=\Delta/\|d_{k}\|\in(0,1)$. Thus, we have
$\eta_{k}-\eta_{k}^{2}/2\geq 0$. Hence

$$ $\left(\eta_{k}-\frac{\eta_{k}^{2}}{2}\right)\left(\delta-\theta_{k}\right)\leq 0.$ (B.0.11) $$

Hence, the following inequality holds with probability at least
$1-2\exp(-s)$.

$$ $\displaystyle f(x_{k+1})-f(x_{k})$ $\displaystyle=f(x_{k}+\eta_{k}d_{k})-f(x_{k})$ (B.0.12) $\displaystyle\leq\eta_{k}g_{k}^{\top}d_{k}+\frac{\eta_{k}^{2}}{2}d_{k}^{\top}H _{k}d_{k}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by \eqref{eq: lips_cubic}}\right)$ (B.0.13) $\displaystyle=\eta_{k}|t_{k}|(\delta-\theta_{k})-\frac{\eta_{k}^{2}}{2}\theta_ {k}\|\tilde{v}_{k}\|^{2}-\frac{\eta_{k}^{2}}{2}t_{k}^{2}(\delta-\theta_{k})+ \frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by}~{}\eqref{eq:d_k^TH_kd _k_nu}\text{ and }\eqref{eq:g_k^Td_k_nu}\right)$ (B.0.14) $\displaystyle\leq\eta_{k}t_{k}^{2}(\delta-\theta_{k})-\frac{\eta_{k}^{2}}{2} \theta_{k}\|\tilde{v}_{k}\|^{2}-\frac{\eta_{k}^{2}}{2}t_{k}^{2}(\delta-\theta_ {k})+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by }0\leq|t_{k}|\leq 1\right)$ (B.0.15) $\displaystyle=\left(\eta_{k}-\frac{\eta_{k}^{2}}{2}\right)t_{k}^{2}(\delta- \theta_{k})-\frac{\eta_{k}^{2}}{2}\theta_{k}\|\tilde{v}_{k}\|^{2}+\frac{M}{6} \eta_{k}^{3}\|d_{k}\|^{3}$ (B.0.16) $\displaystyle\leq-\frac{\eta_{k}^{2}}{2}\theta_{k}\left\|\tilde{v}_{k}\right\| ^{2}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\text{(by \eqref{eq:eta_k-eta_k^ 2/2})}$ (B.0.17) $\displaystyle\leq-\frac{\eta_{k}^{2}}{2}\theta_{k}\cdot\frac{1}{(\sqrt{n/s}+ \mathcal{C})^{2}}\|d_{k}\|^{2}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left( \text{by}~{}\text{Lemma~{}\ref{lem:approximate_isometry}}\right)$ (B.0.18) $\displaystyle\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta+ \frac{M}{6}\Delta^{3}\quad\left(\text{by}~{}\eqref{eq:delta_le_theta_k}\text{ and }\eta_{k}=\Delta/\|d_{k}\|\right)$ (B.0.19) $$

This completes the proof.
∎

Next, we consider the case where $|t_{k}|\geq\nu$. In this case, $d_{k}$ is
given by $d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k}$. Since $|t_{k}|\geq\nu$ implies $t_{k}\neq 0$,
we have the following result by using the same argument as in the proof of Lemma C.4.

###### Lemma B.2 .

Suppose Assumption 1
holds. Let $d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k}$. If $t_{k}\neq 0,\|d_{k}\|>\Delta$ and $\eta_{k}=\Delta/\|d_{k}\|$, then

$$ $f(x_{k+1})-f(x_{k})\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2} \delta+\frac{M}{6}\Delta^{3}$ (B.0.20) $$

holds with probability at least $1-2\exp(-s)$.

By Lemmas B.1 and
B.2, we can state that, when
$\|d_{k}\|>\Delta$ holds, the objective function value decreases by at least
$\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta-\frac{M}{6}\Delta^{3}$ at each iteration, with probability at least $1-2\exp(-s)$.

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

## Appendix C Proofs for theoretical analysis

### C.1 Preparation of the theoretical analysis

We recall the fundamental property in probability theory. For any events
$E_{1}$ and $E_{2}$, we have

$$ $\displaystyle\mathrm{Pr}\left[E_{1}\cap E_{2}\right]\geq 1-\left(1-\mathrm{Pr} \left[E_{1}\right]\right)-\left(1-\mathrm{Pr}\left[E_{2}\right]\right).$ (C.1.1) $$

This is used throughout this paper without further explicit mention. The
optimality conditions of the dimension-reduced subproblem (3.1.3)
are given by the following statements: there exists a non-negative random
variable $\theta_{k}$ such that

$$ $\displaystyle\left(\tilde{F}_{k}+\theta_{k}I\right)\left[\begin{array}[]{l} \tilde{v}_{k}\\ t_{k}\end{array}\right]=0$ (C.1.4) $\displaystyle\tilde{F}_{k}+\theta_{k}I\succeq 0$ (C.1.5) $\displaystyle\theta_{k}\left(\left\|\left[\tilde{v}_{k};t_{k}\right]\right\|-1 \right)=0,$ (C.1.6) $$

where

$$ $\displaystyle\tilde{F}_{k}=\left[\begin{array}[]{cc}\tilde{H}_{k}&\tilde{g}_{k }\\ \tilde{g}_{k}^{\top}&-\delta\end{array}\right].$ (C.1.9) $$

It immediately follows from (C.1.5) that

$$ $\displaystyle\lambda_{\min}(\tilde{F}_{k})\geq-\theta_{k}.$ (C.1.10) $$

We also obtain from (C.1.5)

$$ $\displaystyle\delta\leq\theta_{k}.$ (C.1.11) $$

by considering the direction $\left[0,\cdots,0,1\right]^{\top}$.

We directly deduce the following result from (C.1.4).

###### Corollary C.1 .

(C.1.4) implies the
following equations

$$ $\displaystyle\left(\tilde{H}_{k}+\theta_{k}I\right)\tilde{v}_{k}$ $\displaystyle=-t_{k}\tilde{g}_{k}$ (C.1.12) $\displaystyle\tilde{g}_{k}^{\top}\tilde{v}_{k}$ $\displaystyle=t_{k}\left(\delta-\theta_{k}\right).$ (C.1.13) $$

Furthermore, if $t_{k}=0$, then

$$ $\displaystyle\left(\tilde{H}_{k}+\theta_{k}I\right)\tilde{v}_{k}=0$ (C.1.14) $\displaystyle\tilde{g}_{k}^{\top}\tilde{v}_{k}=0$ (C.1.15) $$

hold. If $t_{k}\neq 0$, then

$$ $\displaystyle\tilde{g}_{k}^{\top}\frac{\tilde{v}_{k}}{t_{k}}=\delta-\theta_{k}$ (C.1.16) $\displaystyle\left(\tilde{H}_{k}+\theta_{k}I\right)\frac{\tilde{v}_{k}}{t_{k}} =-\tilde{g}_{k}$ (C.1.17) $$

hold.

We also obtain a slightly stronger inequality $\delta<\theta_{k}$ under an
additional condition.

###### Lemma C.1 .

If $g_{k}\neq 0$, then $\delta<\theta_{k}$
holds almost surely.

###### Proof.

We first prove the following inequality.

$$ $\displaystyle\lambda_{\mathrm{min}}(\tilde{F}_{k})<-\delta$ (C.1.18) $$

To prove this inequality, it suffices to show that $\tilde{F}_{k}+\delta I$ has negative curvature. Let us define

$$ $\displaystyle f(\eta,t)$ $\displaystyle=\begin{bmatrix}-\eta\tilde{g}_{k}\\ t\end{bmatrix}^{\top}\left(\tilde{F}_{k}+\delta I\right)\begin{bmatrix}-\eta \tilde{g}_{k}\\ t\end{bmatrix}$ (C.1.19) $\displaystyle=\eta^{2}\tilde{g}_{k}^{\top}(\tilde{H}_{k}+\delta I)\tilde{g}_{k }-2\eta t\left\|\tilde{g}_{k}\right\|^{2}.$ (C.1.20) $$

Then for any fixed $t>0$, we have

$$ $f(0,t)=0,\quad\frac{\partial f(0,t)}{\partial\eta}=-2t\|\tilde{g}_{k}\|^{2}$ (C.1.21) $$

Since $g_{k}\neq 0$, we almost surely have $\|\tilde{g}_{k}\|\neq 0$, which
implies $\frac{\partial f(0,t)}{\partial\eta}<0$. Thus, for sufficiently
small $\eta>0$, we have that $f(\eta,t)<0$. This shows that $\tilde{F}_{k}+\delta I$ has negative curvature. Finally, by combining (C.1.10) and (C.1.18),
the proof is completed.
∎

We recall the following lemma from [].

###### Lemma C.2 .

Suppose Assumption 1 holds. Then for
any $x,y\in\mathbb{R}^{n}$, we have

$$ $\displaystyle|f(y)-f(x)-\nabla f(x)^{\top}(y-x)|\leq\frac{L}{2}\|y-x\|^{2}$ (C.1.22) $\displaystyle\|\nabla f(y)-\nabla f(x)-\nabla^{2}f(x)(y-x)\|\leq\frac{M}{2}\|y -x\|^{2}$ (C.1.23) $\displaystyle\left|f(y)-f(x)-\nabla f(x)^{\top}(y-x)-\frac{1}{2}(y-x)^{\top} \nabla^{2}f(x)(y-x)\right|\leq\frac{M}{6}\|y-x\|^{3}$ (C.1.24) $$

###### Corollary C.1 .

###### Lemma C.1 .

###### Proof.

###### Lemma C.2 .

### C.2 Analysis of the case where ‖ d k ‖ > Δ norm subscript 𝑑 𝑘 Δ \|d_{k}\|>\Delta ∥ italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ∥ > roman_Δ

Let us consider the case where $\|d_{k}\|>\Delta$ and evaluate the amount of decrease of the objective function value at each iteration (Lemmas C.3 and C.4, leading to Lemma 4.1). Note that, under $\|d_{k}\|>\Delta$, the update rule is given by

$$ $\displaystyle x_{k+1}=x_{k}+\eta_{k}d_{k}$ (C.2.1) $\displaystyle\eta_{k}=\Delta/\|d_{k}\|.$ (C.2.2) $$

First, we consider the case where $t_{k}=0$. In this case, $d_{k}$ is given
by $d_{k}=P_{k}^{\top}\tilde{v}_{k}$.

###### Lemma C.3 .

Suppose that Assumption 1 holds. Let
$d_{k}=P_{k}^{\top}\tilde{v}_{k}$ and
$\eta_{k}=\Delta/\|d_{k}\|$. If $t_{k}=0,g_{k}\neq 0$ and $\|d_{k}\|>\Delta$ , then we have

$$ $f(x_{k+1})-f(x_{k})\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2} \delta+\frac{M}{6}\Delta^{3}$ (C.2.3) $$

with probability at least $1-2\exp(-s)$.

###### Proof.

By $t_{k}=0$ and Corollary C.1, we have

$$ $\displaystyle\tilde{v}_{k}^{\top}\tilde{H}_{k}\tilde{v}_{k}$ $\displaystyle=-\theta_{k}\|\tilde{v}_{k}\|^{2}$ (C.2.4) $\displaystyle\tilde{v}_{k}^{\top}\tilde{g}_{k}$ $\displaystyle=0.$ (C.2.5) $$

Therefore we obtain

$$ $\displaystyle d_{k}^{\top}H_{k}d_{k}$ $\displaystyle=\tilde{v}_{k}^{\top}\tilde{H}_{k}\tilde{v}_{k}\quad(\text{by definition of }d_{k})$ (C.2.6) $\displaystyle=-\theta_{k}\|\tilde{v}_{k}\|^{2}\quad\text{(by \eqref{eq:vHv_sub })}$ (C.2.7) $\displaystyle g_{k}^{\top}d_{k}$ $\displaystyle=\mathrm{sign}(-\tilde{g}_{k}^{\top}\tilde{v}_{k})\tilde{g}_{k}^{ \top}\tilde{v}_{k}\quad(\text{by definition of }d_{k})$ (C.2.8) $\displaystyle=0\quad(\text{by \eqref{eq:vg_sub}})$ (C.2.9) $$

Hence, the following inequality holds with probability at least
$1-2\exp(-s)$.

$$ $\displaystyle f(x_{k+1})-f(x_{k})$ $\displaystyle=f(x_{k}+\eta_{k}d_{k})-f(x_{k})$ (C.2.10) $\displaystyle\leq\eta_{k}g_{k}^{\top}d_{k}+\frac{\eta_{k}^{2}}{2}d_{k}^{\top}H _{k}d_{k}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by \eqref{eq: lips_cubic}}\right)$ (C.2.11) $\displaystyle=0-\frac{\eta_{k}^{2}}{2}\theta_{k}\|\tilde{v}_{k}\|^{2}+\frac{M} {6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by}~{}\eqref{eq:d_k^TH_kd_k}\text { and }\eqref{eq:g_k^Td_k}\right)$ (C.2.12) $\displaystyle\leq-\frac{\eta_{k}^{2}}{2}\theta_{k}\cdot\frac{1}{(\sqrt{n/s}+ \mathcal{C})^{2}}\|d_{k}\|^{2}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left( \text{by}~{}\text{Lemma~{}\ref{lem:approximate_isometry}}\right)$ (C.2.13) $\displaystyle\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta+ \frac{M}{6}\Delta^{3}\quad\left(\text{by}~{}\eqref{eq:delta_le_theta_k}\text{ and }\eta_{k}=\Delta/\|d_{k}\|\right)$ (C.2.14) $$

This completes the proof.
∎

Next, we consider the case where $t_{k}\neq 0$. In this case, $d_{k}$ is
given by $d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k}$.

###### Lemma C.4 .

Suppose Assumption 1
holds. Let $d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k}$. If $t_{k}\neq 0,\|d_{k}\|>\Delta$ and $\eta_{k}=\Delta/\|d_{k}\|$, then

$$ $f(x_{k+1})-f(x_{k})\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2} \delta+\frac{M}{6}\Delta^{3}$ (C.2.15) $$

holds with probability at least $1-2\exp(-s)$.

###### Proof.

Since $t_{k}\neq 0$, we obtain from (C.1.17)

$$ $\displaystyle\frac{\tilde{v}_{k}^{\top}}{t_{k}}\tilde{H}_{k}\frac{\tilde{v}_{k }}{t_{k}}$ $\displaystyle=-\theta_{k}\frac{\|\tilde{v}_{k}\|^{2}}{t_{k}^{2}}-\frac{\tilde{ g}_{k}^{\top}\tilde{v}_{k}}{t_{k}}.$ (C.2.16) $$

Therefore, it follows that

$$ $\displaystyle d_{k}^{\top}H_{k}d_{k}$ $\displaystyle=\frac{\tilde{v}_{k}^{\top}}{t_{k}}\tilde{H}_{k}\frac{\tilde{v}_{ k}}{t_{k}}$ (C.2.17) $\displaystyle=-\theta_{k}\frac{\|\tilde{v}_{k}\|^{2}}{t_{k}^{2}}-\frac{\tilde{ g}_{k}^{\top}\tilde{v}_{k}}{t_{k}}\quad\left(\text{by}~{}\eqref{eq:d_k^TH_kd_k _nonzero_t}\right)$ (C.2.18) $\displaystyle=-\theta_{k}\frac{\|\tilde{v}_{k}\|^{2}}{t_{k}^{2}}-g_{k}^{\top}d _{k}\quad\left(\text{by definition of }d_{k}\right)$ (C.2.19) $\displaystyle g_{k}^{\top}d_{k}$ $\displaystyle=\delta-\theta_{k}\quad\left(\text{by}~{}\eqref{eq:2.1.t_nonzero_ delta_theta}\right)$ (C.2.20) $\displaystyle\leq 0.\quad\left(\text{by}~{}\eqref{eq:delta_le_theta_k}\right)$ (C.2.21) $$

Since $\eta_{k}=\Delta/\|d_{k}\|\in(0,1)$, we have $\eta_{k}-\eta_{k}^{2}/2\geq 0$. Thus we obtain

$$ $\left(\eta_{k}-\frac{\eta_{k}^{2}}{2}\right)g_{k}^{\top}d_{k}\leq 0.\quad\left (\text{by}~{}\eqref{eq:g_k^Td_k_nonzero_t}\right)$ (C.2.22) $$

Therefore, the following inequality holds with probability at least $1-2\exp(-s)$.

$$ $\displaystyle f(x_{k+1})-f(x_{k})$ $\displaystyle=f(x_{k}+\eta_{k}d_{k})-f(x_{k})$ (C.2.23) $\displaystyle\leq\eta_{k}g_{k}^{\top}d_{k}+\frac{\eta_{k}^{2}}{2}d_{k}^{\top}H _{k}d_{k}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by \eqref{eq: lips_cubic}}\right)$ (C.2.24) $\displaystyle=\eta_{k}g_{k}^{\top}d_{k}+\frac{\eta_{k}^{2}}{2}\left(-\theta_{k }\frac{\|\tilde{v}_{k}\|^{2}}{t_{k}^{2}}-g_{k}^{\top}d_{k}\right)+\frac{M}{6} \eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by}~{}\eqref{eq:d_k^TH_kd_k_nonzero_ t_2}\right)$ (C.2.25) $\displaystyle=\left(\eta_{k}-\frac{\eta_{k}^{2}}{2}\right)g_{k}^{\top}d_{k}- \frac{\eta_{k}^{2}}{2}\theta_{k}\frac{\|\tilde{v}_{k}\|^{2}}{t_{k}^{2}}+\frac{ M}{6}\eta_{k}^{3}\|d_{k}\|^{3}$ (C.2.26) $\displaystyle\leq-\frac{\eta_{k}^{2}}{2}\theta_{k}\frac{\|\tilde{v}_{k}\|^{2}} {t_{k}^{2}}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left(\text{by}~{}\eqref{ eq:eta_k-eta_k^2/2_nonzero_t}\right)$ (C.2.27) $\displaystyle\leq-\frac{\eta_{k}^{2}}{2}\theta_{k}\cdot\frac{1}{(\sqrt{n/s}+ \mathcal{C})^{2}}\|d_{k}\|^{2}+\frac{M}{6}\eta_{k}^{3}\|d_{k}\|^{3}\quad\left( \text{by~{}Lemma~{}\ref{lem:approximate_isometry}}\right)$ (C.2.28) $\displaystyle\leq-\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta+ \frac{M}{6}\Delta^{3}\quad\left(\text{by~{}}\eqref{eq:delta_le_theta_k}\text{ and }\eta_{k}=\Delta/\|d_{k}\|\right)$ (C.2.29) $$

This completes the proof.
∎

By Lemmas C.3 and
C.4, we can state that, when
$\|d_{k}\|>\Delta$ holds, the objective function value decreases by at least
$\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta-\frac{M}{6}\Delta^{3}$ at each iteration, with probability at least $1-2\exp(-s)$.
This proves Lemma 4.1.

###### Lemma C.3 .

###### Proof.

###### Lemma C.4 .

###### Proof.

### C.3 Analysis of the case where ‖ d k ‖ ≤ Δ norm subscript 𝑑 𝑘 Δ \|d_{k}\|\leq\Delta ∥ italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ∥ ≤ roman_Δ

Now we consider the case where RSHTR satisfies $\|d_{k}\|\leq\Delta$ at the
$k$-th iteration and outputs $x_{k+1}=x_{k}+d_{k}$. To investigate the
property of $x_{k+1}$, we analyze $\|g_{k+1}\|$ and $\lambda_{\min}(\tilde{H}_{k+1})$.

We first derive an upper and lower bound on the eigenvalues of $\nabla^{2}f(x)$.

###### Lemma C.5 .

Suppose Assumption 1 holds.
Then for all $x\in\mathbb{R}^{n}$,

$$ $\displaystyle\lambda_{\mathrm{min}}(\nabla^{2}f(x))\geq-L$ (C.3.1) $\displaystyle\lambda_{\mathrm{max}}(\nabla^{2}f(x))\leq L$ (C.3.2) $$

holds.

###### Proof.

Let $v$ be a unit eigenvector corresponding to the smallest eigenvalue.
By definition of $\nabla^{2}f(x)$, we have

$$ $\nabla^{2}f(x)v=\lim_{h\to 0}\frac{\nabla f(x+hv)-\nabla f(x)}{h}.$ (C.3.3) $$

To bound the right side, we use the $L$-Lipschitz property. We obtain

$$ $\displaystyle\|\nabla^{2}f(x)v\|$ $\displaystyle\leq\lim_{h\to 0}\frac{\|\nabla f(x+hv)-\nabla f(x)\|}{|h|}$ (C.3.4) $\displaystyle\leq\frac{L\|hv\|}{|h|}=L\|v\|.$ (C.3.5) $$

Finally, since
$\|\nabla^{2}f(x)v\|=|\lambda_{\mathrm{min}}(\nabla^{2}f(x))|\|v\|$,
we obtain $\lambda_{\mathrm{min}}(\nabla^{2}f(x))\geq-L$. The proof of
the second inequality is similar.
∎

Next, we derive upper and lower bounds on the eigenvalues of $\tilde{H}_{k}$.

###### Lemma C.6 .

Suppose Assumption 1 holds. Then we have

$$ $\displaystyle\lambda_{\mathrm{min}}\left(\tilde{H}_{k}\right)\geq-\left(\sqrt{ \frac{n}{s}}+\mathcal{C}\right)^{2}L$ (C.3.6) $\displaystyle\lambda_{\mathrm{max}}\left(\tilde{H}_{k}\right)\leq\left(\sqrt{ \frac{n}{s}}+\mathcal{C}\right)^{2}L.$ (C.3.7) $$

with probability at least $1-2\exp(-s)$.

###### Proof.

Let us consider the first inequality. Let
$E=\left\{\tilde{x}\in\mathbb{R}^{s}\;\middle|\;\tilde{x}^{\top}\tilde{H}_{k}
\tilde{x}<0\right\}$. Then we have:

$$ $\displaystyle\lambda_{\mathrm{min}}\left(\tilde{H}_{k}\right)$ $\displaystyle\geq\min\left\{0,\min_{\tilde{x}\in E}\frac{\tilde{x}^{\top} \tilde{H}_{k}\tilde{x}}{\|\tilde{x}\|^{2}}\right\}.$ (C.3.8) $$

By Lemma 2.2, we have

$$ $\displaystyle\|P_{k}^{\top}\tilde{x}\|^{2}\leq\left(\sqrt{\frac{n}{s}}+ \mathcal{C}\right)^{2}\|\tilde{x}\|^{2}$ (C.3.9) $$

with probability at least $1-2\exp(-s)$. Therefore, we obtain

$$ $\displaystyle\min\left\{0,\min_{\tilde{x}\in E}\frac{\tilde{x}^{\top}\tilde{H} _{k}\tilde{x}}{\|\tilde{x}\|^{2}}\right\}$ $\displaystyle\geq\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}\min\left\{0, \min_{\tilde{x}\in E}\frac{\tilde{x}^{\top}P_{k}H_{k}P_{k}^{\top}\tilde{x}}{\| P_{k}^{\top}\tilde{x}\|^{2}}\right\}\quad(\text{by \eqref{eq:Px_le_x}})$ (C.3.10) $\displaystyle\geq\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}\min\left\{0, \min_{x\in\mathbb{R}^{n}}\frac{x^{\top}H_{k}x}{\|x\|^{2}}\right\}\quad(\text{ by}~{}\mathrm{Im}(P_{k}^{\top})\subset\mathbb{R}^{n})$ (C.3.11) $\displaystyle=\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}\min\left\{0, \lambda_{\min}\left(H_{k}\right)\right\}$ (C.3.12) $\displaystyle\geq-\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}L.\quad(\text {by \eqref{eq:lambda_min_H_lower_bound}})$ (C.3.13) $$

Hence, by (C.3.8), the first inequality (C.3.6)
holds with probability at least $1-2\exp(-s)$. The proof of (C.3.7)
is similar.
∎

Using this lemma, we can derive an upper bound for $\|g_{k}\|$. It should be
noted that this is an auxiliary lemma and not an upper bound for
$\|g_{k+1}\|$, the norm of the gradient at the output of RSHTR.

###### Lemma C.7 .

Suppose that Assumption 1 holds. If
$\|d_{k}\|\leq\Delta\leq\frac{1}{2\sqrt{2}}$, then

$$ $\|g_{k}\|\leq 8\Delta\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}L+ \delta\right).$ (C.3.14) $$

with probability at least $1-2\exp\left(-\frac{C}{4}s\right)-2\exp(-s)$.

###### Proof.

The proof for the case of $g_{k}=0$ is trivial. Thus, in the following argument,
we suppose that $g_{k}\neq 0$. By $g_{k}\neq 0$, we almost surely have
$\theta_{k}-\delta>0$ by Lemma C.1. Applying the
Schur complement property to (C.1.5), we obtain

$$ $\tilde{H}_{k}+\theta_{k}I_{s}-\frac{1}{\theta_{k}-\delta}\tilde{g}_{k}\tilde{g }_{k}^{\top}\succeq 0.$ (C.3.15) $$

Hence,

$$ $\displaystyle\frac{\theta_{k}-\delta}{\|g_{k}\|^{2}}\tilde{g}_{k}^{\top}\left( \tilde{H}_{k}+\theta_{k}I_{s}-\frac{1}{\theta_{k}-\delta}\tilde{g}_{k}\tilde{g }_{k}^{\top}\right)\tilde{g}_{k}\geq 0.$ (C.3.16) $$

The inequality can be rewritten as

$$ $\displaystyle(\theta_{k}-\delta)\frac{\tilde{g}_{k}^{\top}\tilde{H}_{k}\tilde{ g}_{k}}{\|g_{k}\|^{2}}+(\theta_{k}-\delta)\theta_{k}\frac{\|\tilde{g}_{k}\|^{2 }}{\|g_{k}\|^{2}}-\frac{\|\tilde{g}_{k}\|^{4}}{\|g_{k}\|^{2}}\geq 0.$ (C.3.17) $$

By multiplying $\|g_{k}\|^{2}/\|\tilde{g}_{k}\|^{2}$ and applying
$\theta_{k}=(\theta_{k}-\delta)+\delta$, it follows that

$$ $(\theta_{k}-\delta)^{2}+(\theta_{k}-\delta)\left(\frac{\tilde{g}_{k}^{\top} \tilde{H}_{k}\tilde{g}_{k}}{\|\tilde{g}_{k}\|^{2}}+\delta\right)-\|\tilde{g}_{ k}\|^{2}\geq 0.$ (C.3.18) $$

Moreover, by (C.1.16) in Corollary C.1,
we deduce

$$ $\theta_{k}-\delta=-g_{k}^{\top}d_{k}\leq\|g_{k}\|\|d_{k}\|\leq\Delta\|g_{k}\|.$ (C.3.19) $$

Let us define

$$ $h(t)=t^{2}+\left(\frac{\tilde{g}_{k}^{\top}\tilde{H}_{k}\tilde{g}_{k}}{\| \tilde{g}_{k}\|^{2}}+\delta\right)t-{\|\tilde{g}_{k}\|^{2}}.$ (C.3.20) $$

Since we have $h(0)=-\|\tilde{g}_{k}\|^{2}<0$ almost surely by
$g_{k}\neq 0$, $h(t)=0$ has a positive root. Let us denote it by
$t_{2}$. From $\theta_{k}-\delta>0$ and $h(\theta_{k}-\delta)\geq 0$
due to (C.3.18), we obtain $t_{2}\leq\theta_{k}-\delta$.
Since $h(t)$ is monotonically increasing in $t_{2}\leq t$, by (C.3.19),
we have

$$ $h(\Delta\|g_{k}\|)=\Delta^{2}\|g_{k}\|^{2}+\left(\frac{\tilde{g}_{k}^{\top} \tilde{H}_{k}\tilde{g}_{k}}{\|\tilde{g}_{k}\|^{2}}+\delta\right)\Delta\|g_{k} \|-{\|\tilde{g}_{k}\|^{2}}\geq 0.$ (C.3.21) $$

By Lemma 2.1, we have $\frac{1}{2}\|g_{k}\|\leq\|\tilde{g}_{k}\|$ with probability at least $1-2\exp\left(-\frac{C}{4}s\right)$.
It follows that

$$ $\Delta^{2}\|g_{k}\|^{2}+\left(\frac{\tilde{g}_{k}^{\top}\tilde{H}_{k}\tilde{g} _{k}}{\|\tilde{g}_{k}\|^{2}}+\delta\right)\Delta\|g_{k}\|-\frac{\|g_{k}\|^{2}} {4}\geq 0.$ (C.3.22) $$

This implies

$$ $\left(\frac{1}{4}-\Delta^{2}\right)\|g_{k}\|\leq\left(\frac{\tilde{g}_{k}^{ \top}\tilde{H}_{k}\tilde{g}_{k}}{\|\tilde{g}_{k}\|^{2}}+\delta\right)\Delta$ (C.3.23) $$

Since we have $\Delta\leq\frac{1}{2\sqrt{2}}$, the left side is bounded
from below by $\frac{\|g_{k}\|}{8}$. Moreover, from (C.3.7),
the right side is bounded from above by $\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}L+\delta\right)\Delta$ with probability at least
$1-2\exp(-s)$. Thus we conclude that

$$ $\|g_{k}\|\leq 8\Delta\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2}L+ \delta\right)$ (C.3.24) $$

holds with probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-2\exp(-s)$, which completes the
proof.
∎

We have the following additional auxiliary lemma.

###### Lemma C.8 .

If $t_{k}\neq 0,d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k},\|d_{k}\|\leq\Delta$, then we have

$$ $\|H_{k}d_{k}+g_{k}\|\leq\frac{2\delta\Delta+2\|g_{k}\|\Delta^{2}}{\sqrt{n/s}- \mathcal{C}}$ (C.3.25) $$

with probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-2\exp(-s)$.

###### Proof.

By Lemma 2.1 and Lemma 2.2,
we have

$$ $\displaystyle\frac{1}{2}\|H_{k}d_{k}+g_{k}\|\leq\left\|P_{k}\left(H_{k}d_{k}+g _{k}\right)\right\|$ (C.3.26) $\displaystyle\|d_{k}\|=\frac{\|P_{k}^{\top}\tilde{v}_{k}\|}{|t_{k}|}\geq\left( \sqrt{\frac{n}{s}}-\mathcal{C}\right)\frac{\|\tilde{v}_{k}\|}{|t_{k}|}$ (C.3.27) $$

with probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-2\exp\left(-s\right)$. Hence,

$$ $\displaystyle\|H_{k}d_{k}+g_{k}\|$ $\displaystyle\leq 2\left\|P_{k}\left(H_{k}d_{k}+g_{k}\right)\right\|\quad( \text{by}~{}\text{\eqref{eq:tmp_1}})$ (C.3.28) $\displaystyle=2\theta_{k}\left\|\frac{\tilde{v}_{k}}{t_{k}}\right\|\quad(\text {by}~{}\text{\eqref{eq:2.1.t_nonzero_hessian} in Corollary~{}\ref{cor:cases_t_ zero_nonzero}})$ (C.3.29) $\displaystyle\leq\frac{2\theta_{k}}{\sqrt{n/s}-\mathcal{C}}\|d_{k}\|\quad( \text{by}~{}\eqref{eq:bound_d})$ (C.3.30) $\displaystyle\leq\frac{2\delta\Delta+2\|g_{k}\|\Delta^{2}}{\sqrt{n/s}-\mathcal {C}}.\quad(\text{by}~{}\text{\eqref{eq:theta_k-delta_bound} and $\|d_{k}\|\leq \Delta$})$ (C.3.31) $$

∎

Proof of Lemma 4.2

###### Proof.

This is proved by the following inequalities.

$$ $\displaystyle\|g_{k+1}\|$ $\displaystyle\leq\|g_{k+1}-H_{k}d_{k}-g_{k}\|+\|H_{k}d_{k}+g_{k}\|$ (C.3.32) $\displaystyle\leq\frac{M}{2}\|d_{k}\|^{2}+\frac{2\delta\Delta+2\|g_{k}\|\Delta ^{2}}{\sqrt{n/s}-\mathcal{C}}\quad(\text{by}~{}\text{Lemma~{}\ref{lem:bound_ Hkdk+gk}})$ (C.3.33) $\displaystyle\leq\frac{M}{2}\Delta^{2}+\frac{1}{\sqrt{n/s}-\mathcal{C}}\left(2 \delta\Delta+16\Delta^{3}\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C}\right)^{2} L+\delta\right)\right).\quad(\text{by Lemma~{}\ref{lem:grad_bound}})$ (C.3.34) $$

The second and the third inequalities both hold with probability at
least $1-2\exp\left(-\frac{C}{4}s\right)-2\exp\left(-s\right)$. Therefore,
this lemma holds with probability at least
$1-4\exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$.
∎

Proof of Lemma 4.3

###### Proof.

By (C.1.5) and Cauchy’s interlace theorem, we have $\tilde{H}_{k}+\theta_{k}I\succeq 0$. With (C.3.19) and Lemma C.7,
it follows that

$$ $-\theta_{k}\geq-\left[8\Delta^{2}\left(\left(\sqrt{\frac{n}{s}}+\mathcal{C} \right)^{2}L+\delta\right)+\delta\right].$ (C.3.35) $$

with probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-2\exp\left(-s\right)$. This implies

$$ $\tilde{H}_{k}\succeq-\left[8\Delta^{2}\left(\left(\sqrt{\frac{n}{s}}+\mathcal{ C}\right)^{2}L+\delta\right)+\delta\right]I.$ (C.3.36) $$

We can now bound $\tilde{H}_{k+1}$ and obtain

$$ $\displaystyle\tilde{H}_{k+1}$ $\displaystyle\succeq\tilde{H}_{k}-\|\tilde{H}_{k+1}-\tilde{H}_{k}\|I$ (C.3.37) $\displaystyle\succeq\tilde{H}_{k}-M\Delta I\quad(\text{by}~{}\text{Assumption~ {}\ref{asmp:lips} and $\|d_{k}\|\leq\Delta$})$ (C.3.38) $\displaystyle\succeq-\left[8\Delta^{2}\left(\left(\sqrt{\frac{n}{s}}+\mathcal{ C}\right)^{2}L+\delta\right)+\delta+M\Delta\right]I.\quad(\text{by}~{}\eqref{ eq:sub_Hk_bound})$ (C.3.39) $$

This completes the proof.
∎

###### Lemma C.5 .

###### Proof.

###### Lemma C.6 .

###### Proof.

###### Lemma C.7 .

###### Proof.

###### Lemma C.8 .

###### Proof.

###### Proof.

###### Proof.

### C.4 Proof of Theorem 4.1

###### Proof.

Let us consider how many times we iterate the case where $|d_{k}|>\Delta$
at most. According to Lemma C.3
and Lemma C.4, the objective function
decreases by at least

$$ $\frac{1}{2(\sqrt{n/s}+\mathcal{C})^{2}}\Delta^{2}\delta-\frac{M}{6}\Delta^{3}= \frac{\varepsilon^{3/2}}{3M^{2}}.$ (C.4.1) $$

with probability at least $1-2\exp\left(-s\right)$. Since the total
amount of decrease does not exceed
$D:=f(x_{0})-\inf_{x\in\mathbb{R}^{n}}f$, the number of iterations for
the case where $\|d_{k}\|>\Delta$ is at most $\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor$ with probability at least $1-2\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor\exp\left(-s\right)$. Also, since the algorithm terminates
once it enters the case $\|d_{k}\|\leq\Delta$, the total number of
iterations $m$ is at most
$U_{\varepsilon}=\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor+1$ at least
with the same probability as the above.

We can compute an $\varepsilon$–FOSP with probability at least $1-4\exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$, which can be easily
checked by applying Lemma 4.2 to
the given $\delta$ and $\Delta$.

Therefore, RSHTR converges in $\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor+1=O(\varepsilon^{-3/2})$ iterations with probability at least

$$ $\displaystyle 1$ $\displaystyle-2\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor\exp\left(-s\right)-4 \exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$ (C.4.2) $\displaystyle\geq 1-4\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+2)\exp \left(-s\right).$ (C.4.3) $$

∎

###### Proof.

### C.5 ε 𝜀 \varepsilon italic_ε –SOSP under the assumption of [ 37 ]

Let us introduce the following assumption.

###### Assumption 5 .

Let $\xi\in(0,1)$ and define $r=\mathrm{rank}(\nabla^{2}f(x^{*}))$, $\lambda_{1}$ as the maximum non-zero eigenvalues of
$\nabla^{2}f(x^{*})$, and $\lambda_{r}$ as the minimum non-zero eigenvalues
of $\nabla^{2}f(x^{*})$. Then, the following inequality holds

$$ $\displaystyle 1-\xi+16\frac{r-1}{s}\frac{1+\xi}{1-\xi}\frac{\lambda_{1}}{ \lambda_{r}}\geq 0.$ (C.5.1) $$

By the contraposition of [, Lemma 5.6.6], under Assumption 5, the lower bound on the minimum eigenvalue of $H^{*}$ is proportional to the lower bound on the minimum eigenvalue of $\tilde{H}^{*}$ with high probability. Therefore, Lemma 4.3 leads to the following theorem.

###### Theorem C.1 (Global convergence to an $\varepsilon$ –SOSP under Assumption 5 ) .

Suppose Assumptions 1 and
5 hold. Set $\varepsilon,\delta\text{ and }\Delta$ the same
as Theorem 4.1, i.e.,

$$ $0<\varepsilon\leq\frac{M^{2}}{8},\quad\delta=\left(\sqrt{\frac{n}{s}}+\mathcal {C}\right)^{2}\sqrt{\varepsilon}\quad\text{and}\quad\Delta=\frac{\sqrt{ \varepsilon}}{M}.$ (C.5.2) $$

Then RSHTR converges to an $\varepsilon$–SOSP in at most $O(\varepsilon^{-3/2})$ iterations with probability at least

$$ $\displaystyle(0.9999)^{r-1}\left(1-2\exp\left(-\frac{s\xi^{2}}{C_{3}}\right) \right)-6\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+2)\exp\left(-s\right),$ (C.5.3) $$

where $U_{\varepsilon}:=\lfloor 3M^{2}D\varepsilon^{-3/2}\rfloor+1$.

###### Proof.

By Theorem 4.1, RSHTR converges to an
$\varepsilon$–FOSP in at most $O(\varepsilon^{-3/2})$ iterations with probability
at least,

$$ $\displaystyle 1-4\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+2)\exp\left( -s\right).$ (C.5.4) $$

Let $x^{*}$ denotes the $\varepsilon$–FOSP. We now proceed to prove
that $x^{*}$ is also an $\varepsilon$–SOSP as well. By applying Lemma 4.3
to the given $\delta$ and $\Delta$, we have

$$ $\displaystyle\lambda_{\min}\left(\tilde{H}^{*}\right)$ $\displaystyle\geq-\left[\frac{8\varepsilon}{M^{2}}\left(\sqrt{\frac{n}{s}}+ \mathcal{C}\right)^{2}\left(L+\sqrt{\varepsilon}\right)+\left(\sqrt{\frac{n}{s }}+\mathcal{C}\right)^{2}\sqrt{\varepsilon}+\sqrt{\varepsilon}\right]$ (C.5.5) $$

with probability at least $1-2\exp\left(-\frac{C}{4}s\right)-2\exp\left(-s\right)$. Hence, by using the contrapositive of [, Lemma 5.6.6]
and denoting $\kappa_{H}=\min\{0,\lambda_{1}/\lambda_{r}\}$, we have

$$ $\displaystyle\lambda_{\min}\left(H^{*}\right)$ $\displaystyle\geq-\left(1-\xi+16\frac{r-1}{s}\frac{1+\xi}{1-\xi}\kappa_{H} \right)^{-1}$ (C.5.6) $\displaystyle\cdot\left[\frac{8\varepsilon}{M^{2}}\left(\sqrt{\frac{n}{s}}+ \mathcal{C}\right)^{2}\left(L+\sqrt{\varepsilon}\right)+\left(\sqrt{\frac{n}{s }}+\mathcal{C}\right)^{2}\sqrt{\varepsilon}+\sqrt{\varepsilon}\right]$ (C.5.7) $\displaystyle=\Omega(-\sqrt{\varepsilon})$ (C.5.8) $$

with probability at least
$(0.9999)^{r-1}\left(1-2\exp\left(-\frac{s\xi^{2}}{C_{3}}\right)\right)$. This shows that $x^{*}$ is an $\varepsilon$–SOSP and the lower
bound on the probability is given as follows.

$$ $\displaystyle(0.9999)^{r-1}\left(1-2\exp\left(-\frac{s\xi^{2}}{C_{3}}\right)\right)$ (C.5.9) $\displaystyle\qquad-\left(4\exp\left(-\frac{C}{4}s\right)+(2U_{\varepsilon}+2) \exp\left(-s\right)\right)$ (C.5.10) $\displaystyle\qquad-\left(2\exp\left(-\frac{C}{4}s\right)+2\exp\left(-s\right)\right)$ (C.5.11) $\displaystyle\geq(0.9999)^{r-1}\left(1-2\exp\left(-\frac{s\xi^{2}}{C_{3}} \right)\right)-6\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+4)\exp\left(- s\right)$ (C.5.12) $$

∎

Proof of Lemma
4.4

###### Proof.

$H^{*}$ can be expressed as $H^{*}=U^{*}D^{*}U^{*\top}$ using an orthogonal
matrix $U^{*}$ and a diagonal matrix $D^{*}$. Here,

$$ $D^{*}=\mathrm{diag}(\lambda_{1},\dots,\lambda_{r})$ (C.5.13) $$

is the diagonal matrix with eigenvalues $\lambda_{1},\dots,\lambda_{r}$.
Note that $\lambda_{r+1}=\dots=\lambda_{n}=0$. Hence, it follows
that

$$ $\displaystyle P^{*}H^{*}P^{*\top}$ $\displaystyle=P^{*}U^{*}D^{*}U^{*\top}P^{*\top}$ (C.5.14) $\displaystyle=\hat{P}^{*}D^{*}\hat{P}^{*\top}$ (C.5.15) $\displaystyle=\hat{P}_{1}^{*}D_{1}^{*}\hat{P}_{1}^{*\top}$ (C.5.16) $$

where $\hat{P}_{1}^{*}$ is the first $r$ columns of $\hat{P}^{*}$, and $D_{1}^{*}$ is the leading principal minor of order $r$ of $D^{*}$. Here, $\hat{P}^{*}$ is also a random Gaussian matrix due to the orthogonality of $U^{*}$.
Therefore, $\hat{P}_{1}^{*}$ is almost surely full column rank. This
implies that

$$ $\displaystyle\forall y\in\mathbb{R}^{r},\exists x\in\mathbb{R}^{s}\text{ s.t. }\hat{P}_{1}^{*\top}x=y$ (C.5.17) $$

almost surely. Hence, the following holds almost surely.

$$ $\displaystyle\lambda_{\mathrm{min}}(H^{*})$ $\displaystyle=\min_{z\in\mathbb{R}^{n}}\frac{z^{\top}H^{*}z}{\|z\|^{2}}$ (C.5.18) $\displaystyle=\min_{y\in\mathbb{R^{r}}}\frac{y^{\top}D_{1}^{*}y}{\|y\|^{2}}$ (C.5.19) $\displaystyle\geq\min_{x\in\mathbb{R^{s}}}\frac{x^{\top}\hat{P}_{1}^{*}D_{1}^{ *}\hat{P}_{1}^{*\top}x}{\|P_{1}^{*\top}x\|^{2}}\quad(\text{by \eqref{eq:dim_r_ to_s}})$ (C.5.20) $\displaystyle\begin{aligned} &\geq\min\left\{\min_{x\in E}\frac{x^{\top}\hat{P }_{1}^{*}D_{1}^{*}\hat{P}_{1}^{*\top}x}{\|P_{1}^{*\top}x\|^{2}},0\right\}\\ &\quad\quad\text{where}~{}~{}E:=\left\{x\in\mathbb{R}^{s}\mid x^{\top}\hat{P}_ {1}^{*}D_{1}^{*}\hat{P}_{1}^{*\top}x<0\right\}\end{aligned}$ (C.5.21) $\displaystyle\begin{aligned} &\geq\min\left\{\min_{x\in E}\frac{1}{\sigma_{ \mathrm{min}}\left(\hat{P}_{1}^{*}\right)^{2}}\frac{x^{\top}\hat{P}_{1}^{*}D_{ 1}^{*}\hat{P}_{1}^{*\top}x}{\|x\|^{2}},0\right\}\\ &\quad\quad\left(\text{by}\|\hat{P}_{1}^{*\top}x\|^{2}\geq\sigma_{\mathrm{min} }\left(\hat{P}_{1}^{*}\right)\|x\|\right)\end{aligned}$ (C.5.22) $\displaystyle=\frac{1}{\sigma_{\mathrm{min}}\left(\hat{P}_{1}^{*}\right)^{2}} \min\left\{\lambda_{\mathrm{min}}\left(\hat{P}_{1}^{*}D_{1}^{*}\hat{P}_{1}^{* \top}\right),0\right\}$ (C.5.23) $\displaystyle=\frac{1}{\sigma_{\mathrm{min}}\left(\hat{P}_{1}^{*}\right)^{2}} \min\left\{\lambda_{\mathrm{min}}\left(P^{*}H^{*}P^{*\top}\right),0\right\} \quad\left(\text{by \eqref{eq:PHP_decomp}}\right).$ (C.5.24) $$

Moreover, by [, Theorem 1.1], we have

$$ $\displaystyle\forall\zeta>0,\quad\mathrm{Pr}\left[\sigma_{\mathrm{min}}\left( \hat{P}_{1}^{*}\right)\geq\zeta\left(1-\sqrt{\frac{r-1}{s}}\right)\right]\geq 1 -(\bar{C}\zeta)^{s-r+1}-e^{-\bar{c}s}$ (C.5.25) $$

for some constants $\bar{C},\bar{c}$. Therefore, for any $\zeta>0$, the
following inequality holds with probability at least
$1-(\bar{C}\zeta)^{s-r+1}-e^{-\bar{c}s}$.

$$ $\displaystyle\lambda_{\mathrm{min}}(H^{*})$ $\displaystyle\geq\frac{1}{\zeta^{2}\left(1-\sqrt{\frac{r-1}{s}}\right)^{2}} \min\left\{\lambda_{\mathrm{min}}\left(P^{*}H^{*}P^{*\top}\right),0\right\}$ (C.5.26) $$

∎

Proof of Theorem 4.2

###### Proof.

By following the same argument as in the proof of Theorem C.1
up to (C.5.5), we obtain

$$ $\lambda_{\min}\left(\tilde{H}^{*}\right)\geq\Omega(-\sqrt{\varepsilon})$ (C.5.27) $$

with probability at least $1-6\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+4)\exp\left(-s\right)$. Applying Lemma 4.4
with $\zeta={\bar{C}}/{e}$, $\lambda_{\mathrm{min}}(H^{*})\geq\Omega\left(-\sqrt{\varepsilon}\right)$ with probability at least

$$ $\displaystyle 1-6\exp\left(-\frac{C}{4}s\right)-(2U_{\varepsilon}+4)\exp\left( -s\right)-\exp\left({-s+r-1}\right)-\exp({-\bar{c}s}).$ (C.5.28) $$

for some constant $\bar{c}$. This completes the proof.
∎

###### Assumption 5 .

###### Theorem C.1 (Global convergence to an ε 𝜀 \varepsilon italic_ε –SOSP under Assumption 5 ) .

###### Proof.

###### Proof.

###### Proof.

### C.6 Local convergence

Proof of Lemma 4.5

###### Proof.

By applying (C.1.12) to $g_{k}=0$, we have $(\tilde{H}_{k}+\theta_{k}I)\tilde{v}_{k}=0$. This implies that
$\tilde{v}_{k}=0$ or $(-\theta_{k},\tilde{v}_{k})$ is an eigenpair of
$\tilde{H}_{k}$.

We show that the latter case is impossible by supposing it and leading
to a contradiction. Suppose that $(-\theta_{k},\tilde{v}_{k})$ is an eigenpair
of $\tilde{H}_{k}$. This implies
$\lambda_{\min}\left(\tilde{H}_{k}\right)\leq-\theta_{k}\leq 0$. Thus,
we get

$$ $\displaystyle\exists y\in\mathbb{R}^{s}\setminus\{0\}\text{ s.t. }\frac{y^{ \top}\tilde{H}_{k}y}{\|y\|^{2}}\leq 0.$ (C.6.1) $$

Since $y\neq 0$, we have $0<\|P_{k}^{\top}y\|$ almost surely.
Therefore, $\|y^{2}\|/\|P_{k}^{\top}y\|^{2}>0$ follows. Thus, by multiplying
(C.6.5) by
$\|y^{2}\|/\|P_{k}^{\top}y\|^{2}>0$, we obtain

$$ $\displaystyle\exists y\in\mathbb{R}^{s}\text{ s.t. }\frac{y^{\top}\tilde{H}_{k }y}{\|P_{k}^{\top}y\|^{2}}\leq 0.$ (C.6.2) $$

By taking $z=P_{k}^{\top}y$, it follows that

$$ $\displaystyle\exists z\in\mathbb{R}^{n}\text{ s.t. }\frac{z^{\top}H_{k}z}{\|z \|^{2}}\leq 0.$ (C.6.3) $$

Therefore $\lambda_{\min}(H_{k})\leq 0$ follows. However, this
contradicts Assumption 3.

From the above argument, we have $\tilde{v}_{k}=0$. Since
$\tilde{v}_{k}=0$ implies $t_{k}\neq 0$ from (C.1.6),
$d_{k}$ is defined as:

$$ $\displaystyle d_{k}=P_{k}^{\top}\tilde{v}_{k}/t_{k}=0.$ (C.6.4) $$

Therefore, $\|d_{k}\|\leq\Delta$ holds and
$x_{k+1}=x_{k}+d_{k}=x_{k}$ follows.
∎

Next, we show that in a sufficiently small neighborhood of a local minimum, we
have $\|d_{k}\|\leq\Delta$. To this end, we first
present the following auxiliary lemma.

###### Lemma C.9 .

Under Assumption 3,
$t_{k}\neq 0$ almost surely.

###### Proof.

Suppose on the contrary that $t_{k}=0$, then
$(-\theta_{k},\tilde{v}_{k})$ is an eigenpair of $\tilde{H}_{k}$ by
(C.1.14) in Corollary C.1.
Thus we almost surely have
$\lambda_{\min}(\tilde{H}_{k})\leq-\theta_{k}<-\delta\leq 0$ by
$g_{k}\neq 0$ and Lemma C.1. This implies that

$$ $\displaystyle\exists y\in\mathbb{R}^{s}\text{ s.t. }\frac{y^{\top}\tilde{H}_{k }y}{\|y\|^{2}}<0.$ (C.6.5) $$

Note that $\|y\|\neq 0$ and $\|P_{k}^{\top}y\|\neq 0$ hold since the numerator
and denominator of (C.6.5) are both non-zero.
By multiplying (C.6.5) by
$\|y\|^{2}/\|P_{k}^{\top}y\|^{2}>0$, it follows that

$$ $\displaystyle\exists y\in\mathbb{R}^{s}\text{ s.t. }\frac{y^{\top}\tilde{H}_{k }y}{\|P_{k}^{\top}y\|^{2}}<0.$ (C.6.6) $$

By considering $z=P_{k}^{\top}y$, we obtain

$$ $\displaystyle\exists z\in\mathbb{R}^{n}\text{ s.t. }\frac{z^{\top}H_{k}z}{\|z \|^{2}}<0.$ (C.6.7) $$

Therefore $\lambda_{\min}(H_{k})<0$ follows. However, this contradicts
Assumption 3. The proof is completed.
∎

By Lemma C.9, under Assumption 3,
we have $d_{k}=P_{k}^{\top}\frac{\tilde{v}_{k}}{t_{k}}$ almost surely.
This leads to the following lemma.

###### Lemma C.10 .

Under Assumption 3,
we have $\|d_{k}\|\leq\Delta$ for sufficiently large $k$ with
probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$.

###### Proof.

From Lemma C.9 and (C.1.17), we have the following almost surely.

$$ $\displaystyle\frac{\tilde{v}_{k}}{t_{k}}=-(\tilde{H}_{k}+\theta_{k}I)^{-1} \tilde{g}_{k}.$ (C.6.8) $$

Therefore, by multiplying $P_{k}^{\top}$ from the left, it follows that

$$ $\displaystyle d_{k}=P_{k}^{\top}\frac{\tilde{v}_{k}}{t_{k}}=-P_{k}^{\top}( \tilde{H}_{k}+\theta_{k}I)^{-1}\tilde{g}_{k}.$ (C.6.9) $$

Thus, we obtain

$$ $\displaystyle\|d_{k}\|$ $\displaystyle\leq\|P_{k}^{\top}\|\|(\tilde{H}_{k}+\theta_{k}I)^{-1}\|\|\tilde{ g}_{k}\|$ (C.6.10) $\displaystyle\leq\|P_{k}^{\top}\|\|(\tilde{H}_{k}+\theta_{k}I)^{-1}\|\|g_{k}\| /2\quad\left(\text{by Lemma~{}\ref{lem:preserve_norm}}\right)$ (C.6.11) $\displaystyle\leq\frac{\sqrt{n/s}+\mathcal{C}}{2}\|(\tilde{H}_{k}+\theta_{k}I) ^{-1}\|\|g_{k}\|.\quad\left(\text{by Lemma~{}\ref{lem:approximate_isometry}}\right)$ (C.6.12) $$

Here the second and third inequalities hold with probability at least $1-2\exp\left(-\frac{C}{4}s\right)$ and $1-2\exp\left(-s\right)$ respectively.
By Lemma C.11, we have $\tilde{H}_{k}+\theta_{k}I\succeq\left(\sqrt{\frac{n}{s}}-\mathcal{C}\right)^{2
}\mu+\theta_{k}$ with probability at least $1-2\exp\left(-s\right)$. Hence, we have

$$ $\displaystyle\|d_{k}\|$ $\displaystyle\leq\frac{(\sqrt{n/s}+\mathcal{C})/2}{(\sqrt{n/s}-\mathcal{C})^{2 }\mu+\theta_{k}}\|g_{k}\|$ (C.6.13) $\displaystyle\leq\frac{(\sqrt{n/s}+\mathcal{C})/2}{(\sqrt{n/s}-\mathcal{C})^{2 }\mu}\|g_{k}\|$ (C.6.14) $\displaystyle\leq\frac{(\sqrt{n/s}+\mathcal{C})}{2(\sqrt{n/s}-\mathcal{C})^{2} }\frac{\|g_{k}\|}{\mu}.$ (C.6.15) $$

We have $\|g_{k}\|\to 0$ by Assumption 3, which leads to $\|d_{k}\|\leq\Delta$ for sufficiently large $k$.
∎

Here we present an auxiliary lemma for the proof of Theorem 4.3.

###### Lemma C.11 .

Under Assumption 3,
we have

$$ $\displaystyle\lambda_{\min}\left(\tilde{H}_{k}\right)\geq\left(\sqrt{\frac{n}{ s}}-\mathcal{C}\right)^{2}\mu,$ (C.6.16) $\displaystyle\lambda_{\max}\left(\tilde{H}_{k}\right)\leq\left(\sqrt{\frac{n}{ s}}+\mathcal{C}\right)^{2}\lambda_{\max}(H_{k}).$ (C.6.17) $$

with probability at least $1-2\exp\left(-s\right)$.

###### Proof.

From Assumption 3, it follows that for any
$x\in\mathbb{R}^{n}$, we have $\frac{x^{\top}H_{k}x}{\|x\|^{2}}\geq\mu$.
Therefore, by setting $x=P_{k}^{\top}y$, we have
$\frac{y^{\top}P_{k}H_{k}P_{k}^{\top}y}{\|P_{k}^{\top}y\|^{2}}\geq\mu$
for any $y\in\mathbb{R}^{s}$. Using Lemma 2.2,
we have
$\left(\sqrt{\frac{n}{s}}-\mathcal{C}\right)^{2}\|y\|^{2}\leq\|P_{k}^{\top}y\|^
{2}$
with probability at least $1-2\exp\left(-s\right)$. This implies the following
inequality holds.

$$ $\displaystyle\frac{y^{\top}P_{k}H_{k}P_{k}^{\top}y}{\|y\|^{2}}\geq\left(\sqrt{ \frac{n}{s}}-\mathcal{C}\right)^{2}\mu.$ (C.6.18) $$

This inequality holds for any $y\in\mathbb{R}^{s}$, which proves the first
equation. The proof of the second equation follows a similar argument.
∎

###### Proof.

###### Lemma C.9 .

###### Proof.

###### Lemma C.10 .

###### Proof.

###### Lemma C.11 .

###### Proof.

#### C.6.1 Proof of Theorem 4.3

###### Proof.

$$ $\displaystyle\sqrt{\bar{H}}(x_{k+1}-\bar{x})$ $\displaystyle=\sqrt{\bar{H}}(x_{k+1}-x_{k})+\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.19) $\displaystyle=\sqrt{\bar{H}}d_{k}+\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.20) $\displaystyle=-\sqrt{\bar{H}}P_{k}^{\top}(\tilde{H}_{k}+\theta_{k}I)^{-1}P_{k} g_{k}+\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.21) $\displaystyle=-\sqrt{\bar{H}}P_{k}^{\top}(\tilde{H}_{k}+\theta_{k}I)^{-1}P_{k} H_{k}(x_{k}-\bar{x})$ (C.6.22) $\displaystyle\quad-\sqrt{\bar{H}}P_{k}^{\top}(\tilde{H}_{k}+\theta_{k}I)^{-1}P _{k}(g_{k}-H_{k}(x_{k}-\bar{x}_{k}))$ (C.6.23) $\displaystyle\quad+\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.24) $\displaystyle=-A-B+\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.25) $$

Here, we define

$$ $\displaystyle A$ $\displaystyle:=\sqrt{\bar{H}}P_{k}^{\top}(\tilde{H}_{k}+\theta_{k}I)^{-1}P_{k} H_{k}(x_{k}-\bar{x})$ (C.6.26) $$

and

$$ $\displaystyle B$ $\displaystyle:=\sqrt{\bar{H}}P_{k}^{\top}(\tilde{H}_{k}+\theta_{k}I)^{-1}P_{k} (g_{k}-H_{k}(x_{k}-\bar{x}_{k}))$ (C.6.27) $$

To bound $B$, we give a bound to $\|P_{k}^{\top}(P_{k}H_{k}P_{k}^{\top}+\theta_{k}I)^{-1}P_{k}\|$. By Lemma C.11,
$P_{k}H_{k}P_{k}^{\top}$ is invertible with probability at least $1-2\exp\left(-s\right)$. Therefore, we have:

$$ $\displaystyle\|P_{k}^{\top}(P_{k}H_{k}P_{k}^{\top}+\theta_{k}I)^{-1}P_{k}\|$ $\displaystyle\leq\|P_{k}^{\top}(P_{k}H_{k}P_{k}^{\top})^{-1}P_{k}\|$ (C.6.28) $$

Moreover, the right-hand side satisfies the following inequality.

$$ $\displaystyle\|P_{k}^{\top}(P_{k}H_{k}P_{k}^{\top})^{-1}P_{k}\|$ $\displaystyle\leq\|P_{k}^{\top}\|^{2}\left(\left(\sqrt{\frac{n}{s}}-\mathcal{C }\right)^{2}\mu\right)^{-1}\quad(\text{by Lemma~{}\ref{lem:hessian_sub_ positive_definite}})$ (C.6.29) $\displaystyle\leq\frac{(\sqrt{n/s}+\mathcal{C})^{2}}{(\sqrt{n/s}-\mathcal{C})^ {2}}\cdot\frac{1}{\mu}\quad(\text{by Lemma~{}\ref{lem:approximate_isometry}})$ (C.6.30) $$

Here, the first and the second inequalities both hold with probability at
least $1-2\exp\left(-s\right)$. Therefore, combining (C.6.28)
and (C.6.30), we have

$$ $\displaystyle\|P_{k}^{\top}(P_{k}H_{k}P_{k}^{\top}+\theta_{k}I)^{-1}P_{k}\| \leq\frac{(\sqrt{n/s}+\mathcal{C})^{2}}{(\sqrt{n/s}-\mathcal{C})^{2}}\cdot \frac{1}{\mu}$ (C.6.31) $$

with probability at least $1-6\exp\left(-s\right)$.

By Taylor expansion at $\bar{x}$ of $\nabla f$, we obtain $\|g_{k}-H_{k}(x_{k}-\bar{x})\|=O(\|x_{k}-\bar{x}\|^{2})$. Combining this with
(C.6.31), we get $B=O(\|x_{k}-\bar{x}\|^{2})$
with probability at least $1-6\exp\left(-s\right)$.

Next, to bound $A$, we further decompose $A=A_{1}+A_{2}$ such that

$$ $\displaystyle A_{1}$ $\displaystyle:=\sqrt{\bar{H}}P_{k}^{\top}(P_{k}\bar{H}P_{k}^{\top}+\theta_{k}I )^{-1}P_{k}\bar{H}(x_{k}-\bar{x})$ (C.6.32) $\displaystyle A_{2}$ $\displaystyle:=\sqrt{\bar{H}}P_{k}^{\top}(P_{k}\bar{H}P_{k}^{\top}+\theta_{k}I )^{-1}P_{k}(H_{k}-\bar{H})(x_{k}-\bar{x})$ (C.6.33) $$

Since $\|H_{k}-\bar{H}\|$ tends to 0 and (C.6.31),
we have $\|A_{2}\|=o(\|x_{k}-\bar{x}\|)$. This leads to

$$ $\displaystyle\left\|\sqrt{\bar{H}}(x_{k+1}-\bar{x})\right\|\leq\left\|-A_{1}+ \sqrt{\bar{H}}(x_{k}-\bar{x})\right\|+o(\|x_{k}-\bar{x}\|),$ (C.6.34) $$

which holds with probability at least $1-6\exp\left(-s\right)$.
Therefore, it remains to bound $\left\|-A_{1}+\sqrt{\bar{H}}(x_{k}-\bar{x})\right\|$. This is further decomposed as $\|A_{3}+A_{4}\|$ where:

$$ $\displaystyle A_{3}$ $\displaystyle:=\left(I-\sqrt{\bar{H}}P_{k}^{\top}(P_{k}\bar{H}P_{k}^{\top})^{- 1}P_{k}\sqrt{\bar{H}}\right)\sqrt{\bar{H}}(x_{k}-\bar{x})$ (C.6.35) $\displaystyle A_{4}$ $\displaystyle:=\sqrt{\bar{H}}P_{k}^{\top}\left((P_{k}\bar{H}P_{k}^{\top}+ \theta_{k}I)^{-1}-(P_{k}\bar{H}P_{k}^{\top})^{-1}\right)P_{k}\bar{H}(x_{k}- \bar{x}).$ (C.6.36) $$

Here, $\|A_{4}\|=o(\|x_{k}-\bar{x}\|)$ holds for the following reason.
By (C.1.16), Lemma C.9 and
$\delta=0$, we almost surely have $\theta_{k}=-g_{k}d_{k}$ and thus

$$ $\displaystyle\|\theta_{k}\|$ $\displaystyle\leq\|g_{k}\|\|d_{k}\|$ (C.6.37) $\displaystyle\leq\Delta\|g_{k}\|\quad(\text{by Lemma~{}\ref{lem:norm_d_k_le_ Delta}})$ (C.6.38) $$

with probability at least
$1-2\exp\left(-\frac{C}{4}s\right)-4\exp\left(-s\right)$. This leads
to $\theta_{k}\to 0$ since $\|g_{k}\|$ tends to 0. Therefore,
$\left\|(P_{k}\bar{H}P_{k}^{\top}+\theta_{k}I)^{-1}-(P_{k}\bar{H}P_{k}^{\top})^
{-1}\right\|$
tends to 0, which implies $\|A_{4}\|=o(\|x_{k}-\bar{x}\|)$. Hence, it remains
to bound $\|A_{3}\|$. Using the fact that
$\sqrt{\bar{H}}P_{k}^{\top}(P_{k}\bar{H}P_{k}^{\top})^{-1}P_{k}\sqrt{\bar{H}}$
is an orthogonal projection, this is bounded from above by

$$ $\displaystyle\sqrt{1-\frac{\lambda_{0}}{2\lambda_{\max}(P_{k}\bar{H}P_{k}^{ \top})}}\left\|\sqrt{\bar{H}}(x_{k}-\bar{x})\right\|.$ (C.6.39) $$

Here, $\lambda_{0}$ is the smallest nonzero eigenvalue of $\bar{H}$. Thus,
we obtain the following for sufficiently large $k$

$$ $\displaystyle\left\|\sqrt{\bar{H}}(x_{k+1}-\bar{x})\right\|\leq\sqrt{1-\frac{ \lambda_{0}}{4\lambda_{\max}(P_{k}\bar{H}P_{k}^{\top})}}\left\|\sqrt{\bar{H}}( x_{k}-\bar{x})\right\|$ (C.6.40) $$

Since we have $\lambda_{0}\geq\mu$ and, by Lemma C.11,
$\lambda_{\max}(P_{k}\bar{H}P_{k}^{\top})\leq\left(\sqrt{\frac{n}{s}}+\mathcal{
C}\right)^{2}\lambda_{\max}(\bar{H})$ with probability at least $1-2\exp\left(-s\right)$, the upper bound can be rewritten as

$$ $\displaystyle\left\|\sqrt{\bar{H}}(x_{k+1}-\bar{x})\right\|\leq\sqrt{1-\frac{ \mu}{4\lambda_{\max}(\bar{H})(\sqrt{n/s}+\mathcal{C})^{2}}}\left\|\sqrt{\bar{H }}(x_{k}-\bar{x})\right\|.$ (C.6.41) $$

Since the probabilistically valid properties that we used in this proof
are Lemmas 2.2, C.9,
C.11 and C.10,
the probability lower bound is given by $1-2\exp\left(-\frac{C}{4}s\right)-8\exp\left(-s\right)$.
∎

###### Proof.

#### C.6.2 Local quadratic convergence

Let $\bar{y}=R\bar{x}$, where we recall that $\bar{x}$ be the strict local
minimizer of $f$. Then the following properties hold:

$$ $\displaystyle f(x)$ $\displaystyle=f(R^{\top}Rx)=l(Rx)$ (C.6.42) $\displaystyle\nabla f(x)$ $\displaystyle=\nabla f(\Pi x)=\Pi^{\top}\nabla f(x)=\Pi\nabla f(x)$ (C.6.43) $\displaystyle\|\nabla f(x)\|$ $\displaystyle=\sqrt{\|\nabla f(x)^{\top}\nabla f(x)\|^{2}}=\sqrt{\|\nabla f(x) ^{\top}\Pi\nabla f(x)\|}=\|R\nabla f(x)\|$ (C.6.44) $\displaystyle\exists\rho>0$ $\displaystyle\text{ s.t. }\|\nabla l(y)\|\geq\rho\|y-\bar{y}\|$ (C.6.45) $\displaystyle\exists\gamma>0$ $\displaystyle\text{ s.t. }\|\nabla f(x)\|\geq\gamma\|R(x-\bar{x})\|\quad( \gamma=\sigma_{\min}(R^{\top})\rho)$ (C.6.46) $$

Next, we show some lemmas regarding Lipschitz continuity.

###### Lemma C.12 .

Suppose Assumptions 1 and 4
hold. There exist constants $L_{l},M_{l}>0$ such that for any
$y_{1},y_{2}\in\mathbb{R}^{r}$, the following inequalities hold:

$$ $\displaystyle\|\nabla l(y_{1})-\nabla l(y_{2})\|\leq L_{l}\|y_{1}-y_{2}\|$ (C.6.47) $\displaystyle\|\nabla^{2}l(y_{1})-\nabla^{2}l(y_{2})\|\leq M_{l}\|y_{1}-y_{2}\|$ (C.6.48) $$

###### Proof.

Since $l(y)=f(R^{\top}y)$, by the Lipschitz continuity of $f$, we have

$$ $\displaystyle\left\|\nabla l(y_{1})-\nabla l(y_{2})\right\|$ $\displaystyle=\left\|R\left.\nabla f(x)\right|_{x=R^{\top}y_{1}}-R\left.\nabla f (x)\right|_{x=R^{\top}y_{2}}\right\|$ (C.6.49) $\displaystyle\leq\left\|R\right\|\left\|\left.\nabla f(x)\right|_{x=R^{\top}y_ {1}}-\left.\nabla f(x)\right|_{x=R^{\top}y_{2}}\right\|$ (C.6.50) $\displaystyle\leq\left\|R\right\|L\left\|R^{\top}y_{1}-R^{\top}y_{2}\right\|$ (C.6.51) $\displaystyle\leq\left\|R\right\|^{2}L\left\|y_{1}-y_{2}\right\|.$ (C.6.52) $$

Moreover, we have

$$ $\displaystyle\|\nabla^{2}l(y_{1})-\nabla^{2}l(y_{2})\|$ $\displaystyle=\left\|R\left(\left.\nabla^{2}f(x)\right|_{x=R^{\top}y_{1}}- \left.\nabla^{2}f(x)\right|_{x=R^{\top}y_{2}}\right)R^{\top}\right\|$ (C.6.53) $\displaystyle\leq\left\|R\right\|^{2}\left\|\left.\nabla^{2}f(x)\right|_{x=R^{ \top}y_{1}}-\left.\nabla^{2}f(x)\right|_{x=R^{\top}y_{2}}\right\|$ (C.6.54) $\displaystyle\leq\left\|R\right\|^{2}M\left\|R^{\top}y_{1}-R^{\top}y_{2}\right\|$ (C.6.55) $\displaystyle\leq\left\|R\right\|^{3}M\left\|y_{1}-y_{2}\right\|.$ (C.6.56) $$

Therefore, by setting $L_{l}=\left\|R\right\|^{2}L$ and $M_{l}=\left\|R\right\|^{3}M$, the lemma is proved.
∎

###### Lemma C.13 .

Suppose Assumptions 1 and 4
hold. There exists a constant $L_{\Pi}>0$ such that for any
$x_{1},x_{2}\in\mathbb{R}^{n}$, the following inequality holds:

$$ $\displaystyle\|\nabla f(x_{1})-\nabla f(x_{2})\|_{\Pi}\leq L_{\Pi}\|x_{1}-x_{2 }\|_{\Pi}$ (C.6.57) $$

###### Proof.

$$ $\displaystyle\|\nabla f(x_{1})-\nabla f(x_{2})\|_{\Pi}$ $\displaystyle=\sqrt{\left\|\left(\nabla f(x_{1})-\nabla f(x_{2})\right)^{\top} \Pi\left(\nabla f(x_{1})-\nabla f(x_{2})\right)\right\|}$ (C.6.58) $\displaystyle=\sqrt{\left\|\left(\nabla f(x_{1})-\nabla f(x_{2})\right)^{\top} \left(\Pi\nabla f(x_{1})-\Pi\nabla f(x_{2})\right)\right\|}$ (C.6.59) $\displaystyle=\sqrt{\left\|\left(\nabla f(x_{1})-\nabla f(x_{2})\right)^{\top} \left(\nabla f(x_{1})-\nabla f(x_{2})\right)\right\|}\quad\text{(by \eqref{eq: grad_f_Pi})}$ (C.6.60) $\displaystyle\leq\left\|\nabla f(x_{1})-\nabla f(x_{2})\right\|$ (C.6.61) $\displaystyle=\left\|R^{\top}\left(\left.\nabla l(y)\right|_{y=Rx_{1}}-\left. \nabla l(y)\right|_{y=Rx_{2}}\right)\right\|$ (C.6.62) $\displaystyle\leq L_{l}\left\|R\right\|\left\|Rx_{1}-Rx_{2}\right\|$ (C.6.63) $$

Thus, by setting $L_{\Pi}=L_{l}\left\|R\right\|$, the lemma is proved.
∎

From this lemma, it immediately follows that
$\|g_{k}\|=\|g_{k}\|_{\Pi}=O(\|x_{k}-\bar{x}\|_{\Pi})$.

In the following, we analyze the convergence rate of $\|x_{k}-\bar{x}\|_{\Pi}$, which leads to the convergence rate of $\|f(x_{k})-f(\bar{x})\|$.
First, note that $t\neq 0~{}(a.s.)$ is derived from the fact that the Hessian
is positive semi-definite near $\bar{x}$. However, the proof is omitted since it is
similar to that of Lemma C.9.
This implies $d_{k}=P_{k}^{\top}\frac{\tilde{v}_{k}}{t_{k}}$.

Next, we show two auxiliary lemmas.

###### Lemma C.14 .

Suppose Assumption 4
holds. The following inequality holds with probability at least
$1-4\exp\left(-\frac{C}{4}s\right)$.

$$ $\displaystyle\|H_{k}d_{k}+g_{k}\|\leq 4\|g_{k}\|_{\Pi}\|d_{k}\|_{\Pi}^{2}$ (C.6.65) $$

###### Proof.

Let $U_{R}$ be an orthogonal matrix whose first $r$ rows are given by $R$.
It follows that $U_{R}P_{k}^{\top}$ has the same distribution as
$P_{k}^{\top}$, meaning that each element of $U_{R}P_{k}^{\top}$ is distributed
according to $\mathcal{N}(0,1/s)$. As $RP_{k}^{\top}$ is the first $r$
rows of $U_{R}P_{k}^{\top}$, $RP_{k}^{\top}$ is an $r\times s$ random matrix
with elements independently drawn from $\mathcal{N}(0,1/s)$. Hence, we can
apply Lemma 2.1 to $RP_{k}^{\top}$ and we have

$$ $\displaystyle\|H_{k}d_{k}+g_{k}\|$ $\displaystyle\leq 2\|P_{k}(H_{k}d_{k}+g_{k})\|\quad\text{(by Lemma~{}\ref{lem: preserve_norm})}$ (C.6.66) $\displaystyle\leq 4\|RP_{k}^{\top}P_{k}(H_{k}d_{k}+g_{k})\|\quad\text{(by Lemma~{}\ref{lem:preserve_norm})}$ (C.6.67) $$

with probability at least $1-4\exp\left(-\frac{C}{4}s\right)$. By
multiplying $RP_{k}^{\top}$ to both sides of (C.1.16),
we obtain

$$ $\displaystyle RP_{k}^{\top}P_{k}(H_{k}d_{k}+g_{k})$ $\displaystyle=-\theta_{k}Rd_{k}$ (C.6.68) $$

Thus we have

$$ $\displaystyle\|H_{k}d_{k}+g_{k}\|$ $\displaystyle\leq 4\|RP_{k}^{\top}P_{k}(H_{k}d_{k}+g_{k})\|\quad\text{(by \eqref{eq:RPkPkHkdk+gk})}$ (C.6.69) $\displaystyle=4\|-\theta_{k}Rd_{k}\|\quad\text{(by \eqref{eq:RPkPkHkdk+gk2})}$ (C.6.70) $\displaystyle=4\theta_{k}\|Rd_{k}\|$ (C.6.71) $\displaystyle=4\theta_{k}\|d_{k}\|_{\Pi}.$ (C.6.72) $$

Moreover, from (C.1.16) and $\delta=0$, we
have

$$ $\displaystyle\theta_{k}$ $\displaystyle=-g_{k}^{\top}d_{k}$ (C.6.73) $\displaystyle=-(\Pi g_{k})^{\top}d_{k}$ (C.6.74) $\displaystyle=-(Rg_{k})^{\top}(Rd_{k})$ (C.6.75) $\displaystyle\leq\|g_{k}\|_{\Pi}\|d_{k}\|_{\Pi}$ (C.6.76) $$

Combining (C.6.72) and (C.6.76),
we obtain

$$ $\displaystyle\|H_{k}d_{k}+g_{k}\|\leq 4\|g_{k}\|_{\Pi}\|d_{k}\|_{\Pi}^{2}$ (C.6.77) $$

∎

###### Lemma C.15 .

Suppose Assumptions 1 and
4 hold. The following
inequality holds:

$$ $\displaystyle\left\|g_{k+1}-(H_{k}d_{k}+g_{k})\right\|\leq\frac{1}{2}M_{l}\|d_ {k}\|_{\Pi}^{2}$ (C.6.78) $$

###### Proof.

By considering the Taylor expansion of $t\mapsto\nabla f(x_{k}+td_{k})$, we obtain the following equation:

$$ $\displaystyle g_{k+1}=g_{k}+\int_{0}^{1}\nabla^{2}f(x_{k}+td_{k})d_{k}dt$ (C.6.79) $$

By subtracting $H_{k}d_{k}+g_{k}$ from both sides, we obtain

$$ $\displaystyle g_{k+1}-(H_{k}d_{k}+g_{k})=\int_{0}^{1}\left(\nabla^{2}f(x_{k}+ td_{k})-H_{k}\right)d_{k}dt$ (C.6.80) $$

By evaluating the norm of both sides, we obtain the following inequality:

$$ $\displaystyle\left\|g_{k+1}-(H_{k}d_{k}+g_{k})\right\|$ $\displaystyle\leq\int_{0}^{1}\left\|\left(\nabla^{2}f(x_{k}+td_{k})-H_{k} \right)d_{k}\right\|dt$ (C.6.81) $\displaystyle=\int_{0}^{1}\left\|R^{\top}\left(\left.\nabla^{2}l(y)\right|_{y= R(x_{k}+td_{k})}-\left.\nabla^{2}l(y)\right|_{y=Rx_{k}}\right)Rd_{k}\right\|dt$ (C.6.82) $\displaystyle\leq\int_{0}^{1}\left\|R\right\|\left\|\left(\left.\nabla^{2}l(y) \right|_{y=R(x_{k}+td_{k})}-\left.\nabla^{2}l(y)\right|_{y=Rx_{k}}\right) \right\|\left\|Rd_{k}\right\|dt$ (C.6.83) $\displaystyle\leq\left\|R\right\|\int_{0}^{1}M_{l}\left\|R(x_{k}+td_{k})-Rx_{k }\right\|\left\|Rd_{k}\right\|dt\quad\text{(by \eqref{eq:lipschitz_hess_l})}$ (C.6.84) $\displaystyle=M_{l}\left\|R\right\|\left\|Rd_{k}\right\|^{2}\int_{0}^{1}tdt$ (C.6.85) $\displaystyle=\frac{1}{2}M_{l}\left\|R\right\|\left\|d_{k}\right\|_{\Pi}^{2}$ (C.6.86) $$

Thus, the lemma is proved.
∎

Proof of Theorem 4.4

###### Proof.

The following inequality holds:

$$ $\displaystyle\|x_{k+1}-\bar{x}\|_{\Pi}$ $\displaystyle\leq\frac{1}{\gamma}\|g_{k+1}\|\quad\text{(by \eqref{eq:grad_f_Rx _lower})}$ (C.6.87) $\displaystyle\leq\frac{1}{\gamma}\left(\|H_{k}d_{k}+g_{k}\|+\|g_{k+1}-(H_{k}d_ {k}+g_{k})\|\right)$ (C.6.88) $\displaystyle\leq\frac{1}{\gamma}\left(4\|g_{k}\|_{\Pi}\|d_{k}\|_{\Pi}^{2}+ \frac{1}{2}M_{l}\|R\|\|d_{k}\|_{\Pi}^{2}\right)\quad\text{(by Lemma~{}\ref{lem :upper_bound_Hkdk+gk_Pi} and Lemma~{}\ref{lem:bound_gk+1-Hkdk-gk_Pi})}$ (C.6.89) $\displaystyle=\frac{1}{\gamma}\left(4\|x_{k}-\bar{x}\|_{\Pi}+\frac{1}{2}M_{l} \|R\|\right)\|d_{k}\|_{\Pi}^{2}\quad\text{(by $\|g_{k}\|_{\Pi}=O(\|x_{k}-\bar{ x}\|_{\Pi})$)}$ (C.6.90) $$

Now, we have

$$ $\displaystyle\|d_{k}\|_{\Pi}$ $\displaystyle\leq\|x_{k+1}-\bar{x}\|_{\Pi}+\|x_{k}-\bar{x}\|_{\Pi}$ (C.6.91) $\displaystyle\leq\frac{1}{\gamma}\left(4\|x_{k}-\bar{x}\|_{\Pi}+\frac{1}{2}M_{ l}\|R\|\right)\|d_{k}\|_{\Pi}^{2}+\|x_{k}-\bar{x}\|_{\Pi}$ (C.6.92) $$

which can be rearranged as

$$ $\displaystyle\left(1-\frac{\|d_{k}\|_{\Pi}}{\gamma}\left(4\|x_{k}-\bar{x}\|_{ \Pi}+\frac{1}{2}M_{l}\|R\|\right)\right)\|d_{k}\|_{\Pi}\leq\|x_{k}-\bar{x}\|_{\Pi}$ (C.6.93) $$

Since $\|x_{k}-\bar{x}\|_{\Pi}\to 0$ and $\|d_{k}\|_{\Pi}\to 0$, for
sufficiently large $k$, we have $\frac{1}{2}\|d_{k}\|_{\Pi}\leq\|x_{k}-\bar{x}\|_{\Pi}$. Combining this with (C.6.90), for
sufficiently large $k$, we obtain

$$ $\displaystyle\|x_{k+1}-\bar{x}\|_{\Pi}$ $\displaystyle\leq\frac{4}{\gamma}\left(4\|x_{k}-\bar{x}\|_{\Pi}+\frac{1}{2}M_{ l}\|R\|\right)\|x_{k}-\bar{x}\|_{\Pi}^{2}$ (C.6.94) $\displaystyle\leq\frac{4M_{l}\|R\|}{\gamma}\|x_{k}-\bar{x}\|_{\Pi}^{2}\quad \text{($k$ is sufficiently large)}$ (C.6.95) $$

∎

Proof of Theorem 4.5

###### Proof.

$$ $\displaystyle\|f(x_{k})-f(\bar{x})\|$ $\displaystyle=\left\|\int_{0}^{1}\left(\nabla f(\bar{x}+t(x_{k}-\bar{x}))- \nabla f(\bar{x})\right)^{\top}(x_{k}-\bar{x})dt\right\|$ (C.6.96) $\displaystyle=\left\|\int_{0}^{1}\left(\left.\nabla l(y)\right|_{y=R(\bar{x}+t (x_{k+1}-\bar{x}))}-\left.\nabla l(y)\right|_{y=R\bar{x}}\right)^{\top}R(x_{k+ 1}-\bar{x})dt\right\|$ (C.6.97) $$

(LABEL:eq:norm_f_val) is bounded above by

$$ $\displaystyle\int_{0}^{1}\left\|\left.\nabla l(y)\right|_{y=R(\bar{x}+t(x_{k}- \bar{x}))}-\left.\nabla l(y)\right|_{y=R\bar{x}}\right\|\left\|R(x_{k}-\bar{x} )\right\|dt$ (C.6.99) $\displaystyle\leq L_{l}\|R(x_{k}-\bar{x})\|^{2}\int_{0}^{1}tdt\quad(\text{by \eqref{eq:lipschitz_grad_l}})$ (C.6.100) $\displaystyle=\frac{L_{l}}{2}\|x_{k}-\bar{x}\|_{\Pi}^{2}.$ (C.6.101) $$

(LABEL:eq:norm_f_val) is bounded below by

$$ $\displaystyle\left\|\int_{0}^{1}\left(\left.\nabla l(y)\right|_{y=R(\bar{x}+t( x_{k}-\bar{x}))}-\left.\nabla l(y)\right|_{y=R\bar{x}}\right)^{\top}\frac{tR(x _{k}-\bar{x})}{t}dt\right\|$ (C.6.102) $\displaystyle\geq\left\|\int_{0}^{1}\frac{2\rho\|tR(x_{k}-\bar{x})\|^{2}}{t}dt \right\|\quad(\text{by strong convexity of $l$})$ (C.6.103) $\displaystyle=2\rho\|x_{k}-\bar{x}\|_{\Pi}^{2}\int_{0}^{1}tdt$ (C.6.104) $\displaystyle=\rho\|x_{k}-\bar{x}\|_{\Pi}^{2}.$ (C.6.105) $$

We are now ready to prove the theorem.

$$ $\displaystyle\left\|f(x_{k+1})-f(\bar{x})\right\|$ $\displaystyle\leq\frac{L_{l}}{2}\|x_{k+1}-\bar{x}\|_{\Pi}^{2}\quad(\text{by \eqref{eq:upper_bound_f_norm}})$ (C.6.106) $\displaystyle\leq\frac{8L_{l}M_{l}^{2}\|R\|^{2}}{\gamma^{2}}\|x_{k}-\bar{x}\|_ {\Pi}^{4}\quad(\text{by \ref{thm:local_quadratic_conv_iterate}})$ (C.6.107) $\displaystyle\leq\frac{8L_{l}M_{l}^{2}\|R\|^{2}}{\gamma^{2}\rho^{2}}\left\|f(x _{k})-f(\bar{x})\right\|^{2}$ (C.6.108) $$

∎

###### Lemma C.12 .

###### Proof.

###### Lemma C.13 .

###### Proof.

###### Lemma C.14 .

###### Proof.

###### Lemma C.15 .

###### Proof.

###### Proof.

###### Proof.

## Appendix D Numerical experiments

Throughout all experiments, the parameters of the algorithms were set as follows:

- •
HSODM: $(\delta,\Delta,\nu)=(10^{-3},10^{-3},10^{-1})$
- •
RSGD: $s=100$
- •
RSRN: $(\gamma,c_{1},c_{2},s)=(1/2,2,1,100)$
- •
RSHTR: $(\delta,\Delta,\nu,s)=(10^{-3},10^{-3},10^{-1},100)$

Here, we denote the dimensionality of subspace as $s$.
The time limit was set to 600 seconds only for classification with deep neural network, and 300 seconds for all other problems.

Dataset and other details of each task is described below.

### D.1 Logistic regression

In this task, all datasets were preprocessed as follows:

- •
10,000 features were selected to limit the problem dimensionality for the datasets with features more than 10,000.
- •
1,000 samples were selected to save the computational resource for the datasets with samples more than 1,000.

Here is a list of the datasets we used for this task.

##### news20.binary [ 18 ]

- •
Problem dimension: 10,001
- •
Source: [http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html](http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html)

##### rcv1.binary [ 26 ]

- •
Problem dimension: 10,001
- •
Source: [http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html](http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html)

##### Internet Advertisements [ 23 ]

- •
Problem dimension: 1,558
- •
Source: [https://archive.ics.uci.edu/dataset/51/internet+advertisements](https://archive.ics.uci.edu/dataset/51/internet+advertisements)

### D.2 Softmax regression

In this task, all datasets were preprocessed in the same way as D.1.

- •
For datasets with more than 10,000 features, the first 10,000 features were selected to limit problem dimensionality.
- •
For datasets with more than 1,000 samples, 1,000 samples were selected to conserve computational resources.

Here is a list of the datasets we used for this task.

##### news20 [ 25 ]

- •
Number of classes: 20
- •
Problem dimension: 200,020
- •
Source: [https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html](https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html)

##### SCOTUS [ 7 ]

- •
Number of classes: 13
- •
Problem dimension: 130,013
- •
Source: [https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html](https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html)

### D.3 Matrix factorization

In this task, no preprocess is performed. We chose $50$ as the feature dimension $k$. Here is the dataset we used for this task.

##### MovieLens 100k [ 15 ]

- •
Shape of $R$: (943, 1682)
- •
Problem dimension: 131,250
- •
Source: downloaded using scikit-learn []

### D.4 Classification with deep neural networks

In this task, we used 16-layer fully connected neural network with bias terms
and the widths of each layer are:

$$ $\displaystyle[\text{input dim},128,64,32,32,32,32,32,32,32,32,32,32,32,32,32, \text{output dim}]$ (D.4.1) $$

We utilized subsets of 1,000 images from each following datasets.
Here is a list of the datasets we used for this task.

##### MNIST [ 9 ]

- •
Input dimension: $28\times 28=784$
- •
Output dimension: 10
- •
Problem dimension: 123,818
- •
Source: downloaded using scikit-learn []

##### CIFAR-10 [ 21 ]

- •
Input dimension: $28\times 28\times 3=2,352$
- •
Output dimension: 10
- •
Problem dimension: 416,682
- •
Source: downloaded using scikit-learn []

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. In line 43 and line 168, the notation "subspace $P_{k}^{\top}\mathbb{R}^{s}$" appears. Could the authors please confirm whether this should be corrected to "subspace $P_{k}\mathbb{R}^{n}$" and ensure that the correct notation is used consistently throughout the paper?
2. In Table 1,  could the authors provide a legend or explanation for the symbols "1" and "2" in the Local column? This would help clarify the meaning for readers and improve understanding of the information presented.
3. In line 170, the normal distribution $N(0,1/s)$ is used, with variance chosen as $1/s$? Could the authors provide additional context or a reference to explain this choice of variance, as it would assist readers who may be less familiar with random subspace methods?
4. For equation (2.2.1), the reference to the "homogenization trick" could be expanded. Could the authors either provide a citation or briefly explain how this trick is derived such as Zhang et al. (2022)?
5. In line 184, the authors state that "unlike HSODM, RSHTR allows for other eigensolvers beyond the Lanczos method." However, the experimental section does not specify which algorithm was used for solving. Could the authors clarify this point?
6. In line 255, I understand that HSODM requires calculating $n+1$ Hessian vector products, resulting in a computational complexity of $O(n^2)$, while RSHTR requires $s + 1$ Hessian vector products. However, if RSHTR does not need to store the Hessian, why does HSODM require storing it?
7. In lines 318 and 360, could the authors clarify the relationship between the gradient norm and the relative function values? This would help in understanding why the complexities are expressed as $(n/s)^{3/4}$ and $(n/s)^{3}$.
8. In Algorithm 2, I noticed a difference in the stopping criterion compared to HSODM in Zhang et al. (2022). Could the authors elaborate on the equivalence of the stopping criteria used in both algorithms?
9. In line 1480 and below, the notation $\sqrt{\bar{H}}$ is not defined. Could the authors provide clarification on this notation?

**Reference**: Chuwen Zhang, Dongdong Ge, Chang He, Bo Jiang, Yuntian Jiang, Chenyu Xue, and Yinyu Ye. A homogenous second-order descent method for nonconvex optimization. arXiv preprint arXiv:2211.08212, 2022.

The article contains several typographical and punctuation errors that require careful review by the authors. For example:

- Line 28: "as follows. " should be "as follows:".
- Line 110: "Local" should be "local".
- Lemma 3.4, lines 728, 736, 741, Lemma B.3, line 1345, and so on: unctuation errors are present. I recommend that the authors conduct a thorough review of the entire paper. 
- Line 372 and 417:  "global_mode" should be "False".
- Line 1525: $\||A_3+A_4\||$ should be $\||A_3-A_4\||$.
soundness: 3
strengths: - The paper is well-structured and provides a clear presentation of the proposed algorithm. It establishes a strong theoretical foundation, presenting the first theoretical results for random subspace methods that demonstrate quadratic convergence properties for certain classes of functions.
- The experimental setup is appropriate, with sufficient comparisons made against existing methods. The results clearly illustrate both the practical convergence and favorable computational complexity of the proposed algorithm.
summary: This paper is primarily inspired by the HSODM method developed by Zhang et al. (2022) and extends their ideas to the domain of random subspace methods. The authors  propose a new approach called the Random Subspace Homogenized Trust Region (RSHTR) method. They establish global convergence guarantees under specific conditions and provide theoretical proofs for convergence to a second-order stationary point. Additionally, the paper demonstrates local linear and superlinear convergence under certain assumptions. Experiments conducted on real-world datasets confirm that RSHTR offers significant computational advantages and improved convergence properties over previous algorithms.

**Reference**: Chuwen Zhang, Dongdong Ge, Chang He, Bo Jiang, Yuntian Jiang, Chenyu Xue, and Yinyu Ye. A homogenous second-order descent method for nonconvex optimization. arXiv preprint arXiv:2211.08212, 2022.
weaknesses: - Despite the logical layout, the paper contains numerous typos and punctuation errors, which negatively affect readability and the overall presentation. 
- The paper mentions several constants (e.g., $C, c,\bar{C}, \bar{c}$) but does not provide detailed information regarding them throughout the text and appendix. It would be beneficial to clarify what parameters these constants are associated with, as they are likely not arbitrary values. 
- While the theoretical contributions are substantial, the authors note that it is also possible to provide theoretical guarantees by adopting a standard line search strategy in RSHTR to compute $\eta_k$.
- To enhance the practical significance of the theoretical guarantees, it would be valuable to include additional experiments, such as classification accuracy tasks, to further validate the algorithm's effectiveness. Nonetheless, the current experimental results are already quite strong. Additionally, Figure 5 in Appendix F is missing a title and legend.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: I would be interested in knowing the performance of the proposed algorithms with popular heuristics for training deep neural networks such as adagrad or adam.
soundness: 3
strengths: The main strength of the paper is present the first theoretical analysis of random subspace based trust region methods for non-convex optimization problems. The guarantees also match the best known guarantees for random projection based methods for non-convex optimization.
summary: This paper studies algorithms for solving unconstrained non-convex optimization problems of the form $\min_{x\in \mathbb{R}^n}f(x)$ for a non-convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$, in particular algorithms for finding an $\epsilon$-approximate first order stationary point. The paper considers algorithms that first pick a random small dimensional subspace of $n$-dimensional space and search for the best update direction in that subspace. The main idea of the paper is to develop a random subspace trust region method, and the paper is the first to give a complexity analysis for this class of methods. They show that their algorithm converges to an $\epsilon$-approximate first order stationary point with a global convergence rate of $\epsilon^{-3/2}$ iterations as well as local quadratic convergence under the assumption that $f$ is strongly convex. The main idea behind their work to make the analysis of random subspace trust region methods feasible is the minimum eigenvalue formulation based analysis of the trust region subproblem previous work of Zhang et al (this is a trust region based algorithm without random projections). This approach makes it feasible to analyze the effect of random projections in trust region based methods.
weaknesses: One minor weakness of the paper is that in the experiments section, the comparison of the proposed algorithm is not done with popular heuristic optimization algorithms such as adagrad or adam for experiments on deep neural networks.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - Choosing $s= \Omega(n)$ seems to be the recommended dimensional choice in practice. If one ignores the high-probability bounds, could one show a convergence guarantee in expectation for smaller subspace dimensions under the various assumptions?
- I am a little confused about the probability in the theorem statements of linear and quadratic convergence. Is it that you get a linear/quadratic decrease for a certain iteration with this probability, or is it that this holds uniformly over iterations with this probability? I suspect it's the former, but I want it to be clear.
soundness: 3
strengths: The main strengths of this work are reduced complexity, both in memory and computational time.  The high-probability bounds developed also point to a clear choice of dimension in $s\asymp \log n$. This is to make the probabilities vanishingly small in the dimension. The reduced trust region problem reduces to an eigenvalue problem, just as in past work by Zhang et al 2022, which can be solved efficiently in the lower dimension using standard methods. Overall, this represents an important addition to the nonconvex optimization literature.
summary: This paper offers an extension of current random subspace methods to  the Homogenized Trust Region method of Zhang et al. At each iteration, a random Gaussian matrix is sampled, and they use it to project the gradient and hessian. A trust region problem is then solved in the reduced space by an eigendecomposition. The theoretical analysis proves convergence to an $\epsilon$-FOSP in complexity $O(\epsilon^{-3/2})$, under the assumption of a Lipschitz gradient and Lipschitz Hessian. Under the further assumption of a low-rank Hessian at the output point, the authors prove convergence to an $\epsilon$-SOSP in complexity $O(\epsilon^{-3/2})$. Finally, under strict convexity, the authors prove local linear convergence, and under the assumption of a low-dimensional Hessian, the authors get quadratic convergence.
weaknesses: There are a few weaknesses to this paper. First, the paper should be made more clear. For example, in theorems 3.3 and 3.4, it is unclear what “sufficiently large $k$” means. If the authors could provide statements that make this more precise, that would make the statements of the theorems stronger.

Some things are introduced without proper motivation or definition. For example, what problem does 2.2.1 solve? I know that it somehow comes from the past work and solves a trust region problem, but the paper would be improved with further discussion to motivate the problem. 

In the section discussing overall complexity, the statements include an epsilon that references the later theorem on convergence to an $\epsilon$-FOSP. However, this theorem only applies under certain assumptions -- the authors should make clear in this section that they are examining complexity under these same assumptions.

Another weakness is that the theoretical innovations are not entirely clear. The authors should comment on the theoretical innovations within the text since proofs are pushed to the appendix. Is the theory just a mashup of Zhang et al. 2022 and the JL lemma, or is something more intricate involved?

The assumption of low-rankness in the SOSP and quadratic convergence results seem quite restrictive. While it may be necessary for the quadratic convergence, is Assumption 2 necessary, or is there some weaker condition that could lead to quadratic convergence?  A discussion of the proof techniques would help here.

Meta-review: This paper presents a random subspace trust-region-based method for addressing nonconvex, unconstrained optimization problems. The paper is well-structured and makes a clear contribution to the nonconvex optimization literature. The authors demonstrate, for the first time, locally linear and quadratic convergence rates under certain assumptions. Empirical results showcase the practical advantages of the proposed algorithm compared to existing methods. The reviewers recognized the novelty and significance of this work and raised only minor concerns regarding readability and clarity of the theoretical results, all of which were addressed by the authors during the rebuttal phase. Therefore, I recommend  acceptance  of this paper.

Decision: Accept (Spotlight)