Summary
This paper introduces a new gradient-descent-based algorithm that achieves faster convergence rate on separable linear classification problems. The authors constructed examples which illustrate the limitations of vanilla GD and normalized GD. With such examples in mind, the authors proposed a "progressive rescaling" approach to more precisely control the iterates' orthogonal component to the maximum-margin solution. This paper proves that the proposed "Progressive Rescaling GD" (PRGD) converges to the maximum-margin solution exponentially quickly and the numerical experiments show that PRGD also achieves better convergence rate than GD on a variety of synthetic and real-world datasets.
Strengths
I very much like two specific ideas in this paper:
1. The PRGD algorithm is quite clever. While it is understood that the rate of convergence on logistic regression depends on the magnitude of the iterates (e.g. [1] and [2]), I am not aware of any accelerated algorithms in the literature that directly control this quantity. This paper neatly extended such simple observation by separately consider the components parallel and orthogonal to the max-margin solution. I am pleasantly surprised that the resulting algorithm is simple and its associated proofs do not require much heavy machinery.
2. The lower bounds given by Theorem 6.4 are valuable contribution to the literature. I believe this result can offer useful insights for future studies in the implicit bias and convergence of GD-based optimization algorithms.
[1] Nacson, Mor Shpigel, et al. "Convergence of gradient descent on separable data." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.
[2] Sun, Haoyuan, et al. "Mirror descent maximizes generalized margin and can be implemented efficiently." Advances in Neural Information Processing Systems 35, 2022.
Weaknesses
Despite the contributions of this paper (as I noted above), I feel that there are some significant gaps in this paper.
1. Assumption 5.4 is not consistent with the definition of non-degenerate data in [3]. In Soudry et al. [3], "non-degenerate data" refers to the case where the support vectors are linearly independent, but this paper considers the case where the span of support vectors is equal to the span of all data vectors. Therefore, this brings major concerns on whether Assumption 5.4 is reasonable. I am inclined to say no, as this assumption does not hold in an over-parameterized setting where $d \gg n$.
1b. There are some additional issues with the author's citation of [3]. First, [3] has a separate result showing convergence in their version of degenerate case. Thus, referencing [3] is not a valid justification for making Assumption 5.4 even if it were consistent with the literature. Also, there is no Theorem 4.4 in [3], so the authors were looking at the wrong version of the paper.
2. Theorem 6.2 mentioned the choice of parameter $R_k = \exp(\Theta(k))$. In contrast, its proof uses $R_k = \frac{D \lVert w(T_k) \rVert}{\lVert \mathcal{P}_\perp(w(T_k)) \rVert}$. While the proof does show that these quantities are equal, it does raise the question of whether the choice of $R_k$ is practical, as we do not know $w^\star$ ahead of time and therefore cannot compute the denominator. The authors need to present a choice of $R_k$ that is both *explicit* and *computable*.
3. The proofs of both Corollary 6.3 and Theorem 6.4 are incomplete.
4. The experimental section is very lacking. First, text in the figures are too small. Secondly, the figure captions are too short; for example, I spendt several minutes trying to figure out what are the left plot in Figures 2a and 2b. Next, the authors did not give their choice of hyper-parameters. Finally, and only a minor criticism on the experiments, the deep neural net experiment is a bit thin, as VGG is a not a well-performing architecture, even for a small dataset like CIFAR-10.
Finally, some minor comments:
5. There are a lot of typos in the paper. For example, "we have" is redundant in the first bullet point of Theorem 6.4. Also, in Appendix B, the proof should be for Theorem 5.5, not 5.4.
6. I suggest adding a brief discussion of Theorem 6.4 in Section 4, as it is a substantial result but barely mentioned outside of Section 6.2.
7. In Definition 5.3, the term "semi-cylindrical surface" is misleading, as this normally implies a half-cylinder cut along the direction parallel to its axis, NOT along the cross section.
8. The proofs can be better structured. There are several auxiliary lemmas (e.g. Lemma A.3 and A.4) that are not formally stated until the end of the section. They are preferably introduced in a separate subsection before the main proofs.
[3] Soudry, Daniel, et al. "The implicit bias of gradient descent on separable data." The Journal of Machine Learning Research 19.1, 2018.
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.