BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Paul Dupuis

Paul Dupuis appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.OCcond-mat.stat-mechApplicationsComputationcond-mat.mtrl-scicond-mat.softmath-phmath.MPmath.NAmath.STStatistics TheorySystems and Control

Catalog footprint

What is connected

26works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2021arXiv

Large deviation properties of the empirical measure of a metastable small noise diffusion

The aim of this paper is to develop tractable large deviation approximations for the empirical measure of a small noise diffusion. The starting point is the Freidlin-Wentzell theory, which shows how to approximate via a large deviation principle the invariant distribution of such a diffusion. The rate function of the invariant measure is formulated in terms of quasipotentials, quantities that measure the difficulty of a transition from the neighborhood of one metastable set to another. The theory provides an intuitive and useful approximation for the invariant measure, and along the way many useful related results (e.g., transition rates between metastable states) are also developed. With the specific goal of design of Monte Carlo schemes in mind, we prove large deviation limits for integrals with respect to the empirical measure, where the process is considered over a time interval whose length grows as the noise decreases to zero. In particular, we show how the first and second moments of these integrals can be expressed in terms of quasipotentials. When the dynamics of the process depend on parameters, these approximations can be used for algorithm design, and applications of this sort will appear elsewhere. The use of a small noise limit is well motivated, since in this limit good sampling of the state space becomes most challenging. The proof exploits a regenerative structure, and a number of new techniques are needed to turn large deviation estimates over a regenerative cycle into estimates for the empirical measure and its moments.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quasistationary Distributions and Ergodic Control Problems

We introduce and study the basic properties of two ergodic stochastic control problems associated with the quasistationary distribution (QSD) of a diffusion process $X$ relative to a bounded domain. The two problems are in some sense dual, with one defined in terms of the generator associated with $X$ and the other in terms of its adjoint. Besides proving wellposedness of the associated Hamilton-Jacobi-Bellman equations, we describe how they can be used to characterize important properties of the QSD. Of particular note is that the QSD itself can be identified, up to normalization, in terms of the cost potential of the control problem associated with the adjoint.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large deviations for configurations generated by Gibbs distributions with energy functionals consisting of singular interaction and weakly confining potentials

We establish large deviation principles (LDPs) for empirical measures associated with a sequence of Gibbs distributions on $n$-particle configurations, each of which is defined in terms of an inverse temperature $% β_n$ and an energy functional consisting of a (possibly singular) interaction potential and a (possibly weakly) confining potential. Under fairly general assumptions on the potentials, we use a common framework to establish LDPs both with speeds $β_n/n \rightarrow \infty$, in which case the rate function is expressed in terms of a functional involving the potentials, and with speed $β_n =n$, when the rate function contains an additional entropic term. Such LDPs are motivated by questions arising in random matrix theory, sampling, simulated annealing and asymptotic convex geometry. Our approach, which uses the weak convergence method developed by Dupuis and Ellis, establishes LDPs with respect to stronger Wasserstein-type topologies. Our results address several interesting examples not covered by previous works, including the case of a weakly confining potential, which allows for rate functions with minimizers that do not have compact support, thus resolving several open questions raised in a work of Chafa\"ı et al.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large Deviations for the Single Server Queue and the Reneging Paradox

For the M/M/1+M model at the law-of-large-numbers scale, the long run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: The decay rate of the probability that the long run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path large deviations principle for the model is proved and the rate function is computed. Next, large time asymptotics for the reneging rate are studied for the case when the arrival rate exceeds the service rate. The key ingredient is a calculus of variations analysis of the variational problem associated with atypical reneging. A characterization of the aforementioned decay rate, given explicitly in terms of the arrival and service rate parameters of the model, is provided yielding a precise mathematical description of this paradoxical behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rare event asymptotics for exploration processes for random graphs

Much work in the study of large deviations for random graph models is focused on the dense regime where the theory of graphons has emerged as a principal tool. These tools do not give a good approach to large deviation problems for random graph models in the sparse regime. The aim of this paper is to study an approach for large deviation problems in this regime by establishing Large Deviation Principles (LDP) on suitable path spaces for certain exploration processes of the associated random graph sequence. Our work focuses on the study of one particular class of random graph models, namely the configuration model; however the general approach of using exploration processes for studying large deviation properties of sparse random graph models has broader applicability. The goal is to study asymptotics of probabilities of non-typical behavior in the large network limit. The first key step for this is to establish a LDP for an exploration process associated with the configuration model. A suitable exploration process here turns out to be an infinite dimensional Markov process with transition probability rates that diminish to zero in certain parts of the state space. Large deviation properties of such Markovian models is challenging due to poor regularity behavior of the associated local rate functions. Next, using the rate function in the LDP for the exploration process we formulate a calculus of variations problem associated with the asymptotics of component degree distributions. The second key ingredient in our study is a careful analysis of the infinite dimensional Euler-Lagrange equations associated with this calculus of variations problem. Exact solutions are identified which then provide explicit formulas for decay rates of probabilities of non-typical component degree distributions and related quantities. Please see the paper for the complete abstract.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust bounds and optimization at the large deviations scale for queueing models via Rényi divergence

