Self-tuned Regularized Federated Methods with Guarantees for Optimal Solution Selection

We study a hierarchical federated learning (FL) problem, where clients cooperatively seek to select among multiple optimal solutions of a primary distributed learning problem, a solution that minimizes a secondary loss function. This problem arises from over-parameterized learning and ill-posed optimization problems. First, we consider the setting where the inner-level objective is convex and the outer-level objective is either convex or strongly convex. We propose a self-tuned regularized federated averaging (StR-FedAvg) method where the stepsize and regularization parameter are characterized by the number of communication rounds and problem parameters. We derive new complexity guarantees for addressing the optimal solution selection problem in FL. Second, when the outer-level objective is nonconvex, we propose a two-loop FL scheme in which the outer loop employs an inexact projected first-order method and the inner loop applies StR-FedAvg with an iteratively updated regularization parameter. We derive new communication complexity guarantees for computing a stationary point of the nonconvex solution-selection problem. To our knowledge, this is the first work to establish complexity guarantees for this class of problems in FL. Preliminary experiments validate our theoretical findings.