Spring 2022

Abstract

Classical matrix concentration inequalities give nonasymptotic bounds on the spectral norm of sums of independent random matrices. These bounds are extremely versatile and are widely used in applications. On the other hand, it is well known that these inequalities fail to yield sharp results for even the simplest random matrix models. In this talk, I will describe a powerful new class of matrix concentration inequalities that are able to capture the sharp behavior of the spectrum of many random matrix models. These inequalities arise from an unexpected phenomenon: the spectrum of random matrices is accurately captured by certain predictions of free probability theory under surprisingly minimal assumptions. I aim to explain what these new inequalities look like and how to use them.

The talk is based on joint works with Afonso Bandeira and March Boedihardjo, and with Tatiana Brailovskaya.

Bio

Abstract

The bootstrap is a versatile method for statistical uncertainty quantification, but when applied to large-scale or simulation-based models, it could face substantial computation demand from repeated data resampling and model refitting. We present a bootstrap methodology that uses minimal computation, namely with a resample effort as low as one Monte Carlo replication, while maintaining desirable statistical guarantees. We describe how this methodology can be used for fast inference across different estimation problems. We also discuss its particular relevance and generalizations to handling uncertainties in stochastic simulation analysis.

Bio

Abstract

The practicality of reinforcement learning algorithms has been limited due to poor scaling with respect to the problem size, as the sample complexity of learning an epsilon-optimal policy scales with |S| times |A| over worst case instances of an MDP with state space S, action space A, and horizon H. A key question is when can we design probably efficient RL algorithms that exploit nice structure? We consider a class of MDPs that exhibit low rank structure, where the latent features are unknown. We argue that a natural combination of value iteration and low-rank matrix estimation results in an estimation error that grows doubly exponentially in the horizon length. We then provide a new algorithm along with statistical guarantees that efficiently exploits low rank structure given access to a generative model, achieving a sample complexity that scales linearly in |S|+|A| and polynomially in the horizon and the rank. In contrast to literature on linear and low-rank MDPs, we do not require a known feature mapping, our algorithm is computationally simple, and our results hold for long time horizons. Our results provide insights on the minimal low-rank structural assumptions required on the MDP with respect to the transition kernel versus the optimal action-value function.

Bio

Abstract

Parallel-server systems have received a lot of attention over the last several years and, in particular, a lot of effort has gone towards understanding the join-the-shortest-queue (JSQ) system. In this talk I will show that in the Halfin-Whitt regime, the steady-state distribution of the JSQ system converges to its diffusion limit at a rate of 1/sqrt(n), where n is the number of servers. The proof uses Stein's method and, specifically, the recently proposed prelimit generator approach. This particular application of Stein's method is nontrivial because both the JSQ model and its diffusion limit are multidimensional, and state-space collapse is involved.

Both this result and the underlying methodology are part of a broader agenda to make Stein's method more user friendly and expand the class of models for which it can be applied. Time permitting, I will give a brief overview of the current frontiers and limitations of the approach.

Bio

Abstract

Making use of modern black-box AI tools is potentially transformational for online optimization and control. However, such machine-learned algorithms typically do not have formal guarantees on their worst-case performance, stability, or safety. So, while their performance may improve upon traditional approaches in “typical” cases, they may perform arbitrarily worse in scenarios where the training examples are not representative due to, e.g., distribution shift or unrepresentative training data. This represents a significant drawback when considering the use of AI tools for energy systems and autonomous cities, which are safety-critical. A challenging open question is thus: Is it possible to provide guarantees that allow black-box AI tools to be used in safety-critical applications? In this talk, I will introduce recent work that aims to develop algorithms that make use of black-box AI tools to provide good performance in the typical case while integrating the “untrusted advice” from these algorithms into traditional algorithms to ensure formal worst-case guarantees. Specifically, we will discuss the use of black-box untrusted advice in the context of online convex body chasing, online non-convex optimization, and linear quadratic control, identifying both novel algorithms and fundamental limits in each case.

Bio

Abstract

In the multi-secretary problem, T nonnegative, independent, random variables with common distribution are sequentially presented to a decision maker who is allowed to make k ≤ T selections to maximize the expected total value of the selected elements. Assuming that the values are drawn from a known distribution with finite support, we develop an adaptive budget-ratio policy and prove that its regret—the expected gap between the budget-ratio policy and the optimal offline solution in which all T values are made visible at time 0—is bounded by a constant that does not depend on the time horizon T and on the budget k. When we generalize the arrival process of this multi-secretary problem to one in which the arrivals in each period can be of different types and characterized by their rewards and by the resources they consume, we recover a general resource allocation problem. This (multidimensional) generalization, however, does not hinder our ability to construct an adaptive budget-ratio policy that continues to exhibit a regret that does not depend on the time horizon T or on the initial budget of each resource. Our analysis focuses on the geometric evolution of the remaining resource budgets as a stochastic process and proving that it is attracted to ``sticky'' regions of the state space where the budget-ratio policy takes actions consistent with the optimal offline solution. (Based on joint work with A. Vera, I. Gurvich and E. Levin.)

Bio

Abstract

We consider centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A network topology determines the feasible matches in the market and the value generated from each match. An inherent trade-off arises between short- and long-term objectives. A social planner may delay match decisions to thicken the market and increase match opportunities to generate high value. This inevitably compromises short-term value, and the planner may match greedily to maximize short-term objectives.

A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. We first establish that in multi-way networks, where a match can include more than two agent types, acting greedily is suboptimal, and a periodic clearing policy with a carefully chosen period length is hindsight optimal. Interestingly, in two-way networks, where any match includes two agent types, suitably designed greedy policies also achieve hindsight optimality. This implies that there is essentially no positive externality from having agents waiting to form future matches.

Central to our results is the general position gap, ε, which quantifies the stability or the imbalance in the network. No policy can achieve a regret that is lower than the order of 1/ε at all times. This lower bound is achieved by the proposed policies.

The talk is based on joint work with Suleyman Kerimov and Itai Ashlagi.

Bio

Abstract

In this talk I will describe two vignettes of sequential decision making problems arising in the OR literature. The first is the classical “house selling” problem (or optimal stopping): given a random sequence of independent observations revealed one at a time over some finite horizon of play, the objective is to design an algorithm that “stops’’ this sequence to maximize the expected value of the ``stopped” observation. The second vignette is the worker assignment problem (or sequential stochastic assignment): arriving items (“jobs”) with independent stochastic attributes need to be sequentially matched to a pool of awaiting recipients (“workers”). Once each job/worker are matched they are no longer admissible for further assignment, and the objective is to maximize the expected cumulative value of the resulting matchings. Both problems date back more than 50 years and can be solved in a relatively straightforward manner using dynamic programming; both have been used as modeling constructs in numerous applications including recent online marketplaces. Somewhat surprisingly, neither has been studied extensively when the underlying information on the stochastic primitives is unknown a priori. While it is possible to analyze this incomplete information setting with generic multi-purpose learning theoretic methods, these tend to be quite inefficient when further “structure” is present in the problem and can be exploited to construct more customized algorithms. The main focus of this talk is to broadly describe possible learning theoretic formulations of the two vignettes, and illustrate some “design principles” for constructing near-optimal policies.

Bio