Incentivizing Federated Learning Under Long-Term Energy Constraint via Online Randomized Auctions

Mobile users are often reluctant to participate in federated learning to train models, due to the excessive consumption of the limited resources such as the mobile devices' energy. We propose an auction-based online incentive mechanism, FLORA, which allows users to submit bids dynamically and repetitively and compensates such bids subject to each user's long-term battery capacity. We formulate a nonlinear mixed-integer program to capture the social cost minimization in the federated learning system. Then we design multiple polynomial-time online algorithms, including a fractional online algorithm and a randomized rounding algorithm to select winning bids and control training accuracy, as well as a payment allocation algorithm to calculate the remuneration based on the bid-winning probabilities. Maintaining the satisfiable quality of the global model that is trained, our approach works on the fly without relying on the unknown future inputs, and achieves provably a sublinear regret and a sublinear fit over time while attaining the economic properties of truthfulness and individual rationality in expectation. Extensive trace-driven evaluations have confirmed the practical superiority of FLORA over existing alternatives.