Power-of-Choice (Biased Loss-Based Client Selection Strategies for Federated Learning: pow-d, cpow-d, and rpow-d)

A biased client-selection framework and theoretical convergence analysis for partial-participation federated learning (Cho, Wang, & Joshi 2022, Sections 3-4, Definitions 3.1-3.2, Equations 4-8, Theorem 3.1, Theorem A.1, Appendix F Algorithms 1-2) that characterizes any client selection policy pi mapping the global model w to an active cohort S(pi, w) of size m = max(C K, 1) via the local-global objective gap Gamma = F^* - sum_{k=1}^K p_k F_k^* >= 0 (Definition 3.1, Equation 4) and the selection skew rho(S(pi, w), w') = E_{S(pi,w)}[(1/m) sum_{k in S(pi,w)} (F_k(w') - F_k^*)] / (F(w') - sum_{k=1}^K p_k F_k^*) with extremal bounds rho_bar = min_{w,w'} rho(S(pi, w), w') and rho_tilde = max_w rho(S(pi, w), w^*) (Definition 3.2, Equations 5-6). Under L-smooth, mu-strongly convex objectives, Theorem 3.1 proves that biasing selection toward higher-loss clients (rho_bar > 1) accelerates the O(1 / (T rho_bar)) vanishing error term by a factor of rho_bar while introducing a bounded solution bias Q(rho_bar, rho_tilde) = (8 L Gamma / (3 mu)) (rho_tilde / rho_bar - 1) (Equation 7). To span this speed-bias trade-off efficiently, Power-of-Choice (pi_{pow-d}) first samples a candidate set A of d clients (m <= d <= K) without replacement in proportion to dataset sizes p_k, evaluates or estimates their local losses F_k(w_bar^{(t)}), and selects the m clients in A with the largest local losses, with resource-saving variants pi_{cpow-d} (mini-batch loss estimation, Algorithm 1) and pi_{rpow-d} (cached cumulative local training loss piggybacked on model uploads without extra communication, Algorithm 2).