Fall 2023

Yanlin Qu: A New Class of Bounds for Convergence of Markov Chains to Equilibrium

Abstract

We introduce a unified framework to derive computable convergence bounds for Markov chains. Under this framework, bounds with various rates, ranging from polynomial to exponential, are derived from a single “contractive drift” (CD) condition. These bounds are computable, as all elements are explicitly defined in terms of one-step transition expectations. Various techniques are devised to verify CD for examples from queueing theory and stochastic optimization. For these examples, we obtain sharp bounds that scale correctly with respect to model parameters such as the traffic intensity in queueing models and the step size in optimization algorithms.

Speaker's Bio 

Yanlin Qu is a final-year PhD candidate at Stanford University in the Operations Research group within Department of Management Science and Engineering. His research interest lies in applied probability with a focus on Markov chain theory and its application to stochastic models in operations research and management science as well as to stochastic algorithms in optimization and simulation. He is on the 2023-2024 academic job market. His work has been recognized as the winner of Applied Probability Society Best Student Paper Prize and Applied Probability Society Conference Best Poster Award.

Mansi Sood: Network Design and Performance Analysis for Reliable Inference in Distributed Systems

Abstract

In this talk, I will present a brief overview of my doctoral research on stochastic modeling, analysis, and optimization toward making networked systems that interface with society more trustworthy and performant. The key focus of this talk will be on the connectivity properties of a class of random graph models known as ‘random K-out graphs,’ which are receiving increasing attention as a model to construct sparse yet well-connected topologies in distributed systems including distributed learning, blockchains, and next-generation internet architectures. Yet, the structural properties of the random K-out graphs that are critically tied to the system performance in practical settings have not been well studied in the literature. Through the example of privacy mechanisms based on pairwise additive masking (e.g., secure aggregation for federated learning and private gossip averaging for fully decentralized learning), where random K-out graphs have been deployed, I will discuss how the strength of connectivity impacts system performance. In this talk, I will discuss our recent body of work that characterizes the connectivity of random K-out graphs under various practical settings, including non-asymptotic connectivity bounds and analysis of the strength of connectivity under client heterogeneity and random and targeted node failures.

Speaker's Bio 

Mansi Sood is a Ph.D. candidate in Electrical and Computer Engineering and Cylab Security and Privacy Institute at Carnegie Mellon University (CMU). Before this, she completed her Bachelors and Masters in Electrical Engineering at the Indian Institute of Technology (IIT) Bombay, India. Her research interests span stochastic modeling, performance analysis, learning, and optimization for making networked systems that interface with society more trustworthy and performant. Her work won a Best Paper Award at the IEEE International Conference on Communications (ICC), and she has been twice recognized as an EECS Rising Star (MIT'21 and Georgia Tech'23). For her contributions to diversity, equity, and inclusion, she has been recognized with an Unsung Hero Award at CMU and the Advanced Graduate Ambassadorship of the Institute for Advanced Study (IAS), Princeton. She is on the 2023-2024 Academic Job Market for faculty and post-doc positions.

Alexander Van Werde: Matrix Concentration Inequalities with Dependent Summands and Sharp Leading-order Terms

Abstract

Many applications, such as reinforcement learning and the analysis of time series, involve sums of high-dimensional random matrices that are generated by a stochastic process. A key difficulty is that the summands are then typically dependent. In this talk, I present new matrix concentration inequalities which allow for dependent summands and whose main term has a sharp constant. Such a sharp constant is beyond the reach of classical results. In fact, previous results suffer from an often-suboptimal logarithmic dependence on the dimensionality and hence do not provide the appropriate asymptotic order, let alone the appropriate constant. A significant challenge in the proof is that techniques based on classical cumulants, which have been used by Brailovskaya and van Handel (2022) in a setting with independent summands, fail to produce efficient estimates in our dependent setting. For this reason, we developed a new approach based on a lesser known quantity called Boolean cumulants.

This talk is based on joint work with Jaron Sanders, available at arXiv:2307.11632. 

Speaker's Bio 

Alexander Van Werde received a MSc in mathematics at KU Leuven, Belgium in 2021 and is currently pursuing a PhD degree from Eindhoven University of Technology, The Netherlands. His research interest are in theoretical and applied probability theory; particularly concerning random matrices, stochastic processes, random graphs, and applications thereof.

