Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization
Authors: Rei Higuchi
Pierre-Louis Poirion
Akiko Takeda
Venue: ICLR 2025 Spotlight (2025)
Keywords: random projection
trust region method
non-convex optimization
second-order stationary point
local convergence
Primary area: optimization
TL;DR: This paper proposes the Random Subspace Homogenized Trust Region (RSHTR) method with the best theoretical guarantees among random subspace algorithms for non-convex optimization.

Abstract: In recent years, random subspace methods have been actively studied for large-dimensional nonconvex problems. Recent subspace methods have improved theoretical guarantees such as iteration complexity and local convergence rate while reducing computational costs by deriving descent directions in randomly selected low-dimensional subspaces. This paper proposes the Random Subspace Homogenized Trust Region (RSHTR) method with the best theoretical guarantees among random subspace algorithms for nonconvex optimization. RSHTR achieves an $\varepsilon$-approximate first-order stationary point in $O(\varepsilon^{-3/2})$ iterations, converging locally at a linear rate. Furthermore, under rank-deficient conditions, RSHTR satisfies $\varepsilon$-approximate second-order necessary conditions in $O(\varepsilon^{-3/2})$ iterations and exhibits a local quadratic convergence. Experiments on real-world datasets verify the benefits of RSHTR.

Published as a conference paper at ICLR 2025
IMPROVING CONVERGENCE GUARANTEES OF RAN- DOM SUBSPACE SECOND-ORDER ALGORITHM FOR NONCONVEX OPTIMIZATION
Rei Higuchi -!.2, Pierre-Louis Poirion 12 and Akiko Takeda 11,2
Graduate School of Information Science and Technology, The University of Tokyo 2Center for Advanced Intelligence Project, RIKEN
ABSTRACT
recent years, random subspace methods have been actively studied for large-dimensional nonconvex problems. Recent subspace methods have im- proved theoretical guarantecs such as iteration complexity and local con- vergence rate while reducing computational costs by deriving descent direc- tions in randomly selected low-dimensional subspaces. This paper proposes the Random Subspace Homogenized Trust Region (RSHTR) method with the best theoretical guarantees among random subspace algorithms for non- convex optimization. RSHTR achieves an é-approxinate first-order station- ary point in ((e-3/( iterations, converging locally at linear rate. Fur- thermore, under rank-deficient conditions, RSHTR satisfies e-approximate iterations and exhibits lo-
second-order necessary conditions in cal quadratic convergence. Experiments on real-world datasets verify the benefits of RSHTR.
INTRODUCTION
We consider unconstrained nonconvex optimization problems as follows:
min f(x), zER"
(1.0.1)
where f R" + is a possibly nonconvex C function and bounded below. Nonconvex optimization problems often encountered in real-world applications, such training deep neural networks, and they are often high-dimensional recent years. Therefore, there growing need for nonconvex optimization algorithms with low complexity relative to dimensionality.
Recently, subspace methods have been actively investigated for problems with large dimension n; they compute the search di- rection each iteration on low s-dimensional space (i.e., < n), reducing the computational cost involved in gradient computation and Hessian matrices. Among these methods, the method using random projection, where the function f is re- stricted al each ileration k to subspace PTR" with the use of random matrix Pa R is referred to as random sub- space method. When finding the search direction at the it- erate Tki minjee- f(x; + Pe d) can be considered instead of mindeR= f(x, + d) in the random subspace method, and various solution methods can be derived depending on how a solution d is found.
X Øk-1
Figure 1: Illustration of our random subspace method R2, Each it- eration restricts the up- 1-dim. ran- domly selected subspace.
date
"higuchi-rei7140g. ecc. w-tokyo. ac.
'pierre-louis, ppierre-louss.piirioniieeeer poirionériken.
"takeda@mist. u-tokyo..aaae ac. akiko. takedadriken.

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of random subspace algorithms for nonconvex optimization. The SOSP column indicates whether the convergence point is second-order stationary point or not. The "Feas.' column indicates whether numerical exporiments were given, implying the implementation is possible. The number in the 'Local' column indicates the rate of convergence: 1 for linear, 1+ for superlinear, and for quadratic. The represents the condition that the Hessian al the local minimizer is rank deficient. The signifies that the objective function has low effective dimensionality. The indicates that in addition to the same assumption the previous work in v, this property holds under another assumption.
Underlying algo.
Subprob. cost/iter
Global
Local
SOSP
Peas.
Roberts & Royel (APPK]
Direct search
Multi. line-search
O(E 2
Zeroth order
Finite diff. grad.
0(e
Kozak
Zeroth order
Finite diff. grad.
0(e-2)
Kozak ef
Grad. descent
Gradient
0(s
1irtss pl
Gaus-Newton
Cond.quad.proo (QP)
((s-2)
Staan (4122]
Cubic Newton
Cond. rubic.reg.co QP
Ofe O(aa)/2) 8/2)
Zhan 0f A
Cubic Newton
Cubic.reg.QQ QP
O(e-3/3)
05 41
Reg, Newton
Solve eq.
O
Ours
Trust Region
Min eigenvalue
O(E 3/2)
Overview of existing random subspace methods: We can use ideas from existing optimization algorithms for dealing with min deR + I d), and various random subspace optimization methods have been proposed for convex optimization in e.g., Berahas et al
(2022); Gower et all (2mл)); @mshhhhnnkaa all (2122)); Lacotte & Pilanci (2n22); PPllaci &
Wainwright (20E)) Recently, some random subspace algorithms have started to be devel- oped for nonconvex optimization and the main ones related to our research are summarized in Table It may not be so challenging to construct a random subspace variant for each optimization method. What is difficult is to show that the sequence of iterates computed in subspaces converges with high probability to stationary point of the original problem. The derivation of the faster local convergence rate (e.g., superlinear rate) is complicated when it comes subspace methods. Indeed, Fuji et al. (2022) proved that even for strongly convex ʃ locally around striet local minimizer, we cannot. aim, with high probability, at local superlinear convergence using random subspace, even though the full dimensional reg- ularized Newton method allows it. Based on the above and the discussion in Section [+]] shown later, the following question naturally arises:
To what extent can theoretical guarantees be improved by performing gradient- vector and Hessian-matria operations in low-dimensions subspace?
Our research idea: Trust region methods are known to be fast and stable with excellent
theoretical guarantees. Nevertheless, with conventional methods of solving subproblems, it is challenging to develop a subspace algorithm with convergence guarantees. In fact, prior to a recent series of subspace method studies, Erway & Gill (2010) proposed a trust region method based on projection calculations onto a low-dimensional subspace, but there was no discussion of convergence speed. To the best of our knowledge, random subspace trust region methods with complexity analysis have not been developed until now. Only recently, a new type of trust region method was developed by Zhang et all (2022), and we realized that we could develop subspace variant with convergence guarantees based on this method. However, deriving local convergence rates is still tricky. The trust region method in Zhang basic minimum cigenvalue problem,
at (2022) treats the trust region subproblem which makes thcorotical analysis possible. This approach contrasts with the intricate design of update rules in the previous trust region methods and makes the theoretical analysis of dimension reduction using the random subspace method more concise.
Contribution: We propose a new random subspace method, Random Subspace Homog- enized Trust Region (RSHTR), which efficiently solves high-dimensional nonconvex opti- mization problems by identifying descent directions within randomly selected subspaces. RSHTR does not need to compute the restricted Hessian, 2V2 fx² E *xx making our algorithm more advantageons than other second-order methods numerically. It also has excellent. theoretical properties as in Table MI: more concretely,
2

---

Published as a conference paper at ICLR 2025
convergence to e-approximate first-order stationary point with global convergence rate O( (/2),, giving an analysis of the total computational complexity and confirming well as space complexity, improved over
that the total computational complexity, the existing algorithm (Zhang et all, 2022) in full space, convergence to second-order stationary point under the assumption that the Hessian at the point is ramk-deficient or under the same assumption as Shad (2122),
local quadratic convergence under the assumption on being strongly convex within its low effective subspace.
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 (Wi et all, 2020; Sagun et all 2017 2016; Ghorbani et all, 201)). Thus, our thcoretical guarantee considered important from a practical perspective.
1.1 EXISTING RANDOM SUBSPACE ALGORITHMS FOR NONCONVEX OPTIMIZATION
As summarized Table D. various types of random subspace methods have been proposed in recent years to tackle high-dimensional machine learning applications characterized by wver-paramettization.. Several papers (Hanzely et all 22120; Shad, 2022) investigate subspace cubic regularization algorithm. It can be noticed that Shad (2122) achieves the current best global convergence rate for a random subspace method of O(e-0/1 3/2) for a nonconvex function. Although it guarantees the convergence to a second-order stationary point under some strong assumptions the condition number and the rank of the Hessian around that point, it does not discuss local convergence rates. We also noticed a concurrent work (Zhao cf. all, 20221),, which was uploaded after finishing our project, ensuring the convergence rate of O(= 3/2) to second-order stationary point. However, their algorithm requires subspace size (2()) in general for the guarantee, which is larger than ours 8 = 2(log and leads to larger computation cost per iteration (see Theorem 572).
In contrast, the study by Fuji et all (2022) proves that a subspace variant of the regu- larized Newton method achieves linear local convergence in general and superlinear local convergence under the rank-deficiency assumption for the Hessian. However, the global con- vergence rate is limited O))-)), and they only guarantce the convergence a first-order stationary point. Other random subspace algorithms for nonconvex optimization include Roberts Rover (2023), where the algorithm converges first-order stationary points with 0(s-2) and the local convergence rates are not studied. A series of studies (Cartis et. all, 2022: 2023; Carlis Otemissovi 202T) assume the use of global optimization method to solve subproblems, and do not discuss local convergence rates.
Notations. We define I as the identity matrix. For related quantities a and B, we write (3) if there exists constant > such that < c3 for all 8 sufficiently small. We also write a = o(3) if lim a 3 = holds, and a = 2(3)) if 3 = (a). For a positive semi-definite matrix S, we denote by v5 its squared root, i.e., V
PROPOSED METHOD
2.1 EXISTING ALGORITHM: HSODM
Before proposing our method, we briefly describe new type of trust region method, a homo- geneous second-order descent method (HSODM), for the nonconvex optimization problem (L::));; ; see Appendix A for the details. One of the exciting points HSODM (Zhang ef all 2022) is that it uses eigenvalue computations to solve trust region subproblems (TRSs). The TRS is a subproblem constructed and solved in each iteration of the trust region method. 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 at- tracted much attention (see, e.g., Adachi et (2017); Lieden (2020)). HSODM is a method that incorporates the idea of homogenization into TRS and solves it by eigenvalue compu- tation in the trust. region method.
3

---

