acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Nonconvex Nonsmooth Optimization with Client-Data Sampling

Abstract

This paper studies decentralized online non-convex optimization (D-ONO), where a network of agents collaboratively minimizes a sequence of non-convex global loss functions through local computation and communication. Existing approaches either rely on an offline optimization oracle, which may require computational cost, or analyze window-averaged local regret based on local objectives, which does not accurately characterize the performance of individual agents. How to solve D-ONO under the standard notion of local regret, without requiring computations beyond gradient evaluations, remains largely unexplored. We propose Accelerated Decentralized Gradient Tracking (ADGT), which integrates gradient tracking into a block-wise online accelerated gossip scheme. Under both exact and stochastic gradient oracle feedback, we establish nearly optimal upper bounds on individual local regret and provide matching lower bounds. Extensive experiments on both synthetic and real-world datasets corroborate our theoretical findings and demonstrate the effectiveness of the proposed algorithm.

Primary area:
optimization
Keywords:
decentralized optimization, nonconvex optimization, nonsmooth optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_yQ8tOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The paper considers decentralized nonconvex nonsmooth opitmization and proposes an online to nonconvex conversion algorithm with client data sampling using multinomial distribution along with Chebyshev acceleration. The paper shows analytically that the proposed method can achieve an (δ\delta,ϵ\epsilon)-Goldstein stationary point with efficient complexity and communication bounds. Numerical results have been provided to show the performance of the proposed method.

Critical strengths

Decentralized nonconvex and nonsmooth optimization is a highly compelling topic that arises in various practical applications (e.g., machine learning). Developing efficient methods for such problems is therefore essential. The paper presents an algorithm with a thorough analytical convergence analysis to a (δ,ϵ)-Goldstein stationary point, with derived bounds on communication and computation complexity.

Critical weaknesses
  • The proposed algorithm appears to be a combination of existing methods : client data sampling in known in Federated Learning literature, chebyshev acceleration is also known as well as online to nonconvex conversion.

  • The client data sampling cannot be considered as decentralized : an entity doing the client sampling is required.

  • It is not clear how this method is specifically tailored to nonsmooth optimization: the analysis in the paper is conducted mainly for the smooth case, and the extension to the nonsmooth setting relies on a result from Sahinoglu & Shahramour 2024. Moreover, the smooth-case analysis follows standard tools, and the specific challenge involved in proving the results is not made explicit.

  • The numerical results are insufficient to demonstrate superiority over prior work. An improvement shown only on MNIST is not convincing, and it is unclear whether the experiments use IID or non-IID data distributions across clients (non-IID being more common in practice). Results on additional datasets (e.g., CIFAR) are needed. Furthermore, an ablation study is required: since the proposed algorithm combines client data sampling and Chebyshev acceleration, the ablation study must show the gain achieved by each component.

Questions for authors
  • The paper should discuss further how the client data sampling can be implemented in a decentralized way.

  • The challenges involved in proving the results in Lemmas 3, 4, 5, and 7 must be highlighted, as the proofs appear to follow standard tools.

4 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We thank the reviewer yQ8t for the detailed and helpful comments.

W1: The proposed algorithm appears to be a combination of existing methods: client data sampling in known in Federated Learning literature, Chebyshev acceleration is also known as well as online to nonconvex conversion.

R1: The proposed algorithm is not a combination of existing techniques. We clarify the novelty of our method as follows.

  1. The general nonsmooth nonconvex setting. To the best of our knowledge, existing algorithms with client(-data) sampling for nonsmooth nonconvex optimization require that the objective has some specific structure, e.g., the composite objective (smooth loss + nonsmooth regularization) [1] or weakly convexity [2]. In contrast, our method address the general nonsmooth nonconvex problem, which is more challenging.

  2. Logarithmic dimension dependence and the shared interpolation coefficients.
    We emphasize that our communication upper bound depends only logarithmically on the dimension dd, while that of the baseline method ME-DOL [3] contains an explicit d\sqrt d dependence (see Table 1). This improvement comes from our new proposed scheme, that is, coupling FastGossip with a shared interpolation coefficient sts_t across all clients, which can be implemented by using a shared random seed (see R2 for details).

