acceptodds
Under review as a conference paper at ICLR 2027

When Does Symmetry Reduce Effective Rank in Zeroth-Order Optimization?

Abstract

Fine-tuning large neural networks is often limited by the substantial memory overhead of backpropagation. To address this bottleneck, memory-efficient zeroth-order optimization (MeZO) enables fine-tuning using only function evaluations, but classical zeroth-order optimization (ZO) query-complexity bounds typically scale with the ambient parameter dimension. Recent theory suggests that ZO efficiency can instead depend on the effective rank, a spectral measure of how curvature is distributed across parameter directions. In this work, we show that, for smooth objectives with appropriate symmetries, the effective rank of the Hessian is bounded by the codimension of the symmetry orbit together with an explicit correction term that quantifies nonstationarity. Our bound is tight, with equality achieved by an explicit family of smooth invariant objectives. At stationary points, it recovers the exact Hessian null directions induced by symmetry. Lastly, we establish finite-sample convergence of ZO-SGD under mild conditions and obtain dimension-independent function-query bounds without assuming a dominate low-effective-rank Hessian matrix. In experiments, empirical evidences are provided to illustrate the theoretical mechanism and the connection between effective rank and ZO optimization.

Primary area:
optimization
Keywords:
zeroth-order optimization, optimization theory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WJSuOpenReview ↗
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
  1. 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.
  2. 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 dd, then the tangent Hessian residual must be of order 1/d1/d in assumption 2. This is not a consequence of invariance, and it might require a very peculiar geometry around stationary points.
  3. 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.
  4. 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

We sincerely thank the reviewer for the careful assessment. Below are our point-by-point responses.

W1. That symmetry-orbit tangent directions are contained in the kernel of the Hessian is well known in the differential geometry of quotient manifolds. The bound of Theorem 1 follows immediately from an additive matrix decomposition and a differential identity associated with the invariance. It is unclear whether this result is novel.

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:

  • It turns the differential identity in Equation (2) into a bound on the effective rank at nonstationary points, connecting it to zeroth-order optimization.
  • It shows that symmetry can upper bound the effective rank by the orbit codimension, explaining why zeroth-order method can be effective for high-dimensional optimization problems.
  • The bound is tight: Proposition 2 attains equality for every mm, kk, and τ\tau, which requires a construction and does not follow from the decomposition.

W2. The dimension-independent query bound of Corollary 1 and Remark 3 relies on assumptions that may not be realistic. If the orbit dimension mm grows linearly with dd, the tangent Hessian residual δ\delta must be of order 1/d1/d in Assumption 2. This is not a consequence of invariance, and it might require a very peculiar geometry around stationary points.

We thank the reviewer for this observation; the scaling is correct. With m∝dm\propto d and τ\tau fixed, Assumption 2 requires δy≤τL/m=O(1/d)\delta_y\le\tau L/m=O(1/d) on UU. However, this condition can be viewed from two perspectives.

For every invariant objective, Equation (2) gives δy≤κy∥∇f(y)∥\delta_y\le\kappa_y\|\nabla f(y)\|, so myδy≤τLm_y\delta_y\le\tau L holds wherever myκy∥∇f(y)∥≤τLm_y\kappa_y\|\nabla f(y)\|\le\tau L. In other words, it suffices that ∥∇f(y)∥\|\nabla f(y)\| is sufficiently small, that is, UU is a small neighborhood of a stationary orbit.

Therefore, we have the following two perspectives:

  • With τ\tau fixed, the set UU becomes smaller as mm grows. It is a neighborhood of the stationary orbit whose width, measured by the gradient norm, is proportional to 1/m1/m. This is the setting of Corollary 1: Assumption 2 is introduced as holding "on a small convex neighborhood near the stationarity".
  • With UU fixed, τ\tau can grow in proportion to mm. The bound then depends on dd, and it is at most the classical one because reff≤dr_{\rm eff}\le d. We note that a rate that is globally independent of dd is not possible in general: minimax lower bounds show that the query complexity of zeroth-order methods grows with dd over broad convex problem classes (Jamieson et al., 2012; Shamir, 2013; Duchi et al., 2015).

