
We study an optimizationbased approach to construct statistically accurate
confidence intervals for simulation performance measures under nonparametric
input uncertainty. This approach computes confidence bounds from simulation
runs driven by probability weights defined on the data, which are obtained from
solving optimization problems under suitably posited averaged divergence
constraints. We illustrate how this approach offers benefits in computational
efficiency and finitesample performance compared to the bootstrap and the
delta method. While resembling robust optimization, we explain the procedural
design and develop tight statistical guarantees of this approach via a
generalization of the empirical likelihood method.

Any performance analysis based on stochastic simulation is subject to the
errors inherent in misspecifying the modeling assumptions, particularly the
input distributions. In situations with little support from data, we
investigate the use of worstcase analysis to analyze these errors, by
representing the partial, nonparametric knowledge of the input models via
optimization constraints. We study the performance and robustness guarantees of
this approach. We design and analyze a numerical scheme for solving a general
class of simulation objectives and uncertainty specifications. The key steps
involve a randomized discretization of the probability spaces, a simulable
unbiased gradient estimator using a nonparametric analog of the likelihood
ratio method, and a FrankWolfe (FW) variant of the stochastic approximation
(SA) method (which we call FWSA) run on the space of input probability
distributions. A convergence analysis for FWSA on nonconvex problems is
provided. We test the performance of our approach via several numerical
examples.

Effective and accurate model selection is an important problem in modern data
analysis. One of the major challenges is the computational burden required to
handle large data sets that cannot be stored or processed on one machine.
Another challenge one may encounter is the presence of outliers and
contaminations that damage the inference quality. The parallel "divide and
conquer" model selection strategy divides the observations of the full data set
into roughly equal subsets and perform inference and model selection
independently on each subset. After local subset inference, this method
aggregates the posterior model probabilities or other model/variable selection
criteria to obtain a final model by using the notion of geometric median. This
approach leads to improved concentration in finding the "correct" model and
model parameters and also is provably robust to outliers and data
contamination.

Studies on simulation input uncertainty often built on the availability of
input data. In this paper, we investigate an inverse problem where, given only
the availability of output data, we nonparametrically calibrate the input
models and other related performance measures of interest. We propose an
optimizationbased framework to compute statistically valid bounds on input
quantities. The framework utilizes constraints that connect the statistical
information of the realworld outputs with the inputoutput relation via a
simulable map. We analyze the statistical guarantees of this approach from the
view of datadriven robust optimization, and show how the guarantees relate to
the function complexity of the constraints arising in our framework. We
investigate an iterative procedure based on a stochastic quadratic penalty
method to approximately solve the resulting optimization. We conduct numerical
experiments to demonstrate our performance in bounding the input models and
related quantities.

A common bottleneck in evaluating extremal performance measures is that, due
to their very nature, tail data are often very limited. The conventional
approach selects the best probability distribution from tail data using
parametric fitting, but the validity of the parametric choice can be difficult
to verify. This paper describes an alternative based on the computation of
worstcase bounds under the geometric premise of tail convexity, a feature
shared by all common parametric tail distributions. We characterize the
optimality structure of the resulting optimization problem, and demonstrate
that the worstcase convex tail behavior is in a sense either extremely
lighttailed or extremely heavytailed. We develop lowdimensional nonlinear
programs that distinguish between the two cases and compute the worstcase
bound. We numerically illustrate how the proposed approach can give more
reliable performances than conventional parametric methods.

Evaluation and validation of complicated control systems are crucial to
guarantee usability and safety. Usually, failure happens in some very rarely
encountered situations, but once triggered, the consequence is disastrous.
Accelerated Evaluation is a methodology that efficiently tests those
rarelyoccurring yet critical failures via smartlysampled test cases. The
distribution used in sampling is pivotal to the performance of the method, but
building a suitable distribution requires casebycase analysis. This paper
proposes a versatile approach for constructing sampling distribution using
kernel method. The approach uses statistical learning tools to approximate the
critical event sets and constructs distributions based on the unique properties
of Gaussian distributions. We applied the method to evaluate the automated
vehicles. Numerical experiments show proposed approach can robustly identify
the rare failures and significantly reduce the evaluation time.

The vast majority of stochastic simulation models are imperfect in that they
fail to exactly emulate real system dynamics. The inexactness of the simulation
model, or model discrepancy, can impact the predictive accuracy and usefulness
of the simulation for decisionmaking. This paper proposes a systematic
framework to integrate data from both the simulation responses and the real
system responses to learn this discrepancy and quantify the resulting
uncertainty. Our framework addresses the theoretical and computational
requirements for stochastic estimation in a Bayesian setting. It involves an
optimizationbased procedure to compute confidence bounds on the target outputs
that elicit desirable largesample statistical properties. We illustrate the
practical value of our framework with a call center example and a manufacturing
line case study.

