Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization
Authors: Hanmin Li
Avetik Karagulyan
Peter Richtárik
Venue: ICLR 2024 poster (2024)
Keywords: Optimization
First-order optimization
Non-convex optimization
Distributed optimization
Primary area: optimization
TL;DR: We propose two matrix stepsized sketch gradient descent algorithms for minimizing matrix-smooth non-convex objectives.

Abstract: This paper introduces a new method for minimizing matrix-smooth non-convex objectives through the use of novel Compressed Gradient Descent (CGD) algorithms enhanced with a matrix-valued stepsize. 
The proposed algorithms are theoretically analyzed first in the single-node and subsequently in the distributed settings. Our theoretical results reveal that the matrix stepsize in CGD can capture the objective’s structure and lead to faster convergence compared to a scalar stepsize. 
As a byproduct of our general results, we emphasize the importance of selecting the compression mechanism and the matrix stepsize in a layer-wise manner, taking advantage of model structure. 
Moreover, we provide theoretical guarantees for free compression, by designing specific layer-wise compressors for the non-convex matrix smooth objectives. Our findings are supported with empirical evidence.

Published as a conference paper at ICLR 2024
DET-CGD: COMPRESSED GRADIENT DESCENT WITH MATRIX STEPSIZES FOR NON-CONVEX OPTIMIZATION
Hanmin Li Avetik Karagulyan Peter Richtárik
King Abdullah University of Science and Technology (hanmin, 1,, avetik. karagulyan, peter. reteraiichtarik .edaust.edu.se
ABSTRACT
This paper introduces new method for minimizing matrix -orri-h non-convex ob- jectives through the use of novel Compressed Gradient Descent (CGD) algorithms enhanced with a matrix-valued stepsize. The proposed algorithms are theoretically analyzed first in the single-node and subsequently in the distributed settings. Our theoretical results reveal that the matrix stepsize in CGD can capture the objec- tive's structure and lead to faster convergence compared to scalar stepsize. As a byproduct of our general results, we emphasize the importance of selecting the compression mechanism and the matrix stepsize in layer-wise manner, taking advantage of model structure. Moreover, we provide theoretical guarantees for free compression, by designing specific layer-wise compressors for the non-convex matrix smooth objectives. Our findings are supported with empirical evidence.
INTRODUCTION
The minimization of smooth and non-convex functions is fundamental problem in various domains of applied mathematics. Most machine learning algorithms rely on solving optimization problems for training and inference, often with structural constraints non-convex objectives accurately capture the learning and prediction problems in high-dimensional or non-linear spaces. However, non-convex problems are typically NP-hard to solve, leading the popular approach of relaxing them convex problems and using traditional methods. Direct approaches to non-convex optimization have shown success but their convergence and properties are not well understood, making them challenging for large scale optimization. While its convex alternative has been extensively studied and is generally an easier problem, the non-convex setting is of greater practical interest often being the computational bottleneck in many applications.
In this paper, we consider the general minimization problem:
min f(x) .E
where / Rd - a differentiable function. order for this problem to have finite solution we will assume throughout the paper that f is bounded from below.
Assumption 1. There exists fint e R such that f(x) 2 finl for all x Rdd
The stochastic gradient descent (SGD) algorithm (Moulines & Bach, 2011; Bubeck et al., 2015; Gower et al., 2019) is one of the most common algorithms to solve this problem. In its most general form, it can be written as
k+] b 7g(a*);
where g(x*) is a stochastic estimator of (x(**) and 7 is a positive scalar stepsize. particular case of interest is the compressed gradient descent (CGD) algorithm (Khirirat et al., 2018), where the estimator g is taken as compressed alternative of the initial gradient:
g(x²) C(V
and the compressor chosen to be a "sparser" estimator that aims to reduce the communication overhead in distributed federated settings. This is crucial, highlighted in the seminal paper by

---

Published as a conference paper at ICLR 2024
Konečný et al. (2016), which showed that the bottleneck of distributed optimization algorithms is the communication complexity. In order to deal with the limited resources of current devices, there various compression objectives that practical to achieve. These include also compressing the model broadcasted from server to clients for local training, and reducing the computational burden of local training. These objectives mostly complementary, but compressing gradients has the potential for the greatest practical impact due to slower upload speeds of client connections and the benefits of averaging Kairouz al. (2021). In this paper we will focus on this latter problem.
An important subclass of compressors are the sketches Sketches are linear operators defined on Rd i... C(y) Sy for every y E R., where S is a random matrix. A standard example of such a compressor is the Rand-k compressor, which randomly chooses & entries of its argument and scales them with scalar multiplier to make the estimator unbiased. Instead of communicating all coordinates of the gradient, one communicates only a subset of size k. thus reducing the number of communicated bits by factor of d/ k. Formally, Rand-k is defined as follows: S = k Σ}=1 Ci e where G3y is the 1z-th standard basis vector in Rd. We refer the reader to (Safaryan et al., 2022) for an overview on compressions.
Besides the assumption that function f is bounded from below, we also assume that it is L matrix smooth, as are trying to take advantage of the entire information contained in the smoothness matrix L and the stepsize matrix D.
Assumption (Matrix smoothness). There exists E 84 such that
((x) S f(v) (VS(v), v) 2 (L(x - y), - -y)
holds for all x, y E Rdd
The assumption of matrix smoothness, which is a generalization of scalar smoothness, has been shown to be more powerful tool for improving supervised model training. In Safaryan et al. (2021), the authors proposed using smoothness matrices and suggested a novel communication sparsification strategy to reduce communication complexity in distributed optimization for convex objectives. The technique was adapted to three distributed optimization algorithms the convex setting, resulting in significant communication complexity savings and consistently outperforming the baselines. The results of this study demonstrate the efficacy of the matrix smoothness assumption in improving distributed optimization algorithms.
The case of dhick-d smoothness matrices is particularly relevant in various applications, such neural networks (NN). In this setting, each block corresponds characterize the smoothness with respect to nodes in the i-th layer by a corresponding matrix L,- Unlike in the scalar setting, we favor the similarity of certain entries of the argument over the others. This is because the information carried by the layers becomes more complex, while the nodes in the same layers are similar. This phenomenon has been observed visually in various studies, such as those by Yosinski et al. (2015) and Zintgraf et al. (2017).
layer of the network, and
We study two matrix stepsized CGD-type algorithms and analyze their convergence properties for non-convex matrix smooth functions. As mentioned earlier, we put special emphasis on the block- diagonal case. We design our sketches and stepsizes in way that leverages this structure, and we show that in certain cases, we can achieve compression without losing in the overall communication complexity.
1.1 RELATED WORK
Many successful convex optimization techniques have been adapted for use in the non-convex setting. Here is a non-exhaustive list: adaptivity (Dvinskikh et al., 2019; Zhang et al., 2020), variance reduction (J Reddi et al., 2016; Li et al., 2021), and acceleration (Guminov et al., 2019). A paper of particular importance for work is that of Khaled & Richtárik (2020), which proposes unified scheme for analyzing stochastic gradient descent in the non-convex regime. A comprehensive overview of non-convex optimization can be found in (Jain et al., 2017; Danilova et al., 2022).
classical example of matrix stepsized method is Newton's 's method. This method has been popular in the optimization community for long time (Gragg & Tapia, 1974; Miel, 1980; Yamamoto, 1987).
2

---

Published as a conference paper at ICLR 2024
However, computing the stepsize as the inverse Hessian of the current iteration results in significant computational complexity. Instead, quasi-Newton methods use an easily computable estimator to replace the inverse of the Hessian (Broyden, 1965; Dennis & Moré, 1977; Al-Baali & Khalfan, 2007; Al-Baali et al., 2014). An example is the Newton-Star algorithm (Islamov et al., 2021), which we discuss in Section 2.
Gower & Richtárik (2015) analyzed sketched gradient descent by making the compressors unbiased with a sketch-and-project trick. They provided an analysis of the resulting algorithm for the linear feasibility problem. Later, Hanzely et al. (2018) proposed variance-reduced version of this method. Sketches are also of independent interest. In particular, Song et al. (2023) described a way of designing the distribution of sketch matrices, while Lee et al. (2019); Qin et al. (2023) used sketches in solving empirical risk minimization problems.
Leveraging the layer-wise structure of neural networks has been widely studied for optimizing the training loss funetion. For example, (Zheng al., 2019) propose SGD with different scalar stepsizes for each layer, (Yu et al., 2017; Ginsburg et al., 2019) propose layer-wise normalization for Stochastic Normalized Gradient Descent, and (Dutta et al., 2020; Wang et al., 2022) propose layer-wise compression in the distributed setting.
DCGD, proposed by Khirirat al. (2018), has since been improved in various ways, such as in (Horvath et al., 2019; Li et al., 2020). There is also a large body of literature other federated learning algorithms with unbiased compressors (Alistarh et al., 2017; Mishchenko et al., 2019; Gorbunov al., 2021; Mishchenko et al., 2022; Maranjyan et al., 2022; Horváth et al., 2023).
1.2 CONTRIBUTIONS
Our paper contributes the following ways:
We propose two novel matrix stepsize sketch CGD algorithms Section 2, which, to the best of our knowledge, are the first attempts to analyze fixed matrix stepsize for non- convex optimization. We present a unified theorem in Section that guarantees stationarity for minimizing matrix-smooth non-convex functions. The results show that taking algorithms improve on their scalar alternatives. The complexities are summarized in Table for some particular cases.
We design our algorithms' sketches and stepsize to take advantage of the layer-wise structure of neural networks, assuming that the smoothness matrix is block-diagonal. In Section 4, we prove that our algorithms achieve better convergence than classical methods.
Assuming the that the server-to-client communication is less expensive Konečný et al. (2016); Kairouz et al. (2021), we propose distributed versions of our algorithmss in Section following the standard FL scheme. and prove weighted stationarity guarantees. Our theorem recovers the result for DCGD in the scalar case and improves general.
We validate our theoretical results with experiments. The plots and framework are provided in the Appendix.
1.3 PRELIMINARIES
The usual Euclidean norm on Rd is defined as ||. We use bold capital letters to denote matrices. By Ia we denote the d x d identity matrix, and by Oa denote the d d zero matrix. Let S (resp. $ be the set of d x d symmetric positive definite (resp. semi-definite) matrices. Given Q e sd and x E Rd, we write ||=||e == V(Qr, x)., where (--)) 1) is the standard Euclidean inner product on Rd. For matrix A E s4 we define by Amax (resp. Amin (A)) the largest (resp. smallest) eigenvalue of the matrix A. Let A, Rdd;d;; and d d1 + ... + dz. Then the matrix A = -Diag( A,...., As) is defined as a block diagonal d x matrix where the i-th block is equal to A,. We will use ding( (A) dRdxd denote the diagonal of any matrix A E Raxd Given function f : Rd + IR, its gradient and its Hessian at point r E IRd are respectively denoted as ff(x) and f2)(). A random vector x E ddd is an e-stationary point if E [[](())]]] < E?, where the expectation is over the randomness of the algorithm.
3

