acceptodds
Under review as a conference paper at ICLR 2027

Stability and Generalization of Decentralized Riemannian Stochastic Gradient Descent

Abstract

Generalization bounds for Euclidean decentralized SGD rely on the nonexpansiveness of averaging. Manifold projection can amplify perturbations caused by replacing a training sample, complicating the extension of these guarantees to manifold constraints. We analyze stochastic decentralized projected Riemannian gradient descent (DPRGD) on compact smooth embedded manifolds without boundary. By bounding projection expansion through consensus error, we derive a stability-based generalization bound whose additional geometric factor is controlled by the sum of squared step sizes. Motivated by this analysis, we propose DPRGD-ATC, an adapt-then-combine variant that averages locally updated models before projection. Under the same assumptions, step sizes, and communication budget, we prove a tighter generalization bound by reducing the terms associated with consensus error. A local curvature construction further shows that DPRGD-ATC can have strictly lower sensitivity to a single-sample replacement. We also establish empirical stationarity guarantees for both methods and compare their network-dependent error terms. Experiments on synthetic PCA across three geometries and on Fashion-MNIST with up to 32 agents illustrate these geometric effects.

Primary area:
optimization
Keywords:
Decentralized learning, Riemannian optimization, Algorithmic stability, Generalization bounds, Consensus error.

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_e7AFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper investigates the stability and generalization properties of decentralized projected Riemannian stochastic gradient descent (DPRGD) on compact smooth embedded manifolds.

The authors derive stability-based generalization bounds by relating the expansion induced by manifold projection to consensus errors and showing that the additional geometric factor can be controlled through the accumulated squared step sizes.

Motivated by this analysis, they introduce DPRGD-ATC, an adapt-then-combine variant that averages locally updated models before projecting them onto the manifold. They establish tighter stability and generalization upper bounds than for DPRGD under identical assumptions and communication budgets. A local geometric construction further demonstrates that DPRGD-ATC can achieve strictly lower sample sensitivity. The authors also establish empirical stationarity guarantees for both algorithms.

The theoretical results are complemented by numerical experiments involving synthetic PCA problems on sphere, Stiefel, and Grassmann manifolds, together with an application to subspace learning on Fashion-MNIST.

Critical strengths

The paper addresses an important difficulty in extending Euclidean stability results to manifold-constrained optimization, namely the possible amplification of perturbations by the projection operator. Relating this amplification to consensus errors and controlling its accumulation through squared step sizes provides an interesting theoretical contribution. The analysis also makes explicit the respective influences of manifold geometry and network topology on generalization guarantees.

The proposed DPRGD-ATC algorithm is a natural extension of the adapt-then-combine strategy to manifold-constrained optimization. The authors establish that changing the order of local adaptation and combination reduces the consensus-dependent terms in the stability upper bound without increasing the per-iteration communication budget. The local construction relating the improvement in sample sensitivity to manifold curvature is also of interest, as it demonstrates that the benefit can extend beyond the comparison of theoretical upper bounds.

The additional stationarity analysis and the numerical experiments across several manifold geometries further strengthen the theoretical investigation.

Critical weaknesses

The main theoretical result establishes that DPRGD-ATC admits a tighter stability-based generalization upper bound than DPRGD. However, improving an upper bound does not necessarily imply a corresponding improvement in actual algorithmic stability or generalization performance.

This distinction is particularly important in view of the numerical results. Although the reported stability upper bounds decrease substantially in the synthetic experiments, the observed differences in sample sensitivity and generalization are much smaller and generally not statistically significant. On Fashion-MNIST, the experiments with identical parameters also show nearly indistinguishable generalization performance between the two algorithms. The additional experiments with a fixed DPRGD baseline provide statistically significant improvements in the pooled absolute generalization gap, but their practical magnitude remains extremely small.

Overall, although the theoretical improvement is mathematically interesting, the numerical evidence does not convincingly establish that it translates into a practically meaningful improvement in generalization performance.

--

The main comparison between DPRGD and DPRGD-ATC relies on relatively restrictive assumptions, including sufficiently small deterministic step sizes and a strong mixing condition requiring the network contraction factor to satisfy (sigma<1/2).

The latter condition may entail substantial communication costs on poorly connected networks, raising questions about the practical scalability of the theoretical guarantees.

