Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimization

1. Some highly relevant works are not cited. For instance, [1] and [2] discuss storm-like algorithms for compositional optimization problems, while [3] addresses momentum-based federated methods for distributed compositional optimization.
2. The improvement presented in the paper appears to be incremental. The use of an adaptive matrix is not novel within adaptive algorithms, as similar approaches have been explored, such as in [4]. In the distributed setting, the adaptive matrix operates independently on each client without communication. While communicating this matrix would be computationally expensive and unnecessary, this choice makes the theoretical analysis closely resemble that of the non-federated setting. As a result, the contribution of this paper is trivial, limiting its overall novelty.
3. There is a typo in Eq.(4), a_t should have a squared root.

[1] Huizhuo Yuan, Wenqing Hu. Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization, arXiv preprint arXiv: 2006.01688, 2020. [2] Liu, Jin, et al. Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization. Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 12. 2024. [3] Zhang, Xinwen, et al. Federated compositional deep auc maximization. Advances in Neural Information Processing Systems 36 (2024). [4] Feihu Huang, et al. Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 34:9074–9085, 2021b.

• The literature review is not up-to-date. It seems the authors only considered works up to 2022. As far as I know, there are more recent works on Distributed/ Federated Composition Optimization (e.g., [1], [2], [3]). The authors should conduct a more thorough literature review.
  [1] Hongchang Gao. A Doubly Recursive Stochastic Compositional Gradient Descent Method for Federated Multi-Level Compositional Optimization. ICML 2024.
  [2] Xidong Wu et al. Federated Conditional Stochastic Optimization. NeurIPS 2023.
  [3] Xinwen Zhang et al. Federated Compositional Deep AUC Maximization. NeurIPS 2023.

• Novelty of this Approach: Upon review, there appears to be an overlap with recent advances, specifically with the Fed-DR-SCGD algorithm published at the ICML proceedings in early May (Fed-DR-SCGD Paper). This algorithm demonstrates comparable sample complexity of $O\left(\frac{1}{\epsilon^3}\right)$ and communication complexity of $O\left(\frac{1}{\epsilon^2}\right)$. Given this context, comparing Fed-DR-SCGD would strengthen the paper’s contribution and clarify its unique value. Could the authors highlight any distinctive advantages of MFCGD / AdaMFCGD over Fed-DR-SCGD?

• Lack of Explicit Dependence on the Number of Machines $M$: The convergence rates in Theorem 1. and Theorem 2. do not explicitly depend on the number of machines $M$, which is atypical in distributed stochastic optimization. In many distributed settings, the convergence rate often scales with the number of machines, reflecting the collective contribution to reducing variance and accelerating convergence.

• Unavailable Code: The absence of available code for the experiments reduces the transparency of the results, making it challenging to validate the findings and restricting the community's ability to build upon this work.

• The proof of Lemma 6 seems to be problematic. How can you get (27) from (26)? To be specific, how can you get $<w\_t^m,\frac{1}{\eta\_t \gamma}(\bar{x}\_t - \bar{x}\_{t+1})>$ from $\frac{1}{M}\sum_{m=1}^M<w\_t^m,\frac{1}{\eta\_t \gamma}(x\_t^m - x\_{t+1}^m)>$? Note that $w\_t^m$ also depends on $m$.
• The title "Federated Methods for Distributed Compositional Optimization" is potentially misleading. Federated learning and distributed learning are fundamentally distinct paradigms, each with different settings, assumptions (on data and clients), and requirements. See, e.g., Table 1.1 in [3]. Using these terms interchangeably is quite confusing.
• In lines 18 and 19 of Algorithm 1, the proposed algorithms require projection onto balls with unknown problem-specific constants $C_g$ and $C_f$. This limits the applicability of the proposed algorithm.
• Client sampling is highly desirable in the cross-device federated learning regime since the total number of clients M is quite large. Unfortunately, the proposed algorithms in this paper do not support this feature.
• The function g in (10) is an exponential function. It makes no sense to assume its stochastic gradient is Lipschitz and bounded (as in Assumption 2 and Assumption 3), considering the model w in this paper is unconstrained.
• The numerical experiments cannot fully verify the robustness of the proposed AdaMFCGD algorithm without comparing it to standard local algorithms such as FedAvg and SCAFFOLD. This can justify why the composition optimization problem in (10) is meaningful and whether it can improve the robustness compared to Federated ERM.

[3] Kairouz, Peter, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz et al. "Advances and open problems in federated learning." Foundations and trends® in machine learning 14, no. 1–2 (2021): 1-210.