---

Published as a conference paper at ICLR 2024
2
THE ALGORITHMS
Below we define our two main algorithms:
k+1 I - f(*").
(det-CGDI)
and
x k+1 = x² - DV f(²".
(det-CGD2)
Here, D E $4 the fixed stepsize matrix. The sequences of random matrices S and T satisfy the following assumption.
Assumption 3. We will assume that the random sketches that appear in our algorithms are i.id. unbiased, symmetric and positive semi-definite for each algorithm. That is
St. I S S S and T iid T E
S = =E - La for every KEN,
where S and T are probability distributions over Sd
A simple instance of det- det-CGDI and det-CGD2 is the vanilla GD. Indeed, if S = T = La and D Ld, then +++ . (x**). In general, one may view these algorithms Newton-type methods. In particular, our setting includes the Newton Star (NS) algorithm by Islamov et al. (2021):
k+1 = x - (v² (xx (x²*).
(NS)
The authors prove that the convex case it converges to the unique solution ginf locally quadratically, provided certain assumptions met. However, is a practical method it requires knowledge of the Hessian at the optimal point. This method, nevertheless, hints that constant matrix stepsize can yield fast convergence guarantees. Our results allow us choose the D depending on the smoothness matrix L. The latter can be seen as a uniform upper bound on the Hessian.
The difference between det-CGDI and det-CGD2 the update rule. In particular, the order of the sketch and the stepsize is interchanged. When the sketch S and the stepsize D are commutative w.r.t. matrix product, the algorithms become equivalent. general, simple calculation shows that if take
T DDS*
(5)
then det-CGD1 and det-CGD2 are the same. Defining Th according (5), recover the unbiased- ness condition:
T DE S D Ia.
(6)
However, in general DE S D is not necessarily symmetric, which contradicts to Assumption 3. Thus, det-CGD1 and CGD2 are not equivalent for our purposes.
MAIN RESULTS
Before state the main result, present stepsize condition for det-CGDI and det-CGD2, respectively:
E DDD*S D.
and
E DT* L D] D.
(8)
In the case of vanilla GD (7) and (8) become 7 < -- which is the standard condition for con- vergence. Below is the main convergence theorem for both algorithms in the single-node regime.
Theorem 1. Suppose that Assumptions 1-3 are satisfied. Then, for each k 2 0
K-1
2(f(x²) finf)
(9)
k=
one of the below conditions is true:
4

---

Published as a conference paper at ICLR 2024
The vectors æ² are the iterates of det-CGDI and D satisfies (7);
ii The vectors x are the iterates of det-CGD2 and D satisfies (8).
It is important to note that Theorem 1 yields the same convergence rate for any D s despite the fact that the matrix norms on the left-hand side cannot be compared for different weight matrices. To ensure comparability of the right-hand side of (9), it necessary normalize the weight matrix D that is used to measure the gradient norm. We propose using determinant normalization, which involves dividing both sides (9) by det( DD)1/d yielding the following:
2(f(2)) fiuf) det (D) (
(10)
K
This normalization is meaningful because adjusting the weight matrix to der allows its determi- nant to be 1, making the norm on the left-hand side comparable the standard Euclidean norm. is important note that the volume of the normalized ellipsoid {z Rd D/ec S 1] does not depend on the choice of D E $4 Therefore, the results of (9) are comparable across different D the sense that the right-hand side (9) measures volume the ellipsoid containing the gradient.
3.1 OPTIMAL MATRIX STEPSIZE
In this section, describe how choose the optimal stepsize that minimizes the iteration complexity. The problem is easier for det-CGD2. We notice that (8) can be explicitly solved. Specifically, is equivalent to
D 3 (E [T*
(11)
We want to emphasize that the RHS matrix is invertible despite the sketches not being so. Indeed. The map h: T TLT is convex on $4. Therefore, Jensen's 's inequality implies
T LT*
= L Oa-
This explicit condition on D can assist in determining the optimal stepsize. Since both D and (E TTk LT*))= are positive definite, then the right-hand side of (10) is minimized exactly when
D (E [T*
(12)
Note that the explicit solution of D needs to be calculated only once, at the beginning of the algorithm. It is then fixed for all iterations. The situation is different for det-CGD1. According to (10), the optimal D is defined as the solution of the following constrained optimization problem:
minimize subject to
log det D D-1) E [S DLDS* D
(13)
D
Proposition 1. The optimization problem (13) with respect to stepsize matrix D E S is convex optimization problem with a convex constraint.
The proof of this proposition can found in the Appendix. is based on the reformulation of the constraint its equivalent quadratic form incquality. Using the trace trick, prove that for every vector chosen in the quadratic form, it convex. Since the intersection of convex sets is convex, conclude the proof.
One could consider using the CVXPY (Diamond Boyd, 2016) package to solve (13), provided that it is first transformed into Disciplined Convex Programming (DCP) form (Grant et al., 2006). Nevertheless, (7) not recognized as DCP constraint the general case. To make CVXPY applicable, additional steps tailored to the problem hand must be taken.

---

Published as a conference paper at ICLR 2024
Table 1: Summary of communication complexities of det-CGD1 and det-CGD2 with different sketches and stepsize matrices. The D, here for det-CGDI is W; with the optimal scaling determined using Theorem 2, for det-CGD2 it is the optimal stepsize matrix defined in (12). The constant 2x) - //c² 22 is hidden, l is the number of layers, k; is the mini-batch size for the i-th layer if we use the rand-k sketch. The notation L,, is defined as d-k I-I diag( L.) d-I Li.
The
(st p.)
1.44 Ei b layer
1. del-CGDI
Tainti +)
det
d det(
2. del-OGiD1
(a- 1(2)))
d- det (diag(2)))/4
det (diag(L)) 1/4
3. det CGDI
(Ia 14,)
d- (Miiz (L)x) 1/4
Amxe(L)
del-CGDI
(mmd-L1, 71a,))
e- (TTi ot (max, ( ) y/u
(Zzz)
Mi oe Amax L diogle 222)))
1/a
dAmax ( dios (2 -)))
5. det-CGDD
I deale?
det de
[m oet (ataaeeea 1/d
de--CGDI
(m (/2
8.
Di deste 173)
a A1/2 (I. dess (L) (244)
[i== 1/a""
7. des-CGiD
(mnd-1, y ding dingg-((r..))) +(x.1)
8.
11 (15-1(173))
a- det (ding( 1)) 1/d
k. (11= (2) di dot ( ())) 1/4
8. del-CGDI
(nind-kerr ding (x.))
d det (ding( (ding(L))) 1/a a- da( d det(ding(D)))/ det(fr)
9. des-CGi02
(Ta )
a d-
rand-1, dlog )(1.)) d.
e- (Mi o4)) 1/2 detiding 1/
10. det-CGD2
de-CGGD2
(mnd--,, & k.,,
[1'= (th) t
(11'e) d,
del CGD2
(E-r1 -imm (2)) dot(E)
det(L) 1/8 d. Amoce (L)
13. GD
L1. Aaala (L))a)
MA
4 LEVERAGING THE LAYER -IIEE STRUCTURE
In this section we focus on the block- diagonal case of L for both det-CGD1 and det-CGD2. In particular, we propose hyper- parameerss of det-CGD1 designed specifically for training NNs. Let us assume that L = Diag( Li.... Lt), where L; E s This setting is generalization of the classical smoothness condition, as in the latter case L, = I.Ia, for all i = 1,...., Respectively, we choose both the sketches and the stepsize to be block diagonal: D S* St ..... ) where D,, S s
Dp) and
Let us notice that the left hand side of the inequality constraint in (13) has quadratic dependence on D, while the right hand side is linear. Thus, for every matrix W E S4 there exists y such that
>2mmax (TE
S 7mmin (W).
Therefore, for y W we deduce
E ( The following theorem is based on this simple fact applied the corresponding blocks of the matrices D, L. 5 for det-CGD1.
3 >> (E [S Ia 3 7mmin ( I W.
(14)
Theorem 2. Les f Rd + R satisfy Assumptions and 2, with L admitting the layer-separable struc- ture L Diag( Li...., . Le). where Lı...., Le E sd. Choose random matrices St...., St S to satisfy Assumption 3 for all [6, and let S Diag(S) SS....... St.). Furthermore, choose
matrices W,,... W. sd and scalars 71.... 7t O such that
7/ S 1-1
E W 1/2 W.W.W.W..W.. 121))
Vi [4]
(15)
Letling W = -Daa W
ve Ia) and D = rW, we gel We). r = Diag(> Ia,....,
K
2(f(2²) - finf) det (TW) 1/d K
K
E
||
BarEw)/4
rw
-
(16)

---

Published as a conference paper at ICLR 2024
In particular, if the scalars {7a} are chosen to be equal to their maximum allowed values from (15), then the convergence factor of (16) is equal to
E W; $ WW, S.W.L.WSSWWW #1]] det(W-1)a
det (TW) -
II X
d: max
Table I contains the (expected) communication complexities of det- det-CGD2 and GD for several choices of W, D and S Here are a few comments about the table. We deduce that taking a matrix stepsize without compression (row 1) we improve GD (row 13). A careful analysis reveals that the result row always worse than row complexity. However, the results in 6 and row 7 are not comparable in general, meaning that neither them is universally better. More discussion on this table can be found in the Appendix.
terms both communication and iteration
Compression for free. Now, let us focus on row 12. which corresponds to a sampling scheme where the i-th layer is independently selected with probability qi. Mathematically, it goes as follows:
T
Th Id., 9
where
7 ~ Bernoull(qq)).
(17)
Jensen's inequality implies that
Σ
q:d;
2 d.
(18)
9:
i=1
The equality is attained when 9i = q for all E [4]. The expected bits transferred per iteration of this algorithm is then equal to kexp = qd and the communication complexity equals d (L)) 1/4 Comparing with the results for det-CGD2 with rand-hixxp on row 11 and using the fact that det L) < det (diag [)). we deduce that the Bernoulli scheme better than the uniform sampling scheme. Notice also, the communication complexity matches the one for the uncompressed det-CGD2 displayed on row 9. This, in particular means that using the Bern-g sketches we can compress the gradients for free. The latter means that reduce the number of bits broadcasted at each iteration without losing in the total communication complexity. In particular, when all the layers have the same width d, the number of broadcasted bits for each iteration is reduced by factor of q.
DISTRIBUTED SETTING
In this section we describe the distributed versions of our algorithms and present convergence guarantees for them. Let us consider an objective function that is sum decomposable:
f(x)
T Σ f((x),
where each f: Rd + IR is differentiable function. We assume that f satisfies Assumption I and the component functions satisfy the below condition. Assumption Each component function fi is Li-smooth and is bounded from below: f((x) 2 fiul for all x E Rdd.
This assumption also implies that f is of matrix smoothness with L E S4+ where L = - L,- Following the standard FI. framework (Konečný et al., 2016; McMahan et al., 2017: Khirirat et al., 2018), assume that the i-th component function f4 is stored the i-th client. At each iteration, the clients in parallel compute and compress the local gradient V fi and communicate it to the central server. The server, then aggregates the compressed gradients, computes the next iterate, and in parallel broadcasts it to the clients. See the below pseudo-codes for the details.
Theorem 3. Let fi Rdd + R satisfy Assumption 4 and let f satisfy Assumption I and Assumption with smoothness matrix L. If the stepsize satisfies
DLD D,
(19)
7

---

Published as a conference paper at ICLR 2024
then the following convergence bound is true for the iterates of Algorithm 1:
2(1 + AD ) (f(x9) - -fint)
2 Aint inf det D)i/dn
[|
min OSkER-1
+
(20)
det( D) / K
where A inf fint 1 -x=1 fimt and
AD max max Xmax (L
Ia) DLD (S) Ia) L }
Algorithm 1 Distributed det-CGDI
Algorithm Distributed det-CGD2
1: Input: Starting point x!,, stepsize matrix D, number of iterations K"
Input: Starting point .²", stepsize matrix D,
number of iterations K
2: for ==0 0, 2....
do
for k 0, 2. 2..... K do
3: The devices in parallel:
3: The devices in parallel:
4: sample S S:
sample T T:
5: compute S. Vc(x"))
compute T DV f((x:";;
6: broadcast V (xx
6: broadcast T D f((x))
7: The server:
The server:
8: combines g D Σ S V(((()
combines g Σ. DVF
9: computes k+1 x² g":
computes x++1 x² g":
10: broadcasts x k+
10: broadcasts I k+1
end for Return: x
11: end for
12:
12: Return: x
The same result is true for Algorithm with different constant Ap. The proof of Theorem 3 and its analogue for Algorithm 2 are presented in the Appendix. The analysis is largely inspired by (Khaled & Richtárik, 2020, Theorem 1). Now, let us examine the right-hand side of (20). We start by observing that the first term has exponential dependence in K. However, the term inside the brackets, + AD/ n, depends on the stepsize D. Furthermore, has a second-order dependence on D, implying that \nD = a² AAD. as opposed to de which is linear a. Therefore, we can choose a small enough coefficient to ensure that Åp is of order n/K. K. This means that for fixed number of iterations K, we choose the matrix stepsize to be "small enough" to guarantee that the numerator of the first term is bounded. The following corollary summarizes these arguments, and its proof can be found in the Appendix.
Corollary 1. We reach an e-stationarity, that is the right-hand side of (20) is upper bounded by e?, the following conditions are satisfied:
nE? K inine det (D)
12(f(z9) finf)
DLD = D, AD S min
K
(21)
Proposition 3 in the Appendix proves that these conditions with respect to D are convex. In order to minimize the iteration complexity for getting E² error, one needs to solve the following optimization problem
minimize
log det (D-1)
subject to Choosing the optimal stepsize for Algorithm is analogous to solving (13). One can formulate the distributed counterpart of Theorem 2 and attempt to solve it for different sketches. Furthermore, this leads convex matrix minimization problem involving D. provide formal proof of this property in the Appendix. Similar to the single-node case, computational methods can be employed using the CVXPY package. However, some additional effort is required to transform (21) into the disciplined convex programming (DCP) format.
satisfies (21)
The second term in (20) corresponds to the convergence neighborhood of the algorithm. does not depend on the number of iteration, thus it remains unchanged, after choose the stepsize. Nevertheless, depends on the number of clients n. In general, the term A inf /nf/n can be unbounded, require An be upper-hounded by n/ K. Thus,
when +00. However, per Corollary
8

---

Published as a conference paper at ICLR 2024
elo cant-1 sittch A C. n 100
patrp mid aead - p
28c cant-1 deidi A G.1. i 500
DO00 end
Cascs02cagee
de CGD2 doyoral
2
Figure 1: Comparison of standard DCGD, DCGD with matrix smoothness, D-det-CGDI and D- det-C's CGD2 with optimal diagonal stepsizes under rand-1 sketch. The stepsize for standard DCGD is determined using (Khaled & Richtárik, 2020, Proposition 4), the stepsize for DCGD with matrix smoothness along with D1, D2 determined using Corollary 1, the error level set be 8² 0.0001. Here GK.D:- = 1 K-1
K E [[V]((>)]] (()aat()))))))))))
the neighborhood term will indeed converge zero when K +00, if we choose the stepsize accordingly.
We compare our results with the existing results for DCGD. In particular we use the technique from Khaled & Richtárik (2020) for the scalar smooth DCGD with scalar stepsizes with the results from (Khaled & Richtárik, 2020, Corollary 1). See the Appendix for the details on the analysis of Khaled & Richtárik (2020). Finally, we back up our theoretical findings with experiments. See Figure 1 for a simple experiment confirming that Algorithms and have better iteration and communication complexity compared to scalar stepsized DCGD. The graphs of the two proposed algorithms coincide, as the diagonal stepsize and the diagonal sketch commute, resulting in the same method. For more details the experiments we refer the reader to the corresponding section in the Appendix.
CONCLUSION
In this paper, enhance compressed gradient descent method with matrix-valued stepsize for general non-convex objectives. Convergence guarantees are provided for the algorithms both in the single node case and the distributed setting. By considering the layer-wise structure of models such as neural networks, we are able to design compression mechanisms that achieve compression for free. This is the first time matrix stepsize used and analyzed together with compression in the non-convex case. Our theoretical findings are supported with abundant numerical experiments.
6.1 LIMITATIONS
is worth noting that every point in Rd can be enclosed within some volume I ellipsoid. Therefore, having the average D-norm of the gradient bounded by small number does not guarantee that the average Euclidean norm is small. However, for a fixed D, the standard Euclidean norm equivalent the weighted D-norm. This due to
Amin (D)
Amax D
|V < [Vf(()) D/ ((
det 1) [Vf(2)]
(22)
det 1)
This relation is further validated by our experiments described in the Appendix.

---

Published as a conference paper at ICLR 2024
REFERENCES
Mchiddin Al-Baali and H Khalfan. An overview of some practical quasi-newton methods for unconstrained optimization. Sultan Qaboos University Journal for Science [SQUJS], 12(2): 199-209, 2007.
Mehiddin Al-Baali, Emilio Spedicato, and Francesca Maggioni. Broyden's quasi-Newton methods for a nonlinear system of equations and unconstrained optimization: a review and open problems. Optimization Methods and Software, 29(5):337-954 2014.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
Charles G Broyden. A class of methods for solving nonlinear simultaneous equations. Mathematies of computation, 19(92):577-593, 1965.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM
transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent theoretical advances in non-convex optimiza- tion. In High- Biigh-Dimensioal Optimization and Probability: With a View Towards Data Science, pp. 79-163. Springer, 2022.
John E Dennis, Jr and Jorge J Moré. Quasi-Newton methods, motivation and theory. SIAM review, 19(1):46-8) 1977.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2009-9113, 2016.
Aritra Dutta, El Houcine Bergou, Ahmed M Abdelmoniem, Chen- Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3817-3824, 2020.
Darina Dvinskikh, Aleksandr Ogaltsov, Alexander Gasnikov, Pavel Dvurechensky, Alexander Tyurin, and Vladimir Spokoiny. Adaptive gradient descent for convex and non-convex stochastic optimiza- tion. arXiv preprint arXiv: 1et:::9111.0000 1.08380, 2019.
Boris Ginsburg, Patrice Castonguay, Oleksii Hrinchuk, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, Huyen Nguyen, Yang Zhang, and Jonathan M Cohen. Stochastic gradient methods with layer-wise adaptive moments for training of deep networks. arXiv preprint arXiv:190..11266 2019.
Eduard Gorbunov, Konstantin P Burlachenko, Zhize Li, and Peter Richtárik. Marina: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pp. 7788-3799... PMLR, 2021.
Robert M Gower and Peter Richtárik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36(4): (6644):6660-1) 1660-1690, 2015.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik, Sgd: General analysis and improved rates. International Conference on Machine Learning, pp. $209-5209. PMLR, 2019.
William B Gragg and Richard A Tapia. Optimal error bounds for the Kentton-Kantrrovch theorem. SIAM Journal on Numerical Analysis, 11(1):10-13, 1974.
Michael Grant, Stephen Boyd, and Yinyu Ye. Disciplined convex programming. Global optimization: From theory implementation, pp. 155-210, 2006.
10