Furthermore, the Fashion-MNIST experiments use step sizes that fall outside the sufficient conditions of the theoretical analysis, while several network configurations do not satisfy the strong mixing requirement. Although these experiments demonstrate that the algorithms can operate beyond the theoretically covered regime, they do not establish whether the guaranteed ordering of the stability upper bounds remains valid or informative in these more practical settings.

A more systematic investigation of the influence of step size, network connectivity, and communication costs would help clarify the conditions under which DPRGD-ATC provides a significant advantage.

Questions for authors

The theoretical stability bounds show a substantial improvement for DPRGD-ATC, whereas the empirical differences in sample sensitivity and generalization are generally very small. Could the authors explain this discrepancy and provide further insight into the tightness of the bounds? Under which conditions should one expect the theoretical advantage to translate into a meaningful improvement in generalization performance?

2 comments

Part 1/2

Thank you for asking about statistical gains, assumptions and costs.

1. Weakness: Bounds and actual statistical performance

  • Theorem 3 orders uniform bounds; Proposition 4 proves a strict actual local effect under specified geometry and data conditions. For each manifold in the stated class, it constructs an instance with lower ATC replacement sensitivity (Section 4.1).

  • Both orderings agree in an admissible circle experiment. At η=η∗=0.004238021180\eta=\eta_*=0.004238021180, replacement size 10−310^{-3}, Appendix G.2 gives:

QuantityDPRGDDPRGD-ATC
Complete bound1.4186×10−41.4186\times10^{-4}1.4129×10−41.4129\times10^{-4}
Expected absolute replacement loss change7.063410921×10−87.063410921\times10^{-8}7.063368633×10−87.063368633\times10^{-8}

Summation uses 80-digit arithmetic. The ordering agrees with the derivative ratio 3/(1+2/1+η2)>13/(1+2/\sqrt{1+\eta^2})>1 and its quadratic step scale.

  • The statistical quantities are distinguished: stability bounds ∣Egen⁡∣|\mathbb E\operatorname{gen}|; experiments also measure E∣gen⁡∣\mathbb E|\operatorname{gen}| and average replacement sensitivity. Their percentage reductions need not coincide.

2. Weakness: Magnitude and practical significance

  • Geometric improvements are clear at comparable learning quality; matched-parameter average-gap intervals contain zero. Common decaying steps satisfy the theorem, with complete bounds 0.0133 versus 0.0117, a 12.22% reduction below the loss range. Consensus error falls 78.98% and maximum projection distance 56.13%, with essentially equal risk decreases. The absolute-gap difference interval is [−8.392,2.260]×10−9[-8.392,2.260]\times10^{-9} (Appendix G.1).

  • Observed distances explain one source of the difference in effect sizes.

DiagnosticDPRGDDPRGD-ATC
Maximum observed/bounded distance0.01660.0127
Mean observed-distance product minus one3.7354×10−53.7354\times10^{-5}1.0657×10−51.0657\times10^{-5}
Uniform-distance projection product1.31201.0344

Observed products are close to one; actual sensitivity also depends on direction, loss and data distribution. Fashion-MNIST consensus ratios A/B are 0.208, 0.499, 0.686, 0.803 at 4, 8, 16, 32 agents, with comparable risks. E6 reports separate tuning results.

3. Weakness: Small steps and strong mixing

  • Both DPRGD and ATC use small-step and mixing safeguards to control manifold projection. These keep update inputs and final means in a tube with unique projection and controlled expansion. Baseline DPRGD has analogous safeguards in Lemmas 5.5-5.6, with contraction 2λk2\lambda^k. We control both neighboring-data trajectories for every sampling sequence; ATC uses the same admissible configuration and budget. Deng and Hu, Section 5.2

  • The main threshold also gives bound ordering. For σ<1/2\sigma<1/2,

    =a(1-\sigma^2)\delta_t^2+C_1(1-2\sigma)\delta_t\eta_tG\ge0, \quad a=\frac1{2\tau}+\frac{C_1}{2}.$$ Here $\delta_t$ bounds node distance, $G$ bounds gradients, and $\tau,C_1$ are geometric constants.
  • Individual guarantees allow weaker mixing: Appendix A.10 uses Lhσ<1L_h\sigma<1, Lh=(1−h/(4τ))−1L_h=(1-h/(4\tau))^{-1}, and its own step threshold. Every fixed σ<1\sigma<1 permits sufficiently small hh and steps. Main bound ordering additionally uses the nonnegative difference above; decreasing steps alone leaves σ\sigma unchanged.

