- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the advantages of signGD under imbalanced classes. The authors establish a minimal setting to study the difference in convergence rate between signGD, GD, and normalized steepest descent under specific initialization and other assumptions. Experimental evidence is also provided to validate their claims.
Critical strengths
- This paper establishes convergence results across multiple algorithms and both deterministic and stochastic settings, and propose a minimal setting to study these algorithms.
Critical weaknesses
- The presentation of theoretical results and emphasis of the story are not clear enough. See questions. Also, the abstract does not seem to cover all the strengths. Emphasizing the minimal setting is good; however, if there are no clear properties revealed behind these convergence results, I would suggest still focusing on the difference between these algorithms, which is the main strength of this paper.
Questions for authors
- Does Theorem 4.1 only work for learning rate ? If so, what is the intuition for this? What if both Theorem 4.1 and 4.2 are not initialized at 0? Which part will fail in the current analysis?
- The statement of Theorem 4.3 seems a bit weak, since it assumes the trajectory is bounded and the objective is convex and Lipschitz smooth. However, the explanation below it indicates stronger results if I understand it correctly (the bounded trajectory is proved instead of assumed in each algorithm; also, bounded trajectory and Lipschitz smoothness is repeated if the function is for example C^1). It would be better if the statement could be revised to ensure better interpretation. The overall organization of Section 4.2 (including all statements of the theorem and corollaries) is readable but not in its strongest and cleanest version.
- Existing literature sometimes uses normalized GD to understand spectral methods, where signGD roughly belongs to this family. Results in this paper show the difference. I wonder what is the reason behind this and what is special about signGD compared to different level/versions of spectral methods. It would be good if the author could provide a brief discussion on this.
2 comments
Dear Reviewer,
We wanted to follow up on our rebuttal and would appreciate any additional feedback on whether our responses have addressed your concerns. We would be happy to provide further clarification if needed. Thank you again for your time and consideration.
Rebuttal
We thank the reviewer for the time and effort spent reading and engaging with our work! We are glad that the reviewer recognizes that our paper establishes convergence results across multiple algorithms and both deterministic and stochastic settings. We now answer their questions.
Clarity
We thank the reviewer for their feedback on our presentation and have incorporated their suggestions into the main draft.
Thank you for raising this point. Could you please clarify what you mean by “spectral methods” in this context, perhaps with a reference? Our understanding is that these methods typically apply to matrix-valued weights, and we would like to ensure we address the intended comparison.
Learning Rate Guarantees
We can modify Theorem 4.1 so that it holds for η<2=1/L2 . The learning rate η=2 is the largest learning rate that guarantees convergence under the standard smoothness-based condition and larger learning rates may fail to converge. In Theorem F.4., we show that GD is unstable near any minimizer of the softmax unigram model for η≳logd Nevertheless, our main comparison is using the lower bound of GD which covers a large interval of learning rates, 0<η<d/2. The upper bound is supplementary and provides additional theoretical evidence of the worse dimensional dependence of the ℓ2 geometry for the softmax unigram model.
Initialization
Although our current theorems are stated with zero initialization for clarity, the conclusions extend to the commonly used initialization θ0∼N(0,σ2I) for small σ. For arbitrary θ0, the NSD-WD theorem bound depends on D=max∥θ0∥,1/λ. For θ0∼N(0,σ2I) we can average the theorem over initialization and use the fact that E∥θ0∥∞2=O(σ2logd) and E∥θ0∥22=σ2d to obtain O(((logd)2+σ2logd)/T) bound for SignGD-WD and O(d(1+σ2)/T) for normalized GD-WD. Hence, we recover the poly-log d dependent bound for SignGD-WD and the d dependent bound for normalized GD-WD. Without weight decay, adjusting the horizon-tuned stepsizes to the initial distance gives the same bounds with an additional logT factor, since the initial logit distance is at most logd+2∥θ0∥∞ and the expected squared Euclidean distance to a minimizer is O(d(1+σ2)). The GD lower bound also extends in expectation: each initial dyadic log-ratio is θ0,i−θ0,2i∼N(0,2σ2), and a constant fraction remain sufficiently close to zero for the original slow-progress argument to apply, changing only a σ-dependent constant. Thus, both the upper-bound comparison and the polynomial GD lower bound are robust to standard Gaussian initialization and can be extended to schemes that initialize close to zero.
Concluding remarks
We thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise.