Adaptive resource allocation for cloud computing and federated learning

Abstract

The efficiency of large computing systems, such as cloud computing platform and distributed learning system, heavily relies on the quality of resource allocation strategies. The advent of neural networks and deep learning brings in performance improvement for all kinds of problems, which motivates us to tackle resource allocation problems in computing systems from the perspective of deep learning. We first study the online resource allocation and pricing problem from the deep learning angle to seek the possibility of designing online resource allocation algorithms and understanding worst cases from scratch. We consider single-type non-recycled resource allocation and pricing problem and utilise adversarial learning to approach worst-case based competitive ratio/gap. Specifically, we leverage two neural networks (NNs) as online algorithm and adversary respectively, and let them play a zero-sum game. We propose a single-round gradient descent method to break the complex dependency of sequence to ensure better convergence. We show the ability to converge to NE and a better competitive ratio of our method both theoretically and empirically. Next, We study VM allocation and pricing problem for cloud computing platform. Traditional methods are based on careful problem formulation, which is suboptimal in understanding the highly complex dynamics of cloud computing platforms. Instead, we resort to a deep reinforcement learning method to better capture the dynamics in order to build the connection between optimal policy and the states of system. We carefully design states, actions, and rewards in Deep Reinforcement Learning (DRL) to combine time series prediction and Markovian RL. Evaluation based on real-world traces shows that our method outperforms existing white-box methods in both profits and accepted user numbers. We further study the communication and privacy resource allocation problem in federated learning (FL) system. The bandwidth in FL is a scarce resource while the neighbour feature transmission in geo-distributed graph training would consume a large number of communication resources and dominate the whole training process. We propose conducting neighbour sampling periodically by trading off the relationship between convergence error, runtime, and neighbour sampling frequency. We derive the optimal sampling interval based on this relationship when there is no communication constraint and propose an online algorithm for constrained case. The experiment shows that the sampling interval found by our method achieves the best trade-off between convergence error and actual runtime. We next consider the privacy budget allocation problem for FL framework. Differential privacy (DP) was introduced to FL to protect sensitive data. However, the uniform gradient clipping and the noise addition of DP mechanism would cause significant skewness in performance degradation/unfairness among clients. We propose to set adaptive clipping values for different clients by analysing the effect of DP to gradients of individual client and deriving the relationship between loss variance and clipping values. The adaptively updated clipping values determine the variance of noise and privacy budget allocated for each model aggregation. Empirical results validate the effectiveness of our method for improving the fairness of FL.