In cloud services, autoscaling is one of the most important features, which enables system intelligence to adaptively assign computing resources for users according to real-time workloads and quality of service requirements. In our paper, we treat the process of autoscaling as a sequential decision problem of online optimization with switching cost constraints and propose two algorithms to solve it using noisy predictions for future workloads. Particularly, these two algorithms, which are called C-AFHC and SC-AFHC respectively, are designed for different situations according to a parameter of the constraints. Both of them have theoretical guarantees in terms of our well-defined performance metrics. Using real workload data collected from an enterprise Cloud Service, we demonstrate the performance of our algorithms in different scenarios of autoscaling problems.

In many applications such as statistical machine learning, reinforcement learning, and optimization for large data centers, the increasing data size and model complexity have made it impractical to run optimizations over a single machine. Therefore, solving the distributed optimization problem has become an important task. In this work, we consider a distributed processing network $G = \left( {\mathcal{V},\mathcal{E}} \right)$ with n nodes, where each node i can only evaluate the values of a local function (i.e., has zeroth-order information) and can only communicate with its neighbors. The objective is to reach consensus on the global optimizer of ${\max _{x \in \mathcal{X}}}\frac{1}{n}\sum\nolimits_{i = 1}^n {{f_i}(x)} $. Previous methods either assume first-order gradient information which is not suitable for many model-free learning scenarios, or consider the zeroth-order information but assume convexity of the objective functions and can only guarantee convergence to a stationary point for nonconvex objectives. To address these limitations, we drop both the known gradient assumption and convexity assumption. Instead, we propose a distributed Bayesian framework for the problem with only zeroth-order information and general nonconvex objective functions in a Matérn Reproducing Kernel Hilbert Space (RKHS). Under this framework, we propose an algorithm and show that with high probability it reaches consensus on all nodes and has a sublinear regret with regard to the global optimal. The results are validated under numerical studies.

As a classical problem, online optimization with switching cost has been studied for a long time due to its wide applications in various areas. However, few works have investigated the bandit setting where both the forms of the main cost function $f(x)$ evaluated at state $x$ and the switching cost function $c(x, y)$ of transitioning from state $x$ to $y$ are unknown. In this paper, we consider the situation when $\left(f(x_t)+\varepsilon_t,\,{c}(x_t, x_{t-1})\right)$ can be observed with noise $\varepsilon_t$ after making a decision $x_t$ at time $t$, aiming to minimize the expected total cost within a time horizon. To solve this problem, we propose two algorithms from a Bayesian approach, named Greedy Search and Alternating Search, respectively. They have different theoretical guarantees of competitive ratios under mild regularity conditions, and the latter algorithm achieves a faster running speed. Using simulations of two classical black-box optimization problems, we demonstrate the superior performance of our algorithms compared with the classical method.

Despite many valuable advances in the domain of online convex optimization over the last decade, many machine learning and networking problems of interest do not fit into that framework due to their nonconvex objectives and the presence of constraints. This motivates us in this paper to go beyond convexity and study the problem of stochastic continuum-armed bandit with long-term constraints. For noiseless observations of constraint functions, we propose a generic method using a Bayesian approach based on a class of penalty functions, and prove that it can achieve a sublinear regret with respect to the global optimum and a sublinear constraint violation (CV), which can match the best results of previous methods. Additionally, we propose another method to deal with the case where constraint functions are observed with noise, which can achieve a sublinear regret and a sublinear CV with more assumptions. Finally, we use two experiments to compare our methods with two benchmark methods in online optimization and Bayesian optimization, which demonstrates the advantages of our algorithms.

Yiran Xing, Zai Shi, Zhao Meng, Gerhard Lakemeyer, Yunpu Ma, Roger Wattenhofer. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

As an emerging technique to employ machine learning processes within an edge computing infrastructure, federated learning (FL) has aroused great interests in both industry and academia. In this paper, we consider a potential challenge of FL in a wireless setup, whereby uplink communication from edge devices to the central server has limited capacity. This is particularly important for machine learning tasks (such as training deep neural networks) in FL with extremely high-dimensional domains that can substantially increase the communication burden. To tackle this challenge, we first propose a basic method called Subspace Stochastic Gradient Descent for Federated Learning (FL-SSGD) to introduce the idea of subspace methods. Through theoretical analysis, we show that by choosing appropriate subspace matrices in FL-SSGD, we can reduce uplink communication costs compared to classical FedAvg method. To improve FL-SSGD, we then propose another method called Subspace Stochastic Variance Reduced Gradient for Federated Learning (FL-SSVRG) that has a faster convergence rate with less assumptions on objective functions. By conducting experiments of a nonconvex machine learning problem in two FL setups, we demonstrate the advantages of our methods compared to other communication-efficient methods.

