This dissertation focuses on developing algorithms and systems to improve the efficiency of operating mega datacenters with hundreds of thousands of servers. In particular, it seeks to address two challenges: First, how to distribute the workload among the set of datacenters geographically deployed across the wide area? Second, how to manage the server resources of datacenters using virtualization technology? In the first part, we consider the workload management problem in geo-distributed datacenters. We first present a novel distributed workload management algorithm that jointly considers request mapping, which determines how to direct user requests to an appropriate datacenter for processing, and response routing, which decides how to select a path among the set of ISP links of a datacenter to route the response packets back to a user. In the next chapter, we study some key aspects of cost and workload in geo-distributed datacenters that have not been fully understood before. Through extensive empirical studies of climate data and cooling systems, we make a case for temperature aware workload management, where the geographical diversity of temperature and its impact on cooling energy efficiency can be used to reduce the overall cooling energy. Moreover, we advocate for holistic workload management for both interactive and batch jobs, where the delay-tolerant elastic nature of batch jobs can be exploited to further reduce the energy cost. A consistent 15% to 20% cooling energy reduction, and a 5% to 20% overall cost reduction are observed from extensive trace-driven simulations. In the second part of the thesis, we consider the resource management problem in virtualized datacenters. We design Anchor, a scalable and flexible architecture that efficiently supports a variety of resource management policies. We implement a prototype of Anchor on a small-scale in-house datacenter with 20 servers. Experimental results and trace-driven simulations show that Anchor is effective in realizing various resource management policies, and its simple algorithms are practical to solve virtual machine allocation with thousands of VMs and servers in just ten seconds.

Nonparametric convex regression has been extensively studied over the last two decades. It has been shown any Lipschitz convex function can be approximated with arbitrarily accuracy with a max of linear functions. Using this framework, in this thesis we generalize convex regression to learning an arbitrary Bregman divergence and learning a difference of convex functions. We provide approximation guarantees and sample complexity bounds for both these extensions. Furthermore, we provide algorithms to solve the resulting optimization problems based on 2-block alternative direction method of multipliers (ADMM). For this algorithm, we provide convergence guarantees with iteration complexity of O(n√d/𝜖) for a dataset X 𝝐 ℝ^n,d and arbitrary positive 𝜖. Finally we provide experiments for both the Bregman divergence learning and difference of convex functions learning based on UCI datasets that demonstrate the state of the art on regression and classification datasets.

Energy management strategies for microgrids, containing energy storage, renewable energy sources (RES), and electric vehicles (EVs); which interact with the grid on an individual basis; are presented in Chapter 3. An optimization problem to reduce cost, formulated over a rolling time horizon, using predicted values of load demand, EV connection/disconnection times, and charge levels at time of connection, is described. The solution provides the on-site storage and EV charge/discharge powers. For the first time, both bidirectional and unidirectional charging are considered for EVs and a controller which accommodates uncertainties in EV energy levels and connection/disconnection times is presented. In Chapter 4, a stochastic chance constraints based optimization is described. It affords significant improvement in robustness, over the conventional controller, to uncertainties in system parameters. Simulation results demonstrate that the stochastic controller is at least twice as effective at meeting the desired EV charge level at specific times compared to the non-stochastic version, in the presence of uncertainties. In Chapter 5, a network of microgrids, containing RES and batteries, which trade energy among themselves and with the utility grid is considered. A novel distributed energy management system (EMS), based on a central EMS using a Multi-Objective (MO) Rolling Horizon (RH) scheme, is presented. It uses Alternating Direction Method of Multipliers (ADMM) and Quadratic Programming (QP). It is inherently more data-secure and resilient to communication issues than the central EMS. It is shown that using an EMS in the network provides significant economic benefits over MGs connected directly to the grid. Simulations demonstrate that the distributed scheme produced solutions which are very close to those of the central EMS. Simulation results also reveal that the faster, less memory intensive distributed scheme is scalable to larger networks -- more than 1000 microgrids as opposed to a few hundreds for the central EMS. / Thesis / Doctor of Philosophy (PhD)

