Cost-Effective Federated Learning Design

Bing Luo; Xiang Li; Shiqiang Wang; Jianwei Huang; Leandros Tassiulas

Source-linked AI summary

Cost-Effective Federated Learning Design

Bing Luo, Xiang Li, Shiqiang Wang, Jianwei Huang, Leandros Tassiulas

arXiv:2012.08336v1Dec 15, 2020cs.LGcs.DCcs.NImath.OC

TL;DR

Federated learning must reduce the time and energy costs of iterative on-device training while maintaining convergence. This paper jointly optimizes client participation and local iterations using a theoretically grounded, sampling-based controller, which achieves near-optimal performance across varied datasets, models, and heterogeneous systems.

Problem
FL cost depends strongly on the selected-client count and local-iteration count, while existing approaches often optimize only one control variable or a single cost component.
Method
The paper relates total cost and convergence through an analytical bound, learns unknown parameters with low-cost sampling, and solves the resulting biconvex optimization over K and E.
Results
Near-optimal performance is demonstrated across simulated and hardware settings, including different datasets, models, and heterogeneous systems.
Takeaways & Limitations
The derived properties identify how to choose K and E for priorities such as reducing learning time or saving energy.

Abstract

from arXiv · show

Federated learning (FL) is a distributed learning paradigm that enables a large number of devices to collaboratively learn a model without sharing their raw data. Despite its practical efficiency and effectiveness, the iterative on-device learning process incurs a considerable cost in terms of learning time and energy consumption, which depends crucially on the number of selected clients and the number of local iterations in each training round. In this paper, we analyze how to design adaptive FL that optimally chooses these essential control variables to minimize the total cost while ensuring convergence. Theoretically, we analytically establish the relationship between the total cost and the control variables with the convergence upper bound. To efficiently solve the cost minimization problem, we develop a low-cost sampling-based algorithm to learn the convergence related unknown parameters. We derive important solution properties that effectively identify the design principles for different metric preferences. Practically, we evaluate our theoretical results both in a simulated environment and on a hardware prototype. Experimental evidence verifies our derived properties and demonstrates that our proposed solution achieves near-optimal performance for various datasets, different machine learning models, and heterogeneous system settings.

I. INTRODUCTION

This paper studies adaptive federated learning that jointly chooses participating clients and local iterations to minimize time-and-energy cost while preserving convergence. It develops theory, an efficient optimization algorithm, and experimental validation across heterogeneous settings.

FL preserves decentralized data while coordinating collaborative model training across many clients, but communication limits and heterogeneous devices complicate algorithm design.
Time and energy are distinct FL costs whose relative importance depends on the application, motivating joint cost optimization.Solar sensor networks prioritize energy, whereas search-and-rescue applications prioritize timely learning.
The paper jointly adapts K participating clients and E local iterations per round, addressing limitations of approaches that adapt only communication intervals.The two variables are tightly coupled, and their convergence relationship contains unknown coefficients.
A sampling-based algorithm learns unknown convergence parameters with marginal overhead and solves the resulting biconvex cost-minimization problem using closed-form methods.
Large K favors learning-time reduction while small K favors energy saving; neither very small nor very large E is cost-effective.The best E depends on the relationship between computation and communication costs.
Experiments on simulated environments and a 20-device Raspberry Pi prototype verify the design properties and show near-optimal performance across datasets, models, and heterogeneous systems.The evaluation includes non-i.i.d. data and both convex and non-convex models.

A. Federated Learning

The paper formulates federated learning as decentralized optimization solved by FedAvg, where sampled clients perform local updates before server aggregation. Its cost model accounts for computation, communication, parallel stragglers, learning time, and energy.

A. Federated Learning: FL minimizes a weighted global loss across N devices while keeping training data decentralized.The global objective uses device weights p_k that sum to one.
A. Federated Learning: FedAvg samples a client subset each round, runs E local SGD iterations in parallel, and aggregates their updated model parameters at the server.
A. Federated Learning: After R rounds, each device performs ER local iterations, while the training process continues until the global loss converges.
B. Cost Analysis of Federated Learning: The total FL cost includes learning time and energy consumed during local computation and global communication in every round.
B. Cost Analysis of Federated Learning: Client sampling is uniform without replacement, with K clients selected per round; device computation and communication costs vary under system heterogeneity.Aggregation cost is omitted because averaging is much less complex than local model updates.
1) Time Cost:: For heterogeneous devices, per-round time combines E local-iteration time with communication time, and parallel execution makes the slowest participating client the straggler.

2) Energy Cost:

FL cost combines learning time and energy, whose optimal control choices can differ. The paper formulates minimizing expected total cost while satisfying an ε-convergence constraint, despite difficult exact cost and convergence relationships.

