acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Dynamic Smoothing with Partial Gradient Tracking on Compact Submanifolds

Abstract

We study decentralized composite optimization on compact embedded submanifolds, where each local objective contains a smooth agent-specific loss and a common convex nonsmooth regularizer. Tracking the full smoothed gradient introduces a Lipschitz factor that diverges as the smoothing parameter decreases. We propose a decentralized smoothing method with partial gradient tracking (DSPGT), which tracks only the heterogeneous smooth gradients and evaluates the common smoothing gradient locally. A Lyapunov function containing the local regularizer values controls the latter term through the Jensen decrease induced by mixing. For a uniformly sampled tail iterate, the expected smoothed stationarity residual and consensus error are . For Moreau smoothing, these bounds give a generalized -stationary point of the original problem at every agent in projection-oracle calls and communication rounds, matching the centralized order. Across the 18 reported settings on MNIST and CIFAR-10, DSPGT has the lowest median residual.

Primary area:
optimization
Keywords:
Decentralized optimization, nonsmooth optimization, gradient tracking, manifold optimization.

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_B9QxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies decentralized composite optimization on compact embedded submanifolds, where each agent has a smooth local loss and all agents share a convex nonsmooth regularizer. The authors propose DSPGT, which combines dynamic smoothing with projected consensus and partial gradient tracking. The method tracks only the heterogeneous smooth gradients while evaluating the smoothed regularizer locally.

The theoretical analysis introduces a local-regularizer Lyapunov function and uses weighted consensus estimates to establish an O(ε−3)O(\varepsilon^{-3}) complexity bound for generalized stationarity of the original nonsmooth problem, matching the centralized dynamic-smoothing order under the stated oracle assumptions. Experiments on regularized subspace learning using MNIST and frozen CIFAR-10 features compare DSPGT with several existing decentralized methods across different network topologies and data distributions.

Critical strengths
  1. The paper establishes an O(ε−3)O(\varepsilon^{-3}) complexity guarantee for decentralized nonsmooth optimization on compact embedded submanifolds using a single communication round per iteration. The local-regularizer Lyapunov function and Jensen-gap argument provide a useful way to control smoothing-dependent errors without introducing the diverging Lipschitz factor into the main network recursion.

  2. The analysis connects the smoothed convergence guarantee to generalized stationarity of the original nonsmooth problem, including the local outputs returned by individual agents. This strengthens the theoretical relevance of the result beyond convergence to a stationary point of a fixed smoothed objective.

Critical weaknesses
  1. The algorithmic novelty appears somewhat limited, as DSPGT largely combines existing dynamic smoothing (Beck and Rosset, 2023) with decentralized projected Riemannian gradient tracking (Deng and Hu, 2025). The paper does not sufficiently clarify the technical novelty beyond this combination.

  2. The theoretical benefit of gradient tracking is not sufficiently isolated. Without analyzing the corresponding dynamic-smoothing method without tracking, it remains unclear which heterogeneity-induced errors are eliminated and whether tracking is necessary to achieve the claimed O(ε−3)O(\varepsilon^{-3}) rate.

  3. The theoretical advantage over existing methods remains insufficiently characterized. DR-ProxGT (Wang et al., 2025) already achieves O(ε−2)O(\varepsilon^{-2}) iteration complexity using a stronger proximal oracle, but the paper does not clearly establish the computational trade-off between the two approaches.

References

[1] Beck, A., and Rosset, I. (2023). A Dynamic Smoothing Technique for a Class of Nonsmooth Optimization Problems on Manifolds. SIAM Journal on Optimization, 33(3), 1473–1493.

[2] Deng, K., and Hu, J. (2025). Decentralized Projected Riemannian Gradient Method for Smooth Optimization on Compact Submanifolds Embedded in the Euclidean Space. Numerische Mathematik, 157(6), 2173–2210.

[3] Wang, L., Bao, L., and Liu, X. (2025). A Decentralized Proximal Gradient Tracking Algorithm for Composite Optimization on Riemannian Manifolds. Journal of Machine Learning Research, 26(106), 1–37.

Questions for authors
  1. What is the main technical contribution beyond combining dynamic smoothing with decentralized projected gradient tracking? In particular, which difficulties cannot be directly addressed using the existing analyses of Beck and Rosset (2023) and Deng and Hu (2025)?

  2. What convergence guarantee can be obtained for the proposed dynamic-smoothing framework without gradient tracking? Which heterogeneity-induced error terms arise, and how would they affect the O(ε−3)O(\varepsilon^{-3}) complexity bound?

  3. How does the proposed method compare theoretically with DR-ProxGT (Wang et al., 2025), particularly regarding the stationarity guarantees and local oracle requirements? Can the authors clarify the computational trade-off between the O(ε−3)O(\varepsilon^{-3}) smoothing-based method and the existing O(ε−2)O(\varepsilon^{-2}) proximal method?