This paper develops tools to obtain robust probabilistic estimates for queueing models at the large deviations (LD) scale. These tools are based on the recently introduced robust Rényi bounds, which provide LD estimates (and more generally risk-sensitive (RS) cost estimates) that hold uniformly over an uncertainty class of models, provided that the class is defined in terms of Rényi divergence with respect to a reference model and that estimates are available for the reference model. One very attractive quality of the approach is that the class to which the estimates apply may consist of hard models, such as highly non-Markovian models and ones for which the LD principle is not available. Our treatment provides exact expressions as well as bounds on the Rényi divergence rate on families of marked point processes, including as a special case renewal processes. Another contribution is a general result that translates robust RS control problems, where robustness is formulated via Rényi divergence, to finite dimensional convex optimization problems, when the control set is a finite dimensional convex set. The implications to queueing are vast, as they apply in great generality. This is demonstrated on two non-Markovian queueing models. One is the multiclass single-server queue considered as a RS control problem, with scheduling as the control process and exponential weighted queue length as cost. The second is the many-server queue with reneging, with the probability of atypically large reneging count as performance criterion. As far as LD analysis is concerned, no robust estimates or non-Markovian treatment were previously available for either of these models.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms

Parallel tempering, or replica exchange, is a popular method for simulating complex systems. The idea is to run parallel simulations at different temperatures, and at a given swap rate exchange configurations between the parallel simulations. From the perspective of large deviations it is optimal to let the swap rate tend to infinity and it is possible to construct a corresponding simulation scheme, known as infinite swapping. In this paper we propose a novel use of large deviations for empirical measures for a more detailed analysis of the infinite swapping limit in the setting of continuous time jump Markov processes. Using the large deviations rate function and associated stochastic control problems we consider a diagnostic based on temperature assignments, which can be easily computed during a simulation. We show that the convergence of this diagnostic to its a priori known limit is a necessary condition for the convergence of infinite swapping. The rate function is also used to investigate the impact of asymmetries in the underlying potential landscape, and where in the state space poor sampling is most likely to occur.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Large Deviation Principle For Finite-State Mean Field Interacting Particle Systems

We establish a large deviation principle for the empirical measure process associated with a general class of finite-state mean field interacting particle systems with Lipschitz continuous transition rates that satisfy a certain ergodicity condition. The approach is based on a variational representation for functionals of a Poisson random measure. Under an appropriate strengthening of the ergodicity condition, we also prove a locally uniform large deviation principle. The main novelty is that more than one particle is allowed to change its state simultaneously, and so a standard approach to the proof based on a change of measure with respect to a system of independent particles is not possible. The result is shown to be applicable to a wide range of models arising from statistical physics, queueing systems and communication networks. Along the way, we establish a large deviation principle for a class of jump Markov processes on the simplex, whose rates decay to zero as they approach the boundary of the domain. This result may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Escaping from an attractor: Importance sampling and rest points I

We discuss importance sampling schemes for the estimation of finite time exit probabilities of small noise diffusions that involve escape from an equilibrium. A factor that complicates the analysis is that rest points are included in the domain of interest. We build importance sampling schemes with provably good performance both pre-asymptotically, that is, for fixed size of the noise, and asymptotically, that is, as the size of the noise goes to zero, and that do not degrade as the time horizon gets large. Simulation studies demonstrate the theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Limits of relative entropies associated with weakly interacting particle systems

The limits of scaled relative entropies between probability distributions associated with N-particle weakly interacting Markov processes are considered. The convergence of such scaled relative entropies is established in various settings. The analysis is motivated by the role relative entropy plays as a Lyapunov function for the (linear) Kolmogorov forward equation associated with an ergodic Markov process, and Lyapunov function properties of these scaling limits with respect to nonlinear finite-state Markov processes are studied in the companion paper [6].

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Local stability of Kolmogorov forward equations for finite state nonlinear Markov processes