Specifically our DOC$^2$S takes the shared st∼Unif([0,1])s_t\sim{\rm Unif}([0,1]) across all clients (line 6 of Algorithm 1), which implies wt,i=xt−1,i+stvt,i\mathbf{w}_{t,i} = \mathbf{x}_{t-1,i} +s_t\mathbf{v}_{t,i} and wˉt=xˉt−1+stvˉt\bar{\mathbf{w}}_t=\bar{\mathbf{x}}_{t-1}+s_t\bar{\mathbf{v}}_t. This results E[∣∣wt,i−wˉt∣∣]=E[∣∣xt−1,i−xˉt−1+st(vt,i−vˉt)∣∣]≤E[∣∣xt−1,i−xˉt−1∣∣]+E[st∣∣vt,i−vˉt∣∣]≤2ϵ′,\mathbb{E}[||\mathbf{w}_{t,i}-\bar{\mathbf{w}}_t||] = \mathbb{E}[||\mathbf{x}_{t-1,i}-\bar{\mathbf{x}}_{t-1} +s_t(\mathbf{v}_{t,i}-\bar{\mathbf{v}}_t)||] \leq \mathbb{E}[||\mathbf{x}_{t-1,i}-\bar{\mathbf{x}}_{t-1}||] + \mathbb{E}[s_t||\mathbf{v}_{t,i}-\bar{\mathbf{v}}_t||] \leq 2\epsilon', where the last step uses Lemma 2 and Lemma 1 to bound the consensus error ∣∣xt−1,i−xˉt−1∣∣||\mathbf{x}_{t-1,i}-\bar{\mathbf{x}}_{t-1}|| and ∣∣vt,i−vˉt∣∣||\mathbf{v}_{t,i}-\bar{\mathbf{v}}_t||, respectively. According to the analysis in lines 1040–1050, we take H=O(Ld/μ)H=O(L\sqrt d/\mu) and require ϵ′=O(ϵH)=O(μϵLd).\epsilon' = O\left(\frac{\epsilon}{H}\right) = O\left(\frac{\mu\epsilon}{L\sqrt{d}}\right). Based on Lemma 1, the accuracy ϵ′=O(μϵ/(Ld))\epsilon'=O(\mu\epsilon/(L\sqrt{d})) can be achieved by setting the number of consensus steps as R=O(log⁡(1/ϵ′)γ1/2)=O(log⁡(Ld/(μϵ))γ1/2),R= O\left(\frac{\log(1/\epsilon')}{\gamma^{1/2}}\right)= O\left(\frac{\log(L\sqrt{d}/(\mu\epsilon))}{\gamma^{1/2}}\right), which only contains the logarithmic dependence on dd.

On the other hand, existing method ME-DOL [1] takes independent st,i∼Unif([0,1])s_{t,i}\sim\mathrm{Unif}([0,1]) across all clients, which implies wt,i=xt−1,i+stvt,i\mathbf{w}_{t,i} = \mathbf{x}_{t-1,i} +s_t\mathbf{v}_{t,i} and wˉt=xˉt−1+(1/n)∑j=1nst,jvt,i\bar{\mathbf{w}}_t=\bar{\mathbf{x}}_{t-1}+ (1/n)\sum_{j=1}^n s_{t,j}\mathbf{v}_{t,i}. This results

\leq \mathbb{E}[||\mathbf{x}_{t-1,i}-\bar{\mathbf{x}}_{t-1}||] + \mathbb{E}\Big[\Big|\Big|s_{t,i}\mathbf{v}_{t,i}-\frac{1}{n}\sum_{j=1}^n s_{t,j}\mathbf{v}_{t,j}\Big|\Big|\Big].$$ Note that we cannot guarantee the term $||s_{t,i}\mathbf{v}_{t,i}-(1/n)\sum_{j=1}^n s_{t,j}\mathbf{v}_{t,j}||$ be arbitrary small even if $\mathbf{v}_{t,i}=\bar{\mathbf{v}}_t$ for every $i$, since the clients have different $s_{t,i}$. Hence, the upper bounds of ME-DOL include additional polynomial dependence on $d$, which cannot be avoided even by involving the Chebyshev acceleration. > **W2:** The client data sampling cannot be considered as decentralized: an entity doing the client sampling is required. **R2:** Our client-data sampling is indeed decentralized because each client can **locally** computes its own batch size by multinomial distribution from **a shared random seed**. In fact, the use of shared randomness is very popular in decentralized algorithms, e.g., Section 6 (page 9, paragraph "More efficient Moniqua") of [4], Section 2 (page 3, paragraph "Correlated policy") of [5], and Section 3 (page 9, after Remark 3) of [6]. Similarly, achieving the shared interpolation coefficient $s_t$ also can be implemented in this way. We greatly thank the reviewer for point this out. In our rebuttal revision, we have provided a discussion on the shared randomness in Remark 3 (line 259–263).
AuthorsOpenReview ↗

