A Statistical Analysis of Deep Federated Learning for Intrinsically Low-dimensional Data
It addresses generalization error in federated learning for heterogeneous clients, which is an incremental contribution to existing optimization-focused research.
This paper tackles the problem of analyzing generalization error in deep federated regression for heterogeneous data, showing that convergence rates depend on the intrinsic dimension rather than nominal high dimensionality, with error rates scaling as $ ilde{O}((mn)^{-2eta/(2eta + ar{d}_{2eta}(\lambda))})$ for participating clients and $ ilde{O}(\Delta \cdot m^{-2eta/(2eta + ar{d}_{2eta}(\lambda))} + (mn)^{-2eta/(2eta + ar{d}_{2eta}(\lambda))})$ for non-participating clients.
Despite significant research on the optimization aspects of federated learning, the exploration of generalization error, especially in the realm of heterogeneous federated learning, remains an area that has been insufficiently investigated, primarily limited to developments in the parametric regime. This paper delves into the generalization properties of deep federated regression within a two-stage sampling model. Our findings reveal that the intrinsic dimension, characterized by the entropic dimension, plays a pivotal role in determining the convergence rates for deep learners when appropriately chosen network sizes are employed. Specifically, when the true relationship between the response and explanatory variables is described by a $β$-Hölder function and one has access to $n$ independent and identically distributed (i.i.d.) samples from $m$ participating clients, for participating clients, the error rate scales at most as $\Tilde{O}((mn)^{-2β/(2β+ \bar{d}_{2β}(λ))})$, whereas for non-participating clients, it scales as $\Tilde{O}(Δ\cdot m^{-2β/(2β+ \bar{d}_{2β}(λ))} + (mn)^{-2β/(2β+ \bar{d}_{2β}(λ))})$. Here $\bar{d}_{2β}(λ)$ denotes the corresponding $2β$-entropic dimension of $λ$, the marginal distribution of the explanatory variables. The dependence between the two stages of the sampling scheme is characterized by $Δ$. Consequently, our findings not only explicitly incorporate the ``heterogeneity" of the clients, but also highlight that the convergence rates of errors of deep federated learners are not contingent on the nominal high dimensionality of the data but rather on its intrinsic dimension.