---

Published as a conference paper at ICLR 2024
SV Guminov, Yu E Nesterov, PE Dvurechensky, and AV Gasnikov. Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems. Doklady Mathematics, volume 99, pp. 125-128. Springer, 2019.
Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. SEGA: Variance reduction via gradient sketching. Advances in Neural Information Processing Systems, 31, 2018.
Samuel Horvath, Chen- Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtarik. Natural compression for distributed deep learning. arXiv preprini arXiv: 1905. 10988, 2019.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik, and Sebastian Stich. Stochastic distributed learning with gradient quantization and double-variance reduction. Opti- mization Methods and Software, 38(1):91-106 2023.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. In International conference on machine learning, pp. 4617-4628. PMLR, 2021.
Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016.
Prateek Jain, Purushottam Kar, et al. Non-convex optimization for machine learning, Foundations and Trends in Machine Learning. 1063-4)112-333,, 2017.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-21 220,, 2021.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint WwXiv:2002.03322, 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint 1806.08006.663 2018
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization the current matrix multiplication time. In Conference on Learning Theory, pp. 2140-2157. PMLR, 2019.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002. 1364, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal
probabilistic gradient estimator for nonconvex optimization. In International conference machine learning, pp. 6286-6295. PMLR, 2021.
Artavazd Maranjyan, Mher Safaryan, and Peter Richtárik. GradSkip: Communicaionn-Aceeeraate Local Gradient Methods with Better Computational Complexity. arXiv preprint arXiv:2210. 2022.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. communication-cffficee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017. URL http:/ /ttp///axxiii wrwg
wttpi/////...... 05629.
George Miel. Majorizing sequences and error bounds for iterative methods, Mathematics of 10mpptation,344144)118,, 34(149):185-002, 1980.
11