Official Comment by Authors (2/2)

W3: It is not clear how this method is specifically tailored to nonsmooth optimization: the analysis in the paper is conducted mainly for the smooth case, and the extension to the nonsmooth setting relies on a result from Sahinoglu & Shahramour 2024. Moreover, the smooth-case analysis follows standard tools, and the specific challenge involved in proving the results is not made explicit.

R3: We emphasize that the algorithm and analysis of Sahinoglu & Shahramour [3] results an an explicit d\sqrt d dependence in the complexity bound (see Table 1). In contrast, we introduce a new proposed scheme by coupling FastGossip with a shared interpolation coefficient sts_t across all clients (Lines 5–6 of Algorithm 1), achiving the logarithmic dependence on dd. Please refer to paragraph Logarithmic dimension dependence and the shared interpolation coefficient in R1 for details.

W4-1: The numerical results are insufficient to demonstrate superiority over prior work. An improvement shown only on MNIST is not convincing, and it is unclear whether the experiments use IID or non-IID data distributions across clients (non-IID being more common in practice). Results on additional datasets (e.g., CIFAR) are needed.

R4-1: We conduct experiments under a heterogeneous (non-IID) data setting. Specifically, we partition the dataset among clients according to class labels, each client contains at most data of one label. For the examples of MNIST and Fashion-MNIST (10 classes), we assigned one class of data to each of the 10 client.

We also provide additional experimental results on the CIFAR-10 dataset in Appendix F (1215–1241). The results in Figure 4 shows that the proposed DOC$^2$S outperforms the baseline method on all three metrics, which is consistent with our theoretical results.

W4-2: Furthermore, an ablation study is required: since the proposed algorithm combines client data sampling and Chebyshev acceleration, the ablation study must show the gain achieved by each component.

R4-2: We conduct ablation studies on the Fashion-MNIST dataset to evaluate the gain achieved by FastGossip and client-data sampling in Appendix G (1242–1276). Specifically, we compare our DOC$^2$S with mini-batch size b∈5,10,20,40,80b\in\\{5,10,20,40,80\\} with two baselines: DOC$^2$S by replacing FastGossip with ordinary mixing (DOC$^2$S-Mix) and ME-DOL by replacing ordinary mixing with FastGossip (ME-DOL-FG).

We present the experimental results in terms of sample complexity, computation rounds, and communication rounds in Figure 5. We can observe that FastGossip improves performance across all tested batch sizes. Additionally, with an appropriate mini-batch size, client–data sampling also outperforms the baseline ME-DOL-FG.

Q1: The paper should discuss further how the client data sampling can be implemented in a decentralized way.

A1: The client-data sampling is can be implemented in a decentralized way by using a shared random seed across all clients. Please refer to R2 for details.

Q2: The challenges involved in proving the results in Lemmas 3, 4, 5, and 7 must be highlighted, as the proofs appear to follow standard tools.

A2: The main technical challenge arises in the proof of Lemma 7, which shows that the number of consensus steps RR only has logarithmic dependence on dimension dd.
As discussed in R1, our algorithm uses an identical interpolation coefficient sts_t shared by all clients, whereas existing method ME-DOL [3] draws independent st,is_{t,i} for each client ii.

We greatly thank the reviewer's insightful suggestion. In our rebuttal revision, we have highlighted our novelty in lines 207–212 and 1176–1211.

References

[1] Quoc Tran Dinh, Nhan H. Pham, Dzung Phan, and Lam Nguyen. FedDR – randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization. NeurIPS 2021.

[2] Krishna Pillutla, Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggregation for heterogeneous data. Machine Learning 2024.

[3] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In ICML 2024.

[4] Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In ICML 2020.

[5] Weichao Mao, Lin F. Yang, Kaiqing Zhang, and Tamer Başar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In ICML 2022.

[6] Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Optimal gradient tracking for decentralized optimization. Mathematical Programming 2024.

