- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
In this work, the authors study the relation between continuous parameter space symmetries, Hessian effective rank and complexity of ZO optimization methods. Given the result on the bounding effective rank, the authors provide convergence results for ZO-SGD, claiming that the bound does not depend on the extrinsic dimension but only on the effective symmetry induced dimension on the quotient.
The theory is complemented by a series of numerical results monitoring the behaviour of the effective rank of the Hessian durining training.
Critical strengths
The work is overall written in a clear way, despite notation which can be simplified in some points. To my knowledge, the derivation of the convergence results is novel and contains potentially interesting theoretical arguments.
Critical weaknesses
- The key observation that symmetry-orbit tangent directions are contained in the kernel of the Hessian is a well known fact in differential geometry of Lie quotient manifolds. The bound resulting from Theorem 1 follows immediately from a matrix additive decomposition and a differential identity associated to the invariance. To me, it's personally unclear if this result is novel.
- The result on dimension independent query bound of Corollary 1 and Remark 3 rely on unjustified assumptions which I am not sure are realistic. In particular, to have a real dimension independence, if the orbit dimension grows linearly with , then the tangent Hessian residual must be of order in assumption 2. This is not a consequence of invariance, and it might require a very peculiar geometry around stationary points.
- Experimental results are somehow disconnected to the theory, and they seem just to focus mainly on the result in Theorem 1. Moreover, in the Transformer experiment proposed in section 5.2, it seems that the bound provided by the theory remains vacuous with respect to the observed results. In particular, the upper bound provided by Theorem 1 and the observation in Example 3 does not seem to be sharp and to explain the results in section 5.2.
- The improvement provided by the convergence results in section 4.2 is not clearly inserted in the literature, making it diffucult to judge how much are they informative or applicable with respect to standard ones.
Questions for authors
See "Critical Weaknesses".
2 comments
W4. The improvement of the convergence results in Section 4.2 is not clearly placed in the literature, which makes it difficult to judge how informative or applicable they are compared with standard ones.
We thank the reviewer for this comment. Corollary 1 is not a refinement of a standard rate under the standard assumptions; under those assumptions the dependence on cannot be removed. Standard analyses of ZO-SGD give query bounds that grow with the ambient dimension (Nesterov & Spokoiny, 2017; Ghadimi & Lan, 2013), and minimax lower bounds show that this dependence is unavoidable over broad convex problem classes (Jamieson et al., 2012; Shamir, 2013; Duchi et al., 2015). A bound that does not grow with therefore needs a more restricted setting.
In Corollary 1, the restriction is that the result is local. Assumptions 2 and 3 are required on a neighborhood of a stationary point, and the iterates are assumed to remain in ; the standard results do not need this. Within , the symmetry of the objective replaces the factor of the standard bound by (Equation (16)). Without symmetry, and , and the bound is of the standard order in .
We sincerely thank the reviewer for the careful assessment. Below are our point-by-point responses.
We thank the reviewer for this comment, and we agree that Proposition 1 is classical in the differential geometry of quotient manifolds. The revised manuscript now also cites Absil et al. (2008), Neyshabur et al. (2015), and Simsek et al. (2021) directly above the proposition. We include this proposition as technical motivation and do not claim it as a contribution.
Although Theorem 1 is short to prove, it extends the bound at stationary points to nonstationary points. More precisely, Theorem 1 covers nonstationary points, where the tangent directions are no longer in the kernel of the Hessian. We have not found this bound in the literature, so we still regard Theorem 1 as a new result.
We would like to emphasize what is new in Theorem 1:
We thank the reviewer for this observation; the scaling is correct. With m∝d and τ fixed, Assumption 2 requires δy≤τL/m=O(1/d) on U. However, this condition can be viewed from two perspectives.
For every invariant objective, Equation (2) gives δy≤κy∥∇f(y)∥, so myδy≤τL holds wherever myκy∥∇f(y)∥≤τL. In other words, it suffices that ∥∇f(y)∥ is sufficiently small, that is, U is a small neighborhood of a stationary orbit.
Therefore, we have the following two perspectives:
We thank the reviewer for this comment and answer its two parts in turn.
Connection between the experiments and the theory. We hope the following clarification makes the connection clearer:
The Transformer experiment. We agree that, on this model, the bound of Theorem 1 with the symmetry of Example 3 is larger than the measured effective rank, and Section 5.2 is not a test of the tightness of the bound. As stated at the beginning of Section 5, this experiment "examines whether similar low-effective-rank behavior occurs in practice", that is, whether the progression (P) is observed, and Figure 3 shows that it is.