Safe-EF: Error Feedback for Non-smooth Constrained Optimization

1. We thank the reviewer for this valuable comment and pointing out this reference! Indeed, the workers cloning idea described in that paper can be extended to our result in convex (smooth) setting. We have revisited the convergence analysis of EF21 in our supplementary Theorem C.1. following the analysis from the proposed reference. The updated rate is $\mathbb{E}[f(x^T) - f(x^*)] \le \frac{R_{\mathcal{X}}^2}{\gamma T}\left(1+ \log\left(\frac{\gamma \Lambda_0 T}{R_{\mathcal{X}}^2}\right)\right),$ where $\gamma \le \mathcal{O}\left(\frac{\delta}{\frac{1}{n}\sum_{i=1}^nL_i}\right).$ The potential improvement compared to our Theorem C.1. is in the difference between the average $\frac{1}{n}\sum_{i=1}^nL_i$ and the quadratic mean $\sqrt{\frac{1}{n}\sum_{i=1}^n L_i^2}$. This derivation follows directly from our analysis by replacing equation (15) in the proof of Theorem C.1. with more refined Lemma 7 in Appendix C.1. of the suggested paper. We will include the improved derivation in the next revision and cite the missing reference.
2. We appreciate this useful suggestion. The hyperparameters used in Section 6.1 are provided in Appendix I. We perform a grid search over several choices of $\gamma$ and select the one that gives the smallest train loss at the end of training. Table 1 in Appendix I gives concrete numbers for the selected step size for each heterogeneity level $s = 0.1, 1.0, 10.0$. In Safe RL experiment, we don’t tune the hyper-parameters and use the default step-size $\gamma = 10^{-4}$ from the (non-distributed) PPO implementation that is known to work well on standard RL benchmarks. The slackness parameter $c$ is set to $0$, which is sufficient to get decent performance for both tasks. We did not try to further tune these parameters and agree that, in general, these parameters are problem-dependent. We will clarify these details in the revision, thank you for this advice!
3. Thank you for bringing this to our attention. We highlight that we use $5$ seeds for all of our RL experiments, as also mentioned in the “Setup” paragraph of section 6.2.
4. We emphasize that the choice of $c$ highly depends on the application. The choice of $c$ is dictated by the fact of how much constraint intolerance we can allow. From theory perspective, the choice of hyperparameters $\gamma = \mathcal{O}(\frac{R\sqrt{\delta\delta_s }}{M\sqrt{T}})$ and $c=\mathcal{O}(\frac{MR}{\sqrt{\delta\delta_s T}})$ depends on the compression levels $\delta$ and $\delta_{s}$, the gradient bound $M$, number of iterations $T,$ and the upper bound on the initial distance to the optimal set $R=\\|x^0-x^*\\|^2.$ The compression levels and the number of iterations are typically known beforehand as it is a user who sets them. Therefore, there is no need to estimate them. To set $\gamma$ and $c$ we should provide an estimate on $M$ and $R.$ For example, we can estimate $M = \max_i\\|f_i^\prime(x^0)\\|$ and set $R \geq \\|x^0\\|,$ if $x^*$ is close to zero. In general, we believe that choosing $\gamma, c = \mathcal{O}(1/\sqrt{T})$ or diminishing $\gamma, c = \mathcal{O}(1/\sqrt{t})$, $1 \leq t \leq T$, can be a good starting point.

We appreciate the reviewer for their thoughtful feedback! We believe we have addressed the main concerns (1–4) and would appreciate if you could confirm that everything is resolved and consider adjusting the score.

