Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Authors: Donghwa Kim
Jaewook Lee
Chulhee Yun
Venue: ICML 2025 poster (2025)
Keywords: Optimization
Stochastic Optimization
Coordinate Descent
Random Permutations
Primary area: optimization->stochastic
TL;DR: We prove that using indices from random permutations for coordinate descent (RPCD) is provably faster than using uniformly sampled indices (RCD) for a subclass of positive definite quadratic functions.

Abstract: We analyze the convergence rates of two popular variants of coordinate descent (CD): random CD (RCD), in which the coordinates are sampled uniformly at random, and random-permutation CD (RPCD), in which random permutations are used to select the update indices. Despite abundant empirical evidence that RPCD outperforms RCD in various tasks, the theoretical gap between the two algorithms’ performance has remained elusive. Even for the benign case of positive-definite quadratic functions with permutation-invariant Hessians, previous efforts have failed to demonstrate a provable performance gap between RCD and RPCD. To this end, we present novel results showing that, for a class of quadratics with permutation-invariant structures, the contraction rate upper bound for RPCD is always strictly smaller than the contraction rate lower bound for RCD for every individual problem instance. Furthermore, we conjecture that this function class contains the worst-case examples of RPCD among all positive-definite quadratics. Combined with our RCD lower bound, this conjecture extends our results to the general class of positive-definite quadratic functions.