Thank you for your detailed responses. I agree that shared randomness can be used to make the algorithm decentralised (thank you for this clarification). I noticed also that you have provided additional results using CIFAR-10 dataset. Regarding W1 and your reply: I maintain that the algorithm (not the analysis) is a combination of existing methods.

  1. client sampling is used in FL. The fact that it has been applied under some specific objective structures does not imply that using it in the context of this paper makes the method itself novel.
  2. The proposed algorithm is a combination of existing methods: online to nonconvex conversion., fast gossip, client data sampling.
  3. I believe the value of this paper is in showing numerically and analytically that this combination yields improvements as compared to prior work. I'll carefully re-read the proofs this week (especially Lemma 7) and compare them with the previous works (e.g [3]) to provide a final fair recommendation. I will increase the score if I see differences in the proof.

Thank you again for your efforts in replying to my comments.

Thank you for your careful reading and insightful response. We are pleased that you acknowledged our clarification of shared randomness and our additional experiments on CIFAR-10. However, we think it is inappropriate to regard our method as a combination of existing methods. We would like to further emphasize the novelty of our work in the following respects.

Q3: Client sampling is used in FL. The fact that it has been applied under some specific objective structures does not imply that using it in the context of this paper makes the method itself novel.

A3: Our method has the following essential difference from existing algorithms for FL in the specific nonsmooth nonconvex setting.

  1. Note that existing methods for FL in specific nonsmooth nonconvex setting only include client sampling [1, 2], rather than client-data sampling. In other words, these methods require each client to access the exact local gradient, which is expensive in large-scale applications (In the specific weakly convex setting, paper [2] states that their method can use local stochastic gradients; however, no theoretical analysis is provided). In contrast, our method iterates with the more practical inexact local gradients, so that it includes an additional step of data sampling (line 229) after the step of client sampling (line 225) to construct local gradient estimates.

  2. The proposed client-data sampling strategy is novel, which is based on multinomial batch allocation [bt,1,…,bt,n]⊤∼Multinomial(b,1/n)[b_{t,1},\dots,b_{t,n}]^\top\sim {\rm Multinomial}(b,\mathbf{1}/n). This scheme guarantees each client receives ∑i=1nbi/n=b/n\sum_{i=1}^n b_i/n=b/n samples in expectation. In the case of b<nb<n, our scheme is more computation efficient than the standard uniform sampling, i.e., all clients have the identical number of samples in each iteration. Note that in the case of b<nb<n, the uniform sampling requires each client receives ⌈b/n⌉=1\lceil b/n \rceil=1 sample (rather than b/nb/n), resulting all clients receive nn sample in total. In contrast, our strategy still guarantees that each client receives b/nb/n samples in expectation and all clients receive bb sample in total. Please refer to A2-1 and A2-2 to Reviewer T9pn for details.

  3. The use of shared interpolation coefficient sts_t is specific to the algorithm design for general nonsmooth nonconvex setting, which is novel and has not been proposed by previous works [1–3].

Q4: The proposed algorithm is a combination of existing methods: online to nonconvex conversion, fast gossip, client data sampling.

A4: As we mentioned in above responses, our method includes the new proposed client-data sampling strategy (see A3.1 and A3.2) and the shared interpolation coefficient sts_t (see R1.2 and A3.3), which are not introduced in previous works [1, 2, 3]. Hence, we think our method cannot be regarded as a combination of existing methods.

References

[1] Quoc Tran Dinh, Nhan H. Pham, Dzung Phan, and Lam Nguyen. FedDR – randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization. In NeurIPS 2021.

[2] Krishna Pillutla, Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggregation for heterogeneous data. Machine Learning 2024.

[3] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In ICML 2024.

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

The paper studies decentralized stochastic optimization of Lipschitz, nonsmooth, nonconvex objectives and proposes DOC2S, combining online-to-nonconvex conversion, multinomial client-data sampling, and Chebyshev-accelerated consensus. Its sampling scheme distributes a fixed gradient-evaluation budget across clients, allowing unselected clients to skip computation. The analysis claims that each client can obtain an expected (δ,ϵ)(\delta,\epsilon)-Goldstein stationary point with optimal δ−1ϵ−3\delta^{-1}\epsilon^{-3} dependence, while improving other parameter dependencies over existing methods. The batch size provides a tradeoff between sampling cost and communication efficiency. Experiments on capped-ℓ1\ell_1-regularized SVMs and ReLU neural networks illustrate these benefits across four datasets.