---

Published as a conference paper at ICLR 2024
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.092000 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 15750-15769. PMLR, 17-23 Jul 2022.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 101-156. PMLR, 2023.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances Neural Information Processing Systems, 34: 4384 4396, 2021.
Mher Safaryan, Filip Hanzely, and Peter Richtárik. Smoothness matrices beat smoothness constants: Better communication compression techniques for distributed optimization. Advances in Neural Information Processing Systems, 34:25688 25702, 2021.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compres- sion in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 11(2):557-580, 2022.
Zhao Song, Yitan Wang, Zheng Yu, and I Lichen Zhang. Sketching for first order method: Efficient algorithm for low-handwidth channel and vulnerability. In International Conference on Machine Learning, pp. 32365-32417. PMLR, 2023.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 107.v:1907.04232. 2019.
Bokun Wang, Mher Safaryan, and Peter Richtárik. Theoretically better and numerically faster distributed optimization with smoothness-awwer aware quantization techniques. Advances in Neural Information Processing Systems, 35:9841-9852 2022.
Tetsuro Yamamoto. A convergence theorem for Newton-like methods in Banach spaces. Numerische Mathematik, 51:545-557, 1987.
Jason Yosinski, Jeff Clune, Anh Nguyen, Thomas Fuchs, and Hod Lipson. Understanding neural networks through deep visualization. arXiv preprint arXiv: 150.006906606779, 2015.
Adams Wei Yu, Lei Huang, Qihang Lin, Ruslan Salakhutdinov, and Jaime Carbonell. Block- normalized gradient method: An empirical study for training deep neural network. arXiv preprint arXiv: 2017.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 153883153333,, 2020.
Qinghe Zheng, Xinyu Tian, Nan Jiang, and Mingqiang Yang. Layer-wise learning based stochastic gradient descent method for the optimization of deep convolutional neural network. Journal of Intelligent & Fuzzy Systems, 37(4):5641-5644 2019.
Luisa M Zintgraf, Taco S Cohen, Tameem Adel, and Max Welling. Visualizing deep neural network decisions: Prediction difference analysis. arXiv preprint arXiv: 0402.04595, 2017.
12


