Publications

We explore the control of stochastic systems with potentially continuous state and action spaces, characterized by the state dynamics . Here, , , and represent the state, action, and exogenous random noise processes, respectively, with denoting a known function that describes state transitions. Traditionally, the noise process is assumed to be independent and identically distributed, with a distribution that is either fully known or can be consistently estimated. However, the occurrence of distributional shifts, typical in engineering settings, necessitates the consideration of the robustness of the policy. This paper introduces a distributionally robust stochastic control paradigm that accommodates possibly adaptive adversarial perturbation to the noise distribution within a prescribed ambiguity set. We examine two adversary models: current-action-aware and current-action-unaware, leading to different dynamic programming equations. Furthermore, we characterize the optimal finite sample minimax rates for achieving uniform learning of the robust value function across continuum states under both adversary types, considering ambiguity sets defined by -divergence and Wasserstein distance. Finally, we demonstrate the applicability of our framework across various real-world settings.

Authors
Shengbo Wang, Nian Si, Jose Blanchet, Zhengyuan Zhou
Publication date
2024/6/17
Journal
arXiv preprint arXiv:2406.11281

Recent studies have established a connection between the macroscopic mechanical response of polymeric materials and the statistics of the shortest path (SP) length between distant nodes in the polymer network. Since these statistics can be costly to compute and difficult to study theoretically, we introduce a branching random walk (BRW) model to describe the SP statistics from the coarse-grained molecular dynamics (CGMD) simulations of polymer networks. We postulate that the first passage time (FPT) of the BRW to a given termination site can be used to approximate the statistics of the SP between distant nodes in the polymer network. We develop a theoretical framework for studying the FPT of spatial branching processes and obtain an analytical expression for estimating the FPT distribution as a function of the cross-link density. We demonstrate by extensive numerical calculations that the distribution of the …

Authors
Zhenyuan Zhang, Shaswat Mohanty, Jose Blanchet, Wei Cai
Publication date
2024/6/1
Journal
Journal of the Mechanics and Physics of Solids
Volume
187
Pages
105636
Publisher
Pergamon

Convergence rate analysis for general state-space Markov chains is fundamentally important in areas such as Markov chain Monte Carlo and algorithmic analysis (for computing explicit convergence bounds). This problem, however, is notoriously difficult because traditional analytical methods often do not generate practically useful convergence bounds for realistic Markov chains. We propose the Deep Contractive Drift Calculator (DCDC), the first general-purpose sample-based algorithm for bounding the convergence of Markov chains to stationarity in Wasserstein distance. The DCDC has two components. First, inspired by the new convergence analysis framework in (Qu et.al, 2023), we introduce the Contractive Drift Equation (CDE), the solution of which leads to an explicit convergence bound. Second, we develop an efficient neural-network-based CDE solver. Equipped with these two components, DCDC solves the CDE and converts the solution into a convergence bound. We analyze the sample complexity of the algorithm and further demonstrate the effectiveness of the DCDC by generating convergence bounds for realistic Markov chains arising from stochastic processing networks as well as constant step-size stochastic optimization.

Authors
Yanlin Qu, Jose Blanchet, Peter Glynn
Publication date
2024/5/30
Journal
arXiv preprint arXiv:2405.20435

Aligning generative models with human preference via RLHF typically suffers from overoptimization, where an imperfectly learned reward model can misguide the generative model to output undesired responses. We investigate this problem in a principled manner by identifying the source of the misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model; one that simultaneously minimizes the maximum likelihood estimation of the loss and a reward penalty term. Here, the reward penalty term is introduced to prevent the policy from choosing actions with spurious high proxy rewards, resulting in provable sample efficiency of the algorithm under a partial coverage style condition. Moving from theory to practice, the proposed algorithm further enjoys an equivalent but surprisingly easy-to-implement reformulation. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines: (i) a preference optimization loss that directly aligns the policy with human preference, and (ii) a supervised learning loss that explicitly imitates the policy with a (suitable) baseline distribution. In the context of aligning large language models (LLM), this objective fuses the direct preference optimization (DPO) loss with the supervised fune-tuning (SFT) loss to help mitigate the overoptimization towards undesired responses, for which we name the algorithm Regularized Preference Optimization (RPO). Experiments of aligning LLMs …

Authors
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, Zhaoran Wang
Publication date
2024/5/26
Journal
arXiv preprint arXiv:2405.16436

Recent progress in Neural Causal Models (NCMs) showcased how identification and partial identification of causal effects can be automatically carried out via training of neural generative models that respect the constraints encoded in a given causal graph [Xia et al. 2022, Balazadeh et al. 2022]. However, formal consistency of these methods has only been proven for the case of discrete variables or only for linear causal models. In this work, we prove consistency of partial identification via NCMs in a general setting with both continuous and categorical variables. Further, our results highlight the impact of the design of the underlying neural network architecture in terms of depth and connectivity as well as the importance of applying Lipschitz regularization in the training phase. In particular, we provide a counterexample showing that without Lipschitz regularization the NCM may not be asymptotically consistent. Our results are enabled by new results on the approximability of structural causal models via neural generative models, together with an analysis of the sample complexity of the resulting architectures and how that translates into an error in the constrained optimization problem that defines the partial identification bounds.

Authors
Jiyuan Tan, Jose Blanchet, Vasilis Syrgkanis
Publication date
2024/5/24
Journal
arXiv preprint arXiv:2405.15673

The performance of learning models often deteriorates when deployed in out-of-sample environments. To ensure reliable deployment, we propose a stability evaluation criterion based on distributional perturbations. Conceptually, our stability evaluation criterion is defined as the minimal perturbation required on our observed dataset to induce a prescribed deterioration in risk evaluation. In this paper, we utilize the optimal transport (OT) discrepancy with moment constraints on the \textit{(sample, density)} space to quantify this perturbation. Therefore, our stability evaluation criterion can address both \emph{data corruptions} and \emph{sub-population shifts} -- the two most common types of distribution shifts in real-world scenarios. To further realize practical benefits, we present a series of tractable convex formulations and computational methods tailored to different classes of loss functions. The key technical tool to achieve this is the strong duality theorem provided in this paper. Empirically, we validate the practical utility of our stability evaluation criterion across a host of real-world applications. These empirical studies showcase the criterion's ability not only to compare the stability of different learning models and features but also to provide valuable guidelines and strategies to further improve models.

Authors
Jose Blanchet, Peng Cui, Jiajin Li, Jiashuo Liu
Publication date
2024/5/6
Journal
arXiv preprint arXiv:2405.03198

The performance of learning models often deteriorates when deployed in out-of-sample environments. To ensure reliable deployment, we propose a stability evaluation criterion based on distributional perturbations. Conceptually, our stability evaluation criterion is defined as the minimal perturbation required on our observed dataset to induce a prescribed deterioration in risk evaluation. In this paper, we utilize the optimal transport (OT) discrepancy with moment constraints on the (sample, density) space to quantify this perturbation. Therefore, our stability evaluation criterion can address both data corruptions and sub-population shifts—the two most common types of distribution shifts in real-world scenarios. To further realize practical benefits, we present a series of tractable convex formulations and computational methods tailored to different classes of loss functions. The key technical tool to achieve this is the strong duality theorem provided in this paper. Empirically, we validate the practical utility of our stability evaluation criterion across a host of real-world applications. These empirical studies showcase the criterion's ability not only to compare the stability of different learning models and features but also to provide valuable guidelines and strategies to further improve models.

Authors
Jose Blanchet, Peng Cui, Jiajin Li, Jiashuo Liu
Conference
Forty-first International Conference on Machine Learning

A system is disclosed that includes a computer that includes a processor and a memory, the memory including instructions executable by the processor to input an image acquired by a sensor to a neural network to output a prediction regarding an object included in the image. The neural network can be trained, based on (a) a distributed robust optimization that minimizes an expectation applied to probability distributions of loss functions to select training images that yield a solution with a selected uncertainty level and (b) generating additional input images based on adversarial images.

Inventors
Xinru Hua, Huanzhong Xu, Jose Blanchet, Viet Anh Nguyen, Marcos Paul Gerardo Castro
Publication date
2024/5/2
Patent office
US
Application number
18051578

The goal of this paper is to develop distributionally robust optimization (DRO) estimators, specifically for multidimensional Extreme Value Theory (EVT) statistics. EVT supports using semi-parametric models called max-stable distributions built from spatial Poisson point processes. While powerful, these models are only asymptotically valid for large samples. However, since extreme data is by definition scarce, the potential for model misspecification error is inherent to these applications, thus DRO estimators are natural. In order to mitigate over-conservative estimates while enhancing out-of-sample performance, we study DRO estimators informed by semi-parametric max-stable constraints in the space of point processes. We study both tractable convex formulations for some problems of interest (e.g. CVaR) and more general neural network based estimators. Both approaches are validated using synthetically generated data, recovering prescribed characteristics, and verifying the efficacy of the proposed techniques. Additionally, the proposed method is applied to a real data set of financial returns for comparison to a previous analysis. We established the proposed model as a novel formulation in the multivariate EVT domain, and innovative with respect to performance when compared to relevant alternate proposals.

Authors
Patrick Kendal Kuiper, Ali Hasan, Wenhao Yang, Jose Blanchet, Vahid Tarokh, Yuting Ng, Hoda Bidkhori
Conference
The 40th Conference on Uncertainty in Artificial Intelligence

Bootstrap is a popular methodology for simulating input uncertainty. However, it can be computationally expensive when the number of samples is large. We propose a new approach called \textbf{Orthogonal Bootstrap} that reduces the number of required Monte Carlo replications. We decomposes the target being simulated into two parts: the \textit{non-orthogonal part} which has a closed-form result known as Infinitesimal Jackknife and the \textit{orthogonal part} which is easier to be simulated. We theoretically and numerically show that Orthogonal Bootstrap significantly reduces the computational cost of Bootstrap while improving empirical accuracy and maintaining the same width of the constructed interval.

Authors
Kaizhao Liu, Jose Blanchet, Lexing Ying, Yiping Lu
Publication date
2024/4/29
Journal
arXiv preprint arXiv:2404.19145

Average reward reinforcement learning (RL) provides a suitable framework for capturing the objective (ie long-run average reward) for continuing tasks, where there is often no natural way to identify a discount factor. However, existing average reward RL algorithms with sample complexity guarantees are not feasible, as they take as input the (unknown) mixing time of the Markov decision process (MDP). In this paper, we make initial progress towards addressing this open problem. We design a feasible average-reward -learning framework that requires no knowledge of any problem parameter as input. Our framework is based on discounted -learning, while we dynamically adapt the discount factor (and hence the effective horizon) to progressively approximate the average reward. In the synchronous setting, we solve three tasks:(i) learn a policy that is -close to optimal,(ii) estimate optimal average reward with -accuracy, and (iii) estimate the bias function (similar to -function in discounted case) with -accuracy. We show that with carefully designed adaptation schemes,(i) can be achieved with samples,(ii) with samples, and (iii) with samples, where is the mixing time, and is an MDP-dependent constant. To our knowledge, we provide the first finite-sample guarantees that are polynomial in for a feasible variant of -learning. That said, the sample complexity bounds have tremendous room for improvement, which we leave for the community’s best minds. Preliminary simulations verify that our framework is effective without prior knowledge of parameters as input.

Authors
Ying Jin, Ramki Gummadi, Zhengyuan Zhou, Jose Blanchet
Publication date
2024/4/18
Conference
International Conference on Artificial Intelligence and Statistics
Pages
1630-1638
Publisher
PMLR

We study the first passage times of discrete-time branching random walks in where . Here, the genealogy of the particles follows a supercritical Galton-Watson process. We provide asymptotics of the first passage times to a ball of radius one with a distance from the origin, conditioned upon survival. We provide explicitly the linear dominating term and the logarithmic correction term as a function of . The asymptotics are precise up to an order of for general jump distributions and up to for spherically symmetric jumps. A crucial ingredient of both results is the tightness of first passage times. We also discuss an extension of the first passage time analysis to a modified branching random walk model that has been proven to successfully capture shortest path statistics in polymer networks.

Authors
Jose Blanchet, Wei Cai, Shaswat Mohanty, Zhenyuan Zhang
Publication date
2024/4/13
Journal
arXiv preprint arXiv:2404.09064

The sim-to-real gap, which represents the disparity between training and testing environments, poses a significant challenge in reinforcement learning (RL). A promising approach to addressing this challenge is distributionally robust RL, often framed as a robust Markov decision process (RMDP). In this framework, the objective is to find a robust policy that achieves good performance under the worst-case scenario among all environments within a pre-specified uncertainty set centered around the training environment. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, we tackle robust RL via interactive data collection, where the learner interacts with the training environment only and refines the policy through trial and error. In this robust RL paradigm, two main challenges emerge: managing distributional robustness while striking a balance between exploration and exploitation during data collection. Initially, we establish that sample-efficient learning without additional assumptions is unattainable owing to the curse of support shift; i.e., the potential disjointedness of the distributional supports between the training and testing environments. To circumvent such a hardness result, we introduce the vanishing minimal value assumption to RMDPs with a total-variation (TV) distance robust set, postulating that the minimal value of the optimal robust value function is zero. We prove that such an assumption effectively eliminates the support shift issue for RMDPs with a TV distance robust set, and present an algorithm with a provable sample complexity guarantee …

Authors
Miao Lu, Han Zhong, Tong Zhang, Jose Blanchet
Publication date
2024/4/4
Journal
arXiv preprint arXiv:2404.03578

Due to the potential benefits of parallelization, designing unbiased Monte Carlo estimators, primarily in the setting of randomized multilevel Monte Carlo, has recently become very popular in operations research and computational statistics. However, existing work primarily substantiates the benefits of unbiased estimators at an intuitive level or using empirical evaluations. The intuition being that unbiased estimators can be replicated in parallel enabling fast estimation in terms of wall-clock time. This intuition ignores that, typically, bias will be introduced due to impatience because most unbiased estimators necesitate random completion times. This paper provides a mathematical framework for comparing these methods under various metrics, such as completion time and overall computational cost. Under practical assumptions, our findings reveal that unbiased methods typically have superior completion times - the degree of superiority being quantifiable through the tail behavior of their running time distribution - but they may not automatically provide substantial savings in overall computational costs. We apply our findings to Markov Chain Monte Carlo and Multilevel Monte Carlo methods to identify the conditions and scenarios where unbiased methods have an advantage, thus assisting practitioners in making informed choices between unbiased and biased methods.

Authors
Guanyang Wang, Jose Blanchet, Peter W Glynn
Publication date
2024/4/1
Journal
arXiv preprint arXiv:2404.01431

We prove a sample-path large deviation principle (LDP) with sublinear speed for unbounded functionals of certain Markov chains induced by the Lindley recursion. The LDP holds in the Skorokhod space D [0, 1] equipped with the M 1′ topology. Our technique hinges on a suitable decomposition of the Markov chain in terms of regeneration cycles. Each regeneration cycle denotes the area accumulated during the busy period of the reflected random walk. We prove a large deviation principle for the area under the busy period of the Markov random walk, and we show that it exhibits a heavy-tailed behavior.

Authors
Mihail Bazhba, Jose Blanchet, Chang-Han Rhee, Bert Zwart
Publication date
2024/3/27
Journal
Mathematics of Operations Research
Publisher
INFORMS

In this paper, we propose a novel conceptual framework to detect outliers using optimal transport with a concave cost function. Conventional outlier detection approaches typically use a two-stage procedure: first, outliers are detected and removed, and then estimation is performed on the cleaned data. However, this approach does not inform outlier removal with the estimation task, leaving room for improvement. To address this limitation, we propose an automatic outlier rectification mechanism that integrates rectification and estimation within a joint optimization framework. We take the first step to utilize an optimal transport distance with a concave cost function to construct a rectification set in the space of probability distributions. Then, we select the best distribution within the rectification set to perform the estimation task. Notably, the concave cost function we introduced in this paper is the key to making our estimator effectively identify the outlier during the optimization process. We discuss the fundamental differences between our estimator and optimal transport-based distributionally robust optimization estimator. finally, we demonstrate the effectiveness and superiority of our approach over conventional approaches in extensive simulation and empirical analyses for mean estimation, least absolute regression, and the fitting of option implied volatility surfaces.

Authors
Jose Blanchet, Jiajin Li, Markus Pelger, Greg Zanotti
Publication date
2024/3/21
Journal
arXiv preprint arXiv:2403.14067

Recent studies have established a connection between the macroscopic mechanical response of polymeric materials and the statistics of the shortest path (SP) length between distant nodes in the polymer network. Since these statistics can be costly to compute and difficult to study theoretically, we introduce a branching random walk (BRW) model to describe the shortest path statistics from the coarse-grained molecular dynamics (CGMD) simulations of polymer networks. We postulate that the first passage time (FPT) of the BRW to a given termination site can be used to approximate the statistics of the SP between distant nodes in the polymer network.

We develop a theoretical framework for studying the FPT of spatial branching processes and obtain an analytical expression for estimating the FPT distribution as a function of the cross-link density.

Authors
Shaswat Mohanty, Wei Cai, Zhenyuan Zhang, Jose Blanchet
Publication date
2024/3/4
Journal
Bulletin of the American Physical Society
Publisher
American Physical Society

We consider a generic class of chance-constrained optimization problems with heavy-tailed (i.e., power-law type) risk factors. As the most popular generic method for solving chance constrained optimization, the scenario approach generates sampled optimization problem as a precise approximation with provable reliability, but the computational complexity becomes intractable when the risk tolerance parameter is small. To reduce the complexity, we sample the risk factors from a conditional distribution given that the risk factors are in an analytically tractable event that encompasses all the plausible events of constraints violation. Our approximation is proven to have optimal value within a constant factor to the optimal value of the original chance constraint problem with high probability, uniformly in the risk tolerance parameter. To the best of our knowledge, our result is the first uniform performance guarantee of this …

Authors
Jose Blanchet, Fan Zhang, Bert Zwart
Publication date
2024/3
Journal
Stochastic Systems
Volume
14
Issue
1
Pages
22-46
Publisher
INFORMS

We study distributionally robust offline reinforcement learning (RL), which seeks to find an optimal robust policy purely from an offline dataset that can perform well in perturbed environments. We propose a generic algorithm framework Doubly Pessimistic Model-based Policy Optimization () for robust offline RL, which features a novel combination of a flexible model estimation subroutine and a doubly pessimistic policy optimization step. Here the double pessimism principle is crucial to overcome the distribution shift incurred by i) the mismatch between behavior policy and the family of target policies; and ii) the perturbation of the nominal model. Under certain accuracy assumptions on the model estimation subroutine, we show that is provably sample-efficient with robust partial coverage data, which means that the offline dataset has good coverage of the distributions induced by the optimal robust policy and perturbed models around the nominal model. By tailoring specific model estimation subroutines for concrete examples including tabular Robust Markov Decision Process (RMDP), factored RMDP, and RMDP with kernel and neural function approximations, we show that enjoys a convergence rate, where is the number of trajectories in the offline dataset. Notably, these models, except for the tabular case, are first identified and proven tractable by this paper. To the best of our knowledge, we first propose a general learning principle---double pessimism---for robust offline RL and show that it is provably efficient in the context of general function approximations.

Authors
Jose Blanchet, Miao Lu, Tong Zhang, Han Zhong
Publication date
2024/2/13
Journal
Advances in Neural Information Processing Systems
Volume
36

This paper studies the use of a machine learning-based estimator as a control variate for mitigating the variance of Monte Carlo sampling. Specifically, we seek to uncover the key factors that influence the efficiency of control variates in reducing variance. We examine a prototype estimation problem that involves simulating the moments of a Sobolev function based on observations obtained from (random) quadrature nodes. Firstly, we establish an information-theoretic lower bound for the problem. We then study a specific quadrature rule that employs a nonparametric regression-adjusted control variate to reduce the variance of the Monte Carlo simulation. We demonstrate that this kind of quadrature rule can improve the Monte Carlo rate and achieve the minimax optimal rate under a sufficient smoothness assumption. Due to the Sobolev Embedding Theorem, the sufficient smoothness assumption eliminates the existence of rare and extreme events. Finally, we show that, in the presence of rare and extreme events, a truncated version of the Monte Carlo algorithm can achieve the minimax optimal rate while the control variate cannot improve the convergence rate.

Authors
Jose Blanchet, Haoxuan Chen, Yiping Lu, Lexing Ying
Publication date
2024/2/13
Journal
Advances in Neural Information Processing Systems
Volume
36

In this paper, we study the problem of learning in quantum games-and other classes of semidefinite games-with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

Authors
Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose Blanchet
Publication date
2024/2/13
Journal
Advances in Neural Information Processing Systems
Volume
36

Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Most existing algorithms rely on one-sided information, such as the convexity (resp. concavity) of the primal (resp. dual) functions, or other specific structures, such as the Polyak-Łojasiewicz (PŁ) and Kurdyka-Łojasiewicz (KŁ) conditions. However, verifying these regularity conditions is challenging in practice. To meet this challenge, we propose a novel universally applicable single-loop algorithm, the doubly smoothed gradient descent ascent method (DS-GDA), which naturally balances the primal and dual updates. That is, DS-GDA with the same hyperparameters is able to uniformly solve nonconvex-concave, convex-nonconcave, and nonconvex-nonconcave problems with one-sided KŁ properties, achieving convergence with complexity. Sharper (even optimal) iteration complexity can be obtained when the KŁ exponent is known. Specifically, under the one-sided KŁ condition with exponent , DS-GDA converges with an iteration complexity of $\mathcal {O}(\epsilon^{-2\max\\{2\theta, 1\\}}) $. They all match the corresponding best results in the literature. Moreover, we show that DS-GDA is practically applicable to general nonconvex-nonconcave problems even without any regularity conditions, such as the PŁ condition, KŁ condition, or weak Minty variational inequalities condition. For various challenging nonconvex-nonconcave examples in the literature, including* Forsaken*,* Bilinearly-coupled minimax*,* Sixth-order polynomial*, and* PolarGame*, the proposed DS-GDA can all get …

Authors
Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, José Blanchet, Jiajin Li
Publication date
2024/2/13
Journal
Advances in Neural Information Processing Systems
Volume
36

In materials science, experimental datasets are commonly used to estimate various statistics of random variables. This paper focuses on a specific random variable: the rupture stretch of a material. Examples of statistics include average, standard deviation, coefficient of variation, and different quantiles. How accurate is the estimate of such a statistic? The answer depends on the statistic, the size of the experimental dataset, and how much the random variable scatters. Here we demonstrate a procedure to generate a large experimental dataset and use the experimental dataset to estimate the accuracy of various statistics of the rupture stretch. We use a high-throughput experiment to measure the rupture stretches of 160 specimens of a silicone rubber. We then use the bootstrap method to determine the 90 % confidence intervals of several statistics. We find that the experimental dataset accurately estimates the …

Authors
Yifan Zhou, Sirui Lin, Xuhui Zhang, Hou Wu, Jose Blanchet, Zhigang Suo, Tongqing Lu
Publication date
2024/2/1
Journal
Journal of the Mechanics and Physics of Solids
Volume
183
Pages
105521
Publisher
Pergamon

In this paper, we consider online learning in generalized linear contextual bandits where rewards are not immediately observed. Instead, rewards are available to the decision maker only after some delay, which is unknown and stochastic. Such delayed feedback occurs in several active learning settings, including product recommendation, personalized medical treatment selection, bidding in first-price auctions, and bond trading in over-the-counter markets. We study the performance of two well-known algorithms adapted to this delayed setting: one based on upper confidence bounds and the other based on Thompson sampling. We describe modifications on how these two algorithms should be adapted to handle delays and give regret characterizations for both algorithms. To the best of our knowledge, our regret bounds provide the first theoretical characterizations in generalized linear contextual bandits with …

Authors
Jose Blanchet, Renyuan Xu, Zhengyuan Zhou
Publication date
2024/2
Journal
Mathematics of Operations Research
Volume
49
Issue
1
Pages
326-345
Publisher
INFORMS

We review distributionally robust optimization (DRO), a principled approach for constructing statistical estimators that hedge against the impact of deviations in the expected loss between the training and deployment environments. Many well-known estimators in statistics and machine learning (e.g. AdaBoost, LASSO, ridge regression, dropout training, etc.) are distributionally robust in a precise sense. We hope that by discussing the DRO interpretation of well-known estimators, statisticians who may not be too familiar with DRO may find a way to access the DRO literature through the bridge between classical results and their DRO equivalent formulation. On the other hand, the topic of robustness in statistics has a rich tradition associated with removing the impact of contamination. Thus, another objective of this paper is to clarify the difference between DRO and classical statistical robustness. As we will see, these are two fundamentally different philosophies leading to completely different types of estimators. In DRO, the statistician hedges against an environment shift that occurs after the decision is made; thus DRO estimators tend to be pessimistic in an adversarial setting, leading to a min-max type formulation. In classical robust statistics, the statistician seeks to correct contamination that occurred before a decision is made; thus robust statistical estimators tend to be optimistic leading to a min-min type formulation.

Authors
Jose Blanchet, Jiajin Li, Sirui Lin, Xuhui Zhang
Publication date
2024/1/26
Journal
arXiv preprint arXiv:2401.14655

Given a collection of multidimensional pairs , we study the problem of projecting the associated suitably smoothed empirical measure onto the space of martingale couplings (i.e. distributions satisfying ) using the adapted Wasserstein distance. We call the resulting distance the smoothed empirical martingale projection distance (SE-MPD), for which we obtain an explicit characterization. We also show that the space of martingale couplings remains invariant under the smoothing operation. We study the asymptotic limit of the SE-MPD, which converges at a parametric rate as the sample size increases if the pairs are either i.i.d. or satisfy appropriate mixing assumptions. Additional finite-sample results are also investigated. Using these results, we introduce a novel consistent martingale coupling hypothesis test, which we apply to test the existence of arbitrage opportunities in recently introduced neural network-based generative models for asset pricing calibration.

Authors
Jose Blanchet, Johannes Wiesel, Erica Zhang, Zhenyuan Zhang
Publication date
2024/1/22
Journal
arXiv preprint arXiv:2401.12197

In this study, we give an extension of Montanaro's arXiv/archive:1504.06987 quantum Monte Carlo method, tailored for computing expected values of random variables that exhibit infinite variance. This addresses a challenge in analyzing heavy-tailed distributions, which are commonly encountered in various scientific and engineering fields. Our quantum algorithm efficiently estimates means for variables with a finite moment, where lies between 0 and 1. It provides a quadratic speedup over the classical Monte Carlo method in both the accuracy parameter and the specified moment of the distribution. We establish both classical and quantum lower bounds, showcasing the near-optimal efficiency of our algorithm among quantum methods. Our work focuses not on creating new algorithms, but on analyzing the execution of existing algorithms with available additional information about the random variable. Additionally, we categorize these scenarios and demonstrate a hierarchy in the types of supplementary information that can be provided.

Authors
Jose Blanchet, Mario Szegedy, Guanyang Wang
Publication date
2024/1/15
Journal
arXiv preprint arXiv:2401.07497

In the field of computational physics and material science, the efficient sampling of rare events occurring at atomic scale is crucial. It aids in understanding mechanisms behind a wide range of important phenomena, including protein folding, conformal changes, chemical reactions and materials diffusion and deformation. Traditional simulation methods, such as Molecular Dynamics and Monte Carlo, often prove inefficient in capturing the timescale of these rare events by brute force. In this paper, we introduce a practical approach by combining the idea of importance sampling with deep neural networks (DNNs) that enhance the sampling of these rare events. In particular, we approximate the variance-free bias potential function with DNNs which is trained to maximize the probability of rare event transition under the importance potential function. This method is easily scalable to high-dimensional problems and provides robust statistical guarantees on the accuracy of the estimated probability of rare event transition. Furthermore, our algorithm can actively generate and learn from any successful samples, which is a novel improvement over existing methods. Using a 2D system as a test bed, we provide comparisons between results obtained from different training strategies, traditional Monte Carlo sampling and numerically solved optimal bias potential function under different temperatures. Our numerical results demonstrate the efficacy of the DNN-based importance sampling of rare events.