Xingyu Wang: How to Characterize Global Dynamics with Rare-Event Analysis: A Heavy-Tail Framework in Deep Learning

Abstract

The empirical success of deep learning is often attributed to the mysterious ability of stochastic gradient descents (SGDs) to avoid sharp local minima in the loss landscape, as sharp minima are believed to lead to poor generalization. In this talk, we show that a sharp characterization of the local stability and global dynamics in deep learning can be obtained through the heavy-tailed large deviations framework. This framework systematically characterizes the rare events in heavy-tailed dynamical systems; building on this, we characterize intricate phase transitions in the first exit times, which leads to the heavy-tailed counterparts of the classical Freidlin-Wentzell and Eyring-Kramers theories. Moreover, applying this framework to SGD, we reveal a fascinating phenomenon in deep learning: by injecting and then truncating heavy-tailed noises during the training phase, SGD can almost completely avoid sharp minima and hence achieve better generalization performance for the test data. We will also briefly discuss the applications of this framework in simulation and queuing theory.

Speaker's Bio 

Xingyu Wang is a Ph.D. candidate in the Department of Industrial Engineering and Management Sciences at Northwestern University. His research interests lie in applied probability, machine learning theory, stochastic simulation, and heavy-tails. He won second place in the 2023 George Nicholson Student Paper Competition and was also awarded the 2022 Nemhauser Prize for Best Student Paper at Northwestern University.

Abstract

Standard bandit algorithms that assume continual reallocation of measurement effort are challenging to implement due to delayed feedback and infrastructural/organizational difficulties. Motivated by practical instances involving a handful of reallocation epochs in which outcomes are measured in batches, we develop a computation-driven adaptive experimentation framework that can flexibly handle batching. Our main observation is that normal approximations, which are universal in statistical inference, can also guide the design of adaptive algorithms. Instead of the typical theory-driven paradigm, we leverage computational tools and empirical benchmarking for algorithm development. Our approach significantly improves statistical power over standard methods, even when compared to Bayesian bandit algorithms (e.g., Thompson sampling) that require full distributional knowledge of individual rewards. Overall, we expand the scope of adaptive experimentation to settings that are difficult for standard methods, involving limited adaptivity, low signal-to-noise ratio, and unknown reward distributions.

Speaker's Bio

Hongseok Namkoong is an Assistant Professor in the Decision, Risk, and Operations division at Columbia Business School and a member of the Columbia Data Science Institute. His research interests lie at the interface of machine learning, operations research, and causal inference, with a particular emphasis on developing reliable learning methods for decision-making problems. Hong's research has been recognized by several awards, including paper awards at Neural Information Processing Systems, International Conference on Machine Learning, INFORMS Applied Probability Society, and Conference on Computer Vision and Pattern Recognition. He received his Ph.D. from Stanford University and worked as a research scientist at Facebook Core Data Science before joining Columbia. Outside of academia, he serves as a LinkedIn Scholar at LinkedIn's Responsible AI team.

Abstract

Patient survival from out-of-hospital cardiac arrest (OHCA) can be improved by augmenting traditional ambulance response with the dispatch of community first responders (volunteers) who are alerted via an app. How many volunteers are needed, from where should volunteers be recruited, and how should they be dispatched? We use a combination of Poisson point process modeling and convex optimization to address the first two questions; the right areas from which to recruit are not always obvious, because volunteers recruited from one area may spend time in various areas across a city. To answer the third question we use a combination of dynamic programming and decision trees, balancing the goal of a fast response to the current patient with the need to avoid disengagement of volunteers that arises when multiple volunteers respond. A case study for Auckland, New Zealand demonstrates the ideas.

This is joint work with Pieter van den Berg, Océane Fourmentraux, Caroline Jagtenberg, and Hemeng (Maggie) Li

Speaker's Bio

Professor Shane G. Henderson holds the Charles W. Lake, Jr. Chair in Productivity in the School of Operations Research and Information Engineering (ORIE) at Cornell University. His research interests include simulation optimization, emergency services planning and transportation. He is an INFORMS Fellow and a co-recipient of the INFORMS Wagner Prize for his work on bike-sharing programs. He has served as Director of the School of ORIE, as chair of the INFORMS Applied Probability Society, as editor in chief of the open-access journal Stochastic Systems and as simulation area editor for Operations Research. He likes cats, climbing walls, biking, Harry Potter and being a Dad.