W3. The experiments are somewhat disconnected from the theory and focus mainly on Theorem 1. In the Transformer experiment of Section 5.2, the bound of the theory remains vacuous with respect to the observed results: the upper bound of Theorem 1 with the symmetry of Example 3 is not sharp and does not explain the results.

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:

  • Theorem 1 and Figure 2(a,b). Theorem 1 states that, near a stationary orbit, the effective rank can be low and independent of the ambient dimension dd. Figure 2(a,b) shows exactly this: as the loss decreases, the effective rank converges to one for all dd from 50 to 1,000.
  • Theorem 2, Corollary 1, and Figure 2(c). The query bound of Corollary 1 is independent of dd for a specific class of functions. Figure 2(c) shows exactly this: the median query count is nearly the same for all dd from 50 to 1,000.

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.

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 dd cannot be removed. Standard analyses of ZO-SGD give query bounds that grow with the ambient dimension dd (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 dd 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 UU of a stationary point, and the iterates are assumed to remain in UU; the standard results do not need this. Within UU, the symmetry of the objective replaces the factor dd of the standard bound by K+τ+2K+\tau+2 (Equation (16)). Without symmetry, K=dK=d and τ=0\tau=0, and the bound is of the standard order in dd.

Reviewer_qiHUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks why the low effective rank that makes ZO (MeZO-style) fine-tuning efficient actually arises, and proposes continuous parameter symmetry as the structural explanation. A key conceptual distinction via Examples 1 vs 2: a rotationally-invariant quadratic has symmetry yet full effective rank dd and spherical Θ(dlog⁡1/ϵ)\Theta(d\log 1/\epsilon) query cost, while a translation-invariant objective with orbit codimension rr costs only O(rlog⁡1/ϵ)O(r\log 1/\epsilon). So symmetry is insufficient and the orbit codimension at stationary points is what governs ZO dimension dependence. Motivated by this insight, this paper shows under smooth invariant objective assumption, the Hessian positive-part effective rank is bounded by the orbit codimension k=d−mk=d-m plus a nonstationarity correction mκθ∣∣g∣∣m\kappa_\theta||g||; i.e. tr(H0)≤kℓ+mκθ∣∣g∣∣\mathrm{tr}(H_0)\le k\ell+m\kappa_\theta||g||, so reff≤min⁡d,k+τr_{\mathrm{eff}}\le\min{d,k+\tau} (Thm. 1). And Prop 2 that gives an explicit example ensures that the bound is tight. Then (Thm. 2) under boundedness (Assumption 2) and PL (Assumption 3), finite-sample ZO-SGD converges with a dimension-independent function-query bound depending on KK (the symmetry-induced effective rank) rather than ambient dd, without assuming a common low-effective-rank Hessian upper matrix (weakening Malladi et al. 2023). Finally, they empirically observes effective rank falling along ZO training on a synthetic radial quartic and a 28,930-parameter Transformer.

Critical strengths
  1. A sincerely good question, answered with a sharp and self-aware theory. The Example 1 vs Example 2 comparison forms a good insight: it cleanly refutes the naive "symmetry to low rank" intuition and correctly localizes the operative quantity to orbit codimension at stationarity. Thm 1's decomposition into a codimension term plus an explicit non-station correction mκθ∣∣g∣∣m\kappa_\theta||g||, together with the tightness construction (Prop 2), is a clean and complete theoretical package.
  2. A meaningfully weaker assumption than prior ZO analysis. Deriving dimension-independent query complexity from tr((∇2f)+)≤(K+τ)L\mathrm{tr}((\nabla^2 f)_+)\le(K+\tau)L rather than assuming a shared low-rank Hessian upper bound (as in MeZO's analysis) is a real technical refinement.
Critical weaknesses
  1. The entire motivation is MeZO-scale LLM fine-tuning, yet the largest experiment is a 28,930-parameter Transformer trained on SMS-spam, plus a synthetic quartic. So the experiment is insufficient and lacks applicability.
  2. The paper never measures the symmetry orbit codimension of the trained model and checks that it matches the observed effective rank (log scale ≈1.94\approx1.94). The experiments show only "effective rank decreases as training approaches stationarity": fully consistent with the generic low-rank-Hessian phenomenon that exists without any exact continuous symmetry. Nothing isolates symmetry as the cause, so the headline thesis remains empirically unverified at any scale that matters.
Questions for authors

Please see weaknesses.

  1. Could you compute the symmetry orbit dimension (from the GL(h)\mathrm{GL}(h) / SwiGLU scaling symmetries) for the trained Transformer and show d−md-m matches the observed log-scale effective rank ≈1.94\approx1.94?
  2. Any MeZO fine-tuning result (OPT/Llama) where measured effective rank tracks the predicted orbit codimension and query count stays weakly dimension-dependent or dimension-independent?
  3. Beyond explaining why symmetry yields low effective rank, what concrete guidance does the theory provide for designing ZO algorithms? E.g., can the orbit-codimension bound be used to (a) predict which models/layers will be ZO-trainable before training, (b) choose perturbation directions or a subspace, or (c) select a stepsize? As written, the results appear explanatory but do they change how one would build or tune a ZO optimizer in practice?
2 comments

We sincerely thank the reviewer for the thoughtful review. Below are our point-by-point responses.

W1. The entire motivation is MeZO-scale LLM fine-tuning, yet the largest experiment is a 28,930-parameter Transformer trained on SMS spam, plus a synthetic quartic.

We thank the reviewer for this comment. Our submission does not contain a MeZO-scale experiment, and our main motivation goes beyond MeZO-scale LLM fine-tuning. Our results aim to explain when and how classical zeroth-order optimization can work in high-dimensional optimization problems, even though many minimax optimality results indicate that the complexity scales with the problem dimension. We believe the theoretical interest behind this question plays a more important role than the application itself.

W2. The paper never measures the symmetry orbit codimension of the trained model and checks that it matches the observed effective rank. The experiments show only that the effective rank decreases as training approaches stationarity, which is consistent with the generic low-rank-Hessian phenomenon. Nothing isolates symmetry as the cause.

Q1. Could you compute the symmetry orbit dimension for the trained Transformer and show that kk matches the observed effective rank ≈2\approx2?

Q2. Is there a MeZO fine-tuning result (OPT/Llama) in which the measured effective rank tracks the predicted orbit codimension and the query count stays weakly dimension-dependent or dimension-independent?

We thank the reviewer for these points. The submission indeed contains one such check: the stationary orbit of the objective in Section 5.1 has codimension one, and the measured effective rank converges to one in every dimension from 50 to 1,000 (Figure 2(a,b)).

We have added two further checks in which only the symmetry changes (Appendix C.1 and C.3). In both, the measured effective rank matches the orbit codimension kk, and the query count grows with kk.

  • Synthetic objectives. With d=1000d=1000 fixed and kk from 1 to 1,000, the effective rank equals kk, and the query count grows almost linearly in kk.
  • Two-layer linear networks. With k=64k=64 fixed, increasing dd from 128 to 8,192 changes neither the effective rank (64) nor the query count (about 2,750), so there is no dependence on dd. With d=4,096d=4{,}096 fixed, increasing kk from 16 to 1,024 increases the query count from 751 to 43,240.
  • The Transformer of Section 5.2. The orbit dimension is m=4,806m=4{,}806, so k=d−m=24,124k=d-m=24{,}124 with d=28,930d=28{,}930 (Appendix C.2). The bound of Theorem 1 is an improvement of at least 19.8% over the worst case dd, since mm includes only the symmetries that we identified. Theorem 1 is a worst-case guarantee: not every objective attains it with equality, and on this Transformer the measured effective rank is about 2. However, we emphasize that the bound itself is tight: it is attained by the family of Proposition 2 and by the radial quartic of Section 5.1.

For larger LLM fine-tuning tasks, we emphasize that it could be expensive to evaluate the effective rank; as Malladi et al. (2023) note, it is "prohibitively expensive to directly measure the effective rank of the Hessian" of a large LM. But we believe that symmetry would be the correct direction to explain or motivate the theory behind the usefulness of zeroth-order optimization in LLM fine-tuning.

Q3. Beyond explaining why symmetry yields low effective rank, what concrete guidance does the theory provide for designing ZO algorithms? Can the orbit-codimension bound be used to (a) predict which models or layers will be ZO-trainable before training, (b) choose perturbation directions or a subspace, or (c) select a step size?

We thank the reviewer for this question. The purpose of this work is not to design a new ZO algorithm. It is to explain why the classical ZO-SGD, used without modification, is effective in high-dimensional optimization although classical bounds scale with the ambient dimension. Accordingly, we analyze the classical update of Equation (1), and the symmetry enters only through the analysis. The orbit-codimension bound may not help in choosing the optimal step size, but it is consistent with practice, where ZO-SGD usually converges with step sizes larger than the classical 1/(4Ld)1/(4Ld). For example, in Section 5.1, ZO-SGD converges with the same step size η=0.2\eta=0.2 for every dd from 50 to 1,000. In short, our results are explanatory, as the reviewer notes, and we regard turning them into guidance for designing or tuning ZO optimizers as an interesting future direction.

Thank you for the additional experiments and comments. The substantial gap between the symmetry-induced upper bound (approximately 23,200) and the observed erank (approximately 2) in the Transformer does not address my concern about the explanatory power of the proposed theory in practical neural networks. While I appreciate the theoretical contribution, its practical relevance remains insufficiently established, and I will retain my original score.

Reviewer_AokdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper shows that Zero-order (ZO) optimizers can achieve faster learning on optimization problems which obey a high degree of symmetry, owing to a reduction in effective rank produced by the symmetry. More specifically, symmetry is shown to contribute to a reduction in the Hessian trace, which in turn is used to bound the accelerated ZO convergence rate along with several basic assumptions. Experiments show that the effective rank of the Hessian decreases as training progresses using a ZO optimizer.

Critical strengths
  • By Theorem 2, a useful practical takeaway can be extracted: when using ZO optimizers, designing a more symmetrical architecture can lead to faster learning (by lowering DD and thus allowing for increased learning rate η\eta).
  • The theory presented offers to explain why zero-order optimizers have been shown to require fewer function evaluations than expected in recent research: presence of symmetry in the networks can accelerate learning.
  • The theory offers hints that as a network gains more (parameter-specific) symmetries and/or loses effective rank during the course of it's training, zero-order optimization's convergence rate may improve during training.
Critical weaknesses

Generally, weaknesses stem from communication and clarity, and experimental validation of the theory.

Clarity:

  • Providing a couple definitions about Lie algebra would help, such as orbits, and what it means to exponentiate XX in the definition of ξX(θ)\xi_X(\theta).
  • Equation (3) is difficult to interpret, I can't figure out what this object is supposed to be. Is it the spectral norm of the Jacobian from Lie algebra element to parameters? But if it is, then does there need to be a definition for a norm on the underlying Lie algebra, or is that not necessary?
  • Poorly chosen symbols and messy convoluted definitions, explanations, and notations. They are not wrong nor are any particular examples of these issues major, but the quantity of them makes the paper difficult to understand. A select subset of clarity issues relating to this are presented below:
    • Assumption 2 is very strangely worded, why not say the objective is LL-smooth? Also, LL is usually used for Lipschitz constants common in such analyses, whereas smoothness parameter is usually denoted as β\beta, so the overlap with more common notations is easily misleading.
    • MM is used for the Hessian rather than HH. Taken alone, this is fine, but together with all the other notational practices, the paper becomes difficult to read.
    • (K+τ)L(K + \tau)L is written on Line 337 while Line 341 right after jarringly shows L(K+τ)L(K + \tau) for no particular reason.
    • There is a proliferation of symbols where repeated use of a smaller set of symbols would reduce the number of indirections and references requiring the reader to jump across pages. As one example, in the writing there is use of θ\theta, xx, and even yy, in different places when they all refer to elements of the same space Rd\mathbb{R}^d or UU, which the loss is defined over. There's no reason to be using multiple unrelated symbols where just one would be much clearer.

Other, more minor and fixable weaknesses:

  • Minor typos: "There are a" on line 345, missing period on line 348.
  • I don't see how (13) follows from (12), specifically in the additive constants part? Does plugging in T=1T=1, η\eta large, and D=1/(4η)D=1/(4\eta) break the way (13) flows from (12)?

Alignment of the proposed theory with potential applications:

  • In Remark 3, the bound holds when the codimension KK is independent of dd. But in most use cases, the number of weight dimensions not obeying symmetries (i.e. non-redundant parameters) will increase substantially as we add parameters - that is usually the purpose of adding parameters in the first place. So the bound's independence from dd will almost never be applicable in practical experimental settings.

Scientific methods, and experimental validation of the theory: While a correlation is observed between effective rank and loss when using a ZO optimizer, during a training run. This does not test the hypothesis presented by the theory in the paper, which by the title and abstract, is that symmetry in the network creates a lowered effective rank, which in turn allows faster ZO learning. In a good test of this hypothesis, we should want to perturb the degree of symmetry mm, and measure whether the effective rank (or ZO convergence speed) changes as a result, while controlling for confounding variables such as dd, η\eta, μ\mu, and any other items expected to cloud the conclusion. So from a scientific perspective, we have the following issues with using this experiment as evidence for the theory presented:

  • The independent variable, which is the amount of symmetry in the network, is not being independently controlled and perturbed by the experimenter. In fact, since there is only one architecture in use, only one choice of independent variable is used, so no meaningful causality towards the effective rank can be extracted.

  • The dependent variable, which can either be taken to be the effective rank or the ZO learning rate, is shown to vary across the number of steps. But the number of steps is not supposed to be the independent variable in this hypothesis, rather it's a confounding variable. Rather, we should be looking to fix the number of steps when the effective rank is measured, to ensure it is controlled for while we extract a comparison between symmetry and either effective rank or ZO convergence rate.

  • A method must be provided to perturb the degree of symmetry mm while leaving confounding variables such as dd as fixed as possible. This means training models across different architectures at matched parameter count, or any other group of objective functions with fixed dd but varying mm, but this is not done in the experiments.

  • Overall, as these experiments provide no validation for the theory being posed, I am not sure why the authors chose to include them.

  • In order to practically exploit the theoretically accelerated convergence, you actually need to know what kind of symmetry is present in order to pick the learning rate (since you use knowledge of the symmetry to determine KK, and thus DD, and thus η\eta). While some symmetries are known, many develop during training and are specific to the parameters being trained at the time, and would be difficult to figure out. This may block the results in this paper from becoming useful in a practical training recipe.

Questions for authors
  • Corollary 1 shows a convergence rate which depends on how much symmetry there is. How improved is this convergence rate over the convergence rate under similar assumptions but which does not take into account the symmetry?
  • What are some typical values of kk versus mm in a scenario where this theory may become useful to understand? Or, how do the dd parameters of GPT-2 split up into kk versus mm?
  • Putting together the two points above, how much numerical gain might we expect this theory to provide, in terms of convergence speed in a usage scenario, as a result of the symmetry?
  • If we do some measurements in neural network training experiments, how tight is inequality (4) of Theorem 1, and what are the values of the variables involved? I am fearing that ∣g∣|g| may be proportionally too large, rendering the bound weak and in turn the theory's conclusions non-instructive.
3 comments

We sincerely thank the reviewer for the careful and detailed review. Below are our point-by-point responses.

W1 (Clarity). (i) Define the Lie-group notions that are used, such as orbits and the exponential in the definition of ξX\xi_X. (ii) Equation (3) is difficult to interpret: is it the spectral norm of a Jacobian from the Lie algebra to the parameters, and does it need a norm on the Lie algebra? (iii) Assumption 2 is strangely worded: why not say that the objective is LL-smooth? Also, LL usually denotes a Lipschitz constant. (iv) Notation: MM is used for the Hessian; (K+τ)L(K+\tau)L appears on Line 337 and L(K+τ)L(K+\tau) on Line 341; several symbols (θ\theta, yy, xx) denote points of the same space.

(i) We thank the reviewer for this suggestion. We have added an introduction to Lie groups at the beginning of Appendix A.

(ii) We thank the reviewer for this question. For a fixed XX, ξX\xi_X is a vector field on the parameter space, and DξX(θ)D\xi_X(\theta) is its d×dd\times d Jacobian with respect to θ\theta, not with respect to XX. Hence ∥DξX(θ)∥op\\\|D\xi_X(\theta)\\\|_{\rm op} is the spectral norm of a d×dd\times d matrix, and no norm on the Lie algebra is needed: the normalization is the constraint ξX(θ)=q\xi_X(\theta)=q with ∥q∥=1\|q\|=1, in the parameter space. Geometrically, κθ\kappa_\theta measures how curved the orbit is at θ\theta: it is 00 for the translations of Example 2 and 1/∥θ∥1/\|\theta\| for the rotations of Example 1. This explanation is now in Appendix A as well.

(iii) We thank the reviewer for this question. Assumption 2 is not LL-smoothness. Its first part, ℓy≤L\ell_y\le L, is the one-sided bound ∇2f(y)⪯LId\nabla^2f(y)\preceq LI_d of Equation (8), which does not restrict negative curvature. The other two parts, ky≤Kk_y\le K and myδy≤τLm_y\delta_y\le\tau L, concern the symmetry orbit and have no counterpart in a smoothness assumption. The constant LL plays the role of the usual smoothness constant, as an upper bound on the Hessian.

(iv) We thank the reviewer for these observations. We have explicitly defined the notation in the revised manuscript and corrected the typo.

W2 (Minor). (i) Typos on Lines 345 and 348. (ii) How does (13) follow from (12), specifically in the additive constants? Does plugging in T=1T=1, η\eta large, and D=1/(4η)D=1/(4\eta) break the way (13) flows from (12)?

(i) We thank the reviewer for catching these; both are corrected in our revised manuscript.

(ii) We thank the reviewer for the question. Write Δt=E[f(θt)−f⋆]\Delta_t=\mathbb E[f(\theta_t)-f^\star], ρ=1−ην/2\rho=1-\eta\nu/2, and c=η2Dσ2+ηAη,λeμ2c=\eta^2D\sigma^2+\eta A_{\eta,\lambda}e_\mu^2. Applying Equation (12) at every step gives Δt+1≤ρΔt+c\Delta_{t+1}\le\rho\Delta_t+c with 0<ρ<10<\rho<1, and therefore

ΔT  ≤  ρTΔ0+c∑t=0T−1ρt  ≤  ρTΔ0+c1−ρ  =  ρTΔ0+2cην.\Delta_T\;\le\;\rho^T\Delta_0+c\sum_{t=0}^{T-1}\rho^t\;\le\;\rho^T\Delta_0+\frac{c}{1-\rho}\;=\;\rho^T\Delta_0+\frac{2c}{\eta\nu}.

The additive constant of Equation (13) is 2cην=2ηDσ2+2Aη,λeμ2ν\frac{2c}{\eta\nu}=\frac{2\eta D\sigma^2+2A_{\eta,\lambda}e_\mu^2}{\nu}, and the first term follows from ρT≤e−ηνT/2\rho^T\le e^{-\eta\nu T/2}. This is the step "Summing the geometric series, whose sum is at most 2/(ην)2/(\eta\nu)" in Appendix A.6.

The choice T=1T=1, η\eta large, and D=1/(4η)D=1/(4\eta) does not break this step, because such an η\eta cannot be large: D≥L≥νD\ge L\ge\nu (Appendix A.5), so D=1/(4η)D=1/(4\eta) gives ην=ν/(4D)≤1/4\eta\nu=\nu/(4D)\le1/4. For T=1T=1, Equation (12) is Δ1≤ρΔ0+c\Delta_1\le\rho\Delta_0+c, and Equation (13) follows from ρ≤e−ην/2\rho\le e^{-\eta\nu/2} and c≤2cηνc\le\frac{2c}{\eta\nu}, which holds since ην≤2\eta\nu\le2.

W3. In Remark 3, the bound is dimension-independent only when the codimension KK does not depend on dd. In most use cases the number of non-redundant parameters grows substantially when parameters are added, so the independence from dd will almost never apply.

Q1. How much does the rate of Corollary 1 improve over the rate under similar assumptions that does not take the symmetry into account?

Q2. What are typical values of kk versus mm in a scenario where the theory is useful? How do the dd parameters of GPT-2 split into kk versus mm?

Q3. Putting these together, how much numerical gain in convergence speed can be expected?

We thank the reviewer for these points. To address the concern in W3, we answer the three questions below.

  • (Q1) Without taking the symmetry into account, the best possible query complexity is linear in the ambient dimension dd, namely O(dϵlog⁡1ϵ)O\big(\frac{d}{\epsilon}\log\frac{1}{\epsilon}\big). Corollary 1 replaces dd with K+τ+2K+\tau+2 and gives O(K+τϵlog⁡1ϵ)O\big(\frac{K+\tau}{\epsilon}\log\frac{1}{\epsilon}\big), an improvement by a factor of about d/(K+τ+2)d/(K+\tau+2).

  • (Q2) The values of kk and mm depend on the function class. When the added parameters are redundant, as in the first two examples below, kk does not grow with dd.

    • In Example 2, the symmetry gives m=d−rm=d-r, so k=rk=r, which does not depend on dd.
    • In a two-layer linear network with 8 inputs, 8 outputs, and width hh, we have d=16hd=16h and k=64k=64 for every width. For example, width 512 gives d=8,192d=8{,}192, m=8,128m=8{,}128, and k=64k=64, which is much smaller than dd.
    • In Transformers, kk grows with dd but remains smaller than dd, so the bound still improves on the classical theory. With the symmetries that we identified, the Transformer of Section 5.2 has d=28,930d=28{,}930, m=4,806m=4{,}806, and k=24,124k=24{,}124 (about 83% of dd). In GPT-2 small, d≈1.24×108d\approx1.24\times10^8, and the symmetries of the form of Example 3 alone give m≈1.18×106m\approx1.18\times10^6 and k≈1.23×108k\approx1.23\times10^8. Both counts include only the symmetries that we identified, so they are lower bounds on mm.
  • (Q3) The table below lists the gain in three examples.

ExampleddK+τK+\tauGain d/(K+τ+2)d/(K+\tau+2)
Synthetic objective with k=1k=1 (Appendix C.1)1,0002.41227×
Two-layer linear network of width 512 (Appendix C.3)8,19267.5118×
Two-layer Transformer of Section 5.2 (Appendix C.2)28,93024,1301.2×

That is, our theory explains why ZO-SGD performs much better than the lower bounds of the classical theory suggest.

W4. The experiments do not test the hypothesis of the paper. The degree of symmetry mm is not varied by the experimenter, and the number of steps is a confounding variable. A valid test perturbs mm while controlling for confounding variables such as dd, η\eta, and μ\mu, for example across architectures at matched parameter count, or across a family of objectives with fixed dd and varying mm.

Q4. In neural network training, how tight is inequality (4) of Theorem 1, and what are the values of the variables involved? ∥g∥\|g\| may be proportionally too large, rendering the bound weak.

We thank the reviewer for this suggestion. Following it, we have added an experiment that fixes dd and varies mm (Appendix C.1). We use the family of Proposition 2 at d=1,000d=1{,}000 and increase the symmetry step by step, from no symmetry (m=0m=0) to m=999m=999:

Orbit dimension mm (with d=1,000d=1{,}000)0 (no symmetry)900990999
Orbit codimension k=d−mk=d-m1,000100101
Effective rank at the target1,000.0100.010.001.00
Median queries, η=1/(4D)\eta=1/(4D)42,0474,285509149

As the symmetry increases with dd fixed, the effective rank falls with kk, as Theorem 1 predicts, and the query complexity decreases, from 42,047 queries to 149. This validates our theory. Two-layer linear networks at matched parameter count show the same behavior (Appendix C.3).

Regarding neural network training, we measured the quantities of inequality (4) on the Transformer of Section 5.2 at its saved iterates (Appendix C.2). This model has d=28,930d=28{,}930 parameters. The exact continuous symmetries of the architecture that we identified span m=4,806m=4{,}806 directions, of which 4,096 are of the form of Example 3, so k=d−m=24,124k=d-m=24{,}124. This indicates that our theory accounts for a reduction of about 16.6% in the query complexity of training this Transformer, a factor of about 1.2.

W5. One may need to know the symmetry in order to pick the learning rate.

We thank the reviewer for raising this point. The algorithm we analyze is plain ZO-SGD (Equation (1)). It does not take the symmetry group, KK, or τ\tau as input; these quantities appear only in the analysis. As with the smoothness constant in first-order methods, the step size is tuned in practice.

Thank you for responding to my concerns. On your responses:

(i) Introduction to Lie groups: Thank you for including the explanation, it is very clear and defines all necessary concepts.

(ii) Thank you for the clarification, this concern is resolved as well.

(iii) I see, Assumption 2 is only one side of the smoothness condition. It can still be helpful and more concise to explain it as such As LL in your case plays the typical role of a smoothness constant, I would suggest switching it out for a more conventional symbol typically used for this purpose, such as β\beta, for sake of readability. I still also believe other parts of Assumption 2 are poorly written since there are many easy ways to make the statement easier to read, such as removing the trivially true condition on existence of K, definition of δy\delta_y which is never used again, and probably more unnecessary indirections elsewhere too.

(iv) Not much has changed in the revised version. I would have preferred, as a bare minimum in terms of notational convention, if at least all elements of the same set were Greek letters or all were Latin letters, and to not mix the two which inhibits readability.

On the minor weaknesses listed: Thank you for showing me the derivation, my concerns are resolved.

On (W3), (Q1), (Q2), and (Q3): As demonstrated by the calculations requested, the improvement of the bound (over one that does not require considering symmetry) rapidly vanishes as the problem grows more realistic. By the time we get to GPT-2, it is already less than 1% better than a bound that does not require symmetry. So I do not believe the symmetry argument for faster learning will be of any practical use. Fundamentally the bound's effectiveness is limited to small and unrealistic settings, and I cannot think of any scenario where it can ever become useful to know the bound you presented, let alone one which specifically uses ZO optimization, because the same bound without symmetry considerations will be basically equally effective. This is the largest core issue which greatly affects my decision on what score I give to this paper.

On the experimental design, I appreciate the new results which provide the theory with a basic level of empirical validation, albeit with an unrealistic toy task designed for the purpose.

As for the small Transformer mentioned where the bound is 1.2x more effective than a non-symmetry-based bound, I estimate the 1.2 factor will decrease drastically when the MLP dim is increased from 0.5x the model dimension to a typical practical size of 2-4x the model dimension. It will also decrease drastically decrease once again when the number of heads is increased above 1, due to most of the symmetries being counted like the square of the head dimension (due to redundancy between Q/K weights and V/O weights).

Based on the quality of the notation/writing and the fundamental issue of the bound becoming incredibly weak (in comparison to a similar non-symmetry bound) when brought to realistic scenarios, I intend to keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.