structures, the con- Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Donghwa Kim
Jaewook Lee!
Chulhee Yum
Abstract
significantly reduce the computational overhead of high- dimensional large-scale problems by updating only single coordinate (or sometimes a small subset, referred to as blocks) instead of the whole set of parameters. Stemming from extensive studies on different types of CD algorithms (Beck & Tetruashvili, 2013; Lee & Sidford, 2013; Wright, 2015; Nesterov & Stich, 2017), randomized versions of CD have been especially popularized since Nesterov (2012); Richtárik & Takác (2011). Usually referred to as random coordinate descent (RCD), these types of algorithms choose the coordinates to update i.i.d. randomly from certain distribution, typically uniform and sometimes specifically chosen according to the problem geometry. The introduction of randomness has been demonstrated in Sun & Ye (2016) to outperform deterministic algorithms like cyclic coordinate descent (CCD) in terms of worst-case performance.
We analyze the convergence rates of two popu- lar variants of coordinate descent (CD): random CD (RCD), which the coordinates are sampled uniformly random, and pundotn-permutation CD (RPCD), in which random permutations are used to select the update indices. Despite abun- dant empirical evidence that RPCD outperforms RCD in various tasks, the theoretical gap between the two algorithms' performance has remained elusive. Even for the benign case of positive- definite quadratic functions with permutation- invariant Hessians, previous efforts have failed to demonstrate provable performance gap be- tween RCD and RPCD. To this end, we present novel results showing that, for a class of quadrat- ies with permutation-invatte traction rate upper bound for RPCD is always strictly smaller than the contraction rate lower bound for RCD for every individual problem instance. Furthermore, we conjecture that this function class contains the worst-case examples of RPCD among all positive-definite quadratics. Combined with our RCD lower bound, this con- jecture extends our results to the general class of positive-definite quadratic functions.
Meanwhile, for stochastic algorithms under finite-sum mini- mization settings, utilizing random permutations has been common for a long time, based on observations that tak- ing full pass among the component gradient updates in a randomly permuted order (commonly referred to SGD with Random Reshuffling) shows faster convergence speed than its ordinary, i.i.d. part. After empirical observations and some conjectures (Bottou, 2009; Recht & Re, 2012), a recent line of work has theoretically analyzed the exact convergence rates of SGD- RR and demonstrated the benefits over ordinary SGD (Ahn et al., 2020; Mishchenko et al., 2020; Cha et al., 2023; Liu Zhou, 2024). Many other stochastic algorithms also incorpo- rate random reshuffling for acceleration, including federated learning (Mishchenko et al., 2022; Yun et al., 2022) and minimax optimization (Das et al., 2022; Cho & Yun, 2023).
sereplacement-sampliinnn counter-
1. Introduction
We consider the minimization problem:
min f(x),
(L)
#ER
A similar variant also exists for CD, often referred to as cendom-permutation coordinate descent (RPCD) (Sun et al., 2020). While RPCD is based on similar idea that using permutations can accelerate, theoretical analysis of RPCD even harder because must focus the preconditioning- like effects of using permutations, which is very different from the case of SGD-RR (where random permutations induce variance reduction) and is notoriously difficult to in- spect theoretically. However, for strongly convex quadratic Hessians, is possi-
where : R is a smooth and convex function.
The coordinate descent (CD) algorithm has been proposed and widely used for solving problem (1) arising in mod- optimization and machine-learning problems it can
KAISS AI, Scoul, South Korea. Correspondence to: Chulhee Yun <chulhee, yun kr>>
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
functions with permutation-invant ble to compute the expectation of such matrices over all

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
permutations explicitly. Based on this approach, Lee & Wright (2019) (first appeared in 2016) derive convergence bounds for the expected finction value for quadratic func- tions with permutation invioonnii Hessians, and a follow-up work Wright & Lee (2017) further extends to Hessians with slight diagonal perturbations.
RCD vs RPCD, Pl, a= 0.7, n 25
10a
10-1
natural, important question arises on whether RPCD beats RCD, just as in the case of SGD with random permutations Bottou (2009). Many empirical studies have shown this to be true, as we demonstrate in Figure 1, but the theoretical as- pects of this phenomenon have been relatively less revealed in the literature. Gürbüzbalaban et al. (2018) demonstrate that it is possible to derive a stronger convergence upper matrices with
10-3
RCD
RPCD
Iterations
bound for RPCD for permutation-invee negative off-diagonal entries. However, they only compare between the upper bounds of RCD and RPCD, failing to demonstrate rigorous gap between the two algorithms. Also, even for this comparison, the paper does not provide a clear analysis (other than numerical experiments) on the assertion that the ratio contraction upper bounds for RCD to RPCD is larger than
Figure I. Performance comparison of RCD and RPCD. We use the objective function f(z) = = T Aæ with A aI + (1 (1-o)) o)11".
For this plot usc 0.7 and dimension 25.
Lipschitz constant. (The case a corresponds uni- form sampling). Richtárik & Takáe (201 1) further improve the constant factors of the convergence rate and extend to composite minimization problems. After Beck & Tetru- ashvili (2013) established global non-asymptotic conver- gence rates of block CCD with gradient-based updates, Sun & Ye (2016) show that RCD outperforms CCD for quadrat- ies f(x) = L Ar with permutation- innariinn Hessians of the form A al + (1-o)117 for some o E (0, 1]. hav- ing positive off-diagonals' They also show that this is the worst-case instance of CCD via a (up-to-constant) matching lower bound. Gürbüüzalaban et al. (2017) demonstrate a different case analysis on when CCD outperforms RCD, the Hessians which they refer to as 2-cyclic matrices.
Summary of Contributions. Our results contribute to overcoming these limitations by adequately comparing the lower bounds for RCD and the upper bounds for RPCD. We present the following results in the paper.
In Theorem 3.1, we show a novel convergence lower bound of RCD that holds for general quadratics with positive definite Hessians.
In Theorem 3.3, we show the convergence upper bound of RPCD for class of quadratic functions including permutation-invarian
Hessians. This upper bound co- incides with the RCD lower bound, concluding that RPCD outperforms RCD for any problem instance.
Random Permutations. One of the earliest works on RPCD by Sun et al. (2020) (first appeared in 2015) analyzes the convergence of RPPCD, While the results cover all positive definite quadratic functions and also the more general method of alternating direction method of multipli- ers (ADMM), expected iterate convergence is weaker guar- antee than the expected iterate norm or function value. An- other work by Lee & Wright (2019) (first appeared in public in 2016) derived convergence bounds for the expected func- tion value for quadratic functions with Hessians, and follow-up work Wright & Lee (2017) fur- ther extends Hessians with subtle diagonal perturbations, which turns out to be equivalent to A = oI + (1 o')u" where the entries of u are not too far from 1. Gürbüzbalaban et al. (2018) compares the contraction ratio upper bound for RCD and RPCD to demonstrate that RPCD has better convergence guarantees for permutation invariinn matrices with negative dff-oiagon entries. (We later provide more detailed, quantitative comparison in Table 2.)
In Theorem 3.4, we show a stronger convergence lower bound of RCD that holds for the same function class with the RPCD upper bounds. This demonstrates the existence of a wider gap between RCD and RPCD for all problem instances in this function class.
In Section 4, we conjecture that our RPCD upper bounds can be extended to the general class of positive definite quadratic functions. We also provide some experiments demonstrating the convergence of RPCD and RCD in practice.
-nvvaiiiannn
1.1. Related Work
Randomized CD. Nesterov (2012) presents global non- asymptotic convergence rates of RCD for (strongly) convex, smooth functions, where the probability of sampling each in- dex is proportional to the a-th power of the coordinate-wise
See Section 2 for definitions and notations.
2

---

We denote by & the k-dimensional identity matrix, 1; the k- dimensional ones vector, and diag (a1...... . a, the diagonal matrix with (i, i)-th entry 0g or the similarly constructed Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Reference
Algorithm
Function Class
Bounds
Theorem 3.1
RCD
All Quadratics
max
(1 ")) (1
2n
(L.B)
Theorem 3.3
RPCD
Hessian in .Ao
max
(1 - 1):
2n
(UB)
Theorem 3.4
RCD
Hessian in AA.
1 + (1-a)"
(LB)
Appendix D
RPCD
Hessian in AA
20
2g
+ 20 +0
(UB)
Table Summary of our results for subclass of) strongly convex, smooth quadratic functtins. The rightmost column indicates the
1/K
mx [x
upper/lower bounds (UB/LB) of the value limk-
where æx is the algorithm output after either K epochs of RPCD
nk iterations of RCD.
2. Preliminaries
if D = I, then we have o = Amin (A).
For positive integer N, write [N] == (1, N). We denote the dimension (number of coordinates) by n E N. We define S" ($7) as the collection of all symmetric (positive-definite) matrices of size n X n. We write || for the Euclidean ε2-norm for vectors and the spectral norm (i.e., operator norm) for matrices. We also use || llso for the Euclidean -nom in an analogous sense. The symbols @ and @ represent the matrix Kronecker product and the elementwise Hadamard product, respectively.
By definition, we must have E (0, 1]. Later in Assump- tion 2.2, we justify why we can set D = I without loss of generality. For such cases, a is equivalent to the strong convexity constant of the function f. and the convergence bounds we derive will depend on a.
Remark. Our analysis automatically includes the translated quadratics f(x)= = _ Ax + b æ + for any b E R" and c E R, as long as the Hessian A is positive definite. We can straightforwardly replace æ with æ æ-x" -rr for xx = A b, the minimizer of the translated problem Wright & Lee (2017).
The spectral radius (i.e., maximum absolute eigenvalue) of a matrix M is denoted by p(M), and the minimum (maximum) eigenvalue of matrices M (with real cigenval- ues) is denoted by (M) (Amax (M)). We denote by tril(M) the lower triangular part of M, including the diag- onals. We will usually denote the elements of matrices by lower-case letters with subscripts, as in A (aiz), and the elements of vectors via parentheses indicating the index, as xn))..
2.2. Algorithms
Algorithm shows a general framework for coordinate de- scent (CD) methods. We focus on two versions of CD that differ in how we choose the index is each iteration.
For random coordinate descent (RCD), choose
in æ =
i Unif([n])-
coordinate descent (RPCD), we use = n.K iterations (K the number of epochs). For each O..... K 1 we choose a permutation Pk: of [n] uniformly at random and choose
For
block diagonal matrix if the elements are matrices. (We may drop the k subscript in obvious cases, usually when k n.) Also, we denote by e, E R" the unit vector with the in the i-th coordinate and E, E Raxa by the unit matrix e,e,T
i, pp 1),
2.1. Problem Settings
where nk + with {0. (O..... . 1}.
Remark. For quadratic objectives f(x) J.2 Aæ. we can rewrite the arg min updates of Algorithm in explicit form:
Our goal is to minimize the following quadratic function:
1 min fxx = 2 Ax.
1c++1 = F.
Ei, Ax, = C. aigi
E. ff(x))
where the Hessian A ST is positive definite matrix. We write A = (at)) for the elements of A. The objective will be to find the minimizer xt = 0 of
which can also be viewed as a coordinate gradient descent method with step size Mi asts
Such gradient-based
For useful purposes, we define the following quantity. Definition 2.1. We define o = Amin (D-1A) where D diag (a11,-..; ann) the diagonal part of A. In particular,
methods are often used as proxy of CD when it hard compute the exact arg mins via line search. In the case of quadratics, the two are essentially equivalent.
3

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Algorithm 1 Coordinate Descent (CD)
more concisely:
Input: Number of iterations T Initialize:
2 = - 1-111- (A T)
R
= (I - r A)
for : = 0 to I" 1 do
Choose the index 4, E [n] to update
where r = tr). In the general case, can similarly observe that one epoch of RPCD with permutation pa: boils down to
Update 2++1 = (z) (I).....
Te [n)), where
r' arg min f (xt
...., (n))
end for Output: 2T E R
44th
Ek+1 A. &.
where define
RPCD
:= - - A. A.p
(5)
RCD. As shown in Equation (2), RCD randomly chooses a coordinate index per iteration to update.
Here, P PE {0, 1)mxn is the permutation matrix generated by the permutation p (i.e. Pe; = Cp(i) for all E [nl) and Pp = tri AP).
We can concisely write one iteration of RCD as follows:
1++1
R-D Ct
Unit-diagonal Assumption. Here we state and justify the following assumption on the Hessian A of
where we choose update index & i and we define
Assumption 2.2. We assume that the Hessian A has unit diagonals, equivalently, d11
Onn 1.
RCD A.
E.A.
(4)
This assumption might seem restrictive, but this is without loss of generality for any coordinate-descent type methods on quadratics. For any nonzero diagonal matrix F, every iterate of certain CD algorithm (RCD, RPCD, etc.) applicd on f(x) 1 x Ax for A F AF-1 proceeds as Th Fæg, where wy the trajectory of the same algorithm applied on f(x) with the same initialization and choices of i (see Appendix A of Wright & Lee (2017)). We may therefore assume that D = I by choosing F = D (Note that D is defined as the diagonal part of A.)
Remark. Nesterov (2012) also considers RCD with indices sampled from non-uniform distribution, primarily when the probabilities are proportional to the Lipschitz constants of each coordinate. However, in our work, we only focus on the uniformly sampled case as our purpose is to make a fair comparison with RPCD.
RPCD. shown in Equation (3), RPCD randomly chooses a permutation of indices and then takes coordinate updates in the order of the permutation we chose.
Sign-flip Invariance. Another particularly useful case of the diagonal transformation is when F diag(v) with v E {+1}". In this setting, we have = F A--AF-1 A Ooo which corresponds to flipping the signs of specific rows and columns of A.
This time, we focus on one epoch (containing iterates) of RPCD for quadratic objectives f(x) x Ax. Accord- ingly, here we denote by Øx++1 the iterate after applying one epoch (of n updates) to Øgg- For a better illustration, we follow Sun al. (2020) and consider the simple case when - and Po (123) is the identity permutation (which can also be viewed as epoch of cyclic coordinate descent). Observing that we update only the i-th coordinate at the i-th iteration (which won't It change for the rest of the epoch), we can write RPCD in terms of coordinates as follows:
2.3. Matrix Operators
Suppose that f(x) = f Ar and we have some iteration that proceeds according the following update:
I = TA
20 (1) = (1) 1 (a1100 (1) + (2) + 41 (3))
where the iteration matrix TA E Raxx is i.i.d. random and independent with the iterate æs. Let us define a linear matrix operator MA : R p - x as
z: (2) 22) ag2
(02121 (1) 022 (2) 023 (3))
x1 (3) = 23(33 (1 (1) + 0z221 (2) + (3))
MA = E
which can be rearranged and written in matrix form as:
Note that also write MA in matrix form by vector- izing the input and output matrices:
011
0
0
012
413
021
022
0
0 0
023
Fo.
031
433
033
0
0
(e)(Ma(X)) = E [T] T vec(X).

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
We denote the matrix operator for RCD and RPCD, gener- ated by the random matrix iterations TRCD and TRPCD by M and M respectively.
100
1.0
max maxplMa
Zaten
For the case of RCD, we can plug in TA.: = I - E,A (as in (4) with Ogi = 1) to explicitly compute
Thm 3.3 RHS
(Thm 3.4 RHS)"
0.6
( B, [I E,A)
X - E[A)
1 X
1
A (n diag (X) X
n12
0.0
To motivate the use of such matrix operators, suppose that we define the convergence measure as the quadratic form below, where θ E $ is a positive definite matrix that might depend on but not on Zg:
0.0
0.2
0.4
0.6
0.8
1.0
Figure 2. Plots of MMM) (s) (bluc), maxagk5. ( (MAt is (yellow), the RPCD upper bound in Theorem 3.3 (green), and the r-th power (for fair comparison) of the stronger RCD lower bound for A Ag in Theorem 3.4 (red).
RRCD
V
T T Or..
This (up to scaling) includes typical choices like the squared Euclidean norm ||> (using θ I) and the function value (xxx (using ② = A). Then we can observe that
3. RCD vs RPCD
In this section, compare the convergence rates of RCD and RPCD, under the problem setting defined in Section 2.
E v V
yo (0-1/2 1/2M) (0)0 1/2 yo
(7)
3.1. RCD Lower Bounds
where yo 1/22x0 xp and the expectation above is condi- tioned by Zu- Similarly, we omit the conditional notation part of the expectations if clear by context.
Theorem 3.1 provides the convergence lower bound of RCD for the expected iterate norm. Note that this convergence measure is equivalent to choosing O = in (6).
Diagonalizability. If a linear matrix operator MA is di- agonalizable, then we can view M ()) in (7) as power iteration. The limit as & + oo will be dominated by the eigenmatrix of MA with the largest absolute eigenvalue among nonzero components of the eigendecomposition of O Hence we can understand the spectral radius of the operator p(MA) as upper bound of the contraction for convergence measures.
Theorem 3.1. For an initial point Do E RR, let æT be the output of RCD after T iterates. Then, except a Lebesgue measure zero set of initial points,
E
||2 |2
(1- 1
lim T-+00
Z max
The green graph in Figure 2 coincides with the (n-th power of the) RCD lower bound. We can observe that the former term of the max dominates for large a and the latter for small σ, where the transition happens near o 2"
Lemma 2.3. The matrix operators RRCD and RPCD both diagonalizable.
are A
While we defer the proof of Lemma 2.3 to Appendix A.1, the main idea is to define similar operator:
We defer the proof of Theorem 3.1 Appendix B.I. Remark. For general convergence lower bounds for a certain function class, the existence of bad function and initial- ization usually suffices. Our results show an even stronger lower bound argument that holds for almost all initialization points and, altogether with Theorem 3.3, shows perfor- mance gap for every specific instance in the function class.
Ma(X) = A M. x A-
(8)
which can be shown to have symmetric matrix form
TIC X9 TI TA = A
for both MRCD and MRRCD, therefore is diagonalizable.
Furthermore, if we can show that MA is closed inside a subspace S which contains positive definite matrices, then choosing any E S. it suffices to show an upper bound of p(MAls), the spectral radius of MA restricted S.
3.2. RPCD Upper Bounds
In this section, we focus on the case when A is either commutationinvariaann or is closely related to such matrix.
5

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
In partieular, we focus on the following class of Hessians. Definition 3.2. We define the class of Hessians Ap Ar as
o. We then proceed to divide the range of into three regions: (0, 0.6], [0.6, 0.8), and [0.8, 1.0]. Perhaps interest- ingly, we can find (nearly) sign-alternating trend in the coefficients of both the polynomials from | ll and the upper bound. This allows us to use lower-order Taylor ap- proximations instead of the true lower and upper bounds and compare these to complete the proof for the cases (0, 0.6] and [0.6, 0.8). where the difference in which part of the max of the upper bound we use for comparison. For the remaining region [0.8, 1.0). we can show that [MMallss is a always too small compared to =
f + - 1 L--1) 22 k k) A = (diag( FIı A = {A- A vo A E A E (+1}"}
for given E (0,
Note that oI (1<t is a unil-diagonal, permutation- invariant matrix with a Amin of a, and that the sign-flip invariance of CD (see the end of Section 2.2) allows us to extend any type of convergence analysis from A to Ar.
We defer the full proof of Theorem 3.3 to Appendix B.2. Remark. In Figure 2, we can observe that for permutation- invariant instances A. with large enough n, small bump appears in the graph of P(M close to a = 1. This breaks monotonicity and makes theoretical analysis harder, motivating us to separately handle the cases of small and large a in Theorem 3.3 and the proof.
Theorem 3.3 provides the convergence upper bound of RPCD for the expected iterate norm.
Theorem 3.3. For an initial point Do E BR" lel a be the output of RPCD after K epochs. If A E Ar and no # O.
E ||| [| |
(1-
σ 2n
lim K K-+00
S max
n
n
3.3. Stronger RCD Lower Bound
Summarizing our results in Theorem 3.1 and Theorem 3.3, we can show that RPCD outperforms RCD for all instances of the form A d + (1 - o)1,1 1 In- The threshold between the two bounds is
If we solely focus on the class Ag, we can further show an RCD lower bound stronger than Theorem 3.1.
Theorem 3.4. Let E Ag. For an initial point Bg E R", let æT be the output of RCD after T iterates. Then, except for a Lebesgue measure zero set of initial points,
max (1-
R n
(1-))-11)))
(1-2))
2n :
(10)
+
EE
2
1
(1 (1-
where we recall that n iterations of RCD are equivalent to one epoch of RPCD for fair comparison.
lim T-
1
71
Proof Sketch. The proof starts from the observation that if A S = span (I, 11_,, considering Assumption 2.2:
Summarizing our results in Theorem 3.3 and Theorem 3.4, we can now show that there exists a clear gap between the convergence rates of RCD and RPCD for A AA.. The green line depicted in Figure 2 is equal to the RPCD upper bounds in Theorem 3.3, which is strictly smaller than the red RCD lower bound graph in Theorem 3.4 at a E (0, 1).
A = al + (1 =
(11)
then MRRCED is closed in S = span I, 11 This allows us to convert the restricted matrix operator
We defer the proof of Theorem 3.4 to Appendix B.3. Remark. While our results are written in terms of the ex- pected iterate norm E [[]=)]]]]] for any f(x) = 2 a Ax where A + 0 has unit diagonals and Amin (A) = a we have
MPCCD
Is
into a 2 x 2 matrix M
Therefore, if we choose any + E S with θ > to define the convergence measure (we choose θ = I for Theorem 3.3), the matrix (MARD (O) will stay in span (I, ] and it suffices to find an upper bound of p(MMRC (s) = ((M)) for this 2 x 2 matrix. We also show that the matrix
// || < f(x) < n2 (n 1)
|
2
and hence we can easily extend the same convergence anal- yses function values by scaling with a constant factor.
A = diag(aTe- (1 (1-0)la1k. In
Non-asymptotic results. The inequality between the RCD and RPCD bounds which we establish in the asymp- totic limit, in fact, already holds after a finite number of epochs. The required number of epochs depends on a, and the corresponding non-asymptotic result is given in Ap- pendix G.
for all 2 < k < n has the same value of P(MMRCDD with that of the k x k matrix A = aI, + (1 1
After this, we upper bound (. with A. low. which can be expressed as the maximum of two polynomials of
6

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
extend an upper bound for all positive definite quadratics.
Table A comparison of existing convergence upper bounds and our results for RPCD. Note that Wright & Lee (2017) consider a larger function class and Gürblizbalaban et al. (2018) consider different function. In the last row, we use R-T
Conjecture 4.1. For an initial point zo E R let æxK be the outpul of RPCD after K epochs. Ifa E (0, A E $ with Amin (A) = o, and to # O, then
Relerence
Convergence Rate
Lee & Wright (2019)
O (1 2n + 2x²
Ours (Theorem 3.3)
O max (1 - ;) 2)²m))
E 2 1121
*
S max { (1-=)
1 x
2n
Ours (Appendix D)
o (1 - 20 20 + 200")
lim K K000
Wright & Lee (2017)
KK (1 =
zt [1+a)2n-1 -1
Gürbüzzaalaba al. (2018)
((x=2)
Algorithmic Search. We use the following framework to search for the worst-case example among the larger space of all (unit-diagonal) quadratics.
Comparison with Previous Work. Lee & Wright (2019)
demonstrate that, n 2 10 and (0, 0.4], the epoch-wise contraction ratio of RPCD is of order
Start with a (randomly initialized) lower trian- gular matrix X E RR=x with nonzero diagonals.
Step 1.
20 + 20 +
1 1 1 2g
- + (0")
Construct unit-diagonal, positive semi- definite matrix by computing Y = X X and set unit diagonals by Z = Dy YDD where Dy is the diagonal part of Y.
Step 2.
for quadratic functions with permutation-invarre Hessians. While our result seems to be weaker in the sense that
2 2n = - 20 + 20² + O(02), (1-m)
σ
Step Construct a matrix A with o -min (A) by
A = 1 - 0 0
O-HI p
we can deduce from the details in our proof that in fact, a tighter exposition of our result can recover the rate of Lee & Wright (2019) (see Appendix D) while also providing stronger analysis by (i) finding the exact bounds with explicit coefficients (without asymptotic terms) and (ii) cov- ering the whole region of a E (0, 1] and smaller values of n using the (1 - 1 term and novel proof techniques.
Z
#
where = Amin ( ()). Note that A is also unit-diagonal and positive semi-definite.
Step 4. Construct an objective function that takes an input X to compute the value of p(MRPCD and run scipy optimizer to maximize the objective.
Wright & Lee (2017) consider an extension to Hessians of the form II + +11 o)uu" where the coordinates of ranges from val(a +c) for some small e. Their convergence rate upper bound shown in Table 2 is quanti- tatively weaker, but it is not directly comparable because it applies to a slightly larger function class. Gürbüzbalaban et al. (2018) consider a different function with Hessian of the form A= = (1 + at) I - al1T, where o = - (n - 1)a, an instance for which CCD also shown to outperform RCD (Gürbüzbalaban al., 2017).
We explore dimensions = 3, 4, 6 and a values ranging from 0.1 to 0.9 with increments of 0.1. Note that Algorith- mic Search finds the arg max of p(M which is an upper bound of the convergence rates. The results suggest that A E Ag are the worst cases concerning this upper bound, as all of our trials of Algorithmic Search converged to problem instance A Ar with various sign flips. We also observed that for any A E Ag, always have p(MRRCD) p(MRPCD|s) (where S span(1, 11 }), which we were able to show in Theorem 3.3 that is smaller than the same upper bound. These observations altogether motivated us to propose Conjecture 4.1 on the worst-case instance for general quadratic functions.
4. RPCD on General Quadratics
One limitation of our work is that the RPCD upper bounds in Theorem 3.3 only apply to problem instances in A E A.. Here we leave some noteworthy discussions considering ways to generalize to the entire class quadratic faanratiifuunctionn functions.
Remark. Sun & Ye (2016) show that A II +1-o))))111 is the worst-case example of cyclic coordinate descent (CCD), which partially aligns with the idea of our con- jecture that CD algorithms using one update per coordinate in each epoch (including both CCD and RPCD) are slow for similar types of matrices.
4.1. Conjecture on the RPCD Worst Case
Here we propose a conjecture that the RPCD upper bound we have shown for A E A in Theorem 3.3 could possibly
7

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
0.3,
0.7.
tive:
105
10-1
1
m
A log(L exp(- x)) 2
min
22
77
RCD
10-3
RCD
RPCD
RPCD
50
100
150
200
30
100 Rerationa
150
250
where a, ~ ~N In) and the labels are generated by sam- pling Ture (0, I,), setting b, sign(a, Fnue), and flipping each b, independently with probability 0.1. This setup follows Nutini et al. (2015).
Fsrations
Quad.
Quad. 0.7.0 n
10:1
10
10
Our theoretical contribution focuses on establishing the superiority of RPCD over RCD for the specific case of quadratic functions with permutation- inntuttationnnvariant Hessians (i). As demonstrated Figure 3, RPCD does not only show faster convergence than RCD for (i) in practice, but also in minimizing both (ii) and (fii). Results for (ii) particu- larly support immediate corollary of Conjecture 4.1; that RPCD is generally faster than RCD for any problem inslance in the broader class of quadratic functions. Readers may refer to Appendix for more details on the experiments.
1000
160
Herallors
Band
Quad. + LSE, aw 0.3, a 2.00, 25
Quad. LSE, em 0.7, a 2.0, n 25
10
16-1
10-1
10-1
150
200
1.00
250
Ridge Log. Req.A. 0.001
Ridge Log. Reg.. 0.1
10
4.3. Discussions
All previous results considering the convergence of expected iterate norm or function value² of RPCD (Lee & Wright, 2019; Wright & Lee, 2017) rely on the properties of permu- tation invariant matrices, for which ARPCD is closed in a certain low-dimensional matrix subspace S. In this section, first discuss special portion of cases when we might be able to use similar arguments, then proceed to discussions regarding arbitrary positive definite quadratics for which we cannot use such an approach.
Ex10
RCD
MCD RPCD
RPCD
200
400
600
200
400
620
Berat
Figure 3. Numerical experiments comparing RCD and RPCD. We plot the values and min-max range over multiple trials of RCD/RPCD. For (i)-, we use 25, a E (0.3, 0.7]. The experiments conducted (i) a quadratic function with A E As, (ii) a random quadratic with Amin (A) = a. (iii) random quadratic + (scaled and transformed) LSE function, and (iv) an fz-regularized sparse logistic regression objective with n = 100.
Partially Invariant Hessians. Suppose that we have a x 4 unit-diagonal matrix of the form:
4.2. Experiments
1
a
a
a
a
1
b
b
To compare the performance of RCD and RPCD, we con- ducted experiments on four types of convex and smooth functions: (i) quadratic functions with permutation-inye invariant Hessians, (ii) general quadratic functions with positive defi- nite Hessians, (iii) general quadratic functions with positive definite Hessians plus scaled log-sum-exp (LSE) term, and (iv) lg le-regularized logistic regression objective functions. Specifically, we use the following form for (i)-(iii)
a
b
1
b
a
b
b
1
For these types of matrices, there are only 4 possible cases of matrices P_ AP. Then we can define the bases using
the following (1 + (n 1)) x (1 + (n 1)) block matrices:
1 0
0
V
V/
0
0
1
1 Ax + LSE(Qx),
f(x)
2
V/3
0 0
V4
0
0
11
where A is either oI + (1 0) or randomly generated with unit diagonals and Amin (A) (following Steps 1-3 of Algorithmic Search), Q is a randomly generated orthog- onal matrix we use to avoid coordinate-friendly structures, LSE(a)...... a,) = log(e + +... + e²n), and a 2 O.
and show MMRCPD is closed in S' = span ( [V, V2, Va, Vz).
Then the problem reduces into finding p(M (s:) which
Convergence of the expected iterate [[ is weaker than that of the expected iterate norm TE [E[[|T]]] []] function value E (ør))
For (iv), we use the l lz-regularized logistic regression objec-
as the latter implies the former (if f is convex) but not vice versa.
8

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
requires a fine spectral analysis of asymmetric 4 4 matrix with controllable variables a, [0, 1]. See
100
1.0
|A |A- (AJA 112
Appendix E. for more detailed discussion.
Thm 3.3 RHS
0.8
General Quadratics. The only known results that con- sider RPCD for general quadratics are those by Sun et al. (2020), where they observe that for each permutation
0.6
0.4
T A RIRPCD A
(12)
= I - A PTp A
A A p(n)) ... pp())
0.2
0.0
where - i-th column of A They then show expected ilerate* convergence from p (T ((TA)D) I -. The resulting iteration complexity upper bound is n times loose compared to both upper bounds and previous results for A E Ar that involves the n-th exponent, 2 ) instead.
a projection matrix with vi being
0.0
0.2
0.4
0.6
0.8
1.0
Figure 4. Plot of || || --
(.Ma(A)A (I=
and the RPCD upper bound from Theorem 3.3 for n 100.
For our goal, it is sufficient to show
We obtain results demonstrating that RPCD outperforms RCD for any problem instance A A (Theorems 3.1 and 3.3), show a stronger RCD lower bound that induces clear gap between RCD and RPCD (Theorem 3.4). and conjecture that RPCD will also outperform RCD for general quadratic functions (Conjecture 4.
p(MarD) EE [ & TRPCDT])
2n
1
B
(13)
max
While there are no well-known analyses on the upper bounds of the spectral radius of the expectation of Kronecker pow- ers of matrices over permutations, we can use (12) and P(MBPDD) = p(MMRCDD (see (8)) to equivalently write?
An immediate future direction would be to prove (or dis- prove) Conjecture 4.1 for general quadratic functions, and possibly further analyze the benefits of random permutations for even broader function/algorithm classes, such non- quadratic (strongly) convex functions block coordinate descent algorithms.
(MMADD p (B TRPDDT IRRCDT]]
= p E
(Zm()) Zp(i)) T&2]
A Acknowledgements
One possible strategy could be to use
This work was supported by National Research Founda- tion of Korea (NRF) grant funded by the Korean government (MSIT) (No. RS-2023-0021 (0011322))13 and Institute for Infor- mation & communications Technology Planning & Evalua- tion (IITP) grant funded by the Korean govermment (MSIT) (No. 19-209991190077 Artificial Intelligence Graduate School Program (KAIST)).
P(MBRDD) < A 1/2 12 RPCD (A)A (A)A-1/
1/
(14)
to circumvent the need to compute the sum of the Kronecker powers. We can use (12) to express the RHS of (14) as
E Zp(1) Zp(m) ... Zp(r)]
We have numerically checked that (14) is quite tight enough to be useful when < 4. but unfortunately gets suddenly loose for o > 1 if n gets large, as shown in Figure 4. See Appendix E.2 for proofs of some of the statements above and more detailed discussion.
Impact Statement
This paper presents the convergence analyses of randomized coordinate descent algorithms. We do not have any specific ethical/socictal impact or consequences of our work, other than trivial implications related to the advancement of the field of Machine Learning.
5. Conclusion
We have shown convergence lower bounds for RCD and convergence upper bounds for RPCD for positive definite quadratic functions with permutation-invariant structures.
References
Ahn, K., Yun, C., and Sra, S. SGD with shuffling: Opti- mal rates without component convexity and large epoch
'The notation (.)22 is the Kronecker product with itself.

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
requirements. In Advances in Neural Information Pro- cessing Systems (NeurIPS), 2020.
Jacobson, N. Basic Algebra I. W. H. Freeman and Company, New York, edition, 1985.
Beck, A. and Tetruashvili, L.. On the convergence of block coordinate descent type methods. SIAM Jour- nal Optimization, 23(4):2037-266) 2013. doi: 10.11377110888767. URL https: org//o.rg1.... 1137/120887679
Knutson, A. and Tao, T. Honeycombs and sums of Hermi- tian matrices. Notices Amer. Math. Soc., 48, 09 2000.
Lai, Z. and Lim, L.-H. Recht-re noncommutative arithmetic-geometri mean conjecture is false. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference Machine Learn- ing, volume 119 of Proceedings of Machine Learn- ing Research, pp- 5608-5617. PMIR, 13-18 Jul 2020. URL https: / httpp//coeeenng..eeee////e prroceecings.mLr.pree.... mir.press. v119/1ai200 html.
Bhatia, R. Positive Definite Matrices. Princeton Series in Applied Mathematics. Princcton University Press, Princeton, NJ, USA, 2007. URL http://press. princeton. twwt:etees/eeeeeeeeeeeeeeeeeeeee 8445. 844..mm14................
Bottou, L. Curiously fast convergence of some stochas- tic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, 2009.
Lee, C.-P. and Wright, S. J. Random permutations fix worst case for cyclic coordinate descent. IMA Journal of Numerical Analysis, 39(3):1246-122 1275, 2019.
Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD: Random permutations and beyond. In International Conference on Machine Learning (ICML), 2023.
Lee, Y. T. and Sidford, A. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In 54th Annual IEEE Symposium on Founda- tions of Computer Science, FOCS 2013, pp- 147-156, 2013. URL 2013.24.
Cho. H. and Yun, C. SGDA with shuffling: faster vergence for nonconvex-pl minimax optimization. In International Conference on Learning Representations (ICLR), 2023. URL https:://ppeeeeeeeeeeee htt///pperevveeeeeeeeeeeeee nett Forum?id=se (orum?idd=xxtMMbFFF 6XXLMBDFFJ.
1ttp://....111////11 FOCS.
Liu, Z. and Zhou, Z. On the last-iterate convergence of shuffling gradient methods. In International Conference on Machine Learning (ICML), 2024.
Das, A., Schölkopf, B., and Muchlebach, M. Sampling without replacement leads to faster rates in finite-sum minimax optimization. In Advances in Neural Informa- tion Processing Systems (NeurIPS), 2022.
Mishchenko, K., Khaled, A., and Richtarik, P. Random reshuffling: Simple analysis with vast improvements. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
De Sa, C. M. Random reshuffling is not always better. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, vol- ume 33, pp. 5957-5967. Curran Associates, Inc., 2020. URL https:: https://procceddnss.eeee oc hes/paper___e hcc/paper_fllesspppeeeeee wtt.feee//pppee/22///tiii 09229666ee1199555777777999933839 pdf.
Mishchenko, K., Khaled, A., and Richtarik, P. Prox- imal and federated random reshuffting In Inter- national Conference Machine Learning (ICML), 2022. URL.ttpss//pproeeddnn mlr. wtw.ings.......ss//..... v162 11622miishcheenoo2222 htt.hhhhhnnnk2222.......
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Opti-
Gürbüzbalaban, M., Ozdaglar, A., Parrilo, P. A., and Vanli, N. When cyclic coordinate descent outperforms random- ized coordinate descent. In Advances in Neural Informa- tion Processing Systems (NeurIPS), 2017.
mization, 22(2):341-362, 2012. doi: 10. 10.11137/1008020001 URL https: doi 1ttt://///0..1111/0000000000
Nesterov, Y. and Stich, S. U. Efficiency of the accelerated
coordinate descent method on structured optimization problems. SIAM Journal on Optimization, 27(1):110- 123, 2017. doi: 10. 10.1133/16M1000188 URL https: //doi. orgoi.orrg/in 0 1 377 6M1 600182.
Gürbüzbalaban, M., Ozdaglar, A. E., Vanli, N. D., and Wright S. J. Randomness and permutations in coordinate descent methods. Mathematical Pro- gramming, 181:349 - 376, 2018 URL https: //api. semanticscholar Org/CorpSSID: 119151332.
Nutini, J., Schmidt, M., Laradji. I., Friedlander, M., and Koepke, H. Coordinate descent converges faster with the gauss-southwell rule than random selection. In Interna- tional Conference on Machine Learning, pp. 1632-1641 1641. PMLR, 2015.
Hom, R. A. and Johnson, C. R. Matrix M Cambridge University Press, 2 edition, 2012.
10

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Recht, B. and Re, C. Toward a noncommutative arithmetic- geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory (COLT), 2012.
Richtárik, P. and Takác, M. Iteration complexity of random- ized block-coordinate descent methods for minimizing composite function. Mathematical Programming, 144:1 38, 2011. URL org/Corpus ID: 16816638.
Russo, B. and Dye, H. A. A note on unitary op- erators in -llalgebras. Duke Mathematical Jour- nal, 33(2):413 416, 1966. doi: 10.1215/ 50012-70044-6-00346611 URL cettps://doi.oo
10.
Sun, R. and Ye, Worst-case complexity of cyclic coordinate descent: O(n²) gap with randomized ver- sion. Mathematical Progrumming, 185:487 520, 2016. URL https: sewanticsssttsimeeeeee org/ ort/Corpus1D::2233522
Sun, R., Luo, Z.-Q., and Ye, Y. On the efficiency of ran- dom permutation for ADMM and coordinate descent. Mathematics of Operations Research, 45(1))233-22 271, 2020. doi: 10.1287/moor.2011.99900 URL https: //doi. wrg./rrg///. 10. 1287 2287/mooz 2019.00100000000000000000.00222. 0990.
Weyl, H. Das asymptotische verteilungsgesetz der eigen- werte linearer partieller differentialgleichuneen (mit einer anwendung auf die theorie der hohlraumstrahlung) Math- ematische Anmalen, 71(4):441-479, 1912. URL https: //doi. org/ 10. 1007 FF44145004
Wright, S. Coordinate descent algorithms. Mathematical Programming, 151:3 2015. URL https://api.
Wright, S. J. and Lee, C.-P. Analyzing random per- mutations for cyclic coordinate descent. Math. Com- put., 89:2217-2248, 2017. URL. https::/api: semanticscholar. www.aaarrrrrrooooooaaaaaa 39214484:9...
Yun, C., Sra, S., and Jadbabaie, A. Open problem: Can single-shuffle sgd be better than reshuffling sgd and gd? In Belkin, M. and Kpotufe, S. (eds.), Proceedings of Thirty Fourth Conference on Learn- ing Theory, volume 134 of Proceedings of Machine PMLR, 15-19 Aug Learning Research, pp. ngs ml r.ress// 2021. httpttts:: http///occecoccoooooo v1 pwobbeeee- www.eeemmyunllaatttth.. html.
Yun, C., Rajput, S., and Sra, S. Minibatch vs local sgd with shuffling: Tight convergence bounds and beyond. In 10th International Conference on Learning Representa- tions, ICLR 2022. International Conference on Learning Representations (ICLR), 2022.

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
A. Proofs in Section 2
A.1. Proof of Lemma 2.3
Here we prove Lemma 2.3, restated below for the sake of readability.
Lemma 2.3. The matrix operators MRD and M both diagonalizable.
Proof. For M consider the matrix operator:
MRCD
(X) = RCD
(A X X X
similar operator to MRD as it maps A XAX A
A
MA
RCD (X) A 3,
This can be rewritten in the form of
M
RCD
(X) = E TRRDDT XTAD
where the expectation over symmetric matrices
1 A E, A
TARCD = I
Therefore the matrix form of MRCD
E
T A,E
T A,
must also be symmetric, which implies that MRCD is diagonalizable. Hence MRCD must also be diagonalizable by similarity.
For MRPCD, also consider the matrix operator:
MRFCD (x) = MRRCD (A XA A-
which is also similar to .RRPED and can be rewritten as
MRRCD (X) = E
TRPCD TRRD
where the expectation is over the matrices
TRRC
: A A: PT A A.
For each permutation p, we consider a complementary permutation p' defined as:
p'()== (n + 1) p((), Vi [nt]
The permutation matrix P' generated by p' satisfies P'T prT = (PTpPT) )
(Sun et al., 2020). This is because
PTpP Ptril(P AP)P A Wp.
where Wp is binary matrix with
1, p(i) ((1
Wp
0, otherwise.
Since p(i) 2 p(i) and only pf) 2 p'),,, we have Wp WP and PTP (PPPPT)T.
Therefore we have TRPCDD
AT (TRPPCD) and the following sum:
T
A.P
RPPCD
A.P
+
RPCCD A.P'
RPCCD A.p'
also symmetric as a sum of transposes. As the set of all permutations can be paired with its unique complementary permutation, the matrix form of MRRCD
RPCDT C R
must be symmetric, which implies that. RPCD and RPCC must also diagonalizable.
12

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
B. Proofs in Section 3
B.1. Proof Theorem 3.1
Here we prove Theorem 3.1, restated below for the sake of readability. Theorem 3.1. For an initial point Zo E IR",, let ar be the output of RCD after T iterates. Then, except for a Lebesgue measure zero set of initial points,
E [|
max (1-2))
-
lim 70000
x 1
71
n
Proof. We will prove the following two inequalities:
1/T
[|arr 12
lim 7-000
2
[
1/7
IE
| 12
20
(1 -1-
2
lim T-000
7
To show the first inequality, the fact that MRCD
(I) 1
2A +
A
Then,
E
2
Fk-1]
k M
MRRD
I
2A
A
= k-
Fh
2A
A
2 Amin
+
2 k-
--1
Since the cigenvalues I 24 + are in the form of for any x E R, we have
22 2
n where is an eigenvalue of A, and
2z
+
2
2
1
E [ 2t
xk-1]
1 (1-
T kk-
Ik-1.
By the law of total expectation,
2 WT
Øo]
= E
[E
x xT-1] x0
E [xT- (T
T ||00||
For the second part, we use the following lemma.
Lemma B.1 (Nesterov (2012), Lemma 1). X nm is positive semi-definite matrix,
X diag(X) (X).
Now we define the following matrix operator:
A
X 1- A n
MRCD MR) =
13

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
According to Lemma B.I, M MM for any = because
A (n diag( X) X)A
M (X) M (x)
n²
Moreover, if X 3 Y, then D MAD(Y)
We now aim to show that for any positive integer & and X ž 0,
(MA ( N (MA (X).
(15)
We prove this by induction on k.
Base Case: For A = 1, we have already shown that MAD (X) I MM (X). (X)
Inductive Step: Assume that for some positive integer k. we have
(MBDD)* 3 (
We need show that (MRRDD)++ M+ (X) 3 (MRDD)&+1 (X). Since
(M k+1 (X) = MAD((MMRDD)
3 (CMED(C (X))
(:: (M: = (M
(: (MMM() 3 (X) (MAD) 0)
-(MBDD)&t
we have (MBCD)++100 (X) 3 (MBOD) (X) and Equation (15) holds for any positive integer k.
Therefore,
ØT xT
xo]
= x (MRCD) -TTPT)
(1))0
2 2 (M (T)
A 2T
x I
Let 01, 02,..., Un be the eigenvectors of corresponding to the eigenvalues S A2 .... S An. respectively. Since A 0, the eigenvalues are positive and the eigenvectors form an orthonormal basis for R2 Therefore, can express Zg E R a linear combination, To Cj C2 + Cn where G; scalar coefficients.
Excluding measure zero set of vectors such that i x. 0, we may assume that * 0.
Now, let us define
X n
d;
14
Σ k=
1
k
25 (1-A))² x
Then, di # d; 2 0 for E [n), Σ d, and nn C and pa:
2
u22
2 pn
O.
We can express
in terms of
a, æ00
II
A
2T
ED
a
dipu
2T
x.
Thus, we have
[
A
æ0
1/T
Σ
n
diit
2T
1/r
2T
2T
1/2
f1
Unn
dj
+
dz
+
+
dn
μi
#1
14

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Ar Since 0 1a < 1, have
1/T
27
2T
d²tT= S
di + d2
112
+
+
dn
Un
S (d) + +...t
:.....)d)" dn)
1el
p1
Thus,
21
1/T
122
lim T-000
d1 + d2
dn
=1
because d1 0. Therefore we can conclude that
1/T
E 2 2T
Fo
2 11 = (1-20
0
lim 7-000
nt
which finishes the proof.
B.2. Proof of Theorem 3.3
Here prove Theorem 3.3, restated below for the sake of readability.
Theorem 3.3. For an initial point æo IR", let æ be the output of RPCD after K epochs. If A Ao and xo # 0.
E < 12]
S max 11-
0
2n
lim K-000
|zol22
12
Proof. We first assume that A = oIn + (1 - (1-0)1n11) Then, (min(A) and Amax = (n 1)0.
Let = (A) and - I-----
P-IA A. Since both and 11 T are permutation-invarian,, we have
M (I) CP
RFCCD (11T) =
We use the following lemma to compute M (T) and (ARPCD((11))
Lemma B.2 (Lee Wright (2019), Lemma 3.1). Given any matrix Q E Rx and permutation matrix selected
uniformly at random from the set of all permutations we have Ep PPQP [] = TI 7211 where
Q'Q - Ir Q n(n - 1)
(r
72
71
72-
n
As consequence of this lemma, MRRPD and MRRCD (11)
can be expressed as
I (1) "1ITT MRRPRD
( I +
(2) 11 (11
where 7/)
T2 :1 and T22 (2)
(1)
(2)
can be computed using TT (r C) I and i1(C
We remark that span I, 11T } is invariant under MRPCD and the matrix representation of MPCCD
(ppan(I.11T) is MA :=
(11
(2)
TI 7
That is,
(1)
(2)
T2
T2
MA
b'
15

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
then MA (al + - d' ='I+
Let us denote 1 CI," we have
and 11 C) a, B, and 6, respectively. Then, by Lemma B.2,
1
n3 - a no
MA
n(n 1) a 3 7
To derive the explicit forms, we first calculate C, which is given by I - r-1 A. We can express r-1 as follows:
0 TT
<
1
ifi=j
- (1 (1-0)00-33
ifi
Consequently, have
-(1 0)0-1 ifi
Cj
(16)
(1 (0- - o if
To proceed, we introduce v = C1, w = 1 and L = Amax (A) = n2 (n 1)0. Then, by Equation (16), we have
1
0
= 1-
With the explicit form of the entries of C, we can now calculate the four quantities ar 8,7, and 6, as follows (when or + 1):
- nt
2n
a 1 1==- n-
1-0
22
1 2n
1 1 σ 2(n--++1) 20--11
==
Σ
C
Σ
(1 o)²
+
(1
1 o²
1 0²
j=1
- 0
2n
no 2n
- 22(1-
n+1
1 n
2
1 2a
(17)
1+0
1-0
1 02
7 = (1 v) 2
1
1
2
1
+
11
+
1 - 0
1 -
1 σ
- 2n
= w w
no 2n - n11
to2
1-o
1 1- 1-
Note that all of these values are polynomials in a. (If 1, all four quantities above are equal zero.)
The explicit form of 9,7, and 8 allows us establish the following lemma.
Lemma B.3. (1) T (1)) and (2) are all non-negative.
(2) (1)
T2
Proof. First, we show that T1 , - 2 0 from the fact that RPCC preserves positive semi-definiteness.
Recall that M (X) E XTRPCD). Since X > implies TRPCDT A, positive semi-definits matrices is also positive semi-definite, we can conclude that .MRPCD X > 0 whenever X > 0. As
XT > and the expectation of A.P
A.P
both I 2 0 and 11 > 0, it follows that (MPCD(()) > 0 and MRPCD(111) m 0, i.e., their eigenvalues are non-negative.
Since T| (1) and - (2) are eigenvalues of RPPCC (T) Z and M RPCC (11 T) Z respectively, we have 7( [
(2) 0.
16

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
(2) Next, we show that 72 2 For
C 1, we have
= 1 www' " = (1 T w)² 8 tr(ww) ) tr(w" ((wwww -| 12
Since 72 7 77-6, -6, we have
22
(1 T w) 2
Σ w( (i)
i<j
Since voii 0² - o < 0 for all i E [n]. we have w(i)w(i 2 0, and therefore T2 = - -i w(i)w(() 2 0.
Finally, to show that T2 (1) In particular, we can prove the following two inequalities:
2 0, we first show that the entries of C C is non-negative.
If j < n, then CTC, 2 C. Cj+1.
If2 n,, then C.C,, 2 CJ,,C
where C; denotes the i-th column of C. To show the first inequality, we begin by considering the difference Cj Cj+1- We have
k < j.
(C, Cj+1)s
if = j.
(18)
(1
k > j.
Therefore, if2 n.
=[(0 - Σ (1 (1-o) (1-0)
-oh=1) 11-0)(00=-00-11000 oh-i-1)
k=j+1
n
= -1 =10-0)(0-1-07 -
σ + -
Σ
2h
A=j+1
Since i 2 2 and E (0, 1]. we have (1 - o)2 2 0 and (0 (0- 2 0. Thus, it suffices to show that
od - Σ
2h 2 0.
k=j+1
Since
22h σd + 10-11----110 -0-1-1)0242 1- (nn-f)
ol + (0-1 - -
E
1- o²
k=
1 1+0 (1 - g2(n=11)
Ito + 22+11
we have C. (C, - Cj+1) 2 0.
17

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
For the second inequality, will show that C,) C, O. Using Equation (18), we obtain
j-1
(,) = =1 (1-o)² -oi-2 (0-1-11 -
2k + (a-
- - 0000 11000-o01 -o-1) Σ o
kmi
k kmj
Since
n
10-1t1-000 (000 - Σ
0-
24 20
k=j
is sufficient to show that
xi-2
+ (001-1 0
0 S
Since
+ 10 -i-1 0000002 02(i-1)
i (0
+
i-1 0
2k
-0" 1-2
1001-1
kmi
$ - d'-1 of
0²
a+1
00,
it follows that (C, - C,-1) C, 0.
Using chain of the inequalities we showed, we can obtain ming<iejgn
C. = C2 Cn. Moreover, since
C. -1-=)
+ (1 - -- 0n - -00 D
2)
Σ
2k
-on-1)
2=
and
1 (0 -3
2
Σ
2k + (1
00-
0"11)
2 (0
2k
k=2
k=2
(0 3
IV
0.
we have C.J Cn 2 0. Additionally, since Ci = 0, we have C, C, = 0 whenever i i= or = With the fact that
CTC, 2 if S i,j S n, we have min si.jnn CTC, min siinssC C).; 2 0, i.e. all entries of CT C are non-negative. Therefore we can conclude that
(1) -
-CCT
2 0,
which completes the proof.
18

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
We now shift our focus the left-hand side of the inequality in the theorem. Since (MA (MAAD)) is symmetric, have
E
x
[1
2id (MARDD) (T)
xoll
Fo 20
I Amax (MM RRCDD (T)).
Importantly, we have previously shown that (MA (I) can be computed using only MA. Specifically, if we write (MADCD) akI + 3x11", then it follows that
Fak 3x
M
Moreover, since the entries of MA are non-negative by Lemma B.3, we have ak, 3xx 2 for all K 2 0. Since the eigenvalues of matrix of the form af + b11 are and a + nb (with multiplicity n 1), the largest eigenvalue of (MRRD)) (I) agI + 3x11 is given by
ak + n3x -y' M x
1 and =
1
where æ
To proceed, use the following lemma, known as the Gelfand formula.
Lemma B.4 (Horn & Johnson (2012), Corollary 5.6.14.). If A _ then p(A) limm - 11/K
Since A (I)) =y TMM x 2 O, we have
(MMmx (I)) (1)) 1/K K-0c
lim
lim ly T M A x: 2///K
K-000
s lim ([]v|]| A
(||=|| [||==|))
k k0000
I lim ||
|
|<]
||M 1/
K0000
(MM)).
(: Lemma B.4)
Now, consider A diag(olx + (1 (1- 1) In- for an integer k with S k n. We denote the submatrix aI (1 1) by Ag. Let Sn be the set of permutations [n]. We first show the following lemma:
Lemma B.5. Let P be n X permutation matrix generated by permutation p E S,, Let be permutation of [n]
such that (() = in for E [k], where i,,...,y in is reordering of [k] satisfying p (ix) > ... > p (ii), and q(1) = for 1 k. Define Q as an n x n permutation matrix generated by q. Then,
РPpP* = QTQQ
Proof. Since
e trii(AA), = aij
ifi2j
ifi
and P P for any permutation matrix P, we have
e, PTpP
e; = 201) I pep 1())
(P APPe
if 2 p (() if
p 1())
0
Aij
(1) (
0
if) p (().
19

---

Note that for any E Sn, there exists unique permutation 9s E S5 satisfying q() = i for E [A:], where in. . d is reordering of [k] such that p (ix)) > p (ii). Furthermore, there exist n! Ør permutations in S, that correspond to Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent Consider first the case where i, [k:] Then,
p (1) 2 (() = == las j = in for some a, b E [k]] such that a 2 b
= 9- = a 2 b = q (is).
Therefore,
e, PTpP = = QrQQQQQe cj
for all ز E [k].
Now consider the case where i E [k] and & [k]. In this case, we have dij = 0, so the equality e PT pTpP"e ej = e, QQrQQ ej holds trivially. Similarly, the equality holds when & [k] and j E [k]-
Finally, suppose i,j $ [k]. Then both e pTpP ej and e, QT e are equal to 1 if = j. and otherwise. Therefore, we conclude that
e, PTpP e Qr ej
for all i.j E [n].
given 9k-
Let D the set of block diagonaa matrices consisting of a l x block and an (n - k) x (n (nnnk) k)) block. Then, D closed under sealar multiplication, matrix multiplication, addition, transposition, and inversion.
Qra'Q A by Lemma B.5. Also, I,P,Ip and are in P so TRPCDD E DR.n-k- To analyze the structure, let 9ı be the restriction of to [k] and Qx be the permutation matrix A.P
Now, we have TRPCD A.p I PT A
generated by 4s. which is equal to the (1, 1)-block of Q. Then, the (1, block of TDPCD is given by I Qu Q. Q A and the (2, -lblokk is nn-k meaning that
RPCDD A.P
TRPCD Au.ge
Ok
On-ki
On-knn-k
X11 11
Ok X122
Therefore, if X
E DR have
On-k,k
MRRCD
(X)
n! Σ
RPRCD XTRDCD)
PES.
TRRCDT
Ok &
X11
0k X
TRRPCD Av.ga
Og.
k!
On-k,k
0 Packn-k k
On-k,k
On-k,
0 -
9r.
TRPCDT
Au.ge
11
TRPCD Az.uu
Ok
ES
RRRDD (X11)
Kkn-k
On-
-
By the above, for all K 2 1, we can see that
[MRPCDD K (Ix)
(MMREDD)
O
On-k.k
0
and
Amax (MRRCDS (In)) Amax (K (II))
20

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
because (MBRDD) (Tx) =
Since we have already shown that x-me Amax A ((MAAE (II))) ((MAR))<(II))""
- p((MA.) ), it suffices to show that
p(MA.) S max
(1- (1
0
2n
To proceed, we can use the fact that (M S |M 20 Since || MA 01.0 max (1) + +11 +111 72 positive values by Lemma B.3), is sufficient show that the inequalities
(2) (1) (2) (all being
(
1 a
-| 0 (k) (k. S max
1
1
(19)
a
2 (k; 0) +
(k. (k)
max
(20)
hold for all integers & such that 2 < k S n, where 7. (1) left-hand sides in (19) and (20) are polynomials in a, the problem reduces to comparison of polynomials.
(k:, o) denotes (MA))s for i = 1, and = 1,2. Since both
now focus on finding the coefficient series of 8, 7, and when each written as polynomial of a. This because the left-hand sides of the inequalities can be expressed terms of these polynomials. We introduce some notations for brevity. Let 8n Ex= of and t, =E= σ2: Then, for E (0, 1), have
1 1-0" Sn
tn 1 o2n
1-o¹
o²
Since = = 0 when 1, we will focus calculating the coefficients of a, 8, and for (0, 1).
COEFFICIENTS OF
We have
Ls, = Σ 0 1m
1=1
R-1
L't, =n²- = -2n(n
Σ
21+1 +nn + (n 1)3)
Σ
2142
(n 1)202n
i=U
1=0
Since = n n-2s, + 1, if we write a
2n 4
n n 12
if k = 0 if < < n 1 and & odd
2n + 2m
2n 2n 1
if < k S 1 and & even
-2(n 1)²
if k: = n and odd
ag
2n²
if l: and even
-2n(n 1)
if n + 1 < h: < 2n and k odd
2n² - 2n + 1
if + 5 k < 2n and even
(n - 1)2
if k: 2n.
COFFFICIENTS OF 3
We first expand
n-j
(1 (1-
Σ
[1 -1-28 (1-20--1 105
Σ
σ 2
= (1 - o)²
25
(1 x)
2
25
1=1
1=1
1=1 1=0
j=1
1=0
21

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Using the fact that
R-1 n
k)o
we can simplify the first term:
7 a
2n 2
(1 0
12n
1 k)o**
k=1
For the second term, we have
R-/
2n
0)²
21
(-o)*
j=1
Now, the remaining part
1 0
n11 - -0) (1 + 0 +... + 2n-2)
2n-1 1
= 12 + no 2n
+
2n -0)
k=
Therefore, 3= Ex= b where
2n - 2
if k: 0
-3n +3
l: = n and n odd
bk-
3n + 1
if t: n and even
- 1
if k: 2n
(-1)* (4n -
otherwise.
COFFFICIENTS OF 7
We use the fact that y= ()=(10)) (1 = (n Ls Since n Lsn = (n - 1)0" -En- 0¹, we have
(n Lsn)²
(n 1)0"
o²
i=1
2n-2
(n - 1)2
-2(n 1)0" "
o¹ Σ (j 1)o0.
j=2
Consequently, 7 Ein & where
if 0 0
if < k In n
C6
k
if 1 < 2n 1
1)2
k 2n.
22

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
COFFFICIENTS OF
Let =E dRo Since
8 0 d'j²
1=1
2n 20 + 02112
2(0 n1 +... 0 (0² +.....0 )
no
0
if =
0
if S n and k odd
1
if S & S n and k even
-2
if
2n 1 and & odd
-1
if +
2n 1 and & even
-- 1 i = 2n.
We can now express the left-hand sides of inequalities (19) and (20) using the coefficients of a, 8, and 6. Let us define
(i n(3 + 6) (a + =
k=
T2(n,o) (a 7) - (8+ +8)
12,10
Then, o) = -n(nnn1())))) 1)( + (2) J,T2(n, = n(n - 1) 4 T2
(2)
n
if = 0
(n 1)k 2n2
if S < n and & odd
11
+ 1)k 2n
2 +2
if
and 1: even
(n 2
if 1 S k <
2n and k odd
(n +
if
2n and even
and
n2 3n +2
if 0
-2n2 + 6n -
if < k < n and t odd
2k + 2n 6n 2 2
if < k < n 1 and & even
f2.
-2n² + 8n 6
if n and odd
2n² 2n
if = n and even
-2k 2n 2 + 6n +
if + < k < 2n and odd
2n 6n
if x k 2n and i even.
We will first address the case where n is sufficiently large. For the remaining cases, including inequalities (19) and (20) for smaller values of as well as specific polynomial inequalities arising during the proof for sufficiently large n, we will utilize Sturm's theorem (Proposition B.6), which provides method for counting the number of distinct real roots of polynomial within given interval.
23

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Proposition B.6 (Jacobson (1985), Sturm's 's Theorem). Let I (x) be any polynomial with coefficients in R of positive degree. We define the standard sequence for f(x) by:
fo(x) = [(x), fi(x)= = ('(x) (formal derivative of f(x))
fo(z) = (x) - f2(z), deg fa < deg f1
(2-1()) = (x))(()))))))) - Set(()), deg S441 < deg Si
fa(x) go (z)f(((z) (that is, fe+1(1)= 0).
Given sequence c = (c1, Cm.).., of elements of R. we define the number of variations in sign of c to be the number of variations in sign of the subsequence d' obtained by dropping the O's in c.
Let [(x) be a polynomial of positive degree with coefficients in a real closed field R and let ((x))....ff((1) be the standard sequence for f(z). Assume [a, b] an interval such that f(a) * 0. f(b) + Then the number of distinct roots of f(x) in (a,b) b) is Va Vo, where Ve denotes the number of variations in sign of f(f.....))...............
= f())
To apply Proposition 8.6 inequalities, utilize the following property: for polynomial p, if p(x) # 0 on (a, b) and p(a) > 0, then p(b) 2 O; similarly, if p(b) > O, then p(a) 2 0. By this property, we can verify that 2 0 on (a, b). [a, b), or aa, bj. That is, since p(x)= * 0 can be confirmed using Proposition B.6, we only need to check that is positive at the specific endpoint of the interval. Once this is established, we can conclude that 2 0 on the interval (a, 6), [a, b). or [a, bj. as required.
Prior to the main proof, we establish the following results using Proposition B.6, which address not only the remaining cases for smaller values of but also certain inequalities that arise during the proof.
For i = 1,2, (m
< 7)
=)2n"
2n for all integers m and n where 2 S m S n S 6 and E 00,).6).
Tim.or) < 2 for all integers m where < m 10 and a E [0.6, 0.8).
m(m-1)
Tmmmo))
< 1 for all integers m where S m S 14 and a E [0.8, 1).
m(m 1)
4
T2(m.o)
S i
1 for all integers m where 2 < m S 10 and a E [0.6, 1).
m(m-1)
We verify these results in Appendix C using Proposition B.6 implemented in a computer algebra system. See Appendix for more details on the implementations of the computational verification system.
Back to the main proof, to prove (19) and (20) the interval (0, 1] for all integers & and such that 2 < k: S n, we first divide the interval into three subintervals: (0, 0.6). [0.6, 0.8] and [0.8, 1]. We then show these inequalities for each subinterval. In the subsequent proof, for the cases when a E (0, 0.6] and when o E [0.6, 0.8), we initially assume that n 2 7 and n 2 11, respectively. The results of our proof can be summarized as follows:
a E (0, 0.6:: Both inequalities (19) and (20) hold for all integers and n such that n 2 7 and 2 S l S n.
a E [0.6, 0.8): Both inequalities (19) and (20) hold for all integers & and n such that n > 11 and 2 < k: S n.
a E [0.8, 1]: If + 1, inequality (19) holds for all integers l and n such that n 2 15 and 2 < 1: < n, and (20) holds for all integers and n such that n 2 10 and 2 s k S n. If o = 1, since the left-hand side of both (19) and (20) is 0, thus they are trivially satisfied.
24

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
CASE E 00. We first show that if 2 S n, then 1122 2 0, 1, S 0 and + S If S S n
12 = (n - 1)2i + 2n + 2n +
2m 2 -n - 1)n+ 2n + +
n² +
2 0
and
1,21-1 (n 1)(2i - 2n n 3
S ( - 1)2 2n 3
= - 2 3n 5
S 0.
Moreover, we have 11,25-1 + 1122
6 < 0 because i 2 2.
2i = n +++1. 1,
1,21 (n 1)(n + 1) 2n -2
= 21
20
and
11211-1
(n 1)n 2n n +3
=n 2n +3
< 0.
Furthermore, we have -1,21-1 + f1,21 = -2n 2 2 0.
Finally, n < 2i - < 2n 1,
11,2 -(n 1)2i 2n² 2
-nn(n - 1) 2n
2n -2
2
and
1,21-1
(n + 1)(2i 1) 2n 3n
(2n 1)(n + 2n 3n
-2n
0.
In this case, we have 1,20-11 + f1,2 4i 4n 5 because 2i < 2n.
Now, if (0,1).
2 + +11121-1000 2i-1
= 2i-1 (11,200 + (1,25-1)
< (t1,2:0 + t1,2611
< 11,21 11,21-1
(v 2 0)
5 0.
25

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Thus, for 2 Siis n1, have
Σ km 0
t 2 on.
(21)
This provides an upper bound for (i(n,o).
A similar result can be obtained for (n, rr. We first show that 12,21-1 S. 2, 2 0 for all i [n]].
Since 2n² 6n + 4, 2n - 2n 4, 2n 8n + 6 2 0, we only consider when & is even and 2 s k S n 1, or k is odd
and n + < k < 2n. For the first case,
12 = 2h + 2n
6n 2
2 2n 6n +
2 0
and for the second case,
12 2k 2n² + 6n 2
S -2nn + 1) 2 6n +
-2n +4n
Now, we show that 22,2 + 1, S 0if 12 n + 1. We have
t2,2 = 2n - 6n + 4
2
and
2,21111 = 2((i - 1) 2n +6 +2
< -2nn + 1) - 2n + 6n +2
22n 4n
< 0.
Moreover, 22,2 + 2,,2111 -4i + 8 < 0 because 2i - 1 2 n +
Using the fact that 12,21-1 < 0, 22 2 0 for all i E [n]] we have
12:2:02 24 + 12,21-10 21-1 = 28- (12,200 202-11(12200 + 12,21-1)
00
if a 0,
12.25 12
Thus, if
0. 12,21-1
12
0. min Isisn
22225
we have
2i 2
12 2 o2
k=0
for 2
26

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Now, we focus on the minimum of
12,26-1 2,
If even,
2n 6
2f S n
12,21-1
2n bn 24.4
2n 6x+1
2
1,,2i
2n
2n
2n
6n 4+44
if
S 2i < 2n.
Therefore, if n is even and n 2 4,
12,21-1
2n 6n
2n
6n
2n 4n
min 1Si5
min
2,
2n
4n
2n
2n 2n
6n +
n
If is odd and 2i - n,
2n 2 +
i 1 -1
2n -4-244i
12,21-1
2n 8
1
12,21
2n on+4
2n
6n 4+4i
in 1 2n.
2nd 64+4
Therefore, is odd and n 2 3.
12,25-1
2n 8n + 6 2n 6n + 4
2n 4n
min S
min
t222
2n 6n 4
2n²
4n
2 2n2 6n +
n1 -
2
Thus,
12,21-1 min
n
3
min 15:50
(22)
12,25
n +
Since 0.6 < n-1 n-3 for 2 5, for e 0.6 and i [n]. have
n+1 n-2
2i t2 2 o2.
(23)
K=0
Our next step is to find a lower bound for (1 =)²² coefficients.
2n
To this end, we first prove the following lemma about binomial
Lemma B.7, For positive integers r and n such that
S r < n
2n 1
2n
1
n"
+
1
n"+I"
Proof.
(++
NFT
2n
2n
nr + 1)
and
2n r
51
(n + 1)r.
n(r + 1)
Since S (n + 1)r for all 2 and both (2n) nr
and (m2m) कानन are positive, we conclude that
2n
2n
2
nr
+ 1 n1+1*
27

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
By the Binomial Theorem,
(1-
2n
2n
(
1 d'.
r
n
Additionally, for i S n
1, we have
2n
2n
n-1
2n
2n
1)
2k+1
o²
2n
22 +
(-m
22h41
n1
2n
2k
2k + 1
2
kmi
2k
2n
1
2k
2n
)
1
2h+1
( n2n 2tm 20
2k
71
2k
n
R-
(nn
1
2n
2k
26
2k +
n n 1
1n
2n
2h
(::0 S 11))
2k
n
2k 1)
n2k+1
k=
IV
0.
(: Lemma B.7)
Therefore, we obtain
2i-1 2n
1 -
2n
-
(24)
which provides lower bound for (1- == 2n
Let Pi = En d1,t0 By Equation (21), (T a) S (i, Moreover, if m is integer with 2 < S
Pi(m + 1,0)
2 m(m - 1) m(m² -1] 1) (m(o - -05 02 o0) 50 +05 + 20 0² -o).
Pi Pm
(25)
(m 1)m
Let Pı (o) σ6 - 05
oz 2 and (0) = 5 t 2 0²
It can be easily verified that 6p1 + 2 0 holds for a E (0. 0.6]. Also, (1 = o(a 1)2(3 1) +1) 2 0if 2 0.
so mp1 + 41 2 0 for all m 2 6 and a E (0.0.6.. This implies that
Pi(m + 1,
> ())
(m + 1)m
m(m - 1)²
or equivalently, Pi(m.a) mfm-1)
increasing in m, for all 2 6.
28

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Now, define Di = (Er=o (2r) (-
n[n-1] Ex=o d1,20*. Then,
d1,0 0
d1, =
33 +
d1,2 = n(n - 1)
2m² 6n - 2
d1,3
3n2
8n 4n + 35n
14n +
d1,4
6n (n - 1)
26n
10n² 35n² + 25n 6
d1,5
15n
2(-n² + 2n 2)
d1,s
n(n - 1)
Note that d1, 2 0 and d1,2 S Since implies 0.6 S for a E 0....6.. Now, rı (n, .) = d1, + d2,50² + d1 d1.3. Then, we have D1 = o + 21 + d1,10, Therefore, it suffices to show that ri 2 0.
d1.1 da,2
2n-2 3n-1"
we have +1 =dd1,00
We proceed by examining the derivative of 1i with respect to to determine its monotonicity this interval. The derivative is given by
d
(1, 0) = =3d1,0² + +211,50 + d1,4-
do
For 2 7, we have 3d1,6 -4, 2d I 4 and d1,1 -1 Therefore, for (0, 0.6), we have
d (n s -40² + 40
dg
-20 1)² S 0.
Thus, () is decreasing on 0.6). Consequently, ri (n, a) 2 ri (m if E (0,0.6). Furthermore, we have
ri (0.6) = 44n + 700n + 823n + 530n² 333n + 108 2 0.
750m (n 1)
Thus, we can conclude that Dj (n, 0) ('ri(n, + 20 + d1. 2 for a (0, 0.6] and m 2 7.
Similar to Pt. let P2
Ei=o k Then, T2 P2 by (23). Furthermore.
P2(m + L, P2 σ)
2 (m + +1m m(m - 1) m(m² - 1) (mp2(o) + 92(0))
(26)
where p2(a) 20 - + 2 3 + 202 - 2o + I and 92(a) 88 + 20 - 40 + 20 + 20 1.
Then, follows that 2p1 + 91 2 0 for E (0.0.6).
Moreover,
P2(a) 20 - o 0² - 03 4 0²)
1-o 7
1 1+0
0,
29

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Pa(m.)) so mp2(0) ()) 2 0 for all 2 2. Therefore, m(m-1) is increasing m.
Now, similar to D1, we define o2 = 2 (2)) (-1)"
n(n-1) = Ei d2, Then,
Pa(n,o)
2
d2,0 n
d2,1
3n 1
22,2
n (n 1)
2n 2 6n -
22
3n
8n* + +0m² - 13n² - 14n + 3
22,
6n (n 1)
26n 40n 35m + 25n 6
d2,5
15n
2 (--n2 + 3n 5)
d2
n (n 1)
Letr2(n, 22 + d2,50 d2 d2.3. Then, express D2
D2 = o - + 22 + d2.10 + d2,0.
We will show that the minimum of D2 is non-negative on (0, 0.6). First, we consider d2 + d2210 + d2,0. This quadratic attains its minimum value of 2(n+1) 2(n-1) n(3n-1) 3m-1 Thus, to prove that D2 2 on (0, 0.6), it suffices show that
2n 1)
+ min o r²r2(0)= 2 O. (E
n33n - 1)
If min.. 2 0, then the inequality holds. On the other hand, if min r2(o) S 0, then we have
min r'r2(0) 2 0.6 min r2(0). (E(00066)
e
Taking the derivative, we have
d
3d2,00² + +2d2,50 + d2,4-
da
We can also observe that 3d2,6 S 2d2,5 <
and d2,4 S - 3 for all n. Therefore, given that ar 2 0, we can see that
15
13
52
12 <
0²
do
3
15
4
< 17
300
Hence, 72 is decreasing in a and we have
min eE(0.0.))
r2(a) r0(66)
4
716n
1505m 530n²
333n + 108
750n (n 1)
30

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
For 2 19, have (2.6. 2 0. In the remaining cases, we use the fact that minoo (²)2() 0.66). Then, for all n such that 7 v n I 18, we have
2(n 1) + min r²)2(0) 2 n(3n - 1) + 0.6692((0.6) n33 1)
2(n + 1)
eE(0,0.6)
1188m 6 + 427722n -41191 34645m - 13761 + 5913n - -972 31250n"(nn 4n 1)
2 0.
Hence, we can conclude that D2 2 0 for n 2 and a E (.,0.6)
Finally, we use the following lemma:
Lemma B.8. (1 ) is increasing if 2
Proof. Let an = (1 + =)" Then, by the AM-GM inequality,
Og 1 n
n1
=1 (1 )
... 1 )
n
n
n + 1 n+1
n n+1
01+11
For 00,0.6 and i 1,2, have
T. 0)
T2 σ)
Ti(m, o))
max 25
mmm
max
max 25
m(m - 1)
TgmSn m(m
max
T.
max
max s m(m 1)
P.(m, o)
max
1
max
(:: T. (T for 2 7)
7SmSn m(m
(2 σ))
P. σ)
max
is increasing in m for m 7
n(n 1)
m(m - 1)
max
[1
1
(:: D; 2 0 and (24))
σ 2n
(: Lemma B.8)
Note that we used the fact that maX2gm56 Proposition B.6.
Tim,.o) m(m-1)
< (1 - (1 for the first inequality, which can be verified using
CASE 11. a E [0.6, 0.8] Since (1 a) 2n < (1 1)" for [0.6, 0.8), is enough show that
n
T, σ)
(1-1) 1)
max 25m5n m(m 1)
<
for 1,2.
31

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
We start by examining P1. which is upper bound for Ti. By Equation (25), if mp1 + 01 2 0, we have
Pi(m + 1,0) Pi σ)
(m + 1)m m(m - 1) 2 0.
Note that p1 (a) = a(a - 1) + 1) + +1) 2 for a 2 0 and 2p1 q1 2 on [0.6, 0.8). Therefore, mpp + 91 2 0 for all m 2, and
o) Pi 0)
max 25mSn m(m - 1) n(n- - 1)
Pi (n)
s lim
n-00 n(n 1)
20 20 + 20 22 + 20 20
for E [0.6,0.8]
Next, we consider P2. We have already shown that if a E 0, min n-1 n-3 then (23) holds. Since we assumed that 2 11 in this case, and 0.8 v 1+1 I
n-I: n-2
a-3 for n 2 11, we have T2 S Ps on [0.6, 0.8).
n-2
Similar to P1. we first note that (o) conclude that
1-0+20" 140
2 0 on [0.6, 0.8]. Using the fact that 11p₂ + 2 0 on [0.6, 0.8]. we can
Pa 0)
P2(n, 0)
max
Smmm m(m - 1) n(n - 1)
s lim O2
nン n(n -1 1)
20 20
-
3 20²
20 + 1.
We also note that 2
20 + 20 20 + 20
20 +
S 20
7
(1
1
on 0...0.8).
11
Thus, for = 1,
max Ti(m,o) o) 25m5n m(m- 1)
max T.(m, σ) 25m m(m - 1)' Iimmsn m(m 1)
Ti(m,r)
$ max
o),, 115m5n m(m - 1) P. σ) |
max
max
4
1
max
max
(:: T.S P. for 2 11)
4
11smen m(m - 1)
1
20" 20 + 1
max
20 20
20
20
1
1
< max
1 11
2
1
Lemma B.8)
n
T.m.a) The second inequality follows from the fact that max25m$10
< 4. which can be confirmed using Proposition B.6.
m(m-1)
CASE III. E [0.8,1]
o = 1, we have Ti T2 =0 0, and hence inequalities (19) and (20) are trivially satisfied. Therefore, we proceed to prove the incqualities for E [0.8, 1).
We first prove the following three lemmas.
Lemma B.9. log(1 + x) 2 1+z for x >
32

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Proof. The inequality is equivalent log 2 + 1 for O. This inequality can be easily verified by considering the function g(x) log
1. Since g' (a) 2 x 0 has the local minimum 1. Since g(1)
have
g(z) 0, which implies log 2 1 x²
Lemma B.10.
logí H+m)))
2_ for 1 0 and x > O. 2+x
Proof. If x > 0, the inequality becomes (2 + x) log(1 + x) 2 2x. Define f()) = (2 + 2) log(1 + =) - 2r. Then, (x)) = log(1 + x) Ite and (x)x) (1-m).- Since lim [a(r) and f"(x) > 0, (x)) 2 0 on x 0. Now,
suppose -1 < x < O. Then, the inequality is equivalent to f(x) < 0. Then, lim fx) = 0 and (=)x) < 00 f())) < 0
on 1 < x < 0. Since limz-so f(x) = 0, fxx x 0 for -1 < x < 0.
x² for x 2 O Lemma B.11. log(1 + x) 2 x 2
Proof. Let f(x) log(1 + +) x 2. Then, (z) 1 - 1 1 and f"(x) = (1+z)² Since f(0) (') = 0
Itx and (x)x) 2 0, (z) 2 0, f(x) 2 0 and the inequality proved.
We first find an upper bound for w(n-1) Recall that w = CC = -i of and L = n (n 1)o. We also define
I'
1.
n++
We use the following two lemmas: Lemma B.12.
0 Lsn Tn.
Proof. The first inequality holds because 8,
l-a" I-o
- 0 2 0 and
(1 o)- (1, 0-
n = (n - (n - (10) - - nn1 - o)
1
no" + (n -1)0
n 2
(1 o)
Σ 1=0
o² - (n 1)0"-1
0.
For the second inequality, need to show that
(n (n 1) -n(1 -nn1-)) +r, 5.. 50
To this end, let
(n( = (n - (n - (1 - -) (n 1 no" + + tn 1).
Then, (0) (n²² - 1)o" n + 1 T.. Since n- - (n² 1)o" has the maximum at a _ have
n4I [0, 1],
gn (0) 2 gn
ni +
by the definition of rn. Therefore, In. is increasing on [0, 1] As gr. (1) = O, we have 9n. S on [0, 1]. and therefore on [0.8, 1).
33

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Lemma B.13.
n(=-1) 1) S 1
Proof. Let > 1 and f(x) ( x+1]
8-1
By showing that f'(x) e²
can show that f(x) I (x: 1) + because
f(1) and
- - Jr 1(0)
Once the above is shown, it follows that
(1(x) 1)2
[(x)
2
1
x(x -
x-
1
2 < şz. To show that ('(x) 2.2 we differentiate (xx and obtain n(n-1)
and therefore
x-1
2x
1 _ )
(x))
x log
x
+
+
By Lemma B. log (1+ 1))
2x
2x+1+
f(x) -
T
2x.
2x
I +
+ 1
2x +
2x
2x
3:
Thus, suffices to show
2x
2r +1
x + 1
which is equivalent to
2r2 2x
(1+2)
1 x
S log 1+
+ x log
We now prove the inequality using Lemma B.10 and B.11. suffices to show that S 2x
8x + 2x+1
because 2x 80 S
log (1 + 2rd and Zr+I < x log (1 + 4). Multiplying both sides by (2x + 1)8x² we have 8x.2 < (4x
2x
1) + 1), which
holds for all 2 2 and therefore for x: > 1.
By the lemma above, have
7 1
(27)
n(n 1)
because (n 2.s)22
Next, we will focus deriving upper bound for nn)2, and (a* o0)2 attains its maximum a 1/(n-1) we have
on [0, 1]. Since 8 = Σm-(6 (0" - o00 < ~I m
2/(1 )
1/(1 +
n
Now we use the following lemma:
34

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Lemma B.14. x=/(1=2) -111))))--/----2- e (Alogg 2) if0~ < x <
x2/(1-2)
Proof. Let f(x)= ) Then, = x==
2) and therefore we need show that log f(x) I-r + log Then, g (z) =² "10g==(1=2)"
I-e I-glog + log(1 - x) - (4 2) Let g(z) lug
To check the
x(I-x)
change of the sign of g' define h(z) = x² log Since (x)
+ + (1 -2) = 2r log + - 2) log(1 - x)+1 1 and 2x: log x convex, so is (x) + (1(1 -x) and lim (1(xx) h1(1 - 2)= -lima + h1 x) - and 21((5) < 0. Thus,
for some c E (0, )) h' (z) +
is < x
and (x) + (11
0ffe
c.
Consequently, o 2 0f0 < I and g' 0f 1 Sx < 1. This shows that g has the maximum g (5) -4 2 and the lemma has been proved.
By the lemma above,
8 S
2/gg
8 Sog 2)i/n
-=1
1
e8 log 2)/n
and since و:'1 S 1 fort 0,
8
8 log 2
12 1 (n 1) blog 2 e log 2)/n 1
< 11
(28)
1 8 log 2
Next, we consider an upper and lower bounds of a. Recall that
1 - o a 2T,
1- + 1,2 22
0²
First, derive upper bound of a. To achieve this, will establish upper bounds for the terms -2
-2 1-o" and 1 222-020
1-o 1-0²
We start by analyzing L T-a Since L (n 1) and Sn = 1-0" by Lemma 1. we have
1 o" 2
(29)
Next examine the term 1
22
1-a2- Since L (n- (n]- 0) + obtain
2
- 2n
= (1 -11-o22
(n 1)2 1 σ
+
2(n 1)
+ 1- 0²
1
1- 02
1
1
< <nn - 1)2
- +
2(n
1)
+
1 - 2n
1+0
1 10
1 02
(n 1)2 1 - 2(n An-11 1)
+n.
(30)
Ita
1+a
1- The first inequality holds because 0 < 1 2n S 1, while the second inequality follows from the fact that
1-o2
En-1 g21 < From (29) and (30), we have
<
1 11-1
2 n 1 n(1 +1)
1 1
(31)
n ann - 1)
35

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Next, we obtain lower bound of a. For any real have
1 d"
S nc = dl -0) 0) -1 01- (1 (1-(1-10) n
2 0,
1 1-0 σ
which motivates us to define g( c(1 -) σ) - (1-0-))))
- 0th) (1 - (1- - ..))). Then, our objective is to find a value for such that ( 2 0. Now, we analyze the function g(0r) to determine suitable value for c. We have g(1) = 0 and
g'(o) (-) n nn-n n 0" no" - -e+ c+1-- 1
n
n-1
Since -2) 0" + non +1 1-
has the local maximum
n n+1
+1
at n -f 11
1+ e g((o) = by
the following lemma:
x-1
Lemma B.15.
s if
a+1
x-1
Proof.
Let f(x) =
18
1. We first show that f is increasing on > 1. Taking the derivative, we have
x+1
f((x)
log
x
1
I
It x(x + 1)
x2
To show that f'(x) 2 O, we can use the inequality log 2 1 1 for x > 0, which is directly derived from Lemma B.9. Applying this inequality to the term log I-1 we have
f((x)
x
log
x
1
+
1
I + 1
+ 1
s(x
x2
8-1
1
1
+
+
x + 1
x(x
+ 1)
x.a
2
x-1
1
x(x + 1)
x +++1
x²2
Since
2 xxx + 1)
x-1
(1+2)² 22
20
x +
and (1+ 1)2 2 2 holds for all by Bernoulli's inequality, it follows that f((x) 2 0 and f(x) is increasing. Since lim f(x) 1 and / (1x) is continuous x >> we have f(x) S 1.
Therefore, g(o) 2 on [0, 1] and
1- n In n (1+ (1+ !
(32)
1 1-0
For the term 2 2 2n
1 we use the fact that
1 - 2n
(n- 1)2 (n-1 0 2(n 1)
1
1
1 1- =(1-221)
1to + lto
1- 02
1 1-a an 0
1-0) (1 (1- )2n)
(2(n-1)
22(n - 1)
1
=(n- 1)2
1to +
It Ito
1- 02
36

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Since are considering the case [0.8, 1), have Ito J. Also, a2n a) has the local maximum at 2x++
and since 2n-1 is decreasing (the inverse (1 + 1 ) is positive and increasing by Lemma B.8).
2n
2 1
0 2m (1
σ)
1+0
2n
2n
1
2n
2n
256
1125 2n 1
Next, since
(1 d2) (u-
(2(m-1)
2( -1) 1)
1+o (1+o
(1 2n 12(1- -)) +) - n(1 - -2))
- n1
1 oz
2n
(1 - o)²
n1 - 1 Σ
(i - 1)o¹
2=
2 0,
we have
(2
(2(--1)
2( -1)
(1 2n)
+
2
1+0
1- 0²
because 02 0. Therefore,
0 2n
1-
256
1
2
2 (n 1)2
+
(33)
02
1+0
1125 2n +
By (32) and (33), we obtain
1
(nn
1- o
256
-11
(34)
(n
n(n -
1
1125 2n
+
We now derive an upper bound for 3. Since
1 Ua
0
3
2n no - 2(1 n+1
+
1 0²
1 "1
< 1 1+
2n 2(1 - 0th a+1
we need to find a lower bound for the term (1- -1-0
1-0"
I-o We claim that (1 (1-o"t1) 2 20 a)). Since 1 1 o > 0.
this is equivalent to showing that 1-
1-a"
>
20. We can rewrite the inequality as
I-o
1-o
Σ oz
Σ
o²
>
20,
The left-hand side is increasing in a for a E (0, 1). Given that n
> 15, we can verify the inequality holds because
0.8 Σ
Σ
0.8
2 20.
i-n
==
Therefore, we have (1 - 1 2 20(1 σ) as claimed.
37

---

1 Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Substituting this into the inequality for B, obtain
1
1 - 0"
1 1 0
3
2n no -2(1 -0"t1
0
1
1 0²
1
2n 2(1 xn+1)) 1 1 0
++a
1 1-
< 1
(2n - 40(1 - -o)).
(35)
Using the derived bounds for a. 3, and 8, we now establish upper bounds for Ti and T2. Combining (28), (34) and (35), we have
Ti
(n3 - a + max nd)
(n
(n - 1)
2n -
40
(1 (1-
(n-
1-o
256
<
-
1 1 + a
n 1+0
n(n 1)
1+0
1125 2n
+
8log 2
n²+ 2m 11 - 0
40 (1 - o)² (1-o)3
256
2
n
+
+
n(n 1) + σ
n n-1 1+0
1125 (2n +1)
en
8log 2
5 n + 2n (1 0)
40
256 n
2
o)²
n(n 1)
n
1125 n22 + 1)
e
8 8log n
where the last inequality holds because 2 15 implies Similarly, by (27) and (31), have
n=²22-1 (1 6) カ (1 x)² > 0 and
Ita S.
z(n-1)
T2 I n(n - 1)
(a + max 7)
n(n - 1)
oE(U,1]
2
<
n1
1 1
n1 - σ)
e²
5
5
1
(: 11 + 9)
1 9)
<
0
1
+
9
9
n1
22
Now, let
Un(n,o) =
5
n² + 2n
(1 - 0)
40
(1 0)3)
+
256
n n-1
2 1
+
9
n(n 1)
1
1125 (2n +1)
-
8
5
1
U2(n,0)
0 +
1 +
+ e2
9
We first consider U1 (n, o). Note that U1 (n, .x) quadratic function a, which attains its maximum at a
n² =222n-1
80n
Thus, Un (n, has its maximum 0.8 [0.8, 1) because
22 0.8 for all 2 15. Since
80n
Us (1n,,)) < Un (n,
n12 + 2n -1
8
256
1
71
9n(n - 1)
9nn - 1)
1125
(2n
+ 1)
e
8 log 2 n
2
128
8
1
- n2n + 1)
<
+
+
+
5
n
nnn 1)
1125
e
8
log
2
9
n
2(n 1)
38

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
and the last line is decreasing in n, substituting 15 yields
(n S U1 (n, 0.8)
1867
2
1
+
23625
e
8
llgg 2
14
8 log 2
1
15
15
for 2 15 and [0.8, 1). Similarly, since U2 is decreasing in a,
o) S U2(n, 0.8)
+
+
9
e²
10
10
for n 2 10.
Recall that we can verify that
Ti,m, -
m(m - 1) 4
2 m & 14 and
T2(m, 0)
1
5
m(m 1)
for 2 S m S 9 using Proposition B.6.
Therefore, we have
(i 0) 25mSn m(m- - 1)
Ti (m,,0) o)
(i,, 0)
max
max
max
max
25m
m(m - 1)² 155mSn m(m 1)
1
1
2
15
max
2
15
1
1
(: Lemma B.8)
7i
if 2 15 and
1 2
max
1
25 m(m
2
1
1
if2 < n S 14.
Similarly, we have
[2(m, σ) max 25m5n m(m 1)
Te o)
T2(m,
25m59 m(m 1)' 105m5n m(m 1)
max {
(1
1 10
n
( Lemma B.8)
n
39

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
if n 2 10 and
T2(m, σ)
1 2
max Sn m(m - 11
-
1
2
1
s
1
nt
2f f225n5 n 9.
B.3. Proof of Theorem 3.4
Here prove Theorem 3.4, restated below for the sake of readability.
Theorem 3.4. Let A Ao- For an initial point Zo E IR",, let or be the output of RCD after T iterates. Then, except for Lebesgue measure zero set of initial points,
E [|<T]] 1|3]
1 (1 o)2
lim 10000
|2oll
11
11
Proof. We first assume that = ala + (1 - 1 1 Then,
a |1
w (M (MRCD)T(IT) (T)ar
x
z. Do Amin (MBRD)=(I)
because (I) is symmetric.
Now, we observe that spanfI, > is invariant under MRCD. To verify this, we compute M (I) and (B1T(111)) Then, we obtain
MRCD( (f) n 1+ 1 11-00 o)2
(1 2 11
a²
2) 2 (n-
MRCD (11
I+
11
n
n
which confirms that both M (I) and M (117 T) are in span [I, 1,111T} }. Consequently, we can only focus on the 2 x 2 matrix MA which represents the restriction of MR to span [1 where
n
1 + (1 o)²
(1 - (n - 2)]
MA
2 - 2)
That is, if
[a]
MA
1/
then .BRC (aI b111) = d'I 111T.
Now, define or and 3r as
[T 3T
[
= MT
0
Then,
Amio ((MRCD)T(I))
Amin I 11
orr
if Br
aT + nB3r
if pr < 0.
40

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Since the entries of MA are all non-negative, have 8T 2 0 for all 7 2 0. Therefore, have
Amin ( or-
When 2, we have
1+ (1-0)
0 0
MA =
2
σ²
and
[+(1-0)2 T
M
2
o²
[1(1-00²2
T-1
Therefore, or (=+(1-02) T
and we obtain
[|xTT|| 1/7
E
1/T
aT
|000|
1 o1
2
This establishes the result for the case
We now turn to the general case where 3. Let v be the dominant cigenvector (i.e., the eigenvector corresponding the eigenvalue with the largest magnitude) of MA. We will show that [1 0] not orthogonal to v. Assume for contradiction
is orthogonal to v. Then, v must be the form |0 c) for some nonzero scalar c. Since is an eigenvector of M A. MA must also multiple of 0 1] This implies that (Ma)12 = However, implies o 1. In this case,
that [1 0] T
MA = 1
0
and MA (1- ]) Nevertheless, is not the the eigenvalue of MA with the largest absolute value because the eigenvalues of MA are 1 1 and - Therefore, [1 0] is not orthogonal to v. This implies that
lim of T4000
1/T p(MA).
Now, let p(A) be the characteristic polynomial of MA, which is defined as det(AI MA). Since MA E R2x we have
p(A) X² tr(MA) + det(MA)
= x2 ((MA)n + (MA)22) + ((MA) - (MA)))(M))))..
Furthermore, since tr(MA) = (nn 1)02 2 20 + 2 0, det(MA) = =000 1)(n - -2) 2 0, p(A) does not have a negative root. Thus,
o)2
1
= p((MM)))))
71
(MA) ((MA) + (MA))) + ((MAI) (MA)))(MA))))
= (Ma)a)
0,
because the entries of MA are all non-negative.

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Therefore, have
1 (1-o)² o) S (MM)).
n
n
Next, consider A = d + (1 -1-1000 o x } for an integer & with 2 S & S Since 1 implies A In. which has already been considered, we will assume that o E 1).
We will denote aI + (1 - (1-o)1 as Ag, and the set of of block-diagone matrices consisting of a k: x & block and an (n (m= x (n - k) block as Du,n-k- Recall that D closed under scalar multiplication, matrix multiplication, addition, transposition, and inversion. Thus, if X E D then MRD (X) D because TRCD I E,A E Dknnk- Therefore, we will now compute the (1, 1)-block and (2, 2)-block of MMA (X) when X E DR.n-k-
To analyze the 11,1)-block of MMCD (X); we consider two cases for the index 1 S S k and k Sis n. 1 S i S k. the (1, 1)-block of TRCDT XTRC is (I Ax) III At,, where E,, denotes the t matrix XT is X
A,i e.e," If k + < S since the (1, (1.locklock of E, is zero, the (1, 1)-block of A. A,
Therefore, the (1, 10-kkkcokkkkk of M (X) is
k n I EI-EAAA AR) Xn AR +
I
X11 = (KMMADD (X.) + (n k))
1=++1
We denote the matrix operator X + (R (X) + (n - x) on Rk as MA. Note that span Ia. 1,1]] is invariant under MA. and the matrix representation of MA MAlspan(T,111) is
MA. + (1- 12
1z:
n
where
1+ 11 k
o)²
(1 (1 2) 0² - 2)
MA
0²
Let us now consider the (2, 2)-block of MRCD((X) Given that the (2, block of A In- the (2, 2l-block of can be computed as X22 when < ls and (In-k -i X22 (In-k kink.nkk) when k + S S n.
Therefore, if we denote the diagonal part of X D22, the (1, 1) block of MRCD(XX (X) is
k
X +
(In-k- Ei X22 km
= (kx22 (n 2--2 2) + Dm2)
1=1
k=++1
-(1
= 1
2
1
Xx2 Dr2
n
n
because ERet E and Em E. E. X Ei k.nk = Dr2-
From the above, we have
(MRCD)T(IA) (II)
Ok
On-kak
(1 (1- 2) I
Now, we define or and 3r
or
MI
[
42

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
We now proceed to examine the limit
z (TM 1/T
lim 7-
To æo
To this end, [yo zo] zo, where yo E Th and 2g E mRn Since the set (mo E R yo 00.} has measure zero in I" we assume that yo + Then,
To ( = yo (aT + 11 yyo + (1 (1-
|| 12
2 ar|1y0l12 (1- || |
T
(: Br 2 0)
By the same argument in the case when & = n,, we can show that
lim of 7-000
1/T
= p
k
MA. +
-1- k
12
71
71
(1 o)2
k
+
1
n
h
T2
1
(1 o)²
n
n
Since a # 1 by the assumption, we have
(1
(1- - 1
T
lim
lim
T
OT
T-x
Orr
1/T
and
1/r
or arl1yol 1| + (1 2)²² ||
1/2
lim T-c0
lim
Zi 20
T4000
| 2 | 1
|1/0112
(1
2)²
ž 12
1/T
1/T
lim QT T-200
+
1 12 + | 12
or
||
2
+
||
lim 0q T-+x0
1/T
1 + (1 -1-00 0)2
2 1
43

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
C. Computational Verification of Inequalities Deferred from Appendix B
In this section, we provide the computer-assisted verification the inequalities presented Appendix B, which were stated be verifiable using Sturm's 's theorem (Proposition B.6). Recall that for a polynomial p. if p(z) * on (a, b) and p(a) then p(b) 0; similarly, if p(6) O, then p(a) 2 0. Therefore, to verify that p(z) on an interval, it suffices show that p(x) has real roots in the interval using Proposition B.6 and then check that p(x) is positive at of the endpoints.
The specific cases that require verification using Proposition B.6 are as follows:
T((ma) For i = 2, mmm-11
< (1 - =)) 2n ) for all integers m and n where 2 S m S n S 6 and E (0,0.6).
(m,.)) < 1 m(m-1)
4 for all integers m where $ m S 10 and a E [0.6, 0.8].
Ti (m,.) m(m-1) S 1 for all integers m where S m S 14 and α E [0.8, 1). T2(m,0) m(m-1)
4 for all integers where < 10 and E [0.6, 1).
The following SymPy code can be used to verify these inequalities. Since the coefficients are all rational numbers, the computations are exact and free from floating-point errors.
import sympy as sp
def sturm sturm_sequence (f, x)
f0 sp. ex.and fi (f (x)
sturm_segp [50, f1]
while sturn_scql-1] != 0:
f_prev sturm_seq[-2)
f_curr sturm_seq [-1]
9, = sp. doo.div(f_rrree f_curr)
sturm_aeq, appu___)
return sturn_aeq
def sign_variations (seq)
_og_nonzero = Ival for val in seq if val != 0] if not seq_nonzero;
return
variations -
for i in range (len seeg_nonzero) - 1):
if (seq_nonzero > and seq seg_nonzero(i+1] < 0) or
(seq_nonzero [i] and seq_nonzero(i+] 0):
variations
return variations
def count_real_roott (f, b, x):
seq storm_sequancelie (f,
vals_a [poly. (x, a) for poly in seq]
bals Ipoly subs (x, b) for poly in seql return sign_variate variations (vals_ a) sign variations (vals. b)
def tau (n, 8):
= n - (n 1) +
alpha =
for i in range (n): alpha
(1
x*2
sp. Mp.Maxxix. zeros (n, n)
for i in range (1, , + 1):
for in range (1,
1):
if iikji j:
S(i - 1, 11 -1 8) * S** (1 1)
44

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
else: C[i - 1, J 11 = (1 - (S** (1 }) s** (1 1))
beta (C +]*+2 for in range (n) (n) for j in range (n))
gamma sum L s+.i for in range (n)) ++2
delta aum (s**n - -*vi) x*2 for in range (1, n 1))
t: ap. Rat.aaionlll (1, (n 1))* (beta delta) \
ap.Rational
(n *
gamma)
t2 sp Rp. n- in + (aapha gamma) (beta delta))
return :1, t2
def p [n, 8):
pi_coeffs []
p2 co__ceffs []
for k in range(7):
if == 0:
pl_coeffs. append (n**2
p2 p2_coeffs. append (n++2 3+n + 2)
else:
if $ 2 1:
pl_coeffa append x 2*n**2 3)
p2_coeffs append (-2*n**2 6*n 4)
else:
p1 coeffs..ppentt (- (n+1) *k 2+ 2+n 2)
p2 apped (2+k 2*n**2 6+n 2)
pi sum [coeff s++i for 1, coeff enumerate (pl_coeffs) ])
p2 sum [coeff s++i for 1, coeff in enumerate (p2_coeffs) return pl, p2
sp.symbols ('s')
tau_k = (
for k in zange (2, 15); tau_k[k] - tau (k, 8)
for in range (2, 7):
red = (1 - sp. Ratioaal (1, n) x* (2xB) Enequality_verifaal for in range (2, m+1):
= True
d1
tau_k(k] [0]
d2 red tau_k[k] [1]
toots_1 = count_real_roots (d1, Rp.Ralional (0), sp. Ratinal (1), s)
roots_2 count_real_roots (d2, sp.Rational (0), Rational (1),
dl_end dl.subs (s, sp. Ratiionalll]] (1))
d2__nd d2.subs (s, sp. Rational (1))
if not all [[roots]] == 0, roots_2 = 0, dl end > 0, d2_ > 0])
Lnequality_veritied. = False
assert r 0, roots_2 0, al 0, d2 end 01), \ f"Error: Inequality verification failed for n (n), k (k)."
if inequality
print (E"Case 1, (n): All inequalities verified.") ")
else:
print (E"Case 1, n :n): Inequality verification failed for some k.")
for in range (2, 11);
ihs sp Rot.Rtional (1, m= (m-1)) tau [m] [0]
rhs Ratiniionall (1, 4)
di ff = rha 1hs
di ff_endd - diff.subs (s, sp. RatiRatiaa (4, 5
roots count_real roots
roots (diit, sp. sp. Rationaionnnaaaa (3, 5), RatiRai (4, s)
assert roots and diff end 0,
45

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
F"Error: Inequality verification failed for Case 2, = {m) print (f"Case 2, m {m): Inequality verificd.")
for n zange (2, 1 ihs ap. apt.naaioaa1 (1, m- (m-1)) tau_k[m) [0]
rhs = Ratonaio (1, 4)
diff = rhs 1hs
diff end diff.sube (s, (p.Rationaa(1)) (1))
roots count_real ctt___ere_rorrsst_eeeeeeoeoo
roots (chs (rhs lhs, sp Ep.Rational (4, 5), sp. Ratiioal (1), s)
assert roots == 0 and diff_end > 0, \
f"Error: Inequality verification failed for Case 3, - {m)
print (f"Case 3, m {m): Inequality verified.")
for
m zange (2, 11):
ihs = sp. RrtRRationnl (1, m- (m-1)) tau_k[m] [1]
rhs sp. Rational (1, 4)
diff = rhs 1hs
diff_end diff. subs (s, sp. Ratiaaii (1))
roots = count_real_ roots
1hs, sp. sp.Rational (3, 5), sp. Ra.Raiional (1), s)
assert roots =- 0 and diff_end > 0, \
f"Error: Inequality verification failed for Case 4, (m)."
print (f"Case
{m]: Inequality ity verified.")
We also provide an example demonstrating the computation involved in applying Proposition B.6 to verify the inequality (m,.a) on (0.6, 1), when m = 3. Since
To Ts σ)
6
20
2
m(m 1)
9
9
18
36
Sturm sequence
20
0+
o²
(o(
+
+
11
9
9
9
18
36
Pa(a) =
+
54
27
36
5
10
4
4
Pi(a)
161a
488
Ps(a) 484
3
9
121
2g
20
7a
65
10021099
P2(0)
+
Po(a)
81
81
27
81
324
311052
Pa(o) 3
2
15g
7
Pr(a) 0.
4
2
Therefore, we have
134329
1
(0.6))
Po(1) = 4'
562500
1142
P1 (0.6))
P1(1) O,
28125'
47993
(0(6))) 202500'
P2(1) 4'
193
(o.66) 500*
Ps(1) = 4'
191
5
(0.6) 900
(1 12
Ps 9277
1791
P5(1) 484
2420'
10021099
10021099
(0(66))
Po(1)
311052
311052
(0.6)) O,
P7(1) 0.
46

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
We examine the number of variations in sign for each sequence. Recall that for sequence e (c1, 02r.0...... y Cm of real numbers, the number of variations in sign is defined as the number of sign changes in the subsequence obtained by removing any zeros from
0). For the sequence evaluated at 0 = 0.6, we observe the signs are given by (+++, -.. +, -,, Removing the zero, the signs of the subsequence are (+, -, +, +, -, -) Thus, there are three variations in sign.
Similarly, for the sequence evaluated at a = 1, we observe the signs are (+, 0, -, ,, ,) 0). Removing the zeros, the signs of the subsequence are (+, - , +, -) This also has three variations in sign.
Applying Proposition B.6, the number of distinct real roots of po( in the interval (0.6, 1) is given by Va.6 - V1 = 3- 0. where V. denotes the number of variations in sign of the sequence (po(a), pi (()....,P((()) Thus, we conclude that po (o)
has no roots in the interval (0.6, 1).
47

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
D. Comparison with Previous Work
In this section, we provide detailed comparison of previous work by Lee Wright (2019), continuing from the discussion the end of Section Recall that Lee & Wright (2019) established that, for quadratic functions with iettuuttttooiivvvriinn Hessians, the epoch-wise contraction ratio of RPCD of order
(
(1=) 71
1 2x
20 +0
+ (0
(36)
n
when n 2 10 and a E (0,0.4.. In comparison, Theorem 3.3 provides an upper bound of max {11 _0 (1 1)²²
2n x)
which simplifies to (1 (1)
2n the region a E (0,0.4)
As noted earlier, we obtain
(1 -1- =) n = 1 20
o² + 20 0 (00).
-
n
This expansion initially appears to have extra terms compared to Equation (36). However, a closer examination of our proof methodology reveals more refined upper bound.
We exploit the inequality p(M) S || where M is the iteration matrix. In our analysis, we define the iteration matrix as
n3 - a nd 180-9 7 MA = n(n 1) a - 3
1
where a. 3, y, and are polynomials in a (see (17) in Appendix B for their explicit definitions).
Lemma B.3 establishes that all entries of MA are non- non-negative. Consequently, |Mall simplifies to the maximum of the sums of the first and second rows of A. both of which are polynomials in a. We define Ti and T2 as the sum of the first and second rows of n23 no respectively.
a B
Importantly, our proof explicitly determines the coefficients of the polynomials Ti and T3 in terms of n. Furthermore, (21) and (23) establish that the even-degree Taylor approximations of Tj and T3 serve as upper bounds. Specifically, if we consider the 4-th order Taylor approximations of Ti and T2, have
T
1 n
2n
-2 2(n² n 11)
1
2
0
0²
(nn
1)
n1
n(n 1 1)
T2
2
2(n² 3n + 1) 0² 2
2 n
3n 3) 2(n²
<
2
0 nnn 1) 0+
03
04.
nnn - 1)
n
n(n-1) -11 1)
Ti Remarkably, the upper bound for n(n-1) precisely matches the contraction ratio given in Equation (36). While the upper bound for nin-1j does not directly match this expression, we have
T2
2
4
20
+
+
20²
0² 0 (0²)
nn - 1)
n
n
n
< 20
o
+ 20 +
+ 0 (a²)
n
n
where the last inequality follows from the fact that 2 - 60 + 2 2 0. Therefore, we conclude that
P(MA) S |MMll 1o0
T;
-max
==1,2 n(n - 1)
20
(02)
-1 - 2a
+ 20 +
+ (o²).
48

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
E. Further Discussions: RPCD on General Quadratics
Here we continue from and elaborate on our discussions in Section 4.3.
E.1. Partially Invariant Hessians.
Let us revisit the x 4 unit-diagonal matrix
1
1
b
b
A
(37)
b
1
b
a
1
As stated in Section 4.3, we can observe that there are only 4 possible cases of matrices PT AP:
1
1
a
b
b
b
1
b
b
a
1
b
b
b
b
1
b b
b
a
1
b
b
b
b
a
b
1 b
a
b
1
b
1
a
a a
1
one for each i [4] with unit diagonals, a in the non-diagonal entries i-th row and column, and for the rest the entries. We can also think of similar formulation where an n unit-diagonal matrix with the non-diagonal elements of the first row and column filled with o's and the rest of the elements filled with b's:
1 al (1 (1- b)- + 611
a1
A
(38)
Note that the upper diagonal block is scalar, the lower diagonal block is (n - 1) (n 1), permutation- invariann matrix, and the off off-oiagonal blocks are constant-filled (n diddieensional vectors.
We define the bases using the following block matrices with the dimensions:
0 V2
= 0 1
0 I
Vi = 0
V =
Va = 11
Lemma E.1. If A is defined as in (38), then MRPCD is closed S' = span V1, V2, V3, V4
Proof. First, we observe that we can define
Cp=I- P AP tril(p AP) AP
so that RPPCD A.p
PC Suppose we have any X E S'. Then write
(X) RRFC (X) = E PPPP"XPCPPP. M
Now, think of partitioning the set of all possible permutations into sets, denoted by II, for i [n]], each containing the set of all permutations such that p(i) 1. For any i, each permutation E TT; can be uniquely decomposed into two parts:
p = p' o P(1))
where P(1s) is a permutation that swaps and and is permutation that satisfies y(1) For each E [n] have (n 1)! different choices of p' and hence well. Let the same analogy between permutations p and permutation matrices P preserving the subscripts. Using this decomposition, for each fixed i [n]] we have
Cp = I tr AP) -P AP
I - PPT T PTT AP'P TT P'T AP'P
(10)
I - T
*The minimal example would be a x version with two a' one helow the diagonal, we choose 4 for clearer illustration.
49

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
where we use our construction of A E S' such that A is P'iinvariant. Thus, if we fix then Cp is also fixed (constant) matrix, allowing us use the notation Cp C; instead. Considering the expectation over πΙ for fixed have
Bpen: PCPPT XPCpP pell,
P' CT P P 1 CPPP)) (1)) P
pell
PP P(O XP (IO (1)) P"T PT.
where we also the fact that X E S' P'-invariant. Therefore conclude that the lower diagonal block is permotation-invariiant, and (ii) also observe that the off-diagonal block parts also filled with constants. (This is because the entries in (1.2)..... (1, of P(a)) C ( CiP(1a) will be averaged after taking expectations P', and the same holds for entries in (2,1),..., (n, 1). Moreover, the averaged values must be identical because the matrix P(1)) C P(1o) X (1a)C (1i) is symmetric.)
(i) Lemma B.2 over the permutations P' to
Therefore we can conclude that for all i [n].
Eeen, [PCPP] XPCpP"] Eee
C. Pla C.P P'T E ES.
Taking one final average over [n]. we have shown that
MADD (x) = [PPPP] XPCpP"] ES'
as desired.
As we have discussed in Section 4.3, we can see that Lemma E.1 allows us to reduce the problem into finding p(M (s+). which can be written as matrix using the subspace S' as the basis. Note that the remaining steps will require relatively complicated analysis of an asymmetric 4 4 matrix with two controllable variables a, b E [0, 1]. compared to Theorem 3.3 where use 2 matrix with only variable
More generally, it is intuitive that a similar dimension-reduetion argument can also apply to different block structures. For example, we can think of the following x 4 matrix:
1
A
(39)
1 b
b
1
For this case, we instead have = 2:2 types of matrices PT AP. Similar arguments are also always possible for various and various dimensions of blocks. In general cases, however, it is much more likely that we cannot find such nice block structure that reduces permutation variance and thus a small-dimensional subspace S on which we can express MRPCD s as smaller matrix.
E.2. General Hessians: Matrix AM-GM Inequality
Continuing from our discussion the second paragraph Section 4.3, the only results we are aware of that consider RPCD for general quadratics are those by Sun al. (2020). In particular, their objective was show that
p (ETTAPCD <
This is direct corollary of weak version of the well-known matrix AM-GM inequality (Recht & Re, 2012; Lai & Lim, 2020; De Sa, 2020; Yun et al., 2021). To elaborate, Sun et al. (2020) (Claim 4.1) observe that:
A } T.RPCD - A.p
A A
Zp(n) Zp(1)>
(40)
where Z, = - V.aa - is projection matrix, with being the i-th column of A!, Then they show for the expectation:
ppm) ... Zo(1) 1 Σ Z:
A
-
1=1
50

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
which is called weak because the RHS is missing the n-th exponent from the original matrix AM-GM,
1 n!
Σ p())
2p(1= =
n n
Z
To obtain a proper comparison with the RCD lower bound results Theorem 3.1, it suffices to show an upper bound of
p( p(MA = pE T
R
S max (1-2)
= n
2n
(1-
which is not only stronger than the weak AM-GM, considering that we have an order n exponent added to the upper bound, also much more difficult in many aspects.
Analyzing the upper bounds of quantities derived from sum of Kronecker power of matrices is presumably the harder direction than the opposite (we typically use the sum of squares as upper bound).
Even for the case of two matrices A and B, the relationship between the spectrum of A + B and each of the matrices A and B (beyond Weyl's inequality (Weyl, 1912)) is highly nontrivial (Knutson & Tao, 2000). In our case, we have a sum n! matrices, and a fine spectral analysis is extremely hard.
One of the few possible solutions avoid computing the Kronecker powers could to use the following lemma.
Lemma E.2. We have
p p(MBCCD) S (A
(41)
Proof. The Russo-Dye theorem (Russo & Dye (1966), Theorem 2.3.7 of Bhatia (2007)) states that if M is a positive linear map, then we have |||M||| = [I) where ||| is the operator norm induced by the matrix operator norm ||-|]. For our case, we can easily check that MMRPCD is positive as it outputs the expectation of positive semi-definite matrices. Moreover, we have defined a similar matrix operator earlier in Section 2:
M MRRCD (X) A MRRCD (AAA
which is also positive linear map (with symmetric matrix form). Using the Russo-Dye theorem MRRCD have |
p(M p( MRPEDD s
M (1) = A AMRRDD (A
which completes the proof.
One caveat of the approach is that the RHS of (41) gets too large and exceeds the RCD lower bound for some values of (g. after gets sufficiently large, i.e. (41) is too loose for this case (as shown in Figure 4 in Section 4). The same
bound still seems tight enough for the region E (0, 1.. where we also have (1 y)nn 2 (1 1j" and hence the upper bound simply reduces to (1 g)2n.
From (40), we can observe the following:
RPCD (A)
AA)
E. (I
A P
AE) A At)
1
p(n)) -.(()) ((Z)))(((())) Zp(z)).
Then by (41), suffices to show
2n
n! Σ 2 p(n) T (Zp(n) Zp(u) sp
1
Zi
m
to prove Conjecture 4.1 on (0, }. and we leave the proof/disproof for future work.
'A linear map R=xa - R positive if maps positive semi-definite matrices into positive semi-definite matrices.
51

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
F. Details on Experiments
F.I. Algorithmic Search.
Here we provide detailed information about the algorithmic search used to find the worst-case instances for RPCD. Recall that we use the following framework to search for the worst-case example among the space of all (unit-diagonal) quadraties.
Step Start with a (randomly initialized) lower triangular matrix E IRax" with nonzero diagonals.
Step 2. Construct unit-diagonal, positive semi-definite matrix by computing X X and set unit diagonals by
Z Dy YDD" where Dy is the diagonal part of Y.
Step 3. Construct matrix A with a Amiu (A) by
Z I,
where / Amin (Z). Note that A is also unit-diagonal and positive semi-definite.
Step 4. Construct an objective function that takes input X to compute the value of p ((MBRCD) and run a scipy optimizer to maximize the objective.
Experiment Settings. In our search for worst-case matrices, we explored the performance of our algorithm for dimensions n E (3,4,5, 5) and for minimum eigenvalue a E {0.1,.... 0..9) (with increments of 0.1).
Initialization. To initialize the lower-triangulat matrix X, we generated a vector of length "(++1) with elements drawn from a standard normal distribution and then used this vector to create an n X n lower- triangular matrix. We used 10 random initial vectors for n = 3, 4 and 2 vectors for n = 5, 6. The reduced number of initializations for n = 5 and n = 6 was due to the computational complexity of calculating the matrix representation of M and its spectral radius, which is O( n!).
1 Z 1-p where μ Amin ( ()). This construction ensures that is unit-diagonal matrix and that its eigenvalues are of the form 1- X + e_ where À is eigenvalue of Z. Since Z is unit-diagonal positive semi-definite matrix, its minimum eigenvalue lies in [o, 1). and thus 1-a 2 0. This guarantees that T-
Construction of A. We computed
the minimum eigenvalue of A is + T- =
Optimization. We used the BFGS method in the scipy optimizee mww.mmii....immiia..mmmm...m minimimiiii function with default parameters the optimization algorithm to minimize the function p(MRRRDD) ). To calculate the spectral radius of MRRCD we utilized its matrix representation, which is given by E ( (TRRDD) Here, TRPCD is defined in Equation (5).
Results. We present a few examples of the optimized matrices obtained through Algorithmic Search. Specifically, for each combination of E [3, 5, 6} with a (0.3.0.7) 0.7). we selected the matrix that achieved the largest p(D))PD) among the trials. These examples demonstrate that the optimization process converges to matrices in A, with various sign flips. Here, An,o represents the matrix o I, + (1 1)1,1, 1, E API. Note that An @ vv"
E A. when {=1]".
An,o 3 vo
A,
1]
A F R 1.2 10-10
for n 3, a 0.3
An, 3 va
A,
-1 -1] [1
F = 8.7 10
for n 3, σ 0.7
An,o 3 ww
+
A,
-1
A
F R 2.7 10-10
for n 4, a 0.3
An,o 3 vv
A,
-1 -1
A F = 2.5 10-10
for n
4, σ 0.7
An,o 3 vv
T
A, t
-1 1 -1
A F ~ 1.1 10
for n
5, σ 0.3
An,o 3 vo
-1 -1 A,
A F 9.3 10-10
for n 5, σ 0.7
An,o @ vv
A,
-1 -1]
| F 1.9 10
for d 0.3
An 3 vv T
A,
-1 1 -1 1]
| F 9.4 1
for n
0.7
Furthermore, we empirically observed that for any optimized matrix A, holds that ((MRPCD) S max AEA, pl ((MRRCD)
52

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
The following Python code implements Algorithmic Search, which also empirically validates that p(M)BCCD maxAsA, P(MA)) for all optimized Á.
A
import numpy np from scipy ceipy.optimize import minimize
from itertools import permutations from minaly import
from math import factorial
def rho (M)
return max (abs (eig (M) [0]))
def unit diag (M)
tiag_sqrt sqrt (np. diag (M)
return / (diag_sqrt siag_sqrtl:: 1; Nonel)
def mat_rep_rpcdd)):
shapee
result np. zeros (n-n, non))
for perm in 1ist (permutations arange )
p np.eye (n) [mp. (perm)
Ap I.AAAF
Gp ap. (xpr
Exp PēGpeF.T
temp (np. -inv (GXp)
result +- kron (temp, temp)
return result/factorial (n)
def rped pi (n, s):
L = n (a 1)
if != 1.:
alpha
- 2 x L (1 S**n) / (1 5) L**2 (1 (2+n)) / (1 S**2)
beta ((1 - 8) / (1 8)1 (2 + - g** (2+n)
- (1 - s* +1)
(1-s)
(1 - 8]
8**2
(2)) (1--))2))
gamma = (1 1/(1 -3) (n -1-1+1/00 8)) s**n) **2
delta
gex
1)
s**n) (1 8)
s**2 (1 Sxx nl) (1 8x*2)
else:
alpha = 0.
beta = 0.
gamma
delta 0.
M ap array (1 In*beta alpha, nxdelta ganmal,
(alpha beta, gamma deltal]) (n* (n-1))
return rho
def set set_min_eigval (A, 8):
n = A. shape [0] mu min (eigvals )A))
(1-s) (1-mu)
b (s (s-mu) (1-mu)
B a*A + byep.eye
return
def X_to_A (X, n, 8):
if (X) !- int (nx (n+1) :2):
raise ValueError ("X must have length (n+1) /2.")
L np.zeros (nn m)) astyye astype (float)
idx 0
for i (n)
for j in rango (1 + 1): L[i, il = [[ixx] idx += 1
53

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Y b.TeL.
2 = unit_diag (Y)
set_min_oigvalee (2, s)
return
#*## Optimization ####
def objective (x, A to (X, n, s)
return -ho (mat rep (ep_rppd(()) )
n_values [3, 4, 5, 6] s_values np. aip.pineacc (C.1, 0.9,
sim num list = [10, 10, 2, 2]
results =
Compute max rho (M A (RCD), for in siggma tho_maxxdict = (} for n in range (n_values):
for in s_values:
temp []
for & (2, n+1):
Aks = sye. (k) (1-s) +np, ones ( (k, k)
temp. azh (mattrep. rped ))
cho_max_dict (n, s)] max (temp)
for 1, n in coueerate
for a in s_values:
sim_num = sim_nuum [i__n_m__st[i]
for sim in range (sim_num)
values []
i_itt np. random. randn (int (n* (n+1) )2))
result minimize (objective, Xniit, args= (n, s), method=/BFGS')
X result.x
res_A X_to_A(X, n,
results. reaults.append app.adpppnn" (i'n': n, 's': 8, 'sim': simtl, IA': res_A})
assert rho (mat rep xped (res A)) <= rho max dict I (n, s) 1, 3"Counterexample"
F.2. RCD RPCD.
Problem Settings. We considered four types of convex and smooth optimization problems in n-dimensional space. The first three share a common structure of the form
f(x) T Ax + a....... LSS((QQ:)
where LSE is the log-sum-exp function, i.e., LSE(a)...... ...., = log(e") + + e.n). These problems differ in the specific construction of A and the presence of the LSE term:
(i) Quadratic functions with intenuttationinvaiiinn Hessians: A = aI, + (1 (1) with E (0, 1] and = 0.
(ii General quadratic functions with positive definite Hessians: A randomly generated with unit diagonals and (0, 1), and 0.
Amin (A)
(iii) General quadratic functions with positive definite Hessians and a scaled LSE term: we used the same A as in (ii)
with an additional term a LSE( where Q is randomly generated orthogonal matrix.
We further consider logistic regression problem with ridge regularization.
54

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
(iv) fg-regularized logistic regression: the objective is
min Σ 2=1
log(1 + exp(-b;a, æ)) + ||011
where each a, E R" is drawn from (O,,..) We sample ground truth vector Enve NO0 In), set b; sign(a, Fune); and flip each 4y independently with probability 0.1. This setup follows Nutini et al. (2015).
Matrix Generation. For (ii) and (iii), the matrix A was constructed by first generating entries drawn from the standard normal distribution, followed by Steps 2-3 of Algorithmic Search detailed in Appendix F.I. This procedure ensures that the generated A is unit-diagonal and has a minimum eigenvalue o. The orthogonal matrix Q in the LSE term was generated by applying QR decomposition to random matrix with entries drawn from the standard normal distribution.
random matrix X with
Initialization. For each parameter setting in problems (i)- (i.e., each combination of n, d, a, or A), we sampled 10 initial points from the standard normal distribution. For each initial point, both RCD and RPCD were run 10 times, resulting in 100 runs per setting.
Parameter Settings. We performed experiments for dimension n E (25.50} and minimum eigenvalue a E {0.1.... 0.9} (with increments of 0.1). For (iii), we considered the scaling factor a E {0.55, 2.0}. For each algorithm execution, we ran 200 iterations when n = 25 and 300 iterations when n = 50. For (iv), we set n = m = 100, À E (0.0001, 0.001, 0.1, 1.0), and ran 600 iterations.
Implementation Details. For the implementation RCD and RPCD, we computed the arg min for the objective function at each coordinate, as described in Algorithm 1. For (i) and (ii), the update rule can be computed in closed form:
1
E++1
24
E,, Azi
ai,i,
This update rule is derived from the CD update formula for quadratic objectives, as remarked in Section 2.2. For (iii) and (iv), we used scipy. opt imi ze. www.miieesscaate with default parameters to compute the coordinate- wise updates.
Mcasurement. To evaluate the convergence, we measured Im [===="|| as our metric. This metric is motivated by Theorems [00==" =="]
3.1 and 3.3, which provide convergence bounds in terms of the norm of the iterates. For (i) and (ii), the optimal solution is known to be x= = O, simplifying the metric to || in scipy- . opt ietiiiiiieie. mi n inmimizi ze with custom parameters (gtol=1e-12, maxiter=10000) to ensure more accurate approximate optimal solution xx before running the RCD and RPCD algorithms.
For (iii) and (iv), we used the BFGS method implemented [
Results. Figures 5-15 illustrate the convergence behavior of RCD and RPCD, Each algorithm was executed 100 times (10 random initial points and 10 runs per initial point) for each combination of o). The plots depict the ratio log scale. In the plots, solid lines represent the average of the convergence values over all trials each iteration, and shaded regions indicate the min-max range of the convergence values across all trials at each iteration. The results demonstrate that RPCD consistently converges faster than RCD. For small values of (e.g., = 0.1), the performance of RCD and RPCD is similar in (i), with RPCD) showing only slight speed advantage. However, for the same small the performance gap between RCD and RPCD becomes noticeably larger in (ii). This supports Conjecture 4.1 that RPCD is faster than RCD for general quadratic functions and provides additional evidence that (i) represents a worst-case instance for RPCD.
|<a==="|
|| [|
55

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RCD vs NPCD, on n 25
RCD vs RPCD. Pl, om n
vs RPCD, Pl, or n
RCD
R2D
RCD
IPCD
RPCD
RCCD
101
107-
3x 10
-0
75
125
125
175
200
125
175
200
Derations
Baralion
Daral
RCD us RPCD, Pl, o= n 25
RCD vs RPCD, PI, o= 0.5. ==
RCD vs RPCD, Pl, o= 0.6 n=
RCD
RPCD
10a
RCD
RFED
10a
RCD
RXCD
10
10
10-1
75
125
125
175
125
175
Berations
Baraloons
Been
RCD vs RPCD. Pl, a 0.7, 25
RCD vs RPCD, PI, am 0.8. 25
RCD vs RPCD. Pl, 0.9,
100
10:1
10-2
10-3
10-1
10-1
RCD RPCD
IKD RPCD
RCD RPCD
75
175
125
175
Itarations
Earaboons
Figure 5. RCD RPCD, permutationninnarre quadratic functions. A= - 25, E (0.1. 0.9}. The y-axis is log scale.
56

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RCD vs NPCD, on 0.1.
vs RPCD. Pl, al. 0
vs RPCD, Pl, orm n
RCD
20
RCCD
105
10x
107
3x 10
RDD
RCD RPED
3PDD
300
300
Berations
Baralions
Diral
RCD vs RPCD, o n. 50
RCD vs RPCD, PI, om =
RCD vs RPCD, Pl, o= 0.6 n
1.0-
RCD
RPCD
10a
RCD
RFED
107
RCD
RXCD
10:
10:1
10a2
Derations
Baraloons
RCD vs RPCD. Pl, a 0.7, n. 50
RCD vs RPCD, PI, am 0.0.... 0.8. 50
RCD vs RPCD. Pl, or 0.9,
RCD
10a
SPCD
10-2
10
10a2
10-1
IKD RPCD
RCD RPCD
Itarations
Earabions
Figure 6. RCD RPCD, peermutation-invariann quadratic functions. A A= (1 log scale.
1] (1-o)11 50, E (0.1. 0.9}. The y-axis is
57

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
vs RPCD, Quad. d 0.1,n
Quad, 0Z, n 25
Quad. d- n
RCD
10a
RCD RPCD
RCD RCCD
IPCD
10
75
125
150
25
125
175
200
125
175
200
Itaratians
kerations
Ite htaationn
vs RPCD, Quad,
25
Quad., 0.S, n 25
Quad,, 0.6,
RCD SPCD
RCD
RPCD
10
1012
10-2
10
10
10-4
10-1
10-1
10.1
RCD RPCD
75
125
125
175
125
175
Itarations
Eoration
vs RPCD, Quad, a- 0.7, 25
vs RPCD, Quad., 25
RPCD, Quad., 0.9,
10a
10a
10a
10-2.
10
10-3
10
10+4
10-1
10
RCD RPCD
10-7
RCD RPCD
10:4.
RCD RFCD
10-4
25
75
125 175
25
75
125
175
200
100
125
175
200
Itarations
Earations
Figure 7. RCD vs RPCD, quadratic functions with unit-diagonal Hessians. A is unit- unit-diagonal and Amin (A) (0.1....,0.9) The y-axis log scale.
25,
58

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
vs RPCD, Quad. d= -
Quad, 50
RPCD, Quad., d- 0.0.33
109
RCD
10r
RCD
RCD RPCD
IPCD
RPCD
10-4
14-
300
300
Itarations
Rerations
Ite 00
vs RPCD, Quad,
RPCD, Quad.,
RPCD, Quad,,
RCD
10a
RPCD
10-4
10
10-7
10
RCD
RCD
10a2
RPCD
RPCD
Itarations
Eoraboos
vs RPCD, Quad, a- 0.7, 50
RPCD, Quad.,
RPCD, Quad., 0.9,
100
10a
10a
10
10'3
10:2
10-4
10
10
1.0
10-1
10
RCD
RCD RPCD
RCD RFCD
RPCD
100
100
250
150
300
Itarations
Earations
barat.ona
Figure 8. RCD vs RPCD, quadratic functions with unit-diagonal Hessians. A is unit- unit-diagonal and Amin Amin(A) = 50, 0 0.9). The y-axis in log scale.
59

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RPCD, LSE, d 0.1, 0.5,
d a
RPCD, d 0.3, 0.5,
RCD
10r
R2D RPCD
10*
IPCD
10
RCD RPCD
125
375
25
125
175
175
Itaratians
RPCD, a=
RPCD,
d' a n
APCD,
a
10a
RPCD
10:2
10-2
10a0
RCD XPCD
RCD
10-4-
10-3
RPCD
125
175
125
175
175
Itarations
Eordiions
RPCD, LSE, a-
25
RPCD, Quad. LSE, a a
APCD, LSE, a 0.0,
10'
10a
10r
10
10-2
10*2
10
10-
10:3
10-1
10-1
10
10-1
RCD RPCD
10:7
RCD
RPCD
10:
RCD RFCD
25
125
375
25
125
175
100
125
175
Itarations
Earabions
barat.ond
Figure 9. RCD RPCD, quadratic functions with unit-diage diagonal Hessians and log log-sum-exy exp term. A is unit unit-diagonal and Auin (4) 25, E (0.1.... (0.1,...,0.9), a 0.5. The y-axis log scale.
60

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RPCD, LSE, d a- 0.5.
LSE, d e
RPCD, di 0.3, 0.5.
107-
RCD
10a
RCD
RCD
IPCD
RPCD
RFCD
S 10
16-
300
300
Itaratians
Iterations
Ite nn
RPCD, LSE, d a-
RPCD, d- a
APCD,
a
10a
RPCD
10-1
10
10--
Fi
BCD
RCD
RPCD
RPCD
Itarations
Eorations
RPCD, LSE, a
RPCD, LSE, a a
APCD, LSE, 0.0. n
100
10a
10a
10a4
10-1
10-2
10-2
10-1
10-1
10-1
10-4
10'4
RCD RPCD
10-1
RCD
RPCD
10
RCD RFCD
100
100
155
300
ltarations
Earations
Darat.nn
Figure 10. RCD vs RPCD, quadratic functions with unit- diagonal Hessians and log-sum-exp exp term. A is unit diaionaa and Amin (A) 50, E a 0.5. The y-axis log scale.
61

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RPCD, LSE, 0- 2.0.
LSE, d a..00.
RPCD, di g.0..
109
RCD
10a
30*
RCD RPCD
IPCD
10
Viee
10
10-1
16
10
RCD RPCD
125
375
25
125
175
125
175
Itarations
horabions
RPCD, a
RPCD, d a
APCD,
a 2.0,
10a
10*
RPCD
10a4
10:1
10%
10-4
10
10-1
RCD XPCD
RCD
RPCD
125
175
125
175
175
Itarations
Eorations
RPCD, LSE, 0.7.7, 2.0. 25
RPCD, Quad. LSE, a a
APCD, LSE, a
2.0.
10'
10a
10'
10-1
10
10:
10-1
10-3
10
10-5
10
10-1
RCD RPCD
10-7
ACD
RPCD
10
RCD RFCD
25
125
375
25
125
175
100
125
175
Itarations
Earabions
barat.ond
Figure 11. RCD vs RPCD, quadratic functions with unit- diagonal Hessians and log log-sum-eue exp term. A is unit unit-diagonal and Amin (4) 25, a E (0.1...., ....),,......... a 2.0. The y-axis log scale.
62

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
RPCD, LSE, d 0.1.a-2.0.
LSE, d 0.2. 2.00.
RPCD, di 0.3, 2.0..
10a
RCD
10a
R2D
RCD
IPCD
RPCD
RPCD
20
10-
16
300
Itaratians
Iterations
Ite non
RPCD, LSE, d a
RPCD, d a
APCD,
2.0,
RCD RPCD
10'
10
10:2
10m2
10
BCD RPCD
RCD
RPCD
Itarations
Eoratoon
RPCD, LSE, a a 2.0,
RPCD, LSE, a a
APCD, LSE,
10'
10a
10a
10-1
10-4
10-
10-2
10
10ml
10'1
RCD RPCD
10-3
RCD
16-4
RCD
RPCD
RFCD
100
100
250
155
300
ltarations
Earations
Darat.on
Figure 12. RCD vs RPCD, quadratic functions with unit- diagonal Hessians and log-sum-exp exp term. A is unit diaionaa and Amin (A) 50, E (0.1....,0.. a 2.0. The y-axis log scale.
63

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
vs. RPCD, Quad. LSE, 25, d=0.1, a-20.0
vs RPCD, Quad. n=25, ow0.2, d=20..0
vs APCD, Quad. LSE, n=25, 0-0.3, e-20.0
RCD
RC0
SPCD
RFCD
10-3
10-t
10-1
10-
50
100
125
150
175
200
30
100
12b
150
175
200
50
100 Sanations
125
150
175
200
RCD vs RPCD, Qued. ISE, 2525, gm0.4, um20.0
ACD vs RPCD, Quad, LSE, nm25, pm0.5, 2=20..
RCD vs RPCD, Quad, LSE, nm25, p=0.6. am20.0
10
10-1
10
10
10-1
10--
10-
10:9
10
25
50
100
125
150
175
200
50
100
125
150
175
200
50
100
125
150
175
200
Serations
RPCD, Quad. LSE, n525, o-0.7, g-20.0
vs RPCD, Quad. n-25, 0.0.8, 2020.0
RPCD, Quad. LSE, n-25, 6=0.9, 2020.0
10
10:1
10
10
10:4
10
10-
10-
10-4
10
25
50
100
125
159
175
200
50
100 Beeaalons
12s
150
195
200
25
50
100 Secalions
125
150
L95
200
Hereioons
Figure 13. RCD vs RPCD, quadratic functions with unit-dian diagodia Hessians and log log-sum-exe exp term. A is unit unit-diagonal and Auin (4) 25, a E (0.1.... 1o.1.....0.. 0,0.9, a 20.0. The y-axis in log scale.
64

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
vs. RPCD, Quad. LSE, nim 50, d=0.1, 2-20..0
vs RPCD, Quad. n550, 0w0.2, d=20..0
vs RPCD, Quad. n=50, 0=0.3, d=20.0
10"
RCD
SPCD
20-3
20
10
10'2
50
100
150
200
250
300
50
100
150
200
250
300
50
100
130
200
250
300
Senaiions
vs. RPCD, Qued. LSE, 50 gm0.4, um20.0
RCD vs RPCD, Quad, nm50, pm0.5, 2m200.0
RCD vs RPCD, Quad. n= am0.6, am20.0
10-1
10
10-4
10"1
10-3
50
100
150
200
300
50
100
150
200
250
300
50
100
150
200
300
Hensiors
Sarations
RPCD, Quad. LSE, o-0.7, g-20.0
vs RPCD, Quad. n-50, 0.8.8, 20.0
vs RPCD, Quad. LSE, no50, 6-9.9, 2020.0
10
10-2
10
10+2
10
10-
10
10-1
100
150 Hersioo
200
300
100
150
250
300
50
150
150
300
Iteratioss
Recations
Figure 14. RCD vs RPCD, quadratic functions with unit- diagonal Hessians and log log-sum-eee exp term. A is unitunniaaaa miit-diagonal and Amin (4) 50, E (0.1...., (.........99,, a 20.0. The y-axis in log scale.
65

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
ACD vs RPCD, Ridge Log. Reg. A 0.0001
RCD vs RPCD, Ridge Log. Reg. 0.001
RCD vs RPCD, Ridge Log. Reg., A= 0.01
RC0
RKDD
199-
6x100
100
200
300
400
500
600
100
200
300
400
500
600
100
200
300
400
900
Fr ons
Benttior
Benelions
RCD vs RPCD, Ridge Log. Reg., 0.1
RCD vs RFCD, Ridge Log. Reg., A 1.0
RCD
RPED
45 <6 1900 K11
20-1
10
10-4
10-4
100
200
300 Reeiloos
400
300
600
100
200
300 Bersioos
400
500
500
Figure 15. RCD vs RPCD, Ridge-regularized logistic regression, log scale.
100. À E (0.0001, 0.01, 1.3. The y-axis is in
66

---

1 + (1 0) Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
G. Non-Asymptotic Comparison of RCD and RPCD
This section shows that RPCD outperforms RCD even after a finite number of epochs when Aa. complementing the asymptotic results in the main text.
To avoid confusion, we introduce separate notations for RCD and RPCD. We denote by æ and RPCD the iterates after T iterations and K epochs, respectively, both starting from the same initial point 2o. The corresponding iteration matrices, denoted by RRCD and A. are both 2 x 2 iteration matrices of RCD and RPCD that represent the restriction of M and MRCD to span I, 11
=
G.1. RCD Lower Bound
From the proof of Theorem 3.4, we have
min (MM 0T:
where or ej (M)D)) e1. Let Vn and v2 be the unit eigenvectors of M associated with eigenvalues A and X2. where A Ag. Then can decompose ei = 0i + 02U2, where o + cï since 0s and U2 form an orthonormal basis.
Using this decomposition, we compute
or = ej (MR
(c1V) 0202) (MRCD) (clV)
(cru) + c202)
= G + c22
2 e.AT.
The inequality follows from the fact that \a 2 0, as shown in the proof of Theorem 3.4.
We now consider cases: (i) and (fi) 2.
(i) 2. When 2, all entries of MRCD are positive. Therefore, Ferron-Frobenius Theorem.
apply the following lemma, known as the
Lemma G.1 (Horn & Johnson (2012), Theorem 8.2.8.). Let A RRxx be positive matrix, ie., all entries strictly positive. Then there exists unique real vector such that Ax p(A)x and æ is positive vector, i.e., all entries are strictly positive.
By this lemma, the eigenvector [111 have strictly positive components.
v12]
corresponding to the largest eigenvalue \max \max(MRCD can be chosen to
Now, from the equation MRDD 01 = 11 comparing the second coordinates gives
nd1 0²(n 2)
U1
V1
g²
Hence, V11 2 V12 is equivalent to λ₁ 2 (1 (1-4) 4) o². Now let p be the characteristic polynomial of M
One can compute that
(11
2(n 1)0²
0.
n
Since is convex quadratic polynomial, the inequality above implies that d 2 (1 - 11) 0². Therefore, U11 U12 and
since C = e, un and u + u22 1, we conclude that of 2
l 2.
(ii) n 2. In this case,
1
MRCD
2
2
67

---

Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
whose cigenvalues are and 1+(1-0)²
The cigenvector corresponding to the largest eigenvalue is proportional to
2
1 + (1 o)²
w
so the normalized eigenvector is 01 again obtain c 1 Finally, we have
Since + (1-o) 2 o², follows that 211 2 V12 and as in the previous case,
E E||| RCD|"
||
1 (1 0)
|
11
G.2. RPCD Upper Bound
From the proof of Theorem 3.3, we have
E
a
RPCD [|2|
z (MAD) (T)
|
2. 2o
S Amx ((MBRD))K (I))
y (M
where x == [1 oJ_ and [1 n] Let and 22 be the unit eigenvectors of MMRCD such that | = 1, associated with eigenvalues dι A2 with A1 2 A2. Then = c1 + C2 for some c1, with of + ca 1, because C1. We have
y M K c, K y
11 + 22
A y
022
A2 A1
K
xx
cıy T 01 +
U2
12
K
s X
| v + |021
w2ll
X1
$ X [11l[((a]] + lc2))
Since of c = 1, we have le1 + l021 S 22. Also, ||
vn 11, so get y T (MMRRDD K S AK 22 + 1).
G.3. Comparison of RCD and RPCD From the above, if T nK, we have
E
T
|12]
1
(1
0)
2
+
|
n
n
E
RPCD
K
[12]
max
(1- (1-
-
σ
2n
} ( (v2(n2+1))
+1)
|
71
Thus, if we can show that
(1
"
t
n )1-")² (1- m)² 2n)
n
(V2(n² + 1) t
max
(42)
n
2
then we can conclude that RPCD is faster than RCD. The following is equivalent to (42):
1
(1-a)²) "
N 22/2(m² + +1) *
n
max
Since the left-hand side is 2 1, for any a E (0, 1), there exists Ko such that K 2 Ko, then (42) holds.
Therefore, after Kn epochs, RPCD is faster than RCD.
68


Reviews:
[{"review_id": "M5IJKE7QG6", "reviewer": "Reviewer_gqcX", "summary": "This paper investigates the convergence rates of random coordinate descent (RCD) and random permutation coordinate descent (RPCD) for minimizing a class of quadratic functions. The key contributions are: (a) a novel lower bound for RCD's contraction rate on general positive definite quadratic functions and a stronger version on a specific function class (denoted by $\\mathcal{A}\\_{\\sigma}$); (b) an upper bound for RPCD's contraction rate on $\\mathcal{A}\\_{\\sigma}$; (c) showing that the upper bound of RPCD is strictly smaller than the lower bound of RCD on $\\mathcal{A}\\_{\\sigma}$.\n\n## Update after rebuttal\n\nI am satisfied with the further clarifications in the rebuttal, and I decide to keep my score.", "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": "We thank the reviewer for the positive response and meaningful questions. Below, we summarize and respond to your questions one by one.\n\n### Weaknesses\n\n> *The main weakness is that the results only hold on a restricted function class, and it is likely that the technical tool developed in this paper may be difficult to generalize to other problems.*\n\nWhile the reviewer’s comment is correct overall, we would like to carefully add that we have empirical evidence that the function class $\\mathcal{A}_{\\sigma}$ represents the worst case among general quadratics and that there still exist potential ways to extend the proof techniques to a slightly larger subclass of quadratics (see **Appendix E**). As a side note, for deterministic algorithms, it is possible that convergence results on quadratics could also yield *local* convergence rates of non-quadratic functions by considering the Hessian at the optimum (see, e.g., [Bertsekas, 1997, Proposition 4.4.1]). While this motivates us to extend our results to non-quadratic objectives and demonstrate local convergence, directly applying this approach is likely challenging in the stochastic setting. Identifying a suitable operator for analyzing the expected iterate norm is a technical hurdle, and we therefore leave this extension to future work. (We also leave another discussion point regarding non-quadratic functions in our response to reviewer h7Qf.)\n\n[Bertsekas, 1997] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334–334, 1997.\n\n\n### Comments\n\n> *Since the whole analysis focuses on quadratic functions, it may not be very meaningful to introduce the general optimization problem in equation (1). Clearly setting the scope of this paper helps the readers better comprehend the main contributions.*\n\nOur purpose in starting with the general minimization problem (1) was for a smoother exposition of the introduction section, as some of the previous works we discuss therein consider general convex functions. Nevertheless, we appreciate the feedback and will try to clarify the scope of our results by adding more details in the **Summary of Contributions** paragraph.\n\n> *Since different theorems are presented for different function classes, I suggest the author(s) making a table that clearly classifies the problems and summarizes the known results for each class. This may help the readers understand which part of the theory is proved and which is unknown.*\n\nWe tried to add a summary table of our results in the main paper, but had to remove it due to space limitations; we will add this table in our next revision.\n\n\n### Questions\n\n> *Is there any specific reason why you consider the quadratic+LSE problem in Section 4.2? Since the setting (iii) is no longer within the scope of the theory, it may be more interesting to investigate problems that are more commonly seen in machine learning tasks. Also, is there any $\\alpha$ that breaks the superiority of RPCD? This may provide some insights into how the benefit of RPCD relies on the quadratic form of the objective function.*\n\nFor the quadratic+LSE experiments in Section 4.2, we would like to clarify that our purpose in using the LSE term was to simply construct a non-quadratic example. Considering the reviewer's question, we also conducted additional experiments on (1) expanding the range of $\\alpha$ up to 100 in setting (iii) in our experiments, and (2) a logistic regression task with a ridge penalty, following the setup in [NSLFK15] (with n=m=100). The loss function for this experiment is as follows: \n$$ \\min_x \\frac{1}{m} \\sum_{i=1}^{m} \\log(1 + \\exp(-b_i a_i^{\\top} x)) + \\frac{\\lambda}{2} ||x||^2, $$ where $a_i$ and $y$ are drawn from the standard normal distribution and $b_i=\\text{sign}(a_i^{\\top} y)$ but randomly flipped the sign with probability 0.1. Across all experiments, we observed that RPCD consistently converged faster than RCD. Another thing to note is that convergence slowed with increasing $\\alpha$ in (1) and decreasing ridge penalty in (2).\n\nWe provide a link to the experimental results: https://anonymous.4open.science/r/rcd_rpcd-7416/\n\n[NSLFK15] Julie Nutini, Mark Schmidt, Issam H. Laradji, Michael Friedlander, Hoyt Koepke. Coordinate descent converges faster with the Gauss-Southwell rule than random selection. In Proceedings of the 32nd International Conference on Machine Learning, 2015.", "claims_and_evidence": "Yes, the theoretical claims are supported by proofs and numerical experiments.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have not checked the full technical details, but the overall correctness seems to be sound.", "experimental_designs_or_analyses": "The numerical experiments are mainly usesd to support the theoretical claims and seem to be valid.", "relation_to_broader_scientific_literature": "Although the results are restricted to a specific function class, the analysis in this paper provides insights on the benefit of RPCD over RCD on a broader class of problems.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I think this paper is a solid contribution to the understanding of coordinate-descent-type algorithms, and the theoretical results and their implications are well presented.\n\nThe main weakness is that the results only hold on a restricted function class, and it is likely that the technical tool developed in this paper may be difficult to generalize to other problems.", "other_comments_or_suggestions": "Here are a few additional comments aiming at helping the author(s) further improve the article:\n1. Since the whole analysis focuses on quadratic functions, it may not be very meaningful to introduce the general optimization problem in equation (1). Clearly setting the scope of this paper helps the readers better comprehend the main contributions.\n2. Since different theorems are presented for different function classes, I suggest the author(s) making a table that clearly classifies the problems and summarizes the known results for each class. This may help the readers understand which part of the theory is proved and which is unknown.", "questions_for_authors": "I have one question mainly on the design of the numerical experiments. Is there any specific reason why you consider the quadratic+LSE problem in Section 4.2? Since the setting (iii) is no longer within the scope of the theory, it may be more interesting to investigate problems that are more commonly seen in machine learning tasks. Also, is there any $\\alpha$ that breaks the superiority of RPCD? This may provide some insights on how the benefit of RPCD relies on the quadratic form of the objective function.", "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": "Goza9H6rie", "reviewer": "Reviewer_M9VV", "summary": "The paper studies the stochastic coordinate descent method for quadratic optimization and focuses on two schemes: uniform sampling versus random permutation. Under the mild unit-diagonal assumption, the authors show that random-permutation coordinate descent (RPCD) converges faster than random coordinate descent (RCD).  Precisely, the authors establish the following results.\n\n1. The authors prove a lower bound for RCD.\n\n2. For a special function class, RPCD is proven to be faster than the lower bound of RCD mentioned above.\n\n3. For the same special function class, RCD admits an even stronger (slower) lower bound.\n\nThe authors also discuss how to generalize their results and provide several numerical experiments.\n\n## update after rebuttal\n\nI maintain my score.", "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": "We deeply appreciate the constructive review and feedback. We thank the reviewer for reading the paper thoroughly in detail, and we hope our response relevantly addresses all points raised in the review.\n\n### Appendix\n\n> *Line 622: $k\\to \\infty$ should be $T\\to \\infty$.*\n\nThanks for finding the typo. We will fix this in our next revision.\n\n> *Line 720: I can't see the reason why $\\mu_{i}<\\mu_{1}$ (they possibly equal to each other).*\n\nIt is true that we must consider cases when $\\mu_i = \\mu_1$ and yet the limit remains unchanged. We will fix the details in our next revision as well.\n\n### Comments\n\n> *I think it's better to clarify that $\\mathcal{M}\\_{\\boldsymbol{A}}^{k}$ denotes the function composition instead of its k-th power. For some places, the identity matrix is written as $I$ instead of $I_{n}$ as defined at the beginning of Section 2.*\n\nWe will elaborate on these points in Section 2 in our next revision.\n\n> *It's better to say Theorems 3.1 and 3.4 hold with respect to the Lebesgue measure.* \n\nIt is true that the ‘measure zero sets’ are with respect to the Lebesgue measure. We will also add this in our next revision.\n\n> *It could be better to provide the explicit expression of $\\mathcal{M}_{\\boldsymbol{A}}^{\\text{RCD}}$ since it is computable and will be used many times in the proof.*\n\nWe deferred the explicit form of $\\mathcal{M}_{\\boldsymbol{A}}^{\\text{RCD}}$ to Line 660 of the Appendix, but we appreciate the feedback and will consider moving this into the main text in our next revision.\n\n\n### Questions\n\n> *The paper focuses on asymptotic results. Could the authors say something about non-asymptotic analysis?*\n\nThis is a very good question. The reason why our results are asymptotic is that they involve matrix powers. Specifically, see Line 705 (Theorem 3.1), Line 943 (Theorem 3.3), and Line 2081 (Theorem 3.4). However, with a more refined analysis, we can determine the minimum number of iterations to guarantee RPCD's faster convergence compared to RCD. In order to obtain non-asymptotic convergence guarantees for some large enough yet finite $K$ or $T$, we must find the non-asymptotic counterparts of parts like Lines 708-714 and Lines 941-948 in our proofs. However, this is not so straightforward as, for instance, the quantity in Lines 716-719 reaches $1$ at the limit but is smaller than 1 for finite $T$. In fact, our RCD lower bound increases as $T \\rightarrow \\infty$, while our RPCD upper bound decreases as $K \\rightarrow \\infty$, which necessitates characterizing the \"crossing\" point when the RPCD upper bound becomes smaller than RCD lower bound after a certain number of iterations; this makes the non-asymptotic analysis harder.\n\nWe plan to add these discussions as a remark in our next revision.", "claims_and_evidence": "All claimed theorems are proved.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "I mainly viewed proofs of Theorems 3.1 and 3.4. As far as I can check, they are correct.", "experimental_designs_or_analyses": "The experiments are sufficient and details are also reported.", "relation_to_broader_scientific_literature": "The analysis may be useful in more general optimization problems.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "The paper is well-written in general. I can't find any major weaknesses.", "other_comments_or_suggestions": "1. I think it's better to clarify that $\\mathcal{M}_{\\boldsymbol{A}}^{k}$ denotes the function composition in stead of its $k$-th power.\n\n2. For some places, the identity matrix is written as $\\boldsymbol{I}$ instead of $\\boldsymbol{I}_{n}$ as defined at the beginning of Section 2.\n\n3. It's better to say Theorems 3.1 and 3.4 hold with respect to the Lebesgue measure.\n\n4. It could be better to provide the explicit expression of $\\mathcal{M}_{\\boldsymbol{A}}^{\\mathrm{RCD}}(\\cdot)$ since it is computable and will be used many times in the proof.", "questions_for_authors": "The paper focuses on asymptotic results. Could the authors say something about non-asymptotic analysis?", "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": "Nal2b2Mtx7", "reviewer": "Reviewer_h7Qf", "summary": "Authors reiterate the problem of proving that the coordinate descent method with a random permutation of coordinates (RPCD) is theoretically faster than classical random coordinate descent (RCD). They prove that the asymptotic lower bound on the convergence rate of RCD is worse than the upper bound on the convergence rate of RPCD. Furthermore, they show a strict gap between the convergence rates of RCD and RPCD on the class of quadratic functions with permutation-invariant Hessians.", "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": "We are grateful for the reviewer's valuable questions and rich comments. Below, we have put together our responses to the questions.\n\n### Relation To Broader Scientific Literature\n\n> *As the authors themselves note, their convergence results for RPCD (Equation 10 in the paper) are weaker than those of Lee & Wright (Equation 3.15 in the linked work). In the appendix, the authors claim to improve the convergence rate and extend its applicability to a broader range of values for $\\sigma$.*\n\nWe would like to clarify that our RPCD upper bound results in the main paper (Theorem 3.3) are presented in a slightly weaker but more concise form solely for the purpose of readbility and easier comparison with the RCD lower bounds, and we have demonstrated in Appendix D that our analysis is not fundamentally weaker than that of previous works.\n\n### Essential References Not Discussed\n\nXu & Yin (2015) analyze an RPCD-like algorithm by fixing the update order without loss of generality. This approach does not fully address the distinction between a randomly permuted coordinate selection and a deterministic, fixed-order update. Nevertheless, thanks for the suggestion and we will consider adding discussions in our next revision.\n\n### Questions\n\n> *The paper conjectures that the benefits of RPCD extend beyond quadratic objectives. Have you considered applying your analysis framework to more general convex functions, such as strongly convex but non-quadratic functions?*\n\nThis is a very interesting question. It is true that our framework (or more precisely, the proof techniques) cannot be directly applied to broader function classes, as it all heavily relies on the idea of using matrix operators that act on the 'Hessian-like matrices' of the quadratics. \n\nThere are two possible directions to generalize to general non-quadratic objectives:\n* One would be to derive local convergence results for non-quadratics, which we discuss in our response to Reviewer gqcX.\n* Another direction could be to use existing results for other permutation-based algorithms like SGD with random reshuffling (SGD-RR) [MKR20] by basically substituting the finite-sum gradient oracles with the coordinate blocks of the gradients. Unlike SGD-RR, however, CD-type algorithms already enjoy *linear convergence* (even without random permutation) if the function is $\\mu$-strongly convex. (This is also related to the analysis of SGD-RR under the interpolation condition by [FTS23], where plugging in $\\sigma = 0$ yields linear convergence.) Thus, we cannot benefit from the variance reduction analysis in previous work, and it turns out that directly applying variance reduction analysis from SGD-RR leads to a loose upper bound. It is more likely that the effect of using permutations will be closer to a *preconditioning-like* effect (similar to previous analyses on cyclic CD [SY16]), which is largely different from SGD-RR, and we leave this direction for future investigation.\n\n[MKR20] Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik. Random Reshuffling: Simple Analysis with Vast Improvements. NeurIPS 2020.\n\n[FTS23] Chen Fan, Christos Thrampoulidis, Mark Schmidt. Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-Lojasiewicz Condition. ECML PKDD 2023.\n\n[SY16] Ruoyu Sun, Yinyu Ye. Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version. Mathematical Programming, 2016.", "claims_and_evidence": "The claims seem well-supported by the provided theory, but I have not independently checked the proofs.", "methods_and_evaluation_criteria": "The proposed class of functions appears adequate and is somewhat accepted in other works (Lee & Wright, Random permutations fix a worst case for cyclic coordinate descent)", "theoretical_claims": "I have not verified the correctness of the provided claims.", "experimental_designs_or_analyses": "The experiments seem appropriate for a work with a predominantly theoretical focus.", "relation_to_broader_scientific_literature": "Other studies analyze the Lipschitz smoothness of the function as the key parameter driving RCD-related methods (https://arxiv.org/pdf/1805.09185, https://arxiv.org/pdf/2102.07245). However, the current paper is more directly comparable to Lee & Wright, 2019 (https://optimization-online.org/wp-content/uploads/2016/07/5562.pdf). As the authors themselves note, their convergence results for RPCD (Equation 10 in the paper) are weaker than those of Lee & Wright (Equation 3.15 in the linked work). In the appendix, the authors claim to improve the convergence rate and extend its applicability to a broader range of values for $\\sigma$.", "essential_references_not_discussed": "This paper (Xu & Yin, 2015, https://epubs.siam.org/doi/epdf/10.1137/140983938) analyzes an RPCD-like algorithm, which performs descent over a subspace rather than exact minimization within it. The study establishes a \\(1/\\sqrt{k}\\) convergence rate in the convex setting, assuming standard conditions.", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "The paper conjectures that the benefits of RPCD extend beyond quadratic objectives. Have you considered applying your analysis framework to more general convex functions, such as strongly convex but non-quadratic functions?", "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": "INF8JPgEBw", "reviewer": "Reviewer_Mbvp", "summary": "The paper considers coordinate descent with updates performed on iid coordinates (RCD) versus coordinates chosen by random permutation (RPCD).  The permutation updates are empirically known to outperform the iid baseline, but this has lacked theoretical justification.  The main result of the paper proves the RPCD method converges faster than RCD for a class of quadratic objectives with constraints on the quadratic form.", "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": "We appreciate the valuable questions and comments, and we express our gratitude for the positive feedback and recognizing the novelty of our work. We provide detailed responses to the questions below.\n\n### Methods And Evaluation Criteria\n\n> *The evaluations generally make sense for the setting. One area somewhat under explained is section 4.1 in particular the algorithm to search for ‘difficult’ PSD matrices and section 4.2 where the log-sum-exp term is included for some of the experiments. Both sections would benefit from a bit more explanation; why is that algorithm a better candidate for generating hard quadratic programs than any other matrix distribution? When the authors write that the log-sum-exp terms make the loss less coordinate-friendly, is there a reference or quick explanation they could give for why this should be especially difficult for these algorithms? Intuitively I can look at this function as very non-separable and guess that coordinate descent would have slower convergence, but the plots in Table 3 with or without the LSE terms appear almost identical. I should mention I quite like this section for trying to give empirical ways to stress test the authors' hypothesis.*\n\n- To elaborate on the **Algorithmic Search** part in Section 4.1, this method works by using a scipy optimizer (as in Step 4) to maximize the value $\\rho(\\mathcal{M}\\_{\\boldsymbol{A}})$, while Steps 1–3 ensure that the matrix $\\boldsymbol{A}$ is generated to be inside the desired function class (unit-diagonal PSD with fixed $\\lambda_{\\min} = \\sigma$). The worst case examples are likely to be in a (Lebesgue) measure zero set, which motivated us to use such an optimization approach rather than sampling-based methods. We will add a more detailed explanation in our next revision.\n- For the quadratic+LSE experiments in Section 4.2, we would like to clarify that our purpose of using the LSE term was to simply construct a non-quadratic example; it is not specially designed as a hard instance for CD algorithms, while we did add the orthogonal matrix $\\boldsymbol{Q}$ to see if random permutations are beneficial for the 'non-coordinatewise-separable' cases as well.\n- We also conducted experiments expanding the range of $\\alpha$ up to 100 in the quadratic+LSE setting. Across all experiments, RPCD consistently converged faster than RCD. However, convergence slowed with increasing $\\alpha$. However, the performance gap between RPCD and RCD narrowed as $\\alpha$ increased. (You may also refer to our response to reviewer gqcX.)\n\nWe provide a link to the experimental results: https://anonymous.4open.science/r/rcd_rpcd-7416/\n\n### Relation To Broader Scientific Literature:\n\n> *The paper seems to improve on earlier bounds at the expense of stricter assumptions.*\n\nWhile we thank the reviewer again for the diligent review and positive response, we would like to carefully point out that our assumptions are not necessarily *stricter* than directly relevant previous works that consider *permutation-based* coordinate descent algorithms.\nSpecifically, [LW19] considers a narrower class of problems than we do (as noted in Section 3.3, Comparison with Previous Work). While [WL17] considers a slightly larger class of quadratics allowing small diagonal perturbations on permutation-invariant Hessians, [GOVW18] also relies on the permutation-invariant Hessian assumption, although they considered negative off-diagonal cases.\n\n[LW19] Ching-Pei Lee and Stephen J. Wright. Random permutations fix a worst case for cyclic coordinate descent. IMA Journal of Numerical Analysis, 2019.\n\n[WL17] Stephen J. Wright and Ching-Pei Lee. Analyzing random permutations for cyclic coordinate descent. Mathematics of Computation, 2017.\n\n[GOVW18] Mert Gurbuzbalaban, Asuman Ozdaglar, Nuri Denizcan Vanli, Stephen J. Wright. Randomness and permutations in coordinate descent methods. Mathematical Programming, 2018.", "claims_and_evidence": "The claims are well supported by simple experiments measuring convergence and solid proofs.", "methods_and_evaluation_criteria": "The evaluations generally make sense for the setting.  One area somewhat under explained is section 4.1 in particular the algorithm to search for ‘difficult’ PSD matrices and section 4.2 where the log-sum-exp term is included for some of the experiments.  Both sections would benefit from a bit more explanation; why is that algorithm a better candidate for generating hard quadratic programs than any other matrix distribution?  When the authors write that the log-sum-exp terms make the loss less coordinate-friendly, is there a reference or quick explanation they could give for why this should be especially difficult for these algorithms?  Intuitively I can look at this function as very non-separable and guess that coordinate descent would have slower convergence, but the plots in Table 3 with or without the LSE terms appear almost identical.  I should mention I quite like this section for trying to give empirical ways to stress test the authors' hypothesis.", "theoretical_claims": "The results appear correct, I mainly confirmed the analysis in the appendix up to page 19, although I didn’t go through all the details of the very technical followup chasing polynomial root identities.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper seems to improve on earlier bounds at the expense of stricter assumptions.  I can appreciate why the problem is difficult as analyzing RPCD requires evaluating n gradient updates at a time.  The trick of (essentially) constraining the class of Hessians to the two-dimensional space of matrices invariant to conjugation by permutation makes sense, although it is quite limiting for the problem.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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: This paper studies the open question whether RPCD (randomly permuted coordinate descent) is faster than RCD (randomized coordinate descent). It shows that RPCD is faster than RCD for a class of quadratic optimization problems where the Hessians are permutation invariant. More specifically, it establishes rigorously the upper bound of RPCD for this class, and the lower bound of RCD for this class, and by comparing them it reaches the results that RPCD is faster than RCD for this class of problems. A limitation is that the results focus on a specific function class; nevertheless, given the slow progress on this problem over years, the results in this paper are encouraging and may shed light on this difficult and fundamental problem. I recommend accept.
Decision: Accept (poster)