Critical strengths
  1. Client-data sampling gives a useful separation between sampling cost and communication. Allocating a total budget bb through a multinomial distribution allows clients with zero assigned samples to skip gradient evaluations. Crucially, the n/bn/b scaling makes the network-average estimator unbiased for the average local smoothed gradients, while independent oracle noise contributes σ2/b\sigma^2/b. This provides a principled mechanism for trading more samples per iteration against fewer communication rounds.
  2. Accelerated consensus fits the nonsmooth analysis particularly well. Chebyshev gossip preserves network averages and contracts disagreement at approximately exp⁡(−cRγ)\exp(-cR\sqrt{\gamma}), giving an inverse-square-root spectral-gap dependence. Uniform smoothing introduces a smoothness constant proportional to Ld/δL\sqrt d/\delta; sufficiently accurate consensus can absorb this dependence through logarithmic mixing costs. This is a technically valuable design choice for avoiding polynomial dimension dependence in the leading complexity bounds.
Critical weaknesses

The per-client stationarity proof uses an expectation bound as a deterministic guarantee. Lemma 1 bounds velocity disagreement only in expectation, whereas equations (21)~(27) use pointwise disagreement bounds to place the epoch’s evaluation points inside the output’s δ\delta-neighborhood. That geometric inclusion is essential for Goldstein-subdifferential membership and does not follow from expected closeness alone. A repair may be possible using clipping, but the central stationarity guarantee is not established by the argument as written.

Questions for authors
  1. What batch-size regime is intended in Corollary 2? For b<nb<n, can the bound retain the unavoidable cost of at least one computation round per iteration?
  2. Can you provide a deterministic neighborhood bound supporting equations (21)–(27), given that Lemma 1 controls disagreement only in expectation? Please also clarify the consensus-tolerance choice ϵ′\epsilon', which does not generally make the error small.
  3. How do the second-moment bounds account for cross terms within summed local gradients and correlations caused by sharing one smoothing perturbation across a client’s batch?
1 comment

We thank the reviewer eWZa for the detailed and helpful comments.

Q1: What batch-size regime is intended in Corollary 2? For b<nb<n, can the bound retain the unavoidable cost of at least one computation round per iteration?

