iFedDR: Auto-Tuning Local Computation with Inexact Douglas-Rachford Splitting in Federated Learning

We thank the reviewer for the feedback and address all remaining concerns below.

Alternative methods to Douglas-Rachford splitting (DRS)

One alternative to the primal problem (2.4a) is the forward-backward splitting (FBS) which proceeds as follows:

$\mathbf x^{k+1} = (\operatorname{id} + \gamma B)^{-1}(\mathbf x^k - \gamma A(\mathbf x^k))$

There are mainly two reasons for why we consider DRS instead:

• FBS may not converge when the operator $A$ is merely monotone. Monotonicity is important for moving beyond minimization and capturing e.g. convex-concave minimax problems.
• FBS applied to FL reduces to aggregating gradients on the clients and requires additional conditions on the stepsize $\gamma$. In contrast, using DRS we can move the bulk of the computation to each client (through the proximal subproblem) and take large stepsizes. Having an explicit client subproblem additionally allows us to use any fast solver for the subproblem (as comment on in l. 245-255).

We thank the reviewer for the suggestion and have included a remark regarding FBS after the introduction of DRS in the updated version.

Interpretation of $s$ and definition of $m$

• The integer $m$ is defined through the min-operator in Theorem 3.1(ii). Its is the total number of communication rounds, which we now explicitly state to make it more apparent.
• The iterate $\mathbf s^k$ in DRS is the running sum of residuals and is simply an auxilliary variable. The more relevant quantities are $\mathbf u^k$ and $\mathbf v^k$ which are gauranteed to converge to a solution of the primal problem. In the context of FL, these correspond to the client states $\bar x^k_i$ and the server average $\hat p^k$ respectively.

Discussion of limitation (e.g., convexity)

We have tried to be transparent about focusing on convexity (or more generally monotonicity) throughout the writeup and also explicitly mention extending to nonconvex problems as an interesting direction in the conclusion. With that said, it is worth mentioning that without changing our analysis, our work can immediately be generalized to all variationally stable games, which handles certain nonconvex cases even in the multiplayer setting.

Regarding experiments, we go beyond other theoretical work such as the celebrated ProxSkip paper, which only tests on logistic regression on a single dataset (w8a). In comparison we evaluated on:

• logistic regression on the vehicle dataset and w8a
• linear probing on CIFAR10 and Fashion-MNIST
• fair classification

Evaluation on nonconvex neural network training is definitely interesting, but requires its own dedicated treatment.

Questions:

What types of constraints can the algorithm handle?

The algorithm can specifically handle projectable constraints (specifically $(\operatorname{id} + \gamma G)^{-1}$ in Step I.2 of Algorithm 1 reduces to a projection, when $G=\partial g$ and $g$ is the indicator function of some closed convex set). A concrete example is provided in the fair classification experiments, which is a minimax problem involving a simplex constraint.

Imbalanced client loads

Notice that the error condition involves a sum over the clients. In other words, iFedDR does not require an error condition to hold for each of the clients individually. So as long as the sum is small enough, some clients can have large error.

Is the proposed method extendable to allow for asynchronous updates?

This is definitely an interesting direction to consider, but outside the scope of this work.

We thank the reviewer for the feedback and address all remaining concerns below.

On "computationally negligible error condition"

The error condition is computationally negligible in Step I.2 of Algorithm I, since it only involves computing norms and inner products which are additionally carried out on the (computationally efficient) server. This is detailed in Remark D.3 referenced in the Algorithm I.

Regarding $\zeta$, it is important to clarify that the error condition, $err_k \leq \sigma^2\max \{\xi_k, \zeta_k\}$, is computationally negligible even when $\zeta$ is involved. However, if a simpler error condition is desired, $\zeta$ can simply be ignored by instead requiring $err_k \leq \sigma^2\xi_k$, while the same theoretical results still apply. The stopping criterion would just become slightly more stringent.

Computation of the client update (3.3)

We detail this in the paragraph "client subproblem" (l. 200-208). The approximate client update in (3.3) is equivalent to approximately solving a strongly monotone and Lipschitz subproblem. This can be done with an iterative solver such as the gradient method.

In the special case of minimization this reduces to computing an approximate proximal update, i.e. approximately solving

$\min_x f_i(x) + \frac{1}{2\gamma} \Vert x - s_i^k\Vert^2$

We have added a reference in "client subproblem" to the Appendix D.3 which describes this special case.

Questions:

"If I understand correctly, automatically adjusting the number of location computations needed is a “trade-off” in the sense that instead the step size $\gamma$ needs to be tuned"