4. Weakness: Communication on poorly connected networks

  • Strong mixing can require many rounds; at a fixed setting both algorithms have identical communication costs. For the lazy ring, σ=cos⁡2k(π/m)\sigma=\cos^{2k}(\pi/m). At 32 agents:
Rounds kkσ\sigmaMain step thresholdRounds at T=2048T=2048
20.9809mixing fails4096
720.49901.5038×10−61.5038\times10^{-6}147456
1440.24903.8020×10−43.8020\times10^{-4}294912
  • The minimum is 72 rounds, an analytical calculation; training uses 2 or 144. The stronger settings cost 36 or 72 times the two-round case. More mixing permits a larger certified step; fixed target contraction on this ring requires k=Θ(m2)k=\Theta(m^2).

  • ATC adds no communication within a setting. Both methods exchange equal-sized vectors and use equal gradient counts. Table 13 gives costs; Table 20 gives conditions. Single-server simulations report algorithmic costs, not measured distributed speedup.

Part 2/2

5. Weakness: Fashion-MNIST and theorem conditions

  • Fashion-MNIST evaluates empirical performance beyond the sufficient step thresholds, using fixed multi-round communication. It retains all 784 pixels, St⁡(784,8)\operatorname{St}(784,8), 4096 training images and T=2048T=2048. Separate development data select η=0.1\eta=0.1. We compute Q=WkQ=W^k, charge kk neighbor exchanges, and check projection validity numerically.
AgentsRoundsσ\sigmaMain step threshold
420.25001.0151×10−31.0151\times10^{-3}
820.7286mixing fails
1620.9253mixing fails
3220.9809mixing fails
321440.24903.8020×10−43.8020\times10^{-4}
  • The step exceeds both main and weaker individual thresholds. Appendix G.3 gives the status; the experimental-details attachment retains weaker-mixing thresholds. These runs test high-dimensional learning and network effects. Stiefel and circle experiments separately verify bounds and local loss responses within the certified regime. Steps and communication remain fixed during each run.

6. Weakness: Parameter, network and resource assessment

  • Common-parameter comparisons quantify network dependence; separate tuning uses independent validation. At η=1/2720\eta=1/2720, T=512T=512, twenty shared Stiefel pairs give (Table 19):
kkσ\sigmaB boundA boundReductionTotal rounds
21/40.03100.022826.52%1024
31/80.02580.022114.19%1536
41/160.02480.022011.22%2048

All satisfy the conditions. More communication improves both bounds and reduces ATC's relative advantage. ATC has lower consensus error; sensitivity and absolute-gap intervals contain zero. Constant and square-summable comparisons share data, sampling prefixes and initialization.

  • Independent tuning quantifies resource savings and statistical changes. The added synthetic search evaluates 50 configurations (steps up to 10 and deterministic decays), screens eight on fresh data, and freezes one before 100 untouched validation pairs. Appendix G.4 retains selection rules, results and costs; the attachment gives all search records.
EvaluationGap reductionDifference A-BPaired 95% interval
Fashion-MNIST, pooled0.029%−0.679×10−6-0.679\times10^{-6}[−1.324,−0.079]×10−6[-1.324,-0.079]\times10^{-6}
Synthetic, 100 pairs0.5267%−1.0565×10−5-1.0565\times10^{-5}[−1.2113,−0.9044]×10−5[-1.2113,-0.9044]\times10^{-5}
  • Both configurations halve communication. Fashion-MNIST retains baseline steps and length; over 50 new pairs per node count, the smallest mean progress ratio across both risks and all node counts is 100.001% (Appendix F). Synthetic progress is 99.476%: its 0.524% decrease accompanies a population-risk increase of 1.1876×10−41.1876\times10^{-4}. This tuned configuration has σ=1/2\sigma=1/2 and is evaluated empirically. These results describe joint tuning effects on resources, learning and statistics.

