FedEx Weight-Sharing Exponentiated Gradient for Federated Hyperparameter Tuning

A federated hyperparameter optimization algorithm (Khodak, Tu, Li, Li, Balcan, Smith, & Talwalkar, 2021) that decomposes federated learning algorithms Alg_a into a server aggregation subroutine Agg_b and a local training subroutine Loc_c with client hyperparameters c in C, and casts client hyperparameter tuning as a neural-architecture-search weight-sharing stochastic relaxation min_{theta in Delta_k, w in R^d} sum_{i=1}^n |V_i| E_{c ~ D_theta} L_{V_i}(Loc_c(T_i, w)) (Eqs. 6-7) over k candidate configurations {c_1, ..., c_k} sampled from a local epsilon-perturbation ball. At each communication round t, each active client i in {1, ..., B} receives shared weights w_t and categorical distribution theta_t, samples c_{ti} ~ D_{theta_t}, computes w_{ti} <- Loc_{c_{ti}}(T_{ti}, w_t), and returns (w_{ti}, c_{ti}, L_{V_{ti}}(w_{ti})); the server updates w_{t+1} <- Agg_b(w_t, {w_{ti}}) and updates theta_t via exponentiated gradient theta_{t+1} propto theta_t odot exp(-eta_t tilde_nabla) using the unbiased importance-weighted stochastic gradient tilde_nabla_j = (sum_{i=1}^B |V_{ti}| (L_{V_{ti}}(w_{ti}) - lambda_t) 1_{c_{ti}=c_j}) / (theta_t[j] sum_{i=1}^B |V_{ti}|) (Algorithm 2, Appendix C.1).