Published as a conference paper at ICLR 2025
2.2 RANDOM SUBSPACE HOMOGENIZED TRUST REGION: RSHTR.
Now we propose Random Subspace Homogenized Trust Region (RSHTR), which is an al- gorithm that reduces the dimension of the subproblems solved in HSODM with random projection and solves it by eigenvalue compulations.
For the sake of detail, we will first define by fr the function f restricted to low dimensional subspace Pk R (i.e., & n) containing the current iterate Fh, that is, Vu E IR,, (u( := f(r* + PT(2). u), using random matrix P3 E R where each element follows an independent normal distribution (O 1/s). Random Gaussian matrices Ps are sampled in- dependently at each iteration k. Using the notation 9a = (x(x) and H == V²S( we can write the gradient and Hessian matrix of fa as Đk- == Pagk: H& = P The tilde symbol denotes the subspace counterpart of the corresponding variable. Using the notation, the subproblem we need to solve at each iteration can be written as:
H L
9K -
(2.2.1)
where 2 0 is parameter appropriately selected to meet the desired accuracy. The relation between 8 and the accuracy will be shown in Section B. This subproblem lower dimen- sional version of the subproblem solved in Zhang et al (2022). We explain in Appendix A the motivation of the above subproblem. Similar to the subproblem solved in Zhang all
(2022), [2.2 can also be regarded as a problem of finding the leftmost cigenvector of matrix. Hence, (2.2.1) is solved using eigenvalue solvers, such as Lanczos tridiagonalization
algorithm (Golub & Van Loand 20*) and the randomized Lanczos algorithm [Kuczvński kowski 1992). The random projection decreases the subproblem dimension from + 1 to s 1. Therefore, unlike HSODM, RSHTR allows for other eigensolvers beyond the Lanczos method.
Using the solution of (2.2.] denoted by [ūk, tx], approximate the solution of the full- space subproblem by PP, 0k [x]. We then define the descent direction d, and the iterates update as
{ Tu/l/e if la 40 & rk+1 = { x da, if |d < A
Hb + mads, if d > A
dy :
(2.2.2)
P Tkg otherwise
In RSHTR, the step size selection fixed to 7) = A/||de]l, 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 Tk- The complete algorithm is given in Algorithm MI
As shown Section B, the output of our algorithm is an e approximate first-order sta- tionary point (s FOSP), i.e., it satisfies [[V] < O(e). If some assumption is satis- fied, it will be an E apaproxximate second-order stationary point (e-SOSP), i.c., it satisfies Amn (V) 2 (E- More precisely,
if the condition ||dell S A is satisfied, the algorithm can either terminate and output Tk+1, thereby obtaining an e-FOSP (or E-SOSP if stronger Assumption 0 holds), or reset = 0, fix the update rule to T = Fe + dę and continue, thereby achieving local linear convergence (or quadratic convergence stronger Assumption holds).
2.3 TOTAL COMPUTATIONAL COMPLEXITY AND SPACE COMPLEXITY
We also discuss the computational cost per iteration in Algorithm MI The main cost involving Ps and P is dominated by the computation of Hy for a vector in Line of Algorithm I. Indeed, we notice that it is not needed to compute the whole matrix P, H...P
It might seem to be more natural to describe |tx P instead ta o as HSODM (see Algorithm 2 for pure random subspace variant of HSODM. However, in the fixed-radius strategy, on which we focus (see (2222) ) even if we obtain theoretical guarantees for v E (0, 1/2), the results do not depend on v. Therefore, discuss the case with +0 for simplicity and clarity. Theoretical guarantees regarding a general are provided in Appendix Q
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 RSHTR: Random Subspace Homogenized Trust Region Method
1: function RSHTR(s, n. 8, A, mox_iterr
2: global Lacaalmmdee__ True
3: for k ==1,.... ,...,, max iter do
4:
Pk < 8 random Gaussian matrix with each element being from (( 1/8)
5:
9k Pagk
6:
(tu, Tx f optimal solution of (Z.2.1 by eigenvalue computation
dy + { Pe ün/la,
if lx +
7:
Pk Tk: otherwise
8:
if global mode and ||& A then
9:
7h <- dell
D or get from backtracking line scarch
10:
JR+1 + 2g m.
11:
else
12:
terminate or continue with (6, go.global__oee <- (0, False) for local conv.
13:
F6+1 2g dz
in order to solve the subproblem (A by the Lanczos algorithm. This can be done by computing the Hessian-veclor product V f²(x where we recall that fa( f( + Pk u). Assuming the use of the Hessian-vector product operation, we discuss below the computation cost of Line E, as well the total computational complexity of Algorithm M.
Assuming that the full-space Hessian-vector product can be computed in O(n) using back- propagation (see (Pearlmutter,, (ا93))), ) the lotal complexity of computing V (0)v becomes (sn).. Furthermore, Lanczos tridiagonallizttion algorithm solves, using a random initial- ization, (2.27)) exactly (Camb Xr Van Loam, 201, Theorem 10.1.1). The computational cost boils down to computing + matrix vector products. Hence, by using Hessian product, the computational complexity to solve (2.2.T) exactly is (s 1) O(sn) = =0 ())n). Furthermore, the iteration complexity, under the gradient and Hessian Lipschitz assump- tions (Assumption M) and the low effective setting (Assumption (]), is
-3/2) as detailed in Section K.ll Consequently, the total computational complexity of RSHTR in this setting is O0--8/2 3/2 g//2 ///nn 7/4)). On the other hand, the total computational complexity of the full-space algorithm HSODM (Zhang et al, 2022) is O(E 0(=-3/2n3) because the complexity of solving exactly the subproblem, using Hessian vector products, becomes O(n²). Therefore, when s o(n) (for example s (log (n))), the total computational complexity of the proposod method is smaller than that of HSODM. Notice that any case (for any value of s < n) the actual execution time of the proposed method outperforms HSODM. This is because HSODM's space complexity explodes to O(n²) due to the Hessian, whereas the proposed mothod's 's space complexity is limited to O(sn) laking into account that the random matrix is larger than the restricted Hessian.
THEORETICAL ANALYSIS
We analyze the global and local convergence properties of RSHTR. First, we show that RSHTR converges, with high probability, to an F-FSSP in at most O(E-3/2) iterations. Secondly, we prove that, under some conditions, the algorithm actually converges to e- SOSP. Lastly, we investigate local convergence: proving local linear convergence and, under rank deficiency condition, local quadratic convergence. Note that the analysis in this section is inspired by Zhang el al. (2122).
Assumption 1. f has L-Lipschitz continnous gradient and M M-Lipschitz continuous Hes- sian, that is, for all v, E RR,
VS(MI 1||=- vll. ( M| -
Here, assume the Hessian matrix is stored because rigorously evaluating the space complexity of the Hessian-vector product is challenging.
5

---

Published as a conference paper at ICLR 2025
To prove the global convergence property, we first state that when ||dy objective function value decreases sufficiently at each iteration.
A holds, the
Lemma 3.1. Suppose that Assumption D holds. If ||d > A, then for all > 0
f((x+1) - f((x)) S 2(yn/etoy A 6
with probability least 1 2exp(-s). Here C is an absolute constant.
The following lemma shows that if the descent direction once gel small enough, the norm of the gradient in the subsequent iteration is bounded using 8 and A. Lemma 3.2. Suppose that Assumption D holds. If ||dæll < A
2V2 then
Pr [lollll & 4A Tv Tw/n/8+C +C+
Vn/e-C ] 2 eexp (- - -2 exxp(-s).
AB
1 holds w.l.o.g. we want to take A as small as Notice that we can assume that A S 2v2 possible to ensure a better convergence rate. Next, we show lower bound on the minimum eigenvalue of the Hessian.
Lemma 3.3. Suppose that Assumplion D holds. If ||dall S A S
2/2' then we have
I
Pr = (( L + 6 +6) 2 2 exp (-C,) 2 eep A Although- Lemma Sm does not directly provide lower bound on the eigenvalues of Ha, it is proportional to the bound in Lemmaa 3.3 under certain conditions. We later discuss this
in Section 2
3.1 GLOBAL CONVERGENCE TO AN E FOSP
We now prove that our algorithm converges to an c-FOSP under a general assumption. Theorem 3.1 (Global convergence to an FOSP). Suppose that Assumplion holds. Leb
0 0<ES M² 8 8 ( c)² Ve and A
LE
(3.1.1)
M.
If there crists positive constant t such that s O(ne//T), then RSHTR outputs an E-FOSP in at most O (5-3/2) iterations with probability at least
4 (-Cs/ 4) (2U, + 2) exp (-s),
(3.1.2)
where and C are absolute constants and U = [3M² (f(xo) - infzer" f(x)) E 3/2
+ 1.
Theorem 1 leads to the following corollary on the probability bound, which is confirmed
by rewriting (5 as 1 4n
4n-Ce/3 Cc/4 (2U, 2)n with clog for some > Notice
that ( holds for a small value of if is large and is not too small.
Corollary 3.1. If s = n), then the probability bound [2)) in the order 1-
For comparison with the full-space algorithm HSODM (Zhang et alj 2022), when considering the dependency on n and s, the norm of the gradient at the output point is ((nns)((++))) This result is obtained by substituting the given parameters into Lemma 339 This is (2+)))))+) times worse than the HSODM. Since we want to obtain an F-FOSP in- we need to scale down E by ((n))))(2++))2) leading
stead of an the number of iterations increased by factor (n/s) 8 We have added some detailed explanations Appendix D33 just after the proof of Theorem J.I. This is the price to pay for utilizing random subspace.
We should emphasize that under the assumption low-effectiveness (Assumption H| intro- duced in Section (ee,, the exponent of the n/s factor can be improved to 3/4. Therefore, the total complexity of RSHTR becomes smaller than that of HSODM as discussed in Section 233 See Appendix D for more details.
As mentioned the footnote M, these results (essentially Lemma ( can also be demon- strated for any (0, 1/2), i.e., the similar statement also holds for the pure random subspace variant of HSODM shown in Algorithm H. Refer to Appendix C for the proof.
See Wainwright for more details.

---

Published as a conference paper at ICLR 2025
3.2 GLOBAL CONVERGENCE TO AN E-SOSP
Section [ demonstrated that RSHTR globally converges to an E-FOSP. In this section, we show that. the output x" of RSHTR is also an SOSP under one of two possible assumptions about the Hessian at the point, one of which is presented in Shad (2122). For clarity and
brevity, we move the result under the assumption from Shad (2022 in Appendix D while focusing on the more practical one in this section.
Assumption 2. Let r = rank V2 fxx)) for the output x² of RSHTR. We assume S
Notice that this includes many cases commonly observed in recent machine-learning opti- mization 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 (Wi all, 2020; Sagun et all 2017; 201;; Ghorbani et all, 2019). We also introduce some problems satisfying a stronger condition than Assumption 2 at the beginning of Section BaL Thus, our theoretical guarantee is considered important from a practical perspective. We guarantee in Theorem F that the output xx of RSHTR is SOSP when the Hessian at x=, denoted by H", is rank deficient. Before procoeding to the thcorem, we show in Lemma 3dl that the lower bound of the minimum cigenvalue of H is proportional to the or non-negative with high probability. Here pa denotes the matrix Pk used at the last iteration of the algorithm.
lower bound of the minimumn eigenvalue of H" p H**"
Lemma 3.4. Let Ô and ē be absolute constants". If Assumption & holds, then for all Ç > O, the following inequality holds with probability at least 1 (CC)* ------+11__- ca
Amin (H*) 2-5-2 (1- V(r 1)/s) min {Amin (P (P'HPP')).0)
This lemma implies that under Assumption 0 is sufficient to guarantee that the output of RSHTR is SOSP in full space it is SOSP in a subspace. Since the minimum eigenvalue of H is bounded as shown in Lemma k the following theorem holds.
Theorem 3.2 (Global convergence to an E-SOSP under rank deficiency). Suppose that Assumptions M and @ hold. Set e, 5 and A as in (B.I.)) of Theorem M. If there crists positive constant t such that s = O(nE!/T) then RSHTR outputs an E-SOSP in at most O (32) iterations with probability at least
1 6-6e (-Cx/4 (2U,- + 4) exp (-s) - exp ( 1-s+r-11 exp(-7s)
where ē and C are absolute constants and U: == 1 (f(zo) infzER 3/2 +1.
For comparison with the full-space algorithm HSODM (Zhang et a.l 2I2E when considering the dependency on n and 8, the minimum eigenvalue of the Hessian at the output point (2(-(n/s)VE) This is n/s times worse than the full-space method. In other words, the mumber of iterations required to achieve the same accuracy as the full-space algorithm is (n/s)² times larger. Unlike convergence to an F-SPS. convergence to an s-SOSP requires an additional assumption, Assumption R. The convergence guarantee to & SOSP is not easy because the algorithm run until the termination condition is satisfied, considering only subspaces, while convergence to e S-SOPP can be shown without any extra assumption thanks to Johnson- Johnson-Lindensteeeee Lindenstrauss lemma,, Lemma I Recall that other random subspace algorithms (Zhao et all, 2024 Shad, 20ze) also showed convergence to an E-SOSP, but Zhad dhal (20244 required the dimension of the subspace s to be Q(n) in general, and Shad (2022)
required stronger assumptions explained at the beginning of this subscction.
3.3 LOCAL LINEAR CONVERGENCE
In this section, we discuss the local convergence of RSHTR to a strict local minimizer æ. Here, we consider the case when continue to run Algorithm after ||d&]l < A is satisfied, by setting convergence analysis.
and loobal_mode = False. We consider a standard assumption for local
Assumption 3. Assume that RSHTR converges to a strict local minimizer T such that fz(z) = v
'We refer the reader
Rudelson & Vershynin (A00 for estimations on these constants.

---

Published as a conference paper at ICLR 2025
We denote the Hessian at E by H and introduce the norm | Vx Hr. This assumption
implies that for any 8 > O, there exists ho such that o[] [ S for Vk 2 ko.
Theorem 3.3 (Local linear convergence). Suppose Assumplions M and B hold. Then, for large enough, i.e,, there erists kn such that for all 2 ko,
Pr || x1l S V 4n(0M///s44C)
10x - I 2 21- (1-66xp(-o))
where x(iI)= = Amax (m))
Trust region method closely resembles Newton's method a sufficiently small neighborhood of local minimizer. Consoquently, expect that the impossibility of achioving local superlinear convergence for RSHTR in general can be shown, similar to Fuji et all (2022). Indeed, in order prove local superlinear convergence, Zhang el. all (2112) decompose the direction dę = d + where dx corresponds to the direction in a Newton step. In the subspace setting, this strategy would fail because the di part of the descent direction dy would hinder superlinear convergence, proved in Fuji et al. (2022).
3.4 LOCAL CONVERGENCE FOR STRONGLY CONVEX IN ITS EFFECTIVE SUBSPACE
We now consider the possibility of our algorithm achieving local quadratic convergence by making stronger assumptions than Assumption the function J. Concretely, we focus on so-called "functions with low dimensionality" 6 (Wang et all 2016), which satisfy the following condition:
311 R"*", Ilnk S n 1, s.t. E 12", -(
(3.4.1)
where 1I is an orthogonal projection matrix. These are the functions that only vary over low-dimensional subspace (which is not necessarily be aligned with standard axes), and remain constant along its orthogonal complement. Such functions are frequently encountered in many applications. For instance, the loss functions of neural networks often have low rank
Hessians Gur=Ari el. all (2I])); Sagun el all (2II7); Papvan (2018). This phenomenon also prevalent in other areas such as hyper-paraameeer oplimization for neural networks [Bergstra & Bengio, 2012,, heuristic algorithms for combinatorial optimization problems
(Hutter etl MTT)), complex engineering and physical simulation problems in climate modeling (Knight of all, 2011), and policy search (Eröhlich ot all, 2014.
Now show stronger assumption than Assumption 3 the function f.
Assumption 4. f has s-low effective dimensionality as defined in (5rew)) with an additional restriction rank([I) Furthermore, f is p-strongly convex within its effective subspace.
The assumption indicates that for R E Rrank(l)xn being matrix whose columns form orthonormal basis for Im[II,, the function ((y) == f(R y) is p strongly convex. To measure the distance within the effective subspace, we use the semi-norm ||ж]| = VIx Txl = || RR]
Now we show the local quadratic convergence property of RSHTR with parameters 5 and global_mode mode being reset to 0 and False, respectively, similarly to the local convergence discussion in Section S This is the first theoretical result of random subspace methods having quadratic convergence properties for some classes of functions.
Thcorem 3.4 (Local quadratic convergence under p-strong convexity effective subspacc). Suppose Assumptions M and @ hold. Then, for k large enough, i.e., there erists kn such that for all is 2 ko, the following inequalities hold:
Pr [[] ø||n S 4M|| 'mmia (RT) > =|[]] 2 30 - - e
Pr [((x+1) f(x)= < 8L p ommi (R (f(x)) f())) 2 -
where rIl, ē is universal constant, L1 and Mi are the Lipschitz constants of VI and 4 respectively, and æ is the strict local minimizer of f.
Theey also called objectives with "active subspaces' (Constantine et all 201 "multi- ridge' (Fornasier all 2012)
8

---

Published as a conference paper at ICLR 2025
102
function value
201
function value
1842 (s-202)
R5G3 (1-30)
10";
r=
RERN (c-100)
10-2
r=
(s:200)
10-2
r=100
800
RSHER (x-200)
r=150
REMTR (2-50)
10"1
300
500
500
1200
0
210
iterations
time
Figure 2: Log plot of the convergence of RSHTR on low effective Rosenbrock problems. The sub- space dimension is fixed at 100, and the prob- lem rank is varied (r = 25, 50, 100, 150).
Figure 3: The impact of the choice of subspace dimension (= 50, 100, 200) convergence in random subspace algo- rithms (RSGD, RSRN, RSHTR) for MF.
4 NUMERICAL EXPERIMENTS
We compare the performance of our algorithm and existing methods: HSODM (Zhang et all 2122), RSRN (Fuji al. 2122), Gradient Descent (GD), and Random Subspace Gradient Descent (RSGD) (oozak et all 20Z1). We used backtracking line search in all algorithms to determine the step size. Unless otherwise noted, the subspace dimension
set to 100 for all the algorithms utilizing random subspace techniques. In HSODM and our method, we solve subproblems using the Lanezos method. The numerical experiments were conducted in the euvironment: CPU: Intel(R) Xeon(R) CPU E5-2697 v2 @ 2.70GHZ, GPU: NVIDIA RTX A5000, RAM: GB. The details of datasets we used are provided in Appendix
Low Effective Rosenbrock function (LER): To illustrate the thcoretical properties proved in this paper, we conducted numerical experiments on a Low Effective Rosenbrock (LER) function, chosen for its property of satisfying Assumptions and This function is defined as min R(A Ax), where R(x) = Σx= 100( with n. We set 10000 to represent nign-ntieesioonll setting.
- and A E TR"xx
Figure shows experiments varying r with fixed s. When the rank deficiency r S holds, observe the predicted quadratic convergence. However, when 8, convergence slowed significantly. In Figure [5,, we set r = 50 (S $ = 100). The results show that the full-space algorithm did not complete even single step (and is thus omitted from the figure), while our algorithm outperformed the other algorithms, which supports the discussion in Section Ar Moreover, method surpasses the other random subspace methods, consistently achieving the fastest global convergence rate.
Matrix factorization (MF): We evaluate the real-world performance for MF us- ing MovieLens 100k (Harper & Konstan, 20E): minver xk VeRtxx. |UV - R (m.nn)) where R E x". and || denotes the Frobenius norm.
each algorithm. Figure & shows that despite varying s, the relative performance among these methods remained consistent, and no par- ticular method benefited from specific subspace dimensions. This finding justifies of a fixed subspaco dimension (s = 100) for all subspace methods in all the other experi- ments. Next, the performance of our proposed method compared against other algorithms, as shown in Figure Hr Although RSGD initially exhibits the fastest decrease, likely due to its advantage of not using the Hessian, our method soon surpasses RSGD.
We first examine the effect of changing
choice
Classification:
We test classification tasks using cross-entropy loss:
D My 5) log (x.) (x)(ott;))
minwer"
where N is the number of data and its label, K is the number of classes in the classification, (I,, Mi) is the i-th data, and (x,) = (o) (z.)..... ......... oK (x))) is the model's predicted logit. We explore the following specifie instances.

---

Published as a conference paper at ICLR 2025
GD
HSODM
RSGD (s=100)
RSRN (5= 100)
RSHTR (s=100)
Tunction calue
function value
$230
hunction
function
630
300
time
time
time
time
(a) LER (dim: 10,000)
(b) MF: MovieLens
(c) LR: news20 (dim: 10,001)
(d) LR: RCV1 (dim: 10,001)
(dim: 131, (50)
vake
function value
functin valuee
function
10C 200 Es!
150
330
1000
2000
2000
4000
4X55
00:0
1062
1906
time
time
(e) SR: news20 (dim: 200,020)
(f) SR: scotus (dim: 130,013)
(g) DNN: MNIST (dim: 123,818)
(h) DNN: CIFAR-10 (dim: 416,682)
Figure 4: Comparison of our method to existing methods regarding the function value v.s. computation time. Each plot shows the average + the standard deviation for five runs. A Algorithms that did not complete a single iteralion within the time limit are omitted.
Logistic Regression (LR): K= = and &y (xx,) w [m,;; 1] (with adaptation for the second
class). News20 (Lang. (835) and RCVI datasets (Lewis all 2003) were used.
Softmax Regression (SR): K 2 and A (x;) = w/ [myg 1]. News20 (Lang. (
and
SCOTUS (Chalkidss et all, 2021)) datasets were used.
Deep Neural Networks (DNN): (1;) represents the output of a 16-layer fully connected
neural network. MNIST Deng 2012 and CIFAR-10 (Krizhevsky. 2000) were used.
In all the experiments (Figures our algorithm outperforms existing methods. A notable feature of our method is its rapid escape from flat regions. This can attributed to the algorithm's second-order nature, the homogenization of the subproblem and the utilization of random subspace techniques. In addition, as discussed in the introduction, the rank-deficient assumptions (Assumptions and Bl reflect scenarios commonly encountered in modern machine learning optimization problems. Consequently, our method well-suited to applying Theorems 3.2 and 570
Fi.
1g Hin and additional ones Appendix G
FUTURE WORK
We proposed new random subspace trust region method and confirmed its usefulness thcoretically and practically. We believe that our proposed method can be made faster by incorporating various tochniques thcorctical guarantecs such as convergence rate are not required. For example, the parameter d is fixed, once and for all, at the beginning of the algorithm. In some future work, it would be interesting to develop an adaptive version of this algorithm where the parameter > O adapts to the current iterate.
Recently, authors of HSODM (Zhang et al, 2122 have been vigorously using the idea of HSODM to develop various variants ([e all KIZK of HSODM, application to stochastic optimization (Tannciaall (0²K), and generalization of the trust region method (Jiang et all, We want to investigate whether random subspace methods can be developed similarly. 2023)
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Satoru Adachi, Satoru Iwata, Yuji Nakatsukasa, and Akiko Takeda. Solving the trust-region subproblem by generalized eigenvalue problem. SIAM Journal on Optimization, 27(1): 269-291, 2017.
Albert S. Berahas, Raghu Bollapragada, and Jorge Nocedal. An investigation of Newton- sketch and subsampled Newton methods. Optim. Methods Softw., pp. 1-20, 2020.
James Bergstra and Yoshua Bengio. Random scarch for hyper-paramcter optimization. Journal of machine learning research, 13(2), 2012.
Coralia Cartis and Adilet Otemissov. A dimensionality reduction technique for uncon- strained global optimization of functions with low effective dimensionality. Information and Inference: A Journal the IMA, 11(1):167-01,, 2021.
Coralia Cartis, Jaroslav Fowkes, and Zhen Shao. A randomised subspace Gauss-Newton method for nonlinear least-squares. Workshop on "Beyond First- Order Methods in ML Systems" " at the 37th International Conference on Machine Learning. Vienna, Austria, 2020.
Coralia Cartis, Estelle Massart, and Adilet Otemissov. Bound-constrained global optimiza- tion of functions with low effective dimensionality using multiple random embeddings. Mathematical Programming, pp. 1-62, 2022.
Coralia Cartis, Estelle Massart, and Adilet Otemissov. Global optimization using random embeddings. Matherattcal Programming, 200:781 829, 2023.
Ilias Chalkidis, Abhik Jana, Dirk Hartung, Michael Bommarito, Ion Androutsopoulos, Daniel M. Katz, and Nikolaos Aletras. Lexglue: A benchmark dataset for legal language undorstanding in english. arXiv preprint arXiv:2110.00976, 2021.
Paul G Constantine, Eric Dow, and Qiqi Wang. Active subspace methods in theory and practice: applications to kriging surfaces. SIAM Journal on Scientific Computing, 36(4): A1500-A1524, 2014.
Li Deng. The mnist database of handwrilten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142 2012.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Kwassi Joseph Dzahini and Stefan M. Wild. Stochastic trust-region algorithm in ran- dom subspaces with convergence and expected complexity analyses. STAM Journal on Optimization, 34(3):2671-266) 2024. doi: 10.1137/22M1524077..
Jennifer B. Erway and Philip E. Gill. A subspace minimization method for the trust-region step. SIAM Journal on Optimization, (033):443-1166) 2010. doi:
Massimo Fornasier, Karin Schnass, and Jan Vybiral. Learning functions of few arbitrary linear parameters in high dimensions. Foundations of Computational Mathematics, 12: 229 262, 2012.
Lukas P Fröhlich, Edgar D Klenske, Christian G Daniel, and Melanie Zeilinger. Bayesian optimization for policy search in high-dimensional systems via automatic domain selec- tion. In 2019 IEEE/ RRSJ International Conference on Intelligent Robots and Systems (IROS), pp. 757 764. IEEE, 2019.
Terunari Fuji, Pierre-Louis Poirion, and Akiko Takeda. Randomized subspace regu- larized Newton method for unconstrained non-convex optimization. arXiv preprint arXiv:2209.0411 2022.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net opti- mization via hessian eigenvalue density. In International Conference on Machine Learning, pp. 2232-1222 2241. PMTR, 2019.
11

---

Published as a conference paper at ICLR 2025
Gene H. Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
Robert Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. RSN: Randomized Sub- space Newton. Adv. Neural Inf. Process. Syst., 32:616 6266,,622--002 2019.
Dmitry Grishchenko, Franck lutzeler, and Jérôme Malick. Proximal gradient methods with adaptive subspace sampling. Mathematics of Operations Research, (5(4):3303-1322) 2021.
Guy Gur-Ari, Daniel Roberts, and Ethan Dyer. Gradient descent happens in tiny subspace. arXiv preprint arXiv:1812.04754. 2018.
Filip Hanzely, Nikita Doikov, Peter Richtárik, and Yurii Nesterov. Stochastic subspace cubic Newton method. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 4027 4038. PMLR, 13-18 Jul 2020.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (Liis), 5(4):1-19, 2015.
Chang He, Yuntian Jiang, Chuwen Zhang, Dongdong Ge, Bo Jiang, and Yinyu Ye. Ho- mogeneous second-order descent. framework: A fast alternative to newton-type methods. arXiv preprint ar arXiv:231 1. 1.19489, 2023.
Frank Hutter, Holger Hoos, and Kevin Leylon-Brown. An efficient approach for assessing hyperparameter importance. In International conference on machine learning, pp. 754- 762. PMLR, 2014.
Yuntian Jiang, Chang He, Chuwen Zhang, Dongdong Ge, Bo Jiang, and Yinyu Ye. A universal trust-region method for convex and nonconvex optimization. arXiv preprint arXiv:2311.11489, 2023.
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.696 2014.
Christopher G Knight, Sylvia HE Knight, Neil Massey, Tolu Aina, Carl Christensen, Dave Frame, Jamie A Kettleborough, Andrew Martin, Stephen Pascoe, Ben Sanderson, et al. Association of parameter, software, and hardware variation with large-scale behavior across 57, 17,000 climate models. Proccedings of the National Academy of Sciences, 104 (30):12250-22264, 2007.
Shimon Kogan, Dimitry Levin, Bryan R. Routledge, Jacob S. Sagi. and Noah A. Smith. Pre- dicting risk from financial reports with regression. In Proceedings of Human Language Technologies: the 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 272 280, 2009.
David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. A stochastic subspace approach to gradient- optimization in high dimensions. Computational Optimization and Applications, 79(2):339 368, 2021.
David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Tenorio, and Silvia Villa. Zeroth- order optimization with orthogonal random directions. Mathematical Programming, 199, 2023.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Jacek Kuczyúski and Henryk Wožniakowski. Estimating the largest eigenvalue by the power and lanczos algorithms with a random start. SIAM Journal on Matrix Analysis and Applications, 13(4):1094-1122, 1992.
Nicholas Kushmerick. Internet Advertisements, UCI Machine Learning Repository, 1998. DOL:
12

---

Published as a conference paper at ICLR 2025
Jonathan Lacotte and Mert Pilanci. Adaptive and oblivious randomized subspace methods for sigh-dimensional optimization: Sharp analysis and lower bounds. IEEE Transactions on Information Theory, (8(5):3281-3300 2022.
Ken Lang. Newsweeder: Learning to filter netnews. In Machine Learning Proccedings 1995,
pp. 331-339. Elscvicr, 1995.
David D. Lewis, Yiming Yang, Tony Russell-Rose, and Fan Li. Revl: new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr): 361-397, 2004.
Felix Lieder. Solving large-scale cubic regularization by a generalized eigenvalue problem. STAM Journal Optimization, 30(4):3345-338 2020.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
Vardan Papyan. The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size, arXiv preprint arXiv:1811.0706,, 2018.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1): 147-160, 1994.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in Python. the Journal of Machine Learning Research, 12: 2825-2833 2011.
Mert Pilanci and Martin J. Wainwright. Randomized sketches of convex programs with sharp guarantees. In International Symposium on Information Theory (ISIT), pp. 921- 925, Piscataway, 2014. IEEE.
Lindon Roberts and Clément W. Royer. Direct search based on probabilistic descent in reduced spaces. SIAM Journal Optimization, 33(4):305733082, 2023.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1733 2009.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical anal- ysis of the hossian of parammaaattri neural networks. arXiv preprint arXiv:1706.044 044544 2017.
Zhen Shao, On random embeddings and their application to optimisation. arXiv preprint arXiv:220.00377,, 2022.
Jiyuan Tan, Chenyu Xue, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. A homogenization approach for cradient-dominan stochastic optimization. arXiv preprint axXiv=2311.11488) 2023.
Roman Vershynin. High-dimensional probability, volume 47. Cambridge university press, 2018.
Martin J. Wainwright. Basic tail and concentration bounds, pp. 21 57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hes- sian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020.
13

---

Published as a conference paper at ICLR 2025
Yinyu Ye and Shuzhong Zhang. New results quadratic minimization. SIAM Journal Optimization, 14(1):245-25) 267, 2003.
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.082122 2022.
Chuwen Zhang, Dongdong Ge, Chang He, Bo Jiang, Yuntian Jiang, Chenyu Xuc, and Yinyu Ye. A homogenous sccond-order descent method for nonconvex optimization. arXiv preprint arXiv:2211.0811255, 2024.
Jim Zhao, Aurelien Lucchi, and Nikita Doikov. Cubic regularized subspace newton for non-convex optimization. arXiv preprint arXiv:2406.16666 2024.
14

---

Published as a conference paper at ICLR 2025
A EXISTING WORK: HSODM
Homogeneous Second-Ordes Descent Method (HSODM) proposed by Zhang et al 221 is
a type trust region method, which globally converges to an E-SOSP at a rate O 3/2) and locally converges at 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 described below.
At each iteration, HSODM minimizes the homogenized quadratic model. In other words, it solves the following subproblem:
min [[at]ls
H 9k
Jk -
(A.0.1)
where 5 2 parameter appropriately determined according the required accuracy. The motivation behind is to force the Hessian matrix H& to have negative curvature. To do that (see Ye Zhang (2Ix))) ), we homogenize the second order Taylor expansion, my(d), of f(x + d):
mi (d) 9x d =at Hgd.
By rewriting d= we have
2 (ma(d))
15) 25) =
(w/t) + (w/1)) Ha(o/t) - 1 20
1
1
tgg
HEU
2 5t2
2
v 1
H
9k
9k
-8
1
Notice that (A. can be regarded problem of finding the leftmost eigenvector of a matrix. Hence, the randomized Lanczos algorithm (Kuczynski & Wozmakkwski [992) can be utilized to solve (I.. The solution of (I. is denoted by /xktt)]. Using this solution, HSODM calculates the direction as follows:
di =
uk Uk/tk, sign(- -b UR)UK
if 14 >
if [
S
where (0,1/2) is arbitrary parameter.
Then, the algorithm updates the iterates according to the following rule:
26 + meds. {
if
F A
1k+1
Th de,
if
<A-
Here, TJ denotes the step size, and E [0, 22/2 is parameter set to the appropriate value to achieve the desired accuracy. Tf the first condition || A is met, the step size be either set to пı A/IldF |I or determined by line scarch. If the second condition ||d[] A is satisfied, this algorithm can either terminate and output #x+1, thereby obtaining an e and continue, thereby achieving local quadratic convergence.
SOSP, reset both ô and These steps are shown in Algorithm 2
B PREPARATION OF THE THEORETICAL ANALYSIS
B.1 EXISTING LEMMAS
We introduce two important properties of random projections. The first property is that random projections approximately preserve norms with high probability. Formally, the following Lohnson--Lindensrraue (JT.) lemma holds:
15

---

Published as a conference paper at ICLR 2025
Algorithm 2 Homogencous Second- Order Descent Method (HSODM) (Zhang et all, 2022
1: function (SODM(n, 6, A, max iler)
2: for k= = 1,.... max iter do
3:
(tx, 2k -- solve_ suabr___bbpoollmmggg Hg, 6)
Uk/tR,
if [tx]
4:
dg sign( 9 ūk)oR.
otherwise
5:
if
||d || A then
6:
7k < / de
Di or get from backtracking line search
7:
Fk+1 26 na
8:
else
9:
Th+1 f- 26 dx
10:
terminate
b or continue with (6, + (0,0) for local convergence
Lemma B.1. [Lemma 5.3.2 in [Veshyndrd (АU]) Let P E g be random Gaussian matrix and C an absolute constant. Then, for any æ E R" and any & E (0, 1), the following inequality holds with probability at least 2xx (-C
(1 - <) || & |x = (1+ E) ||=|||
The second property is described by the following lemma, which states that PT is an ap- proximate isometry with high probability.
Lemma B.2 (Theorem 4.6.1, Exercie 4.6.2, 4.6.3 in Vershynin (20T8)) Let P Rexn be random Goussian matrix and C be an absolute constant. The following inequality holds with probobility at least 1 - (exp(-s).
(V=-c) |alll S
|| m/ - (v +C) ||all-
Vy E
We recall the following lemma from Nesterod Lemma B.3. Suppose Assumption 0 holds. Then for any 2. y E RR" we have
L 1ly x1?
ff() (f)=))
.
[V - - v2) x) -
2 11y x||
(V r) T 22 f())(v 1) M lly x113. (B.1.1)
- f(x) (()))-/())(()))))) [1)
B.2
THE OPTIMALITY CONDITIONS OF THE DIMENSION HIMENSION-REDUGED REDUCED SUBPROBLEM
We recall the fundamental property in probability theory. For any events E₁ and Eg, we have
Pr[Ein 2 1 1 (1-
Pr (x)))
This is used throughout this paper without further explicit mention. The optimality ditions of the dimension-reducel subproblem (2.2.) are given by the following statements: there exists non-negative random variable such that
(Fi 0xT))
(B.2.1)
tx
F A 0,
(B.2.2)
0, (1] tx]ll - = 0.
(B.2.3)
where
H2
F
-8
16

---

Published as a conference paper at ICLR 2025
It immediately follows from (B.2.2 that
Amin (F&) 2 -0k-
(B.2.4)
We also obtain from B.2.2
8 S 0k:
(B.2.5)
by considering the direction [0....,0, 00,1
We directly deduce the following result from Corollary B.1. (B.2.1) implies the following equations
(Ilx + 0x1) Uk tt.9k
(B.2.6)
9k Uk tk (6 0k))
Purthermore, 44 =0, O, then
(Ax + 0c1) ox = O,
(B.2.7)
0 U/ 0
hold. Tf l # 0, then
T Ub
9k ts
6 Ox.
(B.2.8)
( + 0g
(B.2.9)
tk
hold.
We also obtain a slightly stronger inequality 5 < 02 under an additional condition. Lemma B.4. If gl 0, then ō Og holds with probability 1.
Proof. We first prove the following incquality:
Amiul (Fx) -8.
(B.2.10)
To prove this inequality, it suffices to show that Fi + 81 has negative curvature, Let us define
1gg -nga f(n.1) -ngk (Fx 61)
t
= 12 Dk (Hx + 81)): - 229 ||
Then for any fixed > 0, we have
0f(0,t)
f(0,t) =
On 22
Since # 0, we have || * 0 with probability 1, which implics 05(0.)) < 0. Thus, for by
sufficiently small 77 > O, we have that f(),t) < 0. This shows that F& + 81 has negative curvature. Finally, by combining (B.2244 and 10), the proof is completed.
C PURE RANDOM SUBSPACE VARIANT OF HSODM
Unlike the pure random subspace variant of HSODM RSHTR excludes the parameter present in HSODM. This exclusion is because our theoretical analysis in the fixed-radius strategy, which we focus on, does not depend on p. Therefore, we discussed it under + +0 for clarity. This section discusses that similar theoretical guarantees can be provided for any E (0, 1/2) as in the case of D +0.
'Here, we cite the algorithm used in Zhang et all (2122) Notice that in the newest version, Zhang et all (2021). the stopping criterion is written differently, but it is equivalent to the one in Zhang
17

---

Published as a conference paper at ICLR 2025
Algorithm 3 Pure random subspace variant of HSODM
1: function RSHTR(s, n, 6, A, max 11,_mae_ett iter)
2: global _oode__dee-_ True
3: for k =1,... ,...., max iter do
4:
Pk < 8 x n random Gaussian matrix with each element being from (o 1/8)
5:
Ok Pagk
6:
(tu, 8k + optimal solution of 2 by eigenvalue computation
7:
(āk: HR, 6)
dx + { PE Ux/tk,
if 4 > otherwise
8:
sign( - 9h Uk
PR Uks
9:
if || || >> then
10:
d&
or get from backtracking line search
11:
Tk+1 - Ti da
else
13:
Tk+1
+ 26 + dx
terminatc or continue with (6, v, gllbbllmodde + (0, 0, False) for local
conv.
C.1 ANALYSIS ON FIXED RADIUS STRATEGY
Here, we consider the case fixed step size, A. When It&l <v, dz given by dN P ūx. Lemma C.1. Suppose that Assumption D holds. Let v E (0,1/2), dz = Pe 0s and me = A/lldxlI. If ttll v. Iu # 0 and ||dull > A then we have
1
M A 28
f(xx+1) f(xx))
2(vn/8+ C)2
with probability least 1- 2exp(-s)
Proof. By Corollary we have
oo Hg = =00 11 2
U Dk.
(C.1.1)
ū2 9k t5 0x)-
(C.1.2)
Since we have 5 0% with probability from Lemma follows that
sign 0k) = sign(ts)
(C.1.3)
with probability 1. Therefore we obtain
d Hyds 0f HuōE (by definition of dx.
=-0xl Tn 2 1u0% Ir
(by (C.II)
0& 0y 2 th 8) (by (M)
(C.1.4)
ge d+ = sign( -1. 8% Tz) Öx (by definition dy)
= sign(  in tx 0x) (by (M
|txl(6 Ax) (by
(C.1.5)
Since ||da|| A, it follows that Th A/ |d (0, 1). Thus, have m - 1 0. Hence
1k
(8 0x) -
(C.1.6)
2
18

---

Published as a conference paper at ICLR 2025
Algorithm 4 Backtracking Line Search
1: function BACKTRACCKLINESEERRCCIC...dd
0, (0.1))
2: 77 =1
3:
for Jk 1..,... do
4:
if f( + +ndd)) - f(xx) - 1 then
5:
return T]
6: else
7: 7h + 3Tπ
Hence, the following inequality holds with probability at least 2 2exp(-s).
f(02+1) f(xx) f(æx + mkdx) - f(xx)
nh9 dx + 1i2
M
d Hadk +
The
nd
(by
2
6
Th
The (5 0x) +
M
=n - 0x)
0x
Mis
|d
(by (.144 and
2
2
6
mohi(0 - 0%)
1
2
1l
Tk (6
2
0u) +
M
The
3
dx ||
(by 0 Hul 1)
6
-(T 11k
1
(6
0n)
nh 0x |6 1
M
melld ||
me
2
M
S
||
1e
nh
(by
(C.LG)
2
Th On
1
M
||dx|1
+
de
(by Lemma 62
2
(Vn/s Ccy
6
M
A78 +
(by 12.5 and 1/2 A/I(del).
2(Vn/s+ C)2
This completes the proof.
We now consider the case where [tl > v. In this case, de is given by d2 P. 0p/tu. Since
Itul 2 y implics t * O, we have the following result by using the same argument as the proof of Lemma DE
Lemma C.2. Suppose Assumption M holds. Let da 0x/tk. If ltal 2 || A and
7 = A/||d=l, then
M A
- ( - 2(/n// C)2
A
6
holds with probubility least - 2exp(-s)
By Lemmas Cal and C.2, we can state that, when ||dall > holds, the objective function
value decreases by at least 2(yn/e-oy= 2 A at each iteration, with probability at least 2 2cxp(-s).
C.2 ANALYSIS CONSIDERING A LINE SEARCH STRATEGY
In this subsection, we analyze the case where the step size is selected by the line search algorithm shown in Algorithm H. Specifically,
show that Algorithm El guarantees sufficient decrease the function value, similar to the fixed step size case. As in the previous subsection, we consider the cases |41 < and [t > v separately, providing a guarantee of function value decrease for each case (Lemma Ce and Lemma Cd respectively).
Lemma C.3. Suppose that Assumption M holds. Let v E (0.1/2), [t&l < v, de
sign(-0) 0g ix) P.T Te, 3 E (0, 10, 0, and nh be chosen by Algorithm g Then, with probabilily
19

---

Published as a conference paper at ICLR 2025
at least - 2 exp(-ss) the number of iterations of Algorithm is bounded above by
(V=+)) 1.
logg
M
and the decrease in the function volue is bounded as follows:
v3r
3 (V=
nn
9y3383
f(xx+1) - f(æx)= - min
16
2(M 7)) (V////+++++++>
Proof. Let ja be the number of iterations at which Algorithm stops in the k-th outer iteration. If the line scarch terminates with Ia = 0, i.., a = 1, then
f(ox + mxdx) f(xx)= - 2 ||dal
2
Px 1
(V n
c)
| l|
(by Lemma B.2
v3y
(v=-
c)
(since
|6,||
tt 2 2 V -1-22 v3/2).
16
Let consider the case where Algorithm MI does not stop at the j-th > 0) iteration. Then f(x + mxdk) - f(x*)= - 2
n dx d Following the proof of Lemma CAI we have
- - n2 < (ark + nz [(xx)
c
0x
n
+
-2 ||dx]| +
M
m
2
6
1 mh
-2
M
+C
||dR 112 +
The
| 1
(by [
6
This implies 7/k > (M dd (VT+C) 2
and j logg [ (C)+
Since ||du|l = IP uell S (V+ |ل < (V3 + C) due to Lemma BV and
| < 1, the number je of iterations where Algorithm stops is bounded above by
log, M+7 (VT + C) +)) Moreover, the decrease the function value can be bounded
34
as follows:
f(rx + mede) - f(xx) S
6 mK |
7 7n
7 3ز5n ||
6
9y
2(M 73)3 (nns+
where the last. inequality follows from 8 d (V +C)+ used only Lemma B.22 as a probabilistic result, the probability that this proof holds is at least 1 exx(
Note that since we
Lemma C.4. Suppose Assumption D holds. Let E (0,1/2), [tal 2 v, dx = PT Bx [[ 2 3, E (0, 1), > 0, and Th be chosen by Algorithum Then, with probubility at least - 2 expp 8), the number of iterations of Algorithm g is bounded above by
M + (vT +C) )
36v
log,3
20

---

Published as a conference paper at ICLR 2025
and the decrease in the function value is bounded as follows:
f(xx+1) - f(xx)) S min A
97
2(M + (MM=))(Vn//++
Proof. Let Jk be the number of iterations at which Algorithm B stops in the k-th outer iteration. If the line search terminates with jk = 0, i.., 7 = 1, then
[xx + mada) [(xx - 2 ldx1
2 (since || 2 A).
Let us consider the case where Algorithm @ does not stop at the j-th (j 2 0) iteration. Then
f(x + mxdx) f(xx) 3 m da [ و| Following the proof of Lemma O we have
2 1d2ll 1 < fx + mx f(1*))
1 0x
M
1
C
||
11
2
-2
M
+
C
||d 11 +
The d
(by (B25
6
35 This implies 7 (M Iddall
(V + C) - and j < logg [M+>)] (VT +C)+ There-
36
fore, je, the number of iterations where Algorithm A stops, is bounded above by
log, M+7 (v CC)
35v
-3) ] Here, we have used the fact that
Uk Pk
||da|
LE
(by
Lemma
B2
[EA
VI
ltul?
[ta|
1
(since [t&] 2 v).
The decrease in the function value can be bounded as follows: f(xx + meds) - f(xx) <
7 mk d
6
gy
2(M - (V/6
where the last inequality follows from G 2 +M+ used only Lemma B. a probabilistic result, the probability that this proof holds is at least 1 - exx(
38
Note that since
From the above lemmas (Lemmas and O we can bound the number of line search iterations and the decrease in the function value for general ig as follows.
Corollary C.1. Suppose Assumption holds. Let 102), B (0,1), 0, 0, and > O. Then, with probability al least 1 (exp((s), the namber of linesearch ilerations of Algorithm g is bounded above by
35v
(
logg
M +
and the decrease in the function volue is bounded as follows:
v37
A
97,3883
f(zx+1) f(xx) S min
C)
16
6
2(M + 7) Wn
21

---

Published as a conference paper at ICLR 2025
D PROOFS FOR THEORETICAL ANALYSIS
D.1 ANALYSIS OF THE CASE WHERE | A
Let us consider the case where [|dx]] > A and evaluate the amount of decrease of the objective function value at each iteration (Lemmas D and D22, leading to Lemma I. Note that, under ||d > A, the update rule is given by
1k+1 Tk + mAdk:
7/ dell
First, we consider the case where & = 0. this case, dx given by ds P ok-
Lemma D.1. Suppose that Assumption M holds. Let dx = Pk on and me = A/||dell- If & 0. # and | A then we have
A + M A f(xx+1) f((x)) S 2(vn/s+
6
with probability at least 1 - 2 2exp(-s))
Proof. By tg and Corollary B
have
0y Ugg =0
(D.1.1)
0y Iz = O.
(D.1.2)
Therefore we obtain
dg Hyds 1hf Ha (by definition of dz)
0002l 0x (by (D.LI))
(D.1.3)
9& ds = sign(- Th En gg on (by definition dx)
=0 O (by (D.L2)
(D.1.4)
Hence, the following inequality holds with probability at least - 2exp(-ss.
f(x+11) - f(xx) = f(xx + medk) - f(*x)
1/ d Hads
m de +
+
de
(by
2
6
nh
M
On || Txll
11
#+
1d
(by
and
2
6
mhe 0x
1
M
||d
|d (by Lemina B.
(Vn/s
C)2
M
A28 +
A
(by 1 and 7e = A/|ldal)).
2( Vn/ C)2
This ends the proof.
Next, we consider the case where tu # O. In this case, d2 is given by dy = P Ux/tz.
Lemma D.2. Suppose Assumption D holds. Let di P. ūn/tu. to + O, ||daall A and
7 = A/||d=ll, then
1
M 3 278
( S 2(/n/8 C)2
holds with probability at least 1 2exp(-s)
22

---

Published as a conference paper at ICLR 2025
Proof.
Since to + 0, obtain from (B.2.9
Uk
11
9k
Hk
Bx
(D.1.5)
tk
tw
tx
tk
Therefore, it follows that dg
Hyds
HR
tx
tk
|| 1i 11
Te U2
00
(by D
12
LE
|| |1 11
0g
9k dk
(by definition of dx),
(D.1.6)
9k d2 = 8 0F (by (1B228))
S (by
(B.2.5)
(D.1.7)
Since My = A/lldall E (0, 1), we have 77s
n//22 2 0. Thus we obtain
The
9k d 5 (by
(D.1.8)
2
Therefore, the following inequality holds with probability at least - 2 eex((-s)
[(*++1) f(xx) f(xx + meds) - [(0k)
Th dx Hyde
M
S nn dx +
+
The
3
(by
(B..II
2
6
vi
|
M
nk9 de +
0k
9k
de
+
nilld
||
(by (D
2
17
11x
9k
d2
Vlk
0R
1 1
M
mi
d
11
2
2
1k 0g
1h 1|
M
7h
||
(by
(D)
2
t
6
1 Ok
1
||
M
d
|
(by Lemma B.2
2
(vn/s C)2
M A3
2
(by B225 and mh A/lldal)).
2( n//s C)2
By Lemmas I and D2 we can state that, when ||dall > A holds, the objective function
value decreases by at least 2(yn/s+e) A M A each iteration with probability least
1 - 2exp(=x)) This proves Lemma 3T1
D.2 ANALYSIS OF THE CASE WHERE ||da| SA A
Now we consider the case where RSHTR satisfies [|de|| A the k-th iteration and outputs Jk. To investigale the properly of Tk, analyze ||g=|| and Amin (Hx).
We first derive an upper and lower bound on the eigenvalues of V2 fxx).. Lemma D.3. Suppose Assumption holds. Then for all a E R".
Amin (22 2 -L,
(D.2.1)
X Xmaxx (V2((x) <
hold.
23

---

Published as a conference paper at ICLR 2025
Proof. Let be unit eigenvector corresponding to the smallest cigenvalue. By definition of fxz), we have
VS(x + hv) Vf(x))
f()())
lim h-0
h
To bound the right-hand side, we use the L-Lipschitzz property. We obtain
IV + hv) vf())
lim
400
h
T.|/|||-
[/]]
Finally, since [z))|l = Aminn (V2 of the second inequality is similar. (z)(()))]lll)) we obtain Amin (ainn(V((x))) -L. The proof
Next, we derive upper and lower bounds on the eigenvalues of Ak
Lemma D.4. Suppose Assumption M holds. Then we have
- -
-(V n
Amin (Ak) 2
+
L
(D.2.2)
2
Amax (Hlx) v
(1
71
+
L
(D.2.3)
with probability at least 1 - -2xpp(-00 -s).
Proof. Let us consider the first inequality. Let E { R
H4 0}. Then have
T H
Amin (Hx) 2 min
0,
min SEB
(D.2.4)
|
By Lemma
2 we have
| :112 & v + c) |
(D.2.5)
with probability at least. 1 - 2 2exp(-x0 -)). Therefore, we obtain
min 0, min ZEB
T
Hyæ
71
+
C
2
min
min SEE
P&HAPPT
(by (D.2.
|
[P 2112
n
+
C
2
min
0. min
x. H
(by Im(PP)) c CR")
||~|||
2
+
C
min {0, Amin (H+)}
2
+
C
L (by (D2.11)
Hence, by (D2.4.) the first inequality The proof of (D.233 similar.
(...22 holds with probability at least 1 - 2exp(-s)
Using this lemma, we can derive an upper bound on [|gH]]-
Proof of Lemma 32
Proof. Notice that by Lemma
Tk Pegk Had 0
to
24

---

Published as a conference paper at ICLR 2025
Hence, by Lemma [. and B.2 deduce that with probability at least 1 - 2exp (- 2 2exp(-8),
n CA +2
O
|1 S 2
A.
Furthermore, by (B.99 we have that
02 S 6 1
Therefore, we have
(1-
2
A8
11 24
L W
+C+
Vn/8
Vn/s
Combining with A <
2/2' we deduce that
2 |g S 22
n +C+
A8
Vn/s
which completes the proof.
We can also derive bound on Amin (Hx).
Proof of Lemma
Proof. By B.2.2 and Cauchy's interlace theorem, we have Hl + Ox! O. With (D.33 and Lemma follows that
((v
n +c) L L +
2 842
with probability at least
- 2 eex
()) 2cxp (-s). This implics
H 2 812 (v
2
n
c
I 8 1 + 8
D.3 PROOF OF THEOREM
Proof. Let us consider how many times we iterate the case where Idal > A at most. Ac-
cording to Lemma DJ and Lemma D.2 the objective function decreases by at least
g//2
25
2 Vn/s++0
(
3M2
with probability at least. - exp (-8). Since the total amount of decrease does not exceed D := f(xo) inf f(x), the number of iterations for the case where ||d& > A is at most D with probability at least 1 2|3M² De-3/2 exp (-s). Also, since the algorithm terminates once it enters the case ||&ell < A, the total number of iterations is at most U. = 2 De 3/2
+ at least with the same probability as the above.
We can compute an e-FOSP with probability at least 1 - cxp (-Q 4exp (-8), which can be easily checked by applying Lemma 1 to the given ô and A.
Therefore, RSHTR converges in 13M2 3/2 + = 0(5-3/2) iterations with probability at least.
1 1-2|3M22 3/2 exp (-s) cxx (-C.)
-4exp (-s)
(-C) ( - (2U, + exp (-s).
-
25

---

Published as a conference paper at ICLR 2025
Algorithm 5 RSHTR (modified)
1: function MODIFIED RSHTR(s;, (1, A, max iter)
2:
global_ @oobal_mode_ True
3: for k = I..... max iter do
4:
random Gaussian matrix with each element being from (O, 1/s) ÿk + Paal
Ps x
5:
6:
(fx, 8k) + optimal solution of (2.2.1) by cigenvalue computation
da <- { u if t # 0
7:
Pk Uk. otherwise
8:
if global mode and ||d > A then Th + A/|ldell
9:
or get from backtracking line search
10:
x++1 + 26 Mx
else
12:
2k+1 + 2か + d2
13:
terminate or continue with (ó, go.globa__mode <- False) for local conv.
Notice that by Theorem and Lemma 592 we obtain that
11 || I (mmsss))22t)))3
where k* denotes the last iteration, k; where ||de|] > A. Therefore, order to obtain an e- FOSP; we need to scale down by (n/s)(2+7)4 We obtain therefore an iteration complexity of
-(2++)/2 (
3/2
)
- ((
(6+3r)/1 -3/2
This has (n/s) times the iteration complexity compared to full-space algorithm. Especially, when t is sulficiently small, becomes almost (n/s)a/2 times.
D.4 IMPROVEMENT OF ITERATION COMPLEXITY UNDER THE ASSUMPTION OF LOW-EFFECTIVENESS
In this section, we show that the total complexity is improved under the assumption of low- effectiveness (Assumption algorithm is shown in Algorithm E The difference from the original Algorithm M is that the algorithm updates x before stopping after the algorithm satisfies the stopping criterion. In order to evaluate the gradient norm at the output point, we first introduce the following lemma
and the slight modification of the algorithm. The modified
Lemma D.5. Assume that satisfies (B..I) and assume that 2 rank(IT). Tf
t * 0, d2 = PTT ūx/t (/dall & A, then we have
8A + 1
HHud + gull
< (11- m-1 Vn/s
with probabilily least 1 2exp (- 2 2exp (xx) (Cc)s-m+1- ct - for any Ç 0.
Proof. Notice that since [(x)= for all x, where IT a rank m projection matrix, we have that there exists orthogonal matrix U TRaxn such that
Hgd + 9h = UU (k
(((())
where Tkk E 1 Since Ps has the same distribution as PRU, we can assumee that
Pa + gh) = Ps [hk = P Park.
26

---

Published as a conference paper at ICLR 2025
where Pk. is an x random matrix whose elements sampled independently from 1/001/s). By Lemma BD we deduce that
m (Pa)(P))]] Hxds + +gull S I| (Hgdy + ge)ll
(D.4.1)
||dx|| = Px ēx
2 (V n c)
(D.4.2)
[t
[x
with probability at least 1-2exp (- ( 2 exp (-s). Moreover, by (B223 in Corollary B
we deduce
0₂ - == - d2 - |1 ||dd/11 = A Al19s1
(D.4.3)
Hence,
1
Had2 + ghll 1
Pp (Hads + 9x)ll
minl (Pk)
Uk
8k
(by (B in Corollary B.
mmnn (Px)
tx
1
||dal
(by D442
Minu (Pk)
v 11/8 C
62 + ||
(by D.433 and || - A).
miin ( vn/s
Morcover, by (Rudcison & Vershynin 2009.
Theorem 1.1), we have
JA > 0, Pr mmin (Pk) 2
2 1 - (C9) -8
for some constants Č, Therefore, for any ( 0, the following inequality holds with probability at least 1 - cxx (- () 2 exp (-8) (Cg))-me mm+mm+1----- c=
5A + 1
H4 + +x 5
5 <(1
11/8-
Here, we evaluate the gradient norm at the output point of RSHTR by using Lemma Di Lemma D.6. Suppose that Assumption @ holds. Assume that f satisfies and assume that 8 2 m rT). If ||d&]l s A S 2
then we have
19 M A
1
26A
[Vnns++C+
Va/s-C
Va/s-c
with probability of at least 1 - 4exp (-Gs) 4 exp (-s) (Ōc)=-mtI-e - for any 0.
Proof. This is proved by the following inequalities.
||g++1|| || < 11 Hyds - gu + H4dd gull
M 5A + |
< |2
(by Lemma D.
Vn/s C
M < 2 fn/8 C
1
4A3
A6 Vn/s
8A +
L LVn/s+C+
(by Lemma 3.2
<(1
m=1
Here, Ç is any positive number. The second and the third incqualities both hold with e -os Therefore, this lemma
probability at least 1 1-2 (- {{(s) -2 2xxp holds with probability at least. 1 4exp GGa) 4 exp (-s) (Cc)s-m+1 ets
27

---

Published as a conference paper at ICLR 2025
To evaluate the iteration complexity using the same parameters as in Theorem 11 we substi- tute these parameters into Lemma D.f This shows that Algorithm B achieves vn/ss-FOSP in O(e-3/3) iterations. Therefore, by rescaling E, it achioves e-FOSP in D((n/s)8/4 iteralions.
D.5 8 SOSP UNDER THE ASSUMPTION OF SHAG 2022
Let us introduce the following assumption.
Assumption 5. Let & E (0, 1), define = rank(V> A be the maximum non-zero eigenvalues of V²f(("), and X, be the minimum non-zero eigenvalues of f²*(x"). Then, the following inequality holds
-1+ A1 Xr
1- + 16
20. 0.
By the contraposition (Shan, 2022, Lemma 5.6.6), under Assumption G. the lower bound on the minimum eigenvalue of H* is proportional to the lower bound the minimum eigenvalue of pa H* PxT with high probability. Therefore, Lemma B leads to the following theorem.
Theorem D.1 (Global convergence an & SOSP under Assumption E) Suppose Assump- tions M and B hold. Set s, and A the same as Theorem 1. i.e.,
M 0 O<ES
2 VE and A VE 8= [=
8
M
If there exists a positive constant such that O(nE!/T), then RSHTR converges to an E e-SOSP in at most ((=33/2) iterations with probobility at least
(0.9999)* (1-2ex) exp
(-x6.)
s52
6exp (-cs) (
C - -(2 + 2) exp (-s),
where U=: = D3 + 1.
Proof. By Theorem 1.1. RSHTR converges to an e e-FOSP in at most O(e33/2) iterations with probability at least,
C 4
1 1 4cxp
-
(2U- + 2) exp (-s).
Let xt denotes the e FOSP. We now proceed to prove that x² is also an e SOSP as well.
By applying Lemmna t to the given ō and A, we have
Amia (P'H'P*T)2 2
85
n V
2 Ve ve) +c) (L+ ve) + (V" +c)=
(D.5.1)
M
with probability at least 1 - 2 exp ()))) ) 2exp (-8). Hence, by using the contraposition
of (Shad, 2022, Lemma 5.6.6) and denoting Ki = min (0, A we have
1 + 16 r 11 1
-1
Amin (H*)
KH
8
n
(L + VE) + (VV +C VE
+
M
22(-VE)
28

---

Published as a conference paper at ICLR 2025
with probability at least (0.9999)*~1 (1 (1-28 and the lower bound on the probability is given follows:
2 exp (-g))
This shows that x" an E SOSP
(0.9999))
2exp
C3
C
4 exp
+ (2Ug + 2) exp (-s)
4
C
2 exp
+ -2exp (-s)
4
(C3s) ))
a5²
C
(0.9999)*~
2 exp
6exp
(-4)
-22 + 4x)xxp(-8
Proof of Lemma 37
Proof. H* can be expressed as H* U*DUUT using an orthogonal matrix U and diagonal matrix D Here,
=== diag(A X,)
is the diagonal matrix with eigenvalues A X, Note that X,41 =...= dn 0. Hence, follows that
P'H'P~T PU
(D.5.2)
where Pr is the first columns of p and Dj is the leading principal minor of order r of D Here, frr also a random Gaussian matrix due to the orthogonality of U*, Therefore, Pt full column rank with probability 1. This implies that
Yy E R,, Fi E R s.t. pT y with probability Hence, the following holds with probability 1.
(D.5.3)
z H
Amin ( (H*) min
||
Diy
min VEll"
|
x Pr
x
min .ER"
(by
D.5
| 1012
x T TT
min
min ZEE
|P
where E = 2 R x PiD x
x PPDI x
min
min ZEE
0
(
2
||0||2
(byl) PT xe|2 > Jmii (Ri) ||E/|]
1
(PiDi .0)
min Amin
Umin (pr)
1
min { Auin (P* (P*HrpTT),0) (by (D.52)
(pr)
mmin
29

---

Published as a conference paper at ICLR 2025
Moreover, by (Rudeison & Vershynin, 2009, Theorem 1.1), we have
J4 O, Pr Omin (r) 25 1- 2 1 (CG) -
for some constants C,7. Therefore, for any Ç 0, the following incquality holds with probability at least - (CC) cce
Amin ( (H))
2
2 min Amin (P*H*P*T).00 .03. r-1
5²
Proof of Theorem S
Proof. By following the same argument as in the proof of Theorem D up to DD5 obtain
Amia P H P*T) 2 S(-vV)
with probability at least 6exp g3) - (2U, + 4) exp (-s). Applying Lemma
with
Ç = C/e, we have Amin (H*) 2 12 (-VEE) with probability at least
1 6xp (-4+0 (2U, (-s) - exp (-s+r-1 exp(-is)
for some constant č. This completes the proof.
D.6 LOCAL CONVERGENCE
We note that under Assumption B, there exists μ >>> and R such that
Vo E B(ū, R),, v² 2 pl,
(D.6.1)
where B(x, R) == (y E RD [yy xl| S RJ. Let us first discuss the special case, We Tr which is equivalent to gk by convexity from Assumption R Lemma D.7. Suppose that Assumplion B holds. IJ gk = 0, then 2e41 3R with probability 1.
Lemma DM states that the iterates do not move away from F once it is reached. Since staying at achieves any local convergence rate, we ignore this case.
Proof. By applying ( to ge = 0, have (He 0zl)ez 0. This implies that ü
or (-0,, Tx) is an eigenpair of Hy.
We show that the latter case is impossible by supposing it and leading to a contradiction. Suppose that (-0x, 0k) is eigenpair of Hy. This implics Amin (Hk) < -6s 0. Thus, get
By E IR* {0) s.t. y Huy
so
|
Since y * O, we have 0 <
[|TTT yl with probability 1. Therefore, || y11 > 0 follows.
Thus, by multiplying (D.6.2) by ||] yll > O, we obtain
y HAY P 2/1
B R s.t.
< 0.
By taking P v, it follows that
= Haz
3s ER s.t.
0.
||
30

---

Published as a conference paper at ICLR 2025
Therefore Amin (H&) S 0 follows. However, this contradicts Assumption
From the above argument, we have ÜR = 0. Since üg = implies ty o from dg is defined as
dR PK 0k/tk 0. Therefore, ||d&|| A holds and 2x+1 26 dj- 3%k follows.
Next, we show that a sufficiently small neighborhood of a local minimizer, we have ||d&|| ll I A. To this end, we first present the following auxiliary lemma.
Lemma D.8. Under Assumption to + 0 with probability 1.
Proof. Suppose on the contrary that 4 = 0, then (-0x, ūx) is an eigenpair of Hy by (1622))
Corollary B3 Thus we have Amin (Hi)(Hs) S 0Ox < S with probability by Ih +
and Lemma B 4 This implies that
y HAY
By YERRS 8.L.
(D.6.2)
1
Note that |Bvll # 0 and |P vll * 0 hold since the numerator and denominator of (D.622
are both non-zero. By multiplying (D.622) by Iwll"/11P2 u112 > 0, it follows that
y H&y
By ER s.L.
[ u1l2 < 0.
By considering 2 P y, we obtain
= Haz |
E s.t.
0.
Therefore Amin(H+) follows. However, this contradicts Assumption The proof is completed.
By Lemma under Assumption we have de P ix with probability This leads to the following lemma.
t
Lemma D.9. Under Assumption E, we have ||d A for sufficiently large k with proba- bilily at least 2exp (-f ()) 4exp(-s)
Proof. From Lemma D.S and (B.2.9) have the following with probability 1.
0k
(Hx + 1..1)=100 ğk-
Therefore, by multiplying PT from the left, it follows that
d2 P.T 0z - ( 12
tx
Thus, we obtain
|dell < [|PT (At, + 021) 111
< ||PT III (H ++ - 1119 (by Lemma Bi
n/s C
[H + +011)~ |11lg (by Lemma
Here the second and third inequalities hold with probability least 1 1-2exp (-Gs) and 1 2 exp (-s) respectively. By Lemma D and [D6. I],, have He. + + ( C) p+ 0g
31

---

Published as a conference paper at ICLR 2025
with probability at least
eexp (-s). Hence, we have
(Vn/s+C)/2
||dx|| -
l
(vn/s- (3588-C)) c) + 0k
(Vn/s+ 19
(vn/s- p
(vn/s + |
2( 2(vn/8 -C μ
We have |191|| + 0 by Assumption E which leads to ||d |l s A for sufficiently large k.
Here, we present an auxiliary lemma for the proof of Theorem
W
Lemma D.10. We have
Amin (Hx)) 2
(1
n
C
Amin (Hx),
2
Amax (Hzz) S
+ +c
Amax (H&)
with probability at least 1 2exp (-s).
Proof. It follows that for any E Ra have 2 Hgw T
2 Amin (Hg)) Therefore, by set-
ting x = P v. we have y PT 2 (Hz) for any y E R Using Lemma B we [| v12
have (V- 11y12 < 1| u/1 with probability at least 1 - 2 exp (-s). This implies the following inequality holds.
PeHlePEy y
(VT-C)
Amin (Hx).
1
This inequality holds for any R', which proves the first equation. The proof of the second equation follows a similar argument.
D.6.1 PROOF OF THEOREM M
Proof.
VII(I4+1 z) V H( IR) + VI( x)
VFde + VA( -5)
-VVIP (1ly +0+1) Paak Vil( Z)
--HPP (Hs - -T)
-VHP, (Hly +0xI) Palga - Ha( - xx))
+ +V - 3)
- - B H(ax - z)
Here, we define
A V HPP (fix + PAHa - -x)
and
B = V HP, (Hs + BxT) - Hz(0v Ft))).
32

---

Published as a conference paper at ICLR 2025
To bound B, we give bound to ||PT + - By Lemma D.I0 PE is invertible with probability at least 2 (-s). Therefore, we have
P (P 0+1) - Pall
(PAH Pkll-
(D.6.3)
Moreover, the right-hand side satisfies the following inequality.
12 (v=" C)
[P (P.H& PAll
-c)
A Amin (H&))
(by Lemma D
(n/s+C)) (n/s- (by Lemma B2 and D.6.
(D.6.4)
Here, the first and the second incqualitics both hold with probability at least 1 1 cxp (-s). Therefore, combining (D6: and (D.44))
have
(PAHAPP + 0xT) S (vn/s+ C)2 (vn/s - C)2 p
(D.6.5)
with probability at least - 6exp (-s).
By Taylor expansion at x of f,, we obtain 119x - Ha (2q - ا||ه 011 =I(²). Combining this with (D.,, we get B = 0 -
with probability at least 1 - 6exp (-s).
Next, to bound A, we further decompose
A + A2 such that
A = V HPP (PAHI, + 1)1) PaH((r z)
A2 = v T (PAHP + 1) PH Hx) - F).
Since 1| - H| lends to 0 and
(1bb we have ||2 = <(1 - =ll). This leads to
|| Vi - 5) ||-AA v [( = +0ll=x =
which holds with probability at least 1 cxx (-s). Therefore, remains to bound -A1 (xx - .) This further decomposod as || -Alll where
Ag [ VA P / / -5). 3).
A4 = V VHPT ((PHPP] -R
PaH -ack--1 7).
Here, ||A4]| = o1| - -I) holds for the following reason. By (.288), Lemma D.N and å = 0,
we have 0g- g with probability and thus
|| S || |||dd
- A Alll (by Lemma D3
with probability at least 2exp (5) - 4exp (-+). This leads to 0g + 0 since ||
tends to O. Therefore, [[PP + 021) (P.HP, )- tends to O, which implies ||A
of o[]====ī]). Hence, it remains to bound ||Aa||- Using the fact that VHPT (P an orthogonal projection, this is bounded from above by
Amnin (H)
| [H(
1) -2)
2Amax (PHHP,))
Thus we obtain that
[H(znn s V1-
Amin (f)
|| HH(e - x) + +oll1xx - =|I).
2x Pa PPHP.
Therefore, when
Xmiu (H)
V((x =)ll-v1
Amin (H)
VH(m -z>|| -011x--11
2Amax (P&HP)
33

---

Published as a conference paper at ICLR 2025
have that
V - s V11
(a)
H(x -
(D.6.6)
4dmax (P&H.P
Notice that the condition above is implied when
Amnin (F)
Amin H
ol11=x =1))
4 (PHHPP))
2d (PHHP)
Amin (H) [| - 3
Thus, we obtain
for sufficiently large
Since we have, by Lemma DAIL Amax (PelH) S (V Amax((H) with probability at least 1 2exp (-s), the upper bound can be rewritten as
V $)|
Amin ( H)
V (( (((x=-=)] -z)
4)max (H) vn/s C)2
Since the probabilistically valid properties that we used in this proof are Lemmas B.2 D.S.
DMI and D.I. the probability lower bound is given by 2 eexp (- ()) 8exp (-s).
D.6.2 LOCAL QUADRATIC CONVERGENCE
Let 7 RØ, where recall that & be the striet local minimizer of Then the following properties hold:
f(x) = f(R Ra) = I(Rx,,
Vf(x) = V((II = II] IVV())))
(D.6.7)
[V)( = V VV)')) VIV ||
[RV
3p > 0 s.t. | 2 -lyy
By > 0 s.L. | 2 7/| x)|l (7= miin (R Pp). (p))..
(D.6.8)
Next, we show some lemmas regarding Lipschitz continuity. Lemma D.11. Suppose Assumptions D and A hold. There ezist constants L,, Mi 0 such that for any y1 E IR", the following inequalities hold:
[[[(())) V((22)I S Lills yall,
(D.6.9)
( (1122) < M1lli 32ll-
(D.6.10)
Proof. Since ((y) s(R y), by the Lipschitz continuity of S, have
[[V(())) - v((22) = R V (
R V V
s Rl
Vf(x)
V
vf(x))
< | L R.R. y11 R y/2
[||
L 1ly1
82ll
Moreover, we have
-
R 4 f(x) |- v2f(2) = ya
R
< || 2
22 f2)(2)) - (2f(x))
< || | [R 1/1 RR y2ll
< || M |/ -yzll-
Therefore, by setting I, || L. and Mr |R]] 3 M, the lemma is proved.
34

---

Published as a conference paper at ICLR 2025
Lemma D.12. Suppose Assumptions N and hold. There ezists constant Ln > 0 such that for any 21, D2 E IR", the following inequality holds:
[Vf(z1) -V(2))))V(222)l1 S Anll=1-z2lln x2
Proof. Since
[ V
vf(=z)) (l V/
/
(V)(a)) vf(xz)) (z)) -IV
(V Vf(xz2) (Vf(x1)) vf(22))
(by (I....))
S [IV -f((x2)
R VI(U)) vi( VI(y)ly=Ro)) Roz))
& Li [| | Reell.
the lemma is proved by setting Ln L1 ||[]||-
From this lemma, immediately follows that || = 119 = O - =||n)-
In the following, analyze the convergence rate of || which leads to the convergence rate of f(xx) ( First, note that. I + O (a.s.) is derived from the fact that the Hessian positive semi-definite near T. However, the proof is omitled since it is similar to that of Lemma D. This implies dy Px
Next, we show two auxiliary lemmas.
Lemma D.13. Suppose Assumption holds. Then,
Hadd + gull S vr/s 11gu I1
holds for r = rTnk universal conslants C and T, and any Ç > with probabilily al least - 2exp(-r) - -
-ss
Proof. Let UR be an orthogonal matrix whose first r rows are given by R. follows that Un Ut has the same distribution PT meaning that each element of UnP is distributed according to A/ 1/s). As R., is the first r rows of URP RPT is an r random matrix with elements independently drawn from N/O, 1/s). Define PT R.... using (D..l) have
Hydd gull
[Pa(Had + gk)ll
Omin ( PP))
Tmaax (Px)
|RP Pa(H&de + g.)l
σ minn (Pk)
From RRudelson & Vershymin, 2009, Theorem 1.1), we have
JC > 0, Pr min (Px) 2
1
1- (C -68
for some constants C, and from Lemma BR
we have
Pr m (Pt)
+ > 1 - 2exp(-r).
V
35

---

Published as a conference paper at ICLR 2025
Therefore, for any 0, the following inequality holds with probability at least 1 2 exp((-r) - (Cg) s-
|| + gull S vr/s+C
|RP Pallleda + gk)ll-
(D.6.11)
5 ((1-v -
By multiplying R.. to both sides of [B (B2288) we obtain
RP3 Ps(Hads + 92) - 02 Rdw.
(D.6.12)
Thus we have
Vr/8 +C
[agd gx S
|RP] Pa gx)ll (by (D.6..I))
5
1
8 c
02 Rd
(by (D.66.
vr/8 + C
Ou Rd
r/8 +C
(D.6.13)
Moreover, from 32 and 8 = 0, we have
0x - 9k dx
(11gx)) T du
(Rgg)) (Rdx)
S Iloxllulldkllu
(D.6.14)
Combining DD 1 and (D.6
we obtain
vr/s+t C
Hada + gull S
|9xl1m|/de111
5
Lemma D.14. Suppose Assumptions M and D hold. The following inequality holds:
1
11ax+1 - (Hrd + gu)ll S M, Mlldd
2
Proof. By considering the Taylor expansion of t Vf(ak + tdk), we obtain the following equation:
9k+1 = + 1 42 5 + (dx)
By subtracting Hgde + ga from both sides, we obtain
gk+1 (Hay + +gx) = 1 (v2 tdx) 11x) dudt.
36

---

Published as a conference paper at ICLR 2025
By evaluating the norm of both sides, obtain the following inequality:
19++1 - (Hedæ + gx)ll - / [[V2 s(o + tdx) - HE) dx dt
/ R
- (2I(v)) Rdl dt
/ ||l]] ( ((
(F REA (21(1)] Rea) Rdd di
< || S Mi [[ + (dd) Rerk [|d di (by (D..6.
Mi [| |d L. tdt
Mi R| |
2
Thus, the lemma is proved.
Proof of Theorem
Proof- At first, we will show the first inequality in Theorem sTl. The following inequality
holds with probability at least 1 1-2exp(--)) (0()* for any Ç > 0:
|| -||n $
19x+1l
(by (.6..))
(ldd + gall + 11 (Huda + gk)ll)
VT/s +C
11 (mllllld + M, Rilld in (by Lemma D.I and Lemma D
<11- v
1
Vr/s + C
1 MM
| 3lln
[|dx
(by Ilglln O(1 =IIn))
< (=11
2
(D.6.15)
Now, have
d & || - F||n + 1| F1In
1 7
+C
|| æln + Mi |l [|dx|] + +11xx - Ilmu.
which can be rearranged as
| æ|in + Mi [RI| )) lidellu S 11:0 - =I|n.
|d ln
Cr/s+C
1
c(1
Since ||T Elln 0 and Id - O, for sufficiently large k we have lll I/ S ||as Combining this with (D...E), for sufficiently large k; we obtain
Fllm-
4
Vr/s +
1 || I|In + 55 Mill MillB || - x
| - Flnn
<
4M
|
(since sufficiently large).
37

---

Published as a conference paper at ICLR 2025
Therefore, we have derived the first statement in Theorem 3 Next, move to the next inequality in Theorem B.
( f(0) = ! (Vʃ( + U(xx z)) vI(()) (Ir =J)dl
L.' (VI(w)))- R(+t)ee1- Vi(v)ly- Ra) R(xR+1 z)dt.
(D.6.16)
D.6.1
is bounded above by
J. [I(y)) R(o))l--( Vi(y)) [|((xx - x)||
< R =]]l S/" ldl (by 1.6.9
L 1 Ellt..
(D.6.17)
D.6.lr is bounded below by
J
T TtR(2x= I)
Vi(y))l y R(x
v((y)) (7(y))g=Re)
dt
1
2plltR((x - T] dt
(by strong convexity of 1)
2p|1=x -b1 {' tdt
= p|| - E
(D.6.18)
We are now ready to prove the theorem.
L
-
(by DD.
2
M?
1 - ællit
(by Theorem B
72
8L (f(#x) - f(z))) (by
R|
0.6
7202
We recall that all of the above hold with probability at least 1- exx((-r))-------- (CC))(rrt--te for any < > 0. If we set Ç sufficiently small, the probability is bounded from below by 3exp(-r) e- which ends the proof.
E CONVERGENCE THEOREMS UNDER ALGORITHM
We provide additional theoretical considerations regarding subspace dimension such as < 2(log n). In practice, = Q(log n) is sufficiently small, and Algorithm @ works effectively; this analysis is primarily of theoretical interest.
While setting = oloogn) means that the success probability of each iteration is no longer high, the algorithm can simply retry until success. Specifically, this section, we present slight modification (see Algorithm D) of Algorithm M. where line Iine IB are added to decrease the value of the objective function f at every iteration. For Algorithm II we can prove the convergence to e-FOSP with arbitrarily high probability under the same hypothesis even for small s independent of the dimension n (s needs only to be greater than some constant). Notice that all the results proved for Algorithm also hold for Algorithm This because the probability that the function decreases at each iteration is already taken into account in the probabilistic results that prove.
38

---

Published as a conference paper at ICLR 2025
Algorithm 6 RSHTR: Random Subspace Homogenized Trust Region Method (variant)
1: function RSHTR(s, n,,,,,,00 A, max iter)
2: global_ loobalmodde-2 True
3: for k = I...., max bar.,,max_itteeee iter do
4:
Ps x n random Gaussian matrix with each element being from (O, 1/s) Gk + PRal
5:
6:
(tx, 8k) + optimal solution of (2.2.1) by cigenvalue computation
du <- { ux/tkt if t # 0 Pk Ük. otherwise
7:
8:
if global __ndeemodeeee and ||d > A then Th < A/|ldell
9:
or get from backtracking line search
10:
Dk+1 t + meds
if (yk+1) < f(x)) then
12:
Th+1 = yk+1
13:
else
14:
Fh+11 =
15:
end
16:
else
17:
Tk+1 f 26 + dk
18:
terminate
continue with @.global_mode) Falsel for local
convergence
Theorem E.1 (Global convergence to an c-FOSP). Suppose that Assumption M holds. Let
0 D<ES
Ma 8 8= CV V and A
M
Then modified RSHTR (Algorithm ( outputs e-FOSP in at most O (5-3/2 iterations with probability at least
(-11-55)13 4 exp (-C9)
C - 4exp (-s),
1- exp
-3/2 +1, and where and C are absolude constants, Ug = L 2 (s(zo) inf x-3)) 5g = 1- exp(-s).
Proof. Let us consider how many times we iterate in the case where [dg] > at most.
According to Lemma D. and Lemma D22 the objective function decreases by at least
3/2
28
2 (Vn/s
n2/s=1 +C)
3M2
with probability at least 2 exp (-8). Let Y& E (0,1) be random variable equal to if and only the objective function decreases at least by the above quantity. Then, after K iterations, the objective function decreases by at least:
3/2 K
Yk.
3.M
Since, for all k E|y] 1 1-2 1-2cxp(-s)) = 1- 8s, we have by Chernoff bound (sce Vershynin (2018) that for all 8 E 10,
Y 2 (1 5)(1 1011-6,4 6,)K - exp (- 82 Σ
K
(1- (1-6))K))
exep exp (- - k5) after iterations, the objective
Hence with probability at least function decreases by at least
3/2
6.1/2 (1 exx((ss)) (s))
39

---

+ O(E- iterations with probability at Published as a conference paper at ICLR 2025
Since the total amount of decrease does not exceed D f((x)) f(z), we deduce that 6= (x=2exp(=s) |- Also, since
the number of iterations for the case where ||de|] > A is at most |
the algorithm terminates once it enters the case | _ A, the total number of iterations is D. -3/2 + at least.
at most Ug = 11-2exp(-2
We can compute an FOSP with probability at least 1 4 exp can be easily checked by applying Lemma k to the given and A.
(- 4ep (-s), which
Therefore, RSHTR converges in 1 expl least
6M De
exp(-e)
exp (-C C - 4 4cxpp (-s)
1 - exp (-8 (1- 5,)Ue
where Ug L (1-2exp(-a)
6M 3/2
+
F EXPERIMENTAL DETAILS
Throughout all experiments, the parameters of the algorithms were set as follows:
HSODM: (6, A. = (10-), 1. (0-0,10-1)
RSGD: 100
RSRN: (7, C1 C2 8) (1,2,2,1,000) 100)
RSHTR: (6, A, V, = =(10- [10-3,10 10 100)
Here, we denote the dimensionality subspace as 8.
The datasets and other details of each task described below.
F.1 MATRIX FACTORIZATION
In this task, preprocessing is performed. We chose 50 the feature dimension k. Here the dataset we used for this task.
MovieLens 100k (Harper Konstan, 2015
Shape of R: (943, 1682)
Problem dimension: 131,250
Source: downloaded using scikit-learn (Pedregosa al, 201
F.2 LOGISTIC REGRESSION
In this task, all datasets preprocessed 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 of more than 1,000.
Here is a list of the datasots we used for this task.
news20.binary (Kogan et ald 2009
Problem dimension: 10,001
Source: http://www.cnt cwwe. ntu edu. http://wwww../...totttooo//////t
rev1.binary Leewis al, 2004
Problem dimension: 10,001
Source: http://www.c csie. ntu. wwt.:/ntt...eeeeeeeeee
40

---

Published as a conference paper at ICLR 2025
Internet Advertisements (Kushmerick, 1998)
Problem dimension: 1,558
Source:
F.3 SOFTMAX REGRESSION
In this task, all datasets preprocessed in the same way
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 datascts we used for this task.
news20 (Lang, 1995)
Number of classes: 20
Problem dimension: 200,020
Source:
http:://www.ciic ntu. edu htt.://.ww....cggg/.//oaoooooto.
multiclass html
SCOTUS (Chalkidis et al, 202T)
Number classes: 13
Problem dimension: 130,013
Source: multiciass.hca html
F.4 DEEP NEURAL NETWORKS
In this task, used 16-layer fully connected neural network with bias terms and the widths of each layer are:
(input_diie dim, 128, 64, 32, 32, 32, 32, 32, 32, 32, 32, output_diatt _imm
We utilized subsets of 1,000 images from each of the following datasets. Here is list of the datasets we used for this task. When using the test data, we sampled an additional 1000 data points.
MNIST (Deng, 20T2)
Input dimension: 28 x 28 784
Output dimension: 10
Problem dimension: 123,818
Source: downloaded using scikit-learn (Pedregosa all, 201
CIFAR-10 (Krizhevsky, 2009)
Input dimension: 32 x 32 x 3 3, 076
Output dimension: 10
Problem dimension: 416,682
Source: downloaded using scikit-learn [Pedregosa el all 201
G ADDITIONAL. NUMERICAL EXPERIMENTS
In all experiments in this section, the proposed method exhibited the fastest convergence.
41

---

Published as a conference paper at ICLR 2025
Matrix factorization with mask (MFM); We first recall matrix factorization (without mask) formulation:
min |UV UER UE
where E R=,x*., Xn. and I1-11 denotes the squared Frobenius norm. The masked version of the problem introduces mask matrix X E {0, [0,1)% X", to handle missing entries in R. Using this mask matrix, MFM is formulated as
min XE
IIUV - R) XTF
where X = 1 if Ry is not mull and X,j = 0 otherwise and the symbol @ denotes element- wise multiplication. The problem dimension is calculated as (nt + ny ). The result of MFM on MovicLens 100k dataset (Harper & Konstan 2015) is shown in Figure 57
The formulation of this task is the same Section The result of logistic regression on the Internet Advertisement dataset (Kushmerick, 1998 is shown in
Classification:
Figure 51
GD
HSODM
RSGD (s=100)
RSRN (s=100)
RSHTR (s=100)
function value
function value
0.6
801
0.4
40
0.7
0.0
80
160
240
80
10C 240
time (s)
time (s)
(a) MFM: MovieLens 100k (dim=131,250)
(b) Logistic reg.: Internet Ads (dim=1,558)
Figure 5: Comparison of our method to existing methods regarding the function value v.s. computation time. Each plot shows the average + the standard deviation for five runs. Algorithms that did not complete a single iteration within the time limit are omitted.
Classification Accuracy To compare several methods from perspectives other than the loss function, we also evaluated train and test classification accuracies at the end of training (4,000 seconds for MNIST and 16,000 seconds for CIFAR-10), where training was stopped due to the time limit. The results are presented in Table While the limited training data restricts generalization and results in moderate test accuracy, our approach still demon- strates superior performance compared to other methods.
Table 2: Train and test accuracies on MNIST and CIFAR-10 datasets. Our method, RSHTR, achieved the highest accuracy on both datasets.
MNIST
CIFAR-10
Algorithm
Train
Test
Train
Test
RSGD
0.412
0.355
0.315
0.146
RSRN
0.735
0.376
0.523
0.150
RSHTR
0.998
0.680
0.959
0.211
Comparison with Heuristic Algorithms We conducted further experiments to evalu- ate the performance of our algorithm against popular heuristics used in training deep noural compared our proposed method with Adam (Kingmaa, 201l) and AdaGrad (Duchi et all, 2011) on the MNIST and CIFAR-10 datasets for classification using neural network. The formulation of the task is the same as Section HL What differs is that,
networks. Specifically,
42

---

Published as a conference paper at ICLR 2025
to ensure meaningful comparison with fast optimization methods beyond random subspace methods, we adjusted the subspace dimension our proposed algorithm to a smaller value than used in Section EI. The result and the hyperparameter settings shown in Figure E While our proposed method does not surpass Adam in terms of convergence speed, it demon- strates superior numerical stability. This is likely attributed to the method's ability avoid directions with rapidly increasing gradient norm by utilizing Hessian information. Further- more, our method can match or outperform AdaGrad in convergence speed depending on the parameter settings. Specifically, when using numerically stable parameters for Ada- Grad, our method exhibits faster convergence rate. Moreover, our method saves time to lune hypeeraraaeeerrs due to its consistent stability across different hyperparameter choices. Conversely, Adam and AdaGrad can become drastically unstable with increased learning rates aimed at faster convergence, necessitating trial and error for parameter optimization.
Adam (triaad)
function value
3-
niaHTs 1a-20, deha-Iod, Deha-le-4)
Adedrad (1-1e::
function value
nIGHT 1a-12, deha-ie-4, Deha-le-4)
AdsCrad (r-1e-3)
(1-1e-4)
IEa tseis dehawiod Dchamin:)
IIaITI (wm32, dehawins (cha-le
2-
2
40
80
120
80
120
time (s)
time (s)
(a) DNN: MNIST 123,818)
(b) DNN: CIFAR-10 (dim=416,682)
Figure 6: Comparison of our method to heuristic algorithms.
43


Reviews:
[{"review_id": "XLMTUtG9u7", "reviewer": "Reviewer_zCBT", "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.\n\n**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.", "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?\n2. 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.\n3. 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?\n4. 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)?\n5. 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?\n6. 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?\n7. 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}$.\n8. 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?\n9. In line 1480 and below, the notation $\\sqrt{\\bar{H}}$ is not defined. Could the authors provide clarification on this notation?\n\n**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.\n\nThe article contains several typographical and punctuation errors that require careful review by the authors. For example:\n\n- Line 28: \"as follows. \" should be \"as follows:\".\n- Line 110: \"Local\" should be \"local\".\n- 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. \n- Line 372 and 417:  \"global_mode\" should be \"False\".\n- Line 1525: $\\||A_3+A_4\\||$ should be $\\||A_3-A_4\\||$.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 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.\n- 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.", "weaknesses": "- Despite the logical layout, the paper contains numerous typos and punctuation errors, which negatively affect readability and the overall presentation. \n- 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. \n- 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$.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZTQTseKQDl", "reviewer": "Reviewer_hJM7", "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.", "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.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ae66tGA3CV", "reviewer": "Reviewer_qDh3", "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.", "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?\n- 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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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.", "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.\n\nSome 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. \n\nIn 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.\n\nAnother 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?\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)