Reviews:
[{"review_id": "zi5U6axeSD", "reviewer": "Reviewer_TXUi", "summary": "In this paper, the authors present two novel matrix stepsize sketch type compression GD algorithms which are optimization algorithms based on sketch based compression gradient calculation. The authors utilize the layered structure of the sketches while designing the sketches.", "questions": "- Why did the authors first present the stochastic gradient and presented the compressed gradient as a  replacement for the stochastic gradient? Is it stochastic?\n- Did the authors try some further algebraic tricks on equation 15? What is the complexity of those operations?\n- What is the take home message in Figure 1, for comparison of CGD 1 and CGD2. Did the authors experiment a scenario where these two methods are performing different?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Matrix smoothness is leveraged to reduce distribution communication complexity. \n\n- layer layer-wise structure of the neural nets is utilized while designing the sketches and block diagonal smoothness is used.\n\n-The number of bits broadcasted at each iteration are reduced without losing in the total communication complexity. (free compression)", "weaknesses": "- Determinant normalization is not too common approach. Hence, I would appreciate some further reference, and supporting statement into why to use the normalized determinant.", "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": "xqX20MP1iL", "reviewer": "Reviewer_y6k9", "summary": "This paper introduces two new matrix stepsize sketch Compressed Gradient Descent (CGD) algorithms for minimizing matrix-smooth non-convex functions. The theoretical analysis of these algorithms extends to both single-node and distributed settings.The newly introduced matrix stepsize strategy captures the underlying structure of the objective function, and lead to faster convergence. Leveraging the block-diagonal structure within neural networks, the proposed Det-CGD algorithm outperforms classical methods.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The authors introduce two novel matrix stepsize sketch CGD algorithms, and offer convergence guarantees for these algorithms in both single-node and distributed scenarios.\n\nS2. Taking into account the layer-wise structure of neural networks, the authors devise efficient compression mechanisms.\n\nS3. The author derives the expression for the optimal step size for the CGD algorithms, offering an important guideline for achieving rapid convergence.", "weaknesses": "W1. Assumption 2 is stringent and may not align well with the characteristics of neural network problems. Note that Inequality (4) in Assumption 2 is assumed to apply to the entire dataset rather than just a mini-batch.\n\n-- Neural network problems can be viewed as high-order polynomial fitting problems that are inherently nonconvex. Inequality (4) should include not only second-order terms but also third-order and higher-order terms. Utilizing a varying matrix D^t is more effective than using a constant stepsize D to capture the curvature information of the nonconvex objective function.\n\n-- Even though Assumption 2 holds, the authors employ a global convex majorization function in Inequality (4), which may lead to slow convergence due to its potential looseness.\n\nW2. The authors claim that their proposed methods take advantage of the layer-wise structure of neural networks, but in the experiments, they only focus on the logistic regression problem with a non-convex regularizer. Additionally, the neural network architecture is not defined.\n\nW3. This stepsize is the minimizer of the right-hand side of the normalization upper bound in (10) under certain conditions. It is not clear why this results in the \"optimal stepsize\".\n\nW4. Solving the log-det minimization problem under the constraints specified in (21) can be challenging and impractical, particularly when the dimension $d$ is large.", "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": "TUCOyFQxXQ", "reviewer": "Reviewer_cDU5", "summary": "The paper investigates matrix step sizes of the compressed gradient descent method and provides convergence analysis.", "questions": "1) The paper claims that the matrix step size improves performance but introduces problems. The presence of the neighboring term in Theorem 3 creates a significant neighborhood when $\\Delta^{inf}$ is large.\n2) This paper uses the compressed gradient as shown in (3), which is a direct compression on the full gradient. Given the prevalence of error feedback techniques in handling compression errors, it is pertinent to consider whether the proposed matrix step size can be extended to incorporate error feedback methods. \n3) The paper does not consider the use of SGD, local update, and partial participation techniques in distributed settings. \n4) The paper introduces det-CGD1, but it is unclear why this algorithm, specifically in a distributed setting, can obtain Algorithm 1.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper investigates matrix step sizes of compressed gradient descent and provides convergence analysis.", "weaknesses": "see questions.", "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 (poster)