With the tremendous growth in the mobile data traffic, the demand for highdata rate is increasing rapidly, and higher frequency resources shall be exploredto alleviate the congestion in the overcrowded spectrum, thus, the millimeterwave (mmWave) frequency resource ranging from 30 GHz to 300 GHz has beenrecognized as a nature fit for the fifth-generation (5G) and beyond network. Tocompensate the severe path-loss in the mmWave band as well to realize theefficient transmissions by applying the low-cost architecture, it is of intereststo investigate the beamforming schemes with large-scale antenna arrays andthe full-duplex (FD) relaying strategy, which are indispensable in the operationof directional signal transmission and the efficient spectrum utilization inthe mmWave transmission, respectively. However, the self-interference (SI)occurring between the separate antenna arrays is the main impediment inrealizing a FD wireless node while considering the simultaneous transmission andreception.This thesis project aims to design efficient hybrid beamforming algorithms toimprove spectral efficiency and eliminate SI. The orthogonal matching pursuit(OMP)-based hybrid analog-digital beamforming design, and the alternatingdirection method of multipliers (ADMM)-based schemes are explored to improvethe spectral efficiency and eliminate the SI in this work. Moreover, a fast ADMMenabledhybrid precoding approach with SI cancellation is proposed to achievethe efficient performance and superior convergence compared with the existingschemes, as it is verified by the presented numerical simulations. / Med den enorma tillväxten i den mobila datatrafiken ökar efterfrågan påhög datahastighet snabbt, och högre frekvensresurser ska undersökas för attminska trängseln i det överbefolkade spektrumet, vilket innebär att Volymvågens(mmwave) frekvensresurs, som sträcker sig från 30 GHz till 300 GHz, har erkäntssom en naturlig resurs för den femte generationen (5G) och utanför nätverket.För att kompensera den allvarliga förlusten av tågläge i mmwave-bandet ochför att förverkliga de effektiva sändningarna genom att tillämpa den billigaarkitekturen.Det är av intresse att undersöka strålformningsprogrammen medstorskaliga antennmatriser och strategin för återutläggning av hela duplex (FD),som är oumbärliga för att driva den direkta signal överföringen och det effektivaspektrumutnyttjandet i mmwave-transmissionen.separata antennmatriser är etthuvudhinder för att förverkliga en trådlös nod från FD samtidigt som manöverväger samtidig överföring och mottagning.Syftet med detta avhandlingsprojekt är att utforma effektiva kombineradestrålformningsinformationsalgoritmer för att förbättra spektraleffektiviteten ocheliminera SI. Den ortogonala matchande jakten (OMP)-baserad hybrid analogdigitalstrålformning, och metoden med alternerande riktning för multiplikatorer(ADMM)-baserade system utforskas för att förbättra spektraleffektiviteten ochelimineraSI i det här arbetet. Dessutom föreslås en snabb, adMM-aktiveradhybrid förkonditionering med SI-annullering för att uppnå effektiv prestandaoch överlägset konvergens jämfört med de befintliga systemen, eftersom denkontrolleras av de presenterade numeriska simuleringarna.

Distributed computing is an approach where computationally heavy problems are broken down into more manageable sub-tasks, which can then be distributed across a number of different computers or servers, allowing for increased efficiency through parallelization. This thesis explores an established distributed computing setting, in which the computationally heavy task involves a number of users requesting a linearly separable function to be computed across several servers. This setting results in a condition for feasible computation and communication that can be described by a matrix factorization problem. Moreover, the associated costs with computation and communication are directly related to the number of nonzero elements of the matrix factors, making sparse factors desirable for minimal costs. The Alternating Direction Method of Multipliers (ADMM) is explored as a possible method of solving the sparse matrix factorization problem. To obtain convergence results, extensive convex analysis is conducted on the ADMM iterates, resulting in a theorem that characterizes the limiting points of the iterates as KKT points for the sparse matrix factorization problem. Using the results of the analysis, an algorithm is devised from the ADMM iterates, which can be applied to the sparse matrix factorization problem. Furthermore, an additional implementation is considered for a noisy scenario, in which existing theoretical results are used to justify convergence. Finally, numerical implementations of the devised algorithms are used to perform sparse matrix factorization. / Distribuerad beräkning är en metod där beräkningstunga problem bryts ner i hanterbara deluppgifter, som sedan kan distribueras över ett antal olika beräkningsenheter eller servrar, vilket möjliggör ökad effektivitet genom parallelisering. Denna avhandling undersöker en etablerad distribuerad beräkningssmiljö, där den beräkningstunga uppgiften involverar ett antal användare som begär en linjärt separabel funktion som beräknas över flera servrar. Denna miljö resulterar i ett villkor för tillåten beräkning och kommunikation som kan beskrivas genom ett matrisfaktoriseringsproblem. Dessutom är det möjligt att relatera kostanderna associerade med beräkning och kommunikation till antalet nollskilda element i matrisfaktorerna, vilket gör glesa matrisfaktorer önskvärda. Alternating Direction Method of Multipliers (ADMM) undersöks som en möjlig metod för att lösa det glesa matrisfaktoriseringsproblemet. För att erhålla konvergensresultat genomförs omfattande konvex analys på ADMM-iterationerna, vilket resulterar i ett teorem som karakteriserar de begränsande punkterna för iterationerna som KKT-punkter för det glesa matrisfaktoriseringsproblemet. Med hjälp av resultaten från analysen utformas en algoritm från ADMM-iterationerna, vilken kan appliceras på det glesa matrisfaktoriseringsproblemet. Dessutom övervägs en ytterligare implementering för ett brusigt scenario, där befintliga teoretiska resultat används för att motivera konvergens. Slutligen används numeriska implementeringar av de framtagna algoritmerna för att utföra gles matrisfaktorisering.

