Federated learning (FL) has emerged as a prevalent distributed machine
learning scheme that enables collaborative model training without aggregating
raw data. Cloud service providers further embrace Federated Learning as a
Service (FLaaS), allowing data analysts to execute their FL training pipelines
over differentially-protected data. Due to the intrinsic properties of
differential privacy, the enforced privacy level on data blocks can be viewed
as a privacy budget that requires careful scheduling to cater to diverse
training pipelines. Existing privacy budget scheduling studies prioritize
either efficiency or fairness individually. In this paper, we propose
DPBalance, a novel privacy budget scheduling mechanism that jointly optimizes
both efficiency and fairness. We first develop a comprehensive utility function
incorporating data analyst-level dominant shares and FL-specific performance
metrics. A sequential allocation mechanism is then designed using the Lagrange
multiplier method and effective greedy heuristics. We theoretically prove that
DPBalance satisfies Pareto Efficiency, Sharing Incentive, Envy-Freeness, and
Weak Strategy Proofness. We also theoretically prove the existence of a
fairness-efficiency tradeoff in privacy budgeting. Extensive experiments
demonstrate that DPBalance outperforms state-of-the-art solutions, achieving an
average efficiency improvement of $1.44\times \sim 3.49 \times$, and an average
fairness improvement of $1.37\times \sim 24.32 \times$.

DPBalance 是一种新型的隐私预算调度机制，通过综合考虑数据分析者级别的优势份额和 FL 特定的性能指标，采用拉格朗日乘数法和有效的贪婪启发式方法设计了一种顺序分配机制，从而同时优化了效率和公平性。