Energy cost sums the selected clients’ local-computation and communication energy in each round.
The balanced objective weights learning time and energy as Ctot(K, E, R) = (1 −γ) ttot(K, E, R) + γetot(K, E, R).γ can represent different preferences, from time-focused operation to energy-prioritized solar sensors.
The optimization minimizes expected total cost subject to expected loss being within ε of the unknown minimum after R rounds.The expectation reflects SGD and client-sampling randomness.
Exact optimization is difficult because time includes a nonlinear maximum over clients and convergence lacks an exact analytical relationship with E, K, and R.

1) Analytical Expression of E[etot]:

The paper derives expected energy and time costs under uniform client sampling, then connects expected total cost to convergence through an upper-bound approximation. The resulting problem remains difficult because heterogeneous client ordering varies with E and combinatorial terms depend on K.

Uniform sampling lets expected total energy be derived by summing per-device local-iteration and communication costs over the expected number of sampled rounds.
Expected time cost is derived using reordered client times and combinatorial terms that account for which sampled device is the slowest.The straggler-related derivation uses the recursive structure of combination counts.
The expected-cost formulation is connected to convergence by requiring a convergence upper bound to satisfy the target constraint.The bound includes constants A0 and B0 related to loss-function properties and statistical heterogeneity of non-i.i.d. data.
P2 is more constrained than P1, so every feasible P2 solution is also feasible for P1.
P2 remains hard because its combinatorial terms depend on K and on client-time ordering that changes with E.The convergence bound is valid for strongly convex problems, while experiments also test non-convex learning empirically.

4) Approximate Optimization Problem of P2:

The paper approximates P2 with a tractable objective for expected time and energy, relaxes the control variables for analysis, and later rounds them to integer choices. Empirically, the resulting P3 solution is near-optimal for P1.

An approximate expected time cost is defined to replace the combinatorial expression while preserving the dependence on K and E.The approximation equals the expected time in specified cases, including homogeneous systems.
The approximate objective combines approximate expected time and expected energy as ˜E[Ctot(K, E, R)] = (1 −γ) ˜E[ttot(E, R)] + γE[etot(K, E, R)].
Relaxing K, E, and R to continuous variables makes the convergence constraint tight at the optimum, allowing R to be obtained from equality.
P3 approximates P2 through the approximate objective ˜E[Ctot], and empirical results show its solution achieves near-optimal performance for P1.

B. Solving the Approximate Optimization Problem P3

The solution to P3 first characterizes its optimization properties, then estimates unknown convergence-bound parameters with sampling. Using those estimates, the paper efficiently computes K* and E*.

The paper characterizes P3 before estimating the unknown parameters A0 and B0 that determine the cost-effective control choices.
A sampling-based algorithm learns A0 and B0, after which K* and E* for P3 are efficiently computed.The overall procedure is specified in Algorithm 2.

1) Characterizing P3:

P3 is a strictly biconvex cost-minimization problem in K and E, with unknown convergence parameters estimated through low-overhead sampling before iterative optimization.

Optimization formulation: The P3 objective is strictly biconvex in K and E, enabling efficient alternating optimization.For fixed K, E has a unique real closed-form solution from the stationary equation, and alternating updates converge to K* and E*.
Parameter estimation: The optimization depends on unknown convergence-bound parameters A0 and B0 that must be learned during training.These parameters enter the equations determining K and E and cannot be fixed beforehand.
Parameter estimation: The sampling algorithm estimates A0 and B0 by testing diverse (K, E) pairs and recording rounds needed to reach two predefined losses.Multiple sampled pairs can be averaged, and the estimation procedure is implemented in Lines 1–4 of Algorithm 2.
Overhead: The estimation overhead is marginal when the target final loss approaches the optimum.The overhead is measured through additional local iterations used during parameter estimation.

V. SOLUTION PROPERTY FOR COST MINIMIZATION

The paper derives solution properties for different cost preferences, providing design principles and alternative ways to solve the cost-minimization problem more efficiently.

Solution properties: The analysis characterizes optimal control choices under different metric preferences.The properties are derived for the continuous versions of K, K*, E, and E* before rounding.
Solution properties: The derived properties provide practical design principles for selecting K and E.They also offer alternative solution methods for the optimization problem.
Validation: Empirical results show that the properties derived for P3 remain valid for the original P1 problem.

A. Properties for Minimizing ˜E[Ctot] when γ = 0

When γ = 0, the objective minimizes learning time: full participation is optimal theoretically, while an intermediate local-iteration count is best for any fixed K.

