Incentivizing Federated Learning Under Long-Term Energy Constraint via Online Randomized Auctions
Incentivizing Federated Learning Under Long-Term Energy Constraint via Online Randomized Auctions
复制标题
DOI：
10.1109/twc.2021.3137024
复制
发表时间：
2022-07
影响因子：
10.4
通讯作者：
Yulan Yuan;Lei Jiao;Konglin Zhu;Lin Zhang
中科院分区：
文献类型：
--
作者：
Yulan Yuan;Lei Jiao;Konglin Zhu;Lin Zhang
由于移动设备能源等有限资源的过度消耗，移动用户通常不愿意参与联邦学习来训练模型。我们提出了一种基于拍卖的在线激励机制FLORA，它允许用户动态且重复地提交出价，并根据每个用户的长期电池容量对此类出价进行补偿。我们制定了一个非线性混合整数程序来捕获联邦学习系统中的社会成本最小化。然后，我们设计了多种多项式时间在线算法，包括分数在线算法和随机舍入算法来选择中标并控制训练精度，以及支付分配算法来根据中标概率计算报酬。在保持所训练的全局模型的令人满意的质量的情况下，我们的方法在不依赖于未知的未来输入的情况下即时工作，并随着时间的推移实现了可证明的次线性遗憾和次线性拟合，同时获得期望中的真实性和个人理性的经济属性。广泛的跟踪驱动评估证实了 FLORA 相对于现有替代品的实际优越性。
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.