Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Authors: Sifan Yang
Yuanyu Wan
Peijia Li
Yibo Wang
Xiao Zhang
Zhewei Wei
Lijun Zhang
Venue: ICML 2025 poster (2025)
Keywords: Online Convex Optimization
Frequent Directions
Adaptive Method
Primary area: theory->online_learning_and_bandits

Abstract: In this paper, we investigate the acceleration of adaptive subgradient methods through frequent directions (FD), a widely-used matrix sketching technique. The state-of-the-art regret bound exhibits a _linear_ dependence on the dimensionality $d$, leading to unsatisfactory guarantees for high-dimensional problems.  Additionally, it  suffers from an $O(\tau^2 d)$ time complexity per round, which scales quadratically with the sketching size $\tau$.  To overcome these issues, we first propose an algorithm named FTSL, achieving a tighter regret bound that is independent of the dimensionality. The key idea is to integrate FD with adaptive subgradient methods under _the primal-dual framework_ and add the cumulative discarded information of FD back.   To reduce its time complexity, we further utilize fast FD to expedite FTSL, yielding a better complexity of $O(\tau d)$ while maintaining the same regret bound. Moreover, to mitigate the computational cost for optimization problems involving matrix variables (e.g., training neural networks), we adapt FD to Shampoo, a popular optimization algorithm that accounts for the structure of decision, and give a novel analysis under  _the primal-dual framework_. Our proposed method obtains an improved dimension-free regret bound.  Experimental results have verified the efficiency and effectiveness of our approaches.

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Sifan Yang" 12
Yuanyu Wan
34
Peijia Li
Yibo Wang"
12
Xiao Zhang
Zhewei Wei Lijun Zhang 162
Abstract
1. Introduction
Adaptive subgradient methods have attracted considerable research interest in past decades, which simplify the learn- ing rate selection while ensuring that their regret bounds are comparable to those obtained through manual tuning (Duchi et al., 2010a; Hazan & Koren, 2012; Agarwal et al., 2019). The pioneering work of Duchi et al. (2011) introduces adaptive subgradient methods with full matrices (ADA- FULL) within both the primal-dual subgradient framework (Xiao, 2009) and the mirror descent framework (Duchi et al., 2010b). ADA-FULL achieves regret bound of ((t(()l/ where GT is the sum of gradient outer prod- ucts over T rounds, and this regret bound is better than that of non non-adaptive methods when gradients are sparse. How- ever, ADA-FULL requires maintaining a preconditioning matrix to store the past gradient outer products and comput- ing the inverse of this preconditioning matrix, resulting in an (dd)) space complexity and an (dd) time complexity, respectively, where d is the dimensionality. Thus, ADA- FULL is impractical for large-scale machine learning tasks involving high- -igh-dimessional data.
In this paper, we investigate the acceleration of adaptive subgradient methods through frequent directions (FD). widely-used matrix sketching technique. The state-of-the-art regret bound ex- hibits a linear dependence on the dimensional- ity d, leading to unsatisfactory guarantees for high-dimensional problems. Additionally, it suf- fers from an d(7'd) time complexity per round, which scales quadratically with the sketching size T. To overcome these issues, we first propose an algorithm named FTSL, achieving a tighter regret bound that is independent of the dimension- ality. The key idea is to integrate FD with adaptive subgradient methods under the primal dual frame- work and add the cumulative discarded informa- tion of FD back. To reduce its time complexity, we further utilize fast FD to expedite FTSL, yield- ing better complexity of O(Td) while maintain- ing the same regret bound. Moreover, to mitigate the computational cost for optimization problems involving matrix variables (e.g., training neural networks), we adapt FD to Shampoo, a popular optimization algorithm that accounts for the struc- ture of decision, and give novel analysis under the primal-due framework. Our proposed method obtains an improved dimension-fres regret bound. Experimental results have verified the efficiency and effectiveness of our approaches.
To address these limitations, several studies propose adopt- ing frequent directions (FD) (Ghashami et al., 2016) to reduce the computational complexity of ADA-FULL (Wan et al., 2018; Wan & Zhang, 2022; Feinberg et al., 2023). In particular, Wan et al. (2018) first develop an efficient variant of ADA-FULL, namely ADA-FD, by employing FD to approximate the sum of gradient outer products over the past rounds. Let < d denote the sketching size and Pt denote the discarded eigenvalue of FD in round t. ADA-FD reduces the space and time complexities to ((rd) and O(r²d), while enjoying O(r((G)/3 + Σt VP) and + TVP() regret bounds under the primal-dual subgradient framework and the mirror descent framework, respectively. Moreover, by exploiting an ac- celerated trick for FD, Wan & Zhang (2022) further pro- pose ADA-FFD with O(rd) space and time complexities, while keeping the same regret bounds. Recently Fein- berg et al. (2023) design Sketchy-ADAGRAD (S-ADA) under the mirror descent framework, which achieves bet- ter O(tr(G//)) + vd(d T)Pi:)) regret bound, where PL:T = Σ Pt. The key idea is to utilize a variant of Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
'Equal contribution NNational Key Laboratory for Novel Soft- ware Technology, Nanjing University, Nanjing, China SShooo of Artificial Intelligence, Nanjing University, Nanjing, China 'School of Software Technology, Zhejiang University, Ningbo, China "Hangzhou HighTech Zone (Binjiang) Institute of Blockchain and Data Security. Hangzhou, China Gaoling School of Artificial In- telligence, Renmin University of China, Beijing, China Pazhou Laboratory (Huangpu), Guangzhou, China. Correspondence to: Lijun Zhang <zhanglj@ @ www.a.nj..edu.e...
FD (Chen et al., 2020), which adds back the cumulative

---

Dimension-Fren Frees Adaptive Subgradient Methods with Frequent Directions
Table CComparison of ADA-FULL and its FD-hased variants, where ADA-FD (P) and ADA-FD (M) represent ADA-FD under the primal-dual subgradient framework the mirror descent framework, respectively. We denote A, be the i-th eigenvalue of Gr.
Algorithms
Regret Bounds
Space
Time
ADA-FULL (Duchi al., 2011)
((I(())))
O(d3)
O(d*)
ADA-FD (P) (Wan et al., 2018)
O(tr(G4)) + Eis1 vP)
((rd)
O(79d)
ADA-FD (M) (Wan al., 2018)
O(tr(G]/) > TVP:)
((Td)
O(r2d)
S-ADA (Feinberg et al., 2023)
((tr(G)))) + / - -))
O(rd)
O(7"d)
FTSL (this work)
O(tr(G)/3) + VPLTT
((Td)
O(7"d)
Table 2. Comparison of FFDD-ased variants of ADA-FULI, where ADA-FFD (P) and ADA-FED (M) represent ADA-FFD under the
primal-dual subgradient framework and the mirror descent framework, respectively.
Algorithms
Regret Bounds
Space
Time
ADA-FFD (P) (Wan & Zhang, 2022)
O(tr(C)/) + El= Vp:
O(rd)
O(rd)
ADA-FFD (M) (Wan & Zhang, 2022)
O(tr(C))) +E ET. TVP))
O(rd)
O(rd)
Fast S-ADA (this work)
O(tr(G)/2++ V /dld-r)plr
O(rd)
O(rd)
FTESL (this work)
O(tr(G]/)) + vPTT)
O(rd)
O(rd)
dropped eigenvalues (referred to as the escaped mass) to keep the positive definite monotonicity of the precondition- ing matrix. However, its regret bound depends on d, leading to unsatisfactory guarantees for high-dimennional problems, and its time complexity is O(7dd), which is worse than that of ADA-FFD. Thus, is natural to ask whether the regret bound and the time complexity of Feinherg et al. (2023) can be further improved.
Moreover, we investigate optimization problems with trix variables X, E Rm*x a scenario commonly encoun- tered in deep learning tasks. In this case, one can ap- ply the aforementioned methods by flattening the gradient GØ E mx into a vector gt E Rmn, which, however, in- curs a memory usage of O(rm)). To improve the memory efficiency, Feinberg et al. (2023) have adapted FD to Sham- poo (Gupta et al., 2018), popular adaptive preconditioning method that accounts for the structure of the parameters. Al- though Feinherg et al. (2023) reduce the space complexity to ( + n)). their regret bound again relies on the dimen- sionality mn, n. To address this issue, we integrate FD with a primal-dual variant of Shampoo and obtain a dimension free regret bound via novel analysis. Our approach, termed FTSL-Shampoo, attains an enhanced theoretical guarantee that independent of the dimensionality m, n. We contrast FTSL-Shampoo with previous methods in Table 3. Finally, we conduct experiments on online classification and neural network training to validate the superiority of our methods.
In this paper, we provide affirmative answer to this ques- tion. Specifically, we first develop an algorithm, namely Nollow-the-Skecch--Leedde (FTSL), to enhance the existing regret bound. We integrate FD with ADA-FULL under the primal-dual framework and add the cumulative discarded eigenvalues of FD back. FTSL enjoys tighter dimension- free (tr((G)/2) VPIT) regret bound, while obtaining the space and time complexities of (Td)) and ((7a)). Addi- tionally, we propose an accelerated variant FTSL, named FTFSL, by doubling the sketching size reduce the num- ber of time-consuming computations. FTFSL preserves the regret bound and space complexity of FTSL, while si- multaneously lowering the time complexity to ((rd) when < Vd. Remarkably, we can also improve the time com- plexity of S-ADA by using this technique, but its regret bound still remains inferior to that of FTFSL. We summa- rize our results and comparisons with the previous work in Table I and Table 2.
2. Related Work
In this section, briefly review the related work adap- tive subgradient methods, their fast variants based on sketch- ing, and Shampoo.
2

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Table 3. Comparison of adaptive subgradient methods for the case where the decision has matrix structure X E Rm We denote
the gradient G E R=xx, r is the largest rank of G Lr clmxm + - G. (G²) )T, Rr cluxn + > (G.)) G. é a
pyper-parameter, Pi.r and Pirr represent the sum of the removed eigenvalues in FD during the approximation of Σ = G (G ) and
Σ (G,) )" G respectively. For ADA-FULL and FTFSL, define Gr Σ gigr E " where g: VGU(G m and (-c(.) denotes the row-major vectorization of a matrix.
Algorithms
Regret Bounds
Space
Time
ADA-FULL (Duchi al., 20
O(tr(G)())
O(m²n²)
O(m"n²)
FTFSL (this work)
O(tr(C/(*) + VPLT)
(
O(rmn)
Shampoo (Gupta et al., 2018)
(
O(m" + n²)
O + n²)
S-Shampoo (Feinberg et al., 2023)
O(F(LU(L)))) + m( (L((12(()) + (14))) O(F(m + n))
((72mn)
FTSL-Shhapoo (this work)
O(Vi(L((L))) +
+ (44 O(r(m + +))
m(rmm))
2.1. OCO and Adaptive Subgradient Methods
defines a symmetric matrix G, = =laxd + G//², where c <>> O is hyper-parameter introduced to ensure the invert- ibility of G.. According to the primal-dual framework, the update rule is given by
Online convex optimization (OCO) is a powerful paradigm for solving sequential decision-making problems (Hazan, 2016; Orabona, 2019; Zhang et al., 2018; 2022). Specifi- cally, it typically formulated as an iterative game between player and an adversary. In each round e [T]. the player begins by selecting a decision X, IR. After that, the ad- versary chooses a convex loss function fo()): Rd + R, and the player incurs loss fx.)... The goal of the player is to minimize the cumulative loss Σi= fe(xx) over T rounds, which is equivalent to minimizing the regret (Zinkevich, 2003)
X1+1 arg min
{ 11 ( Bes (1880))
+
1 1 1
[x((x)
xER
G, B..
where n is the learning rate, g. = Ei gi is the sum of the received gradients and (x = 2 (x. Gxx) is the proximal term. The mirror descent version updates the decision as follows
T Σn(x),
R(T) & Σ f(()))
(1)
X++1 = arg min {1 (gi, + BB, (x,, XER=
= n1; gi.
defined as the excess loss suffered by the player com- pared to the loss of the fixed optimal choice x" e arg min Σ'= f((x). Although Zinkevich (2003) es- tablishes the optimal regret bound of O(VT), it is data- independent. In the following, we will introduce ADA- GRAD (Duchi et al., 2010a; 2011), widely-used adaptive subgradient method, in both the primal-dual subgradient framework (Xiao, 2009) and the mirror descent framework (Duchi et al., 2010b), which achieves a data-dependent re- gret bound.
where BB, yx. = (x - Ve - (VV, y) is the Bregman divergence associated with V.(-). ADA- FULL achieves an O(tr(C)(") regret bound within the both frameworks. However, ADA-FULL store the past gra- dient outer products, i.e., G., and compute G- resulting in O(d2) and O(d3) space and time complexities, respec- tively. The high computational cost of ADA-FULL renders it unsuitable for out-of-the-box use in scenarios with limited resources (Sagun et al., 2017; Ghorbani et al., 2019; Sankar et al., 2021; Zhou, 2024).
ADAGRAD can be categorized into two forms based on how the preconditioner G, is computed: ADAGRAD with full matrices (ADA-FULL) and ADAGRAD with diago- nal matrices (ADA-DIAG). We denote g. be a particular vector in the subdifferential set (x.().). Since we do not require the loss function to be smooth, we will not explicitly distinguish subgradients and gradients in the subsequent discussion. ADA-FULL first calculates the outer product matrix of the past gradients G, = Ei=1 gigT. and further
Different from ADA-FULL, ADA-DIAG only utilizes the diagonal elements of the gradient outer product matrix, i.c. redefining G, elax + diag(G.))/? which thus is com- putationally more efficient. However, since the precondi- tioning matrix of ADA-DIAG only contains limited infor- mation, the regret bound of ADA-DIAG is worse than that of ADA-FULL when high- nigh-dimensional data is dense and has a low-rank structure.
3

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
2.2. Adaptive Subgradient Methods with Sketching
error of FD, Luo et al. (2019) propose a new sketching strat- egy called robust frequent directions (RFD), which is the first method that compensates the discarded singular val- ues back into the second-orde matrix. They utilize RFD to propose a hyperparameter-ffee variant of ONS, which is more robust than FD-SON. In linear contextual bandit setting, Chen et al. (2020) propose spectral compensation frequent directions (SCFD) to approximate the covariance matrices, which adds up the total mass of subtracted values during FD procedure. SCFD can approximate a sequence of incremental covariance matrices while keeping the positive definite monotonicity. In fact, S-ADA can be viewed as a combination of ADA-FULL with SCFD.
To alleviate the computational burden of ADA-FULL, sev- eral works have employed the sketching techniques to re- duce its space and time complexities (Krummenacher et al., 2016; Wan & Zhang, 2018; Wan et al., 2018; Wan & Zhang, 2020; 2022; Feinberg et al., 2023). Krummenacher et al. (2016) propose ADA-LR to enhance the computational com- plexity of ADA-FULL by using random projection (Indyk & Motwani, 1998; Achlioptas, 2003). While ADA-LR re- duces the time complexity to OrTd)), its space complexity remains at (dd)) where T < d is the sketching size. To fur- ther improve the efficiency, they develop RADAGRA, which incorporates a more randomized approximation, achieving space and time complexities of ((Td) and ((+2d), respec- tively. However, RADAGRA is not supported by rigorous theoretical analysis. Later, Wan & Zhang (2018) develop ADA-DP based on random projection, which achieves space and time complexities of (Tdd) and O(F2d), while provid- ing theoretical guarantees.
2.3. Shampoo
Shampoo (Gupta et al., 2018) is an adaptive optimization method that takes the structure of the parameter space into consideration and thus is more efficient than ADA-FULL in scenarios where the decision is a matrix. Specifically, Shampoo maintains set of preconditioning matrices, each of which operates on one dimension, while aggregating information across the remaining dimensions. For exam- ple, for parameter matrix Xe E Rmxa and its gradient GØ E I ADA- treats the matrix-shaped gradi- ent as a vector of size ran and its preconditioner G, has the size of mn x mn, which leads to (m2??²) and 3(m)n3) space and time complexities, respectively. In contrast, Sham- poo construets two smaller matrices, L, Rm and R2 E RRxx, to precondition the rows and columns of G, respectively, which only requires an O(m² + n²²) memory cost and an O(m3 + n²) computation complexity. Since the parameters in the deep learning tasks often have matrix structures, Shampoo has strong empirical performance and receives lots of attentions (Anil et al., 2020; Liu et al., 2023; Eschenhagen et al., 2024).
Another class of sketching based adaptive subgradient meth- ods adopts frequent directions (FD) (Ghashami et al., 2016), a stable matrix sketching technique. Wan et al. (2018) first apply FD with ADA-FULL under both the primal-dual sub- gradient framework and the mirror descent framework by maintaining matrix B, Rd such that B,B, x G2 E Rdxd, where G2 represents the gradient covariance ma- trix. Their approach, ADA-FD, obtains space and time complexities of O(Td) and O(F2d), respectively. ADA-FD achieves regret bounds of ((tr(C)/3 + Et Vpc) and /Pp)) under the primal-dual subgra-
O(tr(G))) + = dient framework and the mirror descent framework, where P: is the removed eigenvalue of FD in round t. Furthermore, Wan & Zhang (2022) introduce a fast variant of ADA-FD, named ADA-FFD, by doubling the sketching size. ADA- FFD improves the time complexity to ((d)) while keeping the same regret bounds. Although ADA-FD and ADA-FFD enjoy better space and time complexities, as mentioned by Feinberg et al. (2023), their regret bounds are 3/(3)/4) in some cases. For this reason, Feinherg et al. (2023) pro- pose S-ADA by adding back the discarded information of FD the FD-based preconditioner instead of utilizing fixed diagonal regularization. While S-ADA enjoys (tr(G)//) + Vald - T)P1:r) regret bound, it suffers from a linear dependence on the dimensionality d. Moreover, it only achieves an unsatisfactory time complexity of Or?d)).
However, the memory demands of Shampoo may still be prohibitive for large-scale neural networks. Anil et al. (2020) address the memory cost of Shampoo by introducing two variants. The first variant, Blocked Shampoo, partitions the decision variable X, E R m into mn/b² blocks, where b is the block size and b S min(m, n.). However, Blocked Shampoo depends on the specific ordering of neurons in the hidden layers. The second variant relies on one-sided covari- ance upper bounds, which cannot effectively handle vector parameters. Feinberg et al. (2023) first incorporate FD into Shampoo and reduce its memory to O(r(m + n)). Their method, named -ketchy-Shampoo (S-Shampoo), uses two low-rank matrices L, RMT and R, RnxT to approxi- mate the preconditioning matrices L, and R₁, respectively. While S-Shampoo improves the space complexity of Sham- poo, its regret bound relies on the dimensions m, n. leading to the unsatisfactory performance when the dimensions are high.
Additionally, we also notice that FD has been utilized to ac- celerate online Newton step (ONS) algorithm (Hazan et al., 2007) for exponentially concave functions, and LinUCB (Chu et al., 2011 I) algorithm in linear contextual bandit set- ting, which also need to maintain a covariance matrix. Luo et al. (2016) first apply FD in ONS to construct a low-rank approximation of the matrix. To reduce the approximation
4

---

Dimension-Fren Free Adaptive Subgradient Methods with Frequent Directions
3. Preliminaries
Algorithm Frequent Directions (FD)
I: Input: Sketching matrix Bt-1 E Rdxr (with its last column as 0,), new gradient vector ge E R
3.1. Assumptions
We adopt two common assumptions of OCO (Hazan, 2016).
2: Insert the gradient g: into the last column of B
Assumption 3.1. All loss functions fa(-) are convex.
( where 4: Compute B, = Wiy/diag(A (1rT) 1!7)
3: Perform SVD to BB-1 = Viy/iag/ (1()) VV,
Assumption 3.2. The optimal decision x* E Rd is bounded by D. i... |xX] < D.
Up E Rdxr
Return: B, and A,5)
Besides, we introduce two assumptions for the scenario where the decision has matrix structure. These assump- tions have also been used in prior works (Gupta et al., 2018; Feinberg et al., 2023).
frequent directions (SCFD), which adds up the total mass of subtracted values Σi= (t) during FD procedure. SCFD is able to approximate a sequence of high-dimensional ma- trices while preserving positive definite monotonicity, i.e.,
Assumption 3.3. The rank of gradient matrix GØ is bounded by i.e., maxtefry rank(G;)) s.
Assumption 3.4. The optimal parameter X* R is bounded by D., i.e., || DM-
Ei=1 I + B.B, ž Diml
Laxd BB- B
4. The Proposed Methods
3.2. Frequent Directions
In this section, we first present FTSL, which incorporates FD with ADA-FULL under the primal-dual framework to obtain a better regret bound. Furthermore, we accelerate FTSL by employing an accelerated trick for FD, achiev- ing enhanced computational efficiency. We demonstrate that this technique can be applied to expediting S-ADA (Feinberg et al., 2023). Additionally, we consider optimiza- tion problems involving matrix variables and propose an improved FD-based variant of Shampoo.
Frequent directions (FD) (Ghashami et al., 2016) is a de- terministic matrix sketching technique by extending the well-known algorithm for approximating item frequencies in online data streams (Misra & Gries, 1982). For given matrix A E Edxt FD aims to generate matrix B E Rd such that BBT ~ AAT, where т < min(t.d) df is the sketching size. The procedure is summarized Algorithm In each round t. we denote the low-rank matrix BI-1 [b1, ...; 1, 0z) E RaxT, where the last column is 0,- Upon receiving the new gradient g: Rd it is inserted into the last column of B Next, we perform singular value de- composition (SVD) on B Us diag( [1:r] VVT and the matrix B, is computed as B; U diag( ( (11:r=] x(9) with its last column set to 0z- The time complexity of FD is (r²2d) for each iteration, which is dominated by comput- ing the SVD of B,- causing a quadratic dependence on sketching size T.
4.1. Our Improved Result
(1)
Before introducing our algorithms, we first briefly discuss why the regret bound of S-ADA (Feinberg et al., 2023) relies on the dimensionality d offering motivation for the methods we design. Since S-ADA is under the mirror descent frame- work, its regret bound contains the Bregman divergence term, that is,
To further reduce the time complexity of FD, Ghashami et al. (2016) propose fast frequent directions (FFD) by expanding the space of Br. Specifically, FFD maintains a matrix Bo = Odx2r E pdx2r, In each round t, we insert the received gradient ge into the first all- zero column of Bt-1. Once B, no longer contains any all-zero columns, we perform SVD to obtain B. = U.y diag(X (1)
O
Bu xx+1) Bu (xx, [etti]]
Σ
| X x=12211-- -0!23
where (x( (x, G//2x) the proximal term, G, is the preconditioning matrix and Bv, V. - (VV,((y).)))) y). To facilitate summation, they upper bound this term by O tr(G)// - G)/3)) and then exploit the additivity of the trace, which yields a bound of ((rr(2//)) Feinberg et al. (2023) add the cu- mulative removed eigenvalues of FD Pı: into G.. Conse- quently, the Bregman divergence term is O(tr((B,, + Pvr (axa)xx))//2) which is further bounded by (tt((G)/3
11:27) VTT Then, the matrix
vx
B, is updated as B, = U2 diag(max (A (t) [1:21] - (4) ,0)), ensuring that the last + columns set to 0z. As we only need to update the matrix B, every + rounds, the time complexity of FFD is (rrd).
Since FD removes a singular value per round, the matrix B, does not preserve monotonicity. To resolve this lim- itation, Chen et al. (2020) propose spectral compensation
5

---

Dimension-Frec Adaptive Subgradient Methods with Frequent Directions
Algorithm 2 Follow the Sketchy Leader (FTSL)
Algorithm 3 Follow the Fast Sketchy Leader (FIFSL)
1: Input: Learning rate 7, sketching size T
1: Input: Learning rate 7, sketching size T
2: Initialize x1 = 02. go = 0g. Gu 0axd, Bg = Odxt
Initialize X1 02rx2r, Vo= = 0dx27: 8o 0a, P
Od, Go
Oaxd, Po
0, Mo
3: for [. = 1 to 7 do
4: Play the decision x, and suffer the loss (x,)
3: for t t= 1 to I" do
5: Query the gradient g. = Vx((x) and calculate g,
4: Play the decision x, and suffer the loss fx(x,)
8i-1 +g
5: Query the gradient = fx())) and compute gi
6: Send BІ-1 and g: to Algorithm
V, VV-I(V,-18t), 8, = -8 ge
7: Receive B, and set Pt. = X
6: if g' + g, then
8: Calculate G. B, + pixlaxa and derive d,1/2 1/2
Set rt-1 rt-1 calculate v!_1
8t gi
1 1Ki-RK xill
9: Update X(+1 according to (2)
and set the re-1-th column of Vi-1 as vi--
10: end for
8:
end if
9:
Set r2 = rt-1, V
10:
Compute M. M, + (V) 1B:)
vd(d-T)pu:T) where BT E IRdxT is the sketching ma- trix and GT = Ei= g:8, As a result, the regret bound of S-ADA exhibits a linear dependence on d, resulting in an unsatisfactory performance in high- problems.
11:
Perform SVD decomposition on M, which is
U.EUU = U,diag() (t)
(1227) (1; = =
12:
Calculate G. = pialaxd + V.
13:
Update x;+1 according to (2) and set pt+1 =0 0
To overcome this issue, we propose integrating FD with ADA-FULL under the primal- dual subgradient frameeenoent framework. Our method, which we call FTSL, is outlined in Algorithm 2. Specifically, we employ the FD to construct a low-rank approximation of the outer product matrix of gradients Gt, aiming to reduce the computational complexity. To ensure the monotonicity of the preconditioning matrix G., we also add back the cumulative escaped masses P1:t into G. Un- der the primal-dual subgradient framework, we update the decision as follows
14:
if r = 27 then
Set Pt+1 = x! Me diag(mas (A
15:
,0)) and V2 = VúUg
16:
Set rt = T and the 7-th to 2r-th columns of V, be 0.5
17:
end if
18:
end for
complexity is O(7²d) per round, which arises from the SVD of B, and the calculation of G-1/² (the detailed discussions can be found in Appendix A). While the time complexity of FTSL is linear with respect the dimensionality d, it still suffers from the quadratic dependence on the sketching size r. To further alleviate its computational burden, we develop a fast variant of FTSL in the next section.
X1+1 arg min {1 (B., x) (x)) xE3
1-1/2 G 8c:
where g. = Ei g. is the sum of the past gradients. Ac- cording to the analysis under the primal-dual framework, the = Br ((I[BBB]. BJ- + PI:r PaxT(ax))1/21) I O(IIG] || + vpi:))
regret of FTSL is upper bounded by the term O(I((,,
4.2. Our Accelerated Variant
thereby avoiding the dependence on d.
The time complexity of FTSL suffers from quadratic de- pendence on the sketching size т, which is introduced by the SVD decomposition on B, E Rd in FD. Drawing in- spiration from the previous work (Chen et al., 2020; Wan Zhang, 2022), we adopt a more efficient strategy for comput- ing the SVD of sketching matrix B, Our method, termed FTFSL, is presented in Algorithm 3.
Formally, present the theoretical guarantec of FTSL.
Theorem 4.1. Under Assumption 3.1 and Assumption 3.2,
by setting the learning rate 1)- = V2
D FTSL ensures
R(T) S 50 ( + VPLT).
where Gr = ET= Big.
Different from FD, the sketching matrix B, is expanded to Rdx2r in FFD. Rather than explicitly maintaining B,, we use two matrices Vú and M, to form B, Specifically, V = [vf.... , v22-l E dx2r consists of r, orthonormal vectors (re S 27) and the rest columns are zero vectors, and M,- R2rx2r is symmetric matrix. We require that V; and M, satisfy the condition V,M, B, E Rdx2r, In each round t, after receiving the gradient gr, we first check whether this
Remark. In contrast to the previous regret bound of
((Ir(G//)) + / /dld (((dd7))) -7)1IT) (Feinberg et al., 2023), the regret bound of FTSI. is dimension-free, benefit realized from the primal-dual subgradient framework.
Remark. Since we only maintain a sketching matrix B, E Rdx7, the space complexity of FTSL O(rd). Its time
6

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
vector lies within the subspace spanned by 1- If the vector is not contained within the subspace, we normalize it and subsequently add it to V thereby enlarging the span of the subspace and ensuring Vi-1V,_ = ge (Step 6-8).
Algorithm 4 Frequent Directions in General Form
I: Input: Sketching matrix B.-1 E R new symmet- ric PSD matrix M, E Rdxd
Eigendecompose U U,diag(A(9)))
B + M,, define U, E _d* be the first T columns of U, and be its eigenvalues
Then we have the following equation
Vi-1M--IV + g.g. =V/-1 (M-- + V2-18:81 V1-1) Vi-1-
\irr]
3: Compute B, = Uty diag )²7
4: Return: B, and X,")
This implies that we only need to perform an SVD de- composition on Mc-1 + (V (V, (g.T E R which only takes a time complexity of O Next, we incorporate the escaped masses to keep the monotonicity of the preconditioning matrix G. When r2 2T, we need to set re = = - 1 and set the last 5 + 1 columns of the sketching matrix B3 to be zero (Step 14-16). Given the de- composition M, = Ug diag( (iag(A(122)) (U and the relationship V.M,/2 = B,, this can be efficiently achieved by updating Mj as diag (max X [1:2+] x O}), calculating V; = VPU, and setting the last r +1 columns of Ve to zero
Algorithm 5 FTSL-Shampoo
Require: Learning rate n, sketching size T, E > 0 1: Initialize Xi = 0m Lo O Omxr, Ro = 0 0nx7, Lo
0mxm: Rg = Onxn. To = 0mxn
2: for ( 1 to T do
Play the decision X, and suffer the loss (Xe)
4: Query the gradient G,² fX(( E Rmxn and -
calculate G22 = --1 + G.
Send - and G. ( to Algorithm and re- ceive Lt
In the following, we provide the theoretical guarantee of FTFSL.
6: Send R:-1 and (G:² T to Algorithm 4 and re- ceive Re
Theorem 4.2. Under Assumption 3.1 and Assumption 3.2, by setting the learning rate 17 = '2'
7: Update L: = L,L,J + (E + P mmxm
D. FTFSL ensures
8: Update Rs = R, + (c+ + pi..) Inxn
R(T) S S (I(()))) + VPLT)
9: Update Xe+1 according to (3)
10:
end for
Remark. In each round, FTFSL computes g/. vI--11 Mr. SVD of Mt and update Xt, with respective time complexities of ((rd), Odd), O(rd), O(r3) and O(rd). Additionally, we only compute V42 = V,U, every T + 1 rounds, incurring a time complexity of ((?2d). When S O(vd), the time complexity of FTSL is O(rd) per round.
4.3. Optimization Problems with Matrix Variables
In this section, we consider a practical scenario where the decision variable is matrix X, Rmxn, which is common for parameters in deep learning tasks. In such settings, the loss f(X) is typically a smooth non-convex function, and the objective is to find a point Xy such that )X S e. As pointed out by Agarwal et al. (2019), a smooth non- convex problem can be transformed into solving a series of offline convex problems by using the online to batch conver- sion. Therefore, we can derive the non-convex optimization guarantees from online regret bounds, with further details provided in Appendix B.
Notably, we can also reduce the time complexity of S-ADA (Feinberg et al., 2023) by adopting this technique. We re- place the update rule for the decision variable x, of FTFSL (Step 13) with the following
X = X, - GG g+,
and analyze under the mirror descent framework.
To utilize the structure information, Gupta et al. (2018) propose Shampoo, which retains the matrix structure of the gradient and maintains two matrices as preconditioners of the rows and columns of G. yielding space complexity of O(m² n²)). While S-Shampoo (Feinberg et al., 2023) improves the space complexity of Shampoo to ((Tmm+n)), its regret bound again relies on the dimensionality m, n. To further reduce its regret bound, we propose FTSL-Shampoo by integrating FD with Shampoo under the primal-dual framework. Our method achieves a superior dimension free guarantee with obtaining an O( + +n)) space complexity,
Then we provide the theoretical guarantee of Fast S-ADA. Theorem 4.3. Under Assumption 3.1 and assuming D1
max ||x, - x1, by setting the learning rate 1) '2'
D.
Fast S-ADA ensures
R(T) < O (u(C)/3) + vild
Remark. Compared to S-ADA (Feinberg et al., 2023), Fast S-ADA obtains a better O(rd) time complexity when T & OVd)), while preserving the same regret bound.
7

---

Dimension-Fren Adaptive Subgradient Methods with Frequent Directions
200
98
150
Accuracy
Loss
Time
94-
100-
50
92
50-
90
500
1000
1500
2000
0
1000
1500
2000
0
500
1000
1500
2000
# of iterations
of Iiterationn
of iterations
ADA-DIAG
RADAGRAD
FD-SON
ADA-FFD
ADA-FFD
S-ADAA
Fast S-ADA
FTFS.
Figure I. Results for Gisette dataset.
1500
88
60-
Accuracy
86
Loss
1000
Time
40
84
20-
82
80
2000
4000
0
2000
4000
2000 # of itcrations
# of iterations
# of iterations
ADA-DIAG
RADAGRAD
FD-SON
ADA-FFD
ADA-FFD
S-ADA
Fart S-ADA
FTFSL
Figure 2. Results for Epsilon dataset.
which is presented in Algorithm 5.
elaxn + (GN) T,,, FTSL-Shanpoo ensures
Specifically, we utilize FD to approximate the left and right preconditioning matrices for Shampoo. We main- tain two matrices i mR R₂ Raxr ensure that L.L. &
R(T) < 0 (Vr(tT(L>)) + (pt.a) )/4
-(tr(R + (P11)"14))
R.R & (GX) We track the cumulative escaped masses P and P of the left and right preconditioning matrices separately, and then add them back into L, and R, to uphold the monotonic- ity. To achieve a dimension-fe regret bound with FD, we update the parameters as follows:
where pir and PLT represent the of the re- moved eigenvalues of FD) during the approximation of Dx GG(G)) and ΣT E GØ respectively.
Remark. In comparison the previous OVV((U((TT)))
(R//") + n n(p )(4)) regret bound of S- Shampoo (Feinberg et al., 2023), we achieve a dimension- free regret bound while enjoying the same O(r(m + n)) space complexity.
X -n
1/4 1/ R, R/
(3)
where T.¹ =i= G. is the sum of the past gradients, and conduct the analysis under the primal-dual framework. Then we present the regret bound of FTSL-Shampoo.
5. Experiments
In this section, we assess the performance of the proposed methods via numerical experiments on online classification and image classification tasks. Due to the limited space, we only present a subset of the experimental outcomes, with the comprehensive set of results accessible in Appendix C.
Theorem 4.4. Under Assumption 3.1, Assumption 3.3 and Assumption 3.4, by setting the learning rale 1) DM and further denoting Lo cinxm + EN.ON
Vr
G. (GX)T Rr
8

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Online Classification. First, we perform online classifi- cation to evaluate the performance of our methods with two real-world datasets from LIBSVM (Chang & Lin, 2011) repository: Gisette and Epsilon, which are high- dimensional and dense. Particularly, Gisette dataset con- tains 6000 training samples and 1000 testing samples, each with 5000 features. Epsilon dataset consists of 400, 000 training samples and 100, 000 testing samples, each with 2000 features. In each round t (T), batch of train- ing examples {(Wr,,, Vt,11 ..... (Wr,n, (t,m)) arrive, where (Wr,i, Vt.a) E [-1 x (-1,1). = 1,...,m, The online learner aims to predict linear model x, and suffers the yxx, w..i)- For Gisette dataset, we set the batch size n = 32, the sketch- ing size T 50 be 1% of the original dimensionality, and T 2000. For Epsilon dataset, we set the batch size 128, r 20 and T- 5000.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here.
References
Achlioptas, D. Database-friende random projections: Johnson-lindenstraus with binary coins. Journal of com- puter and System Sciences, 66(4):671-68) 2003.
hinge loss f((x)) = n Ei=1 max(0,
Agarwal, N., Bullins, B., Chen, X., Hazan, E., Singh, K., Zhang. C., and Zhang, Y. Efficient full-matrix adaptive regularization. In Proceedings of the 36th International Conference on Machine Learning, pp. 102-110, 2019.
Anil, R., Gupta, V., Koren, T., Regan, K., and Singer, Y. Scalable second order optimization for deep learning. arXiv preprint wrXiv:2002.09014 2020.
Results. Following Duchi et al. (2011), we adopt the perfor- mance of accuracy on the testing data to compare different methods. To better demonstrate the improvements of our methods, we additionally plot the training loss and runtime of various methods. From Figure 1 and Figure 2, we ob- serve that FTFSL outperforms all other methods in both loss and testing accuracy, aligning with its superior regret bound, Moreover, FTFSL and Fast S-ADA exhibit signifi- cantly lower runtimes compared to S-ADA, owing to their superior time complexities.
Chang, C.-C. and Lin, C.-J. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology, 2(3):1-27, 2011.
Chen, C., Luo, I.., Zhang, W., Yu, Y., and Lian, Y. Efficient and robust high-dimensional linear contextual bandits. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 4269-4265, 2020.
Chu, W., Li, L.,, Reyzin, L.,, and Schapire, R. E. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
6. Conclusion
In this paper, we investigate adaptive subgradient methods with Frequent Directions (FD). First, we introduce novel method, named FTSL, to achieve tighter dimension-free regret bound of ((t(())/)) + VPLT). ). Next, we propose fast version of FTSL by accelerating FD used in it, which improves the time complexity to ((rd) while preserving the same regret bound. This technique can also be applied to expedite S-ADA (Feinberg et al., 2023). Additionally, we consider a more complex scenario where the decision matrix, and adapt FD Shampoo under the primal- dual framework to obtain a better dimension-free bound. Finally, we substantiate the effectiveness and efficiency of our methods through experimental validation.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. In Proceedings of the 23rd Annual Conference on Learn- ing Theory, 2010a.
Duchi, J., Hazan, E.,, and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Duchi, J. C., Shalev-Shwartz, S., Singer, Y., and Tewari, A. Composite objective mirror descent. In Proceedings of the 23rd Annual Conference on Learning Theory, pp. 14-26, 2010b.
Acknowledge
Eschenhagen, R., Immer, A., Turner, R., Schneider, F., and Hennig, P. Kronecker-factored approximate curvature for modern neural network architectures. In Advances in Neural Information Processing Systems 37, 2024.
This work was partially supported by National Science and Technology Major Project (20222D01 14801), NSFC (U23A20382). and Yongjiang Talent Introduction Pro- gramme (2023A-193-G), The authors would like to thank the anonymous reviewers for their constructive suggestions.
Feinberg, V., Chen, X., Sun, Y. J., Anil, R., and Hazan, E. adaptive regularization with
Sketchy: Memory- frequent directions. In Advances in Neural Information Processing Systems 37, 2023.

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Ghashami, M., Liberty, E.,, Phillips, J. M., and Woodruff, D. P. Frequent directions: Simple and deterministic ma- trix sketching. Journal on Computing, 4565):1762- 1792, 2016.
Luo, H., Agarwal, A., Cesa-Bianchi, N., and Langford, J. Efficient second order online learning by sketching. In Advances in Neural Information Processing Systems 29, 2016.
Ghorbani, B., Krishnan, S., and Xiao, Y. An investigation into neural net optimization via hessian eigenvalue den- sity. In Proceedings of the 36th International Conference on Machine Learning, pp. 2232-2241, 2019.
Luo, L.., Zhang, W., Zhang, Z., Zhu, W., Zhang, T., and Pei, J. Sketched rerlowthe-rggullrizee-d leadeer for on- line factorization machine. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1900-1909, 2018
Gupta, V., Koren, T., and Singer, Y. Shampoo: Precondi- tioned stochastic tensor optimization. Proceedings of the 35th International Conference on Machine Learning, pp. 1842 1850, 2018.
Luo, L., Chen, C., Zhang, Z., Li, W.-.., and Zhang, T. Ro- bust frequent directions with application in online learn- ing. Journal of Machine Learning Research, 20(45):1-41, 2019.
Hager, W. W. Updating the inverse of a matrix. SIAM review, 31(2):221-233 1989.
Merity, S. The wikitext long term dependency language modeling dataset. Salesforce Metamind, 9, 2016.
Hazan, E. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
Misra, J. and Gries, D. Finding repeated elements. Science of computer programming. 2(2):143-152, 1982.
Hazan, and Koren, T. Online gradient descent with adap- tive step size for convex optimization. In Proceedings of the 25th Annual Conference Learning Theory, pp- 77-90, 2012.
Orabona, F. A modern introduction to online learning. arXiv preprint 1912 2019.
Sagun, L., Evei, U., Guney, V. U., Dauphin, Y., and Bottou, L. Empirical analysis of the hessian over- wverparameerrzed neural networks. arXiv preprint arXiv: 706 0445444 2017.
Hazan, E., Agarwal, A., and Kale, S. Logarithmic regret al- gorithms for online convex optimization. Machine Learn- ing, 69(2-3):169-119) 2007.
Sankar, A. R., Khasbage, Y., Vigneswaran, R., and Bala- subramanian, V. N. A deeper look the hessian eigen- spectrum of deep neural networks and its applications to regularization. In Proceedings of the 35th AAAI Confer- ence on Artificial Intelligence, pp. 9481-9488, 2021.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems 30, pp. 5998-6008, 2017.
Indyk, P. and Motwani, R. Approximate nearest neigh- bors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998.
Krizhevsky, A. Learning multiple layers of features from tiny images. Masters Thesis, Deptartment of Computer Science University of Toronto, 2009.
Wan, Y. and Zhang, L. Accelerating adaptive online learning by matrix approximation. In Advances in Knowledge Discovery and Data Mining, pp. 405-417, 2018
Krummenacher, G., McWilliams, B., Kilcher, Y., Buhmann, M., and Meinshausen, N. Scalable adaptive stochastic optimization using random projections. In Advances in Neural Information Processing Systems 29, 2016.
Wan, Y. and Zhang, L. Accelcrating adaptive online learning by matrix approximation. International Journal of Data Science and Analytics, 9(4):389 400, 2020.
Wan, Y. and Zhang, Efficient adaptive online learning via frequent directions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10))6910-6922 2022.
Lancaster, and Farahat, H. K. Norms on direct sums and tensor products. Mathematics of Computation, 26(1 18): 403-410, 1972.
Liu, H., Li, Z., Hall, D., Liang, P., and Ma. T. Sophia: A scalable stochastic second-order optimizer for language model pre-training. arXiv preprint 2xXiv2205..14342 2023.
Wan, Y., Wei, N., and Zhang. L. Efficient adaptive online learning via frequent directions. In Proceedings of the 27th International Joint Conference on Artificial Intelli- gence, pp. 2748 7748-2754, 2018
10

---

Bimension-Free Adaptive Subgradient Methods with Frequent Directions
Xiao, L.. Dual averaging method for regularized stochastic learning and online optimization. In Advances in Neural Information Processing Systems 22, 2009.
Zhang. L., Lu, S., and Zhou, Z.-H. Adaptive online learning in dynamic environments. In Advances in Neural Infor- mation Processing Systems 31 (NeurIPS), pp. 1323-1333, 2018.
Zhang. I.., Wang. G., Yi, J., and Yang, A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference on Ma- chine Learning (ICML), pp. 26605-6666660 26600, 2022.
Zhou, Z.-H. Learnability with time-sharing computational resource concerns. National Science Review, 11(10), 2024.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pp. 928 936, 2003.

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
A. Proof of Theorems
Notations. We denote x to represent a vector and to represent a matrix. For any vector x E R and a positive semi-definite matrix A E Raxd | = (x, Ax). For a matrix A, AA is the inverse of A if A is full rank; otherwise, A 1 is taken be the Moore-Penrose pseudoinverse. For two matrices A, B, 3 B if and only if B is positive semi-definite matrix. define the space complexity and time complexity the memory and time usage in each round, respectively. For example, the time complexity of performing SVD to matrix A E mR=x is O(min(mm n²m}) }). For simplicity, we use ||-I| for I1-112 by default. \p==] is sequence containing T elements, and max a} represents a new sequence, where each element is the maximum of A; and and diag( (Ai=)) is diagonal matrix where the i-th diagonal element is A, S i S 2r. In the proof, we do not require smoothness of loss functions and we do not explicitly distinguish subgradients and gradients.
A.1. Calculation of 1/-1/2
In FTSL, we need to calculate G. 1/2 which can not be directly derived by Woodbury formula (Hager, 1989). We provide the following process.
Assume Ue! is the complementary subspace of U2 R we have Laxd UNU + +U (U.)).. We denote diag(A (0)
( Mg RTxT and have
Pialaxa + UEEU = U,(E, + Pialaxa)U? + Pialaxat; (U,)) U,(,, + PI))UT Pialaxd + U.U. - (UH)
Then get
Pialaxa + UUUU = Ue(2i + PUoUUT + (u = [U; [U
E + PIaleot
where 27
Pualo-rd-r
Therefore, we have
V P U.E.UT = UEV U,, + (V
=VPlalaxd + U,(VE, + Puilext Vptalex.J,.
We can apply Woodbury formula (Hager, 1989) on it.
We can derive
laxd - Up (VIr+ + Pladex)) -1 "(Eit +ieteer V Vplalixt) U,7
(Pialaxd + U,E,U,T)
Vpl.t
A.2. Proof of Theorem 4.1
Before giving the proof of Theorem 4.1, we first introduce some supporting lemmas.
Lemma A.1. (Proposition Duchi et al. (2011)) Let {xi) be the decisions of Algorithm 2 and x" arg min Σ f((x), we have
T Σ fe(x*) s (x('')) 1=1
+ 7 T 2
1
Σ f((x))
lgg 6-112
17
t=1
where vT(x*)= =} {xxx( (x,,o//2 6:12 xx))x*)) )
12

---

Dimension-Fren Free Adaptive Subgradient Methods with Frequent Directions
Lemma A.2. (Lemma 10 in Duchi al. (2011)) Let G₁
Ei=1 Big,
We have
gt. G
(G//2)
22r (G4/2)
ge
2
g6
gt
Then, we illustrate how FD approximates the original matrix.
Lemma A.3. (Remark 11 in Feinberg al. (2023)) With G; =ii= Big: for FD results in FTSL, we have
B, 3 G. 3 G = Plitlaaa + ByB,,
By using Lemma A.I, we can bound the regret of Algorithm 2 by
1 {((s)) Σ f((x)
(x
go 2-212
(4)
1
RD
Re
Then we bound the term RD and Rg, respectively. As for RD, have
vx((")
2
1
GT
1122
x*)
-
2
1
1(x", xx, (BrB] + (CTT) 1/2 x*)
$
1
x², (BT
1/2
x'
1
xx (P
2
2
$
v
P |xx 11
+ 2
xx,
(Gr) 1/2 x-)
2
1
1
$
D2
VPL.
+
D2 Amax Xm
2
2
1
D2 VpT D2 D
1
2
where the first inequality due to Va + bs Va + vb and we assume ||x*|| S D. Therefore, we can get
RD = 1 vT((') s
1 (DeVOL++D D2 tr
(5)
2n
To give the bound for RG. we first derive the lower bound of G.-1, which connects G.-1 with G.. We denote a. Mu--1 max( ||. +p 1} I 1, and we have
G B,-1BII + P1:t-Iaxe
2 a(lgll 1 Iaxa + Pra- + B--1B,
2 (lll 2 Iaxe + G.-1)
x G.Gr
which means 1,1 1
1 at
G-1
Then, letting C₁ m vor
we have
T
T
T -g))
gi
8-102
2
g1
gr (3//)
[=1
1=1
$ C1 Σ
gc (///2/ -
20 22 tr(G)
13

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
where the last inequality is due Lemma A.2. Therefore,
get
" RG
Σ
gd Balla-y S C
(6)
2
By combining inequalities (5) and (6), and setting
we obtain the regret bound for FTSL
R(T) Σ fx(x)) - [(x)) s C n
tr(c
1
D2
VPLT
D2 (r(
2n
t=1
I D 2 +
C1+1
D (
v22
= - + VPL.T).
Notably, the regret bound of Theorem 4.1 can be reformulated, as also presented in Feinberg et al. (2023).
Corollary A.4. We define (GT) Ei=, >:(GT), where X, is the i-th eigenvalue of GT, we can rewrite the regret bound of FTSL as
R(T) S S0 (1r(G//3) +. (rra(CT))
A.3. Proof of Corollary A.4
We first give a lemma to give the upper bound of the cumulative Pu.T-
Lemma A.S. (Lemma I in Feinberg et al. (2023)) The cumulative escaped masses PuT in FD can be upper bounded as
E Xr(TT) (((GT))((GT))
Σ ((GTT) def Xr.a(Gr),
PL.T <
min O....5-1
--k
where the last inequality is to set le = 1.
Combining Theorem 4.1 with Lemma A.5, we can get Corollary A.4.
A.4. Proof of Theorem 4.2
We first introduce some guarantees of the fast frequent directions technique.
In Algorithm 3, we do not perform SVD on the sketching matrix B, every round. Instead, we maintain two matrices M, and
V,, which approximate the sketching matrix B, in Algorithm 2, that is
V.M /2 = B. Rdx27
In each round t, after receiving new gradient gi, we first check whether this vector lies within the subspace spanned by V.11 If the vector is not contained within the subspace, we normalize and subsequently add to V,-1, thereby enlarging the span of the subspace and ensuring Vi-V V_ = gi. In our algorithm design, we want the matrix V, only contains orthonormal vectors, therefore add B to the first all zero column. In round we have
g: 8'll
Vi-1MM-- + gig -V-IMM--VV. + Vi 8ig. V -V--1 -V + V. V/-1) V. V. (M--1 + Vo B.g. V.) V.T
14

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
According to Lemma A.3, we have
V,MVV," B,B, Cr.
In the following, will prove G, 3 G2 which is important for our analysis.
Assume we delete the eigenvalues of Mj in round k, calculate Gj. before we delete the eigenvalues of Mgg in our method. In round k, before we update V2, we have Vi Va-1 and we let V₂ to represent the matrix before we delete its columns.
As perform SVD to V/ [dxx2r, we delete the eigenvalues of MR. update Vi VxU,, and set the last 7+1 columns to zero. In round k 4++1, 1, we have Gk+1 = (diag((maa (k) 1Aah +00)+++++ee 1-1 (1 V k+1 + P1sk+1 Taxds and we can derive
[1:27]
V (diag( max
(k)
X111 0}) + 1+ (V k+1 Patilaxd
")
[1:27]
V (mag
(k)
,0)VV 110h laxd gk+18k+1
[1:27]
2 V&Ugdiaggmaxx {> [1:27]
(k)
, V/ + +1t (VVU)) + gk+18m+1
VVUUidiag(max {X [1:2+]
(k)
A + JU V gh+18
(1 (A)
V gk+18k+1
= =VA.M + g++188++1
(R) where the second inequality is due only first 1 columns of (iag(max(>1122) 1 are non-zero, the first columns of Vk+1 and VgU& same, and Ug and V& orthogonal matrices.
If we do not delete the eigenvalues of M₁ in round k, we have P&+1 = 0 and
M + P141laxd VR+1(M& + Vi Ve+ gk (V. (14418++2) V) K411 V V + g 18:+1
Assume there are most eigenvalues M.. < 27 - 1, and most l + non-zero columns in Ve+1, most & non-zero columns V and the first columns of Ve+1 and VE are same. We have the following
Mx+1 Va+1 Pktilaxd Vi+1 Vi=rUAdiag(A (K) UUN Vi+1 + -g4+18+41 + Olaxd
VyUnddaag A (b) 1:27 YU V/ gk+188+1
V.MAV + g
where the second equality is due to only first elements in (k) Therefore, we have
are non-zero and first columns of Vi and V are same. (1:27))
-. V.M.V + Pialaxa E 1 + PIa-
+ gig. = G 1 + gig.
By summing up, we can get
G 7 ggg Gr.
Next, we need to ensure that after FFD, the preconditioning matrix G, is monotone. It natural to verify that if we do not remove the eigenvalues of Mr. G, remains monotone.
Then, we will prove that G remains monotone even delete the eigenvalues of M,. Assume in round k. we delete
the eigenvalues of Mt. In round k the matrix G Pi:k Taxa + dzUgd (1:21] (X JUT V And G = PiaktTTaxe +
Vi+i M 1- In round 1, since we do not delete the eigenvalues of M 1, the first columns of Ve+1
15

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
of round k 1 and V of round k are same (Notably, V& is different in round & and k + 1). We have M4+1 diag(max { X [:2r] - 2 0,) + (V4428++1)
As we set Pk+1 (*) we can ensure
Gk+1 Pisktlladd + M++1 V+t
=Piktilaxd + V (diag( max (max (1 1 03) + (V+ VVZ+i
= Piiklaxd + (k) laxd + V 1++1diag(man)) (max ( 11:27] - ( .0)V
Plikladd + V (1) LaxaUx Vn +
( ,0)UU V/
= Piikladd + VuUUxdiag( (1)2)))) Va_
Gk:
where the second inequality is due to the r to 2T columns of diag(max (A (R) [:2r]] ,0) is zero and the first 7 - columns of V of round & and Va+1 of round & + 1 are same, can replace Vk+1 with VgUU. and Vk, Up orthogonal matrices.
Therefore, we can ensure G is monotone in FTFSL.
Using the Eq (4), we have the following
T Σ
f(x))
f((x))
1 S
(x((x))
+
g
G
1
RD
RG
As for the term RD. we can derive
RD
1 V
1
xx, G4f2x)
2n
(V. + Laxr 1/2 x*)
2n
(x. (VT 1/2
x+)
+ x", (PiT Taxd) 1/2 x*)
2m
2n
(8)
$
(PLT ldxd) 1/2 ||x*12 +
(x" (Gr)) x*)
2m
21
1
D2
DPITT +
_ (G//2)
1
D22
2m
2n
12
Vp + - tr (c)/
1
21
21
where the second inequality is due to VT BT Gr and we assume ||x*|| < D.
For the term Ro, we denote b, = max
P1
1} < 1, we have
G Vi- + P1:t-1
2 belggel11 Taxa + P1a-1 + B.
be Iaxe + Gr-1)
b.Gr.
16

---

Dimension-Fres Adaptive Subgradient Methods with Frequent Directions
Then, letting C2
[[]]
we can get
vb,"
T
T Σ
T
g
ge,
(G(
gi)
>
(
gt, (G.! gr)
vbl
1=1
t=1
C2
gt (G (
B: Cctt((G])
where the last inequality is due Lemma A.2. Therefore, have
RG
Σ
gg Ball ميي S t
(9)
2
By combining inequalities (8) and (9), and setting v
S we can derive Theorem 4.2.
T
T
R(T) = Σ f((x)) - Σ f((x))
1=1
1=1
< Rn + Ra
1 - = D +2
$ 2n
D2 VPI.T +
2n
((tr(G]//) + vPir).
A.5. Proof of Theorem 4.3
According to the proof of Theorem 4.2, we have the following properties in FFD:
V/M B1, VU,,UU V. = G. G..
Similar to the proof of Theorem in Feinberg et al. (2023), we have the following lemma:
Lemma A.6. Let {x:} be the decision of Fast S-ADA and x" E arg min Σt= f((x), the regret bound of Fast S-ADA
is
T X
T
R(T) S
2T
x"
12
6:/2
+
2
go 6-1/22 1/2.
[=1
t=1
According to Lemma A.6, we have
T
R(T) < 2m
xx -
x"
2
6:/2
+
"
ge
6-1/2.
2
t=1
We first bound the term 3 E |g: 1 1/2, which is easier to bound than that in FTFSL,, as we can directly apply lemma
on it.
lg G-- 1/2
8c (G1/2)-1ss) (8)
$ Σ gri (G//2) /g)
$ 22br(
17

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
where the fist inequality is due G,' G2-
and the last inequality is due Lemma A.2.
Next, we bound the term
Σ
Xx+ -
llay 01100 - which introduces the dependence on dimensionality d. We have
27j
1
Dj tr x x 1lyy S 2n
(
21j
where this inequality is due to monotonicity of G. and D1 max ||x - x*11.
Then need bound the term tr (Gx/)
Assume we delete the cigenvalues of M2 at round k. In round k, before we update Ve, V/. = Va-1 and we use V₂ to represent the matrix before we delete columns.
As we perform SVD to V.M Idx22, we denote V e Rd to be the first T columns of V&U*& before we set the last T + 1 columns to Oa. N& E (dx(d-r) be the complementary subspace of V. and the first t columns of V and VET are same, Pk++ (h) and NNllV N&&l" Laxd.
In round & + 1, we have G441 Vi+1 (0-11diage (diiggmaaaa [1:27] - (1)) ,0)) + (84 + Pick+1 Laxds and we can derive
(k)
(dia(diag(max/
X 11:2-1
, + VI+ (V+ Vitt + Pa+1laxd
Vi+idiag (max
(K)
1 .0)V 1 Laxd 18+18BT
[1:2r]
V&Ugddaa maxx (
(1)
[1:27] 140,0) Vo + (V=''(V N,N, + g++1gH+1
= <VUUddaag maxx
(K)
(k) , Vo + A (MUU(VV))) + NoNT gk+18R+1
[1:27]
VVUuddiag ( (1:27 VK + NoNV g8418
=A NE + V g8+118441
- + V. + gg+1gg+1
where the second equality is due to only first r columns of (mag(max{>))) [1:21] (x) are non-zero and the first 7 columns of V and Vg same, the first inequality is due V. only contains orthogonal vectors at most. If we do not delete the eigenvalues of M& in round k, we have P&+1 = 0 can derive
(k)
Mx+1 Va+1 + Pb+ilaxd Ve+I(M, + V 18 V
-Ve+1 k+41 + g++1g
M VITH
6+1 + g8+
=ONANT + VR+IMA + B
N + Ve+1URdiagl (A ( U VIT + g gg-18
Assume there are most l eigenvalues in M3. 2 therefore, there are most / non-zero columns in V most l non-zero columns in V, and the first l columns of Vx+1 and Vj same. We have the following
Ve41 M Ve+1 + Pk+ I Iaxa NN + V Un Undiag(1 (K) (122)) UU VLL + gx+18
-N + ViUgndiag( (1 ) UU Vo + -g++18++1
(10)
= = + diUg 1:27 UU V + ge+18e41
= PP V gg+1g
where the second equality due to there are most non-zero elements (k) same, and the third equality is due pk+1
and first & columns of Vs and V4+1 are (1:27]
18

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Therefore, have By reduction, we have
Mx41 Ve+1 + Pk+ilaxd 3 P V& + +
GT VT + Pi.Tladd
1V-1 + Pr + +gggT I PIT--llxd + -I--Mr--V--
T
D.N Σ gigt
P.N. GG.
Then we can rewrite the bound of tr(()/) as tr(()//) + (.NN,, 1/2).
We just need give bound of tr PCNoNN According Corollary 4 in Feinberg et al. (2023), the upper bound of this term is
tr((
PrNoNT)1113) S /d(d-r)p1s
Then we can derive the bound of tr tr(
T (r(()/) s ir(c2/3)
+ir(() 2 12 S <ir(o)/2) vd(d T)p1T
By setting 77 Di V2*
we have
R(T)- Σ [xxx) Ex(x)
Σ Xx x" x1122100011 + Σ gr 8 1/2
$ 2n
Dt
(tr(G2/12 + /d(d - -TPP:T) ) + (t
- 2n
< tr (r(( + v d(d -)Pp:T
A.6. Proof of Theorem 4.4
In the following, we give the proof Theorem 4.4.
Due to the update in Algorithm 5 is performed the matrix space, poses challenges for the analysis. Therefore, we first introduce an equivalent update in vector form.
Recall the update in Algorithm 5, X, = -n 1/4 G.¹² R-1/4 We define H, = i. @ R!/1 E Rmaxmm L, L e Rmxm R2 = R. E _ gi= = (ec(G,)) and X, = (e)( where vec denotes the row-major vectorization a given matrix, Kronecker product @ obeys the following properties as shown in Gupta al. (2018).
19

---

Dimension- Free Adaptive Subgradient Methods with Frequent Directions
Lemma A.7. (Lemma 3,4 in Gupta al. (2018)) For matrices A, B, B' of appropriate dimensions and vectors x, x,y,
L R R. Raxx, G Rmxx, the following properties hold:
1. (A O ()' @ B = (AA) @ (BB)).
2. (A B) A B
3. A, 0, (A B) A B-1
Az A', B= B,, then A B = A @ B'.
5. tr(A 8 13) = (t(A)tr())
6. vec(xy = &
7. (L R vec = vec LGR).
By defining 8, = Σi= gi, we can rewrite the update in Algorithm 5 as
Xt+1 = -n,1, 'g:
which is equal to
X = arg 1 (,,, + 2 Ht
||x|]
xmRm
As L, and Rg is monotonically increasing with f, it is not hard to find that H, is also monotonically increasing with t. Thus, by using Lemma A. we have the similar inequality:
T
1 R(T)
7
-
V
gt
(11)
7
RD
RG
where (x(x)) (xx,, H.xx)
We first give the bound of R...
VT((")
1 2 (x", Hrxx
1
|
Ar
1x
2
Then we introduce a lemma give an equality about the norm of Kronecker product.
Lemma A.8. (Theorem 8 in Lancaster & Farahat (1972)) For two matrices A and B, the following equality holds
||A @ B|| = ||||| |||
We have ||x*|| || DM. According to Lemma A.8, | |2+4 & R444
R//l|. then |/ respectively. We first define LT E G + eTmxm and
|
need to give the bound of | and
RT = DT= (GN) GØ + elaxn. Using Lemma A.3, it is not hard to verify that Le + Emmxm I Lr, Rr + eenxn I R..
Therefore, we have
11/4
LT + elmxm + Pl:y Im mm) 3'all
Lr + cImxm) 1/4 + (pt (mxmm) 2///|
Ter + elm xm 1/4 + /
(IT elm 1/4
+ ( 1/4
< ir((TT + et mmxxm)
1/4))
+ ) 1/1
< (r(L (pt.x) 2/4
20

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
where the fourth inequality is due to have for positive semidefinite matrices ir(-) 2 ||-Il and last inequality is due the monotonicity of tr( (r()).
We also have
11/4 RT
(RT + elaxn + pf: I 1nxa)!/4
Rr + claxn) 22/4
(p (nx )2/4
RT + tl xx 1/2
+ ||0fTT 1/4 1xx
(Tr + cluxn) 1/4
+ (p!-r))/4
tr((RT + oT 1//)) 1/2)
+ (1f
s tr + (p/:))) 11/4
Therefore, get
1 RD 1)
(x((x') - (tr(L (pL:1) ((T(())) 144.
D& 21
(12)
To give the bound of RG, we first introduce a lemma.
Lemma A.9. (Lemma 8 in Gupta et al. (2018)) If G. E mR with rank at most r, and g: veo(G?)) then Ve 2 0, V4,
1/2
1/2
mmaxxmn
gig.
<mmxm=
Σ G (O,)))
@ (dIxx E(ON)
Then we utilize lemma in Feinberg al. (2023).
Lemma A.10. (Lemma 14 in Feinberg et al. (2023)) Let V.E.V, I,-1+ G. (Gx) T be the eigendecomposition of the un-deflated sketch. We assume rank(F.{)) k, E [r 1--1, - Write V = [V: V where V, contains the first k columns of V₁ And for the right conditioner W, w WT = +G G Write W2 = [W W.-], where W contains the first k columns of W. Define No = (V,-)) and N = WW((W,) then we have
L = (T + Σ Nf Elmxm =M
Rd Σ (G TG
Σ of N eInxa M.R.
According to Lemma A.3 and Lemma A.10, we have Mr t elmxm + Ei=I ( and M 2 elaxn + (GL Using Lemma A.7, we can derive
1mxm& & Elnxn+ + [(GN)T = 4mxm @ MR,
[elmxm + Σ CX(CXT] 8 Inx I MM & Luxn.
1
Therefore, we have
g:g; 1///2 - (M 1/4 2 (M (M,))/4 = i.I4 & R = H.
1/4
(cImnXmn +
1=1
1/2
Then we define A = (reImaxmn + - g:g.
and can have
A. VrHl.
21

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
We want give the lower bound of H1-1- By defining Ct
have
1r +re
ff = relmmxmn
gig.
= alglll mmnxmn
Σ
8:g, + re relmmxmm)
1=1
= mrcImmx
gig:
c.A..
Define A1 min (T) We have A,H, 1 Hi-1 3 Vi which means
J H H
We can derive
T
T Σ
gr
gr 11 18)
S vr
ge, 1,,1118
1=1
gt H 1 gt
A
Based on the proof of Theorem 5 in Feinberg et al. (2023), we obtain the following inequality.
Σ
ge Hi 1 gt s 2rr((
Therefore, we have
T
vr T A 1=1
2 (ilr(ftr).
gr
2
S
B1: H 8: S
1=1 1
A1
Then, we need to bound the term HT.
1/2
1/2
ft: = (reI Σ g:g, ) r r elmxm
>
[
eInxn + E
rr
1/2
which means A. = / R//4
By defining C3- A we can derive the bound of RG-
7 RG
Σ g: 12 S (nCaFFtr((Tt))
2
S (1 tr((e(
By setting 7 = Dy the final regret bound is vF
T
D2 (cr(z)/t) + (pT.t) + 114)
Σ f((x)) - f((x*) s (Csttt(L)) tr R1/4)+ +
2n
S (TL + FiDM (ur(L) / + (ott)) ((T + 2/4) (13)
2
(ot + 1/4)
22

---

Dimension-Fren Adaptive Subgradient Methods with Frequent Directions
B. Online to Batch Reduction
Algorithm 6 Online to Batch Conversion
1: Input: Time horizon T. rounds N, smoothness parameter L, OCO method A
2: Initialize X, to be any point in the domain
3: for t= 1 to T do
4: Construct fx(x) = f(x) + ||x - X
5: Set x = Xx and pass x to A
6: i to do
7: Play x derive the gradient V (x Er), and construct g((x) Ex)
8: Send (x) to A and receive x;
9: end for
10: Update X++1 = N Σ x
11: end for
12: Return X3 = arg min [xx)))
In this section, we give some details for the reduction of non-convex stochastic optimization online convex optimization for completeness. We use the framework of Agarwal et al. (2019), which Feinberg et al. (2023) also adopt before. Under this framework, we optimize a non-convex loss function fxx through construcing a new loss function fx(x = fxx + L ||x - x112² 1 which is strongly convex. In each round, we pass the loss function ft(x) to any OCO method, A, (it can be any algorithm this paper), and use AA to optimize it for rounds. When deriving the stochastic gradient, we use a batch & to derive fx(,x; Es), which satisfy fxx;; Et) = fx((x, and f( - V fx( S o². The algorithm stated in Algorithm 6, and we provide the convergence guarantees in the following. We first define the adaptive ratio.
Definition B.1. We denote x be the output of an OCO method A and x" E arg minxeR f(x), we define the adaptive ratio of A as
f(xA) f(x*)
(A(
x - x 1
Then we provide the convergence of this reduction.
Theorem B.2. (Theorem A.2 in Agarwal et al. (2019)) We assume fxx is L-smooth. (V2((xx)) I L, maxx,y f(x)
f(y) S F, [t 5 - (x(x))111 S o², and max; (A(fe). By setting T 12ML and N 48y20² the
output of Algorithm 6 satisfies
E [|[V
is evident that the total number of queries to the stochastic gradient oracle is 0(1302/e))
By using this framework, can translate the regret bound of an OCO algorithm into convergence guarantees for stochastic optimization.
C. Full experiments
In this section, we conduct empirical studies to evaluate our proposed algorithms. In online classification task, we compare our methods with ADA-DIAG (Duchi al., 201 RADAGRAD (Krummenacher al., 2016), FD-SON (Luo al., 2018), ADA-FFD under two frameworks (Wan Zhang, 2022) and S-ADA (Feinberg et al., 2023). In image classification task and language modeling task, compare methods with ADA-DIAG, ADA-FFD under two frameworks, S- ADA, Shampoo (Gupta et al., 2018), S-Shampoo (Feinberg et al., 2023). When it comes to hyper-parameter tuning, we either set the hyper-parameter as recommended in the original papers or tune them by grid search. For example, for learning rate 7 and regularizer parameter c, we search them from the set {le - 5, 1e 4, le - 3, le 2, le - 1, and {le 5, le 4, le - 3, 1e - 2, le 1,1, 5). respectively, and select the best one. All experiments are conducted on 8 NVIDIA 3090 GPUs.
23

---

Dimension-Fren Free Adaptive Subgradient Methods with Frequent Directions
200
98
Accuracy
96
150
100
Loss
Time
94-
100
50
50
90
0
0
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2000
of iterations
# of iterations
# of iterations
ADA-DIAG
RADAGRAD
FD-SON
ADA-FED (M)
ADA-FED
S-ADA
Fast S-ADA
FTFSL
Figure 3. Results for Gisette dataset.
90
88
1500
60
Accuracy
86-
Loss
1000
Time
84-
500
20
82
80
2000
4000
2000
4000
2000
4000
# of iterations
# of iterations
# of iterations
ADA-DIAG
RADAGRAD
FD-SON
ADA-FFD (M)
ADA FDD-FFDOG (P)
S-ADA
Fast S-ADA
FIFSL
Figure 4. Results for Epsilon dataset.
95
Training loxs (log scale)
Texing accuracy
0,9
1.0
Testing loss
-2.54
85
0.8
Time
5.0
80
0.6
7.5
0.4
75
50
100
150
200
50
100
150
200
50
100
150
200
%
50
100
150
200
of iterations
of iterations
of iterations
# ofeeriations
ADA-DIAG
ADA-FFD (M)
ADA-FED (P)
SDDDA
Shampoo
Shampoo
FIFSL
FTSL- -SLmpoo
Figure 5. Results for CIFAR-10 dataset.
C.I. Online Classification
First, we perform online classification evaluate the performance of our methods with two real world datasets from LIBSVM (Chang & Lin, 2011) repository: Gisette and Epsilon, which high-dimensional and dense. Particularly, Gisette contains 6000 training samples and 1000 testing samples, with 5000 features. Epsilon dataset consists of 400, 000 training samples and 100, 000 testing samples, with 2000 features. Let T denote the number of total rounds. In each round E [7], a batch of training examples {(wr,1 Vt,1) ..... (Wr.ns Vt,n)) arrive, where (Wr,i, Vt, E []1, {-1,1),i 1,..., The online learner aims to predict linear model x, and suffers the hinge loss fx(x,) = Σ"= max(0, yix; w.,)-
Setup. For Gisette, we set the batch size n 32, the = 50 to be 1 % of the original dimensionality, and 2000. For
24

---

Dimension- Free Adaptive Subgradient Methods with Frequent Directions
75
Testing accumiyy
Testnn Joss
0.0
63
2.5
2255
Time
2.0
Training
5.0
2-
50
50
100
150
200
50
100
150
200
7.5
100
150
200
100
150
200
iterations
of Eltertiions
of iterations
of iterations
ADA-DIAG
ADA-FED (M)
ADA-FED (P)
S-ADA
Shampoo
S-Stampoo
FTFSL
FTSt-Shumpoo
Figure Results CIFAR- 100 dataset.
Epsilon, we set the batch size n = 128, the 20 and T = 5000 to pass through all the training data.
Results. Following Duchi et al. (2011), we adopt the performance of accuracy on the testing data to compare different methods. To better demonstrate the improvements our methods, we additionally plot the loss and runtime (measured in seconds) of various methods. From Figure 3 and Figure 4, we observe that FTFSL outperforms all other methods in both loss and testing accuracy, aligning with its superior regret bound. Moreover, FTFSL and Fast S-ADA exhibit significantly lower runtimes compared to S-ADA, owing to their superior time complexities.
C.2. Image Classification
In this section, conduct numerical experiments multi-class image classification tasks evaluate the performance of the proposed methods, compare FTFSL and FTSL-Shampoo with several baseline methods. The experiments involve training R and ResNet34 models (He et al., 2016) on the CIFAR-10 and CIFAR-100 datasets (Krizhevsky, 2009),
respectively, for 200 iterations with batch size of 128.
Setup. For ADA-FFD, S-ADA, FTFSL, the sketching size is determined based on dimensionality of flattened gradient, which is defined as:
min min [[d x 0.1], 100),
where d represents the total elements parameters in each layer. We dynamically set the upper bound of the sketching size based on dimensionality of each layer. For S-Shampoo and FTSL-Shampoo, due to its memory efficiency, we set
[0.1 1, where de is the dimensionality of the i-th dimension of a gradient. For the sake of fairness, we do employ momentum trick.
Results. We plot the loss value and the accuracy against the iterations on the CIFAR-10 and CIFAR-100 in Figure 5 and Figure 6, respectively. It observed that, for training loss and testing accuracy, our FTSL-Shampoo achieves comparable performance with respect to Shampoo, while significantly improving memory efficiency and reducing running time, which aligns with the theoretical guarantees. Additionally, our FTFSL converges more quickly than other sketching based algorithms, indicating the effectiveness of the proposed method. Moreover, we also present the running time of each method. FTFSL demonstrates a significant reduction in running time compared S-ADA, owing to its improved time complexity.
400
5.00
Texting perpleeer
Training loss
Teating loss
3:75
1.0-
300
5.5
5.50
5.0
0.5
200
5.25
10
20
30
5.00
20
30
0.0
10
20
iteraiions
of iterations
iterations
ADA-DIAG
ADA-FED (M)
ADA-FFD
S-ADA
Shampoo
S-Shampoo
FTFSL
FTSI-Shhampoo
Figure 7. Results for WikiText-2 dataset.
25

---

Dimension-Free Adaptive Subgradient Methods with Frequent Directions
C.3. Language Modeling Task
In this section, we perform experiments on language modeling task. Concretely, we train a 2-layer Transformer (Vaswani et al., 2017) over the WiKi-Text2 dataset (Merity, 2016). We use 256 dimensional word embeddings, 256 hidden unites and 2 heads. We also clip the gradients by norm 0.5 in case of the exploding gradient. The batch size is set 64 and all methods are trained for 40 epochs with dropout rate 0.1.
Setup. The experimental setup follows that of image classification. For computational efficiency, we do not employ a preconditioning matrix in the embedding layer.
Results. We report the loss, perplexity and the run time in Figure As can be seen, FTFSL and FTSL-Shane Shampoo suffer lower loss and obtain better perplexity compared other sketching based algorithms, indicating the effectiveness of the proposed methods. Morcover, FTFSL exhibits markedly improved efficiency over S-ADA.
26


Reviews:
[{"review_id": "uxhJXLzxXI", "reviewer": "Reviewer_5FxL", "summary": "The paper proposes adaptive subgradient methods for online convex optimization that have better regret bounds and time complexities than existing methods. This is achieved by analyzing the frequent directions in the primal-dual framework.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments!\n\n---\n\nQ1: Since the loss functions are only assumed to be convex and hence can be non-smooth, the paper should be careful not to mix gradients and subgradients and clearly indicate whether their arguments work for every subgradient or just one particular subgradient in the subdifferential. \n\n\nA1: Thank you for pointing out this misuse. Actually, the analysis of FTSL does not require the smoothness. We utilize the convexity of the loss functions in Lemma B.1, which uses the subgradients and works for every subgradient. We will correct this misuse in the revised version.\n\n---\n\nQ2: The work makes heavy use of existing techniques. It will be good to explain how the new techniques developed in this paper have applications in other settings.\n\n\nA2: Thank you for your suggestion. We present two potential applications of the new technique:\n* **LLM fine-tuning.** Our sketching technique can be incorporated into LLM fine-tuning. For example, parameter-efficient fine-tuning (PEFT) methods (Zhao et al., 2024) update models for each task within multiple subspaces. We can use this technique to merge them into a single subspace, making the updates more stable.\n* **Bandit problem.** Our sketching technique can also be applied to bandit settings, such as the logistic bandit (Filippi et al., 2010) and the multinomial logistic bandit (Amani and Thrampoulidis, 2021). For example, in the multinomial logistic bandit problem, MNL-UCB needs to maintain a high-dimensional Hessian matrix, which incurs high computational costs. By applying the sketching technique, we can reduce its space and time complexities.\n\n**Reference:**\n\nJiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, Yuandong Tian. GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection. ICML, 2024\n\nSarah Filippi, Olivier Cappe, Aurélien Garivier, Csaba Szepesvári. Parametric bandits: The generalized linear case. NeurIPS, 2010.\n\nSanae Amani and Christos Thrampoulidis. UCB-based algorithms for multinomial logistic regression bandits. NeurIPS, 2021.", "claims_and_evidence": "The claims are supported by clear evidence.", "methods_and_evaluation_criteria": "The proposed evaluations seem standard and make sense. They showed some advantages of the proposed approach.", "theoretical_claims": "I have gone through the proofs quickly, and they look mostly fine. Since the loss functions are only assumed to be convex and hence can be non-smooth, the paper should be careful not to mix gradients and subgradients and clearly indicate whether their arguments work for every subgradient or just one particular subgradient in the subdifferential.", "experimental_designs_or_analyses": "I have gone through the experiment designs and analyses and found them to be in order.", "relation_to_broader_scientific_literature": "The paper makes use of a number of ideas from the literature, including frequent directions, the primal-dual framework, and adaptive methods in online convex optimization. The results are obtained by combining these elements in a new manner.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strengths:\n- Improved regret bounds and time complexities over existing methods.\n- Numerical results show the efficacy of the proposed methods.\n\nWeaknesses:\n- As mentioned earlier, the non-smoothness of the loss functions should be handled more carefully in the analysis.\n- The work makes heavy use of existing techniques. It will be good to explain how the new techniques developed in this paper have applications in other settings.", "other_comments_or_suggestions": "See the comments above.", "questions_for_authors": "See the \"Other Strengths And Weaknesses\" section.", "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": "B4zKomKeOY", "reviewer": "Reviewer_GoSK", "summary": "This work proposed an adaptive online subgradient method with frequent directions. The main contribution is the regret bound is dimension-free and the algorithm only requires the time complexity of $O(\\tau d)$ in each iteration.\n\n## update after rebuttal\nAll of my questions have been addressed. Hence, I would like to increase my overall rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback!\n\n---\n\nQ1. The literature review should be more appropriate. \n\nA1. Thank you for bringing these related works to our attention. After checking the papers, we acknowledge that the idea of adaptive FD by incorporating the cumulative discarded information is first introduced by Luo et al. (2019) and Chen et al. (2020). We sincerely apologize for the omission of these work and will include a discussion of them in the revised version. \n\n---\n\nQ2. The comparison with SCFD (Chen et al., 2020).\n\nA2. Although our sketching technique is similar to SCFD, the setting and algorithmic design of our work are fundamentally *distinct*:\n* Chen et al. (2020) focus on linear contextual bandits, while our work investigates the *general online convex optimization* problem. \n* Their method is based on LinUCB, whereas our FTSL/FTFSL and FTSL-Shampoo are based on ADA-FULL and Shampoo, respectively. \n* Due to the *essential distinctions* in settings, our algorithmic design and theoretical analysis are different from Chen et al. (2020).\n\n---\n\nQ3. Is it possible to replace the low-rank assumption with an approximately low-rank assumption?\n\nA3. First, we would like to emphasize that Assumption 3.3 is _only_ used in the analysis of FTSL-Shampoo. Moreover, the analyses of Shampoo and S-Shampoo also utilize this assumption. In our paper, Assumption 3.3 is used in Lemma B.9 to give the lower bounds of the sketching preconditioning matrices.\n\nSecond, we can replace Assumption 3.3 with the approximately low-rank assumption. However, it would introduce an additional approximation term in the final regret, leading to a difference from the bounds of Shampoo and S-Shampoo.  We consider this modification as a direction for future research.\n\n---\n\nQ4. Can we guarantee $\\tilde{G}_t$ be non-singular during iterations?\n\nA4. In fact, $\\tilde{G}_t$ is not always non-singular. It is _singular_ in the early stages of the iteration. According to Step 8 of Algorithm 2, it becomes _non-singular_ after a certain number of iterations. When $\\tilde{G}_t$ is singular, we use the Moore-Penrose pseudoinverse in our analysis. In practice, we can ensure its non-singularity by adding a small regularization term $\\epsilon I_d, \\epsilon > 0$ into $\\tilde{G}_t$.\n\n---\n\nQ5. The word “gradient” in many sentences should be replaced with “subgradient”. \n\nQ6. Minor comments.\n    \nA5 & A6. Thank you for pointing out these typos. We will correct this misuse and some minor typos in the revised version.\n\n**Reference:**\n\nLuo Luo, Cheng Chen, Zhihua Zhang, Wu-Jun Li, and Tong Zhang. Robust frequent\ndirections with application in online learning. JMLR, 2019.\n\nCheng Chen, Luo Luo, Weinan Zhang, Yong Yu, and Yijiang Lian. Efficient and robust high-dimensional linear contextual bandits. IJCAI, 2020.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The theoretical claims sound correct.", "experimental_designs_or_analyses": "The experimental designs and results sound reasonable.", "relation_to_broader_scientific_literature": "See the part \"Questions For Authors\".", "essential_references_not_discussed": "See the part \"Questions For Authors\".", "other_strengths_and_weaknesses": "See the part \"Questions For Authors\".", "other_comments_or_suggestions": "See the part \"Questions For Authors\".", "questions_for_authors": "The main comments:\n1. The literature review should be more appropriate. The idea of adaptive FD by adding the cumulative discarded information of FD back was first proposed by Luo et al. (2019) and Chen et al. (2020), and their time complexity have achieved $O(\\tau d)$ by using the similar trick in Section 4.2. The main contribution of Feinberg et al. (2023) is improving the regret bound of Luo et al. (2019).\n2. The comparison with Spectral Compensation Frequent Directions (SCFD) (Chen et at., 2020) should be discussed. It seems that both this paper and Feinberg’s et al. (2023) method use SCFD to approximate $G_T$.\n3. Assumption 3.3 looks very strong although it is introduced in previous work. Is it possible to replace the low-rank assumption with an approximately low-rank assumption?\n4. Can we guarantee $\\tilde G_T$ be non-singular during iterations?\n5. The experiments test the algorithms on nonsmooth hinge loss, and I find the analysis also does not rely on the smoothness of the loss function. Therefore, the word “gradient” in many sentences should be replaced with “subgradient”. The notation $\\nabla f_t$ is also somewhat inappropriate.\n\nThe minor comments:\n1. The font of vec in Lemma B.7 should be consistent to the description before this lemma.\n2. The domain of $\\bf x$ is required in line 1051.", "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": "9ecWknGOtE", "reviewer": "Reviewer_KDEM", "summary": "In machine learning, the seminal work [DHS'11] proposed the adaptive subgradient method with full matrices (ADA-FULL), which requires maintaining a preconditioning matrix with $O(d^2)$ space and $O(d^3)$ running time. However, ADA-FULL suffers from high-dimensional dependence in its regret bound and computational complexity, making it inefficient for large-scale optimization problems. To address these limitations, several methods have been proposed, including ADA-FD [WZ'18] and S-ADA [FCSAH'23], which leverage matrix sketching techniques to reduce computational costs. This paper further advances the acceleration of adaptive subgradient methods by integrating Frequent Directions (FD), a powerful matrix sketching approach. Specifically, it introduces the Follow-the-Sketchy-Leader (FTSL) method, which improves regret bound, space efficiency, or time complexity compared to prior works. Additionally, the paper extends these techniques to Shampoo, a second-order optimization method, resulting in the FTSL-Shampoo algorithm, which enhances memory efficiency and achieves dimension-free theoretical guarantees. Experiments on real datasets for online classification and image classification tasks demonstrate that the proposed methods outperform existing approaches in terms of test accuracy and running time.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your constructive feedback!\n\n---\n\nQ1. FTSL and FTFSL have the same complexities with ADA-FD(P) and ADA-FFD(P), and regret bounds are close. \n\nA1. We acknowledge that the proposed methods have the same time and space complexities with ADA-FD(P) and ADA-FFD(P). However, we want to clarify that our regret bounds have a significant improvement compared to them. \n* The additional error terms in ADA-FD(P)/ADA-FFD(P) and FTSL/FTFSL are $\\sum_{t=1}^T \\sqrt{\\rho_{t}}$ and $\\sqrt{\\sum_{t=1}^T\\rho_{t}}$, respectively.\n* As you pointed out, we have $\\sqrt{\\sum_{t=1}^T\\rho_{t}}\\leq\\sum_{t=1}^T\\sqrt{\\rho_{t}}\\leq\\sqrt{T\\sum_{t=1}^T\\rho_{t}}$, which means that there exists‌ a large gap of $\\sqrt{T}$ in the worst case. Note that $T$ is the number of iterations, which keeps on increasing, and cannot be ignored.\n* Moreover, as discussed in Observation 2 of [FCSAH'23], the regret bound of ADA-FD(P)/ADA-FFD(P) is $\\Omega(T^{3/4})$ in some cases, while FTSL/FTFSL achieves a better $O(T^{1/2})$ bound, providing a substantial advantage. We provide the proof below.\n\nAccording to [FCSAH'23], there exists a situation, we receive the linear loss $f_t(\\textbf{x}) = \\langle\\textbf{x},\\textbf{g}_t \\rangle$, where $\\textbf{g} _t \\in \\mathbb{R}^d$ is a random vector drawn iid from any distribution over $r\\leq d$ orthonormal vectors.  \n\nAs pointed out by [FCSAH'23], for any $\\tau\\leq r$, the bound on the expected regret of ADA-FD(P)/ADA-FFD(P) is $\\Omega(T^{3/4})$. \n\nThe regret of FTSL/FTFSL is $\\eta \\text{tr}(G_T^{1/2})+\\frac{1}{\\eta}\\sqrt{\\sum _{t=1}^T\\rho _{t}} \\leq \\eta \\text{tr}(G_T^{1/2})+\\frac{1}{\\eta}\\sqrt{T\\max _{t\\in [T]}\\rho_t} \\leq O(T^{1/2})$, where the last inequality is due to $\\text{tr}(G_T^{1/2}) =O(T^{1/2}), \\rho_t = 0$ or $1$, and setting $\\eta = O(1)$.\n\n---\n\nQ2. Both this paper and ADA-FD/ADA-FFD integrate FD with ADA-FULL, which limits the novelty.\n\nA2. While both our paper and ADA-FD/ADA-FFD integrate FD with ADA-FULL, there do exist significant differences from them.\n\n* Compared to ADA-FD and ADA-FFD, our algorithm tracks the information discarded in FD and incorporates it back into the preconditioning matrix, achieving a better regret bound. \n* Our work additionally considers a more practical setting, optimization problems with matrix variables. We integrate FD with Shampoo and provide a novel analysis under the primal-dual framework. The dimension-free theoretical guarantee is another contribution of this work.\n\n---\n\nQ3. In Figures 3 and 4, FTFSL doesn't have a significant advantage over ADA-FFD (M). In Figures 5 and 6, FTSL-Shampoo exhibits performance comparable to Shampoo and S-Shampoo. \n\nA3. We believe there might be some misunderstandings in this part.\n* Actually, in Figures 3 and 4, FTFSL (red line) outperforms ADA-FFD (M) (pink dashed line) in terms of testing accuracy and training loss. \n* We want to clarify that FTSL-Shampoo is an approximate version of Shampoo, aiming to enhance computational efficiency while maintaining comparable effectiveness. FTSL-Shampoo utilizes less information in each round for updates (some eigenvalues are discarded). In Figures 5 and 6, FTSL-Shampoo exhibits performance comparable to Shampoo, while significantly improving memory efficiency and reducing running time, which aligns with the theoretical guarantees.\n* As demonstrated by the experimental results, FTSL-Shampoo (orange line) substantially outperforms S-Shampoo (blue dashed line) across all metrics, including testing accuracy, testing loss, and training loss.\n\n---\n\nQ4. This paper evaluates methods on only four datasets.\n\nA4. Following your suggestion, we conduct experiments on an NLP task, and the results can be found at the following anonymous link: https://anonymous.4open.science/r/ICML-14491/results.pdf. \n\nConcretely, we train a 2-layer Transformer over the WiKi-Text2 dataset. We use 256 dimensional word embeddings, 256 hidden unites and 2 heads. The batch size is set as 64 and all methods are trained for 40 epochs with dropout rate 0.1.  As can be seen, FTFSL and FTSL-Shampoo suffer lower loss and obtain better perplexity compared to other sketching based algorithms, indicating the effectiveness of the proposed methods.\n\nAdditionally, we would like to take this opportunity to clarify that the primary contribution of this paper lies in the theoretical aspects, which includes the following three key points:\n* First, we propose FTSL, which achieves a dimension-free regret bound and maintains the same memory complexity as previous works.\n* Second, we develop Fast S-ADA and FTFSL to further reduce the time complexity, while preserving the same regret bounds.\n* Next, we investigate optimization problems with matrix variables, a scenario commonly encountered in deep learning tasks. FTSL-Shampoo enjoys an enhanced theoretical guarantee than S-Shampoo [FCSAH'23].", "claims_and_evidence": "I believe so, though I haven’t carefully reviewed the proofs in the appendix.", "methods_and_evaluation_criteria": "Yes, this paper compares with prior works on two tasks: online classification and image classification, in terms of test accuracy, training or test loss, and running time.", "theoretical_claims": "I didn't read the proofs in the appendix.", "experimental_designs_or_analyses": "Yes, I reviewed the experiments in Section 5 and Appendix D. In online classification, the proposed methods are compared with prior works on the datasets Gisette and Epsilon of LIBSVM; in image classification, the experiments are implemented on CIFAR-10 and CIFAR-100.", "relation_to_broader_scientific_literature": "This paper integrates FD with Shampoo to develop FTSL-Shampoo, which provides improved efficiency for optimization problems with matrix variables (e.g., neural network training).", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "$\\textbf{Strengths:}$ (1) This paper combines FD with ADA-FULL and proposes some new methods, including FTSL, FTFSL, and FTSL-Shampoo. On the theoretical aspect, these new methods improve the existing works with respect to regret bound, space or running time.  \n(2) The experimental results indicate the efficiency of the proposed methods on two real tasks.        \n\n$\\textbf{Weaknesses:}$ (1) In Table 1, the proposed method FTSL has the same space and time complexity with the method ADA-FD (P), and their regret bounds are quite close due to $\\sqrt{\\sum_{t=1}^{T} \\rho_t} \\le \\sum_{t=1}^{T} \\sqrt{\\rho_t} \\le \\sqrt{T \\sum_{t=1}^{T} \\rho_t}$. Likewise, in Table 2, FTFSL and ADA-FFD (P) have the same situation. Consequently, from a theoretical perspective, the proposed methods FTSL and FTFSL do not offer a clear advantage over existing works.   \n(2) From a technical perspective, both this paper and the works ADA-FD/ADA-FFD adopt the framework that integrates FD with ADA-FULL, which somewhat limits the novelty of this paper.    \n(3) For the experiments, in Figures 3 and 4, the proposed method FTFSL doesn't have a significant advantage over other methods, like ADA-FFD (M); similarly, in Figures 5 and 6, the proposed FTSL-Shampoo method exhibits performance comparable to the prior methods Shampoo and S-Shampoo.   \n(4) This paper evaluates the proposed methods on only four real datasets for online classification and image classification, which is relatively limited and weakens the assessment of their effectiveness.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See Weaknesses.", "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:

Meta-review: The paper proposes a new algorithm called Follow-the-Sketchy-Leader (FTSL), which is an adaptive subgradient method for online convex optimization. It shows that the algorithm improves upon the existing regret bounds and time complexities. While the reviewers appreciate the new results, they also indicate that the contributions need to be better articulated, especially since the technical development seems to draw heavily on existing techniques. Also, as one reviewer pointed out, the rigor of the presentation needs to be improved. The author(s) should take the reviewers' comments into account when revising the paper.
Decision: Accept (poster)