The focus of this work is on local stability of a class of nonlinear ordinary differential equations (ODE) that describe limits of empirical measures associated with finite-state weakly interacting N-particle systems. Local Lyapunov functions are identified for several classes of such ODE, including those associated with systems with slow adaptation and Gibbs systems. Using results from [5] and large deviations heuristics, a partial differential equation (PDE) associated with the nonlinear ODE is introduced and it is shown that positive definite subsolutions of this PDE serve as local Lyapunov functions for the ODE. This PDE characterization is used to construct explicit Lyapunov functions for a broad class of models called locally Gibbs systems. This class of models is significantly larger than the family of Gibbs systems and several examples of such systems are presented, including models with nearest neighbor jumps and models with simultaneous jumps that arise in applications.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the large deviation rate function for the empirical measures of reversible jump Markov processes

The large deviations principle for the empirical measure for both continuous and discrete time Markov processes is well known. Various expressions are available for the rate function, but these expressions are usually as the solution to a variational problem, and in this sense not explicit. An interesting class of continuous time, reversible processes was identified in the original work of Donsker and Varadhan for which an explicit expression is possible. While this class includes many (reversible) processes of interest, it excludes the case of continuous time pure jump processes, such as a reversible finite state Markov chain. In this paper, we study the large deviations principle for the empirical measure of pure jump Markov processes and provide an explicit formula of the rate function under reversibility.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Path-space information bounds for uncertainty quantification and sensitivity analysis of stochastic dynamics

Uncertainty quantification is a primary challenge for reliable modeling and simulation of complex stochastic dynamics. Such problems are typically plagued with incomplete information that may enter as uncertainty in the model parameters, or even in the model itself. Furthermore, due to their dynamic nature, we need to assess the impact of these uncertainties on the transient and long-time behavior of the stochastic models and derive corresponding uncertainty bounds for observables of interest. A special class of such challenges is parametric uncertainties in the model and in particular sensitivity analysis along with the corresponding sensitivity bounds for stochastic dynamics. Moreover, sensitivity analysis can be further complicated in models with a high number of parameters that render straightforward approaches, such as gradient methods, impractical. In this paper, we derive uncertainty and sensitivity bounds for path-space observables of stochastic dynamics in terms of new goal-oriented divergences; the latter incorporate both observables and information theory objects such as the relative entropy rate. These bounds are tight, depend on the variance of the particular observable and are computable through Monte Carlo simulation. In the case of sensitivity analysis, the derived sensitivity bounds rely on the path Fisher Information Matrix, hence they depend only on local dynamics and are gradient-free. These features allow for computationally efficient implementation in systems with a high number of parameters, e.g., complex reaction networks and molecular simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Moderate deviations for recursive stochastic algorithms

We prove a moderate deviation principle for the continuous time interpolation of discrete time recursive stochastic processes. The methods of proof are somewhat different from the corresponding large deviation result, and in particular the proof of the upper bound is more complicated. The results can be applied to the design of accelerated Monte Carlo algorithms for certain problems, where schemes based on moderate deviations are easier to construct and in certain situations provide performance comparable to those based on large deviations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Performance Measures for Infinite Swapping Monte Carlo Methods

We introduce and illustrate a number of performance measures for rare-event sampling methods. These measures are designed to be of use in a variety of expanded ensemble techniques including parallel tempering as well as infinite and partial infinite swapping approaches. Using a variety of selected applications we address questions concerning the variation of sampling performance with respect to key computational ensemble parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust bounds on risk-sensitive functionals via Renyi divergence

We extend the duality between exponential integrals and relative entropy to a variational formula for exponential integrals involving the Renyi divergence. This formula characterizes the dependence of risk-sensitive functionals and related quantities determined by tail behavior to perturbations in the underlying distributions, in terms of the Renyi divergence. The characterization gives rise to upper and lower bounds that are meaningful for all values of a large deviation scaling parameter, allowing one to quantify in explicit terms the robustness of risk-sensitive costs. As applications we consider problems of uncertainty quantification when aspects of the model are not fully known, as well their use in bounding tail properties of an intractable model in terms of a tractable one.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Large deviation properties of weakly interacting processes via weak convergence methods