Tato diplomová práce se zabývá tématikou konvexní optimalizace a to konkrétně modifikacemi algoritmu ADMM, společně s problematikou proximálních operátorů. Jedna z verzí ADMM je pak implementována v programovacím jazyce Julia s důrazem na obecnost a efektivnost této implementace, a dále aplikována na rozsáhlou úlohu z oblasti odpadového hospodářství.

Stochastic and data-distributed optimization algorithms have received lots of attention from the machine learning community due to the tremendous demand from the large-scale learning and the big-data related optimization. A lot of stochastic and deterministic learning algorithms are proposed recently under various application scenarios. Nevertheless, many of these algorithms are based on heuristics and their optimality in terms of the generalization error is not sufficiently justified. In this talk, I will explain the concept of an optimal learning algorithm, and show that given a time budget and proper hypothesis space, only those achieving the lower bounds of the estimation error and the optimization error are optimal. Guided by this concept, we investigated the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We proposed a novel algorithm named Accelerated Nonsmooth Stochastic Gradient Descent, which exploits the structure of common nonsmooth loss functions to achieve optimal convergence rates for a class of problems including SVMs. It is the first stochastic algorithm that can achieve the optimal O(1/t) rate for minimizing nonsmooth loss functions. The fast rates are confirmed by empirical comparisons with state-of-the-art algorithms including the averaged SGD. The Alternating Direction Method of Multipliers (ADMM) is another flexible method to explore function structures. In the second part we proposed stochastic ADMM that can be applied to a general class of convex and nonsmooth functions, beyond the smooth and separable least squares loss used in lasso. We also demonstrate the rates of convergence for our algorithm under various structural assumptions of the stochastic function: O(1/sqrt{t}) for convex functions and O(log t/t) for strongly convex functions. A novel application named Graph-Guided SVM is proposed to demonstrate the usefulness of our algorithm. We also extend the scalability of stochastic algorithms to nonlinear kernel machines, where the problem is formulated as a constrained dual quadratic optimization. The simplex constraint can be handled by the classic Frank-Wolfe method. The proposed stochastic Frank-Wolfe methods achieve comparable or even better accuracies than state-of-the-art batch and online kernel SVM solvers, and are significantly faster. The last part investigates the problem of data-distributed learning. We formulate it as a consensus-constrained optimization problem and solve it with ADMM. It turns out that the underlying communication topology is a key factor in achieving a balance between a fast learning rate and computation resource consumption. We analyze the linear convergence behavior of consensus ADMM so as to characterize the interplay between the communication topology and the penalty parameters used in ADMM. We observe that given optimal parameters, the complete bipartite and the master-slave graphs exhibit the fastest convergence, followed by bi-regular graphs.