In this paper, we address the problem of stochastic optimization over distributed processing networks, which is motivated by machine learning applications performed in data centers. In this problem, each of a total n nodes in a network receives stochastic realizations of a private function fi(x) and aims to reach a common value that minimizes Σi=1nfi(x) via local updates and communication with its neighbors. We focus on zeroth-order methods where only function values of stochastic realizations can be used. Such kind of methods, which are also called derivative-free, are especially important in solving realworld problems where either the (sub)gradients of loss functions are inaccessible or inefficient to be evaluated. To this end, we propose a method called Distributed Stochastic Alternating Direction Method of Multipliers (DS-ADMM) which can choose to use two kinds of gradient estimators for different assumptions. The convergence rates of DS-ADMM are O(n√k log (2k)/T) for general convex loss functions and O(n k log (2kT)/T) for strongly convex functions in terms of optimality gap, where k is the dimension of domain and T is the time horizon of the algorithm. The rates can be improved to O(n/√T )and O(n log T/T) if objective functions have Lipschitz gradients. All these results are better than previous distributed zerothorder methods. Lastly, we demonstrate the performance of DSADMM via experiments of two examples called distributed online least square and distributed support vector machine arising in estimation and classification tasks.

Distributed optimization has important applications in the practical implementation of machine learning and signal processing setup by providing means to allow interconnected network of processors to work towards the optimization of a global objective with intermittent communication. Existing works on distributed optimization predominantly assume all the processors storing related data to perform updates for the optimization task in each iteration. However, such optimization processes are typically executed at shared computing/data centers along with other concurrent tasks. Therefore, it is necessary to develop efficient distributed optimization methods that possess the flexibility to share the computing resources with other ongoing tasks. In this work, we propose a new first-order framework that allows for this flexibility through a probabilistic computing resource allocation strategy while guaranteeing the satisfactory performance of distributed optimization. Our results, both analytical and numerical, show that by controlling a flexibility parameter, our suite of algorithms (designed for various scenarios) can achieve the lower computation and communication costs of distributed optimization than their inflexible counterparts. This framework also enables the fair sharing of the common resources with other concurrent tasks being processed by the processing network.

There is a rich theory and plethora of algorithms in the literature aiming at the efficient scheduling of stochastic networks. These solutions are predominantly designed under the assumption of traffic demands that are independently generated at network nodes, without any requirement for synchronization among their received services. In this work, we note that many applications, including cloud computing, virtual reality, gaming, autonomous vehicular networks and collaborative design, generate traffic simultaneously at multiple nodes when they arrive, with possibly non-uniform file sizes, whose performance relies on the synchronous completion of the traffic across the network. This calls for the design of new scheduling algorithms that aims to coordinate the service of packets of the same traffic across the network. Towards this end, we propose a novel scheduling algorithm that not only accounts for the heterogeneity of the file size distributions, but also works towards synchronizing the completion time of the same traffic stream across the network. This is achieved by employing two insights that emanate from key motivating examples we develop: (1) the normalization of traffic load with respect to the non-uniform file sizes; and (2) the incorporation of deviation of normalized loads across network nodes that serve synchronized traffic. After establishing the throughput-optimality of our algorithm in general stochastic networks, we perform extensive simulations under various (spanning both wired and wireless) settings to reveal the potential completion time gains that it yields over other throughput-optimal strategies designed under the assumption of independent traffic generation.

In this paper we consider a two-tier heterogeneous network (HetNet) where pico base stations (BSs) can harvest energy from macro BSs. Three cases of special interests are investigated, i.e., pico BSs are deployed 1) without battery and power grid, 2) with power grid, and 3) with battery. In particular, a practical dual-slope path loss model is employed to facilitate the performance analysis. By means of stochastic geometry and Gamma second order moment matching, a compact expression of the distribution of harvested energy is derived. Then the network's energy efficiency (EE) is introduced and optimized with carefully designed system parameters. Finally, an important conclusion is obtained as follows: only when the intensity of pico BSs is high can HetNets with energy harvesting improve the network's EE compared with the conventional HetNets without energy harvesting.