Authors
Xinru Hua, Rasool Ahmad, Jose Blanchet, Wei Cai
Publication date
2024/1/13
Journal
arXiv preprint arXiv:2401.06936

We provide faster algorithms for approximating the optimal transport distance, eg earth mover's distance, between two discrete probability distributions on n elements. We present two algorithms which compute couplings between marginal distributions with an expected transportation cost that is within an additive ϵ of optimal in time O˜(n 2/ϵ); one algorithm is straightforward to parallelize and implementable in depth O˜(1/ϵ). Further, we show that additional improvements on our results must be coupled with breakthroughs in algorithmic graph theory.

Authors
Jose Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
Publication date
2024/1/1
Journal
Operations Research Letters
Volume
52
Pages
107054
Publisher
North-Holland

We study minimax risk bounds for estimators of the spectral measure in multivariate linear factor models, where observations are linear combinations of regularly varying latent factors. Non-asymptotic convergence rates are derived for the multivariate Peak-over-Threshold estimator in terms of the -th order Wasserstein distance, and information-theoretic lower bounds for the minimax risks are established. The convergence rate of the estimator is shown to be minimax optimal under a class of Pareto-type models analogous to the standard class used in the setting of one-dimensional observations known as the Hall-Welsh class. When the estimator is minimax inefficient, a novel two-step estimator is introduced and demonstrated to attain the minimax lower bound. Our analysis bridges the gaps in understanding trade-offs between estimation bias and variance in multivariate extreme value theory.

Authors
Xuhui Zhang, Jose Blanchet, Youssef Marzouk, Viet Anh Nguyen, Sven Wang
Publication date
2023/12/15
Journal
arXiv preprint arXiv:2312.09862

The goal of this paper is to develop a methodology for the systematic analysis of asymptotic statistical properties of data-driven DRO formulations based on their corresponding non-DRO counterparts. We illustrate our approach in various settings, including both phi-divergence and Wasserstein uncertainty sets. Different types of asymptotic behaviors are obtained depending on the rate at which the uncertainty radius decreases to zero as a function of the sample size and the geometry of the uncertainty sets.

Authors
Jose Blanchet, Alexander Shapiro
Publication date
2023/12/10
Conference
2023 Winter Simulation Conference (WSC)
Pages
31-45
Publisher
IEEE

We propose a new unbiased estimator for estimating the utility of the optimal stopping problem. The MUSE, short for ‘Multilevel Unbiased Stopping Estimator’, constructs the unbiased Multilevel Monte Carlo (MLMC) estimator at every stage of the optimal stopping problem in a backward recursive way. In contrast to traditional sequential methods, the MUSE can be implemented in parallel. We prove the MUSE has finite variance, finite computational complexity, and achieves ɛ-accuracy with O (1/ɛ 2) computational cost under mild conditions. We demonstrate MUSE empirically in an option pricing problem involving a high-dimensional input and the use of many parallel processors.

Authors
Zhengqing Zhou, Guanyang Wang, Jose H Blanchet, Peter W Glynn
Publication date
2023/12/1
Journal
Stochastic Processes and their Applications
Volume
166
Pages
104088
Publisher
North-Holland

Using data from cardiovascular surgery patients with long and highly variable post-surgical lengths of stay (LOS), we develop a modeling framework to reduce recovery unit congestion. We estimate the LOS and its probability distribution using machine learning models, schedule procedures on a rolling basis using a variety of optimization models, and estimate performance with simulation. The machine learning models achieved only modest LOS prediction accuracy, despite access to a very rich set of patient characteristics. Compared to the current paper-based system used in the hospital, most optimization models failed to reduce congestion without increasing wait times for surgery. A conservative stochastic optimization with sufficient sampling to capture the long tail of the LOS distribution outperformed the current manual process and other stochastic and robust optimization approaches. These results highlight …

Authors
Yuan Shi, Saied Mahdian, Jose Blanchet, Peter Glynn, Andrew Y Shin, David Scheinker
Publication date
2023/12
Journal
Health Care Management Science
Volume
26
Issue
4
Pages
692-718
Publisher
Springer US

Motivated by the need for a robust policy in the face of environment shifts between training and the deployment, we contribute to the theoretical foundation of distributionally robust reinforcement learning (DRRL). This is accomplished through a comprehensive modeling framework centered around distributionally robust Markov decision processes (DRMDPs). This framework obliges the decision maker to choose an optimal policy under the worst-case distributional shift orchestrated by an adversary. By unifying and extending existing formulations, we rigorously construct DRMDPs that embraces various modeling attributes for both the decision maker and the adversary. These attributes include adaptability granularity, exploring history-dependent, Markov, and Markov time-homogeneous decision maker and adversary dynamics. Additionally, we delve into the flexibility of shifts induced by the adversary, examining SA and S-rectangularity. Within this DRMDP framework, we investigate conditions for the existence or absence of the dynamic programming principle (DPP). From an algorithmic standpoint, the existence of DPP holds significant implications, as the vast majority of existing data and computationally efficiency RL algorithms are reliant on the DPP. To study its existence, we comprehensively examine combinations of controller and adversary attributes, providing streamlined proofs grounded in a unified methodology. We also offer counterexamples for settings in which a DPP with full generality is absent.

Authors
Shengbo Wang, Nian Si, Jose Blanchet, Zhengyuan Zhou
Publication date
2023/11/15
Journal
arXiv preprint arXiv:2311.09018

Extreme events are potentially catastrophic events that occur infrequently within an observation time frame, and it is necessary to understand the distribution of these events to properly plan for them. Extreme value theory provides a theoretical framework for extrapolating to the tails of a distribution using limited observations. However, for high-dimensional data such as images, covariates are generally not extreme but perhaps the features are extreme. In this work, we propose a framework for learning representations according to properties of extreme value theory. Specifically, we use the max-stability property of extreme value distributions to inform the representations of the model such that they extrapolate to the rare data observations. We theoretically characterize the properties of the model and provide an identifiability result for the parameters of the latent distribution. Our preliminary results suggest the promise of the method for extrapolating to regions of the distribution with little density.

Authors
Ali Hasan, Yuting Ng, Jose Blanchet, Vahid Tarokh
Conference
NeurIPS 2023 Workshop Heavy Tails in Machine Learning

We settle the sample complexity of policy learning for the maximization of the long run average reward associated with a uniformly ergodic Markov decision process (MDP), assuming a generative model. In this context, the existing literature provides a sample complexity upper bound of and a lower bound of . In these expressions, and denote the cardinalities of the state and action spaces respectively, serves as a uniform upper limit for the total variation mixing times, and signifies the error tolerance. Therefore, a notable gap of still remains to be bridged. Our primary contribution is to establish an estimator for the optimal policy of average reward MDPs with a sample complexity of , effectively reaching the lower bound in the literature. This is achieved by combining algorithmic ideas in Jin and Sidford (2021) with those of Li et al. (2020).

Authors
Shengbo Wang, Jose Blanchet, Peter Glynn
Publication date
2023/10/13
Journal
arXiv preprint arXiv:2310.08833

Policy learning using historical observational data are an important problem that has widespread applications. Examples include selecting offers, prices, or advertisements for consumers; choosing bids in contextual first-price auctions; and selecting medication based on patients’ characteristics. However, existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment that has generated the data: an assumption that is often false or too coarse an approximation. In this paper, we lift this assumption and aim to learn a distributionally robust policy with incomplete observational data. We first present a policy evaluation procedure that allows us to assess how well the policy does under worst-case environment shift. We then establish a central limit theorem type guarantee for this proposed policy evaluation scheme. Leveraging this …

Authors
Nian Si, Fan Zhang, Zhengyuan Zhou, Jose Blanchet
Publication date
2023/10
Journal
Management Science
Volume
69
Issue
10
Pages
5772-5793
Publisher
INFORMS

Among the reasons hindering the applications of reinforcement learning (RL) to real-world problems, two factors are critical: limited data and the mismatch between the test environment (real environment in which the policy is deployed) and the training environment (e.g., a simulator). This paper simultaneously addresses these issues with offline distributionally robust RL, where a distributionally robust policy is learned using historical data from the source environment by optimizing against a worst-case perturbation thereof. In particular, we move beyond tabular settings and design a novel linear function approximation framework that robustifies the latent space. Our framework is instantiated into two settings, one where the dataset is well-explored and the other where the dataset has weaker data coverage. In addition, we introduce a value shift algorithmic technique specifically designed to suit the distributionally robust nature, which contributes to our improved theoretical results and empirical performance. Sample complexities and are established respectively as the first non-asymptotic results in these settings, where denotes the dimension in the linear function space and represents the number of trajectories in the dataset. Diverse experiments are conducted to demonstrate our theoretical findings, showing the superiority of our algorithms against the non-robust one.

Authors
Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Mingwen Liu, Jiheng Zhang, Zhengyuan Zhou

We introduce a unified framework to estimate the convergence of Markov chains to equilibrium using Wasserstein distance. The framework provides convergence bounds with various rates, ranging from polynomial to exponential, all derived from a single contractive drift condition. This approach removes the need for finding a specific set with drift outside and contraction inside. The convergence bounds are explicit, as they can be estimated based on one-step expectations and do not rely on equilibrium-related quantities. To enhance the applicability of the framework, we introduce the large M technique and the boundary removal technique. We illustrate these methods in queueing models and algorithms in stochastic optimization.

Authors
Yanlin Qu, Jose Blanchet, Peter Glynn
Publication date
2023/8/20
Journal
arXiv preprint arXiv:2308.10341

In the past few years, there has been considerable interest in two prominent approaches for Distributionally Robust Optimization (DRO): Divergence-based and Wasserstein-based methods. The divergence approach models misspecification in terms of likelihood ratios, while the latter models it through a measure of distance or cost in actual outcomes. Building upon these advances, this paper introduces a novel approach that unifies these methods into a single framework based on optimal transport (OT) with conditional moment constraints. Our proposed approach, for example, makes it possible for optimal adversarial distributions to simultaneously perturb likelihood and outcomes, while producing an optimal (in an optimal transport sense) coupling between the baseline model and the adversarial model.Additionally, the paper investigates several duality results and presents tractable reformulations that enhance the practical applicability of this unified framework.

Authors
Jose Blanchet, Daniel Kuhn, Jiajin Li, Bahar Taskesen
Publication date
2023/8/10
Journal
arXiv preprint arXiv:2308.05414

Computational experiments are exploited in finding a well-designed processing path to optimize material structures for desired properties. This requires understanding the interplay between the processing-(micro)structure–property linkages using a multi-scale approach that connects the macro-scale (process parameters) to meso (homogenized properties) and micro (crystallographic texture) scales. Due to the nature of the problem’s multi-scale modeling setup, possible processing path choices could grow exponentially as the decision tree becomes deeper, and the traditional simulators’ speed reaches a critical computational threshold. To lessen the computational burden for predicting microstructural evolution under given loading conditions, we develop a neural network (NN)-based method with physics-infused constraints. The NN aims to learn the evolution of microstructures under each elementary process. Our …

Authors
Junrong Lin, Mahmudul Hasan, Pınar Acar, Jose Blanchet, Vahid Tarokh
Publication date
2023/8/1
Journal
Materials Today Communications
Volume
36
Pages
106884
Publisher
Elsevier

Perpetuities (i.e., random variables of the form D=∫0∞e−Γ(t−)dΛ(t)$$ D={\int}_0^{\infty }{e}^{-\Gamma \left(t-\right)}d\Lambda (t) $$ play an important role in many application settings. We develop approximations for the distribution of D$$ D $$ when the “accumulated short rate process”, Γ$$ \Gamma $$, is small. We provide: (1) characterizations for the distribution of D$$ D $$ when Γ$$ \Gamma $$ and Λ$$ \Lambda $$ are driven by Markov processes; (2) general sufficient conditions under which weak convergence results can be derived for D$$ D $$, and (3) Edgeworth expansions for the distribution of D$$ D $$ in the iid case and the case in which Λ$$ \Lambda $$ is a Levy process and the interest rate is a function of an ergodic Markov process.

Authors
Jose Blanchet, Peter Glynn
Publication date
2023/8
Journal
Naval Research Logistics (NRL)
Volume
70
Issue
5
Pages
454-471
Publisher
John Wiley & Sons, Inc.

Dynamic decision making under distributional shifts is of fundamental interest in theory and applications of reinforcement learning: The distribution of the environment on which the data is collected can differ from that of the environment on which the model is deployed. This paper presents two novel model-free algorithms, namely the distributionally robust Q-learning and its variance-reduced counterpart, that can effectively learn a robust policy despite distributional shifts. These algorithms are designed to efficiently approximate the -function of an infinite-horizon -discounted robust Markov decision process with Kullback-Leibler uncertainty set to an entry-wise -degree of precision. Further, the variance-reduced distributionally robust Q-learning combines the synchronous Q-learning with variance-reduction techniques to enhance its performance. Consequently, we establish that it attains a minmax sample complexity upper bound of , where and denote the state and action spaces. This is the first complexity result that is independent of the uncertainty size , thereby providing new complexity theoretic insights. Additionally, a series of numerical experiments confirm the theoretical findings and the efficiency of the algorithms in handling distributional shifts.

Authors
Shengbo Wang, Nian Si, Jose Blanchet, Zhengyuan Zhou
Publication date
2023/5/28
Journal
arXiv preprint arXiv:2305.18420

Some high-throughput experiments aim to test many samples simultaneously under nominally the same conditions. However, whether a particular high-throughput experiment does so must be certified. We previously described a high-throughput experiment to study the statistics of rupture stretch of materials. In such an experiment, a large set of samples were tested simultaneously. We noticed a systematic bias that samples in different subsets give different statistical distributions of rupture stretch. Here we describe an approach to detect and reduce systematic bias in the high-throughput experiment. We divide the whole set of the data of the experiment into subsets, obtain the statistical distribution of rupture stretches for each subset, and compare the “closeness” of the distributions among the pairs of subsets by using the Anderson-Darling (A-D) test. We then try to reduce the systematic bias by improving the …

Authors
Hou Wu, Xuhui Zhang, Yifan Zhou, Jose Blanchet, Zhigang Suo, Tongqing Lu
Publication date
2023/5/1
Journal
Journal of the Mechanics and Physics of Solids
Volume
174
Pages
105249
Publisher
Pergamon

We consider a reinforcement learning setting in which the deployment environment is different from the training environment. Applying a robust Markov decision processes formulation, we extend the distributionally robust Q-learning framework studied in [Liu et. al. 2022]. Further, we improve the design and analysis of their multi-level Monte Carlo estimator. Assuming access to a simulator, we prove that the worst-case expected sample complexity of our algorithm to learn the optimal robust Q-function within an error in the sup norm is upper bounded by , where is the discount rate, is the non-zero minimal support probability of the transition kernels and is the uncertainty size. This is the first sample complexity result for the model-free robust RL problem. Simulation studies further validate our theoretical results.

Authors
Shengbo Wang, Nian Si, Jose Blanchet, Zhengyuan Zhou
Publication date
2023/4/11
Conference
International Conference on Artificial Intelligence and Statistics
Pages
3370-3398
Publisher
PMLR

We focus on robust estimation of the unobserved state of a discrete-time stochastic system with linear dynamics. A standard analysis of this estimation problem assumes a baseline innovation model; with Gaussian innovations we recover the Kalman filter. However, in many settings, there is insufficient or corrupted data to validate the baseline model. To cope with this problem, we minimize the worst-case mean-squared estimation error of adversarial models chosen within a Wasserstein neighborhood around the baseline. We also constrain the adversarial innovations to form a martingale difference sequence. The martingale constraint relaxes the iid assumptions which are often imposed on the baseline model. Moreover, we show that the martingale constraints guarantee that the adversarial dynamics remain adapted to the natural time-generated information. Therefore, adding the martingale constraint allows to improve upon over-conservative policies that also protect against unrealistic omniscient adversaries. We establish a strong duality result which we use to develop an efficient subgradient method to compute the distributionally robust estimation policy. If the baseline innovations are Gaussian, we show that the worst-case adversary remains Gaussian. Our numerical experiments indicate that the martingale constraint may also aid in adding a layer of robustness in the choice of the adversarial power.

Authors
Kyriakos Lotidis, Nicholas Bambos, Jose Blanchet, Jiajin Li
Publication date
2023/4/11
Conference
International Conference on Artificial Intelligence and Statistics
Pages
8629-8644
Publisher
PMLR

The digital advertising industry heavily relies on online auctions, which are mostly of first-price type. For first-price auctions, the success of a good bidding algorithm crucially relies on accurately estimating the highest bid distribution based on historical data which is often censored. In practice, a sequence of first-price auctions often takes place through multiple layers, a feature that has been ignored in the literature on data-driven optimal bidding strategies. In this paper, we introduce a two-step algorithmic procedure specifically for this multi-layer first-price auction structure. Furthermore, to examine the performance of our procedure, we develop a novel inference scheme for A/B testing under budget interference (an experimental design which is also often used in practice). Our inference methodology uses a weighted local linear regression estimation to control for the interference incurred by the amount of spending in control/test groups given the budget constraint. Our bidding algorithm has been deployed in a major demand-side platform in the United States. Moreover, in such an industrial environment, our tests show that our bidding algorithm outperforms the benchmark algorithm by 0.5% to 1.5%.

Authors
Nian Si, San Gultekin, Jose Blanchet, Aaron Flores
Publication date
2023/3/19
Journal
Available at SSRN 4358914

In this work, we present the Bregman Alternating Projected Gradient (BAPG) method, a single-loop algorithm that offers an approximate solution to the Gromov-Wasserstein (GW) distance. We introduce a novel relaxation technique that balances accuracy and computational efficiency, albeit with some compromises in the feasibility of the coupling map. Our analysis is based on the observation that the GW problem satisfies the Luo-Tseng error bound condition, which relates to estimating the distance of a point to the critical point set of the GW problem based on the optimality residual. This observation allows us to provide an approximation bound for the distance between the fixed-point set of BAPG and the critical point set of GW. Moreover, under a mild technical assumption, we can show that BAPG converges to its fixed point set. The effectiveness of BAPG has been validated through comprehensive numerical experiments in graph alignment and partition tasks, where it outperforms existing methods in terms of both solution quality and wall-clock time.

Authors
Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, Jose Blanchet
Publication date
2023/3/12
Journal
arXiv preprint arXiv:2303.06595

We consider the optimal sample complexity theory of tabular reinforcement learning (RL) for maximizing the infinite horizon discounted reward in a Markov decision process (MDP). Optimal worst-case complexity results have been developed for tabular RL problems in this setting, leading to a sample complexity dependence on and of the form , where denotes the discount factor and is the solution error tolerance. However, in many applications of interest, the optimal policy (or all policies) induces mixing. We establish that in such settings, the optimal sample complexity dependence is , where is the total variation mixing time. Our analysis is grounded in regeneration-type ideas, which we believe are of independent interest, as they can be used to study RL problems for general state space MDPs.

Authors
Shengbo Wang, Jose Blanchet, Peter Glynn
Publication date
2023/2/15
Journal
arXiv preprint arXiv:2302.07477

The scarcity of labeled data is a long-standing challenge for many machine learning tasks. We propose our gradient flow method to leverage the existing dataset (i.e., source) to generate new samples that are close to the dataset of interest (i.e., target). We lift both datasets to the space of probability distributions on the feature-Gaussian manifold, and then develop a gradient flow method that minimizes the maximum mean discrepancy loss. To perform the gradient flow of distributions on the curved feature-Gaussian space, we unravel the Riemannian structure of the space and compute explicitly the Riemannian gradient of the loss function induced by the optimal transport metric. For practical applications, we also propose a discretized flow, and provide conditional results guaranteeing the global convergence of the flow to the optimum. We illustrate the results of our proposed gradient flow method on several real-world datasets and show our method can improve the accuracy of classification models in transfer learning settings.

Authors
Xinru Hua, Truyen Nguyen, Tam Le, Jose Blanchet, Viet Anh Nguyen
Publication date
2023/1/31
Journal
arXiv preprint arXiv:2302.00061

As a framework for sequential decision-making, Reinforcement Learning (RL) has been regarded as an essential component leading to Artificial General Intelligence (AGI). However, RL is often criticized for having the same training environment as the test one, which also hinders its application in the real world. To mitigate this problem, Distributionally Robust RL (DRRL) is proposed to improve the worst performance in a set of environments that may contain the unknown test environment. Due to the nonlinearity of the robustness goal, most of the previous work resort to the model-based approach, learning with either an empirical distribution learned from the data or a simulator that can be sampled infinitely, which limits their applications in simple dynamics environments. In contrast, we attempt to design a DRRL algorithm that can be trained along a single trajectory, i.e., no repeated sampling from a state. Based on the standard Q-learning, we propose distributionally robust Q-learning with the single trajectory (DRQ) and its average-reward variant named differential DRQ. We provide asymptotic convergence guarantees and experiments for both settings, demonstrating their superiority in the perturbed environments against the non-robust ones.

Authors
Zhipeng Liang, Xiaoteng Ma, Jose Blanchet, Jiheng Zhang, Zhengyuan Zhou
Publication date
2023/1/27
Journal
arXiv preprint arXiv:2301.11721

This panel discussion is designed to provide young scholars in the field of simulation with valuable insights into identifying suitable publication avenues for their research endeavors. Senior journal editors will serve as panelists and share their wealth of experience and perspectives. Journals represented include ACM TOMACS, IISE Transactions, INFORMS Journal on Computing, Journal of Simulation, Operations Research, and Stochastic Systems. Specifically, the panelists will introduce preferred topics, focuses, and future trends for each journal. Panelists will also share their own experiences and suggestions on the peer review process, such as how to navigate through revisions and rejections, and ethical policies. Young scholars will also learn the importance of serving the community as a reviewer, and what senior editors expect from reviewers.

Authors
Tom Berg, Jose Blanchet, Weiwei Chen, Christine SM Currie, Peter J Haas, L Jeff Hong, Bruno Tuffin, Jie Xu
Publication date
2023
Pages
1-4

Authors
Shengbo Wang, J Blanchet, P Glynn
Publication date
2023
Journal
CoRR

This paper shows that dropout training in generalized linear models is the minimax solution of a two-player, zero-sum game where an adversarial nature corrupts a statistician's covariates using a multiplicative nonparametric errors-in-variables model. In this game, nature's least favorable distribution is dropout noise, where nature independently deletes entries of the covariate vector with some fixed probability δ. This result implies that dropout training indeed provides out-of-sample expected loss guarantees for distributions that arise from multiplicative perturbations of in-sample data. The paper makes a concrete recommendation on how to select the tuning parameter δ. The paper also provides a novel, parallelizable, unbiased multi-level Monte Carlo algorithm to speed-up the implementation of dropout training. Our algorithm has a much smaller computational cost compared to the naive implementation of dropout, provided the number of data points is much smaller than the dimension of the covariate vector.

Authors
José Blanchet, Yang Kang, José Luis Montiel Olea, Viet Anh Nguyen, Xuhui Zhang
Publication date
2023
Journal
Journal of Machine Learning Research
Volume
24
Issue
180
Pages
1-60

We discuss rare event simulation techniques based on state-dependent importance sampling. Classical examples and counter-examples are shown to illustrate the reach and limitations of the state-independent approach. State-dependent techniques are helpful to deal with these limitations. These techniques can be applied to both light and heavy tailed systems and often are based on subsolutions to an associated Isaacs equation and on Lyapunov bounds.

Authors
Jose Blanchet, Henry Lam
Publication date
2011/12/11
Conference
Proceedings of the 2011 Winter Simulation Conference (WSC)
Pages
146-160
Publisher
IEEE

Modern neural networks are able to perform at least as well as humans in numerous tasks involving object classification and image generation. However, small perturbations which are imperceptible to humans may significantly degrade the performance of well-trained deep neural networks. We provide a Distributionally Robust Optimization (DRO) framework which integrates human-based image quality assessment methods to design optimal attacks that are imperceptible to humans but significantly damaging to deep neural networks. Through extensive experiments, we show that our attack algorithm generates better-quality (less perceptible to humans) attacks than other state-of-the-art human imperceptible attack methods. Moreover, we demonstrate that DRO training using our optimally designed human imperceptible attacks can improve group fairness in image classification. Towards the end, we provide an …

Authors
Xinru Hua, Huanzhong Xu, Jose Blanchet, Viet Anh Nguyen
Publication date
2022/12/11
Conference
2022 Winter Simulation Conference (WSC)
Pages
2641-2652
Publisher
IEEE

Distributionally robust optimization (DRO) has been shown to offer a principled way to regularize learning models. In this paper, we find that Tikhonov regularization is distributionally robust in an optimal transport sense (ie if an adversary chooses distributions in a suitable optimal transport neighborhood of the empirical measure), provided that suitable martingale constraints are also imposed. Further, we introduce a relaxation of the martingale constraints which not only provide a unified viewpoint to a class of existing robust methods but also lead to new regularization tools. To realize these novel tools, provably efficient computational algorithms are proposed. As a byproduct, the strong duality theorem proved in this paper can be potentially applied to other problems of independent interest.

Authors
Jiajin Li, Sirui Lin, José Blanchet, Viet Anh Nguyen
Publication date
2022/12/6
Journal
Advances in Neural Information Processing Systems
Volume
35
Pages
17677-17689

In this paper, we study the statistical limits in terms of Sobolev norms of gradient descent for solving inverse problem from randomly sampled noisy observations using a general class of objective functions. Our class of objective functions includes Sobolev training for kernel regression, Deep Ritz Methods (DRM), and Physics Informed Neural Networks (PINN) for solving elliptic partial differential equations (PDEs) as special cases. We consider a potentially infinite-dimensional parameterization of our model using a suitable Reproducing Kernel Hilbert Space and a continuous parameterization of problem hardness through the definition of kernel integral operators. We prove that gradient descent over this objective function can also achieve statistical optimality and the optimal number of passes over the data increases with sample size. Based on our theory, we explain an implicit acceleration of using a Sobolev norm as the objective function for training, inferring that the optimal number of epochs of DRM becomes larger than the number of PINN when both the data size and the hardness of tasks increase, although both DRM and PINN can achieve statistical optimality.

Authors
Yiping Lu, Jose Blanchet, Lexing Ying
Publication date
2022/12/6
Journal
Advances in Neural Information Processing Systems
Volume
35
Pages
33233-33247

We consider the unconstrained minimization of the function F, where F = f + g, f is an expectation-valued nonsmooth convex or strongly convex function, and g is a closed, convex, and proper function. (I) Strongly convex f. When f is μ-strongly convex in x, traditional stochastic subgradient schemes often display poor behavior, arising in part from noisy subgradients and diminishing steplengths. Instead, we apply a variable sample-size accelerated proximal scheme (VS-APM) on F, the Moreau envelope of F; we term such a scheme as and in contrast with schemes, utilizes constant steplengths and increasingly exact gradients. We consider two settings. (a) Bounded domains. In this setting, displays linear convergence in inexact gradient steps, each of which requires utilizing an inner scheme. Specically, achieves an optimal oracle complexity in steps of with an iteration complexity of in inexact (outer …

Authors
Afrooz Jalilzadeh, Uday Shanbhag, Jose Blanchet, Peter W Glynn
Publication date
2022/12
Journal
Stochastic Systems
Volume
12
Issue
4
Pages
373-410
Publisher
INFORMS

We develop an exact sampling algorithm for the all-time maximum of Gaussian processes with negative drift and general covariance structures. In particular, our algorithm can handle non-Markovian processes even with long-range dependence. Our development combines a milestone-event construction with rare-event simulation techniques. This allows us to find a random time beyond which the running time maximum will never be reached again. The complexity of the algorithm is random but has finite moments of all orders. We also test the performance of the algorithm numerically.

Authors
Jose Blanchet, Lin Chen, Jing Dong
Publication date
2022/12/1
Book
Advances in Modeling and Simulation: Festschrift for Pierre L'Ecuyer
Pages
41-63
Publisher
Springer International Publishing

The optimal design of experiments typically involves solving an NP-hard combinatorial optimization problem. In this paper, we aim to develop a globally convergent and practically efficient optimization algorithm. Specifically, we consider a setting where the pre-treatment outcome data is available and the synthetic control estimator is invoked. The average treatment effect is estimated via the difference between the weighted average outcomes of the treated and control units, where the weights are learned from the observed data. {Under this setting, we surprisingly observed that the optimal experimental design problem could be reduced to a so-called \textit{phase synchronization} problem.} We solve this problem via a normalized variant of the generalized power method with spectral initialization. On the theoretical side, we establish the first global optimality guarantee for experiment design when pre-treatment data is sampled from certain data-generating processes. Empirically, we conduct extensive experiments to demonstrate the effectiveness of our method on both the US Bureau of Labor Statistics and the Abadie-Diemond-Hainmueller California Smoking Data. In terms of the root mean square error, our algorithm surpasses the random design by a large margin.

Authors
Yiping Lu, Jiajin Li, Lexing Ying, Jose Blanchet
Publication date
2022/11/28
Journal
arXiv preprint arXiv:2211.15241

We consider a matching market where buyers and sellers arrive according to independent Poisson processes at the same rate and independently abandon the market if not matched after an exponential amount of time with the same mean. In this centralized market, the utility for the system manager from matching any buyer and any seller is a general random variable. We consider a sequence of systems indexed by n where the arrivals in the nth system are sped up by a factor of n. We analyze two families of one-parameter policies: the population threshold policy immediately matches an arriving agent to its best available mate only if the number of mates in the system is above a threshold, and the utility threshold policy matches an arriving agent to its best available mate only if the corresponding utility is above a threshold. Using an asymptotic fluid analysis of the two-dimensional Markov process of buyers and sellers …

Authors
Jose H Blanchet, Martin I Reiman, Virag Shah, Lawrence M Wein, Linjia Wu
Publication date
2022/11
Journal
Operations Research
Volume
70
Issue
6
Pages
3355-3370
Publisher
INFORMS

Learning mappings between infinite-dimensional function spaces have achieved empirical success in many disciplines of machine learning, including generative modeling, functional data analysis, causal inference, and multi-agent reinforcement learning. In this paper, we study the statistical limit of learning a Hilbert-Schmidt operator between two infinite-dimensional Sobolev reproducing kernel Hilbert spaces. We establish the information-theoretic lower bound in terms of the Sobolev Hilbert-Schmidt norm and show that a regularization that learns the spectral components below the bias contour and ignores the ones above the variance contour can achieve the optimal learning rate. At the same time, the spectral components between the bias and variance contours give us flexibility in designing computationally feasible machine learning algorithms. Based on this observation, we develop a multilevel kernel operator learning algorithm that is optimal when learning linear operators between infinite-dimensional function spaces.

Authors
Jikai Jin, Yiping Lu, Jose Blanchet, Lexing Ying
Publication date
2022/9/29
Conference
The Eleventh International Conference on Learning Representations

Among the reasons hindering reinforcement learning (RL) applications to real-world problems, two factors are critical: limited data and the mismatch between the testing environment (real environment in which the policy is deployed) and the training environment (e.g., a simulator). This paper attempts to address these issues simultaneously with distributionally robust offline RL, where we learn a distributionally robust policy using historical data obtained from the source environment by optimizing against a worst-case perturbation thereof. In particular, we move beyond tabular settings and consider linear function approximation. More specifically, we consider two settings, one where the dataset is well-explored and the other where the dataset has sufficient coverage of the optimal policy. We propose two algorithms~-- one for each of the two settings~-- that achieve error bounds and respectively, where is the dimension in the linear function approximation and is the number of trajectories in the dataset. To the best of our knowledge, they provide the first non-asymptotic results of the sample complexity in this setting. Diverse experiments are conducted to demonstrate our theoretical findings, showing the superiority of our algorithm against the non-robust one.

Authors
Xiaoteng Ma, Zhipeng Liang, Jose Blanchet, Mingwen Liu, Li Xia, Jiheng Zhang, Qianchuan Zhao, Zhengyuan Zhou
Publication date
2022/9/14
Journal
arXiv preprint arXiv:2209.06620

We propose a neural network architecture that enables non-parametric calibration and generation of multivariate extreme value distributions (MEVs). MEVs arise from Extreme Value Theory (EVT) as the necessary class of models when extrapolating a distributional fit over large spatial and temporal scales based on data observed in intermediate scales. In turn, EVT dictates that -max-decreasing, a stronger form of convexity, is an essential shape constraint in the characterization of MEVs. As far as we know, our proposed architecture provides the first class of non-parametric estimators for MEVs that preserve these essential shape constraints. We show that the architecture approximates the dependence structure encoded by MEVs at parametric rate. Moreover, we present a new method for sampling high-dimensional MEVs using a generative model. We demonstrate our methodology on a wide range of experimental settings, ranging from environmental sciences to financial mathematics and verify that the structural properties of MEVs are retained compared to existing methods.

Authors
Ali Hasan, Khalil Elkhalil, Yuting Ng, João M Pereira, Sina Farsiu, Jose Blanchet, Vahid Tarokh
Publication date
2022/8/17
Conference
Uncertainty in Artificial Intelligence
Pages
759-768
Publisher
PMLR

Reinforcement learning (RL) has demonstrated remarkable achievements in simulated environments. However, carrying this success to real environments requires the important attribute of robustness, which the existing RL algorithms often lack as they assume that the future deployment environment is the same as the training environment (ie simulator) in which the policy is learned. This assumption often does not hold due to the discrepancy between the simulator and the real environment and, as a result, and hence renders the learned policy fragile when deployed. In this paper, we propose a novel distributionally robust -learning algorithm that learns the best policy in the worst distributional perturbation of the environment. Our algorithm first transforms the infinite-dimensional learning problem (since the environment MDP perturbation lies in an infinite-dimensional space) into a finite-dimensional dual problem and subsequently uses a multi-level Monte-Carlo scheme to approximate the dual value using samples from the simulator. Despite the complexity, we show that the resulting distributionally robust -learning algorithm asymptotically converges to optimal worst-case policy, thus making it robust to future environment changes. Simulation results further demonstrate its strong empirical robustness.

Authors
Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, Zhengyuan Zhou
Publication date
2022/6/28
Conference
International Conference on Machine Learning
Pages
13623-13643
Publisher
PMLR

Estimators based on Wasserstein distributionally robust optimization are obtained as solutions of min-max problems in which the statistician selects a parameter minimizing the worst-case loss among all probability models within a certain distance from the underlying empirical measure in a Wasserstein sense. While motivated by the need to identify optimal model parameters or decision choices that are robust to model misspecification, these distributionally robust estimators recover a wide range of regularized estimators, including square-root lasso and support vector machines, among others. This paper studies the asymptotic normality of these distributionally robust estimators as well as the properties of an optimal confidence region induced by the Wasserstein distributionally robust optimization formulation. In addition, key properties of min-max distributionally robust optimization problems are also studied …

Authors: Jose Blanchet, Karthyek Murthy, Nian Si
Publication date: 2022/6/1
Journal: Biometrika
Volume: 109
Issue: 2
Pages: 295-315
Publisher: Oxford University Press

We study a distributionally robust optimization formulation (i.e., a min-max game) for two representative problems in Bayesian nonparametric estimation: Gaussian process regression and, more generally, linear inverse problems. Our formulation seeks the best mean-squared error predictor, in an infinite-dimensional space, against an adversary who chooses the worst-case model in a Wasserstein ball around a nominal infinite-dimensional Bayesian model. The transport cost is chosen to control features such as the degree of roughness of the sample paths that the adversary is allowed to inject. We show that the game has a well-defined value (i.e., strong duality holds in the sense that max-min equals min-max) and that there exists a unique Nash equilibrium which can be computed by a sequence of finite-dimensional approximations. Crucially, the worst-case distribution is itself Gaussian. We explore properties of the Nash equilibrium and the effects of hyperparameters through a set of numerical experiments, demonstrating the versatility of our modeling framework.

Authors
Xuhui Zhang, Jose Blanchet, Youssef Marzouk, Viet Anh Nguyen, Sven Wang
Publication date
2022/5/26
Journal
arXiv preprint arXiv:2205.13111

In this paper, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition~\citep{luo1992error}, two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) enjoy the convergence guarantees. Upon task-specific properties, our analysis further provides novel theoretical insights to guide how to select the best-fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.

Authors
Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, Jose Blanchet
Publication date
2022/5/17
Journal
arXiv preprint arXiv:2205.08115

We consider optimal transport-based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded in the DRO problem (e.g., strong convexity even if the non-DRO problem is not strongly convex, a suitable scaling of the Lagrangian for the DRO constraint, etc., which are crucial for the design of efficient algorithms). As a consequence of these results, one can develop efficient optimization procedures that have the same sample and iteration complexity as a natural non-DRO benchmark algorithm, such as stochastic gradient descent.

Authors: Jose Blanchet, Karthyek Murthy, Fan Zhang
Publication date: 2022/5
Journal: Mathematics of Operations Research
Volume: 47
Issue: 2
Pages: 1500-1529
Publisher: INFORMS

We study the problem of transfer learning, observing that previous efforts to understand its information-theoretic limits do not fully exploit the geometric structure of the source and target domains. In contrast, our study first illustrates the benefits of incorporating a natural geometric structure within a linear regression model, which corresponds to the generalized eigenvalue problem formed by the Gram matrices of both domains. We next establish a finite-sample minimax lower bound, propose a refined model interpolation estimator that enjoys a matching upper bound, and then extend our framework to multiple source domains and generalized linear models. Surprisingly, as long as information is available on the distance between the source and target parameters, negative-transfer does not occur. Simulation studies show that our proposed interpolation estimator outperforms state-of-the-art transfer learning methods in both moderate-and high-dimensional settings.

Authors
Xuhui Zhang, Jose Blanchet, Soumyadip Ghosh, Mark S Squillante
Publication date
2022/5/3
Conference
International Conference on Artificial Intelligence and Statistics
Pages
3794-3820
Publisher
PMLR

The first algorithm for exact sampling of SDEs in appeared in [2], under suitable boundedness assumptions. These assumptions were significantly weakened in [1] and further relaxed using a localization technique in [6], but using essentially the same sampling strategy as in [2]. The overall strategy in [2] relies on two essential properties which are non-restrictive in, but are very restrictive in the multidimensional setting. The first is the existence of an invertible transformation (ie, the Lamperti transformation) which, when applied to the process, results in a diffusion process with a constant diffusion matrix. Moreover, after this transformation is performed, the resulting drift coefficient of the transformed diffusion must be of gradient form.

Authors
Jose H Blanchet
Publication date
2022/4
Journal
Queueing Systems
Volume
100
Issue
3
Pages
509-511
Publisher
Springer US
Description
2 Discussion

We study large deviations asymptotics for a class of unbounded additive functionals, interpreted as normalized accumulated areas, of one-dimensional Langevin diffusions with sub-linear gradient drifts. Our results provide parametric insights on the speed and the rate functions in terms of the growth rate of the drift and the growth rate of the additive functional. We find a critical value in terms of these growth parameters that dictates regions of sub-linear speed for our large deviations asymptotics. Our approach is based upon various constructions of independent interest, including a decomposition of the diffusion process in terms of alternating renewal cycles and a detailed analysis of the paths during a cycle using suitable time and spatial scales. The key to the sub-linear behavior is a heavy-tailed large deviations phenomenon arising from the principle of a single big jump coupled with the result that at each regeneration cycle the upper-tail asymptotic behavior of the accumulated area of the diffusion process is proven to be semi-exponential (i.e., of heavy-tailed Weibull type).

Authors
Mihail Bazhba, Jose Blanchet, Roger JA Laeven, Bert Zwart
Publication date
2022/2/22
Journal
arXiv preprint arXiv:2202.10799

Using data from cardiovascular surgery patients with long and highly variable post-surgical lengths of stay (LOS), we develop a modeling framework to reduce recovery unit congestion. We estimate the LOS and its probability distribution using machine learning models, schedule procedures on a rolling basis using a variety of optimization models, and estimate performance with simulation. The machine learning models achieved only modest LOS prediction accuracy, despite access to a very rich set of patient characteristics. Compared to the current paper-based system used in the hospital, most optimization models failed to reduce congestion without increasing wait times for surgery. A conservative stochastic optimization with sufficient sampling to capture the long tail of the LOS distribution outperformed the current manual process and other stochastic and robust optimization approaches. These results highlight the perils of using oversimplified distributional models of LOS for scheduling procedures and the importance of using optimization methods well-suited to dealing with long-tailed behavior.

Authors
Yuan Shi, Saied Mahdian, Jose Blanchet, Peter Glynn, Andrew Y Shin, David Scheinker
Publication date
2022/2/13
Journal
arXiv preprint arXiv:2202.06383

The conditions for rupture of a material commonly vary from sample to sample. Of great importance to applications are the conditions for rare-event rupture, but their measurements require many samples and consume much time. Here, the conditions for rare-event rupture are measured by developing a high-throughput experiment. For each run of the experiment, 1,000 samples are printed under the same nominal conditions and pulled simultaneously to the same stretch. Identifying the rupture of individual samples is automated by processing the video of the experiment. Under monotonic load, the rupture stretch for each sample is recorded. Under cyclic load, the number of cycles to rupture for each sample is also recorded. Rare-event rupture is studied by using the Weibull distribution and the peak-over-threshold method. This work reaffirms that predicting rare events requires large datasets. The high-throughput …

Authors
Yifan Zhou, Xuhui Zhang, Meng Yang, Yudong Pan, Zhenjiang Du, Jose Blanchet, Zhigang Suo, Tongqing Lu
Publication date
2022/2/2
Journal
Matter
Volume
5
Issue
2
Pages
654-665
Publisher
Elsevier

Missing time-series data is a prevalent problem in many prescriptive analytics models in operations management, healthcare and finance. Imputation methods for time-series data are usually applied to the full panel data with the purpose of training a prescriptive model for a downstream out-of-sample task. For example, the imputation of missing asset returns may be applied before estimating an optimal portfolio allocation. However, this practice can result in a look-ahead-bias in the future performance of the downstream task, and there is an inherent trade-off between the look-ahead-bias of using the entire data set for imputation and the larger variance of using only the training portion of the data set for imputation. By connecting layers of information revealed in time, we propose a Bayesian consensus posterior that fuses an arbitrary number of posteriors to optimize the variance and look-ahead-bias trade-off in the imputation. We derive tractable two-step optimization procedures for finding the optimal consensus posterior, with Kullback-Leibler divergence and Wasserstein distance as the dissimilarity measure between posterior distributions. We demonstrate in simulations and in an empirical study the benefit of our imputation mechanism for portfolio allocation with missing returns.

Authors
Jose Blanchet, Fernando Hernandez, Viet Anh Nguyen, Markus Pelger, Xuhui Zhang
Publication date
2022/2/2
Journal
arXiv preprint arXiv:2202.00871

Consider a scenario where a player chooses an action in each round t out of T rounds and observes the incurred cost after a delay of dt rounds. The cost functions and the delay sequence are chosen by an adversary. We show that in a non-cooperative game, the expected weighted ergodic distribution of play converges to the set of coarse correlated equilibria if players use algorithms that have "no weighted-regret" in the above scenario, even if they have linear regret due to too large delays. For a two-player zero-sum game, we show that no weighted-regret is sufficient for the weighted ergodic average of play to converge to the set of Nash equilibria. We prove that the FKM algorithm with n dimensions achieves an expected regret of and the EXP3 algorithm with K arms achieves an expected regret of even when D = ΣTt=1 dt and T are unknown. These bounds use a novel doubling trick that, under mild assumptions, provably retains the regret bound for when D and T are known. Using these bounds, we show that FKM and EXP3 have no weighted-regret even for dt = O (t log t). Therefore, algorithms with no weighted-regret can be used to approximate a CCE of a finite or convex unknown game that can only be simulated with bandit feedback, even if the simulation involves significant delays.

Authors
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, Jose Blanchet
Publication date
2022
Journal
Journal of Machine Learning Research
Volume
23
Issue
139
Pages
1-43

In this paper, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition (Luo & Tseng, 1992), two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) are proven to be (linearly) convergent. Upon taskspecific properties, our analysis further provides novel theoretical insights to guide how to select the best fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.

