Fall 2021

Abstract

We consider a novel formulation of the dynamic pricing and demand learning problem, where the evolution of demand in response to posted prices is governed by a stochastic variant of the popular Bass model with parameters (α, β) that are linked to the so-called "innovation" and "imitation" effects. Unlike the more commonly used i.i.d. demand models, in this model the price posted not only affects the demand and the revenue in the current round but also the evolution of demand, and hence the fraction of market potential that can be captured, in future rounds. Finding a revenue-maximizing dynamic pricing policy in this model is non-trivial even when model parameters are known, and requires solving for the optimal non-stationary policy of a continuous-time, continuous-state MDP. In this paper, we consider the problem of dynamic pricing is used in conjunction with learning the model parameters, with the objective of optimizing the cumulative revenues over a given selling horizon. Our main contribution is an algorithm with a regret guarantee of O (m^2/3), where m is mnemonic for the (known) market size. Moreover, we show that no algorithm can incur smaller order of loss by deriving a matching lower bound. We observe that in this problem the market size m, and not the time horizon T, is the fundamental driver of the complexity; our lower bound in fact indicates that for any fixed α,β, most non-trivial instances of the problem have constant T and large m. This insight sets the problem setting considered here uniquely apart from the MAB type formulations typically considered in the learning to price literature.

Bio

Abstract

Driverless vehicles promise a host of societal benefits including dramatically improved safety, increased accessibility, greater productivity, and higher quality of life. As this new technology approaches widespread deployment, both industry and government are making provisions for teleoperations systems, in which remote human agents provide assistance to driverless vehicles. This assistance can involve real-time remote operation and even ahead-of-time input via human-in-the-loop artificial intelligence systems. In this paper, we address the problem of staffing such a remote support center. Our analysis focuses on the tradeoffs between the total number of remote agents, the reliability of the remote support system, and the resulting safety of the driverless vehicles. By establishing a novel connection between queues with large batch arrivals and storage processes, we determine the probability of the system exceeding its service capacity. This connection drives our staffing methodology. We also develop a numerical method to compute the exact staffing level needed to achieve various performance measures. Our overall staffing analysis may be of use in other applications that combine human expertise and automated systems.

Bio

Abstract

Previous research has shown that early discharge of patients may hurt their medical outcomes. However, in many cases, the "optimal" length of stay (LOS) and the best location for treatment of the patient are not obvious. A case in point is hematology patients, for whom this is a critical decision. These patients are hospitalized on a regular basis for chemotherapy treatments and it is debated whether following these treatments the patients should stay at the hospital for an observation period or be sent home instead. Patients with hematological malignancies are susceptible to life-threatening infections after chemotherapy. Hence, LOS optimization for hematology patients must balance the risks of patient infection and mortality. The former is reduced by minimizing hospital stay, while the latter is reduced by maximizing hospital stay, whereby infections can be identified and treated earlier. We develop a Markov decision process formulation to explore the impact of the infection and mortality risks on the optimal LOS from a single-patient perspective. We further consider the social optimization problem in which capacity constraints limit the ability of hospitals to keep patients for the entirety of their optimal LOS. We find that the optimal policy under this constraint takes the form of a two-threshold policy. This policy may block some patients and immediately route them to home care, or speed up some patients' LOS and send them to home care early after an observation period in the hospital. Joint work with Prof. Galit Yom-Tov from the Technion.

Bio

Abstract

Multiserver jobs, which are jobs that occupy multiple servers simultaneously during service, are prevalent in today's computing clusters. However, little is known about the delay performance of systems with multiserver jobs. In this talk, to capture the large scale of modern computing clusters, we consider the scheduling problem of multiserver jobs in systems where the total number of servers becomes large. The multi-server job model opens up new scaling regimes where both the number of servers that a job needs and the system load scale with the total number of servers. Within these scaling regimes, we first characterize when the queueing probability diminishes as the system becomes large, and then turn our focus to the mean waiting time, i.e., the time a job spends in queueing rather than in service. In particular, we derive order-wise sharp bounds on the mean waiting time under various policies. The sharpness of the bounds allows us to establish the asymptotic optimality of a priority policy that we call P-Priority, and the strict suboptimality of the commonly used First-Come-First-Serve (FCFS) policy. This talk is based on joint works with Yige Hong, Qiaomin Xie, and Mor Harchol-Balter.

Bio

Abstract

In this talk we consider two classic and popular problems in the stochastic multi armed bandit settings. 1) Regret minimization, where given a finite set of unknown reward distributions (or arms) that can be sequentially sampled, the aim is to sample in a manner that maximizes the expected reward, or equivalently, minimizes the expected regret, over a large sampling horizon. 2) Best arm identification, where in a similar sequential setting the aim is to select the arm with the largest mean using a minimum number of samples on average while keeping the probability of false selection to a pre-specified and small value. Both these problems with a myriad of variations have been well studied in the literature. The analysis techniques for the two problems are typically different and typically the arm distributions are restricted to a small class such as a single parameter exponential family or distributions that are bounded with known bounds. In practice, such restrictions often do not hold and the arm distributions may even be heavy-tailed. In this talk we discuss how to optimally solve both the above problems when minimal restrictions are imposed on the arm distributions. Further, we highlight the commonalities of techniques in solving the two problems.

Bio

Abstract

Consider a scenario where we are training a model or performing statistical analyses on a shared dataset with entries collected from several contributing individuals. Differential privacy provides protection against membership inference attacks that try to reveal sensitive information in the dataset. Robust estimators provide protection against data poisoning attacks where malicious contributors inject corrupted data. Even though both types of attacks are powerful and easy to launch in practice, there is no algorithm providing protection against both simultaneously. In the first half of this talk, I will present the first efficient algorithm that guarantees both differential privacy and robustness to the corruption of a fraction of the data. I will focus on the canonical problem of mean estimation, which is a critical building block in many algorithms including stochastic gradient descent for training deep neural networks. In the second half of this talk, I will present a new framework that bridges differential privacy and robust statistics, which we call High-dimensional Propose-Test-Release (HPTR). This is a computationally intractable approach, but universally applicable to several statistical estimation problems including mean estimation, linear regression, covariance estimation, and principal component analysis. In most of these cases, HPTR achieves a near-optimal sample complexity by exploiting robust statistics in the algorithm, thus characterizing the minimax error rate of the corresponding private estimation problems for the first time. This talk is based on two recent papers (https://arxiv.org/abs/2104.11315 and https://arxiv.org/abs/2102.09159) and an unpublished ongoing work.

Bio

Abstract

Many inverse problems arising in applications may be cast as optimization or sampling problems in which the parameter-to-data map is provided as a black-box, derivatives may not be readily available and the evaluation of the map itself may be subject to noise. I will describe the derivation of mean-field (stochastic) dynamical systems which address such problems and show how particle approximations lead to derivative-free algorithms. I will overview some of the analysis of the resulting methods, link the work to parallel developments in consensus-based optimization, and describe open problems. The work will be illustrated throughout by examples from the physical sciences.

Bio