2 comments

1. Weakness 1 and Question 1: Technical contribution

Thank you for recognizing the analysis. Two obstacles require separate treatments: smoothing increments in tracking and regularizer disagreement in descent.

  1. Partial tracking removes recursive dependence on smoothing. Full tracking introduces regularizer-gradient increments with Lipschitz factor 1/μk1/\mu_k (Eq. 3.3). Using the common hh, DSPGT evaluates its smoothing gradient locally and tracks only heterogeneous smooth gradients. The tracker constants are independent of μk\mu_k (Lemma E.3).

  2. The local potential controls descent errors. Agents evaluate hμkh_{\mu_k} at different points. We use Ψμ(x)=fˉ(xˉ)+n−1∑ihμ(xi)\Psi_\mu(\mathbf x)=\bar f(\bar x)+n^{-1}\sum_i h_\mu(x_i). Convexity and doubly stochastic mixing yield a Jensen decrease (Eq. 3.5), absorbing regularizer-induced network errors (Lemma E.7). Intrinsic smoothing curvature remains in the step-size condition.

  3. Together they close the cumulative estimate: (E.28) and (E.33) control the local-to-mean conversion. Neither centralized smoothing nor fixed-smoothness DPRGT supplies this network control as μk→0\mu_k\to0. We recover the centralized O(ε−3)O(\varepsilon^{-3}) order from the decentralized smoothing O(ε−4)O(\varepsilon^{-4}) bound of Wang and Liu (2023), with one neighbor exchange per iteration.

The contribution is resolving these network errors to obtain the cumulative-oracle guarantee, as clarified in Sections 1, 3 and 4.

2. Weakness 2 and Question 2: What changes without gradient tracking?

Without tracking, persistent local heterogeneity can invalidate the cumulative bounds used by our proof.

  1. Local gradients create disagreement at consensus. For the untracked direction di,k=grad⁡fi(xi,k)+grad⁡hμk(xi,k)d_{i,k}=\operatorname{grad}f_i(x_{i,k})+\operatorname{grad}h_{\mu_k}(x_{i,k}), projection expansion at consensus gives

xi+−xˉ+=−α(grad⁡fi(x)−grad⁡fˉ(x))+O(α2).x_i^+-\bar x^+=-\alpha(\operatorname{grad}f_i(x)-\operatorname{grad}\bar f(x))+O(\alpha^2).

The common regularizer cancels; local gradient mismatch can persist at aggregate stationarity.

  1. An exact example shows the obstruction. Set ek2=n−1∑i∥xi,k−xˉk∥2e_k^2=n^{-1}\sum_i\|x_{i,k}-\bar x_k\|^2. For DSPGT, (E.28) and (E.33) give