7. Question: Tightness and conditions for actual gains

  • Proposition 4 gives sufficient conditions for strict local sensitivity improvement; diagnostics quantify conservatism on tested trajectories. Worst-case tightness requires a matching lower bound for the same uniform quantity. Projection and loss bounds cover all perturbation directions.

  • Geometry and data jointly yield the local effect. With nonzero normal curvature, opposing outer-node samples, a middle-node replacement along a unit tangent vv, common initialization and exact averaging,

    =\frac{\eta^2}{3}\|\mathrm{II}_x(v,v)\|^2+o(\eta^2).$$ The second fundamental form $\mathrm{II}$ gives a positive coefficient. Small admissible steps and replacements yield strict finite-loss ordering (E1).
  • Larger average benefits would require these effects to occur often under the data distribution. Different local gradients, larger projection distances and replacements along expanding directions are hypotheses to examine at comparable learning quality; Proposition 4 proves the local effect.

Reviewer_3AAKOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the stability and generalization of stochastic decentralized projected Riemannian gradient descent (DPRGD). Unlike in Euclidean space, manifold projection can amplify perturbations caused by replacing a training sample. The authors first analyze DPRGD: averaging the agents’ models, taking a local Riemannian gradient step, and projecting back onto the manifold. Then they propose DPRGD-ATC, which reverses the order: update locally, average, then project. DPRGD-ATC has smaller consensus error and therefore a tighter bound.

Critical strengths
  1. The paper identifies a concrete geometric obstruction: Euclidean averaging does not increase the average perturbation, whereas nearest-point projection expands it by 1/(1−r/τ)1/(1-r/\tau). Then the authors control the pre-projection distance by the consensus error, which makes the extra factor depend on ∑ηt2\sum\eta_t^2, making the manifold extension of the Euclidean stability recursion possible.

  2. The authors propose another algorithm, DPRGD-ATC, which improves the extra factor as well as the stability bound under the same budget.

Critical weaknesses
  1. The generalization bound is dominated by the Euclidean product ∏(1+ηtLg)\prod(1+\eta_t L_g). Under the standard step size η=cT−1/2\eta=cT^{-1/2}, the product is of order exp⁡(Θ(T))\exp(\Theta(\sqrt{T})), which is not desirable compared with 1/mn1/\sqrt{mn} in Zeng and Lei (ICML 2025). They also require the gradient Lipschitzness condition, which is removed in Zeng and Lei (ICML 2025) for the Euclidean case.

  2. The improvement of DPRGD-ATC seems to exist only in the upper bound (but the bound is vacuous), and the claimed benefit of DPRGD-ATC seems to be unclear in the experiments.

Questions for authors
  1. Could the authors discuss the difficulty in getting a non-vacuous stability bound under the standard step size choice?

  2. Could the authors explain more about how DPRGD-ATC improves generalization over DPRGD from both the perspectives of theory and experiments?

5 comments

Part 1/2

Thank you for recognizing the geometric obstruction and ATC analysis. We address nonconvex propagation, the convex comparison and evidence of actual improvement.

1. Weakness 1 and Question 1: Growth of the bound and the convex comparison

  • For the reviewer's step choice, the bound retains growing nonconvex gradient propagation, while the extra manifold factor stays bounded independently of the horizon. The cited Zeng-Lei rate uses convexity; our analysis controls the additional stability cost of nonlinear projection.

  • Complete bounds are informative at the evaluated horizons. Stiefel uses m=4m=4, n=40n=40, T=512T=512, σ=1/4\sigma=1/4. Both ηt=1/2720\eta_t=1/2720 and ηt=(1/2720)/(1+t/512)\eta_t=(1/2720)/(1+t/512) satisfy ηt≤η∗=0.001015128789\eta_t\le\eta_*=0.001015128789:

Common scheduleDPRGDDPRGD-ATC
Constant0.03100.0228
Decaying0.01330.0117