Authors
Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, Jose Blanchet
Publication date
2022
Journal
arXiv preprint arXiv:2205.08115

Authors
Taoli Zheng, Linglingzhi Zhu, Anthony Man-Cho So, Jose Blanchet, Jiajin Li
Publication date
2022
Journal
arXiv preprint arXiv:2212.12978

We revisit Markowitz’s mean-variance portfolio selection model by considering a distributionally robust version, in which the region of distributional uncertainty is around the empirical measure and the discrepancy between probability measures is dictated by the Wasserstein distance. We reduce this problem into an empirical variance minimization problem with an additional regularization term. Moreover, we extend the recently developed inference methodology to our setting in order to select the size of the distributional uncertainty as well as the associated robust target return rate in a data-driven way. Finally, we report extensive back-testing results on S&P 500 that compare the performance of our model with those of several well-known models including the Fama–French and Black–Litterman models.

Authors: Jose Blanchet, Lin Chen, Xun Yu Zhou
Publication date: 2022/9
Journal: Management Science
Volume: 68
Issue: 9
Pages: 6382-6410
Publisher: INFORMS

We build a data-driven methodology for the performance reliability and the improvement of sensor algorithms for automated driving perception tasks. The methodology takes as input three elements: I) one or various algorithms for object detection when the input is an image; II) a dataset of camera images that represents a sample from an environment, and III) a simple policy that serves as a proxy for a task such as driving assistance. We develop a statistical estimator, which combines I)-III) and a data augmentation technique, in order to rank the reliability of perception algorithms. Reliability is measured as the chance of collision given the speed of the ego vehicle and the distance to the closest object in range. We are able to compare algorithms in the (speed vs distance-to-closest-object) space using p-values and use this information to suggest improved-safety algorithms.

Authors
Huanzhong Xu, Jose Blanchet, Marcos Paul Gerardo-Castro, Shreyasha Paudel
Publication date
2021/12/12
Conference
2021 Winter Simulation Conference (WSC)
Pages
1-12
Publisher
IEEE

Many machine learning tasks that involve predicting an output response can be solved by training a weighted regression model. Unfortunately, the predictive power of this type of models may severely deteriorate under low sample sizes or under covariate perturbations. Reweighting the training samples has aroused as an effective mitigation strategy to these problems. In this paper, we propose a novel and coherent scheme for kernel-reweighted regression by reparametrizing the sample weights using a doubly non-negative matrix. When the weighting matrix is confined in an uncertainty set using either the log-determinant divergence or the Bures-Wasserstein distance, we show that the adversarially reweighted estimate can be solved efficiently using first-order methods. Numerical experiments show that our reweighting strategy delivers promising results on numerous datasets.

Authors
Tam Le, Truyen Nguyen, Makoto Yamada, Jose Blanchet, Viet Anh Nguyen
Publication date
2021/12/6
Journal
Advances in Neural Information Processing Systems
Volume
34
Pages
16964-16976

We propose a novel Frank-Wolfe (FW) procedure for the optimization of infinite-dimensional functionals of probability measures-a task which arises naturally in a wide range of areas including statistical learning (eg variational inference) and artificial intelligence (eg generative adversarial networks). Our FW procedure takes advantage of Wasserstein gradient flows and strong duality results recently developed in Distributionally Robust Optimization so that gradient steps (in the Wasserstein space) can be efficiently computed using finite-dimensional, convex optimization methods. We show how to choose the step sizes in order to guarantee exponentially fast iteration convergence, under mild assumptions on the functional to optimize. We apply our algorithm to a range of functionals arising from applications in nonparametric estimation.

Authors
Carson Kent, Jiajin Li, Jose Blanchet, Peter W Glynn
Publication date
2021/12/6
Journal
Advances in Neural Information Processing Systems
Volume
34
Pages
14448-14462

In this paper, we study the statistical limits of deep learning techniques for solving elliptic partial differential equations (PDEs) from random samples using the Deep Ritz Method (DRM) and Physics-Informed Neural Networks (PINNs). To simplify the problem, we focus on a prototype elliptic PDE: the Schr\"odinger equation on a hypercube with zero Dirichlet boundary condition, which is applied in quantum-mechanical systems. We establish upper and lower bounds for both methods, which improve upon concurrently developed upper bounds for this problem via a fast rate generalization bound. We discover that the current Deep Ritz Method is sub-optimal and propose a modified version of it. We also prove that PINN and the modified version of DRM can achieve minimax optimal bounds over Sobolev spaces. Empirically, following recent work which has shown that the deep model accuracy will improve with growing training sets according to a power law, we supply computational experiments to show similar-behavior of dimension dependent power law for deep PDE solvers.

Authors
Yiping Lu, Haoxuan Chen, Jianfeng Lu, Lexing Ying, Jose Blanchet
Conference
The Symbiosis of Deep Learning and Differential Equations

In this paper, we study the statistical limits of deep learning techniques for solving elliptic partial differential equations (PDEs) from random samples using the Deep Ritz Method (DRM) and Physics-Informed Neural Networks (PINNs). To simplify the problem, we focus on a prototype elliptic PDE: the Schr\"odinger equation on a hypercube with zero Dirichlet boundary condition, which has wide application in the quantum-mechanical systems. We establish upper and lower bounds for both methods, which improves upon concurrently developed upper bounds for this problem via a fast rate generalization bound. We discover that the current Deep Ritz Methods is sub-optimal and propose a modified version of it. We also prove that PINN and the modified version of DRM can achieve minimax optimal bounds over Sobolev spaces. Empirically, following recent work which has shown that the deep model accuracy will improve with growing training sets according to a power law, we supply computational experiments to show a similar behavior of dimension dependent power law for deep PDE solvers.

Authors
Yiping Lu, Haoxuan Chen, Jianfeng Lu, Lexing Ying, Jose Blanchet
Publication date
2021/10/13
Journal
arXiv preprint arXiv:2110.06897

We consider statistical methods that invoke a min-max distributionally robust formulation to extract good out-of-sample performance in data-driven optimization and learning problems. Acknowledging the distributional uncertainty in learning from limited samples, the min-max formulations introduce an adversarial inner player to explore unseen covariate data. The resulting distributionally robust optimization (DRO) formulations, which include Wasserstein DRO formulations (our main focus), are specified using optimal transportation phenomena. Upon describing how these infinite-dimensional min-max problems can be approached via a finite-dimensional dual reformulation, this tutorial moves into its main component, namely, explaining a generic recipe for optimally selecting the size of the adversary’s budget. This is achieved by studying the limit behavior of an optimal transport projection formulation arising from an …

Authors
Jose Blanchet, Karthyek Murthy, Viet Anh Nguyen
Publication date
2021/10
Book
Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications
Pages
227-254
Publisher
INFORMS

The scarcity of labeled data is a long-standing challenge for cross-domain machine learning tasks. This paper leverages the existing dataset (i.e., source) to augment new samples that are close to the dataset of interest (i.e., target). To relieve the need to learn a metric on the feature-label space, we lift both datasets to the space of probability distributions on the feature-Gaussian manifold, and then develop a gradient flow that minimizes the maximum mean discrepancy loss. To perform the gradient flow of distributions on the curved feature-Gaussian space, we unravel the Riemannian structure of the space and compute explicitly the Riemannian gradient of the loss function induced by the optimal transport metric. For practical purposes, we also propose a discretized flow, and provide conditional results guaranteeing the global convergence of the flow to the optimum. We illustrate the results of our proposed gradient flow method in several real-world datasets.

Authors
Truyen Nguyen, Xinru Hua, Tam Le, Jose Blanchet, Viet Anh Nguyen

Least squares estimators, when trained on few target domain samples, may predict poorly. Supervised domain adaptation aims to improve the predictive accuracy by exploiting additional labeled training samples from a source distribution that is close to the target distribution. Given available data, we investigate novel strategies to synthesize a family of least squares estimator experts that are robust with regard to moment conditions. When these moment conditions are specified using Kullback-Leibler or Wasserstein-type divergences, we can find the robust estimators efficiently using convex optimization. We use the Bernstein online aggregation algorithm on the proposed family of robust experts to generate predictions for the sequential stream of target test samples. Numerical experiments on real data show that the robust strategies systematically outperform non-robust interpolations of the empirical least squares estimators.

Authors
Bahar Taskesen, Man-Chung Yue, Jose Blanchet, Daniel Kuhn, Viet Anh Nguyen
Publication date
2021/7/1
Conference
International Conference on Machine Learning
Pages
10162-10172
Publisher
PMLR

We have developed a statistical testing framework to detect if a given machine learning classifier fails to satisfy a wide range of group fairness notions. Our test is a flexible, interpretable, and statistically rigorous tool for auditing whether exhibited biases are intrinsic to the algorithm or simply due to the randomness in the data. The statistical challenges, which may arise from multiple impact criteria that define group fairness and which are discontinuous on model parameters, are conveniently tackled by projecting the empirical measure to the set of group-fair probability models using optimal transport. This statistic is efficiently computed using linear programming, and its asymptotic distribution is explicitly obtained. The proposed framework can also be used to test for composite fairness hypotheses and fairness with multiple sensitive attributes. The optimal transport testing formulation improves interpretability by characterizing the minimal covariate perturbations that eliminate the bias observed in the audit.

Authors
Nian Si, Karthyek Murthy, Jose Blanchet, Viet Anh Nguyen
Publication date
2021/7/1
Conference
International Conference on Machine Learning
Pages
9649-9659
Publisher
PMLR

We study the problem of bounding path-dependent expectations (within any finite time horizon ) over the class of discrete-time martingales whose marginal distributions lie within a prescribed tolerance of a given collection of benchmark marginal distributions. This problem is a relaxation of the martingale optimal transport (MOT) problem and is motivated by applications to super-hedging in financial markets. We show that the empirical version of our relaxed MOT problem can be approximated within error where is the number of samples of each of the individual marginal distributions (generated independently) and using a suitably constructed finite-dimensional linear programming problem.

Authors
Zhengqing Zhou, Jose Blanchet, Peter W Glynn
Publication date
2021/6/14
Journal
arXiv preprint arXiv:2106.07191

We propose and study an asymptotically optimal Monte Carlo estimator for steady-state expectations of a d-dimensional reflected Brownian motion (RBM). Our estimator is asymptotically optimal in the sense that it requires (up to logarithmic factors in d) independent and identically distributed scalar Gaussian random variables in order to output an estimate with a controlled error. Our construction is based on the analysis of a suitable multilevel Monte Carlo strategy which, we believe, can be applied widely. This is the first algorithm with linear complexity (under suitable regularity conditions) for a steady-state estimation of RBM as the dimension increases.

Authors
Jose Blanchet, Xinyun Chen, Nian Si, Peter W Glynn
Publication date
2021/6
Journal
Stochastic Systems
Volume
11
Issue
2
Pages
174-192
Publisher
INFORMS

We introduce a new class of Frank-Wolfe algorithms for minimizing differentiable functionals over probability measures. This framework can be shown to encompass a diverse range of tasks in areas such as artificial intelligence, reinforcement learning, and optimization. Concrete computational complexities for these algorithms are established and demonstrate that these methods enjoy convergence in regimes that go beyond convexity and require minimal regularity of the underlying functional. Novel techniques used to obtain these results also lead to the development of new complexity bounds and duality theorems for a family of distributionally robust optimization problems. The performance of our method is demonstrated on several nonparametric estimation problems.

Authors
Carson Kent, Jose Blanchet, Peter Glynn
Publication date
2021/5/11
Journal
arXiv preprint arXiv:2105.05352