Advancement of micro-electro-mechanics and wireless communication have proliferated the deployment of large-scale wireless sensor networks. Due to cost, size and power constraints, at most a few sensor nodes can be equipped with a global positioning system; such nodes (whose positions can be accurately determined) are referred to as anchors. However, one can deter-mine the distance between two nearby sensors using some form of local communication. The problem of computing the positions of the non-anchor nodes from the inter-sensor distances and anchor positions is referred as sensor network localization (SNL). In this dissertation, our aim is to develop an accurate, efficient, and scalable localization algorithm, which can operate both in the presence and absence of anchors. It has been demon-strated in the literature that divide-and-conquer approaches can be used to localize large net-works without compromising the localization accuracy. The core idea with such approaches is to partition the network into overlapping subnetworks, localize each subnetwork using the available distances (and anchor positions), and finally register the subnetworks in a single coordinate system. In this regard, the contributions of this dissertation are as follows: We study the global registration problem and formulate a necessary “rigidity” condition for uniquely recovering the global sensor locations. In particular, we present a method for efficiently testing rigidity, and a heuristic for augmenting the partitioned network to enforce rigidity. We present a mechanism for partitioning the network into smaller subnetworks using cliques. Each clique is efficiently localized using multidimensional scaling. Finally, we use a recently proposed semidefinite program (SDP) to register the localized subnetworks. We develop a scalable ADMM solver for the SDP in question. We present simulation results on random and structured networks to demonstrate the pro-posed methods perform better than state-of-the-art methods in terms of run-time, accuracy, and scalability.

In recent years, the demand for data center computing has increased significantly due to the growing popularity of cloud applications and Internet-based services. Today's large data centers host hundreds of thousands of servers and the peak power rating of a single data center may even exceed 100MW. The combined electricity consumption of global data centers accounts for about 3% of worldwide production, raising serious concerns about their carbon footprint. The utility providers and governments are consistently pressuring data center operators to reduce their carbon footprint and energy consumption. While these operators (e.g., Apple, Facebook, and Google) have taken steps to reduce their carbon footprints (e.g., by installing on-site/off-site renewable energy facility), they are aggressively looking for new approaches that do not require expensive hardware installation or modification. This dissertation focuses on developing algorithms and systems to improve the sustainability in data centers without incurring significant additional operational or setup costs. In the first part, we propose a provably-efficient resource management solution for a self-managed data center to cap and reduce the carbon emission while maintaining satisfactory service performance. Our solution reduces the carbon emission of a self-managed data center to net-zero level and achieves carbon neutrality. In the second part, we consider minimizing the carbon emission in a hybrid data center infrastructure that includes geographically distributed self-managed and colocation data centers. This segment identifies and addresses the challenges of resource management in a hybrid data center infrastructure and proposes an efficient distributed solution to optimize the workload and resource allocation jointly in both self-managed and colocation data centers. In the final part, we explore sustainable resource management from cloud service users' point of view. A cloud service user purchases computing resources (e.g., virtual machines) from the service provider and does not have direct control over the carbon emission of the service provider's data center. Our proposed solution encourages a user to take part in sustainable (both economical and environmental) computing by limiting its spending on cloud resource purchase while satisfying its application performance requirements.

<p>In this work, we study a class of Markovian information theoretic optimization problems motivated by the recent interests in incorporating mutual information as performance metrics which gives evident success in representation learning, feature extraction and clustering problems. In particular, we focus on the information bottleneck (IB) and privacy funnel (PF) methods and their recent multi-view, multi-source generalizations that gain attention because the performance significantly improved with multi-view, multi-source data. Nonetheless, the generalized problems challenge existing IB and PF solves in terms of the complexity and their abilities to tackle large-scale data. </p> <p>To address this, we study both the IB and PF under a unified framework and propose solving it through splitting methods, including renowned algorithms such as alternating directional method of multiplier (ADMM), Peaceman-Rachford splitting (PRS) and Douglas-Rachford splitting (DRS) as special cases. Our convergence analysis and the locally linear rate of convergence results give rise to new splitting method based IB and PF solvers that can be easily generalized to multi-view IB, multi-source PF. We implement the proposed methods with gradient descent and empirically evaluate the new solvers in both synthetic and real-world datasets. Our numerical results demonstrate improved performance over the state-of-the-art approach with significant reduction in complexity. Furthermore, we consider the practical scenario where there is distribution mismatch between training and testing data generating processes under a known bounded divergence constraint. In analyzing the generalization error, we develop new techniques inspired by the input-output mutual information approach and tighten the existing generalization error bounds.</p>