Line Search in Federated Learning: Local Descent, Global Extrapolation

Line search is a classical tool for reducing sensitivity to learning-rate (LR) choices, and prior work shows that a stochastic Armijo line search can beat well-tuned methods across learning tasks in a centralized setting. In federated learning (FL), however, client-local line search remains largely unexplored as an optimization tool under client heterogeneity and partial participation. We introduce stochastic Line search with SGD as the client-local solver, in which participating clients use stochastic Armijo tests to select their local step sizes. Motivated by interpreting server-side extrapolation as an inexact server-level line search, we propose Federated Extrapolated Stochastic Line Search (FedExpSLS). Under client-wise interpolation and an expected sufficient-accuracy condition for the coupled stochastic function estimates used by the line search, we provide convergence rates for FedExpSLS. Empirically, FedExpSLS is competitive with strong baselines across convex and non-convex FL tasks, while substantially reducing the need to tune client learning rates.