These complete bounds include output projection and are below the loss range of one. Decaying steps give a 12.22% reduction while both methods lower population risk from 0.7500 to about 0.7350. Appendix G.1 checks geometry, sampling, initialization, steps and mixing.

  • The cited convex rate uses different assumptions and a different stability quantity. Zeng-Lei's Theorem 4.1 assumes convex, smooth losses: it removes loss Lipschitzness but retains gradient Lipschitzness, and bounds squared on-average model stability. Our result bounds uniform expected loss stability. Their Theorem 5.1 and Corollary 5.2 relax gradient regularity under convexity. Co-coercivity enables sharper convex propagation estimates. Zeng and Lei, ICML 2025

  • Nonconvex updates explain the propagation factor. For Uη(x)=x−η∇f(x)U_\eta(x)=x-\eta\nabla f(x), ∥Uη(x)−Uη(y)∥≤(1+ηL)∥x−y∥\|U_\eta(x)-U_\eta(y)\|\le(1+\eta L)\|x-y\|; a negative Hessian eigenvalue −λ-\lambda gives local amplification 1+ηλ1+\eta\lambda. Iterating this estimate at η=c/T\eta=c/\sqrt T yields exp⁡(LgcT+O(1))\exp(L_gc\sqrt T+O(1)).

    Hardt et al. (Theorem 3.8) and Le Bars et al. (Theorem 4.1) obtain polynomial bounds with harmonic steps and first-replacement-time arguments. Lei, Sun and Liu (Theorem 7) retain ∏j>k(1+ηjL)\prod_{j>k}(1+\eta_jL) for nonconvex minibatch SGD. These are distinct analyses of nonconvex propagation; our result controls the extra geometric cost. Hardt et al., ICML 2016; Le Bars et al., ICML 2024; Lei et al., ACHA 2025

2. Weakness 1 and Question 1: Controlling the additional manifold cost

  • For the review's step choice, the additional geometric multiplier is bounded independently of the horizon. A fixed projection Lipschitz estimate greater than one would introduce an additional exponential-in-TT factor. Our joint proof controls consensus and the projection neighborhood for both neighboring-data trajectories and every sampling sequence. Under the stated trajectory conditions, the resulting second-order distance estimate gives

    =\exp(C_{\mathrm{geom}}c^2) \quad\text{when }\eta_t=c/\sqrt T.$$ Thus the full bound retains the basic nonconvex propagation term, while the extra manifold factor stays bounded independently of $T$. ATC reduces the projection factors at equal gradient and communication budgets (Section 3 and Appendix A.5). The decaying-step experiment in A1 gives geometric estimate **2.1842** and complete bounds below the loss range.
  • As an additional schedule-specific result, harmonic steps give polynomial horizon dependence. Corollary 13 gives, for ηt=c/(t+1)\eta_t=c/(t+1), 0<c≤η∗0<c\le\eta_* and Lg>0L_g>0,

    \le\frac{2L_0G}{NL_g} e^{C_{\mathrm{geom}}c^2\pi^2/6} \big(e^{cL_gH_T}-1\big),\qquad H_T=\sum_{j=1}^Tj^{-1}.$$ Since $H_T\le1+\log T$, the bound has polynomial horizon dependence and an explicit $1/N$ factor. Appendix A.5 supplies the proof and the $L_g=0$ case. This also gives a concrete schedule for controlling propagation while retaining the ATC comparison.

Part 2/2

3. Weakness 2 and Question 2: Actual sensitivity and measured benefits

  • The improvement is established in the upper bounds and in the actual local loss response of Proposition 4. In training, the clearest matched-parameter gains are lower consensus error and projection distance; separate tuning experiments show communication savings at comparable learning quality. For every manifold in the stated class, Proposition 4 constructs a learning instance using a point and unit tangent direction with IIx(v,v)≠0\mathrm{II}_x(v,v)\ne0. Under the specified three-node linear losses, common initialization, exact averaging and middle-node replacement, the expected test-loss responses satisfy

    =1+\frac{\eta^2}{3}\|\mathrm{II}_x(v,v)\|^2+o(\eta^2)>1$$ for sufficiently small admissible steps. Here $\mathrm{II}$ is the second fundamental form and the expectation is over sampling indices. Theorem 3 supplies the general bound ordering; this construction establishes an actual, curvature-driven sensitivity improvement.
  • Bounds and observable losses have matching order in an admissible instance. Appendix G.2 evaluates the circle construction at η=η∗=0.004238021180\eta=\eta_*=0.004238021180 and replacement size 10−310^{-3}:

QuantityDPRGDDPRGD-ATC
Complete stability bound1.4186×10−41.4186\times10^{-4}1.4129×10−41.4129\times10^{-4}
Expected absolute replacement loss change7.063410921×10−87.063410921\times10^{-8}7.063368633×10−87.063368633\times10^{-8}