1. We appreciate the reviewer’s comment and agree that further elaboration on the lack of prior work in this area would strengthen the manuscript. To the best of our knowledge, constrained optimization with communication compression remains largely unexplored. In fact, besides the two works we cited—(Fatkhullin et al, 2021), which considers projection-based methods, and (Nazykov et al, 2024), which employs linear minimization oracles—we are unaware of any other studies that explicitly address even simple constrained problems in the presence of contractive compression. In the more limited setting with Rand-$K$ operator (unbiased compressor), the recent work (Laurent Condat and Peter Richt{'a}rik. Randprox: Primal-dual optimization algorithms with randomized proximal updates, 2023) has established some results in the proximal setting. However, this is still limited to constraints/proximal functions with simple structure (e.g., Euclidean ball, simplex, affine constraints, etc).

   The situation becomes even more challenging when considering the general constraints of the form (4) in the manuscript, as no existing work tackles such cases. Fundamentally, addressing this problem requires overcoming new technical difficulties arising from the interaction between constrained optimization and communication compression. Specifically, in addition to the usual error accumulation from compression in unconstrained settings, constrained problems introduce further complexities: (i) compression errors affect the feasibility of iterates, making it harder to ensure constraint satisfaction, and (ii) primal-dual methods introduce an additional projection step, which requires the control of errors from projection, the objective and constraint updates simultaneously. These challenges necessitate novel algorithmic techniques, which we discuss in the subsequent paragraph of our introduction by distinguishing between primal-only and primal-dual approaches.

   We will revise the manuscript to clarify these points and emphasize the fundamental difficulties that remain open in this research direction.

2. We thank the reviewer for providing the references. We agree that these studies are relevant to our work, and we will incorporate them in the introduction. These papers examine a general case of SGD with biased stochastic gradients. The special case of their analyses is CGD, described in the introduction. However, their analysis does not fully align with our setting because they consider (i) a single-node training regime $n=1$, (ii) $L$-smooth functions while we focus on a non-smooth setting, and (iii) a plain SGD without a memory buffer to mitigate the bias (e.g., the compression error). Nonetheless, we agree that extending our results from unbiased gradients to biased ones is an interesting research direction for future work.

3. Currently, a detailed description of the stochastic setting is provided in section F due to the page limit. We will try to reorganize the main body to fit the description in the main paper. We appreciate this suggestion.

4. The logarithmic dependency on the failure probability $\beta$ is a typical outcome of the high probability analysis that comes from the use of concentration inequalities [1,2]. To the best of our knowledge, the logarithmic dependency on the failure probability cannot be avoided as there exists a lower bound for a sample complexity of any learning algorithm Theorem 5.2 in [3]. We will add a note on this aspect in the revised version of the paper.

   [1] Nemirovski et al., Robust stochastic approximation approach to stochastic programming, SIAM 2009

   [2] Ghadimi & Lan, Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework, SIAM 2012

   [3] Anthony & Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 2009

1. We appreciate the reviewer's high evaluation of our theoretical guarantees and empirical results. For empirical evaluation, we (i) test our method on a well-controlled synthetic environment with different levels of heterogeneity and (ii) provide an extensive ablation study in more challenging continuous control environments (Cartpole and Humanoid). We believe the latter Federated Safe RL setting is one of the most relevant and challenging applications of our theory that tests the real potential of Safe-EF. Different transition dynamics $p_i$ of each worker make the loss $f_i$ different, resulting in a highly heterogeneous setting. We mentioned this aspect in Section 6.2 and Appendix I, but we will put more emphasis on the heterogeneity aspect in the revision. In our work, we focus on non-smoothness, safety constraints, biased and bidirectional compression. Decentralized aggregation is an important topic, and we leave it to future work.
2. We test Safe-EF on Neyman-Pearson (NP) classification problem following the work (He et al., Federated Learning with Convex Global and Local Constraints, TMLR 2024). This statistical formulation aims to minimize type II error while enforcing an upper bound on type I error, making it particularly relevant for applications with asymmetric misclassification costs, such as medical diagnosis. The NP classification is $\min_xf(x)=\frac{1}{n_0}\sum_{i=1}^{n_0}\phi(h_{x}, z_{i,0}),\text{ s.t. }\quad g(x)=\frac{1}{n_1}\sum_{i=1}^{n_1}\phi(h_{x}, z_{i,1})\le c,$ where $f_x$ is a classifier parameterized by $x$ (3 layers MLP with 64 units in each layer and Relu activation); $\phi$ is a CE loss; $\\{z_{i,0}\\}\_{i=1}^{n_0}$ and $\\{z_{i,1}\\}_{i=1}^{n_1}$ are training samples from class 0 and class 1, respectively. The constraint ensures that the classification error for class 1 does not exceed a predefined threshold $c$. We include the results in https://ibb.co/SXYqWQtB. This benchmark further supports the argument that Safe-EF is useful for federated learning by showing its effectiveness in a well-established classification framework. We believe the Federated Safe RL remains the most relevant application naturally formulated as a stochastic optimization of the form (72), (73) in Appendix F (unlike the standard supervised learning task with finite dataset), but we welcome the reviewer for a discussion if this new set of experiments strengthens our argument that Safe-EF is useful for FL.
3. While we show our hard instance (functions, constraints, compressors) in the main paper, we will detail key steps of the proof in the revised version of the paper.
4. The design of EF21 algorithm can be seen as a variance reduction (VR) technique. In a nonsmooth setting, gradients can change abruptly. Thus, VR mechanisms such as EF21 may fail. In contrast, EF14 algorithm's design is based on tracking the compression error, and the control of gradient change is not needed.
5. We acknowledge reviewer's concern. From theory, in the choice $\gamma=O(\frac{R\sqrt{\delta\delta_s }}{M\sqrt{T}})$ and $c=O(\frac{MR}{\sqrt{\delta\delta_s T}})$ parameters $\delta,\delta_s,T$ are typically set by a user. Thus, there is no need to estimate them. We can estimate $M=\max_i\\|f_i^\prime(x^0)\\|$ and $R>\\|x^0\\|,$ if $x^*$ is close to zero. In general, we believe that choosing $\gamma,c=O(1/\sqrt{T})$ or $O(1/\sqrt{t})$ can be a good starting point. In our experiments, $\gamma=$1e-4 is chosen based on existing default value that is known to work well for PPO on standard RL benchmarks. The slackness parameter $c$ is set to 0, which is sufficient to get decent performance for both tasks. We did not try to further tune these parameters and agree that, in general, these parameters are problem-dependent.
6. Thank you for pointing this out. Based on your suggestion, we will add additional details on our experimental setup to Appendix I. We kindly ask the reviewer to point out more specifically which parts in the exposition should be further clarified. Additionally, we emphasize that the code for our experiments can be found in https://anonymous.4open.science/r/safe-ef-3ABC, as mentioned in Appendix I. We believe that this makes our experiments fairly easy to reproduce.
7. We reference all relevant work within each subsection or paragraph of the introduction while discussing practical challenges and existing solutions. While we can divide the first section into an introduction and practical challenges, separating the related work into a standalone section would not be appropriate. Any additional related work that is not directly relevant to our main narrative is included in the appendix.
8. Investigating convergence in the non-convex setting is indeed an interesting and important question motivated by real-world RL problems. We believe our analysis can be extended to weakly convex functions, i.e., $f(x)+r\\|x\\|^2$ and $g(x)+r\\|x\\|^2$ are convex following, e.g., (Jia and Grimmer, 2022); (Boob et al., 2023)