We present a novel inference approach that we call sample out-of-sample inference. The approach can be used widely, ranging from semisupervised learning to stress testing, and it is fundamental in the application of data-driven distributionally robust optimization. Our method enables measuring the impact of plausible out-of-sample scenarios in a given performance measure of interest, such as a financial loss. The methodology is inspired by empirical likelihood (EL), but we optimize the empirical Wasserstein distance (instead of the empirical likelihood) induced by observations. From a methodological standpoint, our analysis of the asymptotic behavior of the induced Wasserstein-distance profile function shows dramatic qualitative differences relative to EL. For instance, in contrast to EL, which typically yields chi-squared weak convergence limits, our asymptotic distributions are often not chi-squared. Also, the …

Authors
Jose Blanchet, Yang Kang
Publication date
2021/5
Journal
Operations Research
Volume
69
Issue
3
Pages
985-1013
Publisher
INFORMS

We propose a data-driven portfolio selection model that integrates side information, conditional estimation and robustness using the framework of distributionally robust optimization. Conditioning on the observed side information, the portfolio manager solves an allocation problem that minimizes the worst-case conditional risk-return trade-off, subject to all possible perturbations of the covariate-return probability distribution in an optimal transport ambiguity set. Despite the non-linearity of the objective function in the probability measure, we show that the distributionally robust portfolio allocation with side information problem can be reformulated as a finite-dimensional optimization problem. If portfolio decisions are made based on either the mean-variance or the mean-Conditional Value-at-Risk criterion, the resulting reformulation can be further simplified to second-order or semi-definite cone programs. Empirical studies in the US equity market demonstrate the advantage of our integrative framework against other benchmarks.

Authors
Viet Anh Nguyen, Fan Zhang, Jose Blanchet, Erick Delage, Yinyu Ye
Publication date
2021/3/30
Journal
arXiv preprint arXiv:2103.16451

While reinforcement learning has witnessed tremendous success recently in a wide range of domains, robustness–or the lack thereof–remains an important issue that remains inadequately addressed. In this paper, we provide a distributionally robust formulation of offline learning policy in tabular RL that aims to learn a policy from historical data (collected by some other behavior policy) that is robust to the future environment arising as a perturbation of the training environment. We first develop a novel policy evaluation scheme that accurately estimates the robust value (ie how robust it is in a perturbed environment) of any given policy and establish its finite-sample estimation error. Building on this, we then develop a novel and minimax-optimal distributionally robust learning algorithm that achieves regret, meaning that with high probability, the policy learned from using training data points will be close to the optimal distributionally robust policy. Finally, our simulation results demonstrate the superiority of our distributionally robust approach compared to non-robust RL algorithms.

Authors: Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, Peter Glynn
Publication date: 2021/3/18
Conference: International Conference on Artificial Intelligence and Statistics
Pages: 3331-3339
Publisher: PMLR

Algorithms are now routinely used to make consequential decisions that affect human lives. Examples include college admissions, medical interventions or law enforcement. While algorithms empower us to harness all information hidden in vast amounts of data, they may inadvertently amplify existing biases in the available datasets. This concern has sparked increasing interest in fair machine learning, which aims to quantify and mitigate algorithmic discrimination. Indeed, machine learning models should undergo intensive tests to detect algorithmic biases before being deployed at scale. In this paper, we use ideas from the theory of optimal transport to propose a statistical hypothesis test for detecting unfair classifiers. Leveraging the geometry of the feature space, the test statistic quantifies the distance of the empirical distribution supported on the test samples to the manifold of distributions that render a pre-trained …

Authors
Bahar Taskesen, Jose Blanchet, Daniel Kuhn, Viet Anh Nguyen
Publication date
2021/3/3
Book
Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency
Pages
648-665

Consider a player that in each round t out of T rounds chooses an action and observes the incurred cost after a delay of dt rounds. The cost functions and the delay sequence are chosen by an adversary. We show that even if the players’ algorithms lose their” no regret” property due to too large delays, the expected discounted ergodic distribution of play converges to the set of coarse correlated equilibrium (CCE) if the algorithms have “no discounted-regret”. For a zero-sum game, we show that no discounted-regret is sufficient for the discounted ergodic average of play to converge to the set of Nash equilibria. We prove that the FKM algorithm with n dimensions achieves a regret of O (nT 3 4+/nT 1 3 D 1 3) and the EXP3 algorithm with K arms achieves a regret of O (√ ln K (KT+ D)) even when D=∑ T t= 1 dt and T are unknown. These bounds use a novel doubling trick that provably retains the regret bound for when D and T are known. Using these bounds, we show that EXP3 and FKM have no discounted-regret even for dt= O (t log t). Therefore, the CCE of a finite or convex unknown game can be approximated even when only delayed bandit feedback is available via simulation.

Authors
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, Jose Blanchet
Publication date
2021/3
Journal
arXiv preprint arXiv:2103.04550

Missing time-series data is a prevalent practical problem. Imputation methods in time-series data often are applied to the full panel data with the purpose of training a model for a downstream out-of-sample task. For example, in finance, imputation of missing returns may be applied prior to training a portfolio optimization model. Unfortunately, this practice may result in a look-ahead-bias in the future performance on the downstream task. There is an inherent trade-off between the look-ahead-bias of using the full data set for imputation and the larger variance in the imputation from using only the training data. By connecting layers of information revealed in time, we propose a Bayesian posterior consensus distribution which optimally controls the variance and look-ahead-bias trade-off in the imputation. We demonstrate the benefit of our methodology both in synthetic and real financial data.

Authors
Jose Blanchet, Fernando Hernandez, Viet Anh Nguyen, Markus Pelger, Xuhui Zhang
Publication date
2021/2/25
Journal
arXiv preprint arXiv:2102.12736

Authors
Ali Hasan, Khalil Elkhalil, João M Pereira, Sina Farsiu, Jose H Blanchet, Vahid Tarokh
Publication date
2021
Journal
CoRR

Optimal transport costs (e.g. Wasserstein distances) are used for fitting high-dimensional distributions. For example, popular artificial intelligence algorithms such as Wasserstein Generative Adversarial Networks (WGANs) can be interpreted as fitting a black-box simulator of structured data with certain features (e.g. images) using the Wasserstein distance. We propose a regularization of optimal transport costs and study its computational and duality properties. We obtain running time improvements for fitting WGANs with no deterioration in testing performance, relative to current benchmarks. We also derive finite sample bounds for the empirical Wasserstein distance from our regularization.

Authors
Saied Mahdian, Jose H Blanchet, Peter W Glynn
Publication date
2020/12/14
Conference
2020 Winter Simulation Conference (WSC)
Pages
433-444
Publisher
IEEE

We study sample path large deviations for Lévy processes and random walks with heavy-tailed jump-size distributions that are of Weibull type. The sharpness and applicability of these results are illustrated by a counterexample proving the nonexistence of a full LDP in the topology, and by an application to a first passage problem.

Authors
Mihail Bazhba, Jose Blanchet, Chang-Han Rhee, Bert Zwart
Publication date
2020/12/1
Volume
30
Issue
6
Pages
2695-2739

We provide the first generic exact simulation algorithm for multivariate diffusions. Current exact sampling algorithms for diffusions require the existence of a transformation which can be used to reduce the sampling problem to the case of a constant diffusion matrix and a drift which is the gradient of some function. Such a transformation, called the Lamperti transformation, can be applied in general only in one dimension. So, completely different ideas are required for the exact sampling of generic multivariate diffusions. The development of these ideas is the main contribution of this paper. Our strategy combines techniques borrowed from the theory of rough paths, on the one hand, and multilevel Monte Carlo on the other.

Authors
Jose Blanchet, Fan Zhang
Publication date
2020/12
Journal
Advances in Applied Probability
Volume
52
Issue
4
Pages
1003-1034
Publisher
Cambridge University Press

We build a Bayesian contextual classification model using an optimistic score ratio for robust binary classification when there is limited information on the class-conditional, or contextual, distribution. The optimistic score searches for the distribution that is most plausible to explain the observed outcomes in the testing sample among all distributions belonging to the contextual ambiguity set which is prescribed using a limited structural constraint on the mean vector and the covariance matrix of the underlying contextual distribution. We show that the Bayesian classifier using the optimistic score ratio is conceptually attractive, delivers solid statistical guarantees and is computationally tractable. We showcase the power of the proposed optimistic score ratio classifier on both synthetic and empirical data.

Authors
Viet Anh Nguyen, Nian Si, Jose Blanchet
Publication date
2020/11/21
Conference
International Conference on Machine Learning
Pages
7327-7337
Publisher
PMLR

Policy learning using historical observational data is an important problem that has found widespread applications. However, existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment that has generated the data {–} an assumption that is often false or too coarse an approximation. In this paper, we lift this assumption and aim to learn a distributionally robust policy with bandit observational data. We propose a novel learning algorithm that is able to learn a robust policy to adversarial perturbations and unknown covariate shifts. We first present a policy evaluation procedure in the ambiguous environment and also give a heuristic algorithm to solve the distributionally robust policy learning problems efficiently. Additionally, we provide extensive simulations to demonstrate the robustness of our policy.

Authors
Nian Si, Fan Zhang, Zhengyuan Zhou, Jose Blanchet
Publication date
2020/11/21
Conference
International Conference on Machine Learning
Pages
8884-8894
Publisher
PMLR

This paper shows that dropout training in Generalized Linear Models is the minimax solution of a two-player, zero-sum game where an adversarial nature corrupts a statistician's covariates using a multiplicative nonparametric errors-in-variables model. In this game, nature's least favorable distribution is dropout noise, where nature independently deletes entries of the covariate vector with some fixed probability . This result implies that dropout training indeed provides out-of-sample expected loss guarantees for distributions that arise from multiplicative perturbations of in-sample data. In addition to the decision-theoretic analysis, the paper makes two more contributions. First, there is a concrete recommendation on how to select the tuning parameter to guarantee that, as the sample size grows large, the in-sample loss after dropout training exceeds the true population loss with some pre-specified probability. Second, the paper provides a novel, parallelizable, Unbiased Multi-Level Monte Carlo algorithm to speed-up the implementation of dropout training. Our algorithm has a much smaller computational cost compared to the naive implementation of dropout, provided the number of data points is much smaller than the dimension of the covariate vector.

Authors
José Blanchet, Yang Kang, José Luis Montiel Olea, Viet Anh Nguyen, Xuhui Zhang
Publication date
2020/9/13
Journal
arXiv preprint arXiv:2009.06111

We study distributional robustness in the context of Extreme Value Theory (EVT). We provide a data-driven method for estimating extreme quantiles in a manner that is robust against incorrect model assumptions underlying the application of the standard Extremal Types Theorem. Typical studies in distributional robustness involve computing worst case estimates over a model uncertainty region expressed in terms of the Kullback-Leibler discrepancy. We go beyond standard distributional robustness in that we investigate different forms of discrepancies, and prove rigorous results which are helpful for understanding the role of a putative model uncertainty region in the context of extreme quantile estimation. Finally, we illustrate our data-driven method in various settings, including examples showing how standard EVT can significantly underestimate quantiles of interest.

Authors
Jose Blanchet, Fei He, Karthyek Murthy
Publication date
2020/6
Journal
Extremes
Volume
23
Pages
317-347
Publisher
Springer US

Quantile aggregation with dependence uncertainty has a long history in probability theory with wide applications in finance, risk management, statistics, and operations research. Using a recent result on inf-convolution of quantile-based risk measures, we establish new analytical bounds for quantile aggregation which we call convolution bounds. Convolution bounds both unify every analytical result available in quantile aggregation and enlighten our understanding of these methods. These bounds are the best available in general. Moreover, convolution bounds are easy to compute, and we show that they are sharp in many relevant cases. They also allow for interpretability on the extremal dependence structure. The results directly lead to bounds on the distribution of the sum of random variables with arbitrary dependence. We discuss relevant applications in risk management and economics.

Authors
Jose Blanchet, Henry Lam, Yang Liu, Ruodu Wang
Publication date
2020/7/18
Journal
arXiv preprint arXiv:2007.09320

We propose a distributionally robust logistic regression model with an unfairness penalty that prevents discrimination with respect to sensitive attributes such as gender or ethnicity. This model is equivalent to a tractable convex optimization problem if a Wasserstein ball centered at the empirical distribution on the training data is used to model distributional uncertainty and if a new convex unfairness measure is used to incentivize equalized opportunities. We demonstrate that the resulting classifier improves fairness at a marginal loss of predictive accuracy on both synthetic and real datasets. We also derive linear programming-based confidence bounds on the level of unfairness of any pre-trained classifier by leveraging techniques from optimal uncertainty quantification over Wasserstein balls.

Authors
Bahar Taskesen, Viet Anh Nguyen, Daniel Kuhn, Jose Blanchet
Publication date
2020/7/18
Journal
arXiv preprint arXiv:2007.09530

This value τ (x) can be found by evaluating the minimum likelihood values fmin 0 (x) and fmin 0 (x). Unfortunately, it remains intractable to find the exact values of fmin 0 (x) and fmin 1 (x). To demonstrate this fact, we consider the Gaussian parametric setting as in Section 4, and evaluating the minimum likelihood in this case is equivalent to solving min−(µ− x) Σ− 1 (µ− x)− log det Σ st µ∈ Rd, Σ∈ Sd

Authors
Viet Anh Nguyen, Nian Si, Jose Blanchet

Background:

We sought to build an accessible interactive model that could facilitate hospital capacity planning in the presence of significant uncertainty about the proportion of the population that is positive forcoronavirus disease 2019 (COVID-19) and the rate at which COVID-19 is spreading in the population. Our goal was to facilitate the implementation of data-driven recommendations for capacity management with a transparent mathematical simulation designed to answer the specific, local questions hospital leadership considered critical.

Methods:

The model facilitates hospital planning with estimates of the number of Intensive Care (IC) beds, Acute Care (AC) beds, and ventilators necessary to accommodate patients who require hospitalization for COVID-19 and how these compare to the available resources. Inputs to the model include estimates of the characteristics of the patient population and hospital capacity. We deployed this model as an interactive online tool with modifiable parameters.

Results:

The use of the model is illustrated by estimating the demand generated by COVID-19+ arrivals for a hypothetical acute care medical center. The model calculated that the number of patients requiring an IC bed would equal the number of IC beds on Day 23, the number of patients requiring a ventilator would equal the number of ventilators available on Day 27, and the number of patients requiring an AC bed and coverage by the Medicine Service would equal the capacity of the Medicine service on Day 21. The model was used to inform COVID-19 planning and decision-making, including Intensive Care Unit (ICU) staffing and ventilator

Authors
Teng Zhang, Kelly McFarlane, Jacqueline Vallon, Linying Yang, Jin Xie, Jose Blanchet, Peter Glynn, Kristan Staudenmayer, Kevin Schulman, David Scheinker
Publication date
2020/6/11
Description
Background:

We provide the first rate of convergence to stationarity analysis for reflected Brownian motion (RBM) as the dimension grows under some uniformity conditions. In particular, if the underlying routing matrix is uniformly contractive, uniform stability of the drift vector holds, and the variances of the underlying Brownian motion (BM) are bounded, then we show that the RBM converges exponentially fast to stationarity with a relaxation time of order as the dimension d → ∞. Our bound for the relaxation time follows as a corollary of the nonasymptotic bound we obtain for the initial transient effect, which is explicit in terms of the RBM parameters.

Authors
Jose Blanchet, Xinyun Chen
Publication date
2020/5
Journal
Mathematics of Operations Research
Volume
45
Issue
2
Pages
660-681
Publisher
INFORMS

This chapter proposes a novel method for semi‐supervised learning (SSL) based on data‐driven distributionally robust optimization (DRO) using optimal transport metrics. The proposed method enhances generalization error by using the non‐labeled data to restrict the support of the worstcase distribution in DRO formulation. The chapter describes the implementation of DRO formulation by proposing a stochastic gradient descent algorithm, and demonstrates that semi‐supervised DRO method is able to improve the generalization error over natural supervised procedures and state‐of‐the‐art SSL estimators. It includes a discussion on the large sample behavior of the optimal uncertainty region in the DRO formulation. The discussion exposes important aspects such as the role of dimension reduction in SSL.

Authors
Jose Blanchet, Yang Kang
Publication date
2020/4/15
Journal
Data Analysis and Applications 3: Computational, Classification, Financial, Statistical and Stochastic Methods
Volume
5
Pages
1-33
Publisher
John Wiley & Sons, Inc.

We study the sequential batch learning problem in linear contextual bandits with finite action sets, where the decision maker is constrained to split incoming individuals into (at most) a fixed number of batches and can only observe outcomes for the individuals within a batch at the batch's end. Compared to both standard online contextual bandits learning or offline policy learning in contexutal bandits, this sequential batch learning problem provides a finer-grained formulation of many personalized sequential decision making problems in practical applications, including medical treatment in clinical trials, product recommendation in e-commerce and adaptive experiment design in crowdsourcing. We study two settings of the problem: one where the contexts are arbitrarily generated and the other where the contexts are \textit{iid} drawn from some distribution. In each setting, we establish a regret lower bound and provide an algorithm, whose regret upper bound nearly matches the lower bound. As an important insight revealed therefrom, in the former setting, we show that the number of batches required to achieve the fully online performance is polynomial in the time horizon, while for the latter setting, a pure-exploitation algorithm with a judicious batch partition scheme achieves the fully online performance even when the number of batches is less than logarithmic in the time horizon. Together, our results provide a near-complete characterization of sequential decision making in linear contextual bandits when batch constraints are present.

Authors
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, Yinyu Ye
Publication date
2020/4/14
Journal
arXiv preprint arXiv:2004.06321

As of March 23, 2020 there have been over 354,000 confirmed cases of coronavirus disease 2019 (COVID-19) in over 180 countries, the World Health Organization characterized COVID-19 as a pandemic, and the United States (US) announced a national state of emergency.1, 2, 3 In parts of China and Italy the demand for intensive care (IC) beds was higher than the number of available beds.4, 5 We sought to build an accessible interactive model that could facilitate hospital capacity planning in the presence of significant uncertainty about the proportion of the population that is COVID-19+ and the rate at which COVID-19 is spreading in the population. Our approach was to design a tool with parameters that hospital leaders could adjust to reflect their local data and easily modify to conduct sensitivity analyses.

We developed a model to facilitate hospital planning with estimates of the number of Intensive Care (IC) beds, Acute Care (AC) beds, and ventilators necessary to accommodate patients who require hospitalization for COVID-19 and how these compare to the available resources. Inputs to the model include estimates of the characteristics of the patient population and hospital capacity. We deployed this model as an interactive online tool. The model is implemented in R 3.5, RStudio, RShiny 1.4.0 and Python 3.7. The parameters used may be modified as data become available, for use at other institutions, and to generate sensitivity analyses.

We illustrate the use of the model by estimating the demand generated by COVID-19+ arrivals for a hypothetical acute care medical center. The model calculated that the number of patients requiring an …

Authors
Teng Zhang, Kelly McFarlane, Jacqueline Vallon, Linying Yang, Jin Xie, Jose Blanchet, Peter Glynn, Kristan Staudenmayer, Kevin Schulman, David Scheinker
Publication date
2020/3/26
Journal
medRxiv
Pages
2020.03. 24.20042762
Publisher
Cold Spring Harbor Laboratory Press

We consider a generic class of chance-constrained optimization problems with heavy-tailed (ie, power-law type) risk factors. In this setting, we use the scenario approach to obtain a constant approximation to the optimal solution with a computational complexity that is uniform in the risk tolerance parameter. We additionally illustrate the efficiency of our algorithm in the context of solvency in insurance networks.

Authors
JOSE Blanchet, F Zhang, BERT Zwart
Publication date
2020/2
Journal
arXiv preprint arXiv:2002.02149

We consider the parameter estimation problem of a probabilistic generative model prescribed using a natural exponential family of distributions. For this problem, the typical maximum likelihood estimator usually overfits under limited training sample size, is sensitive to noise and may perform poorly on downstream predictive tasks. To mitigate these issues, we propose a distributionally robust maximum likelihood estimator that minimizes the worst-case expected log-loss uniformly over a parametric Kullback-Leibler ball around a parametric nominal distribution. Leveraging the analytical expression of the Kullback-Leibler divergence between two distributions in the same natural exponential family, we show that the min-max estimation problem is tractable in a broad setting, including the robust training of generalized linear models. Our novel robust estimator also enjoys statistical consistency and delivers promising empirical results in both regression and classification tasks.

Authors
Viet Anh Nguyen, Xuhui Zhang, Jose Blanchet, Angelos Georghiou
Publication date
2020
Journal
Advances in Neural Information Processing Systems
Volume
33
Pages
7922-7932

We consider the problem of estimating the Wasserstein distance between the empirical measure and a set of probability measures whose expectations over a class of functions (hypothesis class) are constrained. If this class is sufficiently rich to characterize a particular distribution (eg, all Lipschitz functions), then our formulation recovers the Wasserstein distance to such a distribution. We establish a strong duality result that generalizes the celebrated Kantorovich-Rubinstein duality. We also show that our formulation can be used to beat the curse of dimensionality, which is well known to affect the rates of statistical convergence of the empirical Wasserstein distance. In particular, examples of infinite-dimensional hypothesis classes are presented, informed by a complex correlation structure, for which it is shown that the empirical Wasserstein distance to such classes converges to zero at the standard parametric rate. Our formulation provides insights that help clarify why, despite the curse of dimensionality, the Wasserstein distance enjoys favorable empirical performance across a wide range of statistical applications.

Authors
Nian Si, Jose Blanchet, Soumyadip Ghosh, Mark Squillante
Publication date
2020
Journal
Advances in Neural Information Processing Systems
Volume
33
Pages
21260-21270

Conditional estimation given specific covariate values (ie, local conditional estimation or functional estimation) is ubiquitously useful with applications in engineering, social and natural sciences. Existing data-driven non-parametric estimators mostly focus on structured homogeneous data (eg, weakly independently and stationary data), thus they are sensitive to adversarial noise and may perform poorly under a low sample size. To alleviate these issues, we propose a new distributionally robust estimator that generates non-parametric local estimates by minimizing the worst-case conditional expected loss over all adversarial distributions in a Wasserstein ambiguity set. We show that despite being generally intractable, the local estimator can be efficiently found via convex optimization under broadly applicable settings, and it is robust to the corruption and heterogeneity of the data. Various experiments show the competitive performance of this new class of estimator.

Authors
Viet Anh Nguyen, Fan Zhang, Jose Blanchet, Erick Delage, Yinyu Ye
Publication date
2020
Journal
Advances in Neural Information Processing Systems
Volume
33
Pages
15232-15242

In this paper, we consider online learning in generalized linear contextual bandits where rewards are not immediately observed. Instead, rewards are available to the decision maker only after some delay, which is unknown and stochastic, even though a decision must be made at each time step for an incoming set of contexts. We study the performance of upper confidence bound (UCB) based algorithms adapted to this delayed setting. In particular, we design a delay-adaptive algorithm, which we call Delayed UCB, for generalized linear contextual bandits using UCB-style exploration and establish regret bounds under various delay assumptions. In the important special case of linear contextual bandits, we further modify this algorithm and establish a tighter regret bound under the same delay assumptions. Our results contribute to the broad landscape of contextual bandits literature by establishing that UCB algorithms, which are widely deployed in modern recommendation engines, can be made robust to delays.

Authors: Zhengyuan Zhou, Renyuan Xu, Jose Blanchet
Publication date: 2019
Journal: Advances in Neural Information Processing Systems
Volume: 32

Distributionally Robust Optimization (DRO) has been shown to provide a flexible framework for decision making under uncertainty and statistical estimation. For example, recent works in DRO have shown that popular statistical estimators can be interpreted as the solutions of suitable formulated data-driven DRO problems. In turn, this connection is used to optimally select tuning parameters in terms of a principled approach informed by robustness considerations. This paper contributes to this growing literature, connecting DRO and statistics, by showing how boosting algorithms can be studied via DRO. We propose a boosting type algorithm, named DRO-Boosting, as a procedure to solve our DRO formulation. Our DRO-Boosting algorithm recovers Adaptive Boosting (AdaBoost) in particular, thus showing that AdaBoost is effectively solving a DRO problem. We apply our algorithm to a financial dataset on credit card …

Authors
Jose Blanchet, Fan Zhang, Yang Kang, Zhangyi Hu
Publication date
2019/12/8
Conference
2019 Winter Simulation Conference (WSC)
Pages
3728-3739
Publisher
IEEE

Some recent works showed that several machine learning algorithms, such as square-root Lasso, Support Vector Machines, and regularized logistic regression, among many others, can be represented exactly as distributionally robust optimization (DRO) problems. The distributional uncertainty set is defined as a neighborhood centered at the empirical distribution, and the neighborhood is measured by optimal transport distance. In this paper, we propose a methodology which learns such neighborhood in a natural data-driven way. We show rigorously that our framework encompasses adaptive regularization as a particular case. Moreover, we demonstrate empirically that our proposed methodology is able to improve upon a wide range of popular machine learning estimators.

Authors
Jose Blanchet, Yang Kang, Karthyek Murthy, Fan Zhang
Publication date
2019/12/8
Conference
2019 winter simulation conference (WSC)
Pages
3740-3751
Publisher
IEEE

Semi-parametric dynamic contextual pricing Page 1 Semi-parametric dynamic contextual pricing Virag Shah — Jose Blanchet — Ramesh Johari Stanford University virag@stanford.edu September 27, 2019 1 / 15 Page 2 Dynamic pricing ▶ Several platforms have access to data describing history of different users. ▶ Platforms can leverage this information to price different products and optimize revenue. ▶ This requires learning online the mapping from user context to optimal price, efficiently. 2 / 15 Page 3 Basic Framework ▶ Discrete times 1,2,...,n, one user arrives per time step ▶ Each user is shown one product, which is ex-ante fixed ▶ Let Vt be the value tth user assigns to the product. ▶ Let pt be the price set by the platform. ▶ The user buys the product if pt ≤ Vt. ▶ Platform does not know or observe Vt, but has access to covariates Xt ∈ Rd which may describe user’s history and product’s type ▶ Goal: set …

Authors
R Johari, J Blanchet
Publication date
2019/12/5
Journal
Advances in Neural Infor

We study the occurrence of large queue lengths in the GI / GI / d queue with heavy-tailed Weibull-type service times. Our analysis hinges on a recently developed sample path large-deviations principle for Lévy processes and random walks, following a continuous mapping approach. Also, we identify and solve a key variational problem which provides physical insight into the way a large queue length occurs. In contrast to the regularly varying case, we observe several subtle features such as a non-trivial trade-off between the number of big jobs and their sizes and a surprising asymmetric structure in asymptotic job sizes leading to congestion.

Authors
Mihail Bazhba, Jose Blanchet, Chang-Han Rhee, Bert Zwart
Publication date
2019/12
Journal
Queueing Systems
Volume
93
Pages
195-226
Publisher
Springer US

Using a result of Blanchet and Wallwater (2015) for exactly simulating the maximum of a negative drift random walk queue endowed with independent and identically distributed (i.i.d.) increments, we extend it to a multi-dimensional setting and then we give a new algorithm for simulating exactly the stationary distribution of a first-in–first-out (FIFO) multi-server queue in which the arrival process is a general renewal process and the service times are i.i.d.: the FIFO GI/GI/c queue with . Our method utilizes dominated coupling from the past (DCFP) as well as the random assignment (RA) discipline, and complements the earlier work in which Poisson arrivals were assumed, such as the recent work of Connor and Kendall (2015). We also consider the models in continuous time, and show that with mild further assumptions, the exact simulation of those stationary distributions can also be achieved. We also give, using our …

Authors
Jose Blanchet, Yanan Pei, Karl Sigman
Publication date
2019/12
Journal
Advances in Applied Probability
Volume
51
Issue
4
Pages
1179-1208
Publisher
Cambridge University Press

