ACM SIGMETRICS 2017

Champaign-Urbana, USA
5-9 June, 2017

Home
Call for Papers
Call for Workshops
Registration
Student Travel Grant
Schedule
Organizers
Program Committee
Keynote and Sigmetrics Award Lectures
Sponsors and Supporters
Workshops
Tutorials
Venue, Hotel and Travel Information
 

 Keynote


Speaker: Michael Jordan
Professor, University of California Berkeley

Title: On Gradient-Based Optimization: Accelerated, Distributed, Asynchronous and Stochastic

SLIDES.pdf

Abstract: Many new theoretical challenges have arisen in the area of gradient-based optimization for large-scale statistical data analysis, driven by the needs of applications and the opportunities provided by new hardware and software platforms. I discuss several recent results in this area, including: (1) a new framework for understanding Nesterov acceleration, obtained by taking a continuous-time, Lagrangian/Hamiltonian perspective, (2) a general theory of asynchronous optimization in multi-processor systems, (3) a computationally-efficient approach to stochastic variance reduction, (4) a primal-dual methodology for gradient-based optimization that targets communication bottlenecks in distributed systems, and (5) a discussion of how to avoid saddle-points in nonconvex optimization.

Bio: Michael I. Jordan is the Pehong Chen Distinguished Professor in the Department of Electrical Engineering and Computer Science and the Department of Statistics at the University of California, Berkeley. He received his Masters in Mathematics from Arizona State University, and earned his PhD in Cognitive Science in 1985 from the University of California, San Diego. He was a professor at MIT from 1988 to 1998. His research interests bridge the computational, statistical, cognitive and biological sciences, and have focused in recent years on Bayesian nonparametric analysis, probabilistic graphical models, spectral methods, kernel machines and applications to problems in distributed computing systems, natural language processing, signal processing and statistical genetics. Prof. Jordan is a member of the National Academy of Sciences, a member of the National Academy of Engineering and a member of the American Academy of Arts and Sciences. He is a Fellow of the American Association for the Advancement of Science. He has been named a Neyman Lecturer and a Medallion Lecturer by the Institute of Mathematical Statistics. He received the IJCAI Research Excellence Award in 2016, the David E. Rumelhart Prize in 2015 and the ACM/AAAI Allen Newell Award in 2009. He is a Fellow of the AAAI, ACM, ASA, CSS, IEEE, IMS, ISBA and SIAM.

 

 Keynote


Speaker: Vahab Mirrokni
Principal Scientist, Google Research, New York

Title: Online optimization for markets and the cloud: Theory and Practice

Abstract: Internet applications provide interesting dynamic environments for online optimization techniques. In this talk, I will discuss a number of such problems in the context of online markets, and in serving cloud services.

For online markets, I discuss problems in online advertising. Online ads are delivered in a real-time fashion under uncertainty in an environment with strategic agents. Making such real-time (or online) decisions without knowing the future is challenging for repeated auctions. In this context, I will first highlight the practical importance of considering "hybrid" models that can take advantage of forecasting, and at the same time, are robust against adversarial changes in the input. In particular, I discuss our recent results combining stochastic and adversarial input models. Then I will present more recent results concerning online bundling schemes that can be applied to repeated auction environments. In this part, I discuss ideas from our recent papers about online bundling, stateful pricing, bank account mechanisms, and Martingale auctions. 

For problems on the cloud, I will touch upon two online load balancing problems: one in the context of consistent hashing with bounded loads for dynamic environments, and one in the context of multi-dimensional load balancing. Other than presenting theoretical results on these topics, we show how some of our new algorithmic techniques have been applied by Google and other companies, and confirm their significance in practice.

In both parts, I will state a number of open problems in these areas.

Bio: Vahab Mirrokni is a principal scientist, heading the algorithms research groups at Google Research, New York. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 2001. He joined Google Research in 2008, after spending a couple of years at Microsoft Research, MIT and Amazon.com. He is the co-winner of paper awards at KDD'15, ACM EC'08, and SODA'05. His research areas include algorithms, distributed and stochastic optimization, and computational economics. At Google, he is mainly working on algorithmic and economic problems related to search and online advertising. Recently he is working on online ad allocation problems, distributed algorithms for large-scale graph mining, and mechanism design for advertising exchanges.

 

 2017 Sigmetrics Achievement Award Lecture


Speaker: Sem Borst
Eindhoven University of Technology and Nokia Bell Labs

