# Entropy-Regularized Federated Optimization for Non-IID Data
## 3 Methodology
### Convergence Analysis  
We now present a theoretical convergence analysis for ERFO. We first consider the case of a fixed regularization weight \(\lambda\) and then discuss the decaying \(\lambda_{t}\) scenario. Our analysis is in the context of convex optimization and leverages standard assumptions used in federated learning theory. Assumptions: We assume that each client's loss \(F_{i}(w)\) is convex and \(L\)-smooth (i.e., its gradient is \(L\)-Lipschitz). We also assume that the overall objective \(F(w)=\sum_{i=1}^{N}\frac{n_{i}}{n}F_{i}(w)\) (where \(n=\sum_{i}n_{i}\)) has a unique minimizer \(w\) (for example, \(F(w)\) could be strongly convex to guarantee uniqueness, though strong convexity is not strictly required for convergence--it will, however, yield linear convergence rates). We ignore the effect of client sampling or stochastic gradient noise in this sketch and assume that all clients participate in each round, and full-batch gradients are used for the simplicity of theoretical exposition. Under these conditions, FedAvg is known to converge to \(w\) (or within a small ball if only a few local steps are taken) at a rate of \(O(1/t)\) for convex objectives (or a linear rate of \(O(\rho^{t})\) if both strong convexity is assumed and step sizes are chosen appropriately). For ERFO, the presence of the entropy term modifies the local update dynamics. Nonetheless, we can bound its influence. First, note that the entropy gradient \(g_{H}\) in Equation (5) is bounded: since \(0\leq p_{j}\leq 1\), we have \(|\ln p_{j}|\leq\ln d\) (the extreme case is that one coordinate carries all weight, where \(p_{j}=1\) gives \(\ln p_{j}=0\) or \(p_{j}=1/d\) gives \(\ln p_{j}=-\ln d\)). Also, \(\sum_{k}p_{k}\ln p_{k}\in[-\ln d,0]\). Thus the numerator in Equation (5) satisfies \(|\sum_{k}p_{k}\ln p_{k}-\ln p_{j}|\leq\ln d\). The denominator \(Z=\sum_{k}|w_{k}-w_{k}^{t}|\) is the \(L^{1}\) norm of the update; in practice this will be limited by the convergence of local training (one could also enforce a bound by early stopping of local epochs if needed). Assuming bounded \(Z\) (or switching to an \(L^{2}\)-normalized \(p\), which would naturally bound the influence of large updates), we can assert that \(|g_{H}|\) is bounded by some constant \(G_{H}\). Intuitively, \(g_{H}\) does not blow up unless the model update becomes extremely large or extremely concentrated on a single parameter, both of which can be controlled. Under these conditions, we can establish convergence for ERFO as follows:  
**Theorem 1** (Convergence with fixed \(\lambda\)). : _Suppose each \(F_{i}(w)\) is convex and \(L\)-smooth, and let \(\lambda_{t}=\lambda\) for all rounds (ERFO-Fixed). Let \(\eta\) be a constant step size for local gradient descent that is small enough to satisfy \(0<\eta L(1+\lambda G_{H})<2\) (ensuring descent in the presence of the entropy gradient, where \(G_{H}\) bounds the Lipschitz constant or the norm of \(g_{H}\) as discussed). Then Algorithm 1 (ERFO-Fixed) converges to a neighborhood of the optimal solution \(w^{*}\) of the unregularized objective \(F(w)=\sum\frac{n_{i}}{n}F_{i}(w)\). In particular, after \(T\) rounds the global model \(w^{T}\) satisfies_  
\[F\big{(}w_{T}\big{)}\ -\ F\big{(}w^{*}\big{)}\ \leq\ \mathcal{O}\big{(}T^{-1} \big{)}\ +\ \mathcal{O}(\lambda). \tag{8}\]  
_i.e., suboptimality decreases at the usual \(O(1/T)\) rate down to an error floor on the order of \(\lambda\). Furthermore, if \(F(w)\) is \(\mu\)-strongly convex, \(w^{T}\) converges linearly to a point within \(O(\lambda)\) of \(w^{*}\)._Proof Sketch. : The proof follows the outline of standard FedAvg convergence proofs, with additional terms accounting for entropy regularization. One can view ERFO-Fixed as performing (approximate) gradient descent on the modified global objective \(\widehat{F}(w)=F(w)+\lambda\Phi(w)\), where \(\Phi(w)\) represents the expected entropy term aggregated over all clients.