Georgia Institute of Technology College of Sciences

Consider a linear combination of independent identically distributed random variables $X_1, . . . , X_n$ with fixed weights $a_1, . . . a_n$. If the random variablesare continuous, the sum is almost surely non-zero. However, for discrete random variables an exact cancelation may occur with a positive probability. Thisprobability depends on the arithmetic nature of the sequence $a_1, . . . a_n$. We will discuss how to measure the relevant arithmetic properties and how to evaluate the probability of the exact and approximate cancelation.

Abstract In this talk, I will present a popular distributed method, namely, distributed consensus-based gradient (DCG) method, for solving optimal learning problems over a network of agents. Such problems arise in many applications such as, finding optimal parameters over a large dataset distributed among a network of processors or seeking an optimal policy for coverage control problems in robotic networks. The focus is to present our recent results, where we study the performance of DCG when the agents are only allowed to exchange their quantized values due to their finite communication bandwidth. In particular, we develop a novel quantization method, which we refer to as adaptive quantization. The main idea of our approach is to quantize the nodes' estimates based on the progress of the algorithm, which helps to eliminate the quantized errors. Under the adaptive quantization, we then derive the bounds on the convergence rates of the proposed method as a function of the bandwidths and the underlying network topology, for both convex and strongly convex objective functions. Our results suggest that under the adaptive quantization, the rate of convergence of DCG with and without quantization are the same, except for a factor which captures the number of quantization bits. To the best of the authors’ knowledge, the results in this paper are considered better than any existing results for DCG under quantization. This is based on a joint work with Siva Theja Maguluri and Justin Romberg. Bio Thinh T. Doan is a TRIAD postdoctoral fellow at Georgia Institute of Technology, joint between the School of Industrial and Systems Engineering and the School of Electrical and Computer Engineering (ECE). He was born in Vietnam, where he got his Bachelor degree in Automatic Control at Hanoi University of Science and Technology in 2008. He obtained his Master and Ph.D. degrees both in ECE from the University of Oklahoma in 2013 and the University of Illinois at Urbana-Champaign in 2018, respectively. His research interests lie at the intersection of control theory, optimization, distributed algorithms, and applied probability, with the main applications in machine learning, reinforcement learning, power networks, and multi-agent systems.

We investigate whether the standard dimensionality reduction techniques inadvertently produce data representations with different fidelity for two different populations. We show on several real-world datasets, PCA has higher reconstruction error on population A than B (for example, women versus men or lower versus higher-educated individuals). This can happen even when the dataset has similar number of samples from A and B . This motivates our study of dimensionality reduction techniques which maintain similar fidelity for A as B . We give an efficient algorithm for finding a projection which is nearly-optimal with respect to this measure, and evaluate it on several datasets. This is a joint work with Uthaipon Tantipongpipat, Jamie Morgenstern, Mohit Singh, and Santosh Vempala.

Abstract: Queueing systems are studied in various asymptotic regimes because they are hard to study in general. One popular regime of study is the heavy-traffic regime, when the system is loaded very close to its capacity. Heavy-traffic behavior of queueing systems is traditionally studied using fluid and diffusion limits. In this talk, I will present a recently developed method called the 'Drift Method', which is much simpler, and is based on studying the drift of certain test functions. In addition to exactly characterizing the heavy-traffic behavior, the drift method can be used to obtain lower and upper bounds for all loads. In this talk, I will present the drift method, and its successful application in the context of data center networks to resolve a decade-old conjecture. I will also talk about ongoing work and some open problems. Bio: Siva Theja Maguluri is an Assistant Professor in the School of Industrial and Systems Engineering at Georgia Tech. Before that, he was a Research Staff Member in the Mathematical Sciences Department at IBM T. J. Watson Research Center. He obtained his Ph.D. from the University of Illinois at Urbana-Champaign in Electrical and Computer Engineering where he worked on resource allocation algorithms for cloud computing and wireless networks. Earlier, he received an MS in ECE and an MS in Applied Math from UIUC and a B.Tech in Electrical Engineering from IIT Madras. His research interests include Stochastic Processes, Optimization, Cloud Computing, Data Centers, Resource Allocation and Scheduling Algorithms, Networks, and Game Theory. The current talk is based on a paper that received the best publication in applied probability award, presented by INFORMS Applied probability society.