Title: Delay Scalings and Mean-Field Limits in Networked Systems

Abstract: Load balancing mechanisms and scheduling algorithms play a critical role in achieving efficient server utilization and providing robust delay performance in a wide range of networked systems. We will review some celebrated schemes and optimality results which typically assume that detailed state information, e.g.\ exact knowledge of queue lengths, is available in assigning jobs to queues or allocating a shared resource among competing users. In practice, however, obtaining such state information is non-trivial, and usually involves a significant communication overhead or delay, which is particularly a concern in large-scale distributed systems with massive numbers of queues. These scalability issues have prompted increasing attention for the implementation complexity of load balancing and scheduling algorithms as a crucial criterion, besides the traditional performance metrics.

In this talk we examine the delay performance in such networks for various load balancing and scheduling algorithms, in conjunction with the associated implementation overhead. In the first part of the talk we focus on a scenario with a single dispatcher where jobs arrive that need to be assigned to one of several parallel queues. In the second part of the talk we turn to a system with a single resource, e.g.\ a shared wireless transmission medium, which is to be allocated among several nodes. We will specifically explore the delay scaling properties in a mean-field framework where the total load and service capacity grow large in proportion. The mean-field regime not only offers analytical tractability, but is also highly relevant given the immense numbers of servers in data centers and cloud networks, and dense populations of wireless devices and sensors in Internet-of-Things (IoT) applications. Time permitting, we will also discuss the impact of the underlying network structure and a few open research challenges.

Bio: Dr. Borst is Full Professor of Stochastic Operations Research (part-time) at the Eindhoven University of Technology, which position he has held since 1998. At Nokia Bell Labs, he is a Member of Technical Staff (part-time), which position he has held since 1996. He received the M.Sc. degree in Applied Mathematics from the University of Twente, and the Ph.D. degree from the University of Tilburg in the Netherlands in 1994. In the following year he was a visiting scholar at the Statistical Laboratory of the University of Cambridge, England, and the Mathematics of Networks and Systems Research Department of Bell Laboratories in Murray Hill, NJ. His research interests are in stochastic and queuing systems, applied probability, performance analysis and resource allocation in large-scale communication networks. He developed theoretical methods for analyzing queuing systems in which the workload has heavy-tailed characteristics. He was among the first to address the role of scheduling in mitigating the effects of long-range dependent and self- similar traffic. His work has provided new insights on the possible instability of well-known scheduling algorithms in networks. In the domain of communication networks, his work has impacted wireless networks of several generations, call centers, packet data switches, medium-access control, and content delivery networks. He is co-inventor in 28 patents. In the educational field, he has mentored several researchers, who have gone on to become faculty members in universities in the USA and the Netherlands. His awards include the Best Paper award from the 1992 ACM SIGMETRICS-Performance conference, INFOCOM 2003, the 2001 Yossef Levy Prize of the Operations Research Society of Israel, and the 2005 Van Dantzig prize.

 

 2017 Sigmetrics Rising Star Award Lecture


Speaker: Sewoong Oh
Assistant Professor, University of Illinois

Title: Matrix Factorization at the Frontier of Non-convex Optimizations

Abstract: Principal Component Analysis (PCA) and Canonical Component Analysis (CCA) are two of the few examples of non-convex optimization problems that can be solved efficiently with sharp guarantees. This is achieved by the classical and well-established understanding of matrix factorizations. Recently, several new theoretical and algorithmic challenges have arisen in statistical learning over matrix factorizations, motivated by various real-world applications. Despite the inherent non-convex nature of these problem, efficient algorithms are being discovered with provable guarantees, extending the frontier of our understanding of non-convex optimization problems. I will present several recent results in this area in applications to matrix completion and sensing, crowdsourcing, ranking, and tensor factorization.

Bio: Sewoong Oh is an Assistant Professor in the Department of Industrial and Enterprise Systems Engineering at UIUC. He received his PhD from the department of Electrical Engineering at Stanford University. Following his PhD, he worked as a postdoctoral researcher at Laboratory for Information and Decision Systems (LIDS) at MIT. He was co-awarded the Kenneth C. Sevcik outstanding student paper award at the SIGMETRICS 2010 and the best paper award at the SIGMETRICS 2015. He is a recipient of the NSF CAREER award and Google Faculty Research Award in 2016. His research interest includes matrix/tensor factorizations, graphical models, network analysis, and correlation analysis, with applications in social computing, computational biology, and privacy.