Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm
We consider minimizing a smooth function subject to a summation constraint over its variables. By exploiting a connection between the greedy 2-coordinate update for this problem and equality-constrained steepest descent in the 1-norm, we give a convergence rate for greedy selection under a proximal Polyak-Lojasiewicz assumption that is faster than random selection and independent of the problem dimension $n$. We then consider minimizing with both a summation constraint and bound constraints, as arises in the support vector machine dual problem. Existing greedy rules for this setting either guarantee trivial progress only or require $O(n^2)$ time to compute. We show that bound- and summation-constrained steepest descent in the L1-norm guarantees more progress per iteration than previous rules and can be computed in only $O(n \log n)$ time.
Paper
Similar papers
Peer review
Summary
The paper presents new update rules for block-coordinate descent (BCD) methods to minimize a smooth function subject to one linear equality constraint (precisely, all variables must sum to 1) and possibly a box constraint. A popular method to solve large-scale problems of this type is BCD with blocks of size 2 (i.e. we always update 2 coordinates at a time). A prominent example is SVM training in LibSVM. For problems without the box constraint, the key observation is lemma 2.1, which shows that greedy version of such updates is equivalent to 1-norm steepest descent. This allows the authors to employ known results from non-smooth optimization and propose better update rules and derive their convergence rate. This rate is better than known rates for non-greedy updates. For problems with a box constraint, the situation is more complicated because Lemma 2.1 does not apply. The authors nevertheless propose a new update (GS-1) based on 1-norm steepest descent, which is not guaranteed to change at most 2 variables in every update, but more than 2 variables are changed only in a finite number of updates. This can be seen as a greedy version of BCD with small blocks. The update has a better convergence rate than known updates that can be computed in reasonable (less than $O(n^2)$) time. The theory is supported by a synthetic toy experiment on the linear LS problem with one linear equality constraint and a box constraint.
Strengths
Crisp and elegant theoretical result, non-trivial. However, let me admit that convergence analysis of optimization algorithms is not precisely my expertise, so I am not reliably judge the novelty (these or similar results may be already known or obvious, ...). The text is precise and clear.
Weaknesses
A major weakness is experiments: they are limited only to a simple problem (linear least squares) on synthetic data, end even then the data variability tested is small (only square system). To my understanding, the GS-1 update has never been applied to SVM training - so such experiments would be very interesting. Moreover, in the experiments the difference $f(x)-f^*$ (vertical axis in Figure 1) is never shown to converge to zero, it is shown only in the range $10^{4.8} - 10^{5.2}$. In my experience, it sometimes happens that greedy updates improve the objective better initially but later they slow down and cyclic/random updates catch up. Or, perhaps, the vertical axis in Figure 1 shows $f(x)$ rather than $f(x)-f^*$ (as in the Supplement)? Minor issues in the text: - The five-line derivation on line 79-80 is trivial - it can be shortened to save space. - Lemma 2.1 is very much related to the well-known result that greedy coordinate descent is equivalent to 1-norm steepest descent (see, e.g., Section 9.4 in Boyd's book on convex optimization). This may deserve a citation. - Lemma 2.1 would be clearer if $\nabla f(x)$ were replaced by a general vector, say c. - Line 128: mentioning SVM is not OK here because SVM needs also a box constraint. - Line 139: the notion of "dimension independent convergence rate" is not well-defined because the problem dimension can be hidden in constants (such as $L_1, \mu_1$). But I understand that this notion may be widely used.
Questions
How would Figure 1 look like if the iterations continued to a very small (10^-6) error f(x)-f^* ? How does the GS-1 update behave in SVM training? Are there any other problem types on which you tested the new updates? Were there any negative results (i.e., the convergence was slow in practice despite theoretical guarantees)?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The experiments are limited to a very simple problem with synthetic data. Though the theoretical results are elegant, the optimization problem considered has a rather limited applicability.
Summary
The first goal of the paper is to minimize a smooth function subject to a summation constraint. The authors demonstrate that the greedy 2-coordinate descent (CD) method, when applied to the problem with equality constraints, achieves a linear rate of convergence under the proximal PL inequality under the L1-norm formulation. Notably, this convergence rate remains unaffected by the problem dimension, which sets it apart from random selection methods. Furthermore, they establish that there exists at least one steepest descent direction with respect to L1-norm, which can be utilized as a 2-coordinate descent update. They leverage this relationship to derive the convergence rates of the CD algorithm. Additionally, they explore the minimization involving a summation constraint and prescribed lower and upper bounds on the coordinates. They demonstrate that employing bound- and summation-constrained steepest descent in the L1-norm guarantees significant progress at each step, unlike the GS-s rule. Moreover, this method (called GS-1) is computationally more efficient than GS-q, requiring only $O(n \log(n))$ iterations instead of $O(n^2)$
Strengths
1. The paper gives linear convergence rates for greedy 2-coordinates CD, and the steepest descent in l1-norm under proximal PL for l1-norm. For problems with equality constraints, this work shows that greedy methods may be faster by a factor ranging from $O(n)$ up to $O(n^2)$ than methods picking coordinates at random, 2. For problems with bound constraints and equality constraints, the paper shows that GS-1 rule has the benefits of both GS-q and GS-s. Contrary to GS-q, GS-1 rule can be implemented in $O(n \log n)$ and contrary to GS-s, GS-1 guarantees non-trivial progress at each iteration. 3. The authors also proved a linear convergence rate for GS-q rule under proximal PL for L2-norm. It is not straightforward to use prox-PL to obtain the linear convergence rate for this update rule. They consider the conformal realization used by Tseng and Yun [2009] to upper bound the extra terms in descent inequality by a notion of gradient mapping used in prox-PL’s definition. 4. The paper is clear and well written.
Weaknesses
The experimental part is limited, which is fine for a theoretical optimization paper, but for a ML venue and given the claim made in the paper that many problems in ML require to satisfy an equality constraint, such as discrete probabilities or SVMs with an unregularized bias term, one could expect the experimental section to show the power of GS-1 for other such examples than only a synthetic equality-constrained least square problem.
Questions
1. L42-44: More comments are needed when the authors write that ``despite LIBSVM being perhaps the most widely-used CD method of all time, current analyses of greedy 2-coordinate updates either result in sublinear convergence rates or do not lead to faster rates than random selection [Tseng and Yun, 2009, Beck, 2014]." Did they use proximal PL inequality in L1-norm to analyze the convergence rate of greedy 2-coordinate methods? The linear convergence rate of this method may be due to the PL property. 2. L47-49 "The analysis is based on an equivalence between the greedy update and equality-constrained steepest descent in the 1-norm. This leads to a simple dimension-independent analysis of greedy selection showing that it can converge substantially faster than random selection." Under which assumptions is the faster convergence proven? 3. L. 66 ``If f is continuous, this update is guaranteed to decrease $f$ for sufficiently small $\alpha_k$'' Please quote a relevant paper, or a short proof for this sentence. 4. Question 4 removed as workshop papers are not listed in reviews. 5. L91 “For lower bounding sub-optimality in terms of the 1-norm, we introduce the proximal-PL inequality in the 1-norm.” What do you mean by lower bounding sub-optimality? As far as I can see, you are trying to give an upper bound on sub-optimality in Theorem 2.3. 6. Definition 2.2. “A function, that is L1-Lipschitz”: is it L1-Lipschitz gradient? Did this definition not appear in [Karimi et al. 2016]? 7. Does $f=g(Ax)$ satisfy proximal PL condition in the L1-norm for strongly convex function $f$ and a singular matrix $A$? Can we verify this property for functions in practice such as the SVM dual problem? 8. Did [She and Schmidt 2017] assume the same PL condition in the L1-norm (or L2-norm)? 9. Connection between the prox-PL function used in Theorem 3.2 and prox-PL as defined only by (9) in Def. 2.2: could you give an example of a function that satisfies this new assumption? 10. Some minor questions/typos in the appendix: L372 Should $d_1 + d_2$ not be $d_i + d_j$ L378 second line before end: one $)$ too much L390 Why do you have $\lambda 1$ in (29) and not simply $\lambda$ L428 $d_1 + d_2 + d_3$ should be $d_1 + d_2 - d_3$ L437 Why do we have the parameter $x^\prime$Conv$(\{x,x+d\})$~? ---- The authors have addressed adequately my questions; they intend to conduct extensive experiments. This is indeed missing in the current version of the paper, it is difficult to evaluate that part with the paper as is. But I find the theoretical contribution solid enough to justify publication.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
N/A
Summary
The paper studies new coordinate descent-type methods for equality-constrained problems, where 2 coordinates are updated on each iteration and proves new convergence guarantees under suitable proximal-PL conditions that allow to obtain linear convergence rates for the proposed methods. The first main result considers the case of a single constraint on the sum of coordinates with a simple greedy rule for selecting the two coordinates to update. A linear dimension-independent convergence rate is established using a fixed step-size and assuming PL inequality w.r.t. 1 norm. Next the authors consider the more challenging setting in which on top to the constraints on the sum of coordinates, there are also box constraints on the individual coordinates. Here the authors propose to use a greedy-proixmal update named Gauss-Southwell-q which leads to a linear rate using a fixed step-size and assuming PL inequality w.r.t. 2 norm, however with linear dependence in exponent of the dimension. Finally, in the latter setting (equality constraint on sum + box constraints), considering a PL inequality w.r.t. 1 norm and a diffrerent greedy rule (which corresponds to solving a proximal-style problem w.r.t to 1 norm, which given the gradient direction could be solved in O(nlogn) time), the authors obtain a linear dimension-independent rate. The proofs hinge on relating the 2-coordinate descent updates to the steepest descent method w.r.t. the 1 norm, which is interesting. The authors present experiments that support their findings on a random least squares problem with equality (and then also box) constraints.
Strengths
The paper is very well written and is easy to follow. The results and ideas are clearly presented. I enjoyed reading it. The problems considered are sound and make sense, and the type of methods discussed is of clear practical interest to the community. The technical argument of relating 2-coordinate descent to steepest descent w.r.t. 1 norm is interesting and might be of further use. The convergence rates obtained are novel and interesting to the best of my knowledge.
Weaknesses
1. I think the authors could do a better job in rigorously comparing the complexity of their methods to previous ones. It is not clear at all times if the obtained complexities are state-of-the-art (when not considering only 2-CD greedy methods). In particular, from first paragraph of 2nd page, it is not clear how this compete with known random selection methods. 2. To continue the above point, it seems all selection rules suggested require the full gradient direction. However, in such cases why these methods are better than full-gradient methods? For instance, for unconstrained least squares indeed doing an update to a single coordinate is much faster than computing entire gradient, and makes perfect sense when using random selection (e.g., w.r.t. to coordinate-wise Lipchitz parameters). But in the greedy rules we already need the full gradient. 3. The linear rates that are dimension-independent rely on PL w.r.t 1 norm. This might seem as ``hiding the dimension under the choice of norm''. Could the authors provide examples of interest that will satisfy this inequality with constant independent of the dimension? Or more precisely, that the ratio of the 1 norm constant and 2 norm constant is dimension independent? 4. At some point the authors claim that computing the coordinate-wise Lipchitz parameters can be difficult, however, in the most relevent setting I guess which allows also for the PL inequality: f(x) = g(Ax), with g strongly convex, in case g is well conditioned (e.g., squared Euclid norm in many cases), it is easy to estimate them I believe from the columns of A. 5. Throughout the paper the authors mention SVM as a major application, so why not conduct experiments with this application?
Questions
See weaknesses.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
NA
Summary
This work studies minimizing a smooth function with a summation equality constraint over its variables. The authors show a connection between the greedy 2-coordinate update and steepest descent w.r.t. 1-norm, and introduce a new proximal PL assumption w.r.t. 1-norm. They show improved convergence rates under such assumption over random selection. The authors also consider coordinate-wise Lipschitz smoothness and introduce an approximation for greedy 2-coordinate methods. They complement their theoretical results through numerical experiments on randomly generated problems.
Strengths
1. The connection from 2-coordinate greedy update to steepest descent w.r.t. 1 norm seems non-trival and potentially interesting for equality-constrained problems. 2. The authors offer detailed comparisons on various Gauss-Southwell update rules (GS-1, GS-q and GS-s).
Weaknesses
I believe this work has potential but lacks a few key ingredients. 1) This work lacks justification for their proximal-PL condition w.r.t. 1-norm. For example, Karimi et al (2016) provides five important classes of functions that statisfy the proximal-PL condition w.r.t. 2-norm. It is unclear to me what function classes can statisfy the proximal-PL condition w.r.t. 1-norm where the worst case dependence on $n$ for $\mu_1$ can be avoided. It would also be useful if there can be empirical comparisions for $\mu_1$ against $\mu_2$ as $n$ scales. At its current state, I do not think it is reasonable to claim that the convergence rate is independent of the problem dimension $n$. 2) I would like to see experiments performed on practical datasets (e.g., LIBSVM datasets) rather than randomly generated Gaussian data, since much of the theoretical results aim to improve upon the rules in LIBSVM. I would also like to see experiments on SVM problems to support their claimed improvements for SVM. 3) I suggest adding markers to the plots in Figure 1 and 2, as the overlapping nature of the results renders some plots unparsable.
Questions
1. What are the main differences of GS-1 rule (Algorithm 1) for proximal-PL assumption w.r.t. 1-norm, compared to Song et al. (2017)?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
N/A.
Empirical evaluation
My questions on the theory front are adequately addressed, thank you. About the experimental part: the authors show in Figure 2 in the paper that on the synthetic equality-constrained least square problem, GS-s rule results in the slowest convergence rate. Two of the additional experiments on the SVM real datasets show that GS-s converges as fast as GS-q and GS-1, while the third one shows that GS-s is actually faster than GS-q. Is there any trend (GS-1 being always at least as fast as the GS-q and GS-s) or do all three perform eventually in a similar range, without a clear predictable advantage for either one of them? A more extensive and quantitative empirical evaluation on real datasets would be welcome.
Thank you for reading and responding with your valuable feedback. We were surprised by the superior performance of GS-s over GS-q on some real datasets, although in subsequent experiments their performance was very similar, particularly after feature normalization. To comprehensively explore this phenomenon, we intend to conduct an extensive set of experiments, to tease apart various practical issues and to pinpoint instances where empirical behavior differs from the presented theory.
I thank the authors for their rebuttal. However, the PDF with additional plots (added to the general rebuttal) does not convincingly support the authors' claim that "the greedy methods find a reasonable solution far before random methods". In Figure 2 of the PDF, the "Random" method (blue line) is only slightly worse than the greedy methods, and it is so only for initial $\approx 10^4$ iterations. Since it is not clear at which accuracy the algorithm is supposed to be terminated, the fact that some method is better than the others for some initial number of iterations might be irrelevant. It is a pity that the authors did not show also the plots zoomed in for small values of $f(x)-f^*$ because now it is hard to see how the methods compare in this range. (this applies both to Figure 1 and 2) Is Figure 2 for the real data (SVM) or the synthetic data?
At the final iteration on the plot the 3 greedy methods incorporating the Li values are at numerical precision, the classic greedy method has a sub-optimality close to 0, while the random method has a sub-optimality around 30. It is true that we should have included a zoomed-in version of the end or plotted on a log-scale (which we will update in the paper). (We made Figure 2 in response to the comment "How would Figure 1 look like if the iterations continued to a very small (10^-6) error f(x)-f^", so it is on the same synthetic data. )
Response to Authors' Rebuttal
I thank the authors for the replies and am glad to know that they find my suggestions helpful. My concerns regarding $\mu_1$ vs $\mu_2$ and the comparison to Song et al. (2017) have been properly addressed. However, I maintain my reserve regarding their subpar experimental results for a ML venue. While this is mostly a theoretical work, it concerns a practical problem with well-defined experimental settings using real datasets. I am not fully convinced by the results in the attached PDF, although I do understand that it is already a big ask for the authors to add these results within such short timeframe, and I thank the authors for that. As such, I am increasing my score.
Thank you for reading and considering the response. We plan to add a comprehensive set of experiments on real data (beyond what is included in the author response).
Response
I thank the authors for their comments. Regarding comparison to previous work, I think that usually a table does the best job for comparing complexity bounds of different methods, but I leave it to the authors to decide. Regarding other discussions, in particular concrete discussions where the methods presented can be superior to other, I would be happy if you include them in your revision. I am maintaining my score.
Decision
Reject