- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper considers the decentralized nonconvex nonsmooth optimization problem. The existing SOTA method achieves a linear dependence on the dimension in the sample complexity. By leveraging the shared random interpolation weight across nodes, the paper achieves a sample complexity that is independent of the dimension .
Critical strengths
-
The proposed method achieves a dimension-free sample complexity for solving the decentralized nonconvex nonsmooth problem.
-
The authors provided a theoretical convergence analysis of the proposed method, and it is correct and sound.
-
The overall paper writing is clear and easy to follow.
Critical weaknesses
-
Although the authors claimed they used a shared interpolated weight induced by a shared seed, they only used the shared weight to compute the gradient on a single machine, while all other machines were idle. In this case, why not just running the exact O2N algorithm on a single machine, and distributes all the final weights to all the machine.
-
In Algorithm 1, the algorithm computes the weight averaged over all machines and all iterations, which is quite impractical for large-scale distributed system.
-
No numerical experiments are performed to compare the proposed method with existing methods, such as the DOC$^2$S method.
Questions for authors
-
Would the DOC$^2$S achieves the same rate as your method if they also adopted the shared random seed methodology?
-
Is it possible to obtain a per-machine average for the output instead of a network-average output?
-
Is it possible to extend the current methodology to achieve a linear speedup?
4 comments
Official Comment by Authors (2/2)
Q4: Would the DOC$^2$S achieves the same rate as your method if they also adopted the shared random seed methodology?
A4: Yes. Actually, from Reviewer eDwY’s comment, we became aware that the recent revision of Chen et al. (2026, arXiv:2601.19381v2) also uses shared random interpolation and achieves sample and communication complexities matching those of our work. However, this revision was released on Oct 5, 2026, after our submission deadline of September 25, 2026. We therefore respectfully suggest that the subsequent improvements in v2 should not detract from our independently developed contributions.
Moreover, we want to emphasize that there are important distinctions in our algorithm and analysis.
- Our analysis bypasses a key technical challenge identified by Sahinoglu & Shahrampour (2024) and also addressed by Chen et al. (2026). Specifically, their analysis of the global objective change introduces the following discrepancy -\frac1n\sum_{i=1}^n\int_0^1 \nabla f_i\\!\left(\mathbf x_{t-1,i}^k+s\Delta_{t,i}^k\right)\\,ds,$$ which they bound using the smoothness of the local functions. We instead start from local objective changes (our Eq. (11)) and bound the same global objective change using only function Lipschitzness and iterate consensus.
- We establish a black-box reduction to D-OCO by reducing all three decentralization challenges to update-direction consensus. All gossip operations are handled by the D-OCO subroutine, and our Theorem 1 holds for any valid upper bound on its expected decision-consensus error. In contrast, Chen et al. (2026) separately apply accelerated gossip to both update directions and optimization iterates. Their Goldstein certificate construction also requires a radius-dependent consensus threshold to ensure neighborhood inclusion, whereas our reduction accommodates general consensus bounds.
Q5: Is it possible to extend the current methodology to achieve a linear speedup?
A5: At present, we do not have a theoretical guarantee of linear speedup. Specifically, a natural starting point is to replace client sampling with full participation, which allows us to average gradient estimates across nodes and thereby reduce their stochastic variance in the analysis. Although full participation is accommodated by our framework, the current D-OCO regret bound depends on the second moment of the gradient estimates, rather than their variance alone. Therefore, this variance reduction does not directly yield linear speedup. This limitation also arises in the full-participation analysis of Sahinoglu & Shahrampour (2024). Accordingly, establishing linear speedup may require a sharper analysis of the D-OCO regret, and we regard this as an important direction for future work.
I thank the authors for their careful clarification, and they have addressed most of my concerns. I have raised my score by 1.
Dear Reviewer JD7U,
Thank you for your reassessment and positive update.
Best,
Authors
Official Comment by Authors (1/2)
Many thanks for the constructive review! We hope the reviewer could reevaluate our paper, and are very happy to respond to any additional questions during the discussion period.
Q1: ... they only ... compute the gradient on a single machine, while all other machines were idle ... why not just running the exact O2N algorithm on a single machine, and distributes all the final weights ...
A1: First, although only one machine queries its stochastic gradient at each iteration, we want to clarify that the other machines are not idle: all nodes maintain their local optimization variables and participate in the D-OCO updates and neighbor-to-neighbor communication.
Second, running O2N on a single fixed machine using only its local oracle would optimize the local objective fi, rather than the global objective f=n1∑ifi. Broadcasting the final solution would not resolve this objective mismatch. Therefore, running O2N on a single machine and broadcasting its output cannot directly replace our decentralized procedure.
Q2: ... the algorithm computes the weight averaged over all machines and all iterations ... Is it possible to obtain a per-machine average for the output ...
A2: Thank you for pointing out this issue and providing the helpful suggestion. We have revisited our analysis and proved that each node can return its own local average instead of the network-averaged output, with the same stationarity guarantee.
Specifically, node i computes wik=T1∑t=1Twt,ik and returns wi∼Unifwi1,…,wiK. The key insight is that the local points w1,ik,…,wT,ik of each node i lie within distance TD=δ/2 of their average wik, allowing us to construct a Goldstein stationarity certificate directly for the local output. Moreover, our existing consensus guarantee ensures that replacing wˉtk with wt,ik as the evaluation point of the smoothed global gradient increases the gradient discrepancy bound by at most a factor of 2.
Consequently, only the last term in Theorem 1 increases by a factor of 2. The original parameter choices in Corollary 1 already accommodate this increase, so both the parameter settings and the resulting sample and communication complexities remain unchanged. We have revised Algorithm 1, Theorem 1, Corollary 1, and the corresponding proofs accordingly.
Q3: No numerical experiments are performed ...
A3: We have added experiments on two nonsmooth nonconvex tasks: capped-ℓ1-regularized SVM training on a9a and rcv1, and two-layer ReLU network training on MNIST and Fashion-MNIST. Across all four datasets, D-ONC reduces the global objective faster than DOC$^2$S and ME-DOL as either the sample or communication budget increases, supporting its practical effectiveness. The results are presented in the new “Preliminary Experiments” section, with detailed task formulations and parameter settings in the appendix.