We consider the random field \begin{equation*}M(t)=\mathop{\mathrm{sup}}_{n\geq1}\{-\log A_{n}+X_{n}(t)\},\qquad t\in T,\end{equation*} for a set , where is an i.i.d. sequence of centered Gaussian random fields on and are the arrivals of a general renewal process on , independent of . In particular, a large class of max-stable random fields with Gumbel marginals have such a representation. Assume that one needs function evaluations to sample at locations . We provide an algorithm which samples with complexity as measured in the norm sense for any . Moreover, if has an a.s. converging series representation, then can be a.s. approximated with error uniformly over and with complexity , where relates to the Hölder continuity exponent of the process (so, if is Brownian …

Authors
Zhipeng Liu, Jose H Blanchet, ANTONIUS B Dieker, Thomas Mikosch
Publication date
2019/11/1
Volume
25
Issue
4A
Pages
2949-2981

Let X be a Lévy process with regularly varying Lévy measure ν. We obtain sample-path large deviations for scaled processes X̄n(t) and obtain a similar result for random walks with regularly varying increments. Our results yield detailed asymptotic estimates in scenarios where multiple big jumps in the increment are required to make a rare event happen; we illustrate this through detailed conditional limit theorems. In addition, we investigate connections with the classical large deviations framework. In that setting, we show that a weak large deviation principle (with logarithmic speed) holds, but a full large deviation principle does not hold.

Authors
Chang-Han Rhee, Jose Blanchet, Bert Zwart
Publication date
2019/11/1
Journal
The Annals of Probability
Volume
47
Issue
6
Pages
3551-3605
Publisher
Institute of Mathematical Statistics

In a recent paper, Nguyen et al. (2018) built a distributionally robust estimator for the precision matrix of the Gaussian distribution. The distributional uncertainty size is a key ingredient in the construction of this estimator. We develop a statistical theory which shows how to optimally choose the uncertainty size to minimize the associated Stein loss. Surprisingly, rather than the expected canonical square-root scaling rate, the optimal uncertainty size scales linearly with the sample size.

Authors
Jose Blanchet, Nian Si
Publication date
2019/11/1
Journal
Operations Research Letters
Volume
47
Issue
6
Pages
618-621
Publisher
North-Holland

We show that several machine learning estimators, including square-root least absolute shrinkage and selection and regularized logistic regression, can be represented as solutions to distributionally robust optimization problems. The associated uncertainty regions are based on suitably defined Wasserstein distances. Hence, our representations allow us to view regularization as a result of introducing an artificial adversary that perturbs the empirical distribution to account for out-of-sample effects in loss estimation. In addition, we introduce RWPI (robust Wasserstein profile inference), a novel inference methodology which extends the use of methods inspired by empirical likelihood to the setting of optimal transport costs (of which Wasserstein distances are a particular case). We use RWPI to show how to optimally select the size of uncertainty regions, and as a consequence we are able to choose regularization …

Authors: Jose Blanchet, Yang Kang, Karthyek Murthy
Publication date: 2019/9
Journal: Journal of Applied Probability
Volume: 56
Issue: 3
Pages: 830-857
Publisher: Cambridge University Press

We model optimal allocations in a distribution network as the solution of a linear program (LP) that minimizes the cost of unserved demands across nodes in the network. The constraints in the LP dictate that, after a given node’s supply is exhausted, its unserved demand is distributed among neighboring nodes. All nodes do the same, and the resulting solution is the optimal allocation. Assuming that the demands are random (following a jointly Gaussian law), our goal is to study the probability that the optimal cost of unserved demands exceeds a large threshold, which is a rare event. Our contribution is the development of importance sampling and conditional Monte Carlo algorithms for estimating this probability. We establish the asymptotic efficiency of our algorithms and also present numerical results that illustrate strong performance of our procedures.

Authors
Jose Blanchet, Juan Li, Marvin K Nakayama
Publication date
2019/9
Journal
Operations Research
Volume
67
Issue
5
Pages
1383-1396
Publisher
INFORMS

We propose a novel framework for analyzing convergence rates of stochastic optimization algorithms with adaptive step sizes. This framework is based on analyzing properties of an underlying generic stochastic process; in particular, we derive a bound on the expected stopping time of this process. We utilize this framework to analyze the expected global convergence rates of a stochastic variant of a traditional trust-region method. Although traditional trust-region methods rely on exact computations of the gradient, Hessian, and values of the objective function, this method assumes that these values are available only up to some dynamically adjusted accuracy. Moreover, this accuracy is assumed to hold only with some sufficiently large—but fixed—probability without any additional restrictions on the variance of the errors. This setting applies, for example, to standard stochastic optimization and machine learning …

Authors: Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg
Publication date: 2019/4
Journal: INFORMS journal on optimization
Volume: 1
Issue: 2
Pages: 92-119
Publisher: INFORMS

We propose a family of relaxations of the optimal transport problem which regularize the problem by introducing an additional minimization step over a small region around one of the underlying transporting measures. The type of regularization that we obtain is related to smoothing techniques studied in the optimization literature. When using our approach to estimate optimal transport costs based on empirical measures, we obtain statistical learning bounds which are useful to guide the amount of regularization, while maintaining good generalization properties. To illustrate the computational advantages of our regularization approach, we apply our method to training Wasserstein GANs. We obtain running time improvements, relative to current benchmarks, with no deterioration in testing performance (via FID). The running time improvement occurs because our new optimality-based threshold criterion reduces the number of expensive iterates of the generating networks, while increasing the number of actor-critic iterations.

Authors
Saied Mahdian, Jose Blanchet, Peter Glynn
Publication date
2019/6/7
Journal
arXiv preprint arXiv:1906.03317

The goal of this paper is to provide a unifying view of a wide range of problems of interest in machine learning by framing them as the minimization of functionals defined on the space of probability measures. In particular, we show that generative adversarial networks, variational inference, and actor-critic methods in reinforcement learning can all be seen through the lens of our framework. We then discuss a generic optimization algorithm for our formulation, called probability functional descent (PFD), and show how this algorithm recovers existing methods developed independently in the settings mentioned earlier.

Authors
Casey Chu, Jose Blanchet, Peter Glynn
Publication date
2019/5/24
Conference
International Conference on Machine Learning
Pages
1213-1222
Publisher
PMLR

We provide the first perfect sampling algorithm for a generalized Jackson network of first-in, first-out queues under arbitrary topology and non-Markovian assumptions on the input of the network. We assume (in addition to stability) that the interarrival and service times of customers have a finite moment-generating function in a neighborhood of the origin, and the interarrival times have unbounded support.

Authors
Jose Blanchet, Xinyun Chen
Publication date
2019/5
Journal
Mathematics of Operations Research
Volume
44
Issue
2
Pages
693-714
Publisher
INFORMS

We present general principles for the design and analysis of unbiased Monte Carlo estimators in a wide range of settings. Our estimators posses finite work-normalized variance under mild regularity conditions. We apply our estimators to various settings of interest, including unbiased optimization in Sample Average Approximations, unbiased steady-state simulation of regenerative processes, quantile estimation and nested simulation problems.

Authors
Jose H Blanchet, Peter W Glynn, Yanan Pei
Publication date
2019/4/22
Journal
arXiv preprint arXiv:1904.09929

This paper deals with the problem of quantifying the impact of model misspecification when computing general expected values of interest. The methodology that we propose is applicable in great generality; in particular, we provide examples involving path-dependent expectations of stochastic processes. Our approach consists of computing bounds for the expectation of interest regardless of the probability measure used, as long as the measure lies within a prescribed tolerance measured in terms of a flexible class of distances from a suitable baseline model. These distances, based on optimal transportation between probability measures, include Wasserstein’s distances as particular cases. The proposed methodology is well suited for risk analysis and distributionally robust optimization, as we demonstrate with applications. We also discuss how to estimate the tolerance region nonparametrically using Skorokhod …

Authors: Jose Blanchet, Karthyek Murthy
Publication date: 2019/5
Journal: Mathematics of Operations Research
Volume: 44
Issue: 2
Pages: 565-600
Publisher: INFORMS

Authors
Xinyun Chen, Jose Blanchet
Publication date
2019/3/1

We present the first algorithm that samples maxn≥0{Sn − nα}, where Sn is a mean zero random walk, and nα with defines a nonlinear boundary. We show that our algorithm has finite expected running time. We also apply this algorithm to construct the first exact simulation method for the steady-state departure process of a GI/GI/∞ queue where the service time distribution has infinite mean.

Authors
Jose Blanchet, Jing Dong, Zhipeng Liu
Publication date
2019/3
Journal
Journal of Applied Probability
Volume
56
Issue
1
Pages
116-138
Publisher
Cambridge University Press

This article investigates techniques for the assessment of model error in the context of insurance risk analysis. The methodology is based on finding robust estimates for actuarial quantities of interest, which are obtained by solving optimization problems over the unknown probabilistic models, with constraints capturing potential nonparametric misspecification of the true model. We demonstrate the solution techniques and the interpretations of these optimization problems, and illustrate several examples, including calculating loss probabilities and conditional value-at-risk.

Authors
Jose Blanchet, Henry Lam, Qihe Tang, Zhongyi Yuan
Publication date
2019/1/2
Journal
North American Actuarial Journal
Volume
23
Issue
1
Pages
33-63
Publisher
Routledge

This paper proposes a novel non-parametric multidimensional convex regression estimator which is designed to be robust to adversarial perturbations in the empirical measure. We minimize over convex functions the maximum (over Wasserstein perturbations of the empirical measure) of the absolute regression errors. The inner maximization is solved in closed form resulting in a regularization penalty involves the norm of the gradient. We show consistency of our estimator and a rate of convergence of order , matching the bounds of alternative estimators based on square-loss minimization. Contrary to all of the existing results, our convergence rates hold without imposing compactness on the underlying domain and with no a priori bounds on the underlying convex function or its gradient norm.

Authors
Jose Blanchet, Peter W Glynn, Jun Yan, Zhengqing Zhou
Publication date
2019
Journal
Advances in Neural Information Processing Systems
Volume
32

Motivated by the application of real-time pricing in e-commerce platforms, we consider the problem of revenue-maximization in a setting where the seller can leverage contextual information describing the customer's history and the product's type to predict her valuation of the product. However, her true valuation is unobservable to the seller, only binary outcome in the form of success-failure of a transaction is observed. Unlike in usual contextual bandit settings, the optimal price/arm given a covariate in our setting is sensitive to the detailed characteristics of the residual uncertainty distribution. We develop a semi-parametric model in which the residual distribution is non-parametric and provide the first algorithm which learns both regression parameters and residual distribution with regret. We empirically test a scalable implementation of our algorithm and observe good performance.

Authors
Virag Shah, Ramesh Johari, Jose Blanchet
Publication date
2019
Journal
Advances in Neural Information Processing Systems
Volume
32

Consider a player that in each of T rounds chooses one of K arms. An adversary chooses the cost of each arm in a bounded interval, and a sequence of feedback delays\left {d {t}\right} that are unknown to the player. After picking arm a {t} at round t, the player receives the cost of playing this arm d {t} rounds later. In cases where t+ d {t}> T, this feedback is simply missing. We prove that the EXP3 algorithm (that uses the delayed feedback upon its arrival) achieves a regret of O\left (\sqrt {\ln K\left (KT+\sum {t= 1}^{T} d {t}\right)}\right). For the case where\sum {t= 1}^{T} d {t} and T are unknown, we propose a novel doubling trick for online learning with delays and prove that this adaptive EXP3 achieves a regret of O\left (\sqrt {\ln K\left (K^{2} T+\sum {t= 1}^{T} d {t}\right)}\right). We then consider a two player zero-sum game where players experience asynchronous delays. We show that even when the delays are large enough such that players no longer enjoy the “no-regret property”,(eg, where d {t}= O\left (t\log t\right)) the ergodic average of the strategy profile still converges to the set of Nash equilibria of the game. The result is made possible by choosing an adaptive step size\eta {t} that is not summable but is square summable, and proving a “weighted regret bound” for this general case.

Authors
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, Jose Blanchet
Publication date
2019
Journal
Advances in neural information processing systems
Volume
32

We introduce a class of unbiased Monte Carlo estimators for multivariate densities of max-stable fields generated by Gaussian processes. Our estimators take advantage of recent results on the exact simulation of max-stable fields combined with identities studied in the Malliavin calculus literature and ideas developed in the multilevel Monte Carlo literature. Our approach allows estimating multivariate densities of max-stable fields with precision at a computational cost of order .

Authors
Jose Blanchet, Zhipeng Liu
Publication date
2018
Conference
Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, Stanford, CA, August 14-19 12
Pages
75-97
Publisher
Springer International Publishing

In this work, we provide faster algorithms for approximating the optimal transport distance, e.g. earth mover's distance, between two discrete probability distributions . Given a cost function where quantifies the penalty of transporting a unit of mass from to , we show how to compute a coupling between and in time whose expected transportation cost is within an additive of optimal. This improves upon the previously best known running time for this problem of . We achieve our results by providing reductions from optimal transport to canonical optimization problems for which recent algorithmic efforts have provided nearly-linear time algorithms. Leveraging nearly linear time algorithms for solving packing linear programs and for solving the matrix balancing problem, we obtain two separate proofs of our stated running time. Further, one of our algorithms is easily parallelized and can be implemented with depth . Moreover, we show that further algorithmic improvements to our result would be surprising in the sense that any improvement would yield an algorithm for \textit{maximum cardinality bipartite matching}, for which currently the only known algorithms for achieving such a result are based on fast-matrix multiplication.

Authors: Jose Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
Publication date: 2018/10/17
Journal: arXiv preprint arXiv:1810.07717

Queueing approaches can capture the stochastic dynamics of chemical reactions and provide a more accurate picture of the reaction kinetics than coupled differential equations in situations where the number of molecules is small. A striking example of such a situation is an enzyme cascade with substrate channeling, where reaction intermediates are directly passed from one enzyme to the next via tunnels or surface paths with limited capacity. In order to better understand the contribution of the stochastic dynamics to the observed enhancement in cascade throughput as a result from substrate channeling, we compare the results of a model using differential equations to describe concentration changes with a queueing model. The continuum model and the queueing model yield identical results, except when the maximum rate of reaction of the enzymes are similar. In two enzyme cascades, the queueing model …

Authors
Stanislav Tsitkov, Theo Pesenti, Henri Palacci, Jose Blanchet, Henry Hess
Publication date
2018/10/3
Journal
ACS Catalysis
Volume
8
Issue
11
Pages
10721-10731
Publisher
American Chemical Society

We introduce the first class of perfect sampling algorithms for the steady-state distribution of multi-server queues with general interarrival time and service time distributions. Our algorithm is built on the classical dominated coupling from the past protocol. In particular, we use a coupled multi-server vacation system as the upper bound process and develop an algorithm to simulate the vacation system backward in time from stationarity at time zero. The algorithm has finite expected termination time with mild moment assumptions on the interarrival time and service time distributions.

Authors
Jose Blanchet, Jing Dong, Yanan Pei
Publication date
2018/10
Journal
Queueing Systems
Volume
90
Pages
1-33
Publisher
Springer US

Physical climate risk faced by companies is emerging as a significant concern for long term investors, such as sovereign wealth funds. For the mining sector, each physical asset may have a significant financial exposure to extreme climate events such as floods and droughts. Often, these financial risks are difficult to value given the paucity of data on climate extremes, and limited company assessment and disclosure of the associated financial liability. We propose a generalization of the Brennan-Schwartz approach to real option valuation to address this situation. A Poisson point process is used to model arrivals of extreme events that exceed the estimated design return period of the flood/drought mitigation infrastructure at the site. Using techniques from the field of robust performance analysis, we are able to calculate upper and lower bounds over all the probability models within a certain distance from the original …

Authors
C Dolan, J Blanchet, G Iyengar, U Lall
Publication date
2018/8/1
Journal
Resources Policy
Volume
57
Pages
81-87
Publisher
Pergamon

We present the first exact simulation method for multidimensional reflected Brownian motion (RBM). Exact simulation in this setting is challenging because of the presence of correlated local-time-like terms in the definition of RBM. We apply recently developed so-called ε-strong simulation techniques (also known as tolerance-enforced simulation) which allow us to provide a piecewise linear approximation to RBM with ε (deterministic) error in uniform norm. A novel conditional acceptance–rejection step is then used to eliminate the error. In particular, we condition on a suitably designed information structure so that a feasible proposal distribution can be applied.

Authors
Jose Blanchet, Karthyek Murthy
Publication date
2018/3
Journal
Journal of Applied Probability
Volume
55
Issue
1
Pages
137-156
Publisher
Cambridge University Press

In many platforms, user arrivals exhibit a self-reinforcing behavior: future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit {\em positive externalities}. We study multiarmed bandit (MAB) problems with positive externalities. We show that the self-reinforcing preferences may lead standard benchmark algorithms such as UCB to exhibit linear regret. We develop a new algorithm, Balanced Exploration (BE), which explores arms carefully to avoid suboptimal convergence of arrivals before sufficient evidence is gathered. We also introduce an adaptive variant of BE which successively eliminates suboptimal arms. We analyze their asymptotic regret, and establish optimality by showing that no algorithm can perform better.

Authors
Virag Shah, Jose Blanchet, Ramesh Johari
Publication date
2018
Journal
Advances in Neural Information Processing Systems
Volume
31

In constructing debiased multi-level Monte Carlo (MLMC) estimators, one must choose a randomization distribution. In some algorithmic contexts, an optimal choice for the randomization distribution leads to a setting in which the mean time to generate an unbiased observation is infinite. This paper extends the well known efficiency theory for Monte Carlo algorithms in the setting of a finite mean for this generation time to the infinite mean case. The theory draws upon stable law weak convergence results, and leads directly to exact convergence rates and central limit theorems (CLTs) for various debiased MLMC algorithms, most particularly as they arise in the context of stochastic differential equations. Our CLT theory also allows simulators to construct asymptotically valid confidence intervals for such infinite mean MLMC algorithms.

Authors
Zeyu Zheng, Jose Blanchet, Peter W Glynn
Publication date
2018
Conference
Monte Carlo and Quasi-Monte Carlo Methods: MCQMC 2016, Stanford, CA, August 14-19 12
Pages
465-479
Publisher
Springer International Publishing

This chapter summarizes a body of work which has as objective the quantification of risk exposures that are particularly important in the context of industries such as the mining industry and which are inherently difficult to calibrate against a probabilistic model due to lack of information. In order to address this problem, we propose an approach based on game theoretic representations which are known in the operations research literature as distributionally robust optimization (DRO) problems. Our goal in this chapter is to provide a high level and conceptual discussion of this approach and explain how we extended it and applied it to the mining setting which is the topic of this project.

Authors
J Blanchet, U Lall
Publication date
2017/12/24
Journal
to be submitted

We study a direct Monte-Carlo-based approach for computing the worst-case expectation of two multidimensional random variables given a specification of their marginal distributions. This problem is motivated by several applications in risk quantification and statistics. We show that if one of the random variables takes finitely many values, a direct Monte Carlo approach allows to evaluate such worst case expectation with O(n -1/2 ) convergence rate as the number of Monte Carlo samples, n, increases to infinity.

Authors
Jose Blanchet, Fei He, Henry Lam
Publication date
2017/12/3
Conference
2017 Winter Simulation Conference (WSC)
Pages
2315-2323
Publisher
IEEE

In this paper, we introduce an unbiased gradient simulation algorithms for solving convex optimization problem with stochastic function compositions. We show that the unbiased gradient generated from the algorithm has finite variance and finite expected computation cost. We then combined the unbiased gradient simulation with two variance reduced algorithms (namely SVRG and SCSG) and showed that the proposed optimization algorithms based on unbiased gradient simulations exhibit satisfactory convergence properties. Specifically, in the SVRG case, the algorithm with simulated gradient can be shown to converge linearly to optima in expectation and almost surely under strong convexity. Finally, for the numerical experiment,we applied the algorithms to two important cases of stochastic function compositions optimization: maximizing the Cox's partial likelihood model and training conditional random fields.

Authors
Jose Blanchet, Donald Goldfarb, Garud Iyengar, Fengpei Li, Chaoxu Zhou
Publication date
2017/11/20
Journal
arXiv preprint arXiv:1711.07564

Regularized estimators in the context of group variables have been applied successfully in model and feature selection in order to preserve interpretability. We formulate a Distributionally Robust Optimization (DRO) problem which recovers popular estimators, such as Group Square Root Lasso (GSRL). Our DRO formulation allows us to interpret GSRL as a game, in which we learn a regression parameter while an adversary chooses a perturbation of the data. We wish to pick the parameter to minimize the expected loss under any plausible model chosen by the adversary-who, on the other hand, wishes to increase the expected loss. The regularization parameter turns out to be precisely determined by the amount of perturbation on the training data allowed by the adversary. In this paper, we introduce a data-driven (statistical) criterion for the optimal choice of regularization, which we evaluate asymptotically, in closed form, as the size of the training set increases. Our easy-to-evaluate regularization formula is compared against cross-validation, showing comparable performance.

Authors
Jose Blanchet, Yang Kang
Publication date
2017/11/11
Conference
Asian Conference on Machine Learning
Pages
97-112
Publisher
PMLR

We consider the random field M (t)= sup n≥ 1 {− log An+ Xn (t)}, t∈ T, for a set T⊂ Rm, where (Xn) is an iid sequence of centered Gaussian random fields on T and 0< A1< A2 0, samples M (t1),..., M (td) with complexity o (c (d) dϵ) as measured in the Lp norm sense for any p≥ 1. Moreover, if Xn has an as converging series representation, then M can be as approximated with error δ uniformly over T and with complexity O (1/(δ log (1/δ)) 1/α), where α relates to the Hölder continuity exponent of the process Xn (so, if Xn is Brownian motion, α= 1/2).

Authors
ZHIPENG LIU, JOSE BLANCHET, AB DIEKER, THOMAS MIKOSCH
Publication date
2017/8/30

We provide the first generic exact simulation algorithm for multivariate diffusions. Current exact sampling algorithms for diffusions require the existence of a transformation which can be used to reduce the sampling problem to the case of a constant diffusion matrix and a drift which is the gradient of some function. Such transformation, called Lamperti transformation, can be applied in general only in one dimension. So, completely different ideas are required for exact sampling of generic multivariate diffusions. The development of these ideas is the main contribution of this paper. Our strategy combines techniques borrowed from the theory of rough paths, on one hand, and multilevel Monte Carlo on the other.

Authors
Jose Blanchet, Fan Zhang
Publication date
2017/6/16
Journal
arXiv preprint arXiv:1706.05124

Data-driven Distributionally Robust Optimization (DD-DRO) via optimal transport has been shown to encompass a wide range of popular machine learning algorithms. The distributional uncertainty size is often shown to correspond to the regularization parameter. The type of regularization (e.g. the norm used to regularize) corresponds to the shape of the distributional uncertainty. We propose a data-driven robust optimization methodology to inform the transportation cost underlying the definition of the distributional uncertainty. We show empirically that this additional layer of robustification, which produces a method we called doubly robust data-driven distributionally robust optimization (DD-R-DRO), allows to enhance the generalization properties of regularized estimators while reducing testing error relative to state-of-the-art classifiers in a wide range of data sets.

Authors
Jose Blanchet, Yang Kang, Fan Zhang, Fei He, Zhangyi Hu
Publication date
2017/5/19
Journal
arXiv preprint arXiv:1705.07168

How much of the structure of a Limit Order Book (LOB) by only observing the bid/ask price dynamics? In this paper we provide a model which, surprisingly, allows us to recover with reasonable empirical accuracy the general profile of the LOB in the setting of some small-tick stocks. Our approach exploits the empirically observed multi-scale dynamics of the LOB and we also apply such multi-scale analysis to obtain a jump diffusion model which connects the distribution of jumps with the distribution of orders inside the LOB.

Authors
Jose Blanchet, Xinyun Chen, Yanan Pei
Publication date
2017/2/22
Journal
Preprint. Available at http://www. columbia. edu/∼ jb2814/papers/LOB_v1. pdf

This paper investigates techniques for the assessment of model error in the context of insurance risk analysis. The methodology is based on finding bounds for quantities of interest, such as loss probabilities and conditional value-at-risk, which are obtained by solving optimization problems where the variable to optimize is the model itself in a non-parametric framework. The non-parametric aspect of the approach is crucial for model error quantification.

Authors
Jose Blanchet, Henry Lam, Qihe Tang, Zhongyi Yuan
Publication date
2017/2/7
Journal
Technical Report, Society of Actuaries

Consider a multidimensional diffusion process . Let be a deterministic, user defined, tolerance error parameter. Under standard regularity conditions on the drift and diffusion coefficients of , we construct a probability space, supporting both and an explicit, piecewise constant, fully simulatable process such that

with probability one. Moreover, the user can adaptively choose so that (also piecewise constant and fully simulatable) can be constructed conditional on to ensure an error smaller than with probability one. Our construction requires a detailed study of continuity estimates of the Itô map using Lyons’ theory of rough paths. We approximate the underlying Brownian motion, jointly with the Lévy areas with a deterministic error in the underlying rough path metric.

Authors
Jose Blanchet, Xinyun Chen, Jing Dong
Publication date
2017/2/1
Volume
27
Issue
1
Pages
275-336

We introduce a variant of a traditional trust region method which is aimed at stochastic optimization. While traditional trust region method relies on exact computations of the gradient and values of the objective function, our method assumes that these values are available up to some dynamically adjusted accuracy. Moreover, this accuracy is assumed to hold only with some sufficiently large, but fixed, probability, without any additional restrictions on the variance of the errors. We show that our assumptions apply to the standard stochastic setting assumed in the machine learning problems, but also include more general settings. We then proceed to provide a bound on the expected number of iterations the stochastic algorithm requires to reach accuracy∇ f (x)≤ ǫ, for any ǫ> 0. The resulting bound is O (ǫ− 2), under the assumption of sufficiently accurate stochastic gradient.

Authors
Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg
Publication date
2016/9
Journal
arXiv preprint arXiv:1609.07428
Volume
5
Publisher
Working paper, Columbia University, New York

We propose a novel framework for analyzing convergence rates of stochastic optimization algorithms with adaptive step sizes. This framework is based on analyzing properties of an underlying generic stochastic process, in particular by deriving a bound on the expected stopping time of this process. We utilize this framework to analyze the bounds on expected global convergence rates of a stochastic variant of a traditional trust region method, introduced in \cite{ChenMenickellyScheinberg2014}. While traditional trust region methods rely on exact computations of the gradient, Hessian and values of the objective function, this method assumes that these values are available up to some dynamically adjusted accuracy. Moreover, this accuracy is assumed to hold only with some sufficiently large, but fixed, probability, without any additional restrictions on the variance of the errors. This setting applies, for example, to standard stochastic optimization and machine learning formulations. Improving upon the analysis in \cite{ChenMenickellyScheinberg2014}, we show that the stochastic process defined by the algorithm satisfies the assumptions of our proposed general framework, with the stopping time defined as reaching accuracy . The resulting bound for this stopping time is , under the assumption of sufficiently accurate stochastic gradient, and is the first global complexity bound for a stochastic trust-region method. Finally, we apply the same framework to derive second order complexity bound under some additional assumptions.

Authors
Jose Blanchet, Coralia Cartis, Matt Menickelly, Katya Scheinberg
Publication date
2016/9/23
Journal
arXiv preprint arXiv:1609.07428

We consider the random field M(t)=\sup_{n\geq 1}\big\{-\log A_{n}+X_{n}(t)\big\}\,,\qquad t\in T\, for a set , where is an iid sequence of centered Gaussian random fields on and are the arrivals of a general renewal process on , independent of . In particular, a large class of max-stable random fields with Gumbel marginals have such a representation. Assume that one needs function evaluations to sample at locations . We provide an algorithm which, for any , samples with complexity . Moreover, if has an a.s. converging series representation, then can be a.s. approximated with error uniformly over and with complexity , where relates to the H\"{o}lder continuity exponent of the process (so, if is Brownian motion, ).

Authors
Zhipeng Liu, Jose H Blanchet, AB Dieker, Thomas Mikosch
Publication date
2016/9/20
Journal
arXiv preprint arXiv:1609.06001

We study the convergence properties of a Monte Carlo estimator proposed in the physics literature to compute the quasi-stationary distribution on a transient set of a Markov chain (see De Oliveira and Dickman (2005), (2006), and Dickman and Vidigal (2002)). Using the theory of stochastic approximations we verify the consistency of the estimator and obtain an associated central limit theorem. We provide an example showing that convergence might occur very slowly if a certain eigenvalue condition is violated. We alleviate this problem using an easy-to-implement projection step combined with averaging.

Authors
Jose Blanchet, Peter Glynn, Shuheng Zheng
Publication date
2016/9
Journal
Advances in Applied Probability
Volume
48
Issue
3
Pages
792-811
Publisher
Cambridge University Press

Assortment planning is an important problem that arises in many industries such as retailing and airlines. One of the key challenges in an assortment planning problem is to identify the “right” model for the substitution behavior of customers from the data. Error in model selection can lead to highly suboptimal decisions. In this paper, we consider a Markov chain based choice model and show that it provides a simultaneous approximation for all random utility based discrete choice models including the multinomial logit (MNL), the probit, the nested logit and mixtures of multinomial logit models. In the Markov chain model, substitution from one product to another is modeled as a state transition in the Markov chain. We show that the choice probabilities computed by the Markov chain based model are a good approximation to the true choice probabilities for any random utility based choice model under mild conditions …

Authors: Jose Blanchet, Guillermo Gallego, Vineet Goyal
Publication date: 2016/8
Journal: Operations Research
Volume: 64
Issue: 4
Pages: 886-905
Publisher: INFORMS

Let X be a Lévy process with regularly varying Lévy measure ν. We obtain sample-path large deviations of scaled processes Xn (t) X (nt)/n and obtain a similar result for random walks. Our results yield detailed asymptotic estimates in scenarios where multiple big jumps in the increment are required to make a rare event happen. In addition, we investigate connections with the classical large-deviations framework. In that setting, we show that a weak large deviations principle (with logarithmic speed) holds, but a full large-deviations principle does not hold.

Chang-Han Rhee, Jose Blanchet, Bert Zwart
Publication date
2016/6
Journal
arXiv preprint arXiv:1606.02795

Based on a weak convergence argument, we provide a necessary and sufficient condition that guarantees that a nonnegative local martingale is indeed a martingale. Typically, conditions of this sort are expressed in terms of integrability conditions (such as the well-known Novikov condition). The weak convergence approach that we propose allows to replace integrability conditions by a suitable tightness condition. We then provide several applications of this approach ranging from simplified proofs of classical results to characterizations of processes conditioned on first passage time events and changes of measures for jump processes.

Authors
Jose Blanchet, Johannes Ruf
Publication date
2016/4/2
Journal
Stochastic Models
Volume
32
Issue
2
Pages
233-252
Publisher
Taylor & Francis

In this paper we present a rigorous analysis of the evolution of the temperature of a power line under stochastic exogenous factors such as ambient temperature. We present a solution to the resulting stochastic heat equation and we propose a number of control algorithms designed to maximize delivered power under chance constraints used to limit the probability that a line exceeds its critical temperature.

Authors
Daniel Bienstock, Jose Blanchet, Juan Li
Publication date
2016/2
Journal
Energy Systems
Volume
7
Pages
173-192
Publisher
Springer Berlin Heidelberg

We provide the first rate of convergence analysis for RBM as the dimension grows under natural uniformity conditions. In particular, if the underlying routing matrix is uniformly contractive, uniform stability of the drift vector holds, and the variances of the underlying Brownian Motion (BM) are bounded, then we show that the RBM converges exponentially fast to stationarity with a relaxation time of order

Authors
Jose Blanchet, Xinyun Chen
Publication date
2016/1/16
Journal
arXiv preprint arXiv:1601.04111

We obtain asymptotic bounds for the tail distribution of steady-state waiting time in a two-server queue where each server processes incoming jobs at a rate equal to the rate of their arrivals (that is, the half-loaded regime). The job sizes are taken to be regularly varying. When the incoming jobs have finite variance, there are basically two types of effects that dominate the tail asymptotics. While the quantitative distinction between these two manifests itself only in the slowly varying components, the two effects arise from qualitatively very different phenomena (arrival of one extremely big job or two big jobs). Then there is a phase transition that occurs when the incoming jobs have infinite variance. In that case, only one of these effects dominates the tail asymptotics; the one involving arrival of one extremely big job.

Authors
Jose Blanchet, Karthyek R A. Murthy
Publication date
2015/12
Journal
Queueing Systems
Volume
81
Pages
301-340
Publisher
Springer US

Many Monte Carlo computations involve computing quantities that can be expressed as g(EX), where g is nonlinear and smooth, and X is an easily simulatable random variable. The nonlinearity of g makes the conventional Monte Carlo estimator for such quantities biased. In this paper, we show how such quantities can be estimated without bias. However, our approach typically increases the variance. Thus, our approach is primarily of theoretical interest in the above setting. However, our method can also be applied to the computation of the inner expectation associated with Eg ((EX|Z)), and in this setting, the application of this method can have a significant positive effect on improving the rate of convergence relative to conventional “nested schemes” for carrying out such calculations.

Authors
Jose H Blanchet, Nan Chen, Peter W Glynn
Publication date
2015/12/6
Conference
2015 Winter Simulation Conference (WSC)
Pages
360-367
Publisher
IEEE

Traditional stochastic approximation (SA) schemes employ a single gradient or a fixed batch of noisy gradients in computing a new iterate. We consider SA schemes in which N k samples are utilized at step k and the total simulation budget is M, where Σ k=1 K N k ≤M and K denotes the terminal step. This paper makes the following contributions in the strongly convex regime: (I) We conduct an error analysis for constant batches (N k = N) under constant and diminishing steplengths and prove linear convergence in terms of expected error in solution iterates based on prescribing N k in terms of simulation and computational budgets; (II) we extend the linear convergence rates to the setting where N k is increased at a prescribed rate dependent on simulation and computational budgets; (III) finally, when steplengths are constant, we obtain the optimal number of projection steps that minimizes the bound on the mean …

Authors
Uday V Shanbhag, Jose H Blanchet
Publication date
2015/12/6
Conference
2015 Winter Simulation Conference (WSC)
Pages
368-379
Publisher
IEEE

Traditional stochastic approximation (SA) schemes employ a single gradient or a fixed batch of noisy gradients in computing a new iterate. We consider SA schemes in which N k samples are utilized at step k and the total simulation budget is M, where Σ k=1 K N k ≤M and K denotes the terminal step. This paper makes the following contributions in the strongly convex regime: (I) We conduct an error analysis for constant batches (N k = N) under constant and diminishing steplengths and prove linear convergence in terms of expected error in solution iterates based on prescribing N k in terms of simulation and computational budgets; (II) we extend the linear convergence rates to the setting where N k is increased at a prescribed rate dependent on simulation and computational budgets; (III) finally, when steplengths are constant, we obtain the optimal number of projection steps that minimizes the bound on the mean …

Authors
Uday V Shanbhag, Jose H Blanchet
Publication date
2015/12/6
Conference
2015 Winter Simulation Conference (WSC)
Pages
368-379
Publisher
IEEE

We present general principles for the design and analysis of unbiased Monte Carlo estimators for quantities such as α = g(E (X)), where E (X) denotes the expectation of a (possibly multidimensional) random variable X, and g(·) is a given deterministic function. Our estimators possess finite work-normalized variance under mild regularity conditions such as local twice differentiability of g(·) and suitable growth and finite-moment assumptions. We apply our estimator to various settings of interest, such as optimal value estimation in the context of Sample Average Approximations, and unbiased steady-state simulation of regenerative processes. Other applications include unbiased estimators for particle filters and conditional expectations.

Authors
Jose H Blanchet, Peter W Glynn
Publication date
2015/12/6
Conference
2015 Winter Simulation Conference (WSC)
Pages
3656-3667
Publisher
IEEE

This paper develops the first class of algorithms that enable unbiased estimation of steady-state expectations for multidimensional reflected Brownian motion. In order to explain our ideas, we first consider the case of compound Poisson (possibly Markov modulated) input. In this case, we analyze the complexity of our procedure as the dimension of the network increases and show that, under certain assumptions, the algorithm has polynomial-expected termination time. Our methodology includes procedures that are of interest beyond steady-state simulation and reflected processes. For instance, we use wavelets to construct a piecewise linear function that can be guaranteed to be within distance (deterministic) in the uniform norm to Brownian motion in any compact time interval.

Authors
Jose Blanchet, Xinyun Chen
Publication date
2015/12/1
Volume
25
Issue
6
Pages
3209-3250

We provide the first algorithm that, under minimal assumptions, allows simulation of the stationary waiting-time sequence of a single-server queue backward in time, jointly with the input processes of the queue (interarrival and service times). The single-server queue is useful in applications of Dominated Coupling from the Past (DCFTP), which is a well-known protocol for simulation without bias from steady-state distributions. Our algorithm terminates in finite time, assuming only finite mean of the interarrival and service times. To simulate the single-server queue in stationarity until the first idle period in finite expected termination time, we require the existence of finite variance. This requirement is also necessary for such idle time (which is a natural coalescence time in DCFTP applications) to have finite mean. Thus, in this sense, our algorithm is applicable under minimal assumptions.

Authors
Jose Blanchet, Aya Wallwater
Publication date
2015/11/16
Journal
ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume
25
Issue
4
Pages
1-27
Publisher
ACM

We establish a central limit theorem and a large deviations principle for affine point processes, which are stochastic models of correlated event timing widely used in finance and economics. These limit results generate closed-form approximations to the distribution of an affine point process. They also facilitate the construction of an asymptotically optimal importance sampling estimator of tail probabilities. Numerical tests illustrate our results.

Authors
Xiaowei Zhang, Jose Blanchet, Kay Giesecke, Peter W Glynn
Publication date
2015/10
Journal
Mathematics of Operations Research
Volume
40
Issue
4
Pages
797-819
Publisher
INFORMS

We present the first class of perfect sampling (also known as exact simulation) algorithms for the steady-state distribution of non-Markovian loss systems. We use a variation of dominated coupling from the past. We first simulate a stationary infinite server system backwards in time and analyze the running time in heavy traffic. In particular, we are able to simulate stationary renewal marked point processes in unbounded regions. We then use the infinite server system as an upper bound process to simulate the loss system. The running time analysis of our perfect sampling algorithm for loss systems is performed in the quality-driven (QD) and the quality-and-efficiency-driven regimes. In both cases, we show that our algorithm achieves subexponential complexity as both the number of servers and the arrival rate increase. Moreover, in the QD regime, our algorithm achieves a nearly optimal rate of complexity.

Authors
Jose Blanchet, Jing Dong
Publication date
2015/9
Journal
Advances in Applied Probability
Volume
47
Issue
3
Pages
761-786
Publisher
Cambridge University Press

We propose an insurance network model that allows to deal with default contagion risks with a particular aim of capturing cascading effects at the time of defaults. We capture these effects by finding an equilibrium allocation of settlements which can be found as the unique optimal solution of an optimization problem. This equilibrium allocation recognizes 1) the correlation among the risk factors, 2) the contractual obligations, which are assumed to follow popular contracts in the insurance industry (such as stop-loss), and 3) the interconnections of the insurance-reinsurance network. We are able to obtain an asymptotic description of the most likely ways in which the default of a specific group of participants can occur, by means of solving a multidimensional Knapsack integer programming problem. Finally, we propose a class of strongly efficient estimators (in a precise large deviations sense) for computing the expected loss of the network conditioning on the failure of a specific set of companies of companies.