We study large deviation properties of systems of weakly interacting particles modeled by Itô stochastic differential equations (SDEs). It is known under certain conditions that the corresponding sequence of empirical measures converges, as the number of particles tends to infinity, to the weak solution of an associated McKean-Vlasov equation. We derive a large deviation principle via the weak convergence approach. The proof, which avoids discretization arguments, is based on a representation theorem, weak convergence and ideas from stochastic optimal control. The method works under rather mild assumptions and also for models described by SDEs not of diffusion type. To illustrate this, we treat the case of SDEs with delay.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Large Deviations for Stochastic Partial Differential Equations Driven by a Poisson Random Measure

Stochastic partial differential equations driven by Poisson random measures (PRM) have been proposed as models for many different physical systems, where they are viewed as a refinement of a corresponding noiseless partial differential equations (PDE). A systematic framework for the study of probabilities of deviations of the stochastic PDE from the deterministic PDE is through the theory of large deviations. The goal of this work is to develop the large deviation theory for small Poisson noise perturbations of a general class of deterministic infinite dimensional models. Although the analogous questions for finite dimensional systems have been well studied, there are currently no general results in the infinite dimensional setting. This is in part due to the fact that in this setting solutions may have little spatial regularity, and thus classical approximation methods for large deviation analysis become intractable. The approach taken here, which is based on a variational representation for nonnegative functionals of general PRM, reduces the proof of the large deviation principle to establishing basic qualitative properties for controlled analogues of the underlying stochastic system. As an illustration of the general theory, we consider a particular system that models the spread of a pollutant in a waterway.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Rare-Event Sampling: Occupation-Based Performance Measures for Parallel Tempering and Infinite Swapping Monte Carlo Methods

In the present paper we identify a rigorous property of a number of tempering-based Monte Carlo sampling methods, including parallel tempering as well as partial and infinite swapping. Based on this property we develop a variety of performance measures for such rare-event sampling methods that are broadly applicable, informative, and straightforward to implement. We illustrate the use of these performance measures with a series of applications involving the equilibrium properties of simple Lennard-Jones clusters, applications for which the performance levels of partial and infinite swapping approaches are found to be higher than those of conventional parallel tempering.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Infinite Swapping Approach to the Rare-Event Sampling Problem

We describe a new approach to the rare-event Monte Carlo sampling problem. This technique utilizes a symmetrization strategy to create probability distributions that are more highly connected and thus more easily sampled than their original, potentially sparse counterparts. After discussing the formal outline of the approach and devising techniques for its practical implementation, we illustrate the utility of the technique with a series of numerical applications to Lennard-Jones clusters of varying complexity and rare-event character.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Counting with Combined Splitting and Capture-Recapture Methods

We apply the splitting method to three well-known counting problems, namely 3-SAT, random graphs with prescribed degrees, and binary contingency tables. We present an enhanced version of the splitting method based on the capture-recapture technique, and show by experiments the superiority of this technique for SAT problems in terms of variance of the associated estimators, and speed of the algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distinguishing and integrating aleatoric and epistemic variation in uncertainty quantification

Much of uncertainty quantification to date has focused on determining the effect of variables modeled probabilistically, and with a known distribution, on some physical or engineering system. We develop methods to obtain information on the system when the distributions of some variables are known exactly, others are known only approximately, and perhaps others are not modeled as random variables at all. The main tool used is the duality between risk-sensitive integrals and relative entropy, and we obtain explicit bounds on standard performance measures (variances, exceedance probabilities) over families of distributions whose distance from a nominal distribution is measured by relative entropy. The evaluation of the risk-sensitive expectations is based on polynomial chaos expansions, which help keep the computational aspects tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Importance Sampling for Multiscale Diffusions

We construct importance sampling schemes for stochastic differential equations with small noise and fast oscillating coefficients. Standard Monte Carlo methods perform poorly for these problems in the small noise limit. With multiscale processes there are additional complications, and indeed the straightforward adaptation of methods for standard small noise diffusions will not produce efficient schemes. Using the subsolution approach we construct schemes and identify conditions under which the schemes will be asymptotically optimal. Examples and simulation results are provided.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Large Deviations for Multiscale Diffusions via Weak Convergence Methods

We study the large deviations principle for locally periodic stochastic differential equations with small noise and fast oscillating coefficients. There are three possible regimes depending on how fast the intensity of the noise goes to zero relative to the homogenization parameter. We use weak convergence methods which provide convenient representations for the action functional for all three regimes. Along the way we study weak limits of related controlled SDEs with fast oscillating coefficients and derive, in some cases, a control that nearly achieves the large deviations lower bound at the prelimit level. This control is useful for designing efficient importance sampling schemes for multiscale diffusions driven by small noise.

0 citations0 reviewsNo code linkedOpen access