Client participation: K*=N because the objective is strictly decreasing in K for any fixed E.
Client participation: When N is very large, sampling a small device portion can achieve relatively good learning time because marginal gains decrease as K increases.The reported experiment found similar performance for K=20 out of N=100 and full participation.
Local iterations: For any fixed K, increasing E first decreases and then increases the learning-time objective.Thus, E should be neither too small nor too large for saving learning time.
Local iterations: When communication time increases or computation time decreases, the optimal learning-time strategy increases E before aggregation.

B. Properties for Minimizing ˜E[Ctot] when γ = 1

When γ = 1, the objective minimizes energy consumption: selecting fewer clients is optimal, while E still has an intermediate optimum. The broader trade-off favors larger K for time and smaller K for energy.

Client participation: K*=1 because the energy objective is strictly increasing in K for any fixed E.
Client participation: Sampling fewer devices can reduce total energy consumption but produces longer learning time.The energy total sums consumption across selected clients, so fewer participants can offset the extra rounds needed.
Local iterations: For any fixed K, increasing E first decreases and then increases the energy objective.The same intermediate-E principle therefore applies under energy minimization.
Trade-off: For a given γ, the optimal K balances learning-time reduction against energy consumption.Larger K favors learning-time reduction, whereas smaller K favors energy saving.
Trade-off: When computation and communication have equal power relationships, both K* and E* decrease as γ increases.The stated condition is that em/tp equals ep/tm as represented in the paper's assumption.

VI. EXPERIMENTAL EVALUATION

The evaluation combines simulated and hardware experiments across real and synthetic datasets, using three heterogeneous setups to assess the proposed cost-effective FL algorithm.

Evaluation setup: Experiments use a 20-device Raspberry Pi prototype and a 100-device simulated system.The prototype captures communication and computation heterogeneity, while the simulation models learning time and energy consumption.
Evaluation setup: The evaluation covers MNIST and Synthetic (1, 1) with logistic regression and CNN models under non-i.i.d. data distributions.Setup 1 uses logistic regression with MNIST on 20 devices; Setup 2 uses CNN with MNIST on 100 devices; Setup 3 uses logistic regression with synthetic data on 100 devices.
Evaluation setup: The three setups vary device count, model, dataset, and data balance to test the method under heterogeneous conditions.Setup 1 distributes 6,000 samples evenly across devices, Setup 2 uses unbalanced MNIST device data, and Setup 3 uses an unbalanced power-law distribution.
Evaluation setup: Each experiment initializes w0 = 0, uses SGD batch size b = 64, randomly samples K devices per round, and runs E local SGD steps.Results are evaluated using the aggregated model's global loss; the supplied protocol states that each result is averaged over 50 experiments.
Estimation and comparison: The estimation procedure samples several (K, E) pairs, records rounds to reach two losses, and uses Algorithm 2 to estimate A0 and B0 before selecting K* and E*.KOPT and EOPT are obtained by exhaustive search for comparison.

2) Convergence and Optimality:

The proposed solutions achieve near-optimal convergence and cost across the tested setups while exhibiting the predicted effects of client participation, local iterations, and the time–energy preference factor.

2) Convergence and Optimality: 2.61% and 8.49% optimality errors are reported for Setups 1 and 2, respectively, relative to empirical optima.Setup 1 uses logistic regression and MNIST; Setup 2 uses a non-convex CNN and MNIST.
2) Convergence and Optimality: 856.8s versus 789.0s reaches loss 0.06 in Setup 2 with 8.49% optimality error, while 98.2% test accuracy takes almost the optimal time.The proposed configuration is faster than non-optimal choices with excessively small or large E or small K.
2) Convergence and Optimality: 4.85% average and 10.23% maximum optimality errors are reported for Setup 3 across the full γ range.The solutions approach the optimal trade-off while balancing learning-time and energy preferences.
2) Convergence and Optimality: As γ increases from 0 to 1, both optimal and proposed K decrease from 100 to 1, while E decreases slightly.Here γ shifts preference from reducing learning time toward saving energy.
4) Property Validation: For fixed E, learning-time cost decreases with K, but energy cost increases with K; sampling 15 of 20 or 20 of 100 clients changes learning time little.These observations support the stated theoretical properties of K and the practical value of partial participation.
4) Property Validation: For fixed K, cost first decreases and then increases with E, confirming the stated corollaries and the biconvex property.In the simulation, both K* and E* decrease as γ increases because em/tm = ep/tp = 10^-2.
VII. CONCLUSION: The experiments validate the theoretical analysis and demonstrate effective, efficient control across heterogeneous datasets and models.The conclusion reports that the sampling-based algorithm solves the optimization problem with marginal overhead.