This paper proposes a new framework based on joint statistical models for
evaluating risks of automated vehicles in a naturalistic driving environment.
The previous studies on the Accelerated Evaluation for automated vehicles are
extended from multiindependentvariate models to joint statistics. The
proposed toolkit includes exploration of the rare event (e.g. crash) sets and
construction of accelerated distributions for Gaussian Mixture models using
Importance Sampling techniques. Furthermore, the monotonic property is used to
avoid the curse of dimensionality introduced by the joint distributions.
Simulation results show that the procedure is effective and has a great
potential to reduce the test cost for automated vehicles.

This paper discusses the use of Kriging model in Automated Vehicle
evaluation. We explore how a Kriging model can help reduce the number of
experiments or simulations in the Accelerated Evaluation procedure. We also
propose an adaptive sampling scheme for selecting samples to construct the
Kriging model. Application examples in the lane change scenario are presented
to illustrate the proposed methods.

Automated vehicles have been under heavy developments in major auto and tech
companies and are expected to release into market in the foreseeable future.
However, the road safety of these vehicles remains a concern. One approach to
evaluate their safety is via ontrack experimentation, but this requires
gigantic costs and time investments. This paper discusses a sequential learning
approach based on kriging models to reduce the experimental runs and economize
ontrack experimentation. The approach relies on a heuristic simulationbased
gradient descent procedure to search for the best next test scenario. We
demonstrate our approach with some numerical test cases.

Robust optimization (RO) is a common approach to tractably obtain
safeguarding solutions for optimization problems with uncertain constraints. In
this paper, we study a statistical framework to integrate data into RO, based
on learning a prediction set using (combinations of) geometric shapes that are
compatible with established RO tools, and a simple datasplitting validation
step that achieves finitesample nonparametric statistical guarantees on
feasibility. We demonstrate how our required sample size to achieve feasibility
at a given confidence level is independent of the dimensions of both the
decision space and the probability space governing the stochasticity, and
discuss some approaches to improve the objective performances while maintaining
these dimensionfree statistical feasibility guarantees.

The safety of Automated Vehicles (AVs) must be assured before their release
and deployment. The current approach to evaluation relies primarily on (i)
testing AVs on public roads or (ii) track testing with scenarios defined in a
test matrix. These two methods have completely opposing drawbacks: the former,
while offering realistic scenarios, takes too much time to execute; the latter,
though it can be completed in a short amount of time, has no clear correlation
to safety benefits in the real world. To avoid the aforementioned problems, we
propose Accelerated Evaluation, focusing on the carfollowing scenario. The
stochastic humancontrolled vehicle (HV) motions are modeled based on 1.3
million miles of naturalistic driving data collected by the University of
Michigan Safety Pilot Model Deployment Program. The statistics of the HV
behaviors are then modified to generate more intense interactions between HVs
and AVs to accelerate the evaluation procedure. The Importance Sampling theory
was used to ensure that the safety benefits of AVs are accurately assessed
under accelerated tests. Crash, injury and conflict rates for a simulated AV
are simulated to demonstrate the proposed approach. Results show that test
duration is reduced by a factor of 300 to 100,000 compared with the
nonaccelerated (naturalistic) evaluation. In other words, the proposed
techniques have great potential for accelerating the AV evaluation process.

The process to certify highly Automated Vehicles has not yet been defined by
any country in the world. Currently, companies test Automated Vehicles on
public roads, which is timeconsuming and inefficient. We proposed the
Accelerated Evaluation concept, which uses a modified statistics of the
surrounding vehicles and the Importance Sampling theory to reduce the
evaluation time by several orders of magnitude, while ensuring the evaluation
results are statistically accurate. In this paper, we further improve the
accelerated evaluation concept by using Piecewise Mixture Distribution models,
instead of Single Parametric Distribution models. We developed and applied this
idea to forward collision control system reacting to vehicles making cutin
lane changes. The behavior of the cutin vehicles was modeled based on more
than 403,581 lane changes collected by the University of Michigan Safety Pilot
Model Deployment Program. Simulation results confirm that the accuracy and
efficiency of the Piecewise Mixture Distribution method outperformed single
parametric distribution methods in accuracy and efficiency, and accelerated the
evaluation process by almost four orders of magnitude.

Evaluation and testing are critical for the development of Automated Vehicles
(AVs). Currently, companies test AVs on public roads, which is very
timeconsuming and inefficient. We proposed the Accelerated Evaluation concept
which uses a modified statistics of the surrounding vehicles and the Importance
Sampling theory to reduce the evaluation time by several orders of magnitude,
while ensuring the final evaluation results are accurate. In this paper, we
further extend this idea by using Piecewise Mixture Distribution models instead
of Single Distribution models. We demonstrate this idea to evaluate vehicle
safety in lane change scenarios. The behavior of the cutin vehicles was
modeled based on more than 400,000 naturalistic driving lane changes collected
by the University of Michigan Safety Pilot Model Deployment Program. Simulation
results confirm that the accuracy and efficiency of the Piecewise Mixture
Distribution method are better than the single distribution.