The finite-replacement ordering agrees with the exact analytic ratio 3/(1+2/1+η2)3/(1+2/\sqrt{1+\eta^2}). Exact summation uses 80-digit arithmetic. This verifies the strict local effect and its predicted quadratic step scale in an admissible instance; Proposition 4 establishes the underlying construction throughout the stated manifold class.

  • Training shows substantial reductions in the quantities driving the bound. With common parameters, the decaying-step Stiefel experiment reduces mean final consensus error by 78.98% and mean maximum pre-projection distance by 56.13%, with essentially identical learning progress. The absolute-gap difference has paired 95% interval [−8.392,2.260]×10−9[-8.392,2.260]\times10^{-9}, so its average statistical effect remains unresolved at that scale. Matched-parameter Fashion-MNIST results similarly show lower consensus error with comparable risks and generalization (Table 3).

  • Supplementary independent validation quantifies communication and learning quality. On Fashion-MNIST, the frozen ATC configuration keeps the baseline step and horizon, uses half the communication, and preserves reference- and empirical-risk progress at all four node counts: the smallest observed mean progress ratio is approximately 100.001%, over 50 new pairs per node count. The pooled absolute reference gap decreases by 0.029%, with difference −0.679×10−6-0.679\times10^{-6} and paired 95% interval [−1.324,−0.079]×10−6[-1.324,-0.079]\times10^{-6} (Appendix F). The main practical finding is the communication reduction at comparable learning quality.

    A separate synthetic configuration, frozen before 100 untouched validation pairs, also halves communication and retains 99.476% of baseline learning progress. Its mean absolute gap decreases by 0.5267%: difference −1.0565×10−5-1.0565\times10^{-5}, interval [−1.2113,−0.9044]×10−5[-1.2113,-0.9044]\times10^{-5}. Population risk increases by 1.1876×10−41.1876\times10^{-4}. The measured gap change accompanies a roughly 0.524% reduction in learning progress and characterizes this resource–learning tradeoff. This configuration has σ=1/2\sigma=1/2 and is evaluated empirically (Appendix G.4). The common-parameter theorem and local construction above provide the update-order comparison.

Thanks for the response, which addresses my concerns.

I have a further question. When m=1m=1, we have Q=J=[1]Q=J=[1] and σ=0\sigma=0, and DPRGD and DPRGD-ATC are exactly in the centralized case xt+1=PM(xt−ηtgt).x^{t+1}=P_{\mathcal M}(x^t-\eta_tg_t).

Then E(Xt)=D(Xt)=0E(X^t)=D(X^t)=0. However, Theorem 2 still gives et+1=2ηtG>0e_{t+1}=2\eta_tG>0, which introduces extra factors for DPRGD, while Theorem 3 gives a zero consensus bound for ATC.

Could the authors clarify the difference? Please distinguish the improvement from the algorithm and from the proof techniques.

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

The paper derives stability and expected generalization bounds for decentralized Riemannian SGD and an adapt-then-combine variant on compact embedded manifolds. It establishes an ordering of these bounds under stated conditions, complemented by a local sensitivity construction, stationarity analysis, and PCA experiments.

Critical strengths
  1. The problem is well posed and genuinely under-addressed: existing decentralized manifold work is analyzed for consensus and optimization convergence, and the paper quantified how projection and consensus error jointly drive sensitivity to a replaced training sample.

  2. The ATC proposal is not an arbitrary engineering solution but is derived from the theoritical analysis. The logic from bound to algorithm is coherent.

  3. The experimental program is convincing, including three geometries, a numerical-differentiation check of the circle sensitivity ratio, verification of the predicted quadratic distance-versus-consensus scaling, and a real-data study.

Critical weaknesses
  1. The bound comparison is not demonstrated inside the regime where the theorem applies.

  2. The strictly-lower-sensitivity claim is an existence statement, not a general one.

Questions for authors
  1. Can you provide any experiment in which the ordering of the bounds is checked against the ordering of an observable error?

  2. Please add a bound-comparison experiment with decaying steps such that Ση_t² is bounded and the small-step thresholds hold, and report the actual value of exp(C_geom Ση_t²) so readers can see that the multiplier is non-trivial.

  3. The local curvature construction gives an existence witness. Please state explicitly the curvature/geometry conditions under which A ≤ B for sensitivity. If no general ordering is intended, please soften the phrasing of the informal theorem so that it is not read as universal.

  4. Can you make the V_ν comparison quantitative, i.e. give the two methods' E_ν* and q_ν bounds side by side and show where the separation comes from?