Authors
Jose Blanchet, Juan Li, Yixi Shi
Publication date
2015/9/1
Journal
Analysis and Efficient Monte Carlo (September 1, 2015)

Traditional stochastic approximation (SA) schemes for stochastic optimization employ a single gradient or a fixed batch of noisy gradients in computing a new iterate. We consider the development of SA schemes in which Nk gradient samples are utilized at step k and the total computational budget is M, so that∑ K k= 1 Nk≤ M where K denotes the terminal step. This paper makes the following contributions:(i) We conduct an error analysis for constant batches (Nk= N) both for constant and diminishing steplength regime and show linear convergence in terms of expected optimal value;(ii) we extend the two schemes in (i), and the corresponding linear convergence rates, now in the setting of increasing sample sizes (increasing Nk), assuming constant or diminishing steplength;(iii) finally, when steplengths are constant, we obtain the optimal number of projection steps that minimize the bound on the mean-squared error.

Authors
Uday V Shanbhag, José Blanchet

We construct an unbiased estimator for function value evaluated at the solution of a partial differential equation with random coefficients. We show that the variance and expected computational cost of our estimator are finite and our estimator is unsensitive to the problem dimension so that it can be applied in problems across various disciplines. For the error analysis, we connect the parabolic partial differential equations with the expectations of stochastic differential equations and perform rough path estimation.

Authors
Jose Blanchet, Fengpei Li, Xiaoou Li
Publication date
2018/6/8
Journal
arXiv preprint arXiv:1806.03362

If the inter-arrival time distribution of a renewal process is regularly varying with index (i.e. the inter-arrival times have infinite mean) and if is the associated age process at time . Then we show that if is the length of the current cycle at time ,
where is . This extends a classical result in renewal theory in the finite mean case which indicates that the limit is .

Authors
Jose Blanchet, Peter Glynn, Hermann Thorisson
Publication date
2015/3/29
Journal
arXiv preprint arXiv:1503.08374

We develop importance sampling based efficient simulation techniques for three commonly encountered rare event probabilities associated with random walks having i.i.d. regularly varying increments; namely, 1) the large deviation probabilities, 2) the level crossing probabilities, and 3) the level crossing probabilities within a regenerative cycle. Exponential twisting based state-independent methods, which are effective in efficiently estimating these probabilities for light-tailed increments are not applicable when the increments are heavy-tailed. To address the latter case, more complex and elegant state-dependent efficient simulation algorithms have been developed in the literature over the last few years. We propose that by suitably decomposing these rare event probabilities into a dominant and further residual components, simpler state-independent importance sampling algorithms can be devised for each …

Authors
Karthyek RA Murthy, Sandeep Juneja, Jose Blanchet
Publication date
2015/3
Journal
Stochastic Systems
Volume
4
Issue
2
Pages
321-374
Publisher
INFORMS

An algorithm for estimating quasi-stationary distribution of finite state space Markov chains has been proven in a previous paper. Now this paper proves a similar algorithm that works for general state space Markov chains under very general assumptions.

Authors
Jose H Blanchet, Peter Glynn, Shuheng Zheng
Publication date
2015/2/23
Journal
arXiv preprint arXiv:1502.06451

Our goal is to create a simple, yet robust, statistical model which can be used to quantify the risk present in a portfolio of mining assets. In pursuit of this goal we aim at explaining a systematic approach which takes as input a model which is constructed based on fundamental economic principles and simple statistical technniques (eg a mixed-effect linear model with explanatory variables chosen from economic reasoning). Additional enrichment is then imposed, based on input coming from a more detailed model (built, for instance, from bottom up). And finally, the robustification step is obtained by computing worst-case performance analysis among all models that are within some distance of our simple model. This step quantifies the error induced by using a simple-yet-tractable model, which might be incorrect.

Authors
J Blanchet, C Dolan, G Iyengar, U Lall
Publication date
2015

Integral transforms of the lognormal distribution are of great importance in statistics and probability, yet closed-form expressions do not exist. A wide variety of methods have been employed to provide approximations, both analytical and numerical. In this paper, we analyse a closed-form approximation  of the Laplace transform  which is obtained via a modified version of Laplace’s method. This approximation, given in terms of the Lambert W(⋅) function, is tractable enough for applications. We prove that ~(𝜃) is asymptotically equivalent to ℒ(𝜃) as 𝜃 → ∞. We apply this result to construct a reliable Monte Carlo estimator of ℒ(𝜃) and prove it to be logarithmically efficient in the rare event sense as 𝜃 → ∞.

Authors: Søren Asmussen, Jens Ledet Jensen, Leonardo Rojas-Nandayapa
Publication date: 2016/6
Journal: Methodology and Computing in Applied Probability
Volume: 18
Issue: 2
Pages: 441-458
Publisher: Springer US

We consider a common type of robust performance analysis that is formulated as maximizing an expectation among all probability models that are within some tolerance of a baseline model in the Kullback-Leibler sense. The solution of such concave program is tractable and provides an upper bound which is robust to model misspecification. However, this robust formulation fails to preserve some natural stochastic structures, such as i.i.d. model assumptions, and as a consequence, the upper bounds might be pessimistic. Unfortunately, the introduction of i.i.d. assumptions as constraints renders the underlying optimization problem very challenging to solve. We illustrate these phenomena in the rare event setting, and propose a large-deviations based approach for solving this challenging problem in an asymptotic sense for a natural class of random walk problems.

Authors
Jose Blanchet, Christopher Dolan, Henry Lam
Publication date
2014/12/7
Conference
Proceedings of the Winter Simulation Conference 2014
Pages
595-603
Publisher
IEEE

We develop rare-event simulation methodology for the analysis of loss events in a many-server loss system under the quality-driven regime, focusing on the steady-state loss probability (i.e., fraction of lost customers over arrivals) and the behavior of the whole system leading to loss events. The analysis of these events requires working with the full measure-valued process describing the system. This is the first algorithm that is shown to be asymptotically optimal, in the rare-event simulation context, under the setting of many-server queues involving a full measure-valued representation.

Authors
Jose Blanchet, Henry Lam
Publication date
2014/11
Journal
Mathematics of Operations Research
Volume
39
Issue
4
Pages
1142-1178
Publisher
INFORMS

Let Qλ(t, y) be the number of people present at time t with at least y units of remaining service time in an infinite server system with arrival rate equal to λ > 0. In the presence of a non-lattice renewal arrival process and assuming that the service times have a continuous distribution, we obtain a large deviations principle for Qλ(·)/λ under the topology of uniform convergence on [0, T] × [0, ∞). We illustrate our results by obtaining the most likely paths, represented as surfaces, to overflow in the setting of loss queues, and also to ruin in life insurance portfolios.

Authors
Jose Blanchet, Xinyun Chen, Henry Lam
Publication date
2014/9
Journal
Stochastic Systems
Volume
4
Issue
1
Pages
206-249
Publisher
INFORMS

We present the first exact simulation method for multidimensional reflected Brownian motion (RBM). Exact simulation in this setting is challenging because of the presence of correlated local-time-like terms in the definition of RBM. We apply recently developed so-called strong simulation techniques (also known as Tolerance-Enforced Simulation) which allow us to provide a piece-wise linear approximation to RBM with (deterministic) error in uniform norm. A novel conditional acceptance/rejection step is then used to eliminate the error. In particular, we condition on a suitably designed information structure so that a feasible proposal distribution can be applied.

Authors
Jose Blanchet, Karthyek RA Murthy
Publication date
2014/5/26
Journal
arXiv preprint arXiv:1405.6469

We study a new technique for the asymptotic analysis of heavy-tailed systems conditioned on large deviations events. We illustrate our approach in the context of ruin events of multidimensional regularly varying random walks. Our approach is to study the Markov process described by the random walk conditioned on hitting a rare target set. We construct a Markov chain whose transition kernel can be evaluated directly from the increment distribution of the associated random walk. This process is shown to approximate the conditional process of interest in total variation. Then, by analyzing the approximating process, we are able to obtain asymptotic conditional joint distributions and a conditional functional central limit theorem of several objects such as the time until ruin, the whole random walk prior to ruin, and the overshoot on the target set. These types of joint conditional limit theorems have been obtained …

Authors
Jose Blanchet, Jingchen Liu
Publication date
2014/5/1
Volume
20
Issue
2
Pages
416-456

Authors
Xinyun Chen, Jose Blanchet, Henry Lam
Publication date
2014/3/1

This paper studies a method, which has been proposed in the Physics literature by [8, 7, 10], for estimating the quasi-stationary distribution. In contrast to existing methods in eigenvector estimation, the method eliminates the need for explicit transition matrix manipulation to extract the principal eigenvector. Our paper analyzes the algorithm by casting it as a stochastic approximation algorithm (Robbins-Monro) [23, 16]. In doing so, we prove its convergence and obtain its rate of convergence. Based on this insight, we also give an example where the rate of convergence is very slow. This problem can be alleviated by using an improved version of the algorithm that is given in this paper. Numerical experiments are described that demonstrate the effectiveness of this improved method.

Authors
Jose Blanchet, Peter Glynn, Shuheng Zheng
Publication date
2014/1/2
Journal
arXiv preprint arXiv:1401.0364

In this article, rare-event simulation for stochastic recurrence equations of the form

Xn+1=An+1Xn+Bn+1, X0=0

is studied, where {An;n≥ 1} and {Bn;n≥ 1} are independent sequences consisting of independent and identically distributed real-valued random variables. It is assumed that the tail of the distribution of B1 is regularly varying, whereas the distribution of A1 has a suitably light tail. The problem of efficient estimation, via simulation, of quantities such as P{Xn>b} and P{supk≤nXk > b} for large b and n is studied. Importance sampling strategies are investigated that provide unbiased estimators with bounded relative error as b and n tend to infinity.

Authors
Jose Blanchet, Henrik Hult, Kevin Leder
Publication date
2013/12/16
Journal
ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume
23
Issue
4
Pages
1-25
Publisher
ACM

This paper discusses a control scheme for maintaining low tripping probability of a transmission system power line under thermal stress. We construct a stochastic differential equation to describe the temperature evolution in a line subject to randomness of the ambient temperature. When the distribution of the ambient temperature changes, so does the dependence of the tripping probability as a function of line current. The theory of extremes of Gaussian random fields is used to guide the size of the underlying frequency inspection so as to insure that current is effective for controlling the risk of overheating. In particular, we show that only when the change of temperature is suitably light-tailed (according to a precise definition discussed in the paper), the current provides a powerful enough mechanism to control tripping probabilities due to overheating. We then provide bounds that can be used to control the tripping …

Authors
Jose Blanchet, Daniel Bienstock, Juan Li
Publication date
2013/12/10
Conference
52nd IEEE Conference on Decision and Control
Pages
4977-4982
Publisher
IEEE

Most of the efficient rare event simulation methodology for heavy-tailed systems has concentrated on processes with stationary and independent increments. Motivated by applications such as insurance risk theory, in this paper we develop importance sampling estimators that are shown to achieve asymptotically vanishing relative error property (and hence are strongly efficient) for the estimation of large deviation probabilities in Markov modulated random walks that possess heavy-tailed increments. Exponential twisting based methods, which are effective in light-tailed settings, are inapplicable even in the simpler case of random walk involving i.i.d. heavy-tailed increments. In this paper we decompose the rare event of interest into a dominant and residual component, and simulate them independently using state-independent changes of measure that are both intuitive and easy to implement.

Authors
Karthyek RA Murthy, Sandeep Juneja, Jose Blanchet
Publication date
2013/12/8
Conference
2013 Winter Simulations Conference (WSC)
Pages
564-576
Publisher
IEEE

Rare events in heavy-tailed systems are challenging to analyze using splitting algorithms because large deviations occur suddenly. So, every path prior to the rare event is viable and there is no clear mechanism for rewarding and splitting paths that are moving towards the rare event of interest. We propose and analyze a splitting algorithm for the tail distribution of a heavy-tailed random walk. We prove that our estimator achieves the best possible performance in terms of the growth rate of the relative mean squared error, while controlling the population size of the particles.

Authors
Jose Blanchet, Yixi Shi
Publication date
2013/12/8
Conference
2013 Winter Simulations Conference (WSC)
Pages
724-735
Publisher
IEEE

We consider the problems of computing overflow probabilities at level N in any subset of stations in a Jackson network and of simulating sample paths conditional on overflow. We construct algorithms that take O(N) function evaluations to estimate such overflow probabilities within a prescribed relative accuracy and to simulate paths conditional on overflow at level N. The algorithms that we present are optimal in the sense that the best possible performance that can be expected for conditional sampling involves Ω(N) running time. As we explain in our development, our techniques have the potential to be applicable to more general classes of networks.

Authors
Jose Blanchet
Publication date
2013/11
Journal
Mathematics of Operations Research
Volume
38
Issue
4
Pages
698-719
Publisher
INFORMS

Let (Q t) t∈ R be the stationary workload process of a Lévy-driven queue, where the driving Lévy process is light-tailed. For various functions T (u), we analyze P (∫ 0 T (u) Q s d s> u) for u large. For T (u)= o (u) the asymptotics resemble those of the steady-state workload being larger than u/T (u). If T (u) is proportional to u they look like e− α u for some α> 0. Interestingly, the asymptotics are still valid when u= o (T (u)), T (u)= o (u), and T (u)= β u for β suitably small.

Authors
J Blanchet, Michel Mandjes
Publication date
2013/11/1
Journal
Operations Research Letters
Volume
41
Issue
6
Pages
730-736
Publisher
North-Holland

We derive a continuous time model for the joint evolution of the mid price and the bid-ask spread from a multiscale analysis of the whole limit order book (LOB) dynamics. We model the LOB as a multiclass queueing system and perform our asymptotic analysis using stylized features observed empirically. We argue that in the asymptotic regime supported by empirical observations the mid price and bid-ask-spread can be described using only certain parameters of the book (not the whole book itself). Our limit process is characterized by reflecting behavior and state-dependent jumps. Our analysis allows to explain certain characteristics observed in practice such as: the connection between power-law decaying tails in the volumes of the order book and the returns, as well as statistical properties of the long-run spread distribution.

Authors
Jose Blanchet, Xinyun Chen
Publication date
2013/10/3
Journal
arXiv preprint arXiv:1310.1103

The cross entropy method is an iterative technique that is used to obtain a low-variance importance sampling (IS) distribution from a given parametric family, which must satisfy two properties. First, subsequent iterations of the parameters must be easily computable and, second, the family should approximate the zero-variance IS distribution. We obtain parametric families for which these two properties are satisfied for a large class of heavy-tailed systems. Our estimators are shown to be strongly efficient in these settings.

Authors
Jose Blanchet, Yixi Shi
Publication date
2013/5/1
Journal
Operations Research Letters
Volume
41
Issue
3
Pages
271-276
Publisher
North-Holland