\sum_{k=1}^K e_k^2/\alpha_{k-1}\le C\mathcal E_K.$$ Lemma F.1 considers two agents on $S^1$, $W=J$, $f_1(x)=x_1$, $f_2(x)=-x_1$, $h=0$, and common start $(0,1)$. For $\alpha_k=a(k+1)^{-p}$, $0<p<1$, and sufficiently small $a>0$, the untracked iterates satisfy $$\mathcal E_K^{\mathrm{nt}}\ge\tfrac34\sum_{k<K}\alpha_k,\qquad \sum_{k=1}^K e_k^2/\alpha_{k-1}\ge\tfrac12\sum_{k<K}\alpha_k.$$ Here $\mathcal E_K^{\mathrm{nt}}=\frac12\sum_{k<K}\alpha_k\sum_i\|d_{i,k}\|^2$. Both quantities diverge as $K^{1-p}$. Appendix F.2 verifies the exact recurrence and neighborhood conditions. 3. **Tracking replaces persistent mismatch by smooth-gradient increments**, controlled by a fixed Lipschitz constant times iterate motion. Partial tracking also excludes the $1/\mu_k$ regularizer increments. Without tracking, the pointwise estimate $e_k=O(\alpha_k)$ gives only $e_k/\mu_k=O(1)$ for coupled schedules. **The example establishes failure of the uniform energy bounds needed by this proof**, rather than a lower bound on all untracked methods' stationarity rates. The partial/full ablation separately tests which gradients to track. ### 3. Weakness 3 and Question 3: Stationarity and local-oracle tradeoff with DR-ProxGT 1. **Original KKT certificate.** Appendix F.1 gives a fixed-scale proximal KKT certificate at each returned primal point with $z_K=\nabla h_{\mu_{R_K}}(\bar x_{R_K})$, retaining $O(\varepsilon^{-3})$. Algorithm 1 returns primal points; evaluating this witness requires the projected network mean. 2. **Different local oracles.** DSPGT bounds cumulative gradient, ambient-prox and projection calls. DR-ProxGT's $O(\varepsilon^{-2})$ outer bound uses tangent-space proximal solves; total ambient-prox calls require inner-solver analysis. DSPGT's row-norm prox is rowwise; the tangent-space solve couples rows. Exact-oracle arithmetic costs depend on the problem; DSPGT does not improve the communication exponent. 3. **Common-accuracy costs.** After DR-ProxGT calibration, the strong synthetic setting uses 1,000-1,350 DR-ProxGT rounds and 3,000-4,050 Newton updates per agent, versus 2,450-2,500 rounds and no Newton updates for DSPGT. DSPGT's median paired algorithm-time advantage is **6.59**, while DR-ProxGT communicates less. CIFAR gives comparable algorithm times; DR-ProxGT reaches the stricter residual target. Appendix G.7 reports the protocol and costs, with all records retained. [Jiang et al. (2025), Table 1](https://arxiv.org/pdf/2509.08561), also separate outer iterations and cumulative proximal calls in the centralized setting.

Thank you for the detailed response. I acknowledge that the local-regularizer potential, Jensen-gap argument, and weighted consensus estimates provide a convergence analysis for the proposed method. However, my main concern about the incremental nature of the contribution remains.

Specifically, Algorithm 1 closely resembles the projected Riemannian gradient tracking framework of Deng and Hu (2025), with the main modification being the addition of a dynamic-smoothing gradient correction. Moreover, tracking only the smooth component while handling the shared nonsmooth regularizer locally has already been adopted in DR-ProxGT (Wang et al., 2025).

Although the authors' response explains the technical challenges involved in analyzing this combination, it does not sufficiently clarify which part of the proposed theoretical framework constitutes a substantive advance beyond existing convexity-based analysis, projected-consensus analysis, and gradient-tracking techniques.

Therefore, I will maintain my original rating.

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

The paper studies decentralised nonsmooth optimisation over compact manifolds and proposes DSPGT, a dynamic-smoothing method that tracks the heterogeneous smooth gradients while evaluating the common smoothed regulariser locally. The method yields an O(ϵ−3)O(\epsilon^{-3}) complexity under an approximate stationarity notion.

Critical strengths

The main technical contribution is a Lyapunov/Jensen-gap analysis that prevents the smoothing factor from entering the recursive network errors and thereby prevents its growth.

Critical weaknesses
  • The main concern is that DSPGT cannot claim O(\epsilon^{-3}) as the state of the art complexity for decentralised nonsmooth composite optimisation over compact manifolds. The previous proximal gradient tracking method DR-ProxGT, which considers a very similar formulation, attains an O(ϵ−2)O(\epsilon^{-2}) outer-iteration complexity, albeit with a different composite proximal oracle. The finite-accuracy guarantees in the two works are conceptually similar. Therefore, the main contribution of DSPGT should be framed narrowly as improving the complexity of smoothing/projection-based methods, rather than improving the best-known complexity for decentralised nonsmooth composite optimisation in general.

  • A more fundamental concern is that the guarantee is stated in terms of an approximate stationarity notion, where the nonsmooth subgradient is evaluated at a nearby point yy, rather than necessarily at the returned point xx. In general, yy being close to xx does not imply that a subgradient in ∂h(y)\partial h(y) is close to any subgradient in ∂h(x)\partial h(x). The fact that this notion has appeared in prior work such as DR-ProxGT and THANOS does not justify its continued use as a primary finite-accuracy guarantee. The exact stationarity condition evaluates the smooth gradient and nonsmooth subgradient at the same point xx, i.e., there exists z∈∂h(x)z \in \partial h(x) such that PTxM(∇f(x)+z)=0P_{T_x \mathcal{M}} (\nabla f(x) + z) = 0.

  • Finally, the experiments do not convincingly establish the practical advantage of the proposed method. The empirical schedule is different from the schedule analysed in Theorem 4.1. The theory assumes a single monotone schedule αk=α0(k+1)−1/3\alpha_k=\alpha_0 (k+1)^{-1/3}, while the experiments increase the step size prefactor from 0.6 to 12.5 at iteration 1250, an approximately 20x instantaneous jump. In addition, simulation results should be more comprehensive and compare the performance of the proposed method with the baselines in terms of wall-clock time, local computational cost, and total communication overhead, among others.

Questions for authors
  • Can the authors show whether their approximate stationarity notion can be converted into a same-point stationarity guarantee for the returned iterate, or explain why such a conversion is possible under their assumptions?

  • Can the authors explain why they chose a switching schedule in the simulations, while the theoretical analysis assumes a single monotone schedule?

3 comments

Part 1/2

1. Weakness 1: Complexity relative to DR-ProxGT

Thank you for raising this comparison. DSPGT bounds cumulative gradient, ambient-prox and projection calls; DR-ProxGT's outer bound counts a composite tangent-space proximal solve as one local operation.

  1. DSPGT bounds primitive-oracle calls. Each iteration uses a constant number of gradients, ambient proximal mappings and nearest-point projections per agent. Thus O(ε−3)\mathcal O(\varepsilon^{-3}) bounds cumulative calls to each oracle, without an iterative tangent-space proximal solve.

  2. The local nonlinear operations differ. DR-ProxGT's O(ε−2)\mathcal O(\varepsilon^{-2}) outer bound counts a composite tangent-space proximal solve per iteration. An implementation such as semismooth Newton incurs inner work whose cumulative ambient-proximal-call complexity is not established by that outer theorem.

QuantityDSPGTDR-ProxGT
Outer iterationsO(ε−3)\mathcal O(\varepsilon^{-3})O(ε−2)\mathcal O(\varepsilon^{-2})
Local nonsmooth operationAmbient prox⁡μkh\operatorname{prox}_{\mu_k h}Composite tangent-space proximal solve
Cumulative ambient-proximal callsO(ε−3)\mathcal O(\varepsilon^{-3})Inner-solver total not bounded by the outer theorem
Iterative tangent-space subproblemNoneRequired local solve; SSN in the implementation

These are exact oracles with problem-dependent arithmetic costs. DSPGT uses one neighbor exchange per iteration; its O(ε−3)\mathcal O(\varepsilon^{-3}) communication exponent is distinct from the local-oracle comparison.

  1. Inner-oracle accounting is a separate analytical task. Jiang et al. (2025), Table 1 and Theorems 5.5–5.7, give centralized inexact proximal methods with O(ε−2)\mathcal O(\varepsilon^{-2}) outer iterations but O(ε−3log⁡ε−1)\mathcal O(\varepsilon^{-3}\log\varepsilon^{-1}) or O(ε−3)\mathcal O(\varepsilon^{-3}) ambient-proximal calls, depending on the inner solver. These centralized results illustrate the accounting issue; establishing the corresponding total for DR-ProxGT requires its own inner-solver analysis.

DSPGT directly establishes a decentralized cumulative bound matching the centralized smoothing order under the stated oracle model. This is an upper bound, not a lower bound on DR-ProxGT's inner work.

Revision: Sections 1-2 and the conclusion specify this oracle scope and acknowledge DR-ProxGT's O(ε−2)\mathcal O(\varepsilon^{-2}) outer bound.

2. Weakness 2 and Question 1: From nearby-point subgradients to a certificate at the returned point

The theorem bounds both original KKT residuals at each returned primal point, with an explicit dual witness, in O(ε−3)\mathcal O(\varepsilon^{-3}) oracle calls.

  1. The residual measures the original KKT equations. For any fixed τ>0\tau>0, proximal optimality gives
x=\operatorname{prox}_{\tau h}(x+\tau z).$$ Together with $P_{T_x\mathcal M}(\nabla\bar f(x)+z)=0$, this is the original KKT system. We measure its two equations by \$ \mathcal{K}\_{\tau}(x,z)=\|P\_{T_x\mathcal{M}}(\nabla\bar f(x)+z)\|+\tau^{-1}\|x-\operatorname{prox}\_{\tau h}(x+\tau z)\|. \$ The terms measure tangent stationarity and subgradient consistency; $\tau$ is fixed independently of accuracy and iteration count. 2. **The finite-accuracy bound follows quantitatively.** Algorithm 1 returns $x_{i,R_K}$. Proposition 4.2 constructs the common witness $z_K=\nabla h_{\mu_{R_K}}(\bar x_{R_K})$, with $y_K=\operatorname{prox}_{\mu_{R_K}h}(\bar x_{R_K})$ and $z_K\in\partial h(y_K)$. For any $z\in\partial h(y)$, firm nonexpansiveness implies $\lVert x-\operatorname{prox}_{\tau h}(x+\tau z)\rVert\le\lVert x-y\rVert$. Applying this inequality and the local-output bounds yields $$\mathbb{E}\mathcal{K}_{\tau}(x_{i,R_K},z_K) \le (1+\tau^{-1})C_{\star}\eta_K =\mathcal{O}(K^{-1/3}).$$ Algorithm 1 returns primal points; evaluating the common proof witness requires the projected network mean. Appendix F.1 gives the reverse deterministic conversion using $y=\operatorname{prox}_{\tau h}(x+\tau z)$ and $w=z+(x-y)/\tau\in\partial h(y)$, and distinguishes expected from almost-sure feasibility. 3. **Strict same-point subgradient distance has different finite-accuracy behavior.** On $S^1$, take $f=0$, $h(x)=|x_1|$, $x_t=(t^2,\sqrt{1-t^4})$ and $\mu=t$. The smoothed tangent residual is at most $t$ and the splitting distance is $t^2$, so the fixed-scale KKT residual tends to zero, whereas the strict same-point subgradient distance tends to one. Thus the stronger conversion requested in the question needs additional assumptions. The quantitative KKT guarantee above remains valid under the stated assumptions.

Part 2/2

3. Weakness 3 and Question 2: Theoretical versus empirical schedules, and computational costs

The experiments retain Algorithm 1's updates and use a staged continuation schedule for the fixed iteration budget. Coarser smoothing and larger initial steps precede joint refinement of the smoothing level and step size. The revision gives both the polynomial-form comparison and the requested cost measurements.

  1. The recorded steps decrease rather than increase. The displayed 20-fold increase was a reporting error: archived runs used 0.6/L^0.6/\widehat L followed by 0.0075/L^0.0075/\widehat L. Appendix G.5 records the correction. The additional synthetic study uses physical step sizes 1/3,0.2,0.005,0.00051/3,0.2,0.005,0.0005 with smoothing values 1,0.4,0.01,0.0011,0.4,0.01,0.001 and switches at 1750, 2000 and 2250. The initial stages use coarser approximations; the later stages target finer nonsmooth accuracy with smaller steps.

  2. The schedule changes the parameters, not the update equations. Theorem 4.1 proves the rate for coupled polynomial schedules under its parameter bounds. With the same DSPGT updates, Appendix G.5 compares a p=1/3p=1/3 polynomial-form schedule on all six real-data instances; it gives larger terminal residuals than the retained staged schedule at 2,500 iterations. This observation motivates the finite-budget parameter choice. The polynomial experiment checks the schedule form without certifying every theorem constant; the staged results provide empirical evidence for Algorithm 1 with that parameter sequence.

  3. The new study measures cost at a common original-problem accuracy. Both methods use the same certified evaluator, observation grid, 32-process server setup and single-threaded BLAS. The primary target requires Rk+/R0−≤.03R_k^+/R_0^-\le .03 and RMS consensus ≤10−4\le10^{-4}, where R+R^+ and R−R^- are the residual certificate bounds. The budget is 2,500 iterations.

The table reports median algorithm time to the first observed joint-target hit. Both synthetic settings use ρ=.8\rho=.8 on St⁡(100,20)\operatorname{St}(100,20).

SettingDSPGT hitsDR-ProxGT hitsDSPGT time (s)DR-ProxGT time (s)
Synthetic, λ=.003\lambda=.0033/30/33.010—
Synthetic, λ=.03\lambda=.033/33/33.03219.990
CIFAR, λ=.3\lambda=.33/33/32.6142.721

The measurements separate local computation from communication. In the strongly regularized synthetic setting, the median paired DR-ProxGT/DSPGT time ratio is 6.59, or 4.43 including evaluation and checkpoint storage. DR-ProxGT reaches this target in fewer communication rounds. CIFAR algorithm times are close; elapsed-time medians including diagnostics are 6.453 s for DSPGT and 3.827 s for DR-ProxGT.

Fixed-budget cost: At 2,500 CIFAR iterations, median algorithm times are 3.28 s for DSPGT and 11.41 s for DR-ProxGT. DR-ProxGT's shorter iteration count to the common target offsets its higher per-iteration cost.

I thank the authors for their response and for their efforts in revising the manuscript. However, I maintain my score due to the following remaining issues:

(1) Limited practical advantage over DR-ProxGT. Although the additional experiments provide useful computational comparisons, they do not establish a consistent overall advantage for DSPGT over DR-ProxGT. For example, on CIFAR, DR-ProxGT reaches the prescribed accuracy after 600 iterations, whereas DSPGT requires 1999 iterations. Therefore, DR-ProxGT incurs substantially lower communication overhead and achieves a shorter total elapsed time including evaluation and storage. These results suggest that the practical benefits of DSPGT are problem-dependent.

(2) Insufficient alignment between theoretical guarantees and experimental evidence. Theorem 4.1 establishes convergence guarantees under specific polynomial schedules and step size conditions, whereas the main experiments use staged schedules that are not covered by the theorem. Appendix G adds experiments using a polynomial schedule, but it reports only results at K=2500, without verifying the theorem's step size conditions or examining convergence-rate scaling across different iteration budgets.

Reviewer_bKhuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper extends decentralized projected Riemannian gradient tracking to composite objectives with a common convex nonsmooth regularizer. DSPGT evaluates the smoothing gradient locally and establishes an O(ε−3)O(\varepsilon^{-3}) projection-oracle and communication complexity bound.

Critical strengths

The method is simple, the problem is relevant, and the analysis explicitly addresses the interaction between dynamic smoothing and network disagreement.

Critical weaknesses
  1. Algorithm 1 retains DPRGT’s projected-mixing update and gradient-tracking recursion. Its main modification is adding grad⁡hμk(xi,k)\operatorname{grad}h_{\mu_k}(x_{i,k}) to the local direction. Dynamic smoothing is already established in centralized manifold optimization.

  2. Section 5 compares all methods using a fixed-smoothing gradient residual. However, proximal methods can produce sparse stationary points where a nonzero subgradient of the regularizer balances the smooth gradient. For the ℓ2,1\ell_{2,1} penalty, the Moreau gradient at a zero row is zero, so this balance may be lost when computing the evaluation residual. Consequently, an exact nonsmooth stationary point can receive a positive residual, while a nearby smoothed solution receives a smaller one. Using the same formula for every method therefore does not ensure a fair comparison. Please supplement it with a common stationarity measure for the original nonsmooth problem.

  3. DSPGT increases its step-size coefficient approximately (20.8)-fold at iteration 1250, followed by substantial performance improvements. However, the partial/full-tracking comparison uses different schedules and reports nearly identical results. The current experiments therefore do not isolate the benefit of partial tracking from that of the step-size strategy. Both variants should be compared under the same main-experiment schedule. In addition, all six non-IID CIFAR runs of DR-ProxGT fail to meet the inner-solver tolerance. It remains unclear whether these failures reflect limitations of the method or choices of parameters, solver settings, and computational budget. Further diagnostics are needed to support the comparison.

Questions for authors

What specific conceptual advance distinguishes the analysis from a dynamic-smoothing extension of DPRGT?

4 comments

Reviewer bKhu - Part 1/2

1. Algorithmic novelty and the conceptual advance beyond DPRGT

Thank you for asking us to clarify the conceptual advance. Our contribution is to identify why a direct dynamic-smoothing extension of DPRGT does not recover the centralized complexity order, and to resolve the resulting network-error terms using the shared regularizer structure.

  1. The starting point is a complexity gap, rather than a new update formula. Centralized manifold dynamic smoothing achieves O(ε−3)O(\varepsilon^{-3}), whereas the existing decentralized smoothing analysis gives O(ε−4)O(\varepsilon^{-4}). A direct extension of DPRGT encounters an additional difficulty: tracking the full smoothed gradient introduces regularizer-gradient increments with a Lipschitz factor of O(1/μk)O(1/\mu_k) into the network recursion. This factor grows as smoothing accuracy improves.
  2. Partial tracking removes this dependence from the tracker recursion, but does not complete the analysis. Since hh is common to all agents, DSPGT tracks only the heterogeneous smooth gradients and evaluates the smoothed regularizer locally. However, agents evaluate it at different points, so regularizer-gradient disagreement remains in the descent analysis. Thus, neither the centralized smoothing analysis nor the smooth DPRGT analysis directly yields the claimed rate.
  3. The main analytical step is to exploit the common regularizer through a different potential. We use Ψμ(x)=fˉ(xˉ)+n−1∑ihμ(xi)\Psi_\mu(\mathbf{x})=\bar f(\bar x)+n^{-1}\sum_i h_\mu(x_i), retaining the local regularizer values. Convexity and doubly stochastic mixing then provide a quantitative Jensen decrease that absorbs the regularizer-induced errors, instead of bounding them separately with 1/μk1/\mu_k-weighted network errors. Together with weighted consensus estimates, this closes the analysis while retaining the intrinsic smoothing restriction on the step size.

The resulting advance is an O(ε−3)O(\varepsilon^{-3}) primitive-oracle and communication complexity with one neighbor exchange per iteration, matching the centralized smoothing order. The simple update is supported by a different treatment of smoothing-dependent network errors, rather than a direct combination of existing convergence arguments.

2. A common stationarity measure for the original nonsmooth problem

Thank you for identifying this issue. The new evaluation retains the nonsmooth regularizer and the balancing subgradient at a zero row.

  1. The new residual uses the nonsmooth regularizer directly. At the projected network mean XX, we compute

Dτ(X)=arg⁡min⁡D∈TXM{⟨∇fˉ(X),D⟩+∣D∣F2/(2τ)+h(X+D)}D_\tau(X)=\arg\min_{D\in T_X\mathcal{M}}\{\langle\nabla\bar f(X),D\rangle+\\|D\\|_F^2/(2\tau)+h(X+D)\}

Rτ(X)=∣Dτ(X)∣Fτ.R_\tau(X)=\frac{\\|D_\tau(X)\\|_F}{\tau}.

Strong convexity makes DτD_\tau unique. Its optimality condition at D=0D=0 gives Rτ(X)=0  ⟺  0∈PTXM(∇fˉ(X)+∂h(X))R_\tau(X)=0\iff0\in P_{T_X\mathcal M}(\nabla\bar f(X)+\partial h(X)). Thus an exact nonsmooth stationary point receives zero residual, including the zero-row case raised in the review.

  1. All methods use an independent evaluator: the global gradient, the same instance-wise τ=1/max⁡{1,L^}\tau=1/\max\{1,\widehat L\}, and a primal-dual-gap certificate bounding residual error by 10−510^{-5}. Consensus and local feasibility are checked separately. Evaluation uses no method-specific smoothing level or stopping test.

  2. All five methods were rerun with the common evaluator. Across 12 seed-setting pairs, DSPGT has lower certified residuals than THANOS and DRSM in all pairs, and lower residuals and objectives than DR-ProxGT in all six weak-regularization pairs. DR-ProxGT has lower residuals in four strong-regularization pairs and both corresponding medians. DSPGT has lower consensus errors in 10/12 pairs. Strict residual comparisons require nonoverlapping certificate intervals. Appendix G.6 documents the configurations and additional development tuning allocated to DSPGT.

Three-seed median RτR_\tau after 2,500 iterations on a 32-agent ring, X∈St⁡(100,20)X\in\operatorname{St}(100,20). Here ρ\rho is heterogeneity and λ\lambda the regularization weight; bold marks the lowest median.

ρ\rhoλ\lambdaDSPGTTHANOSDRSMDR-ProxGT
0.10.0030.0053490.0090590.2431710.006667
0.10.030.0006760.0144150.2435050.000134
0.80.0030.0056570.0088110.2430970.006814
0.80.030.0011910.0156490.2434380.000133

Real data: Section 5 compares all four methods on MNIST and CIFAR. CIFAR residual medians are 0.08570 (DSPGT), 0.19718 (THANOS), 10.9704 (DRSM) and 0.02345 (DR-ProxGT); DSPGT has the lowest consensus median, 4.77×10−84.77\times10^{-8}.

Reviewer bKhu - Part 2/2

3(a). Matching partial/full schedules and explaining the step-size switch

Partial tracking has lower consensus error under the identical selected schedule. This controlled comparison changes the tracking choice while fixing the schedule, instance and initialization.

  1. The audit separates reporting and implementation corrections. The archived runs used μk=0.1(k+1)−0.6\mu_k=0.1(k+1)^{-0.6} and a step decrease from 0.6/L^0.6/\widehat L to 0.0075/L^0.0075/\widehat L at iteration 1250; the displayed increase to 12.512.5 was a reporting error. The new runs also use the Algorithm 1 direction based on si,ks_{i,k} and a consistently indexed full-tracking target. Section 5 reports these corrected comparisons; historical records remain in the data supplement.

  2. The synthetic comparison holds the schedule and instance fixed. Both variants use the same physical (μk,αk)(\mu_k,\alpha_k) values: (1,1/3)(1,1/3) for k<1750k<1750, (0.4,0.2)(0.4,0.2) for 1750≤k<20001750\le k<2000, (0.01,0.005)(0.01,0.005) for 2000≤k<22502000\le k<2250, and (0.001,0.0005)(0.001,0.0005) thereafter. Covariances, initialization, graphs and budgets are identical. Writing gi,kfull=grad⁡Fi,μk(xi,k)g_{i,k}^{\mathrm{full}}=\operatorname{grad}F_{i,\mu_k}(x_{i,k}), full tracking uses

+g_{i,k+1}^{\mathrm{full}}-g_{i,k}^{\mathrm{full}}.$$ Thus the update to $s_{i,k+1}^{\mathrm{full}}$ evaluates its new target at $(x_{i,k+1},\mu_{k+1})$, including schedule switches. The archived numerical audit checked the logged schedules and target indices; a short-step reference test checks the iterates, targets and tracker-mean identity. 3. **The clearest effect is on network disagreement.** Partial tracking has lower consensus in **12/12** synthetic pairs and lower residuals in **8/12**. The matched real-data comparison also gives lower consensus in **6/6** pairs and lower residuals in **5/6**. These differences measure the tracking effect under the selected common schedules. The complexity benefit follows from the analysis. The four setting medians favor partial and full tracking twice each in residual, while partial tracking lowers consensus medians by factors of **12.1, 66.1, 1.8 and 8.9**. Each variant has the lower objective in six synthetic pairs. Results at 2,500 iterations are shown below. | $\rho$ | $\lambda$ | $R_\tau$: partial | $R_\tau$: full | Consensus: partial | Consensus: full | | -----: | --------: | ----------------: | -------------: | ----------------------: | ------------------: | | 0.1 | 0.003 | **0.005349** | 0.005379 | **$4.14\times10^{-6}$** | $4.99\times10^{-5}$ | | 0.1 | 0.03 | **0.000676** | 0.001093 | **$8.19\times10^{-6}$** | $5.41\times10^{-4}$ | | 0.8 | 0.003 | 0.005657 | **0.005436** | **$3.38\times10^{-5}$** | $6.05\times10^{-5}$ | | 0.8 | 0.03 | 0.001191 | **0.001155** | **$6.10\times10^{-5}$** | $5.41\times10^{-4}$ | ### 3(b). Diagnosing the six DR-ProxGT inner-solver failures **We traced the failures to a stopping-test mismatch in our implementation and corrected it while retaining the original external accuracy requirement.** The diagnostics below distinguish captured-subproblem validation from complete reruns. 1. **We reproduced the failures before changing the solver.** All six historical CIFAR failures recurred at their original iterations, yielding 19 failing local subproblems. The internal packed symmetric residual could satisfy its stopping test before the normalized tangent-proximal KKT residual met $10^{-6}$. Raising the old iteration cap from 50 to 200 or 1000 did not resolve this premature termination. 2. **We aligned stopping with the actual KKT acceptance test.** The correction retains the subproblem, Newton equation, line search and external tolerance $10^{-6}$, and explicitly checks the final accepted state. The cap now counts 50 Newton updates rather than 50 state checks. All 19 captured subproblems pass and agree with a separately solved reference. | Captured CIFAR subproblems | Passing the $10^{-6}$ KKT test | Maximum KKT residual | | -------------------------- | -----------------------------: | ------------------------: | | Original stopping rule | 0/19 | $1.651\times10^{-6}$ | | Corrected stopping rule | **19/19** | **$2.663\times10^{-14}$** | 3. **The corrected solver completes the reruns and calibrated comparison.** All 18 original DR-ProxGT reruns, 36 calibration runs, nine independent evaluation runs and 18 timing repeats complete under the same $10^{-6}$ acceptance test and 50-Newton-update cap. The current CIFAR baseline table uses the three independent evaluation endpoints, alongside DSPGT, THANOS and DRSM on exactly the same instances. Calibrated DR-ProxGT also reaches the stricter relative-residual target $.01$ with consensus below $10^{-4}$. Section 5 and Appendix G.7 report the primary $.03$ target and measured costs.

Thank you for the reply. I will keep my score.

Thank you for considering our response. DSPGT combines a simple update with a substantive theoretical advance: partial tracking and the local-regularizer potential resolve the smoothing-dependent network errors, closing the decentralized–centralized smoothing complexity gap from O(ε−4)O(\varepsilon^{-4}) to O(ε−3)O(\varepsilon^{-3}). To our knowledge, this is the best-known cumulative gradient, ambient-proximal and projection-oracle bound under the stated assumptions, with one communication round per iteration. Matched-schedule experiments also demonstrate the practical benefit of partial tracking for consensus.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Our Contribution and Revisions

We thank the reviewers for their careful consideration. DSPGT closes the decentralized–centralized manifold smoothing complexity gap, improving O(ε−4)O(\varepsilon^{-4}) to O(ε−3)O(\varepsilon^{-3}) with one communication round per iteration. Partial tracking and the new local-regularizer potential resolve the smoothing-dependent network errors behind this gap. The update is simple; the advance lies in the guarantee it enables.

The revision adds a quantitative original-problem KKT certificate, clarifies cumulative oracle complexity, and provides certified common-residual comparisons, matched-schedule tracking ablations, and computational-cost measurements.

Could the reviewers kindly indicate whether these clarifications and additional results address their concerns, and identify any remaining questions? We would welcome the opportunity to clarify them during the discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.