Fall 2022

Abstract

Contrastive representation learning seeks to acquire useful representations of data by estimating the mutual information between multiple views of data. Here, the choice of data augmentation is sensitive to the quality of learned representations: as harder the data augmentations are applied, the views share more task-relevant information, but also task-irrelevant one that can hinder the generalization capability of representation. Motivated by this, in this talk I will present a new robust contrastive learning scheme, coined RényiCL, which can effectively manage harder augmentations by utilizing Rényi divergence (a generalized version of Kullback–Leibler divergence). Our method is built upon the variational lower bound of Rényi divergence, but a naïve usage of a variational method is impractical due to the large variance. To tackle this challenge, we propose a novel contrastive objective that conducts variational estimation of a skew Rényi divergence and provide a theoretical guarantee on how variational estimation of skew divergence leads to stable training. We show that Rényi contrastive learning objectives perform innate hard negative sampling and easy positive sampling simultaneously so that it can selectively learn useful features and ignore nuisance features. Through experiments on ImageNet, we show that Rényi contrastive learning with stronger augmentations outperforms other self-supervised methods without extra regularization or computational overhead. Moreover, we also validate our method on other domains such as graph and tabular, showing empirical gain over other contrastive methods.

This is a joint work with Kyungmin Lee (KAIST).

Speaker's Bio

Jinwoo Shin is currently an associate professor (jointly affiliated) at Kim Jaechul Graduate School of AI and the School of Electrical Engineering at KAIST. He is also a KAIST endowed chair professor. He obtained B.S. degrees (in Math and CS) from Seoul National University in 2001, and a Ph.D. degree (in Math) from Massachusetts Institute of Technology in 2010 with the George M. Sprowls Award (for best MIT CS Ph.D. theses). He was a postdoctoral researcher at Algorithms & Randomness Center, Georgia Institute of Technology in 2010-2012 and Business Analytics and Mathematical Sciences Department, IBM T. J. Watson Research in 2012-2013. Dr. Shin's early works are mostly on applied probability and theoretical computer science. After he joined KAIST in Fall 2013, he started to work on the algorithmic foundations of machine learning. He received the Rising Star Award in 2015 from the Association for Computing Machinery (ACM) Special Interest Group for the computer systems performance evaluation community (SIGMETRICS). He also received Kenneth C. Sevcik Award at ACM SIGMETRICS/Performance 2009, Best Publication Award from INFORMS Applied Probability Society 2013, Best Paper Award at ACM MOBIHOC 2013, Bloomberg Scientific Research Award 2015, and ACM SIGMETRICS Test of Time Award 2019.

Abstract

This work was motivated by problems of managing stochastic networks featuring temporary overloads, small to moderate time-varying number of servers, non-homogeneous service-time distributions and complex routing of entities. Such problems require prediction of future system behavior over time so that an appropriate design and operational adjustments can be made.

In the talk, we present a methodology to predict transient distributions of key performance metrics over time, e.g., distributions of the number of customers or the virtual wait times in a queueing network. Our methodology is fundamentally non-parametric and non-Markovian. It includes an abstract modeling framework defined by relatively few primitives. In simple models, they might be scalars or probability mass functions. In more elaborate models, they can be specified as code fragments. Once the primitives have been specified the resulting model defines the dynamics from which the desired performance metrics can be computed exactly, but this is not practical due to the sheer size of the number of calculations required. Our computational approach introduces in a vastly lower dimensional space where a much smaller number of calculations suffice, and defines one set of equations that applies to all models that can be defined by the primitives. Experiments on a challenging testbed yield remarkably accurate results and the time to generate thousands of distributions is on the order of seconds. For several classical queueing systems our computational approach generates exact results.

Joint work with Steve Hackman (Georgia Tech).

Speaker's Bio

Ton Dieker is Associate Professor of Industrial Engineering and Operations Research at Columbia University, and a member of Columbia’s Data Science Institute. His research interests lie on the interface between stochastic models and computation. Ton received an M.Sc. from Vrije Universiteit Amsterdam (2002) and a Ph.D. from University of Amsterdam (2006). Honors and awards include the Goldstine Fellowship from IBM Research, the Erlang Prize from the INFORMS Applied Probability Society, and a PECASE Award from the White House.

Abstract