2 comments

Part 1/2

1. Weakness 1: Bound comparison inside the theorem's regime

  • The complete bounds are ordered within the theorem's regime. Section 6 and Appendix G.1 provide an explicit verification of the assumptions for both the original constant-step comparison and the added common decaying-step experiment:
Common step scheduleDPRGDDPRGD-ATC
Constant0.03100.0228
Decaying0.01330.0117

These values include replacement sampling, subsequent propagation, loss conversion and final output projection. Both comparisons are below the loss range of one; the decaying schedule reduces the complete bound by 12.22% at identical gradient and communication budgets.

  • Geometry, network and steps are jointly checked. We use St⁡(8,2)\operatorname{St}(8,2), unit-norm PCA samples, m=4m=4, n=40n=40 and T=512T=512. Certified constants are τ=0.5\tau=0.5, h=0.1h=0.1, G=L0=2G=L_0=2, Lg=8L_g=8 and C1=11.28892953C_1=11.28892953. Two communication rounds give σ=1/4<1/2\sigma=1/4<1/2. Both schedules, ηt=1/2720\eta_t=1/2720 and ηt=(1/2720)/(1+t/512)\eta_t=(1/2720)/(1+t/512), satisfy the common threshold η∗=0.001015128789\eta_*=0.001015128789. The joint trajectory proof guarantees admissible update and output projections throughout both neighboring-data runs.

  • The statistical assumptions also hold. The fixed mixing matrix is nonnegative, symmetric and doubly stochastic. Both methods share a data-independent feasible initialization, uniform sampling with replacement and the prescribed projected-average output. Neighboring-data runs share sampling indices. Common-distribution i.i.d. data justify the stability-to-expected-generalization conversion. Thus the comparison verifies the full set of assumptions, including those beyond the step threshold.

2.Question 1: Bound ordering and an observable error

  • Both orderings now appear in the same admissible experiment. Appendix G.2 and Table 18 extend the original circle derivative check to complete bounds and finite replacement losses. Three agents use exact averaging, common initialization and the linear losses of Proposition 4, with η=η∗=0.004238021180\eta=\eta_*=0.004238021180 and replacement size ϵ=10−3\epsilon=10^{-3}:
QuantityDPRGDDPRGD-ATC
Complete stability bound1.4186×10−41.4186\times10^{-4}1.4129×10−41.4129\times10^{-4}
Expected absolute replacement loss change7.063410921×10−87.063410921\times10^{-8}7.063368633×10−87.063368633\times10^{-8}

Exact summation over sampling outcomes with 80-digit arithmetic resolves the finite-loss ordering. Extra digits are retained here to display the small strict difference.

  • The finite-loss ordering agrees with the exact analytic sensitivity ratio. Writing Φν\Phi_\nu for the expected test-loss response to the replacement,

    =\frac{3}{1+2/\sqrt{1+\eta^2}}>1.$$ DPRGD projects opposing outer-agent updates separately; their average lies inside the circle, so final projection amplifies the middle-agent perturbation. ATC cancels those updates before projection. The relative effect is of order $\eta^2$, as predicted by the curvature expansion. A half-step and a second replacement size give the same ordering. This directly links the improved guarantee to an observable loss response in the constructed instance.

3. Question 2: Decaying steps and the geometric multiplier

  • The common decaying schedule satisfies the step thresholds and square summability, with geometric multiplier 2.1842. Both methods use

    ηt=1/27201+t/512,T=512,σ=1/4.\eta_t=\frac{1/2720}{1+t/512},\quad T=512,\quad\sigma=1/4.

    Every step is below η∗=0.001015128789\eta_*=0.001015128789, and ∑t≥0ηt2≤513/27202\sum_{t\ge0}\eta_t^2\le513/2720^2. Earlier ATC-only square-root decay had a logarithmically growing squared-step sum; this common harmonic schedule supplies the requested finite sum (Appendix G.1).

  • The correction is appreciably above one. With Cgeom=22545.621727C_{\mathrm{geom}}=22545.621727 and U=∑t<512ηt2=3.46528013×10−5U=\sum_{t<512}\eta_t^2=3.46528013\times10^{-5}, eCgeomU=2.1842e^{C_{\mathrm{geom}}U}=2.1842. The sharper update products are 1.3120 versus 1.0344; output factors are 1.0002 versus 1.0000 (B versus A). Including output projection gives complete bounds 0.0133 versus 0.0117, a 12.22% reduction. Full-precision factors are in the experimental-details attachment.

  • Geometric gains accompany essentially identical learning progress. Across twenty pairs, final consensus error falls 78.98% and maximum pre-projection distance 56.13%. The absolute-gap difference is −3.082×10−9-3.082\times10^{-9}, with paired 95% interval [−8.392,2.260]×10−9[-8.392,2.260]\times10^{-9}; sensitivity differs by 0.564×10−90.564\times10^{-9}, with interval [−7.511,8.779]×10−9[-7.511,8.779]\times10^{-9}. These intervals quantify the smaller average statistical effects.