A1: Thank you for pointing this out. We have revised Corollary 2 (line 364) and its proof to include the unavoidable cost of at least one computation round per iteration (line 1160–1164). Specifically, the complexity bound of computation round changes from O~(((bL2+σ2)Δn−1δ−1ϵ−3)\tilde O(((bL^2+\sigma^2)\Delta n^{-1}\delta^{-1}\epsilon^{-3}) to O~((1+n/b)(bL2+σ2)Δn−1δ−1ϵ−3)\tilde O((1+n/b)(bL^2+\sigma^2)\Delta n^{-1}\delta^{-1}\epsilon^{-3}). When b≥nb\ge n, we have 1+n/b=O(1)1+n/b=O(1), so the revised bound recovers the original one. When b<nb<n, the revised bound simplifies to O~(((L2+σ2/b)Δn−1δ−1ϵ−3)=O~(KT)\tilde O(((L^2+\sigma^2/b)\Delta n^{-1}\delta^{-1}\epsilon^{-3})=\tilde O(KT), which aligns with the fact that each of the KTKT iterations requires at least one computation round.

Q2-1: Can you provide a deterministic neighborhood bound supporting equations (21)–(27), given that Lemma 1 controls disagreement only in expectation?

A2-1: We greatly thank the reviewer for pointing out this out. We have revised Lemma 1 by additionally establishing a deterministic neighborhood bound (line 287), i.e., ∣∣vt,i−vˉt∣∣≤2D||\mathbf{v}_{t,i}-\bar{\mathbf{v}}_t||\le 2D. Specifically, the clipping step (line 233) results the norm of each local vector vt,i\mathbf{v}_{t,i} is at most DD, so that we have ∣∣vt,i∣∣≤D||\mathbf{v}_{t,i}||\le D and ∣∣vˉt∣∣≤D||\bar{\mathbf{v}}_t||\le D. Therefore, we can establish deterministic bound ∣∣vt,i−vˉt∣∣≤2D||\mathbf{v}_{t,i}-\bar{\mathbf{v}}_t||\le 2D by the triangle inequality. Accordingly, we have revised the analysis in equations (21)–(27) by using this deterministic bound (lines 1047 and 1068), thereby resolving the concern regarding the use of an expectation-based bound in previous derivations.

Q2-2: Please also clarify the consensus-tolerance choice ϵ′\epsilon', which does not generally make the error small.

A2-2: We have explicitly specified the choice of ϵ′=O(min⁡{D/(T(L2+σ2/b)),1/H})\epsilon'=O(\min\{D/(T(L^2+\sigma^2/b)),1/H\}) in Lemma 7 (line 343). Note that ϵ′\epsilon' only affects the logarithmic term in the number of consensus steps, i.e., R=O(γ−1/2log⁡(1/ϵ′))R = O(\gamma^{-1/2}\log(1/\epsilon')). Hence, its contribution to the overall complexity is only the logarithmic term, which is absorbed into the O~(⋅)\tilde{ O}(\cdot) notation in Table 1.

Q3: How do the second-moment bounds account for cross terms within summed local gradients and correlations caused by sharing one smoothing perturbation across a client’s batch?

A3: We guess the reviewer's question is about the inequality in lines 751–763. We present the derivation in details as follows

\frac{1}{b}\mathbb{E}[\|\mathbf{G}_{t}\|^2] =& \frac{1}{b}\sum_{i=1}^{n}\mathbb{E}[||\sum_{j=1}^{b_{t,i}} \nabla F_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i};\mathbf{\xi}_{t,i,j})||^2] \\\\ \leq& \frac{1}{b}\sum_{i=1}^{n}\mathbb{E}\left[\left(\sum_{j=1}^{b_{t,i}}|| \nabla F_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i};\mathbf{\xi}_{t,i,j})||\right)^2\right] \\\\ \leq& \frac{1}{b}\sum_{i=1}^{n}\left( b_i\sum_{j=1}^{b_{t,i}}\mathbb{E}\left[|| \nabla F_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i};\mathbf{\xi}_{t,i,j})||^2\right]\right) \\\\ \leq& \sum_{i=1}^{n}\sum_{j=1}^{b_{t,i}}\mathbb{E}\left[2||\nabla F_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i})||^2 +2|| \nabla F_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i};\mathbf{\xi}_{t,i,j})-\nabla f_i(\mathbf{w}_{t,i}+\mu \mathbf{z}_{t,i})||^2 \right] \\\\ \leq& 2b(L^2+\sigma^2), \end{aligned}$$ where the second step comes from the triangle inequality; the third step comes from Cauchy–Schwarz inequality; the fourth step comes from Young's inequality and the fact the $b_i\le b$; and the last step comes from Assumptions 1 and 3 and the fact $\sum_{i=1}^{n} b_{t,i} = b$. Here, we find the upper bound of $\frac{1}{b}\mathbb{E}[||\mathbf{G}_{t}||^2]$ should contain additional factor $b$, which is updated in our revision (see lines 758 and 763). Following our derivations in lines 767–790, the upper bound of $\mathbb{E}[||\mathbf{G}_{t}||^2]$ only appears in the logarithmic term of the number of consensus steps $R$ in Lemma 1, so that this modification does not affect our main results. We greatly thank the reviewer's careful reading and point this out.
Reviewer_T9pnOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper develops a decentralized stochastic nonsmooth nonconvex optimization algorithm that utilizes local client data sampling and Chebyshev acceleration. The authors claim this new algorithm eliminates dependency on dimension dd.

Critical strengths

Chebyshev acceleration is a good technique to speed up algorithm convergence.

Critical weaknesses
  1. Table 1 suggests the proposed algorithm does not scale with dimension dd, whereas other existing method does. However, the gradient Lipschitz constant HH scales with d\sqrt{d}. This constant appears in ϵ′\epsilon' as well. So the dependency on dd is there in a somewhat hidden way, but Table 1 is a bit misleading.

  2. Why choosing client batch sizes according to multinomial is a good idea? Would uniform sampling b/nb/n work as well? If this is done for martingale analysis, then how does the random sampling translate into real system's delay/processing time? It seems by using a non-uniform sampling scheme, at each round the system would have to wait for the slowest agent to finish (perhaps the one with the most amount of data) and creates unnecessary engineering hurdles for the algorithm.

  3. I don't understand the comment after Table 1, where the authors are talking about bounded gradient norm by G2G^2 factor. This seems to be also assumed in Lemma 1.

Questions for authors

See weakness

3 comments

