- Rating
- 1
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies finding an -first-order stationary point of a lower-bounded, nonconvex function with Lipschitz gradient and Hessian, using only noiseless comparisons of function values. Its main claim is a randomized algorithm returning a list containing at least one stationary point, with comparison complexity
\frac{n\sqrt L\,\rho^{1/4}\Delta}{\epsilon^{7/4}} +\frac{n\sqrt L}{(\rho\epsilon)^{1/4}} \right).$$ The goal is to obtain accelerated dependence on accuracy while retaining nearly linear dependence on dimension. The method adapts restarted accelerated gradient descent by decomposing each gradient into an anchor magnitude, a relative magnitude, and a direction. It enumerates geometric guesses for anchor magnitudes and estimates magnitude ratios from gradient directions at endpoints and their midpoint.Critical strengths
[1] The research question is significant. Establishing nonconvex acceleration from comparisons alone would clarify how much numerical information accelerated optimization actually requires.
[2] The anchor-based decomposition is a useful idea. Estimating relative magnitudes could avoid enumerating a new magnitude guess at every iteration. Lemma 11 identifies a meaningful geometric relationship and explicitly exposes its conditioning requirements.
Critical weaknesses
[1] The rank-one reconstruction in Algorithm 4 seems incorrect.
Theorem 2 defines \texttt{ComparisonGE} as returning a unit-vector estimate of the normalized gradient. Consequently, Algorithm 4, line 4, computes
\frac{\widehat g_+-\widehat g_-} {\|\widehat g_+-\widehat g_-\|},$$ where \$ \widehat g_\pm \$ estimate normalized gradients. Subtracting these directions generally does not recover the direction obtained by subtracting the full gradients. Therefore, it seems possible that Algorithm 4 fails to supply its direction-accuracy hypothesis, needed Theorem 6 in Theorem 7. [2] The gradient-magnitude grid need not contain a valid guess. Algorithm 1 and Corollary 1 use $G_{max}=2L$, but the stated assumptions do not imply $\|\nabla f(x)\|\le2L$.Questions for authors
[1] What is the intended rank-one reconstruction algorithm? Please reconcile Algorithm 4 and prove a quantitative conditioning bound sufficient for Theorem 6
[2] What justifies the magnitude-grid upper bound (2L)? If large gradients are handled separately, where is that case included in the algorithm and global proof ?
[3] Which result establishes that the actual anchors and precision choices make the ratio estimates satisfy Assumption 1 throughout an epoch ?
[4] Should Algorithm 5 use a normalized step of length (R) rather than (1/L) ?
Thank you so much for these constructive questions and kindly pointing out non-rigorousness in our paper.
For your question [1]: We have reconstructed the rank-one-search framework with a series of line search (Algorithm 4). In each line search process we try two directions: the gradient and the dominant eigen direction of Jacobian, and prove that at least one of them aligns with eigenvector at a constant precision, which is enough. We have provided thorough error analysis about how to get a min{constant,χ/λ} precision (Lemma 3) and why it meets Theorem 6's requirement (Lemma 16). The revised proof therefore does not rely on the original local conditioning constant Cgeo.
For your question [2]: Thank you for pointing out that non-rigorousness! In fact the NormEstimator only apply to anchor norm guessing, thus we can bound their norm under constant scale. We have added a discussion in Remark 2 of the revised manuscript.
For your question [3]: We have added an analysis of how our precision choice can satisfy Assumption 1 in Lemma 2 of new version paper. About anchor choice, we added Appendix C.1 to guarantee an anchor set with at most eight directions and proved that at least one pair in this set can meet the requirement of Assumption 1.
For your question [4]: Thank you so much for pointing out this typo. We should use stepsize R=Θ(ϵ/ρ).