Professor, University of California Berkeley
Title: On Gradient-Based Optimization: Accelerated, Distributed, Asynchronous and Stochastic
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.
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.
Principal Scientist, Google Research, New York
Title: Online optimization for markets and the cloud: Theory and Practice
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.
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.
Eindhoven University of Technology and Nokia Bell Labs
Title: Delay Scalings and Mean-Field Limits in Networked Systems
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.
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.
Assistant Professor, University of Illinois
Title: Matrix Factorization at the Frontier of Non-convex Optimizations
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.
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.