We thank the reviewer T9pn for the detailed and helpful comments.

Q1: Table 1 suggests the proposed algorithm does not scale with dimension dd, whereas other existing method does. However, the gradient Lipschitz constant HH scales with d\sqrt{d}. This constant appears in ϵ′\epsilon' as well. So the dependency on dd is there in a somewhat hidden way, but Table 1 is a bit misleading.

A1: We thank the reviewer for pointing this out. Note that the dependence of HH, dd and 1/ϵ′1/\epsilon' appears in our complexity bound are only inside the logarithmic term. Specifically, it only affects the number of consensus steps (see Lemma 7) R=O(γ−1/2log⁡(1/ϵ′))R = O(\gamma^{-1/2}\log(1/\epsilon')), where ϵ′=O(min⁡{D/(T(L2+σ2/b)),1/H})\epsilon'=O(\min\{D/(T(L^2+\sigma^2/b)),1/H\}). Hence, the resulting dependence on the dimension dd (or HH) is at most logarithmic, rather than polynomial. In rebuttal revision, we have highlighted that the notation O~(⋅)\tilde O(\cdot) hides the logarithmic factors (line 57) and the settings of RR and ϵ′\epsilon' (lines 342–343 and 357–358).

Q2-1: Why choosing client batch sizes according to multinomial is a good idea? Would uniform sampling b/nb/n work as well?

A2-1: According to the definition of multinomial distribution, our multinomial sampling scheme in Algorithm 1 (lines 225 and 231) is equivalent to sampling a client uniformly at random (with replacement) for each of the bb stochastic gradient evaluations. This ensures that each client receives b/nb/n samples in expectation. Note that in the case of b<nb<n, the uniform sampling (we guess the uniform sampling mentioned by the reviewer means all clients have the identical number of stochastic gradient evaluations) requires each client receives ⌈b/n⌉=1\lceil b/n \rceil=1 sample (rather than b/nb/n), resulting all clients receive nn sample in total. In contrast, our strategy still guarantees that each client receives b/nb/n samples in expectation and all clients receive bb sample in total, which is more efficient than the uniform sampling.

Q2-2: If this is done for martingale analysis, then how does the random sampling translate into real system's delay/processing time? It seems by using a non-uniform sampling scheme, at each round the system would have to wait for the slowest agent to finish (perhaps the one with the most amount of data) and creates unnecessary engineering hurdles for the algorithm?

A2-2: In Corollary 2 (lines 362–365), we provide the upper bound on expected computational rounds to describe the processing time in computation, which is widely used in the analysis for stochastic optimization methods with randomized batch sizes [1–3]. Specifically, Lemma 13 (lines 1118–1139) and Corollary 2 (lines 362–365) show that in each iteration, the expected maximum number of stochastic gradient evaluations assigned to any client is bounded by O(b/n+log⁡n)O(b/n+\log n). Thus, the additional computational rounds (delay/processing time) introduced by multinomial sampling is at most O(log⁡n)O(\log n).

Q3: I don't understand the comment after Table 1, where the authors are talking about bounded gradient norm by G2G^2 factor. This seems to be also assumed in Lemma 1.

A3: We thank the reviewer for pointing this out. The term G2G^2 in Lemma 1 was a typo and should be L2L^2. We have corrected it in the rebuttal revision (see line 267). We hope this addresses the reviewer's concern.

References

[1] Zeyuan Allen-Zhu. Katyusha X: Simple momentum method for stochastic sum-of-nonconvex optimization. In ICML 2018.

[2] Yunyan Bai, Yuxing Liu, and Luo Luo. On the complexity of finite-sum smooth optimization under the Polyak–Lojasiewicz condition. In ICML 2024.

[3] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: a simple and optimal probabilistic gradient estimator for nonconvex optimization. In ICML 2021.

Ah, thank the authors for clarifying the issues. The authors have addressed my main concerns on the technical level. I'm increasing my score from 2 to 3.

Thank you for raising your score. We appreciate your time and effort in reviewing our work and are glad that our clarifications have addressed your main concerns.

Comments on the paper

1 comment

Dear Reviewers and Area Chair,

We sincerely thank you for your time and thoughtful comments. We have responded to your questions point by point and revised the manuscript accordingly. We would be grateful if you could let us know whether our responses and revision have addressed your concerns. We welcome any further questions and would be happy to provide additional clarification.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.