Restless bandits and weakly coupled Markov decision processes (WCMDPs) arise in recommender systems, active learning, revenue management, targeted marketing, and resource allocation writ large. In these problems, we allocate limited resources across a collection of "arms", choosing a resource-consuming action to apply to each arm in each time period. An arm generates rewards and changes state stochastically in a manner that depends on the action applied. Unfortunately, in modern applications with many arms N, computing the optimal policy is computationally intractable. Thus, there is a need to create scalable policies that perform well for many arms. We present a new broad class of scalable policies for restless bandits and WCMDPs. In the regime with many arms, we show their optimality gap is at worst O(sqrt(N)), matching the best bound in the literature, and is O(1), strictly better than the literature, in finite-horizon problems when a computationally verifiable non-degeneracy condition is met. In tandem with this theoretical guarantee, these policies also offer state-of-the-art empirical performance on testbed problems. This work is available at https://arxiv.org/pdf/2107.11911.pdf and https://arxiv.org/pdf/2203.15853.pdf.

Speaker's Bio

Peter Frazier is the Eleanor and Howard Morgan Professor of Operations Research and Information Engineering at Cornell University. His methodological research is in Bayesian optimization, multi-armed bandits, and incentive design for social learning. He is also interested in applied work: he is a Senior Staff Applied Scientist at Uber, where he helps design Uber's pricing systems, and he led the Cornell COVID-19 Mathematical Modeling Team, which helped design Cornell's virus testing strategy supporting safe in-person education during the pandemic. He is the recipient of an NSF CAREER Award, an AFOSR Young Investigator Award, and best paper awards from the INFORMS Computing Society, Applied Probability Society, Winter Simulation Conference, and the ACM Conference on Economics and Computation.

Abstract

Cascading failures occur when an initial disturbance triggers failures that may knock on to disastrous proportions. Unfortunately, this process occurs naturally in many different application areas, such as breakdowns in communication networks or blackouts in power grids. Yet, the study of cascading failures has long been viewed as a notoriously challenging problem due to the complexity of system dynamics and underlying dependencies. The emergence of heavy-tailed failure sizes in these settings is particularly alarming, as this implies that large-sized failures cannot be considered as virtually impossible events. A central question is how and why these heavy tails emerge, but a fundamental understanding is still lacking to this day. In this talk, we discuss several possible explanations (e.g. self-organized criticality or exogenous heavy-tailed input) and recent advances in this area, and reflect how such insights open up exciting new directions.

Speaker's Bio

Fiona Sloothaak is an assistant professor in the Department of Mathematics and Computer Science at Eindhoven University of Technology (TU/e), Netherlands. Prior to her current position, she was a postdoctoral researcher in the department of Industrial Engineering and Innovation Sciences at TU/e. She received her Ph.D. in Mathematics at TU/e in 2020, for which she was awarded the 2020 Applied Probability Trust Prize for excellent scientific achievements and received an honorable mention for the Gijs de Leve Prize 2018-2020. Fiona’s research interests include applied probability, stochastic modeling, and (learning) algorithms.

Abstract

In this talk, we report recent advances on the problems of model estimation and reward-free learning in episodic Block MDPs. In these MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function (the mapping from the observations to latent states) based on data generated under a fixed behavior policy. We derive an information-theoretical lower bound on the error rate for estimating this function and present an algorithm approaching this fundamental limit. In turn, our algorithm also provides estimates of all the components of the MDP. We then study the problem of learning near-optimal policies in the reward-free framework. Based on our efficient model estimation algorithm, we show that we can infer a policy converging (as the number of collected samples grows large) to the optimal policy at the best possible rate. Interestingly, our analysis provides necessary and sufficient conditions under which exploiting the block structure yields improvements in the sample complexity for identifying near-optimal policies. When these conditions are met, the sample complexity in the minimax reward-free setting is improved by a multiplicative factor n, where n is the number of possible contexts. Joint work with Y. Jedra, J-H. Lee and S-Y. Yun

Speaker's Bio

Alexandre Proutiere is a professor in the EECS school at KTH, Royal Institute of Technology, Stockholm, Sweden. He was a researcher at Microsoft Research (Cambridge) from 2007 to 2011, and a research engineer at France Telecom R&D from 2000 to 2006. He was an invited lecturer and researcher at the computer science department ENS Paris from 2004 to 2006. Alexandre received a Ph.D. in Applied Mathematics from Ecole Polytechnique, he graduated in Mathematics from Ecole Normale Superieure (Paris) and has an engineering degree from Telecom Paris. He is an engineer from Corps des Mines. He received the ACM Sigmetrics rising star award in 2009, the ACM best papers awards at Sigmetrics 2004 and 2010, and Mobihoc 2009. He held an ERC consolidator grant from 2012 to 2017.