This proximal stepsize $\gamma$ already appears in existing prox-based methods such as FedProx and FedDR. So iFedDR does not introduce another $\gamma$ parameter to be tuned, but rather mitigates the need to predefine the number of local steps $\tau$. Note, that the choice $\gamma=1$ works well throughout our experiments. In the updated revision we have moved our method comparison table from the appendix to the main body (now Table 1), which hopefully makes the comparison clearer.

"In line of above comment, could the authors comment on other federated learning works that use adaptive step size, such as [1,2]?"

The two works can be summarized as follows:

• The reference [1] uses FedAvg with the (adaptive) Polyak stepsize as the client stepsize.
• [2] uses an adaptive client stepsize that tries to estimate the local smoothness.

Our work is orthogonal to both works, and can in fact be combined with any fast client update, including schemes with various forms of adaptive stepsize. This modularity is the benefit of our method having an explicit client subproblem (see Section 3, l. 245-255).

Our work is not concerned with adapting the client stepsize, but rather:

• The adaptive stepsize $\alpha_k$ in iFedDR, which corresponds to the server stepsize in FedAvg.
• Our main interest is in automating the number of steps taken by the clients, and not auto-tuning the client stepsize.

Can the server step size and client step size be decoupled?

The stepsizes are already decoupled in the following sense:

• There is $\gamma$ which is the proximal stepsize (this controls how far the client updates can move)
• There is the client stepsize $\eta$ used for the solver of the proximal subproblem, which is picked based on $\gamma$ through the conditioning number (see Table 1)
• There is $\lambda$ which plays the role of the server stepsize and this can be picked independently of $\gamma$ and $\eta$

Can $\zeta_k$ be ignored?

The error condition can ignore $\zeta_k$ while still maintaining the same theoretically gaurantees. The only consequence is that the resulting error condition is slightly more stringent (so more iterations are needed of the client subsolver). This is a consequence of $err_k \leq \sigma^2\max \{ \xi_k, \zeta_k \}$ being directly implied by the stricter error condition $err_k \leq \sigma^2\xi_k$.

Clarification of reductions

Regarding the problem reformulation, the main steps carried out in Section 2 are:

• We start with the original finite-sum problem (2.1)
• We consider the lifted consensus reformulation (2.4a) which introducing a consensus constraint (this allows us to model $N$ distinct client states)
• This is the problem we solve with an extension of Douglas-Rachford splitting

To obtain iFedDR from iPPPA simply pick $T=T_{\text{PD}}$ and $P$ as detailed in (4.2). With the consensus constraint in (2.4b) the algorithm reduces to iFedDR. After making those two choices, all that remains is a sequence of algebraic steps to simplify the update expression (the step by step reduction can be found in Appendix D.1-D.2).

We thank the reviewer for the feedback and address all remaining concerns below.

Table for comparison

The appendix already included a table comparing iFedDR with existing methods. We agree with the reviewer that it might be helpful to make this table more visible, so we have pulled this into the main body (see Table 1).

To summarize the table, iFedDR achieves a $\mathcal O(\tfrac{1}{m \gamma^3})$ rate, where $m$ is the total number of communication rounds and $\gamma$ is the proximal stepsize. Notice that the rate improves with increasing $\gamma$ and that this stepsize is not restricted by the Lipschitz constant $L$. The tradeoff is that increasing $\gamma$ leads to harder client subproblems, for which the number of steps $\tau$ of the iterative solver is automatically picked. In comparison:

• FedDR requires $\gamma <1/L$ in the analysis (and needs $\tau$ predefined).
• FedProx requires $\gamma \rightarrow 0$, which in turn hurts the complexity (and needs $\tau$ predefined).
• Scaffold obtains a $\tilde{\mathcal{O}}(L/m)$ rate, so has no parameter $\gamma$ to improve the rate (and needs $\tau$ predefined).

Section structure

The main reason for leading with a section on iFedDR (including theorems) is for accessibility:

• The separation allows us to discuss the structure of the algorithm in the context of FL (e.g. the client subproblem and the computation of the adaptive quantities)
• Including the convergence result (Thm. 3.1) allows us to remark on important FL concepts like e.g. the communication rate, heterogeneity agnostic, the tradeoff between communication and local computation, etc (see Remark 3.2).

Theorem 5.1 regarding iPPPA is indeed more general, but the aim with having a separate section on iFedDR is to present iFedDR and its properties without requiring understanding of the higher abstraction level of iPPPA. Additionally, iPPPA has its own dedicated section, since the method is interesting in its own right, and a contribution on its own. For this reason and for clarifying how we arrived at iFedDR we prefer to present both theorems.

Making the plots PDFs

Thank you for the suggestion, we have updated all plots to PDFs. They are hopefully easier to read now.