Part 2/2

4. Weakness 2 and Question 3: Conditions for strictly lower sensitivity

  • Proposition 4 is an existence result on every manifold in the stated class: it constructs a learning instance with strictly lower actual local sensitivity for ATC. It complements Theorem 3’s uniform upper-bound comparison by showing that the geometric improvement can occur in the loss response itself. The abstract, informal result and Section 4.1 now state these quantifiers explicitly.

  • The sufficient conditions specify geometry and data together. Choose a point xx and unit tangent direction vv with IIx(v,v)≠0\mathrm{II}_x(v,v)\ne0, where II\mathrm{II} is the second fundamental form. Three agents start at xx, average exactly, and use linear losses with opposing outer-node samples and a small middle-node replacement along vv. Every compact C3C^3 embedded manifold without boundary of positive dimension has such a direction: its second fundamental form cannot vanish identically.

  • The strict comparison is quantitative. For the expected test-loss responses,

    $ \frac{|\Phi'_{\mathrm B}(0)|}{|\Phi'_{\mathrm A}(0)|} =1+\frac{\eta^2}{3}|\mathrm{II}_x(v,v)|^2+o(\eta^2)>1 $

    for sufficiently small admissible positive steps. Differentiability gives the corresponding ordering for sufficiently small nonzero replacements, verified in D2. Thus curvature affects the actual learning response, beyond its role in the proof estimates. Theorem 3 supplies the uniform bound ordering; Proposition 4 supplies actual sensitivity ordering under the specified construction. The informal theorem now labels its ε\varepsilon quantities explicitly as upper bounds.

5. Question 4: Quantitative comparison of VνV_\nu

  • The comparison gives VA≤VBV_{\mathrm A}\le V_{\mathrm B} under the stated common conditions. ATC improves the consensus and projection-distance terms, while the common local squared-step term cancels. Section 5 displays the components side by side. Under Theorem 5's constant-step conditions, set E=2ηG/(1−2σ)E=2\eta G/(1-2\sigma), D=2mED=\sqrt{2m}E and a=1/(2τ)+C1/2a=1/(2\tau)+C_1/2:
TermDPRGDDPRGD-ATC
Eν∗E_\nu^*EEσE\sigma E
qνq_\nuaD2aD^2aσ2D2a\sigma^2D^2
rν∗r_\nu^*aD2+C1DηG+C1η2G2/2aD^2+C_1D\eta G+C_1\eta^2G^2/2aσ2D2+2C1σDηG+C1η2G2/2a\sigma^2D^2+2C_1\sigma D\eta G+C_1\eta^2G^2/2

These respectively control consensus error, the distance from the ambient mean to its projection, and the update's pre-projection distance. ATC's consensus factor σ\sigma yields a quadratic factor σ2\sigma^2; its mixed term accounts for gradients from different tangent spaces.

  • The exact difference identifies the improvement. Substituting into Vν = Lg Eν* + (Lg + C₁G)qν + rν*/η. gives Eq. (20):

    V_{\mathrm B}-V_{\mathrm A} ={}&(1-\sigma)L_gE\\ &+(1-\sigma^2)aD^2(L_g+C_1G+1/\eta)\\ &+(1-2\sigma)C_1DG\ge0. \end{aligned}$$ The common local squared-step term cancels; every remaining term is nonnegative for $\sigma<1/2$. Consequently, the stationarity upper bound decreases by $5\chi(V_{\mathrm B}^2-V_{\mathrm A}^2)/2$, with the common factor $\chi$ from Theorem 5 and identical initial-gap and noise terms. Appendix A.8 gives the subtraction in full.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.