We study the empirical likelihood approach to construct confidence intervals
for the optimal value and the optimality gap of a given solution, henceforth
quantify the statistical uncertainty of sample average approximation, for
optimization problems with expected value objectives and constraints where the
underlying probability distributions are observed via limited data. This
approach relies on two distributionally robust optimization problems posited
over the uncertain distribution, with a divergencebased uncertainty set that
is suitably calibrated to provide asymptotic statistical guarantees.

Procedures in assessing the impact of serial dependency on performance
analysis are usually built on parametrically specified models. In this paper,
we propose a robust, nonparametric approach to carry out this assessment, by
computing the worstcase deviation of the performance measure due to arbitrary
dependence. The approach is based on optimizations, posited on the model space,
that have constraints specifying the level of dependency measured by a
nonparametric distance to some nominal i.i.d. input model. We study
approximation methods for these optimizations via simulation and
analysisofvariance (ANOVA). Numerical experiments demonstrate how the
proposed approach can discover the hidden impacts of dependency beyond those
revealed by conventional parametric modeling and correlation studies.

Automated vehicles (AVs) must be evaluated thoroughly before their release
and deployment. A widelyused evaluation approach is the NaturalisticField
Operational Test (NFOT), which tests prototype vehicles directly on the public
roads. Due to the low exposure to safetycritical scenarios, NFOTs are
timeconsuming and expensive to conduct. In this paper, we propose an
accelerated evaluation approach for AVs. The results can be used to generate
motions of the primary other vehicles to accelerate the verification of AVs in
simulations and controlled experiments. Frontal collision due to unsafe cutins
is the target crash type of this paper. Humancontrolled vehicles making unsafe
lane changes are modeled as the primary disturbance to AVs based on data
collected by the University of Michigan Safety Pilot Model Deployment Program.
The cutin scenarios are generated based on skewed statistics of collected
human driver behaviors, which generate risky testing scenarios while preserving
the statistical information so that the safety benefits of AVs in
nonaccelerated cases can be accurately estimated. The Cross Entropy method is
used to recursively search for the optimal skewing parameters. The frequencies
of occurrence of conflicts, crashes and injuries are estimated for a modeled
automated vehicle, and the achieved accelerated rate is around 2,000 to 20,000.
In other words, in the accelerated simulations, driving for 1,000 miles will
expose the AV with challenging scenarios that will take about 2 to 20 million
miles of realworld driving to encounter. This technique thus has the potential
to reduce greatly the development and validation time for AVs.

We investigate the use of distributionally robust optimization (DRO) as a
tractable tool to recover the asymptotic statistical guarantees provided by the
Central Limit Theorem, for maintaining the feasibility of an expected value
constraint under ambiguous probability distributions. We show that using
empirically defined Burgentropy divergence balls to construct the DRO can
attain such guarantees. These balls, however, are not reasoned from the
standard datadriven DRO framework since by themselves they can have low or
even zero probability of covering the true distribution. Rather, their superior
statistical performances are endowed by linking the resulting DRO with
empirical likelihood and empirical processes. We show that the sizes of these
balls can be optimally calibrated using chisquare process excursion. We
conduct numerical experiments to support our theoretical findings.

We study a worstcase approach to measure the sensitivity to model
misspecification in the performance analysis of stochastic systems. The
situation of interest is when only minimal parametric information is available
on the form of the true model. Under this setting, we post optimization
programs that compute the worstcase performance measures, subject to
constraints on the amount of model misspecification measured by
KullbackLeibler (KL) divergence. Our main contribution is the development of
infinitesimal approximations for these programs, resulting in asymptotic
expansions of their optimal values in terms of the divergence. The coefficients
of these expansions can be computed via simulation, and are mathematically
derived from the representation of the worstcase models as changes of measure
that satisfy a welldefined class of functional fixed point equations.

We propose a Bayesian approach for recursively estimating the classifier
weights in online learning of a classifier ensemble. In contrast with past
methods, such as stochastic gradient descent or online boosting, our approach
estimates the weights by recursively updating its posterior distribution. For a
specified class of loss functions, we show that it is possible to formulate a
suitably defined likelihood function and hence use the posterior distribution
as an approximation to the global empirical loss minimizer. If the stream of
training data is sampled from a stationary process, we can also show that our
approach admits a superior rate of convergence to the expected loss minimizer
than is possible with standard stochastic gradient descent. In experiments with
realworld datasets, our formulation often performs better than
stateoftheart stochastic gradient descent and online boosting algorithms.