Let be an queue with traffic intensity Consider the quantity $$\begin{aligned} S_{n}(p)=\frac{1}{n}\sum _{j=1}^{n}Q\left( j\right) ^{p} \end{aligned}$$for any The ergodic theorem yields that , where is geometrically distributed with mean It is known that one can explicitly characterize such that $$\begin{aligned} \lim \limits _{n\rightarrow \infty }\frac{1}{n}\log P\big (S_{n}(p)0. \end{aligned}$$In this paper, we show that the approximation of the right tail asymptotics requires a different logarithm scaling, giving $$\begin{aligned} \lim \limits _{n\rightarrow \infty }\frac{1}{n^{1/(1+p)}}\log P\big (S_{n} (p)>\mu \big (p\big )+\varepsilon \big )=-C\big (p\big ) \varepsilon ^{1/(1+p)}, \end{aligned}$$where is obtained as the solution of a variational problem. We …

Authors
Jose Blanchet, Peter Glynn, Sean Meyn
Publication date
2013/4
Journal
Queueing Systems
Volume
73
Issue
4
Pages
425-446
Publisher
Springer US

This special issue contains a selection of papers which are based on some of the invited lectures that were given at the workshop on Simulation of Stochastic Networks which took place on June 21–23, 2010 at the Newton Institute of Mathematical Sciences in Cambridge, UK. The workshop, which was dedicated to topics related to estimation of rare events as well as other aspects including simulation of stochastic differential equations (SDEs), and steady-state simulation, was attended by over fifty active researchers and leading experts in the fields of applied probability and stochastic simulation. The special issue cuts across different areas at the intersection of applied probability and stochastic simulation and we believe that an important strength of the issue is that the contributions suggest interesting research avenues in their respective areas. We therefore hope that the readers will enjoy these contributions and …

Authors
Jose Blanchet, Gareth Roberts
Publication date
2013/4
Journal
Queueing Systems
Volume
73
Pages
341-343
Publisher
Springer US

A binary contingency table is an m× n array of binary entries with row sums r=(r1,…, rm) and column sums c=(c1,…, cn). The configuration model generates a contingency table by considering ri tokens of type 1 for each row i and cj tokens of type 2 for each column j, and then taking a uniformly random pairing between type‐1 and type‐2 tokens. We give a necessary and sufficient condition so that the probability that the configuration model outputs a binary contingency table remains bounded away from 0 as article mathrsfs amsmath empty N= i= 1^ m r_i= j= 1^ n c_j goes to∞. Our finding shows surprising differences from recent results for binary symmetric contingency tables.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012

Authors
Jose Blanchet, Alexandre Stauffer
Publication date
2013/3
Journal
Random Structures & Algorithms
Volume
42
Issue
2
Pages
159-184
Publisher
Wiley Subscription Services, Inc., A Wiley Company

We explore a new framework to approximate life insurance risk processes in the scenario of plentiful policyholders, via a bottom-up approach. Given the insurance contract structure, we aggregate the balance of individual policy accounts, and derive an approximating Gaussian process with computable correlation structure. The methodology is borrowed from heavy traffic theory in the literature of many-server queues, and involves the so-called fluid and diffusion approximations. Our framework is different from the individual risk model in that it takes into account the time dimension and the specific policy structure including the premium payments. It is also different from classical risk theory in that it builds the risk process from micro-level contracts and parameters instead of assuming aggregated claim and premium processes outright. As a result, our approximating process behaves differently depending on the issued …

Authors
Jose Blanchet, Henry Lam
Publication date
2013/7/1
Journal
Insurance: Mathematics and Economics
Volume
53
Issue
1
Pages
237-251
Publisher
North-Holland

We provide a complete large and moderate deviations asymptotic for the steady-state waiting time of a class of subexponential M/G/1 queues under heavy traffic. The asymptotic is uniform over the positive axis, and reduces to heavy-traffic asymptotics and heavy-tail asymptotics on two ends, both of which are known to be valid over restricted asymptotic regimes. The link between these two well-known asymptotics is a transition term that is expressible as a convolution-type integral. The class of service times that we consider includes regularly varying and Weibull tails in particular.

It is our pleasure to contribute to this special issue dedicated to the International Year of Statistics. In response to the request of the editors of this special issue we briefly overview the research topics that we have investigated recently. Our research group has pursued several themes in recent years. All of them lie under the scope of applied probability. Some of our projects deal with computational probability. In this context, our goal is to enable efficient computation in stochastic systems using (and often developing) theory of probability to inform the design of algorithm that are optimal and robust in certain sense (see Blanchet and Glynn (2008)). Most of the computations that we study relate to stochastic simulation (also known as Monte Carlo) methods (see Blanchet and Lam (2012)). Other projects that we pursue relate to classical analysis in probability, such as asymptotic approximations, large deviations, and heavy-traffic limits (Blanchet and Glynn (2006) and Lam et al (2011)). All of our research efforts are motivated by models and problems in areas such as: Finance …

Authors
Jose Blanchet, Henry Lam
Publication date
2013
Journal
Bull. of the Mex. Math. Soc.(3)
Volume
19

This paper studies a method for estimating the quasi-stationary distribution of various interacting particle processes has been proposed by [6, 5, 8]. This method improved upon existing methods in eigenvector estimation by eliminating the need for explicit transition matrix representation and multiplication. However, this method has no firm theoretical foundation. Our paper analyzes the algorithm by casting it as a stochastic approximation algorithm (Robbins-Monro) [12]. In doing so, we prove its convergence and rate of convergence. Based on this insight, we also give an example where the rate of convergence is very slow. This problem can be alleviated by using an improved version of this algorithm that is given in this paper. Numerical experiments are described that demonstrate the effectiveness of this improved method.

Authors
Jose Blanchet, Peter Glynn, Shuheng Zheng
Publication date
2013
Conference
EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II
Pages
19-37
Publisher
Springer Berlin Heidelberg

Given a marked renewal point process (assuming that the marks are i.i.d.) we say that an unbounded region is stable if it contains finitely many points of the point process with probability one. In this paper we provide algorithms that allow to sample these finitely many points efficiently. We explain how exact simulation of the steady-state measure valued state descriptor of the infinite server queue follows as a simple corollary of our algorithms. We provide numerical evidence supporting that our algorithms are not only theoretically sound but also practical. Finally, having simulation optimization in mind, we also apply our results to gradient estimation of steady-state performance measures.

Authors
Jose Blanchet, Jing Dong
Publication date
2012/12/9
Conference
Proceedings of the 2012 Winter Simulation Conference (WSC)
Pages
1-12
Publisher
IEEE

Measuring Systemic Risks in Insurance - Reinsurance Networks Page 1 Measuring Systemic Risks in Insurance - Reinsurance Networks - Stanford University 2012 - Jose Blanchet and Yixi Shi Department of Industrial Engineering and Operations Research, Columbia University November, 2012 Blanchet & Shi (Columbia) Systemic Risks in Insurance Networks 11/2012 1 / 32 Page 2 Modeling Focus, Framework and Question of Interests Outline 1 Modeling Focus, Framework and Question of Interests Focus of the Talk: Insurance Risk The Model: A High-level Overview Insurance: Basics Modeling Framework Questions of Interest 2 Counter-party Risk and Settlement Mechanism A Stylized Contractual Model Default Settlement Mechanism 3 Qualitative Risk Analysis A Tractable Stylized Risk Factor Model A First Qualitative Analysis The Role of Risk Mitigators 4 Enhancing Qualitative Analysis with Efficient Simulation …

Authors
Jose Blanchet, Yixi Shi
Publication date
2012/11
Journal
Preprint

We consider perpetuities of the form where the Yj’s and Bj’s might be i.i.d. or jointly driven by a suitable Markov chain. We assume that the Yj’s satisfy the so-called Cramér condition with associated root θ∗∈(0,∞) and that the tails of the Bj’s are appropriately behaved so that D is regularly varying with index θ∗. We illustrate by means of an example that the natural state-independent importance sampling estimator obtained by exponentially tilting the Yj’s according to θ∗ fails to provide an efficient estimator (in the sense of appropriately controlling the relative mean squared error as the tail probability of interest gets smaller). Then, we construct estimators based on state-dependent importance sampling that are rigorously shown to be efficient.

Authors
Jose Blanchet, Henry Lam, Bert Zwart
Publication date
2012/10/1
Journal
Stochastic Processes and their Applications
Volume
122
Issue
10
Pages
3361-3392
Publisher
North-Holland

In this article we explain some connections between Lyapunov methods and subsolutions of an associated Isaacs equation for the design of efficient importance sampling schemes. As we shall see, subsolutions can be derived by taking an appropriate limit of an associated Lyapunov inequality. They have been recently proposed in several works of Dupuis, Wang, and others and applied to address several important problems in rare-event simulation. Lyapunov inequalities have been used for testing the efficiency of state-dependent importance sampling schemes in heavy-tailed or discrete settings in a variety of works by Blanchet, Glynn, and others. While subsolutions provide an analytic criterion for the construction of efficient samplers, Lyapunov inequalities are useful for finding more precise information, in the form of bounds, for the behavior of the coefficient of variation of the associated importance sampling …

Authors
Jose Blanchet, Peter Glynn, Kevin Leder
Publication date
2012/8/1
Journal
ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume
22
Issue
3
Pages
1-27
Publisher
ACM

The contribution of this paper is to introduce change of measure based techniques for the rare-event analysis of heavy-tailed random walks. Our changes of measures are parameterized by a family of distributions admitting a mixture form. We exploit our methodology to achieve two types of results. First, we construct Monte Carlo estimators that are strongly efficient (i.e. have bounded relative mean squared error as the event of interest becomes rare). These estimators are used to estimate both rare-event probabilities of interest and associated conditional expectations. We emphasize that our techniques allow us to control the expected termination time of the Monte Carlo algorithm even if the conditional expected stopping time (under the original distribution) given the event of interest is infinity–a situation that sometimes occurs in heavy-tailed settings. Second, the mixture family serves as a good Markovian …

Authors
Jose Blanchet, Jingchen Liu
Publication date
2012/8/1
Journal
Stochastic Processes and Their Applications
Volume
122
Issue
8
Pages
2994-3031
Publisher
North-Holland

A source of light is placed d inches apart from the center of a detection bar of length L ≥ d. The source spins very rapidly, while shooting beams of light according to, say, a Poisson process with rate λ. The positions of the beams, relative to the center of the bar, are recorded for those beams that actually hit the bar. Which law best describes the time-average position of the beams that hit the bar given a fixed but long time horizon t? The answer is given in this paper by means of a uniform weak convergence result in L, d as t → ∞. Our approximating law includes as particular cases the Cauchy and Gaussian distributions.

Authors
Jose H Blanchet, Carlos G Pacheco-González
Publication date
2012/7
Journal
Probability in the Engineering and Informational Sciences
Volume
26
Issue
3
Pages
437-448
Publisher
Cambridge University Press

Our focus is on the design and analysis of efficient Monte Carlo methods for computing tail probabilities for the suprema of Gaussian random fields, along with conditional expectations of functionals of the fields given the existence of excursions above high levels, b. Naïve Monte Carlo takes an exponential, in b, computational cost to estimate these probabilities and conditional expectations for a prescribed relative accuracy. In contrast, our Monte Carlo procedures achieve, at worst, polynomial complexity in b, assuming only that the mean and covariance functions are Hölder continuous. We also explain how to fine tune the construction of our procedures in the presence of additional regularity, such as homogeneity and smoothness, in order to further improve the efficiency.

Authors: Robert J Adler, Jose H Blanchet, Jingchen Liu
Publication date: 2012/6/1
Volume: 22
Issue: 3
Pages: 1167-1214

Modern large deviations theory, pioneered by Donsker and Varadhan, concerns the study of rare events, and it has become a common tool for the analysis of stochastic systems in a variety of scientific disciplines and in engineering. The theory developed by Donsker and Varadhan is a generalization of Laplace's principle and Cramér's theorem. Here we concentrate on applications to finance and risk management.

Authors
Jose H Blanchet, Carlos G Pacheco‐González
Publication date
2010/5/15
Journal
Encyclopedia of Quantitative Finance
Publisher
John Wiley & Sons, Ltd

We consider a FCFS M/Hd/n queue which has a Poisson arrival process (M) and iid service times following a hyper-exponential distribution with d components (Hd). We develop rare-event simulation methodology to analyze large deviations for the queue length process in steady-state under the Halfin-Whitt regime. The key strategy consists of constructing two objects: I) a regenerative set A whose probability is bounded away from zero as n→∞, and II) a free process for which the most likely path to overflow is easy to handle. In particular, the free process is coupled with the original system outside the set A and it is not sensitive to boundary behavior. The successful application of the algorithm takes crucial advantage of the simulation and evaluation of a time-inhomogeneous Markov chain that is defined in terms of matrix exponential functions.

Authors
Jose Blanchet, Jing Dong
Publication date
2012/4/9
Journal
ACM SIGMETRICS Performance Evaluation Review
Volume
39
Issue
4
Pages
35-35
Publisher
ACM

This paper surveys recent techniques that have been developed for rare-event analysis of stochastic systems via simulation. We review standard (state-independent) techniques that take advantage of large deviations results for the design of efficient importance sampling estimators. Classical examples and counter-examples are discussed to illustrate the reach and limitations of the state-independent approach. Then we move to state-dependent techniques. These techniques can be applied to both light and heavy-tailed systems and are based on subsolutions (see e.g. Dupuis and Wang (2004) [5], Dupuis and Wang (2007) [6], Dupuis and Wang (2009) [80], Dupuis et al. (2007) [7]) and Lyapunov bounds (Blanchet and Glynn (2008) [9], Blanchet et al. (2007) [11], Blanchet (2009) [12]). We briefly review the ideas behind these techniques, and provide several examples in which they are applicable.

Authors: Jose Blanchet, Henry Lam
Publication date: 2012/1/1
Source: Surveys in Operations Research and Management Science
Volume: 17
Issue: 1
Pages: 38-59
Publisher: Elsevier

Exact sampling of loss systems is important in evaluating system performance. We are interested in designing a series of algorithms that allow us to obtain perfect sampling of these systems in steady state.
In this paper, we develop an exact sampling algorithm to simulate steady state infinite server queues, multi-server loss queues and loss networks. Our method is a derivation from the coupling from the past algorithm. The key is to identify a sequence of coupling times and simulate the process backward in time accordingly. In order to simulate the loss system, we use a coupled infinite server system as a dominating process. We then define the coupling time using the same idea as in [Blanchet and Lam]. This dominated coupling from the past algorithm is shown to be efficient in the asymptotic quality driven regime.

Authors
Jose Blanchet, Jing Dong
Publication date
2012
Publisher
preparation

Authors
Jose Blanchet, Henry Lam
Publication date
2011/12/11
Conference
Proceedings of the 2011 Winter Simulation Conference (WSC)
Pages
3812-3823
Publisher
IEEE
Description
We explore a bottom-up approach to revisit the problem of cash flow modeling in insurance business, and propose a methodology to efficiently simulate the related tail quantities, namely the fixed-time and the finite-horizon ruin probabilities. Our model builds upon the micro-level contract structure issued by the insurer, and aims to capture the bankruptcy risk exhibited by the aggregation of policyholders. This distinguishes from traditional risk theory that uses random-walk-type model, and also enhances risk evaluation in actuarial pricing practice by incorporating the dynamic arrivals of policyholders in emerging cost analysis. The simulation methodology relies on our model's connection to infinite-server queues with non-homogeneous cost under heavy traffic. We will construct a sequential importance sampler with provable efficiency, along with large deviations asymptotics.

We consider a model of an irreducible network in which each node is subjected to a random demand, where the demands are jointly normally distributed. Each node has a given supply that it uses to try to meet its demand; if it cannot, the node distributes its unserved demand equally to its neighbors, which in turn do the same. The equilibrium is determined by solving a linear program (LP) to minimize the sum of the unserved demands across the nodes in the network. One possible application of the model might be the distribution of electricity in an electric power grid. This paper considers estimating the probability that the optimal objective function value of the LP exceeds a large threshold, which is a rare event. We develop a conditional Monte Carlo algorithm for estimating this probability, and we provide simulation results indicating that our method can significantly improve statistical efficiency.

Authors
Jose Blanchet, Juan Li, Marvin K Nakayama
Publication date
2011/12/11
Conference
Proceedings of the 2011 Winter Simulation Conference (WSC)
Pages
3832-3843
Publisher
IEEE

Importance sampling in the setting of heavy tailed random variables has generally focused on models with additive noise terms. In this work we extend this concept by considering importance sampling for the estimation of rare events in Markov chains of the form equation where the B n 's and A n 's are independent sequences of independent and identically distributed (i.i.d.) random variables and the B n 's are regularly varying and the A n 's are suitably light tailed relative to B n . We focus on efficient estimation of the rare event probability P(X n >; b) as b↗∞. In particular we present a strongly efficient importance sampling algorithm for estimating these probabilities, and present a numerical example showcasing the strong efficiency.

Authors
Jose Blanchet, Henrik Hult, Kevin Leder
Publication date
2011/12/11
Conference
Proceedings of the 2011 Winter Simulation Conference (WSC)
Pages
3824-3831
Publisher
IEEE

The cross entropy method is a popular technique that has been used in the context of rare event simulation in order to obtain a good selection (in the sense of variance performance tested empirically) of an importance sampling distribution. This iterative method requires the selection of a suitable parametric family to start with. The selection of the parametric family is very important for the successful application of the method. Two properties must be enforced in such a selection. First, subsequent updates of the parameters in the iterations must be easily computable and, second, the parametric family should be powerful enough to approximate, in some sense, the zero-variance importance sampling distribution. We obtain parametric families for which these two properties are satisfied for a large class of heavy-tailed systems including Pareto and Weibull tails. Our estimators are shown to be strongly efficient in these …

Authors
Jose Blanchet, Yixi Shi
Publication date
2011/12/11
Conference
Proceedings of the 2011 Winter Simulation Conference (WSC)
Pages
516-527
Publisher
IEEE

Classical Edgeworth expansions provide asymptotic correction terms to the Central Limit Theorem (CLT) up to an order that depends on the number of moments available. In this paper, we provide subsequent correction terms beyond those given by a standard Edgeworth expansion in the general case of regularly varying distributions with diverging moments (beyond the second). The subsequent terms can be expressed in a simple closed form in terms of certain special functions (Dawson’s integral and parabolic cylinder functions), and there are qualitative differences depending on whether the number of moments available is even, odd, or not an integer, and whether the distributions are symmetric or not. If the increments have an even number of moments, then additional logarithmic corrections must also be incorporated in the expansion parameter. An interesting feature of our correction terms for the CLT …

Authors
Henry Lam, Jose Blanchet, Damian Burch, Martin Z Bazant
Publication date
2011/12
Journal
Journal of Theoretical Probability
Volume
24
Pages
895-927
Publisher
Springer US

We consider a standard splitting algorithm for the rare-event simulation of overflow probabilities in any subset of stations in a Jackson network at level n, starting at a fixed initial position. It was shown in [8] that a subsolution to the Isaacs equation guarantees that a subexponential number of function evaluations (in n) suffices to estimate such overflow probabilities within a given relative accuracy. Our analysis here shows that in fact O(n2βV + 1) function evaluations suffice to achieve a given relative precision, where βV is the number of bottleneck stations in the subset of stations under consideration in the network. This is the first rigorous analysis that favorably compares splitting against directly computing the overflow probability of interest, which can be evaluated by solving a linear system of equations with O(nd) variables.

Authors
Jose Blanchet, Kevin Leder, Yixi Shi
Publication date
2011/11
Journal
Stochastic Systems
Volume
1
Issue
2
Pages
306-339
Publisher
INFORMS

We consider the problem of efficient estimation of tail probabilities of sums of correlated lognormals via simulation. This problem is motivated by the tail analysis of portfolios of assets driven by correlated Black-Scholes models. We propose two estimators that can be rigorously shown to be efficient as the tail probability of interest decreases to zero. The first estimator, based on importance sampling, involves a scaling of the whole covariance matrix and can be shown to be asymptotically optimal. A further study, based on the Cross-Entropy algorithm, is also performed in order to adaptively optimize the scaling parameter of the covariance. The second estimator decomposes the probability of interest in two contributions and takes advantage of the fact that large deviations for a sum of correlated lognormals are (asymptotically) caused by the largest increment. Importance sampling is then applied to each of …

Authors
Søren Asmussen, José Blanchet, Sandeep Juneja, Leonardo Rojas-Nandayapa
Publication date
2011/9/1
Journal
Annals of Operations Research
Volume
189
Issue
1
Pages
5-23
Publisher
Springer US

We study asymptotically optimal simulation algorithms for approximating the tail probability of P(eX1+⋯+ eXd>u) as u→∞. The first algorithm proposed is based on conditional Monte Carlo and assumes that (X1,…,Xd) has an elliptical distribution with very mild assumptions on the radial component. This algorithm is applicable to a large class of models in finance, as we demonstrate with examples. In addition, we propose an importance sampling algorithm for an arbitrary dependence structure that is shown to be asymptotically optimal under mild assumptions on the marginal distributions and, basically, that we can simulate efficiently (X1,…,Xd|Xj >b) for large b. Extensions that allow us to handle portfolios of financial options are also discussed.

Authors
Jose H Blanchet, Leonardo Rojas-Nandayapa
Publication date
2011/8
Journal
Journal of Applied Probability
Volume
48
Issue
A
Pages
147-164
Publisher
Cambridge University Press

A stochastic perpetuity takes the form D∞=∑n=0∞ exp(Y1+⋯+Yn)Bn, where Yn:n≥0) and (Bn:n≥0) are two independent sequences of independent and identically distributed random variables (RVs). This is an expression for the stationary distribution of the Markov chain defined recursively by Dn+1=AnDn+Bn, n≥0, where An=eYn; D∞ then satisfies the stochastic fixed-point equation D∞D̳AD∞+B, where A and B are independent copies of the An and Bn (and independent of D∞ on the right-hand side). In our framework, the quantity Bn, which represents a random reward at time n, is assumed to be positive, unbounded with EBnp 0, and have a suitably regular continuous positive density. The quantity Yn is assumed to be light tailed and represents a discount rate from time n to n-1. The RV D∞ then represents the net present value, in a stochastic economic environment, of an infinite stream of …

Authors
Jose H Blanchet, Karl Sigman
Publication date
2011/8
Journal
Journal of Applied Probability
Volume
48
Issue
A
Pages
165-182
Publisher
Cambridge University Press

We consider a model of an irreducible network in which each node is subjected to a random demand, where the demands are jointly normally distributed. Each node has a given supply that it uses to try to meet its demand; if it cannot, the node distributes its unserved demand equally to its neighbors, which in turn do the same. The equilibrium is determined by solving a linear program (LP) to minimize the sum of the unserved demands across the nodes in the network. One possible application of the model might be the distribution of electricity in an electric power grid. This paper considers estimating the probability that the optimal objective function value of the LP exceeds a large threshold, which is a rare event. We develop a conditional Monte Carlo algorithm for estimating this probability, and we provide simulation results indicating that our method can significantly improve statistical efficiency.

Authors
Jose Blanchet, Juan Li

The Bernoulli Factory is an algorithm that takes as input a series of i.i.d. Bernoulli random variables with an unknown but fixed success probability , and outputs a corresponding series of Bernoulli random variables with success probability , where the function is known and defined on the interval . While several practical uses of the method have been proposed in Monte Carlo applications, these require an implementation framework that is flexible, general and efficient. We present such a framework for functions that are either strictly linear, concave, or convex on the unit interval using a series of envelope functions defined through a cascade, and show that this method not only greatly reduces the number of input bits needed in practice compared to other currently proposed solutions for more specific problems, and is easy to specify for simple forms, but can easily be coupled to asymptotically efficient methods to allow for theoretically strong results.

Authors
Andrew C Thomas, Jose H Blanchet
Publication date
2011/6/13
Journal
arXiv preprint arXiv:1106.2508

We consider the problem of estimating the probability that the maximum of a Gaussian process with negative mean and indexed by positive integers reaches a high level, say b. In great generality such a probability converges to 0 exponentially fast in a power of b. Under mild assumptions on the marginal distributions of the process and no assumption on the correlation structure, we develop an importance sampling procedure, called the target bridge sampler (TBS), which takes a polynomial (in b) number of function evaluations to achieve a small relative error. The procedure also yields samples of the underlying process conditioned on hitting b in finite time. In addition, we apply our method to the problem of estimating the tail of the maximum of a superposition of a large number, n, of independent Gaussian sources. In this situation TBS achieves a prescribed relative error with a bounded number of function …
Authors
Jose Blanchet, Chenxin Li
Publication date
2011/6
Journal
Journal of Applied Probability
Volume
48
Issue
2
Pages
467-489
Publisher
Cambridge University Press

Two of the most popular approximations for the distribution of the steady-state waiting time, W∞, of the M/G/1 queue are the so-called heavy-traffic approximation and heavy-tailed asymptotic, respectively. If the traffic intensity, ρ, is close to 1 and the processing times have finite variance, the heavy-traffic approximation states that the distribution of W∞ is roughly exponential at scale O((1 − ρ)−1), while the heavy tailed asymptotic describes power law decay in the tail of the distribution of W∞ for a fixed traffic intensity. In this paper, we assume a regularly varying processing time distribution and obtain a sharp threshold in terms of the tail value, or equivalently in terms of (1 − ρ), that describes the point at which the tail behavior transitions from the heavy-traffic regime to the heavy-tailed asymptotic. We also provide new approximations that are either uniform in the traffic intensity, or uniform on the positive axis, that …

Authors
Mariana Olvera-Cravioto, Jose Blanchet, Peter Glynn
Publication date
2011/4/1
Volume
21
Issue
2
Pages
645-668

We develop an efficient importance sampling algorithm for estimating the tail distribution of heavy-tailed compound sums, that is, random variables of the form SM=Z1+…+ZM where the Zi's are independently and identically distributed (i.i.d.) random variables in R and M is a nonnegative, integer-valued random variable independent of the Zi's. We construct the first estimator that can be rigorously shown to be strongly efficient only under the assumption that the Zi's are subexponential and M is light-tailed. Our estimator is based on state-dependent importance sampling and we use Lyapunov-type inequalities to control its second moment. The performance of our estimator is empirically illustrated in various instances involving popular heavy-tailed models.

Authors
Jose Blanchet, Chenxin Li
Publication date
2011/2/18
Journal
ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume
21
Issue
2
Pages
1-23
Publisher
ACM

In this paper we develop efficient Monte Carlo methods for large credit portfolios. We assume the default indicators admit a Gaussian copula. Therefore, we are able to embed the default correlations into a continuous Gaussian random field, which is capable of incorporating an infinite size portfolio and potentially highly correlated defaults. We are particularly interested in estimating the expectations, such as the expected number of defaults given that there is at least one default and the expected loss given at least one default. All these quantities turn out to be closely related to the geometric structure of the random field. We will heavily employ random field techniques to construct importance sampling based estimators and provide rigorous efficiency analysis.

Authors
Jose H Blanchet, Jingchen Liu, Xuan Yang
Publication date
2010/12/5
Conference
Proceedings of the 2010 Winter Simulation Conference
Pages
2810-2820
Publisher
IEEE

We consider asymptotic expansions for defective and excessive renewal equations that are close to being proper. These expansions are applied to the analysis of processor sharing queues and perturbed risk models, and yield approximations that can be useful in applications where moments are computable, but the distribution is not.

Authors
Jose Blanchet, Bert Zwart
Publication date
2010/10
Journal
Mathematical Methods of Operations Research
Volume
72
Pages
311-326
Publisher
Springer-Verlag

We propose a class of strongly efficient rare-event simulation estimators for random walks and compound Poisson processes with a regularly varying increment/jump-size distribution in a general large deviations regime. Our estimator is based on an importance sampling strategy that hinges on a recently established heavy-tailed sample-path large deviations result. The new estimators are straightforward to implement and can be used to systematically evaluate the probability of a wide range of rare events with bounded relative error. They are “universal” in the sense that a single importance sampling scheme applies to a very general class of rare events that arise in heavy-tailed systems. In particular, our estimators can deal with rare events that are caused by multiple big jumps (therefore, beyond the usual principle of a single big jump) as well as multidimensional processes such as the buffer content process of a …

Authors
Bohan Chen, Jose Blanchet, Chang-Han Rhee, Bert Zwart
Publication date
2019/8
Journal
Mathematics of Operations Research
Volume
44
Issue
3
Pages
919-942
Publisher
INFORMS

In this paper we develop efficient Monte Carlo methods for large credit portfolios. We assume the default indicators admit a Gaussian copula. Therefore, we are able to embed the default correlations into a continuous Gaussian random field, which is capable of incorporating an infinite size portfolio and potentially highly correlated defaults. We are particularly interested in estimating the expectations, such as the expected number of defaults given that there is at least one default and the expected loss given at least one default. All these quantities turn out to be closely related to the geometric structure of the random field. We will heavily employ random field techniques to construct importance sampling based estimators and provide rigorous efficiency analysis.

Authors
Jose H Blanchet, Jingchen Liu, Xuan Yang

Eh cient Simulation for Rare Events Page 1 Eh cient Simulation for Rare Events Jose Blanchet Columbia Department of IEOR Lunteren Conference 2010 Blanchet (Columbia) Monte Carlo and Rare Events 1 / 43 Page 2 Agenda Introduction A Simple Random Walk Example Systematic Approach Testing Eh ciency Counter%examples, Heavy%tails and Beyond Blanchet (Columbia) Monte Carlo and Rare Events 2 / 43 Page 3 Rare Event Analysis: Areas of Applicability Rare events are consequential in many areas Insurance / Finance Blanchet (Columbia) Monte Carlo and Rare Events 3 / 43 Page 4 Rare Event Analysis: Areas of Applicability Rare events are consequential in many areas Insurance / Finance Congestion models (queues) Blanchet (Columbia) Monte Carlo and Rare Events 3 / 43 Page 5 Rare Event Analysis: Areas of Applicability Rare events are consequential in many areas Insurance / Finance …