Abstract

In this talk, we discuss recent advances in modeling, statistics, and computational methods for optimal transport based Distributionally Robust Optimization (DRO) - which encompasses divergence based DRO as a particular case. We discuss, for example, motivating formulations which include distributionally pricing and hedging with martingale constraints, portfolio optimization and Bayesian non-parametric inverse problems. As we present these settings, we discuss optimal sample complexity approximations and iterative optimization algorithms for these types of problems.

Speaker's Bio

Jose Blanchet is a Professor of Management Science and Engineering (MS&E) at Stanford. Prior to joining MS&E, he was a professor at Columbia, and, prior to that, he taught at Harvard. Jose is a recipient of the 2010 Erlang Prize and several best publication awards in areas such as applied probability, simulation, and operations management. He also received a PECASE Award. He has research interests in applied probability, distributionally robust optimization, machine learning and Monte Carlo methods.

Abstract

Consider a seller that has one item for sale and receives successive offers drawn from some value distributions. The decision on whether or not to accept an offer is irrevocable, and the value distributions are only partially known. We therefore let the seller adopt a robust maximin strategy, assuming that value distributions are chosen adversarially by nature to minimize the value of the accepted offer. We provide a general maximin solution to this stopping problem that identifies the optimal (threshold-based) stopping rule for the seller for all possible statistical information structures. We show for various information structures (such as mean-variance) that the seller's stopping rule consists of decreasing thresholds converging to the common mean, and that nature's adversarial response, in the long run, is to always create an all-or-nothing scenario. We use a primal-dual method for solving semi-infinite LPs that can also be applied for robust analysis of other stochastic models, such as queues, inventory models and random graphs. Joint work with Pieter Kleer (Tilburg University).

Speaker's Bio

Johan van Leeuwaarden is Professor of Stochastic Operations Research in the Econometrics and Operations Research department at the Tilburg School of Economics and Management (TiSEM). As mathematician, his research interests include probability theory, asymptotic analysis, stochastic processes, queueing theory, random graphs and stochastic optimization. Some of his research is applied for decision making under uncertainty and the design of large-scale systems.

Abstract

In this talk, I will discuss the interplay between control and statistical analysis in service systems. The choice of the control mechanism is key for obtaining desired performance and fast, online detection of persistent changes to system parameters such as servers’ service rates is key to maintaining desired service quality and availability. I will demonstrate that the choice of control has a substantial impact on the nature of the data that is being generated and consequently changes how it should be used. I will discuss the limitations of using state data (e.g. queue lengths) for detection and present a new statistic, namely action data, and demonstrate that it can be very powerful. This is joint work with Professor Kuang Xu (Stanford).

Speaker's Bio

Gal Mendelson is a Postdoc researcher at the Graduate School of Business, Stanford University. He earned a Ph.D. in Electrical Engineering from the Technion, Israel, in 2020. After his PhD, he spent a year at Nvidia before starting his Postdoc at Stanford in 2021. His research centers on resource allocation problems in service systems, decision informing statistical analysis and the interplay between the two.

Discussant's Bio

Michel Mandjes received M.Sc. degrees in mathematics and econometrics from the Free University in Amsterdam, the Netherlands, in 1993, and he received a Ph.D. in operations research from the same university in 1996. After having been a member of the technical staff at KPN Research (Leidschendam, the Netherlands) and Bell Labs (Murray Hill, New Jersey), a full professor of stochastic operations research at the University of Twente, the Netherlands, and department head at CWI in Amsterdam, he is currently a full professor of applied probability at the University of Amsterdam. He is also affiliated as an advisor with EURANDOM, Eindhoven, the Netherlands. He was visiting professor at Stanford University and Columbia University. He is project leader and main applicant of the large Dutch consortium grant NETWORKS.

His main research interests are in stochastic processes, queueing processes, efficient simulation techniques, and applications in transportation and communication networks. He is the author of two books (a single-authored book on Gaussian queues, and a coauthored book on Levy Fluctuation Theory and Queues), with a third book (on the Cramer-Lundberg model) appearing soon, and he has published more than 300 papers in journal proceedings and conferences. He was program chair of several leading conferences (INFORMS Applied Probability, Stochastic Networks), he is the Editor-in-Chief of Queueing Systems, and serves on the editorial board of multiple journals (Stochastic Systems, Stochastic Models, Journal of Applied Probability).