We consider a nonstochastic online learning approach to price financial
options by modeling the market dynamic as a repeated game between the nature
(adversary) and the investor. We demonstrate that such framework yields
analogous structure as the BlackScholes model, the widely popular option
pricing model in stochastic finance, for both European and American options
with convex payoffs. In the case of nonconvex options, we construct
approximate pricing algorithms, and demonstrate that their efficiency can be
analyzed through the introduction of an artificial probability measure, in
parallel to the socalled riskneutral measure in the finance literature, even
though our framework is completely adversarial. Continuoustime convergence
results and extensions to incorporate price jumps are also presented.

We study user behavior in the courses offered by a major Massive Online Open
Course (MOOC) provider during the summer of 2013. Since social learning is a
key element of scalable education in MOOCs and is done via online discussion
forums, our main focus is in understanding forum activities. Two salient
features of MOOC forum activities drive our research: 1. High decline rate: for
all courses studied, the volume of discussions in the forum declines
continuously throughout the duration of the course. 2. Highvolume, noisy
discussions: at least 30% of the courses produce new discussion threads at
rates that are infeasible for students or teaching staff to read through.
Furthermore, a substantial portion of the discussions are not directly
courserelated.
We investigate factors that correlate with the decline of activity in the
online discussion forums and find effective strategies to classify threads and
rank their relevance. Specifically, we use linear regression models to analyze
the time series of the count data for the forum activities and make a number of
observations, e.g., the teaching staff's active participation in the discussion
increases the discussion volume but does not slow down the decline rate. We
then propose a unified generative model for the discussion threads, which
allows us both to choose efficient thread classifiers and design an effective
algorithm for ranking thread relevance. Our ranking algorithm is further
compared against two baseline algorithms, using human evaluation from Amazon
Mechanical Turk.
The authors on this paper are listed in alphabetical order. For media and
press coverage, please refer to us collectively, as "researchers from the EDGE
Lab at Princeton University, together with collaborators at Boston University
and Microsoft Corporation."

We prove the first ChernoffHoeffding bounds for general nonreversible
finitestate Markov chains based on the standard L_1 (variation distance)
mixingtime of the chain. Specifically, consider an ergodic Markov chain M and
a weight function f: [n] > [0,1] on the state space [n] of M with mean mu =
E_{v < pi}[f(v)], where pi is the stationary distribution of M. A tstep
random walk (v_1,...,v_t) on M starting from the stationary distribution pi has
expected total weight E[X] = mu t, where X = sum_{i=1}^t f(v_i). Let T be the
L_1 mixingtime of M. We show that the probability of X deviating from its mean
by a multiplicative factor of delta, i.e., Pr [ X  mu t >= delta mu t ], is
at most exp(Omega(delta^2 mu t / T)) for 0 <= delta <= 1, and exp(Omega(delta
mu t / T)) for delta > 1. In fact, the bounds hold even if the weight functions
f_i's for i in [t] are distinct, provided that all of them have the same mean
mu.
We also obtain a simplified proof for the ChernoffHoeffding bounds based on
the spectral expansion lambda of M, which is the square root of the second
largest eigenvalue (in absolute value) of M tilde{M}, where tilde{M} is the
timereversal Markov chain of M. We show that the probability Pr [ X  mu t
>= delta mu t ] is at most exp(Omega(delta^2 (1lambda) mu t)) for 0 <= delta
<= 1, and exp(Omega(delta (1lambda) mu t)) for delta > 1.
Both of our results extend to continuoustime Markov chains, and to the case
where the walk starts from an arbitrary distribution x, at a price of a
multiplicative factor depending on the distribution x in the concentration
bounds.

We consider perpetuities of the form D = B_1 exp(Y_1) + B_2 exp(Y_1+Y_2) +
... where the Y_j's and B_j's might be i.i.d. or jointly driven by a suitable
Markov chain. We assume that the Y_j's satisfy the socalled Cramer condition
with associated root theta_{ast} in (0,infty) and that the tails of the B_j's
are appropriately behaved so that D is regularly varying with index
theta_{ast}. We illustrate by means of an example that the natural
stateindependent importance sampling estimator obtained by exponentially
tilting the Y_j's according to theta_{ast} 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 statedependent importance sampling that are rigorously
shown to be efficient.

We develop rareevent simulation methodology for the analysis of loss events
in a manyserver loss system under qualitydriven regime, focusing on the
steadystate 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 measurevalued process describing
the system. This is the first algorithm that is shown to be asymptotically
optimal, in the rareevent simulation context, under the setting of manyserver
queues involving a full measurevalued descriptor.