Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent

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.

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.

• 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.
• 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.
• 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.)

We provide a link to the experimental results: https://anonymous.4open.science/r/rcd_rpcd-7416/

Relation To Broader Scientific Literature:

The paper seems to improve on earlier bounds at the expense of stricter assumptions.

While 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. Specifically, [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.

[LW19] Ching-Pei Lee and Stephen J. Wright. Random permutations fix a worst case for cyclic coordinate descent. IMA Journal of Numerical Analysis, 2019.

[WL17] Stephen J. Wright and Ching-Pei Lee. Analyzing random permutations for cyclic coordinate descent. Mathematics of Computation, 2017.

[GOVW18] Mert Gurbuzbalaban, Asuman Ozdaglar, Nuri Denizcan Vanli, Stephen J. Wright. Randomness and permutations in coordinate descent methods. Mathematical Programming, 2018.

We are grateful for the reviewer's valuable questions and rich comments. Below, we have put together our responses to the questions.

Relation To Broader Scientific Literature

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$.

We 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.

Essential References Not Discussed

Xu & 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.

Questions

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?

This 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.

There are two possible directions to generalize to general non-quadratic objectives:

• One would be to derive local convergence results for non-quadratics, which we discuss in our response to Reviewer gqcX.
• 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.

[MKR20] Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik. Random Reshuffling: Simple Analysis with Vast Improvements. NeurIPS 2020.

[FTS23] Chen Fan, Christos Thrampoulidis, Mark Schmidt. Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-Lojasiewicz Condition. ECML PKDD 2023.

[SY16] Ruoyu Sun, Yinyu Ye. Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version. Mathematical Programming, 2016.

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.

Appendix

Line 622: $k\to \infty$ should be $T\to \infty$.

Thanks for finding the typo. We will fix this in our next revision.

Line 720: I can't see the reason why $\mu_{i}<\mu_{1}$ (they possibly equal to each other).

It 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.

Comments

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.

We will elaborate on these points in Section 2 in our next revision.

It's better to say Theorems 3.1 and 3.4 hold with respect to the Lebesgue measure.

It is true that the ‘measure zero sets’ are with respect to the Lebesgue measure. We will also add this in our next revision.

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.

We 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.

Questions

The paper focuses on asymptotic results. Could the authors say something about non-asymptotic analysis?

This 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.

We plan to add these discussions as a remark in our next revision.

We thank the reviewer for the positive response and meaningful questions. Below, we summarize and respond to your questions one by one.

Weaknesses

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.

While 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.)

[Bertsekas, 1997] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334–334, 1997.

Comments

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.

Our 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.

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.

We 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.

Questions

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.

For 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: $\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).

We provide a link to the experimental results: https://anonymous.4open.science/r/rcd_rpcd-7416/

[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.