Distributed Learning under Autonomous Client Participation

The common assumption in distributed learning (DL) is that the central parameter server dictates client participation to optimize its training efficiency, while clients do not actively affect participation decisions beyond sending their updates when requested. However, this does not reflect the clients' real-world behavior, where they act autonomously based on self-interest, privacy concerns, and local model performance. In this paper, we introduce a theoretical framework that models autonomous state-dependent client participation in DL as a Markov chain, and analyze learning convergence in case client availability is dynamic and correlated across rounds. We analyze both homogeneous and heterogeneous data environments, as well as various participation rules that model client behavior. We demonstrate, both theoretically and empirically, that once autonomy exceeds a critical threshold, the Markov chain fails to mix and the learning process stagnates. We further show that, in heterogeneous settings, autonomous dropout of clients from the learning process induces a bias. This bias creates a feedback loop that steers the global model to an equilibrium that favors the more dominant data distributions. Finally, we consider the setting in which the parameter server can incentivize the participation of a uniform set of clients using a limited budget. We develop a policy-optimization method for the allocation of this budget that is based on our error bounds, and show it ensures convergence even in highly autonomous distributed networks.