Authors
Jose Blanchet

We consider the problem of efficient estimation via simulation of first passage time probabilities for a multidimensional random walk with heavy-tailed increments. In addition to being a natural generalization to the problem of computing ruin probabilities in insurance - in which the focus is the maximum of a one-dimensional random walk with negative drift - this problem captures important features of large deviations for multidimensional heavy-tailed processes (such as the role played by the mean of the process in connection to the location of the target set). We develop a state-dependent importance sampling estimator for this class of multidimensional problems. Then, using techniques based on Lyapunov inequalities, we argue that our estimator is strongly efficient in the sense that the relative mean squared error of our estimator can be made arbitrarily small by increasing the number of replications, uniformly as the …

Authors
Jose Blanchet, Jingchen Liu
Publication date
2010/6
Journal
Journal of Applied Probability
Volume
47
Issue
2
Pages
301-322
Publisher
Cambridge University Press

One shortcoming of utilizing the conditional mixture algorithm is the necessity to sample from the conditional distribution. A natural way to get around that is to utilize a scaling based approach introduced in [Hult and Svensson 2012]. When simulating Bj+ 1 given that Xj= x the following sampling density is used, where a∈(0, 1), gS Bj+ 1 (y| x)

Authors
JOSE BLANCHET, HENRIK HULT, KEVIN LEDER

The asymptotic robustness of estimators as a function of a rarity parameter, in the context of rare-event simulation, is often qualified by properties such as bounded relative error (BRE) and logarithmic efficiency (LE), also called asymptotic optimality. However, these properties do not suffice to ensure that moments of order higher than one are well estimated. For example, they do not guarantee that the variance of the empirical variance remains under control as a function of the rarity parameter. We study generalizations of the BRE and LE properties that take care of this limitation. They are named bounded relative moment of order k (BRM-k) and logarithmic efficiency of order k (LE-k), where k ≥ 1 is an arbitrary real number. We also introduce and examine a stronger notion called vanishing relative centered moment of order k, and exhibit examples where it holds. These properties are of interest for various estimators …

Authors: Pierre L'ecuyer, Jose H Blanchet, Bruno Tuffin, Peter W Glynn
Publication date: 2010/2/8
Journal: ACM Transactions on Modeling and Computer Simulation (TOMACS)
Volume: 20
Issue: 1
Pages: 1-41
Publisher: ACM

In this paper we study rare event simulation for the tail probability of an affine point process (J t ) t¿0 that generalizes the Hawkes process. By constructing a suitable exponential martingale, we are able to construct an importance sampling algorithm that is logarithmically efficient in the Gartner-Ellis asymptotic regime.

Authors
Xiao-Wei Zhang, Peter W Glynn, Kay Giesecke, Jose Blanchet
Publication date
2009/12/13
Conference
Proceedings of the 2009 Winter Simulation Conference (WSC)
Pages
1291-1298
Publisher
IEEE

We develop rare event simulation methodology for the tail of a perpetuity driven by a continuous time Markov chain. We present a state-dependent importance sampling estimator in continuous time that can be shown to be asymptotically optimal in the context of small interest rates.

Authors
Jose Blanchet, Peter Glynn
Publication date
2009/12/13
Conference
Proceedings of the 2009 Winter Simulation Conference (WSC)
Pages
444-451
Publisher
IEEE

This paper develops a rare-event simulation algorithm for a discrete-time version of the M/G/s loss system and a related Markov-modulated variant of the same loss model. The algorithm is shown to be efficient in the many-server asymptotic regime in which the number of servers and the arrival rate increase to infinity in fixed proportion. A key idea is to study the system as a measure-valued Markov chain and to steer the system to the rare event through a randomization of the time horizon over which the rare event is induced.

Authors
Jose Blanchet, Peter Glynn, Henry Lam
Publication date
2009/12
Journal
Queueing Systems
Volume
63
Pages
33-57
Publisher
Springer US

We revisit a classical problem in rare-event simulation, namely, efficient estimation of the probability that the sample mean of n independent identically distributed light tailed (i.e. with finite moment generating function in a neighborhood of the origin) random variables lies in a sufficiently regular closed convex set that does not contain their mean. It is well known that the optimal exponential tilting (OET), although logarithmically efficient, is not strongly efficient (typically, the squared coefficient of variation of the estimator grows at rate n 1/2). After discussing some important differences between the optimal change of measure and OET (for instance, in the one dimensional case the size of the overshoot is bounded for the optimal importance sampler and of order O(n 1/2) for OET) that indicate why OET is not strongly efficient, we provide a state-dependent importance sampling that can be proved to …

Authors
Jose H Blanchet, Kevin Leder, Peter W Glynn
Publication date
2009/11/17
Book
Monte Carlo and Quasi-Monte Carlo Methods 2008
Pages
227-248
Publisher
Springer Berlin Heidelberg

Large deviations analysis for light-tailed systems provides an asymptotic description of the optimal importance sampler in the scaling of the Law of Large Numbers. As we will show by means of a simple example related to computational finance, such asymptotic description can be interpreted indifferent ways suggesting several importance sampling algorithms, some of them state-dependent. In turn, the performance of the suggested algorithms can be substantially different.

Authors
Jose Blanchet, Jingchen Liu, Peter Glynn
Publication date
2006/10/11
Book
Proceedings of the 1st international conference on Performance evaluation methodolgies and tools
Pages
20-es

Importance sampling has been reported to produce algorithms with excellent empirical performance in counting problems. However, the theoretical support for its efficiency in these applications has been very limited. In this paper, we propose a methodology that can be used to design efficient importance sampling algorithms for counting and test their efficiency rigorously. We apply our techniques after transforming the problem into a rare-event simulation problem—thereby connecting complexity analysis of counting problems with efficiency in the context of rare-event simulation. As an illustration of our approach, we consider the problem of counting the number of binary tables with fixed column and row sums, cj’s and ri’s, respectively, and total marginal sums d=∑jcj. Assuming that max jcj=o(d1/2), ∑cj2=O(d) and the rj’s are bounded, we show that a suitable importance sampling algorithm, proposed by Chen …

Authors
Jose H Blanchet
Publication date
2009/6/1
Volume
19
Issue
3
Pages
949-982

Randomized approximation algorithms for counting problems have been the subject of many papers and monographs in theoretical computer science (see [13, 15, 25, 26]). At the same time, rare event simulation methodology has a long history of development within the applied probability and operations research communities. In this chapter, we offer a primer on the subject of approximate counting using rare event simulation techniques, thereby connecting two distinct points of view. The use of rare event simulation techniques for counting is very recent (see [5, 22]) and we hope that this chapter will motivate researchers in the rare event simulation community to consider the types of problems that we will discuss. Our focus, consequently, is on the theoretical properties of randomized approximation algorithms for counting and their connections to rare event simulation. Even though powerful heuristic algorithms …

Authors
José Blanchet, Daniel Rudoy
Publication date
2009/3/20
Journal
Rare Event Simulation Using Monte Carlo Methods
Pages
171-192
Publisher
John Wiley & Sons, Ltd

This chapter describes state-of-the-art techniques in rare event simulation for queuing systems, the rare events under consideration being overflow probabilities, probabilities of extremely long delays, etc. We first consider a number of generic examples (and counterexamples) that are very useful in the queuing context. Then we systematically assess importance sampling for the cases of light-tailed input (where large-deviations arguments play a crucial role) and heavy-tailed input (where the change of measure is typically state-dependent). Other issues dealt with are: results under the many-sources scaling, estimation of the tail of the sojourn time distribution for processor-sharing queues, tandem and intree networks, and loss networks.

Authors
José Blanchet, Michel Mandjes
Publication date
2009/3/20
Journal
Rare Event Simulation Using Monte Carlo Methods
Pages
87-124
Publisher
John Wiley & Sons, Ltd

We consider the problem of effi cient estimation via simulation of first passage time probabilities for a multidimensional random walk with regularly varying increments. In addition of being a natural gen# eralization of the problem of computing ruin probabilities in insurance nin which the focus is a one dimensional random walk nthis problem captures important features of large deviations for multidimensional heavy# tailed processes (such as the role played by the mean of the process in connection to the location of the target set). We develop a state# dependent importance sampling estimator for this class of mul# tidimensional problems. Then, we argue using techniques based on Lyapunov inequalities that our estimator is strongly effi cient in the sense that the mean square error of our estimator can be made ar# bitrarily small by increasing the number of replications, uniformly as the probability of interest approaches zero. An important feature of our algorithm involves the interplay between large deviations for reg# ularly varying processes and linear programming. When the target set is the union of half# spaces, our sampler, which can be described in terms of mixtures, can be shown to approximate in total variation the conditional distribution of the walk given that it hits the target set in finite time.

Authors
Jose Blanchet, Jingchen Liu
Publication date
2009/1

Consider a sequence (Xk: k ≥ 0) of regularly varying independent and identically distributed random variables with mean 0 and finite variance. We develop efficient rare-event simulation methodology associated with large deviation probabilities for the random walk (Sn: n ≥ 0). Our techniques are illustrated by examples, including large deviations for the empirical mean and path-dependent events. In particular, we describe two efficient state-dependent importance sampling algorithms for estimating the tail of Sn in a large deviation regime as n ↗ ∞. The first algorithm takes advantage of large deviation approximations that are used to mimic the zero-variance change of measure. The second algorithm uses a parametric family of changes of measure based on mixtures. Lyapunov-type inequalities are used to appropriately select the mixture parameters in order to guarantee bounded relative error (or efficiency) of the …

Authors: Jose H Blanchet, Jingchen Liu
Publication date: 2008/12
Journal: Advances in Applied Probability
Volume: 40
Issue: 4
Pages: 1104-1128
Publisher: Cambridge University Press

Our focus is on efficient estimation of tail probabilities of sums of correlated lognormals. This problem is motivated by the tail analysis of portfolios of assets driven by correlated Black-Scholes models. We propose three different procedures that can be rigorously shown to be asymptotically optimal as the tail probability of interest decreases to zero. The first algorithm is based on importance sampling and is as easy to implement as crude Monte Carlo. The second algorithm is based on an elegant conditional Monte Carlo strategy which involves polar coordinates and the third one is an importance sampling algorithm that can be shown to be strongly efficient.

Authors
Jose Blanchet, Sandeep Juneja, Leonardo Rojas-Nandayapa
Publication date
2008/12/7
Conference
2008 Winter Simulation Conference
Pages
607-614
Publisher
IEEE

We consider the problem of selecting the best among several heavy-tailed systems using a large deviations perspective. In contrast to the light-tailed setting studied by Glynn and Juneja (2004), in the heavy-tailed setting, the probability of false selection is characterized by a rate function that does not require as detailed information about the probability distributions of the system's performance. This motivates the question of studying static policies that could potentially provide convenient implementable in heavy-tailed settings. We concentrate in studying sharp large deviations estimates for the probability of false detection which suggest precise optimal allocation policies when the systems have comparable heavy-tails. Additional optimality insights are given for systems with non-comparable tails.

Authors
Jose Blanchet, Jingchen Liu, Bert Zwart
Publication date
2008/12/7
Conference
2008 Winter Simulation Conference
Pages
489-494
Publisher
IEEE

We are interested in computing tail probabilities for the maxima of Gaussian random fields. In this paper, we discuss two special cases: random fields defined over a finite number of distinct point and fields with finite Karhunen-Loeve expansions. For the first case we propose an importance sampling estimator which yields asymptotically zero relative error. Moreover, it yields a procedure for sampling the field conditional on it having an excursion above a high level with a complexity that is uniformly bounded as the level increases. In the second case we propose an estimator which is asymptotically optimal. These results serve as a first step analysis of rare-event simulation for Gaussian random fields.

Authors
Robert J Adler, Jose Blanchet, Jingchen Liu
Publication date
2008/12/7
Conference
2008 Winter Simulation Conference
Pages
328-336
Publisher
IEEE

Let (Xn : n≥0) be a sequence of i.i.d. r.v.’s with negative mean. Set S0=0 and define Sn=X1+⋯+Xn. We propose an importance sampling algorithm to estimate the tail of M=max {Sn : n≥0} that is strongly efficient for both light and heavy-tailed increment distributions. Moreover, in the case of heavy-tailed increments and under additional technical assumptions, our estimator can be shown to have asymptotically vanishing relative variance in the sense that its coefficient of variation vanishes as the tail parameter increases. A key feature of our algorithm is that it is state-dependent. In the presence of light tails, our procedure leads to Siegmund’s (1979) algorithm. The rigorous analysis of efficiency requires new Lyapunov-type inequalities that can be useful in the study of more general importance sampling algorithms.

Authors: Jose Blanchet, Peter Glynn
Publication date: 2008/8/1
Volume: 18
Issue: 4
Pages: 1351-1378

Proceedings of the Eighth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2008). Springer, Berlin

Authors
J Blanchet, K Leder, P Glynn
Publication date
2008

This paper develops an effi cient importance sampling algorithm for comput $ ing steady $ state tail probabilities for customer waiting times in a G/G/2 queue in which the service time requirements are heavy $ tailed random variables. Un $ der appropriate regularity conditions, we prove that our estimator has bounded relative variance whenever the rate at which work arrives to the system is less than 2 (but not equal to one). The argument hinges on the construction of an appropriate Lyapunov function that can be used to bound the second moment of our estimator. The construction followed here uses fluid heuiristics to guess the form of the Lyapunov function, after which tuning constants that define the algorithmic implementation are then chosen in order to force the function to satisfy the required Lyapunov inequality. In addition, the Lyapunov function can be used to obtain upper bounds for large deviation probabilities; thereby not only allowing to study the performance of the algorithm but also provide large deviations estimates. Our approach takes advantage of the regenerative representation for the steady $ state distribution. We therefore also discuss the use of importance sampling, and related effi ciency issues, in conjunction with regenerative steady $ state simulation.

Authors
J Blanchet, P Glynn, J Liu
Publication date
2008
Journal
Department of Statistics, Columbia University

Compounding processes, also known as perpetuities, play an important role in many applications; in particular, in time series analysis and mathematical finance. Apart from some special cases, the distribution of a perpetuity is hard to compute, and large deviations estimates sometimes involve complicated constants which depend on the complete distribution. Motivated by this, we propose provably efficient importance sampling algorithms which apply to qualitatively different cases, leading to light and heavy tails. Both algorithms have the non-standard feature of being state-dependent. In addition, in order to verify the efficiency, we apply recently developed techniques based on Lyapunov inequalities.

Authors
Jose Blanchet, Bert Zwart
Publication date
2007/12/9
Conference
2007 Winter Simulation Conference
Pages
372-379
Publisher
IEEE

State-dependent importance sampling (SDIS) has proved to be particularly useful in simulation (specially in rare event analysis of stochastic systems). One approach for designing SDIS is to mimic the zero-variance change-of-measure by using a likelihood ratio that is proportional to an asymptotic approximation that may be available for the problem at hand. Using such approximation poses the problem of computing the corresponding normalizing constants at each step. In this paper, we propose the use of path-sampling, which allows to estimate such normalizing constants in terms of one dimensional integrals. We apply path-sampling to estimate the tail of the delay in a G/G/1 queue with regularly varying input. We argue that such tail estimation can be performed with good relative precision in quadratic complexity (in terms of the tail parameter) - assuming that path-sampling is combined with an appropriate …

Authors
Jose H Blanchet, Jingchen Liu
Publication date
2007/12/9
Conference
2007 Winter Simulation Conference
Pages
380-388
Publisher
IEEE

Much of the rare-event simulation literature is concerned with the development of asymptotically optimal algorithms. Because of the difficulties associated with applying these ideas to complex models, this paper focuses on sub-optimal procedures that can be shown to be much more efficient than conventional crude Monte Carlo. We provide two such examples, one based on "repeated acceptance/rejection" as a mean of computing tail probabilities for hitting time random variables and the other based on filtered conditional Monte Carlo.

Authors
Xiaowei Zhang, Jose Blanchet, Peter W Glynn
Publication date
2007/12/9
Conference
2007 Winter Simulation Conference
Pages
389-394
Publisher
IEEE

We consider the problem of efficient estimation of first passage time probabilities for a multidimensional random walk with t distributed increments, via simulation. In addition of being a natural generalization of the problem of computing ruin probabilities in insurance - in which the focus is a one dimensional random walk - this problem captures important features of large deviations for multidimensional heavy-tailed processes (such as the role played by the mean of the random walk in connection to the spatial location of the target set). We develop a state-dependent importance sampling estimator for this class of multidimensional problems. Then, we argue - using techniques based on Lyapunov type inequalities - that our estimator is strongly efficient.

Authors
Jose H Blanchet, Jingchen Liu
Publication date
2007/12/9
Conference
2007 Winter Simulation Conference
Pages
395-402
Publisher
IEEE

Consider a sequence X = (Xn: n ≥ 1) of independent and identically distributed random variables, and an independent geometrically distributed random variable M with parameter p. The random variable SM = X1 + ∙ ∙ ∙ + XM is called a geometric sum. In this paper we obtain asymptotic expansions for the distribution of SM as p ↘ 0. If EX1 > 0, the asymptotic expansion is developed in powers of p and it provides higher-order correction terms to Renyi's theorem, which states that P(pSM > x) ≈ exp(-x/EX1). Conversely, if EX1 = 0 then the expansion is given in powers of √p. We apply the results to obtain corrected diffusion approximations for the M/G/1 queue. These expansions follow in a unified way as a consequence of new uniform renewal theory results that are also developed in this paper.

Authors
J Blanchet, P Glynn
Publication date
2007/12
Journal
Advances in Applied Probability
Volume
39
Issue
4
Pages
1070-1097
Publisher
Cambridge University Press

We develop a strongly efficient rare-event simulation algorithm for computing the tail of the steady-state waiting time in a single server queue with regularly varying service times. Our algorithm is based on a state-dependent importance sampling strategy that is constructed so as to be straightforward to implement. The construction of the algorithm and its asymptotic optimality rely on a Lyapunov-type inequality that is used to bound the second moment of the estimator. The solution to the Lyapunov inequality is constructed using fluid heuristics. Our approach takes advantage of the regenerative ratio formula for the steady-state distribution—and does not use the first passage time representation that is particular to the delay in the G/G/1 queue. Hence, the strategy has the potential to be applied in more general queueing models.

Authors
José Blanchet, Peter Glynn, Jingchen C Liu
Publication date
2007/11
Journal
Queueing Systems
Volume
57
Pages
99-113
Publisher
Springer US

Methods using regeneration have been used to draw approximations to the stationary distribution of Markov Chain Monte Carlo processes. We introduce an algorithm that allows exact sampling of the stationary distribution through the use of a regeneration method and a Bernoulli Factory to select samples within each regeneration cycle that are shown to be from the desired density. We demonstrate the algorithm on a probit model Markov Chain using a known data set for comparison to other approximate methods.

Authors
Jose Blanchet, Andrew C Thomas
Publication date
2007/4/13
Publisher
Technical report, Harvard University. Available at: http://www. acthomas. ca/papers/factory-sampling. pdf

This paper develops an eo cient importance sampling algorithm for comput $ ing steady $ state tail probabilities for customer waiting times in a G/G/2 queue in which the service time requirements are heavy $ tailed random variables. Un $ der appropriate regularity conditions, we prove that our estimator has bounded relative variance whenever the rate at which work arrives to the system is less than 2 (but not equal to one). The argument hinges on the construction of an appropriate Lyapunov function that can be used to bound the second moment of our estimator. The construction followed here uses fluid heuiristics to guess the form of the Lyapunov function, after which tuning constants that define the algorithmic implementation are then chosen in order to force the function to satisfy the required Lyapunov inequality. In addition, the Lyapunov function can be used to obtain upper bounds for large deviation …

Authors
J Blanchet, P Glynn, JC Liu
Publication date
2007/3

Editorial (Special issue on Rare-event simulation for queues) — Eindhoven University of Technology research portal Skip to main navigation Skip to search Skip to main content Eindhoven University of Technology research portal Home Eindhoven University of Technology research portal Logo Help & FAQ English Nederlands Home Researchers Research output Organisational Units Activities Projects Prizes Press/Media Facilities / Equipment Datasets Courses Research areas Student theses Search by expertise, name or affiliation Editorial (Special issue on Rare-event simulation for queues) J. Blanchet, MRH Mandjes Eurandom Research output: Contribution to journal › Article › Academic › peer-review 2 Citations (Scopus) Overview Fingerprint Abstract Without abstract. Original language English Pages (from-to) 57-59 Journal Queueing Systems Volume 57 Issue number 2-3 DOIs https://doi.org/10.1007/s11134-…

Authors
J Blanchet, MRH Mandjes
Publication date
2007
Journal
Queueing Systems
Volume
57
Issue
2-3
Pages
57-59
Publisher
Springer

Let (X n :n ges 0) be a sequence of iid rv's with mean zero and finite variance. We describe an efficient state-dependent importance sampling algorithm for estimating the tail of S n = X 1 + ... + X n in a large deviations framework as n - infin. Our algorithm can be shown to be strongly efficient basically throughout the whole large deviations region as n - infin (in particular, for probabilities of the form P (S n > kn) as k > 0). The techniques combine results of the theory of large deviations for sums of regularly varying distributions and the basic ideas can be applied to other rare-event simulation problems involving both light and heavy-tailed features

Authors
Jose H Blanchet, Jingchen Liu
Publication date
2006/12/3
Conference
Proceedings of the 2006 Winter Simulation Conference
Pages
757-764
Publisher
IEEE

Let (Sn : n ≥ 0) be a mean zero random walk (rw) with light-tailed increments. One of the most fundamental problems in rare-event simulation involves computing P (Sn > nβ) for β > 0 when n is large. It is well known that the optimal exponential tilting (OET), although logarithmically efficient, is not strongly efficient (the squared coefficient of variation of the estimator grows at rate n1/2). Our analysis of the zero-variance change-of-measure provides useful insights into why OET is not strongly efficient. In particular, the iid nature of OET induces an overshoot over the boundary nβ that is too big and causes the coefficient of variation to grow as [EQUATION]. We study techniques used to provide a state-dependent change-of-measure that yields a strongly efficient estimator. The application of our state-dependent algorithm to the Gaussian case reveals the fine structure of the zero-variance change-of-measure. We see how …

Authors
Jose Blanchet, Peter Glynn
Publication date
2006/10/11
Book
Proceedings of the 1st international conference on Performance evaluation methodolgies and tools
Pages
18-es

For the GI/GI/1 queue we show that the scaled queue size converges to reflected Brownian motion in a critical queue and converges to reflected Brownian motion with drift for a sequence of subcritical queuing models that approach a critical model. Instead of invoking the topological argument of the usual continuous-mapping approach, we give a probabilistic argument using Skorokhod embeddings in Brownian motion.

Authors
Erol A Peköz, Jose Blanchet
Publication date
2006/10
Journal
Probability in the Engineering and Informational Sciences
Volume
20
Issue
4
Pages
595-598
Publisher
Cambridge University Press

Consider a random walk (Sn:n≥0) with drift −μ and S0=0. Assuming that the increments have exponential moments, negative mean, and are strongly nonlattice, we provide a complete asymptotic expansion (in powers of μ>0) that corrects the diffusion approximation of the all time maximum M=maxn≥0Sn. Our results extend both the first-order correction of Siegmund [Adv. in Appl. Probab. 11 (1979) 701–719] and the full asymptotic expansion provided in the Gaussian case by Chang and Peres [Ann. Probab. 25 (1997) 787–802]. We also show that the Cramér–Lundberg constant (as a function of μ) admits an analytic extension throughout a neighborhood of the origin in the complex plane ℂ. Finally, when the increments of the random walk have nonnegative mean μ, we show that the Laplace transform, Eμexp(−bR(∞)), of the limiting overshoot, R(∞), can be analytically extended throughout a disc centered at …

Authors
Jose Blanchet, Peter Glynn
Publication date
2006/5/1
Volume
16
Issue
2
Pages
951-983

Importance sampling has been reported to produce algorithms with excellent empirical performance in counting problems. However, the theoretical support for its efficiency in these applications has been very limited. In this paper, we propose a methodology that can be used to design efficient importance sampling algorithms for counting and test their efficiency rigorously. Our techniques for complexity analysis are based on Lyapunov-type bounds for Markov chains and are specially well-suited for the analysis of state-dependent importance sampling algorithms. These techniques are applied after transforming the problem into a rare-event simulation problem–thereby connecting complexity analysis of counting problems with efficiency in the context of rare-event simulation. As an illustration of our approach, we consider the problem of counting the number of binary contingency tables with fixed column and row …

Authors
Jose Blanchet
Publication date
2006
Journal
Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

Authors
J Blanchet, P Glynn
Publication date
2006
Journal
Ann. App. Prob

0 e-Γ (t-) dΛ (t). In this paper, we develop large deviation theory for D in a context in which the accumulated discount process, Γ, is small. More precisely, in this paper we provide: 1) logarithmic large deviations that hold in great generality in both discrete and continuous time, and 2) exact asymptotics derived in the iid (independent and identically distributed) case and also in the case in which Λ is a Levy process and Γ (t) is a function of a Markov process. This setting is motivated by applications in insurance risk theory with return on investments. Our development of logarithmic asymptotics requires the study of a certain non-standard topology in order to apply contraction principles. Finally, our exact asymptotic results, although analogous to classical results for sums of iid random variables, present important qualitative differences that we also explain here.

Authors
J Blanchet, P Glynn
Publication date
2005/8
Publisher
Working paper

0 e− Γ (t−) dΛ (t) play an important role in many application settings. We develop approximations for the distribution of D when the “accumulated short rate process”, Γ, is small. We provide: 1) Characterizations for the distribution of D when Γ and Λ are driven by Markov processes; 2) General sufficient conditions under which weak convergence results can be derived for D, and 3) Edgeworth expansions for the distribution of D in the iid case and the case in which Λ is a Levy process and the interest rate is a function of an ergodic Markov process.

Authors
J Blanchet, P Glynn
Publication date
2005/7

Suppose that Χ φ (Χn: η 0) is a positive recurrent Harris chain. We investigate the connection between various types of drift and minoriza# tion conditions on Χ and exact simulation. We present an exact simula# tion algorithm that can be implemented if three elements are available: 1) We can identify the regeneration epochs of Χ, 2) We can find a pos# itive lower bound for the probability of regeneration in one step, and 3) We can find an upper bound for moments of order larger than 1 for the regeneration time of Χ. We also discuss explicit minorization and drift conditions that provide the bounds required in item 3).

Authors
J Blanchet, X Meng
Publication date
2005/6
Publisher
Technical report, Columbia University. Available at: http://www. columbia. edu/~ jb2814/papers/JSMsent. pdf

The analysis of ruin probabilities constitutes a cornerstone of insurance risk theory. This dissertation develops limit theorems and approximations that can be used to obtain the probability that an insurer faces eventual ruin in both the case of zero interest rates and when of stochastic return on investments are present. This theory is also relevant in the analysis of the single most important model in queueing theory, namely the single-server queue. Other applications to statistical sequential analysis and time series analysis are also discussed.

Authors
Jose H Blanchet
Publication date
2004
Institution
stanford university

Let (Xn: n≥ 1) be a sequence of independent and identically distributed random variables with E (X1)= 0, and let S=(Sn: n≥ 0) be its associated random walk (so that S0= 0 and Sn= X1+...+ Xn for n≥ 1). Let us introduce a small location parameter δ> 0 representing the drift of the random walk. That is, let us consider a parametric family of random walks, Sδ=(Sδ n: n≥ 0), defined by

Authors
Jose Blanchet, Peter Glynn
Publication date
2003/12