Abstract

Large-scale stochastic systems are ubiquitous in practical applications, including foundational models, cloud computing centers, ride-sharing systems, and more. However, the design, control, and analysis of these systems are often challenging due to the curse of dimensionality. In this talk, I will present an analytical framework that combines mean-field approximation, Stein’s method, and state-space concentration, providing a powerful tool for understanding large-scale stochastic systems. This method has been successfully applied to address open questions in various fields such as reinforcement learning, cloud computing, and the Internet of Things. In this talk, I will use the example of load balancing in cloud computing to demonstrate how this approach has enabled us to gain important design insights that would be difficult, if not impossible, to obtain using the traditional mean-field analysis.

Speaker's Bio

Lei Ying is a Professor at the Electrical Engineering and Computer Science Department of the University of Michigan, Ann Arbor. His research is broadly in the interplay of complex stochastic systems and big data, including reinforcement learning, large-scale communication/computing systems for big-data processing, private data marketplaces, and large-scale graph mining. He won the Young Investigator Award from the Defense Threat Reduction Agency (DTRA) in 2009 and NSF CAREER Award in 2010. His research contributions have been recognized as best papers in conferences across different disciplines, including communication networks (INFOCOM and WiOpt), computer systems (SIGMETRICS) and data mining (KDD).

Abstract

Distributed computing enables parallel execution (service) of tasks that constitute a large computing job. In large-scale systems, even small random fluctuations in the service times (inherent to computing environments) often cause a non-negligible number of tasks with long completion times. Redundancy through task replication or erasure coding provides diversity that allows job completion when only a subset of redundant tasks gets executed. Thus, redundancy, as parallelism, reduces the job execution time. However, increasing the number of redundant parallel tasks requires increasing their size in systems with limited resources (e.g., a fixed number of distributed servers). This talk presents the diversity vs. parallelism trade-off for some standard models of task size-dependent execution times. We show that different models operate optimally at varying levels of redundancy and thus require erasure codes of different rates.

Based on joint work with P. Peng and P. Whiting arxiv.org/abs/2010.02147 

Speaker's Bio

Emina Soljanin is a Distinguished Professor of Electrical and Computer Engineering at Rutgers. Before moving to Rutgers in January 2016, she was a (Distinguished) Member of Technical Staff for 21 years in various incarnations of the Mathematical Sciences Research Center of Bell Labs. Her interests and expertise are broad and currently range from distributed computing to quantum information science. She is an IEEE Fellow, an outstanding alumnus of the Texas A&M School of Engineering, the 2011 Padovani Lecturer, a 2016/17 Distinguished Lecturer, and the 2019 IEEE Information Theory Society President. Emina's favorite recognition is the 2023 Aaron D. Wyner Distinguished Service Award.

Abstract

Many queueing systems experience intermittent overload, due to time-varying arrival rates. While there have been several attempts at analyzing such systems, there does not yet exist a simple formula to understand their response time behavior.

We introduce the "relative arrivals" method, a novel drift-based method to tightly bound the mean response time of systems with time-varying arrivals. Our bounds are simple, explicit, and closed-form. To illustrate the relative arrivals method, we apply it to a system with a two-level arrival process and intermittent overload.

Joint work with Yige Hong and Mor Harchol-Balter (CMU).

Speaker's Bio

Isaac Grosof is the Tennenbaum Postdoctoral Fellow at Georgia Institute of Technology. Their research interests lie within queueing theory, with a focus on scheduling, multiserver systems, optimal policies, and heavy-traffic analysis. Before joining Georgia Tech, they received their Ph.D. in Computer Science from CMU in 2023. After Georgia Tech, they will be a postdoc at UIUC, starting in spring 2024, and then an Assistant Professor at Northwestern University, starting in fall 2024. Their work has been recognized by the INFORMS 2022 George Nicholson Award, the ACM SIGMETRICS 2021 Best Paper Award, the ACM SIGMETRICS 2019 Best Student Paper Award, and the IFIP Performance 2018 Best Student Paper Award.