\LARGE How biased is your model? \\Concentration Inequalities, Information and Model Bias
Konstantinos~Gourgoulias
Markos A.~ Katsoulakis
Luc~Rey-Bellet and~Jie~Wang% <-this % stops a space \thanks{K. Gourgoulias is with Babylon Health
London
UK. He contributed to this work while he was at the Department of Mathematics and Statistics
University of Massachusetts Amherst
Amherst
MA
01003
USA (e-mail: kostis.gourgoulias@babylonhealth.com)
....lastname \thanks{...
We derive tight and computable bounds on the bias of statistical estimators, or more generally of quantities of interest, when evaluated on a baseline model $P$ rather than on the typically unknown true model $Q$. Our proposed method combines the scalable information inequality derived by P. Dupuis, K.Chowdhary, the authors and their collaborators together with classical concentration inequalities (such as Bennett's and Hoeffding-Azuma inequalities). Our bounds are expressed in terms of the Kullback-Leibler divergence $\R QP$ of model $Q$ with respect to $P$ and the moment generating function for the statistical estimator under $P$. Furthermore, concentration inequalities, i.e. bounds on moment generating functions, provide tight and computationally inexpensive model bias bounds for quantities of interest. Finally, they allow us to derive rigorous confidence bands for statistical estimators that account for model bias and are valid for an arbitrary amount of data.
main.tex
%% bare_jrnl.tex
%% V1.4b
%% 2015/08/26
%% by Michael Shell
%% see http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8b or later) with an IEEE
%% journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/pkg/ieeetran
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall the IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%*************************************************************************


% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. The IEEE's font choices and paper sizes can   ***
% *** trigger bugs that do not appear when using other class files.       ***                          ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/



%\documentclass[journal]{IEEEtran}
\documentclass[journal,12pt,onecolumn]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[journal]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/pkg/ifpdf
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
%\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of the IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 5.0 (2009-03-20) and later if using hyperref.sty.
% The latest version can be obtained at:
% http://www.ctan.org/pkg/cite
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at: 
% http://www.ctan.org/pkg/graphicx
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/pkg/epslatex
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
\usepackage{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics.
%
% Note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/amsmath





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/pkg/algorithms
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/pkg/algorithmicx




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/array


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
\ifCLASSOPTIONcompsoc
 \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
\else
 \usepackage[caption=false,font=footnotesize]{subfig}
\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/pkg/subfig




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure.
% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
% corrections already built into the system in which case a warning will
% be issued if an attempt is made to load fixltx2e.sty as it is no longer
% needed.
% The latest version and documentation can be found at:
% http://www.ctan.org/pkg/fixltx2e


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/stfloats
% Do not use the stfloats baselinefloat ability as the IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that the IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/pkg/dblfloatfix




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and 
% Axel Sommerfeldt. This package may be useful when used in conjunction with 
% IEEEtran.cls'  captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/pkg/endfloat
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/url
% Basically, \url{my_url_here}.




% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\input{symbols.tex}
\usepackage{todonotes} \newcommand{\tdi}{\todo[inline]}

\usepackage[inline]{enumitem}

\begin{document}
%
% paper title
% Titles are generally capitalized except for words such as a, an, and, as,
% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
% not capitalized unless they are the first or last word of the title.
% Linebreaks \\ can be used within to get better formatting as desired.
% Do not put math or special symbols in the title.
\title{\LARGE How biased is  your model? \\Concentration Inequalities,
    Information
     and Model Bias}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%
\author{Konstantinos~Gourgoulias,
        Markos A.~
    Katsoulakis,
        Luc~Rey-Bellet
        and~Jie~Wang% <-this % stops a space
\thanks{K. Gourgoulias is with Babylon Health, London, UK. He contributed to this work while he was at the Department of Mathematics and Statistics, University of Massachusetts Amherst, Amherst, MA, 01003,  USA (e-mail: kostis.gourgoulias@babylonhealth.com) }
\thanks{M. Katsoulakis is with the Department
of Mathematics and Statistics, University of Massachusetts Amherst, Amherst,
MA, 01003, USA (e-mail:markos@math.umass.edu) }
\thanks{ L. Rey-Bellet is with the Department
of Mathematics and Statistics, University of Massachusetts Amherst, Amherst,
MA, 01003, USA (e-mail:luc@math.umass.edu) }
\thanks{ J. Wang is with the Department
of Mathematics and Statistics, University of Massachusetts Amherst, Amherst,
MA, 01003, USA (e-mail:wang@math.umass.edu) }
% <-this % stops a space
%\thanks{Manuscript received April 19, 2005; revised August 26, 2015.}
}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
%\markboth{Journal of \LaTeX\ Class Files,~Vol.~14, No.~8, August~2015}%
%{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for IEEE Journals}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.




% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2015 IEEE}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark.



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle

% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\begin{abstract}
We derive tight and computable bounds on the bias of statistical estimators, or more generally of quantities of interest,  when evaluated on a baseline model $P$ rather than on the typically unknown  true model $Q$. Our proposed method  combines  the  scalable information inequality derived by P. Dupuis, K.Chowdhary, the authors and their collaborators together with classical concentration inequalities (such as Bennett's and Hoeffding-Azuma inequalities). Our bounds are expressed in terms of the Kullback-Leibler divergence $\R QP$ of model $Q$ with respect to $P$ and the moment generating function for the statistical estimator under $P$. Furthermore, concentration inequalities, i.e. bounds on moment generating functions,  provide tight and computationally inexpensive    model bias bounds for quantities of interest. Finally, they allow us to derive rigorous  confidence bands for statistical estimators that account for  model bias and are valid for an arbitrary amount of data.
\end{abstract}

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Uncertainty quantification, information theory, information bounds, model bias, model uncertainty, goal-oriented divergence, concentration inequalities, Kullback-Leibler divergence, statistical estimators
\end{IEEEkeywords}






% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps.
% 
% form to use if the first word consists of a single letter:
% \IEEEPARstart{A}{demo} file is ....
% 
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by the IEEE):
% \IEEEPARstart{A}{}demo file is ....
% 
% Some journals put the first two words in caps:
% \IEEEPARstart{T}{his demo} file is ....
% 
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
% \IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file''
% for IEEE journal papers produced under \LaTeX\ using
% IEEEtran.cls version 1.8b and later.
% % You must have at least 2 lines in the paragraph with the drop letter
% % (should never be an issue)
% I wish you the best of success.

% \hfill mds
 
% \hfill August 26, 2015

\label{sec:intro}
An essential ingredient of predictive modeling is the reliable calculation  of specific
statistics/quantities of interest  of the predictive distribution. Such
statistics are typically tied to the application domain, for instance moments,
covariance, failure probabilities, extreme events, arrival times, average velocity, energy
and so on. Predictive models can involve (a) statistical aspects or data
collection, and (b) physical/mathematical mechanisms with choices in
complexity/resolution, some of them potentially computationally intractable.
% e.g., electronic structure or atomistic or molecular modeling in materials
% science or more generally,  computationally demanding agent-based modeling across application domains. 
Therefore, to improve the predictive capabilities of models we face  fundamental trade-offs
between model complexity,  amount of available data,  computational efficiency, and  model bias.  

The main focus of the paper is the understanding and control of model bias which often inevitably occurs in model building and which is itself a measure  of reliable predictions. 
Our primary tool are information-theoretic Uncertainty Quantification  methods.
%%%
Uncertainty quantification (UQ) methods address questions related to model selection, model sensitivity, model reduction and misspecification, \cite{Dakota,Smith,Saltelli:global}. 
Sources of uncertainty are broadly classified in two categories: aleatoric, due to the inherent stochasticity of probabilistic models and the limited availability of data, and epistemic, stemming from the inability to accurately model all aspects of a complex system, \cite{dupuis2011uq, Smith, Sullivan2015}.
%
% \medskip\noindent{\bf Information Metrics in UQ.}
Model bias is closely related to epistemic uncertainty, and probability metrics (Wasserstein, total variation) and divergences (Kullback-Leibler, Renyi, $\chi^2$) \cite{tsybakov} are important tools to quantify uncertainty by comparing  models.
% : tractable surrogates to baseline or computationally expensive models, assess
% sensitivity to model perturbations, or select best-fit models to data.
%
Among the divergences, the Kullback-Leibler (KL) divergence (also known as  relative entropy) is widely used 
because of its computational tractability.
% and because it 
% does not focus on any particular statistic or Quantity of Interest (QoI) of
% the model. Model building 
% based on specfic QoI's can be restrictive since additional statistics require retraining, resulting in inconsistencies between predictive models, see for instance works in coarse-graining of molecular systems,
% \cite{mp,Shell,Noid,Kalligiannaki2015,voth2016representability}. 
Specifically, KL-based methods have been used successfully in variational inference and expectation propagation~\cite{bishop}, model selection~\cite{burnham}, model reduction (coarse-graining)~\cite{Shell, KP2013, Noid,  majdabook}, optimal experiment design, \cite{Atkinson2007OptimumExperimentalDesignsWithSAS.}, and UQ~\cite{majdauncertainty,majdafidelity,Komorowski,PK2013}.


% Model Bias \& Complexity Trade-offs.
Information-theoretic methods
for model building
% for model reduction, approximate inference or model misspecification
will typically induce bias for  the various statistics and the QoIs of the predictive distribution compared to the ``true'' model--if known--or the available data.
% Specific quantities of interest (QoIs) are typically tied to the application
% domain, e.g., moments, failure probabilities, extreme events, arrival times,
% average velocity, energy, etc.
Managing the corresponding trade-offs between a range of less biased but more computationally expensive models naturally leads to the following main question 
for the paper :
\begin{center}
  \textit{Can we provide performance guarantees for model bias in models built
    via KL-based approximate inference, model misspecification, or model
    selection methods?}
  % Can we optimize trade-offs between bias, model complexity and
  % computational/data life-cycle budget?
\end{center}


In this paper we ultimately seek to understand how a decrease in KL-divergence--associated with an increase in modeling and/or computational effort--can
guarantee a model bias tolerance; and in addition, we seek the tightest possible control of model bias.
% {Approach and Earlier Work.}
% Our proposed approach is, broadly speaking, based on information inequalities and probabilistic metrics and divergences.
Note that bounds on the model bias of a QoI between two distributions $P$ and $Q$
can be obtained, for example, in terms of their KL or $\chi^2$ divergences using the classical Pinsker or Chapman-Robbins inequalities respectively, \cite{Cover2006ElementsofInformationTheory,tsybakov}. Clearly a decrease in divergence will improve bounds on the model bias.
% \markos{comment: Need to actually know the change in KL: use estimators,
% thermodynamic integration, approximations, bounds etc. Trade-off: what
% reduction in KL is necessary to guarantee model bias bound?}
However, these classical inequalities are 
typically \textit{non-tight} and
\textit{non-discriminating}, in the sense that they scale poorly with the size of data sets,  with the number of variables in high-dimensional models (e.g. molecular systems), or with time in the context of stochastic  processes; we refer to  Sections~2.2--2.3 in \cite{katsoulakisjcp2017} for a complete discussion, see also the  example in Remark~\ref{rem:poor:scalab}.

%in the sense they provide trivial bounds at least
%for high-dimensional data sets and probabilistic models such as Markov Random Fields, long-time dynamics of
%stochastic processes and molecular models, we refer to \cite{katsoulakisjcp2017} for examples and a complete discussion.

To tackle these challenges a class of new information  inequalities have been introduced by Paul Dupuis in \cite{dupuis2011uq} and  further developed in \cite{katsoulakisuq16,katsoulakisjcp2017}
by the authors and their collaborators. 
The resulting bounds on model bias bounds involve (a) the KL divergence $\R QP$
between a baseline model $P$ and  an alternative  models $Q$, and (b) the moment generating function (MGF) for the QoI under  the baseline model  $P$. This inequality inherits the asymmetry of $\R QP$, which in turn allows us to exchange the roles of $P$ and $Q$,  depending on the context and/or availability of data from either $P$ or $Q$. 
Considering a neighborhood of models around the baseline $P$, defined by the KL divergence $\R QP$,  can be associated with a specified error tolerance and is non-parametric in nature.
% (or corresponding data).
The crucial mathematical ingredient behind the inequality is the Donsker-Varadhan variational principle~\cite[Appendix C.]{dupuisellis} for the KL divergence, also known as the  Gibbs variational
formula~\cite{simon2014statistical}.
%or Kullback's inequality~\cite[Section4.]{fuchs1970inegalite}. 
This variational representation actually implies that 
the new inequalities are \textit{tight}, i.e. they become an equality for a suitable model $Q$ within a  KL divergence neighborhood of the baseline model $P$.
Furthermore, the dependence on   the MGF renders the bounds scalable and \textit{discriminating} for high-dimensional data sets and models, e.g. Markov Random Fields, long-time dynamics of stochastic processes and molecular models, \cite{katsoulakisjcp2017} as demonstrated recently in  \cite{katsoulakisjcp2017}.
Finally, broadly related methods  in model misspecification and sensitivity analysis in  financial risk measurement and queuing theory, using a robust optimization perspective, were proposed recently  in    \cite{glasserman2014} and \cite{lam2016}, we also refer to references therein for other  related work  in operations research, finance  and macroeconomics.

The primary goal of this paper is to use these new theoretical advances to develop practical tools to estimate and control model bias, and this raises new theoretical questions and implementation challenges. In particular evaluating or estimating MGFs can be very costly due to high variance of the estimators thus requiring either a large amount of data, see also Table 1, or multi-level/sequential  Monte Carlo methods~\cite{junliu,bishop,lelievre2010free,delmoral2012}. In this paper we rather pursue the use of a variety of QoI-dependent \textit{concentration  inequalities}~\cite{concentration,raginsky2013concentration,ledoux2005concentration}
% comment on bias bounds for families of statistics,
to bypass the evaluation or estimation of the MGF and this leads to computable, tight bounds for model bias. 
%
%
%background on concentration inequalities
Concentration inequalities are a fundamental mathematical tool in the study of rare events~\cite{dembo2010large}, model selection
methods~\cite{massart2007concentration}, statistical mechanics~\cite[Section
8.4]{ledoux2005concentration}, random matrix
theory~\cite{tropp2015introduction}. Usually concentration inequalities are used to bound tail events, i.e. to provide bounds on the probability that a random variable deviates from typical behavior.
%, as well as dimension-independent concentration results. 
In this paper we use concentration inequalities for
the purpose of uncertainty quantification,  specifically to control model bias,  by implementing efficiently the new information inequalities developed in \cite{dupuis2011uq,katsoulakisuq16,katsoulakisjcp2017}, while at the same time maintaining and expanding their theoretical advantages. 

% \tdi{Include in intro this message: 

% The bounds control the model 
% bias  in terms of the relative entropy 
% between  different models and intrinsic statistical quantities associated to the QoIs in a baseline model, e.g. mean, variance,  $L^\infty$ bound. 
% }

The new inequalities proved in this paper--- which we call  \textit{concentration/information} inequalities---combine  concentration inequalities with the variational principles  underlying the bounds and  lead to model bias bounds with the following key features:  
\begin{enumerate}
\item[(a)] Easily  computable bounds  in terms of simple properties of the QoIs such
    as their mean,  %$L^\infty$ 
    upper and lower bounds,  suitable bounds on their variance, and so on; that is, without requiring the costly computation of MGFs. %  however this is achieved at the expense of some accuracy due to the use of a concentration bound. 
    \item[(b)] Scalability for  QoIs that depend on large numbers of data such as statistical estimators,  or for high dimensional probabilistic models. 
    \item[(c)]   Derivation of  rigorous  confidence bands for statistical estimators that account for  model bias and are valid for an arbitrary amount of data.   
    \item[(d)] Applicability  to families of QoIs satisfying  a concentration inequality, 
    and not to just a single QoI.% as the inequalities in~\cite{dupuis2011uq,katsoulakisuq16}.
    \item[(e)] Tightness of  the model bias bounds in the sense that the bounds are always attained within a prescribed KL-divergence \textit{and} the  class of QoIs in (d). 
    %tightness is still valid in spite of the loss of  accuracy due to the  concentration inequality, see (a). 
\end{enumerate}

The structure of the paper is as follows.  In Section~\ref{sec:outline} we set-up the  mathematical  framework for the paper and discuss 
the information inequalities for QoIs of \cite{dupuis2011uq,katsoulakisuq16,katsoulakisjcp2017}.
In Section~\ref{sec:conc-ineq} we use concentration inequalities to derive new concentration/information inequalities on model bias that are typically  straightforward to implement. In Section~\ref{sec:sharpness-and-robustness}, we discuss the  tightness properties of the new concentration/information bounds. 
Finally in Section~\ref{sec:scalability}  we study the bias of statistical estimators, noting that such QoIs will require results  that scale properly with the amount of available data.
% Finally, in Section~\ref{sec:sharpness-and-robustness}, we discuss the 
% tightness properties of the new concentration/information bounds
%with respect 
%are tight over all models within  classes of models and QoIs.
We also illustrate the bounds in a variety of examples. In  Section~\ref{ex:simple-examples} 
we  consider two elementary examples  with bounded or unbounded QoIs. Two examples of systems with epistemic uncertainty are discussed in Section~\ref{sec:epistemic-UQ-conc}; the first one deals with failure probabilities for batteries 
and the second with  Markov Random Fields such as Ising systems. 




% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex, 
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure}

% Note that the IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command,
% and the \label for the overall figure must come after \caption.
% \hfil is used as a separator to get equal spacing.
% Watch out that the combined width of all the subfigures on a 
% line do not exceed the text width or a line break will occur.
%
%\begin{figure*}[!t]
%\centering
%\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
%\label{fig_second_case}}
%\caption{Simulation results for the network.}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat[]), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.
% Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
% labels, the optional argument to \subfloat must be present. If a
% subcaption is not desired, just leave its contents blank,
% e.g., \subfloat[].

\section{Tight Model Bias Bounds using KL Divergence}
\label{sec:outline}

In coarse-graining, model reduction, 
model selection, or variational inference,
as well as in other uncertainty quantification and approximate inference problems, a baseline model $P$ is compared  to a "true" or simply a different model $Q$. In this case the notion of {\em risk or mean
  square error} plays a key role in assessing the quality of the corresponding
estimators. Namely, if $\hat{f}$ is an unbiased estimator of the quantity of
interest $f$ for the baseline  model $P$ (but not of the "true" model $Q$)
then the risk of the estimator is the mean squared error 
%
\begin{align}
  \label{eq:risk}
  \mbox{RISK}:=\mathbb{E}_P[ (\hat{f} - \mathbb{E}_Q[f])^2]= \underbrace{{\rm
  Var}_{P}[\hat{f}] }_{{\rm Variance}}+ \underbrace{ | \mathbb{E}_P[f] -
  \mathbb{E}_Q[f]|^2}_{\rm Model Bias} \,.
\end{align}
If available computational resources can be used to control the variance of
the baseline model P, then the model bias becomes the dominant source of risk thus must be carefully controlled. The main  goal of this work is to understand how to transfer quantitative results on information metrics, specifically the KL divergence  $R(Q\|P)$ (also known as relative entropy), to {\em bounds on the bias for
  quantities of interest} $f$. We formulate the corresponding mathematical
problem next.


\medskip
\noindent{\bf Mathematical Formulation.} 
Let us consider a baseline model given 
by the probability measure $P$ on the 
state space $\mathcal{X}$ which we assume to be a Polish (i.e. complete separable metric) space and  we consider 
a QoI $f$, that is a measurable function 
$f: \mathcal{X} \to\mathbb{R}$. 
We specify next a family of alternative 
probability distributions in terms of the 
Kullback-Leibler (KL) divergence (or relative entropy) $\R Q P$, which is defined as 
\begin{align}
  \label{eq:KL}
  \R QP=\int \log \frac{dQ}{dP} dQ. 
\end{align}
if $Q$ is absolutely continuous with respect to $P$ 
(and $+\infty$ otherwise).  Note that $\R QP$ the 
properties of a divergence that is  $\R QP\geq 0$ for 
all $Q$ and  $\R QP=0$ if and only if  $Q=P$, see e.g. 
\cite{Cover2006ElementsofInformationTheory}.


We fix a positive number $\eta$ which we interpret 
as a level of \textit{model misspecification}, quantified in terms KL divergence or, alternatively, as an error tolerance level between the baseline  model $P$ and alternative models described $Q$.
We then define the set of alternative probability as 
\begin{equation}
  \label{Qfamily}
  \mathcal{Q}_\eta=\{Q: R(Q\|P) \le \eta^2\}\, .
\end{equation}
and any $Q\in\efam$ is referred to as an \textit{$\eta$-admissible model}.
We remark that our approach is 
\textit{non-parametric}, i.e. it does not
rely on any parametric form of the 
probability distributions considered. 
The relative entropy $\R QP$ is convex and 
lower-semicontinuous in $(Q,P)$. 
In general the set  $\efam$ is infinitely  dimensional, although it is compact with respect to the weak topology, \cite{dupuisellis}. 
The fact that the KL divergence is not symmetric in its arguments can be advantageous in some situations. For 
example, in variational inference, it naturally imposes 
a constraint on the support of the possible 
approximations $Q$ of a target model $P$~\cite{bishop}. 

  
Our primary mathematical challenge in 
this work lies in quantifying the model
bias in~(\ref{eq:risk}) if we use an $\eta$-admissible model in $Q_\eta$ rather than the baseline model $P$. That is we need to 
\begin{align*}
\textrm{ Compute (or estimate) }\sup_{Q \in \efam} \{\mathbb{E}_Q[f] - \mathbb{E}_P[f] \} \quad \textrm{ and } \quad \inf_{Q \in \efam} \{\mathbb{E}_Q[f] - \mathbb{E}_P[f]\}\,.
\end{align*}
%Note that by the compactness of $\efam$ and the lower-
%semicontinuity of the entropy the supremum and infimum 
%are actually attained in $\efam$. 
Note that this approach is intrinsically 
goal-oriented since it includes not only  a 
family of alternative models $Q$ but also  a specific choice of QoI $f$.  






%
%Indeed, bounds on the model bias of a QoI $f$ between two distributions can be obtained in terms of their KL or $\chi^2$ divergences using the Pinsker or Chapman-Robbins inequalities respectively, while similar bounds can be derived in terms of the Hellinger distance, and the R\'enyi divergence, \cite{Cover2006ElementsofInformationTheory,tsybakov}. 
%In general, a decrease in the divergence will result in an improved bound on the model bias.
% \markos{comment: Need to actually know the change in KL: use estimators,
% thermodynamic integration, approximations, bounds etc. Trade-off: what
% reduction in KL is necessary to guarantee model bias bound?}
%However, such inequalities are not tight and
%non-discriminating  in the sense they provide trivial bounds at least
%for high-dimensional models or large data sets, 
%such as Markov Random Fields, long-time dynamics of stochastic processes and molecular models, 
%\cite{katsoulakisjcp2017}.


% The goal-oriented (GO) divergence is a sharp and robust bound on the bias
% without the issues that other information metrics suffer from;
% see~\cite{katsoulakis2016scalable}. The GO divergence was first defined
% in~\cite{katsoulakisuq16}, following the work in~\cite{dupuis2011uq}. Given an
% observable $f: \mathcal{X} \to \mathbb{R}$, the moment-generating function
% (MGF) corresponding to $f(X)$, $X\sim P$, is: \mathcal{Q}_\eta$. There are
% many inequalities that connect information metrics and divergences, such as
% the Hellinger distance, the $\chi^2$ and the R\'enyi divergence, with model
% bias. However, those bounds tend to become uninformative in high-dimensional
% situations; see ~\cite{katsoulakis2016scalable} for details.

\medskip
\noindent{\bf Goal-oriented divergence.}
We now define a divergence which incorporates the QoI $f$ and hence is called goal-oriented; it was first introduced in the current form in~\cite{katsoulakisuq16} based on earlier work in~\cite{dupuis2011uq}.
Consider a QoI $f$ and the moment-generating function (MGF)
\begin{align}
  \label{eq:mgf}
  \Mp{c;\ti f}:= E_{P} [e^{c\ti f}]
\end{align}
of the centered QoI $\ti f$,
\begin{align}
  \label{eq:centralized}
  \ti f(x) := f(x)-\Ep[f].
\end{align}
In general (see \cite{dembo2010large} for details) 
the MGF $\Mp{c;\ti f}$ is finite for $c$ in some 
interval $I$ and equal to $+\infty$ otherwise.  
Throughout this  paper we will make the standing 
assumption that $\Mp{c;\ti f}$ is finite in the interval  $I=(d_-, d_+)$ with $d_- < 0 < d_+$, then under this assumption, $\Mp{c;\ti f}$ is $C^\infty$ in $I$ and 
$f$ has finite moments of any order.  We next define  the goal-oriented (GO) divergence as 
\begin{equation}
  \go QPf = \inf _{c>0}\left\{ \frac{1}{c}  \Cp{c;\ti f} +  \frac{1}{c} \R QP \,  \right\}.\label{eq:intro:godiv:2} 
\end{equation}
for $P,Q$ with $\R Q p < \infty$. 
Note that if $d_+$ is finite then  
the infimum can be taken on $(0,d_+)$
and note also that if  $\R Q P = \infty$ 
then the goal  oriented divergence can 
naturally be then set equal to $+\infty$.


In \cite{dupuis2011uq,katsoulakisuq16} 
the following bound on the model bias was proved, along with certain mathematical properties:
\begin{theorem}
\label{thm:GO-bounds} Let $P$ be a probability measure and let $f$ be such that its MGF $\Mp{c;\ti  f}$ is finite in a neighborhood of the origin. Then for any $Q$ with $\R Q P < \infty$ we have 
\begin{equation}
  -\go QP{-f} \leq \bias \leq \go QP{f}.
  \label{eq:intro:bias-bound-go:sec2}
\end{equation}
The GO divergence has the following properties
%\noindent {\bf Properties of the GO divergence}
\begin{enumerate}
\item \label{it:go:non-negative} \textit{Divergence:}
$\Xi(Q \mid \mid P ;f ) \ge 0$ 
and $\Xi(Q \mid \mid P ;f) = 0$ if and only if either $Q=P$
  or $f$ is constant $P$-a.s.
% for all $Q$, $P$ such that $\R QP< \infty$ and QoIs $f$.
%\item \label{it:go:divergence} $\Xi(Q \mid \mid P ;f) = 0$ if and only if $Q=P$
 % or $f$ is constant $P$-a.s.
\item \label{it:go:linearization} \textit{Linearization}: 
$$ \Xi(Q \mid \mid P;\pm f)=
\sqrt{\Vp[f]}\sqrt{2R(Q\mid \mid P)}+O(\R QP)$$ and thus
$$
\mid E_Q(f)- E_P(f)\mid \, \le \, \sqrt{\Vp[f]}\sqrt{2R(Q\mid \mid P)}+O(R(Q\mid
\mid P)).
  $$
\end{enumerate}
\end{theorem}

\medskip
\noindent{\bf Tightness of goal-oriented divergence.}
Our next result complements Theorem~\ref{thm:GO-bounds}
and demonstrates the tightness of the GO divergence
bounds \eqref{eq:intro:bias-bound-go:sec2} for the bias of a  QoI $f$; for the complete proof, we refer to Appendix~\eqref{sec:Appendix:tightness:GO}. An     equivalent tightness result for the upper bound in   \eqref{it:go:tightness:thm} was first shown in \cite{dupuis2011uq}, while   here we present a new formulation  for a  complete  tightness result  in Theorem~\ref{thm:tightness},    based on the goal-oriented divergence formulation in \cite{katsoulakisuq16}.



To state our result we introduce 
the exponential family $P^{c}$ given by 
\begin{equation}
  \label{eq:parametric}
  \frac{dP^{c}}{dP} \,=\, e^{ c f - \log M_P(c; f)}\,=\,\frac{e^{c f}}{\int e^{c f}dP}
  \,,
\end{equation}
which is well-defined for $c$ in the 
interval $I=(d_-,d_+)$ where $\Mp{c;f}$ is finite.

\begin{theorem}
  \label{thm:tightness} 
Let $P$ be a probability measure and let 
$f$ be such the MGF $\Mp{c;\ti  f}$  is finite in a neighborhood of the origin.
Let $\mathcal{Q}_\eta=\{Q: R(Q\|P) \le
\eta^2\}$ be the set all  approximate 
probability $Q$ within a KL tolerance $\eta^2$. 
\begin{enumerate} 
\item There exists $0< \eta_{\pm} \le \infty$ such that for any $\eta \le \eta_{\pm}$ there are probability measures $Q^{\pm}$ such that  
\begin{equation}
\label{eq:max}
\begin{aligned}
\go {Q^+}Pf &= \E_{Q^+}[f] -\E_{P}[f] &=
                \max_{Q\in \mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f],
\end{aligned}
\end{equation}
\begin{equation}
\label{eq:min}
\begin{aligned}
-\go {Q^{-}}P{-f}& = \E_{Q^-}[f] - \E_{P}[f] &=
                   \min_{Q\in \mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f]
\end{aligned}
\end{equation}
The measures $Q_\pm$ are given by the elements $P^{c_\pm}$ of the exponential family \eqref{eq:parametric} where $c_\pm$  are the unique solution of $\R {P^{c_\pm}}{P} = \eta^2$. 
%In other words we have the model bias bound 
%\begin{equation}
%\label{it:go:tightness:thm}
%  -\gom{Q^{-}}P{f}+\E_{P}[f]
  % = \E_{Q^-}[f]-\E_{P}[f]
%  \le
%  \E_{Q}[f] \le 
  % \E_{Q^+}[f]-\E_{P}[f]=
%  \E_{P}[f]+\gop{Q^+}Pf\, \quad \mbox{for all  $Q\in \mathcal{Q}_\eta$ } \quad
%\end{equation}
%with the two equalities holding if $Q=Q^\mp=P^{c_\mp}$ respectively. 
\item If $\eta_\pm$ is finite then $f$ is necessarily bounded above/bounded below 
$P$-almost surely with upper/lower bound $f_{\pm}$. In that case, for $\eta > \eta_{\pm}$ and any $Q$ with $\R QP = \eta^2$
we have  
\begin{equation}
 \label{eq:max2}
\begin{aligned}
\go QPf &= f_+ -\E_{P}[f]&=\sup_{Q\in \mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f],
\end{aligned}
\end{equation}
\begin{equation}
\label{eq:min2}
\begin{aligned}
-\go QP{-f}& = f_- -\E_{P}[f]&=
                    \inf_{Q\in \mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f]
\end{aligned}
\end{equation}
\end{enumerate}
\end{theorem}

% \begin{proof}
%   The proof follows immediately from Lemma~\ref{aux:bound:func:gen:prop}, when   we set $M=\eta^2$. We refer to the Appendix for the proof of the Lemma. An   equivalent tightness result for the upper bound in   \eqref{it:go:tightness:thm} was first shown in \cite{dupuis2011uq}, while   here we proved the complete tightness result \eqref{it:go:tightness:thm}   based on the goal-oriented divergence formulation in \cite{katsoulakisuq16}. \end{proof}

The main result of the theorem provides 
performance guarantees in the sense that $\E_Q[f]$ belongs to the interval 
\begin{equation}
\label{it:go:tightness:thm}
\begin{aligned}
  -\go {Q^{-}}P{-f}+&\E_{P}[f]
  % = \E_{Q^-}[f]-\E_{P}[f]
  \le
  \E_{Q}[f]  
  \le & 
  % \E_{Q^+}[f]-\E_{P}[f]=
  \E_{P}[f]+\go{Q^+}Pf\,  \quad \mbox{for all  $Q\in \mathcal{Q}_\eta$ } 
\end{aligned}
\end{equation}
and the bounds are tight in $\mathcal{Q}_\eta$, in the sense 
that inequalities become equalities  for $Q=Q^\mp$ respectively. 
%
%\begin{theorem}
%Consider a fixed probability distribution $P$ and all approximate probability models $Q$ within a KL tolerance $\eta^2$, \ie consider all models in   $\mathcal{Q}_\eta:=\{Q: R(Q\|P) \le \eta^2\}\, . $ Let $P^{c_\pm}$ be the members of the exponential family \eqref{eq:parametric} and $c_{\pm}$ satisfy $$R(P^{c_\pm} \| P)=\eta^2.$$ Then, for the models $Q^-=P^{c_-}$, $Q^+=P^{c_+} \in \mathcal{Q}_\eta$,  we have the maximum and minimum model bias in the family $\mathcal{Q}_\eta$:
%
%\begin{align}
 % \label{eq:max}
  %\gop{Q^+}Pf &= \E_{Q^+}[f]-\E_{P}[f]=
         %       \max_{Q\in %\mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f],\\
%  -\gom{Q^{-}}P{f}& = \E_{Q^-}[f]-\E_{P}[f]=
%                    \min_{Q\in \mathcal{Q}_\eta}\E_{Q}[f]-\E_{P}[f]
%                    \label{eq:min}
%\end{align}
%therefore we obtain the model bias  bounds 
%\begin{equation}
%\label{it:go:tightness:thm}
%  -\gom{Q^{-}}P{f}+\E_{P}[f]
  % = \E_{Q^-}[f]-\E_{P}[f]
%  \le
 % \E_{Q}[f] \le 
  % \E_{Q^+}[f]-\E_{P}[f]=
 % \E_{P}[f]+\gop{Q^+}Pf\, \quad \mbox{for all  $Q\in \mathcal{Q}_\eta$ } \quad
%\end{equation}
%with the two equalities holding if $Q=Q^\mp=P^{c_\mp}$ respectively. 
%\end{theorem}
%
%
This tightness property is crucial for our discussion because it implies that the GO divergence bounds in~(\ref{eq:intro:bias-bound-go:sec2}) are the best possible in the sense that they have attainable worst-case model scenarios $Q^\pm$ among all probability distributions $Q$ within a KL tolerance
% \ie consider all models $Q$ such that $\R QP\le \eta^2$ for some fixed
$\eta^2>0$, see the schematic in Figure~\ref{fig:tightness_GO}. 
\begin{figure}[!ht]
  \centering \includegraphics[width=0.5\textwidth]{figures/Tightness_GO}
  \caption{ The schematic depiction of Theorem~\ref{thm:tightness} for the QoIs $f_1$, $f_2$ with tolerance $\eta^2$. The solid lines depict the one-parameter tilted
    probability distributions $P^c$ corresponding to the QoIs. The theorem
    implies that the upper and lower bounds in the family
    $\mathcal{Q}_\eta=\{Q: R(Q\|P) \le \eta^2\}$ are attained at the
    probability measures $Q^{\pm}=P^{c_{\pm}}$ for the QoI $f_1$. }
  \label{fig:tightness_GO}
\end{figure}


\begin{remark}{\rm 
The tightness
property~(\ref{it:go:tightness:thm}) is a \textit{non-parametric} result: the family $\mathcal{Q}_\eta$
of all alternative models Q  cannot be parametrized in general and is only
characterized by the property $\R QP\le \eta^2$. In spite of this non-parametric
framework, we showed in Theorem~\ref{thm:tightness}
that the extremal models $Q^\pm$ that yield the tight bounds \eqref{it:go:tightness:thm}
belong to the parametrized family \eqref{eq:parametric},  see also Figure~\ref{fig:tightness_GO}. 
}
\end{remark}
 \begin{table}
  \centering
    \caption{
    \label{tab:estimator-cost}
    For the estimation of $\Vp[Y]$, we assume that $\Ep[Y]$ is unknown and that
    the bias-adjusted estimator is used. For the variance of $\Ep[e^{cY}]$, a
    first-order approximation is used (see \cite{wasserman2004}),
    assuming that $\Ep[Y]$ is small.}
    
    \begin{tabular}{|c||c|}
    \hline
      Quantity& Variance of estimator\\
      \hline 
      $E_P[Y]$& $\Vp[Y]/n$\\
      \hline
      $\Vp[Y]$& $2(\Vp[Y])^2/(n-1)$\\
      \hline
      $\Mp{c;Y}$& $c^2e^{2c\Ep[Y]}\var_P[Y]/n$\\
      \hline
    \end{tabular}
  \end{table}
The  attractive properties of the GO bounds demonstrated in Theorem~\ref{thm:GO-bounds} and 
Theorem~\ref{thm:tightness}, come at a potentially significant cost since they require the knowledge or calculation of the MGF $\Mp{c;\ti f}$ with respect to model $P$. 
If no simple formula for $\Mp{c;\ti f}$ is known,   this can be  a data-intensive operation---compare the estimator variance of the MGF with that of other QoIs in Table~\ref{tab:estimator-cost}. 
Controlling the variance of  an MGF estimator will require a large amount of data and/or the use of a
  multi-level Monte Carlo method, see also the discussion in
  Section~\ref{sec:intro} and 
  Section~\ref{sec:epistemic-UQ-conc}. 
  %
  
In the next section we introduce a new class of inequalities that share the aforementioned  features of the GO divergence and \eqref{eq:intro:bias-bound-go:sec2}, 
but they can  bypass the estimation of an MGF by using the concept of concentration inequalities.


  \section{Concentration/Information Inequalities  for Model Bias}
  \label{sec:conc-ineq}
  To bypass the estimation or 
  computation of the MGF in \eqref{eq:intro:godiv:2} we will  use a QoI-dependent concentration bound for the MGF, \ie a function $\Phip{c}$
taking values in $(0, \infty]$ 
such that 
%
  \begin{align}
    \label{eq:conc:mgf-bound}
    \Mp{c;\ti f}\leq \Phip{c} %\text{ for all } g\in \Fp
  \end{align}
for all $c \in \mathbb{R}$. 
Since the moment generating function 
$\Mp{c;\ti f}$ can take the 
value $+\infty$ it is natural to 
allow the same for $\Phip{c}$. 

Bounds of the form 
\eqref{eq:conc:mgf-bound},
 for explicitly computable 
 functions $\Phip{c}$,
are called concentration inequalities  and we discuss  several such examples in Section~\ref{sec:unbounded-obs} and Section~\ref{sec:bounded-obs}, as well as in Section \ref{sec:scalability}. 
Although we use only the simplest concentration inequalities here, the results are indicative  to what can be accomplished using such 
  information on $f$ and $P$. In upcoming work, we will consider further applications for 
  stochastic  processes and interacting particle systems arising in Kinetic Monte Carlo and molecular dynamics models.
Concentration inequalities is an important  mathematical tool
since they allow, via a Chernov bound, to control  tail events, i.e. they provide explicit bounds on the probability that a
random variable deviates from typical behavior. More specifically, such methods  can address, among others, questions on rare events~\cite{dembo2010large}, model selection
methods~\cite{massart2007concentration}, statistical mechanics~\cite[Section
8.4]{ledoux2005concentration} and random matrices~\cite{tropp2015introduction}.  
%
Here we propose the use of concentration inequalities in tandem with the information inequalities \eqref{eq:intro:bias-bound-go:sec2}
for uncertainty quantification and especially for providing model bias guarantees.
% using them to simplify the implementation of the information inequalities developed in
% \cite{dupuis2011uq,katsoulakisuq16}, while at the same time maintaining and expanding their
% theoretical advantages. 
In  Theorem~\ref{thm:generalized-go-bounds} we show how to construct 
new bounds for the model bias using a function  $\Phi$ satisfying (\ref{eq:conc:mgf-bound}).

\begin{theorem}
  \label{thm:generalized-go-bounds}
  Let $P$ be a probability measure and let $f$ be a QoI such that its MGF $\Mp{c;\ti  f}$ is finite in a neighborhood of the origin. 
%  
 % 
%  Let $f$ be a QoI such that
%  $\Mp{c;\ti f}$ is finite in a neighborhood of  $c=0$.  
  %let $Q$ be such that $\R QP\le \eta^2$ for some $\eta >0$
  %and a QoI $f$ such that
  %$\Mp{c;\ti f}$ exists in a  region around zero. 
Let $\Phi:\mathbb{R}\to  (0,\infty]$  be a  function with $\Phip{0}=1$, $\Phi'(0)=0$ and such that 
  \begin{equation}
  \label{eq:conc:mgf-bound:thm}
  \Mp{c;\ti f}\leq \Phip{c}
  %\quad \mbox{for all $c \in (-c_0, c_0)$}\, ,
  \end{equation}
 for all $c \in \mathbb{R}$.
%
%Assume that there exists a convex function $\Phi:\mathbb{R}\to \mathbb{R}^{+}$ such that
%  $\Phip{0}=0$, $\Phi'(0)=0$, and 
%  \begin{equation}
%  \label{eq:conc:mgf-bound:thm}
%  \Mp{c;\ti f}\leq \Phip{c}
  %\quad \mbox{for all $c \in (-c_0, c_0)$}\, ,
 % \end{equation}
% for all $c \in \mathbb{R}$.
  %for which $\Mp{c;\ti f}$ is finite. 
  We define the set of admissible QoIs by
  \begin{align}
    \label{eq:Fp}
    \Fp=\{g:\Mp{c;\tilde g}\leq \Phip{c} %\quad c \in (-c_0, c_0)
    \}.
  \end{align}
Then,  $f \in \Fp$,  and for every $Q\in \efam =\{Q: R(Q\|P) \le
\eta^2\}$  we have
\begin{equation}
 \label{eq:U-bounds-bias}
 \begin{aligned}   
    -\Um \eta\Fp &\leq \Eq[g]-\Ep[g]  &\leq \Up \eta\Fp\, \quad  \mbox{for every $g\in\Fp$}\, ,
    \end{aligned}
\end{equation}
    where 
    \begin{equation}
    \Upm \eta\Fp:=\inf_{c>0}\left \{\frac{1}{c}\log\Phi(\pm c)+\frac{1}{c} \eta^2 \right\}. \label{eq:U-divpm}
  \end{equation}
\end{theorem}
\begin{proof}
The proof follows immediately from \eqref{eq:intro:godiv:2} and \eqref{eq:intro:bias-bound-go:sec2}, combined with the concentration inequality \eqref{eq:conc:mgf-bound:thm} and the definition of the admissible QoIs, $\Fp$. We discuss specific examples of inequalities of the type  \eqref{eq:conc:mgf-bound:thm} and their corresponding admissible sets $\Fp$, in Section~\ref{sec:unbounded-obs} and Section~\ref{sec:bounded-obs} below.
\end{proof}

% Theorem~\ref{thm:generalized-go-bounds} readily implies that for all
% $\eta$-admissible models $Q$, \ie $Q\in \mathcal{Q}_\eta$, the QoIs under
% consideration lie within the specified region of uncertainty, $[-\Um \eta\Fp ,\ \Up
% \eta\Fp]$.

% \begin{corollary}
%   \label{cor:generalized-go-bounds-region}
%   Under the assumptions of Theorem~\ref{thm:generalized-go-bounds} we have for
%   all models $Q\in \mathcal{Q}_\eta=\{Q: R(Q\|P) \le \eta^2\}$ and for all QoIs
%   $f \in \Fp$ that
% %
%   \begin{align}
%     \label{eq:U-bounds-bias-region}
%     -U_{-}(\eta;\Fp) \leq & \Eq[f]-\Ep[f]  \leq U_{+}(\eta;\Fp), \\
%     % -U_{-}(\eta;\Fp)+\Ep[f] \leq & \Eq[f] \leq
%     % \Ep[f]+U_{+}(\eta;\Fp) \quad
%     % -\Um \eta \Fp &\leq \Eq[f]-\Ep[f] \leq \Up QP\Fp, \\
%     \mbox{where} \quad 
%     U_{\pm}(\eta;\Fp):&=\inf_{c>0}\left\{ \frac{1}{c}\log\Phi(\pm c)+\frac{1}{c}\eta^2 \right\}. \label{eq:U-divpm-region}
%   \end{align}
% \end{corollary}

\begin{remark}[Admissible set of QoIs]{\rm
\label{rem:admiss}
We note that the function 
$\Phi$ depends both on the QoI 
$f$ and on $P$ through 
\eqref{eq:conc:mgf-bound:thm}
and therefore the  set of 
admissible functions $\Fp$ also 
depends on the QoI $f$ and on 
$P$. However, to keep notation simple, we suppress this dependence for both $\Phi$ and $\Fp$.
}
\end{remark}

\begin{remark}
[Computing $\Upm \eta\Fp$]{\rm   
Some concentration bounds  \eqref{eq:conc:mgf-bound:thm} such as the sub-Gaussian and  Hoeffding bounds discussed below provide explicit formulas for $\Upm \eta\Fp$, see for instance \eqref{eq:sub-G-Upm} and (\ref{eq:hoef-u}). However, in general---see the sharper Bennett bounds in~(\ref{eq:bennet-mgf-ineq} and
(\ref{eq:bennet-(a,b)})---we have an explicit formula for $\Phi$ but no explicit closed form solution of the optimization over $c$. 
%we have to solve the two optimization
%problems in \eqref{eq:U-divpm} numerically.
% %
% \begin{align}
%   \label{eq:optim-prob}
%   \inf_{c>0} \left\{ \log \Phip{\pm c}/c+\eta^2/c \right\}.
% \end{align}
The elementary one-dimensional optimization in \eqref{eq:U-divpm} can be carried out with standard solvers, \eg Newton's method.
% Further discussion on the computation
% of the bounds can be found in \ref{sec:technical}.
}
\end{remark}


\sepeq{Divergence structure of $\Upm \eta\Fp $:}
The following properties of the bounds  $U_{\pm}$ in 
\eqref{eq:U-divpm}
are analogous to the properties of the GO divergence \eqref{eq:intro:godiv:2} outlined in Theorem~\ref{thm:GO-bounds}. One notable difference is that here the divergence structure defined by $\Upm \eta\Fp $ contains information about the entire family $\Fp$ in \eqref{eq:Fp}
and not just a single QoI $f$ as was the case in the GO divergence \eqref{eq:intro:godiv:2}.



\begin{theorem}\label{thm:div-U}
Under the assumptions of Theorem~\ref{thm:generalized-go-bounds} and, in addition, if 
\begin{equation}    \label{eq:tightness:U:condition:thm:div-U}
    \Phi(c)=M_{\bar P}(c; \tilde h)\, ,  
  \end{equation} 
 for  some probability $\bar P$ and QoI $h$ and all $c \in \mathbb{R}$ then $\Upm\eta\Fp$ satisfy: 
\begin{enumerate}
\item {\it Divergence Properties:} \label{it:u:non-neg} 
\begin{itemize}
\item[a.] $\Upm \eta\Fp \geq 0$,  and 
\item[b.] $\Upm \eta\Fp=0$ if and only if $\eta=0$ or $\Fp$ is trivial, i.e. consists only  of functions which are constant $P$-a.s. 
\end{itemize}
%\item \label{it:u:div} $\Upm \eta\Fp=0$ if and only if $\eta=0$.
\item \label{it:u:linear}{\it Linearization:}  If $\Phi=\Phi(c)$ is twice differentiable in a neighborhood of $c=0$, then we have the asymptotics  
$\Upm \eta\Fp=\sqrt{2\Phi''(0)}\eta +O(\eta^2)$ and thus,
\begin{equation}
\label{eq:linearize-U}
 \begin{aligned}
%    \label{eq:linearize-U-0}  
%    \Upm \eta\Fp&=\sqrt{2\Phi''(0)}\eta +O(\eta^2)\, ,
 %   \\
    |\Eq[g]-&\Ep[g]| \leq \sqrt{2\Phi''(0)}\eta +O(\eta^2)\,   &\mbox{for all $g \in \Fp$} \quad \mbox{and  all $Q\in \efam$}\, .
 \end{aligned}
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof} The proof follows from Theorem~\ref{thm:GO-bounds}.  Indeed since, by assumption, $\Phi(c)=M_{\bar P}(c; \tilde h)$ we have 
\begin{equation}
\Upm \eta\Fp = \go Q{\bar P}{\pm h} 
\end{equation} 
for any probability $Q$ such that $\R Q {\bar P}=\eta^2$.  Therefore, by Theorem~\ref{thm:GO-bounds}, $\Upm \eta\Fp \ge 0$ and  
$\Upm \eta\Fp = 0$ if and only if  $\eta =0$ or $h$ is constant ${\bar P}$ a.s.  But if  
$h$ is constant ${\bar P}$ a.s then $\Phi(c)=M_{\bar P}(c; \tilde h)=1$ for all $c$ and thus the set of admissible QoIs \eqref{eq:Fp} becomes: 
\begin{align}
    \label{eq:Fp:app}
    \Fp=\{g:\Mp{c;\tilde g}\leq \Phip{c}=1
    %\quad c \in (-c_0, c_0)
    \}\, .
  \end{align}
However for any $g \in \Fp$, 
by Jensen's  inequality, $\Mp{c;\tilde g}\ge 1$ since $\mathbb{E}_{P}[\tilde g]=0$.  Therefore the admissible set $\Fp$ consists only  of constant functions thus $g$ is constant $P$-a.s. Finally, the linearization in Theorem~\ref{thm:div-U} is proved similarly to the linearization result 
of the GO divergence in Theorem~\ref{thm:GO-bounds},  (see the proof in Section 3 of \cite{katsoulakisuq16}).
\end{proof}







Theorem~\ref{thm:generalized-go-bounds} 
and Theorem~\ref{thm:div-U}
motivate the following definition, in analogy to the goal oriented (GO) divergence \eqref{eq:intro:godiv:2} defined for a single QoI $f$:

\begin{definition}[Concentration/Information Divergence]
Given the notation and assumptions of Theorem~\ref{thm:generalized-go-bounds} and Theorem~\ref{thm:div-U}, we define the concentration/information divergence between a baseline model $P$ and the family  of  models $\efam$, satisfying \eqref{eq:U-bounds-bias}
for all   QoIs  in $\Fp$:
\begin{equation}
    \Upm \eta\Fp:=\inf_{c>0}\left \{\frac{1}{c}\log\Phi(\pm c)+\frac{1}{c} \eta^2 \right\}\, , \label{eq:U-divpm:def}
  \end{equation}
where $\efam$  and $\Fp$, are defined in    \eqref{Qfamily}
and \eqref{eq:Fp} respectively.

\end{definition}



\begin{remark} [Features of Concentration/Information Inequalities]
{\rm 
While the GO divergence bounds \eqref{eq:intro:bias-bound-go:sec2} are defined for a specific QoI $f$,  key features  of the 
new bounds in Theorem~\ref{thm:generalized-go-bounds} include:  \begin{enumerate*} \item[(a)] allow to consider whole families of admissible QoIs
$\Fp$ defined in (\ref{eq:Fp}),
and \item[(b)] they bypass the costly MGF
calculations needed in the GO divergence  \eqref{eq:intro:godiv:2}. \end{enumerate*} 
% Indeed, the set of all admissible $\Fp$ can be described in terms of QoIs
% that satisfy the requirements of the bound $\Phip{c}$. Unless otherwise stated,
% $\Fp$ will be 
 Finally,  we next show that the new bounds \eqref{eq:U-bounds-bias} still share the advantages of the  GO divergence bounds, namely: in    Section~\ref{sec:sharpness-and-robustness} we  prove that   \eqref{eq:U-bounds-bias} is, (c) tight in the family of models $\efam$, \eqref{Qfamily}, and the family of QoIs $\Fp$, \eqref{eq:Fp}.
 in Section~\ref{sec:scalability} we show that \eqref{eq:U-bounds-bias} is,  (d) scalable to   QoIs that depend on large numbers of data such as statistical estimators  and  to high dimensional probabilistic models.  
}
\end{remark}



% We summarize this general discussion noting that  the concentration bounds  on the MGF \eqref{eq:conc:mgf-bound:thm} will allow
% us to quantify model bias, in accordance to
% Theorem~\ref{thm:generalized-go-bounds}. 
We will next discuss   specific examples of the bound $\Phip{c}$ in the  concentration bounds  \eqref{eq:conc:mgf-bound:thm} and Theorem~\ref{thm:generalized-go-bounds}; furthermore, we also demonstrate  how we can select 
such  concentration bounds depending on the information we have regarding the distribution $P$. We divide our presentation into two  cases, namely bounded and unbounded QoIs $f$.


\subsection{Sub-Gaussian Bounds}
%$\Phip{c}$: Unbounded QoIs}
\label{sec:unbounded-obs}
For an unbounded QoI $f$ and a probability distribution $P$, we can characterize
the type of concentration by bounding either the tail probabilities $P(f(X)-\Ep[f]>a)$ for all $a$ or
$\Mp{c;\ti f}$ for all $c$ for which the MGF is finite. In this section, we discuss the (classical) sub-Gaussian 
concentration bounds which are characterized by Gaussian
decay of the tails.  
Sub-exponential bounds (see
Section~\ref{ex:expo-dist}) 
and sub-Poissonian bounds 
could also be useful in 
various situations but we will not discuss them further here (see e.g. \cite{ledoux2005concentration}). 


% See also 
% Section~\ref{ex:expo-dist} for sub-Exponential concentration bounds  


% and \ref{ex:poisson-tails}
% for Poisson-like concentration bounds.
% \tdi{We should change the statement here because we do not include poisson behavior any more.}


\sepeq{Sub-Gaussian concentration bounds   ~\cite{concentration}
:} We say that $f=f(X)$ is a sub-Gaussian random variable if there
exists a $\sib>0$ such that
\begin{align}
  \label{eq:sub-Gaussianity}
  \Mp{c;\ti f}\leq \Phip{c}:=\exp(c^2\sib^2/2) \text{ for all } c\in\mathbb{R}.
\end{align}
Now given  a fixed $\sib$, we can consider the family of QoIs defined in \eqref{eq:Fp}, 
\begin{equation}
\label{eq:Fp:subG}
\Fp:=\{g:\Mp{c;\tilde g}\leq \Phip{c}=\exp(c^2\sib^2/2)\}\, ,
\end{equation}
i.e. we consider  all random variables with MGF bounded by the MGF of a normal random variable with
variance $\sigma_B^2$. Furthermore, using \eqref{eq:U-divpm} we can write an explicit formula for
$\Upm{\eta}\Fp=\inf_{c>0}\{\frac{c \sigma_B}{2}+ \frac{\eta^2}{c}\}$ as 
% 
\begin{align}
  \label{eq:sub-G-Upm}
  \Upm \eta\Fp=\sib \sqrt{2} \eta. 
\end{align}
%
By expanding
$\Mp{c;\ti f}$ around $c=0$, we can readily show that $\sib^2$ is an upper bound
of $\Vp[f(X)]$. 
%
Relation~(\ref{eq:sub-G-Upm})  also implies that there is no
$\eta$-admissible model $Q\in \mathcal{Q}_\eta$ for which the QoIs under
consideration lie beyond the uncertainty  region  given by
Theorem~\ref{thm:generalized-go-bounds}:
\begin{equation}
  -\sib \sqrt{2}\eta\leq \E_Q[g]-\E_P[g] \leq
  \sib \sqrt{2}\eta
\end{equation}
for all models $Q\in \mathcal{Q}_\eta$ and QoIs $g \in
\Fp$. In Corollary~\ref{cor:coeff-of-var}, we consider the special case where $P$
is a normal distribution which is compared against any models $Q$--possibly not normal--from $\efam$. 

\begin{corollary}
  \label{cor:coeff-of-var}
  Consider the QoI $f(x)=x$ where $P=N(\mu,\sigma^2)$. Also, let $Q$ be any distribution such that $\R QP\le \eta^2$. Then, if the coefficient of variation (also known as relative standard deviation) is $c_v:=\sigma/|\mu|$, the relative model bias satisfies: 
  \begin{equation*}
    -c_v \sqrt{2}\eta \le \frac{\Eq[f]- \Ep[f]}{|\Ep[f]|} \leq c_v \sqrt{2}\eta \, . 
  \end{equation*}
\end{corollary}

% Note that Corollary~\ref{cor:coeff-of-var} is a non-parametric result as far as
% $Q$ is concerned. The only assumption is that $P$ is Gaussian and $Q\in \efam$. 

In general, sub-Gaussianity is a strong assumption for an unbounded random
variable. For example, if $P=\mathrm{Laplace}(1)$, \ie a two-sided exponential
distribution centered at zero, then $\Mp{c;X}=1/(1-c^2)$, $|c|<1$, which cannot
be bounded by any $\exp(c^2 \sib^2/2)$ for all $c$. 
Finally, we note that results like the McDiarmid's inequality, see
Section~\ref{sec:scalability} below,  or  the logarithmic Sobolev inequalities~\cite{raginsky2013concentration,bobkov1999exponential},  can provide values for the constant 
$\sib^2$ for  QoIs that satisfy specific properties, \eg \eqref{eq:mcdiarmid-cond}.

% We can relax this
% requirement by instead using a function $\Phip{c}$ that bounds the MGF for all
% $c$ in some (potentially small) region around zero.


\subsection{Bennett and Hoeffding Bounds}
%$\Phip{c}$: Bounded QoIs}
\label{sec:bounded-obs}
Many quantities of interest are bounded such as failure  probabilities or   functions of random variables with bounded support.
Bounded random variables are necessarily sub-Gaussian~\cite{concentration},
but much sharper bounds for their MGFs, \eqref{eq:conc:mgf-bound:thm}, can be derived and used to bound the
worst-case bias through Theorem~\ref{thm:generalized-go-bounds}. In this direction, we next
discuss some additional  concentration bounds for bounded QoIs, that we will also showcase  in examples in this work. This list is not
complete by any means and other concentration inequalities can be used here, 
see for instance~\cite{raginsky2013concentration} for other bounds. For each case below, the family of
QoIs $\Fp$ is defined in terms of the concentration bound on the MGF, \eqref{eq:Fp}, as in Theorem~\ref{thm:generalized-go-bounds}.

\sepeq{Bennett concentration bound}~\cite[Lemma 2.4.1]{dembo2010large}: Consider the   random variable $X$ where $X\sim P$  and the  QoI $f=f(X)$ such that $f(X)\leq b$,  for some $0 \le b < \infty$. Setting
$\mu:=\Ep[f(X)]$, $\tilde{b}:=b-\mu$, we have
\begin{equation}
\label{eq:bennet-mgf-ineq}
\begin{aligned} 
  \Mp{c;\ti f}\leq \Phip{c}:=&\frac{\tilde{b}^2}{\tilde{b}^2+\sib^2}\exp(-c\sib^2/\tilde{b})
  +& \frac{\sib^2}{\tilde{b}^2+\sib^2}\exp(c\tilde{b}), 
\end{aligned}
\end{equation}
for all $c\geq 0$ and where $\sib^2$ is any upper bound of $\Vp[f]$. Therefore, keeping in mind Remark~\ref{rem:admiss}, we define
\begin{equation}
\label{eq:Fp:Bennett}
\begin{aligned}
\Fp=&\{g:\Mp{c;\tilde g}\leq \Phip{c}\, 
%,  \; f(X)\leq b\, , \;  \Vp[f] \le \sib^2\, %, \; \mu=\Ep f\, 
\}\, ,   &\mbox{where $\Phi$ is defined in \eqref{eq:bennet-mgf-ineq}.}
\end{aligned}
\end{equation}
%$\Phip$ is defined in \eqref{eq:bennet-mgf-ineq}.


\sepeq{Bennett-$(a,b)$ concentration bound}~\cite[Corollary 2.4.5]{dembo2010large}: If the QoI $f$ is
such that $a\leq f(X)\leq b$, $X\sim P$, then we can set $\sib^2=(\mu-a)(b-\mu)$
in the Bennett bound to obtain
% 
\begin{equation}
\label{eq:bennet-(a,b)}
\begin{aligned}
  \Mp{c;\ti f}\leq \Phip{c}:=\frac{\tilde{b}}{b-a}\exp(c\tilde{a})-\frac{\ti {a}}{b-a}\exp(c\tilde{b})  \text{ for all }  c\in\mathbb{R}.
\end{aligned}
\end{equation}
The right-hand side of~\eqref{eq:bennet-(a,b)} is the MGF of a
Bernoulli-distributed random variable with values $\{a,b\}$. Note that the
Bernoulli is the distribution with the most ``spread'' around the mean value
between all bounded random variables in $[a,b]$. Similarly to \eqref{eq:Fp:Bennett} we have,
\begin{equation}
\label{eq:Fp:Bennettab}
\begin{aligned}
\Fp=&\{g:\Mp{c;\tilde g}\leq \Phip{c}\, 
%,  \; a \le f(X)\leq b\, 
%, \; \mu=\Ep f\, 
\}\, , &\mbox{where $\Phi$ is defined in \eqref{eq:bennet-(a,b)}.}
%, \; \mu=\Ep f \,%\quad c \in (-c_0, c_0) \}.
\end{aligned}
\end{equation}
%where $\Phi$ is defined in \eqref{eq:bennet-(a,b)}.

\sepeq{Hoeffding concentration bound}\cite{hoeffding1963probability,dembo2010large}: When the QoI $f$ is bounded as
in the Bennett-$(a,b)$ case, we can further bound the Bennett-$(a,b)$ bound  by a Gaussian MGF,
giving rise to  the (less tight)  Hoeffding MGF bound,
%
\begin{align}
  \label{eq:Hoeffding}
  \Mp{c;\ti f}\leq \Phip{c}:=\exp(c^2(b-a)^2/8) \text{ for all } c\in\mathbb{R}.
\end{align}
% Unlike the Bennett bounds,  the Hoeffding bound is independent of the location of the mean $\mu$ within the
% interval $(a,b)$ and only depends on the length of the interval $[a, b]$. As such, it
% requires the least amount of information about $f$ and $P$ and is the least
% sharp of the bounds, as can be also seen in the example in Section~\ref{ex:truncated-normal}. 
As in
the sub-Gaussian case of Section~\ref{sec:unbounded-obs}, we can calculate $\Upm
\eta\Fp$ explicitly:
%
\begin{align}
  \label{eq:hoef-u}
  \Upm \eta\Fp =  (b-a)\sqrt{2}\eta. 
\end{align}
Finally the set of QoIs is 
\begin{equation}
\label{eq:Fp:Hoeffding}
\begin{aligned}
\Fp=&\{g:\Mp{c;\tilde g}\leq \Phip{c}\, 
%,  \; a \le f(X)\leq b \,
%\quad c \in (-c_0, c_0)
    \},  &\mbox{where $\Phi$ is defined in \eqref{eq:Hoeffding}.}
\end{aligned}
\end{equation}
%where $\Phi$ is defined in \eqref{eq:Hoeffding}.
\begin{table}
  \centering
  \caption{\label{tab:MGF-bounds} The different MGF bounds along with the
    conditions they impose on $P$ and $f$ and the quantities they depend on for
    their implementation if we are interested in quantifying the worst-case
    bias. However, bounding the worst-case $\Eq[f]$ \textit{does not} require
    $\Ep[f]$. Gaussian decay of the tails of the distribution of $f(X)$ implies
    the sub-Gaussian MGF bound (similar assumptions about the tails exist for
    the rest of the bounds). In terms of information requirements, the Hoeffding
    bound requires the least amount, but it is also the least tight. As
    available information/data  for the bounds grow, the bounds get tighter.}
  \begin{tabular}{|l|c|c|c|r|}
    \hline
    Name & Conditions on $f,P$ & $\Phi=\Phi(c)$ input \\
    \hline
    Hoeffding~(\ref{eq:Hoeffding}) & $a\leq f(X)\leq b$& $a,b$  \\
    Bennett-$(a,b)$~(\ref{eq:bennet-(a,b)})& $a\leq f(X) \leq b$& $\Ep[f],a,b$   \\
    Bennett~(\ref{eq:bennet-mgf-ineq})& $f(X)\leq b$, $\Vp[f]\leq \sib^2$& $\Ep[f],b,\sib$ \\
    \hline \hline
    % unbounded case
    sub-Gaussian~(\ref{eq:sub-Gaussianity})& $\Mp{c;\ti{f}}\leq \exp( \sib^2c^2/2)$ & $\sib$\\
    \hline \hline 
    GO bound~(\ref{eq:intro:godiv:2}) & $\Mp{c;\ti f} < \infty $ &  $\Ep[(f)^k]$ for all $k$\\
    \hline
  \end{tabular}
\end{table}

\begin{remark}[Hierarchy of bounds]{\rm
  \label{rem:order}
 % By Lemma 2.4.1 and Corollary 2.4.5 in~\cite{wainwright2015high}, 
 It is straightforward to demonstrate that we can order
  the bounds in terms of accuracy, noting that  if the QoI $f$ is bounded in $[a,b]$,  then we always have the bound
  $\sib^2\leq (\Ep[f]-a)(b-\Ep[f])$ in the Bennett bound \eqref{eq:bennet-mgf-ineq}. Therefore, we have the hierarchy of concentration bounds:
 % 
  \begin{align}
    \label{eq:ordering}
    \Mp{c;\ti f} 
    %\sim \text{GO bound}
    \leq \text{Bennett} \leq \text{Bennett-(a,b)}\leq \text{Hoeffding}. 
  \end{align}
  Unlike the two Bennett bounds,  the Hoeffding bound is independent of the location of the mean $\mu$ within the
interval $[a,b]$ and only depends on the length of the interval $b-a$.  As such, it
requires the least amount of information about $f$ and $P$ and is the least
sharp of the bounds, see Table~\ref{tab:MGF-bounds}
and the requirements for the QoI families $\Fp$, \eqref{eq:Fp:Bennett}, \eqref{eq:Fp:Bennettab} and \eqref{eq:Fp:Hoeffding}.  On the other end, the GO divergence bound---involving $\Mp{c;\ti f}$---is the  tightest, as we see in \eqref{eq:ordering}, but also the most expensive to implement, see 
Table~\ref{tab:estimator-cost}. We  also refer to a demonstration of this hierarchy in the example in Section~\ref{ex:truncated-normal}. Overall, as
    available information/data  on the QoI $f$ and and the baseline model $P$ grows, concentration  bounds and therefore model bias bounds become tighter.
    Finally, we  refer to Figure~\ref{fig:contour-bennet}, where we demonstrate the tightness of the model bias bounds \eqref{eq:U-bounds-bias},
    \eqref{eq:U-divpm}, 
    in terms of both $\eta^2=\R QP$ and $\sib$, for the  
    Bennett bounds \eqref{eq:bennet-mgf-ineq}.
    }
\end{remark}

\begin{figure}
  \centering \includegraphics[width=0.499\textwidth]{figures/contour_comparing}
  \caption{\label{fig:contour-bennet} Level curves of the upper  model bias bound \eqref{eq:U-bounds-bias} with the
    Bennett bound \eqref{eq:bennet-mgf-ineq} and assuming $b=1$, $\Vp[f]\leq \sib^2$. Knowing $\eta^2=\R QP$ for
    some model $Q$ and an upper bound on the variance provides model-bias
    guarantees (through Theorem~\ref{thm:generalized-go-bounds}). Further
    reduction of the model bias bound requires a corresponding---and potentially
    expensive---decrease in KL and/or a tighter upper-bound for $\Vp[f]$, for
    example, by incorporating additional data. The tightest possible guarantee
    afforded by the Bennett bound is gained when $\sib^2=\Vp[f]$ and
    $\eta^2=\min_Q{\R QP}$.}
\end{figure}


\begin{remark}{\rm 
\label{rem:size:Fp}[How large is the class 
%of admissible QoIs 
$\Fp$?]
 A plausible question is how rich is the set of admissible QoIs, $\Fp$ derived by the various  concentration bounds on the MGF $\Mp{c;\ti g}$ in
\eqref{eq:Fp:subG}, \eqref{eq:Fp:Bennett}, \eqref{eq:Fp:Bennettab} and   \eqref{eq:Fp:Hoeffding}. Here we address this question in the context of the Bennett bound, however the same argument also applies to the Bennett-$(a,b)$ and Hoeffding bounds,
as well as to the sub-Gaussian case in Section~\ref{sec:unbounded-obs}.
%
We can get a simple first  insight in this direction based on \eqref{eq:bennet-mgf-ineq}. Indeed, based on the conditions for this inequality to hold, we readily have that 
$$
\Fp \supset \{g: \; g(X)\leq b\, , \;  \Vp[g] \le \sib^2\, , \; \Ep g=\mu\, 
\}\, .
$$
We also note that enforcing the condition on the mean, $\Ep g=\mu$, is trivial and involves only a translation of the QoI $g$. 
}
\end{remark}



\section{Tightness of the Concentration/Information Inequalities}
\label{sec:sharpness-and-robustness}
In this section we show that, under suitable assumptions, for the concentration/information bounds derived in Section~\ref{sec:conc-ineq} the divergence  $\Upm \eta \Fp$ retains some of the tightness properties of the  GO divergence  $\go QPf$  established in Section~\ref{sec:outline}.

\begin{theorem}
  \label{thm:sharpness-of-U}
Let $P$ be a probability  and  $ \mathcal{Q}_\eta=\{Q: R(Q\|P) \le \eta^2\}$. 
Assume $\Phi(c)=M_{P}(c; \tilde f)$ is   a
MGF for some QoI $f$ with respect to $P$ and let 
\begin{equation}
    \Fp=\{g:\Mp{c;\tilde g}\leq \Phip{c}\, \textrm{ for all } c  \in \mathbb{R}\}\,.
  \end{equation} 
Then,  there exist 
%$f \in \Fp$ 
probabilities $\Ptil{\pm} \in \mathcal{Q}_\eta$ (see  \eqref{eq:parametric}) that satisfy $\R {\Ptil{\pm}}P=\eta^2$ 
and 
\begin{equation}
 \label{eq:U-sharp-plus}
\begin{aligned}
 \Up \eta\Fp &= \E_{\Ptil{+}}[f]-\E_{P}[f]
 &=\max_{Q\in \mathcal{Q}_\eta \,, g \in \Fp}\E_{Q}[g]-\E_{P}[g],
\end{aligned}
\end{equation}
\begin{equation}
 \label{eq:U-sharp-minus}
 \begin{aligned}
    -\Um \eta\Fp & = \E_{\Ptil{-}}[f]-\E_{P}[f]  &=
                   \min_{Q\in \mathcal{Q}_\eta\,, g \in \Fp}\E_{Q}[g]-\E_{P}[g]\, ,                  
 \end{aligned}  
\end{equation}
\ie the maximum and minimum for 
model bias is attained within the family of models $\mathcal{Q}_\eta$ and the family of QoIs $\Fp$, see the schematic in Figure \ref{fig:tightness}. 
% %
%   \begin{align}
%     \label{eq:U-sharp-plus}
%     \Up \eta\Fp &= \E_{\Ptil{+}}[G]-\E_{P}[G]=
%                   \max_{Q\in \mathcal{Q}_\eta\atop g \in \Fp}\E_{Q}[g]-\E_{P}[g],\\
%     -\Um \eta\Fp & = \E_{\Ptil{-}}[G]-\E_{P}[G]=
%                    \min_{Q\in \mathcal{Q}_\eta \atop g \in \Fp}\E_{Q}[g]-\E_{P}[g]\, ,
%                    \label{eq:U-sharp-minus}
%   \end{align}  
%   % \begin{equation}
  %   \label{eq:U-sharp-plus}
  %   \E_{\Ptil{+}}[G]-\Ep[G]=%\U{\Ptil{+}}P\Fp=
  %   \Up \eta\Fp\, , \quad \E_{\Ptil{-}}[G]-\Ep[G]=%-\U{\Ptil{-}}P{-\Fp}=
  %   -\Um \eta\Fp\, .
  % \end{equation}
We also have the  ``confidence band" around the baseline model $P$,

  \begin{equation}
    \label{eq:thm:tightness:main}
    \begin{aligned}
  % -\U{\Ptil{-}}P{-\Fp}
    -\Um \eta\Fp +\E_{P}[g]
    \le
    &\E_{Q}[g] \le \E_{P}[g]+
    \Up \eta\Fp
    % \U{\Ptil{+}}P\Fp
    % \E_{Q^+}[f]-\E_{P}[f]=
    \, &\mbox{for all $Q \in \mathcal{Q}_\eta$,  $g \in \Fp$\, ,}   
    \end{aligned}
  \end{equation}
  with the two equalities holding if $Q=P^{c_\mp}$ respectively and for $g=f \in  \Fp$.
\end{theorem}
  

  % $Z=g(X)\in \Fp $ and
  
  % \tdi{
  % Assume that $\Phi(c)=M_{\bar P}(c; \tilde g)$ some $\bar P$ and some QoI
  % $g$, where $\tilde g=g-\mathbb{E}_Pg$.
  % Define $T$ as a {\it push-forward map} between $P$ and $\bar P$, namely a
  % map $T$ such that $\bar P(A)= P(T^{-1}(A))$ for any measurable set $A$. Then
  % for any QoI $f$ we have:
%   $$
%   \int f(Tx)P(dx)=\int f(y)\bar P(dy)\,.
%   $$
%   Using this property of the push-forward map $T$ we have:
%   $$
%   \Phi(c)= M_{\bar P}(c; \tilde g)=\int e^{\tilde g(y)}\bar P(dy)= \int
%   e^{\tilde g(Tx)} P(dx)= M_{P}(c; \tilde g \circ T)\, .
%   $$
%   Here we also note that
%   $$E_P\tilde g \circ T=\int \tilde g(Tx) P(dx)= \int \tilde g(y)\bar P(dy)=0\, . $$
%   Furthermore we have that $\tilde g \circ T \in \cal{F}_P$ since $M_{P}(c;
%   \tilde g \circ T)=\Phi(c)$. 

\begin{proof} Since $f\in \Fp$, Theorem \ref{thm:tightness} implies that the probabilities 
 $\Ptil{\pm}$ in \eqref{eq:parametric}, with 
$c_\pm$ chosen such that  
$\R
  {\Ptil{\pm}}P=\eta^2$ satisfy
  \begin{align}
    \label{eq:U-equals-GO}
    \go {P^{c_\pm}} P {\pm f} = \Upm \eta\Fp \,.
  \end{align}
%since $\Upm \eta\Fp=\inf_{c>0}\left \{\frac{1}{c}\log\Phi(\pm c)+\frac{1}{c}
 %   \eta^2 \right\}= \inf_{c>0}\left \{\frac{1}{c}\log M_{P}(\pm c; \tilde f)
 %   +\frac{1}{c} \eta^2 \right\}=\Xi(P^{c_\pm}||P; \pm G)$. 
 Therefore, by 
 Theorem~\ref{thm:generalized-go-bounds}, \eqref{eq:U-bounds-bias}, for all $Q \in \mathcal{Q}_\eta, g \in \Fp$
  \begin{equation}
    \label{eq:U-bounds-bias-tight}
    -\Xi(P^{c_-}||P; -f) \leq \Eq[g]-\Ep[g] \leq \Xi(P^{c_+}||P; f)\, .  
  \end{equation}
  Finally, we apply \eqref{eq:max} and \eqref{eq:min} of
  Theorem~\ref{thm:tightness} and 
  use~\eqref{eq:U-equals-GO} to
  conclude the proof.
\end{proof}

 \begin{figure}[!t]
    \centering \includegraphics[width=0.5\textwidth]{figures/tightness_U}
    \caption{ The schematic depiction of Theorem~\ref{thm:sharpness-of-U} for a family of
     QoIs  $\Fp$ and tolerance $\eta^2$. The solid lines depict the one-parameter
      tilted probability distributions $P^c$ corresponding to the QoI $g_1, g_2, f
      \in \mathcal{F}_P$. The theorem implies that the upper and lower bounds in
      the family $\mathcal{Q}_\eta=\{Q: R(Q\|P) \le \eta^2\}$ are attained at
      the probability measures $Q^{\pm}=P^{c_{\pm}}$. }
    \label{fig:tightness}
  \end{figure}



\begin{remark}[Connections to Mass Transport]
{\rm
\label{rem:mass:transport}
The proof of Theorem \ref{thm:sharpness-of-U} is quite straightforward and we discuss here one approach to verify the crucial assumption of the Theorem, namely that 
\begin{equation}
 \label{eq:tightness:real:assumption}
 \Phi(c)=M_{P}(c; \tilde f)\, \quad \mbox{for some QoI $f$\, .}
 \end{equation}
One natural way to ensure this is intimately 
related to mass transport methods, \cite{villani2008optimal}. Instead of 
\eqref{eq:tightness:real:assumption} we may assume the more easily checkable hypothesis
  that $\Phi(c)=M_{\bar P}(c; \tilde h)$ 
for some $h$ and some model $\bar P$;  e.g. $h(x)=x$ and $\bar{P}$ a 
Gaussian distribution for the Hoeffding's bound, see also  Example~\ref{ex:sub-g-tight}
 below. 
To prove \eqref{eq:tightness:real:assumption} one  shows then that there exists  a {\it  transport map} between $P$ and $\bar P$, namely a map $T$ such that $\bar P(A)= P(T^{-1}(A))$ for any measurable set $A$ \cite{villani2008optimal}. If a transport map exists we have 
 $$
  \mathbb{E}_P[h \circ T]=\int h(Tx)P(dx)=\int h(y)\bar P(dy)=\mathbb{E}_{\bar
    P}[h]\,.
  $$
and hence with $f=h\circ T$ 
 $$
  \tilde f=f-\mathbb{E}_P[f]=h\circ T-\mathbb{E}_{\bar P}[h]=\tilde
  h \circ T\, .
  $$ 
This implies that 
\begin{align*}
\Phi(c)= M_{\bar P}(c; \tilde h)=\int e^{c{\tilde h}(y)}\bar P(dy) = \int
  e^{c{\tilde h} (Tx)} P(dx)= M_{P}(c; \tilde{f})\, ,
\end{align*}
 and thus the assumption \eqref{eq:tightness:real:assumption} holds. 
 
 
  
  
%  If we define $f=h\circ T$ 
%  we have
%   $$
%   \tilde f(x)=f(x)-\mathbb{E}_P[f]=h\circ T(x)-\mathbb{E}_{\bar P}[h]=\tilde
%   h \circ T(x)\, .
%   $$
%   % $$\mathbb{E}_P\tilde g \circ T=\int \tilde g(Tx) P(dx)= \int \tilde g(y)\bar
%   % P(dy)=0\, . $$
%   Therefore,
%   \begin{equation}
%     \label{eq:representation}
%   \Phi(c)=M_{P}(c; \tilde f)\, ,
% %   \end{equation}
%   which implies that  $f=h\circ T \in \cal{F}_P$. 
  
To ensure the existence of such a transport map $T$ 
one needs some assumptions on $P$ (and $\bar P$).  
For example, if $P$ and $\bar P$ are non-atomic 
measures then a transport map always exists. 
If the measure $P$ has a density then $T$ can be constructed using the Knothe-Rosenblatt rearrangement or Brenier's $L_2$ optimal transport  map; we refer to  Chapter 1~\cite{villani2008optimal,Carlier2010}  for more details on these maps, and several  other such transport maps and relevant conditions for their existence.
}
%see also \cite{Carlier2010}.
\end{remark}

Next we demonstrate how to use Theorem~\ref{thm:sharpness-of-U} by interpreting
$\Phip{c}$ as the MGF of a suitable QoI $f$ with respect to the distribution $P$. % $\bar P$. 
In Example~\ref{ex:bennet-bernoulli}, we illustrate the tightness of the
concentration bounds for the case of bounded random variables supported in $[-1,1]$, while   
the arguments can be trivially generalized to any other
bounded interval.

\begin{example}[Bennett-(a,b) QoIs]
{\rm 
  \label{ex:bennet-bernoulli}
  Consider a distribution $P$ such that there is  an event $A\subset \mathbb{R}$  such that  $P(A)=1/2$; we consider 
the  family of QoIs, $\Fp$, for which~(\ref{eq:bennet-(a,b)}) is true with $a=-1$, $b=1$, $\Ep[g]=0$ for
  all $g\in \Fp$. The corresponding Bennett-(a,b) bound is
  \begin{align*}
    \Phip{c}=\frac{1}{2}e^c+\frac{1}{2}e^{-c} \, . 
  \end{align*}
%The MGF for a Rademacher distribution ($h(x)=x$ and $\bar P(-1) = \bar P(1)= \frac{1}{2})$. 
Then, if 
we choose 
%   \begin{align}
%     \label{eq:bennet-qoi}
   $ f(x):=2\cdot 1_{A}(x)-1$, 
%  \end{align}
  where $1_A$ is the characteristic function of the set $A$, we have $\Phi(c) =
  M_{P}(c; \tilde f)$.
  Therefore 
Theorem~\ref{thm:sharpness-of-U} is immediately applicable. 
 %The function $f$
%belongs to $\Fp$ and  $
}
 \end{example}
The next example  %~\ref{ex:sub-g-tight} 
covers the case of sub-Gaussian QoIs which contains both bounded and
unbounded random variables.
\begin{example}[sub-Gaussian QoIs]{\rm 
  \label{ex:sub-g-tight}
Consider the probability measure  $P$ on $\mathbb{R}$ which has a density. 
For sub-gaussian QoIs \eqref{eq:sub-Gaussianity}
we have the bound $\Phip{c}=\exp(c^2\sib^2/2)$, however, we  can rewrite the bound as 
$$
\Phip{c}=M_{\bar P}(c; \tilde h)
$$
where  $h(x)=x$ and $\bar P=N(0,\sib^2)$ is a normal 
distribution.  Since $P$ has a density, we can use the measurable isomorphism, or any other applicable map discussed in  Remark~\ref{rem:mass:transport}, to construct a transport map $T$ between $P$ and $\bar P$. 
Thus, we can  show the existence of a a QoI $f$ that satisfies the condition \eqref{eq:tightness:real:assumption}
and we can readily
apply 
Theorem~\ref{thm:sharpness-of-U} to show the tightness of the  bounds given by \eqref{eq:sub-G-Upm}. 
%We consider a distribution $P$, $X\sim P$, and $\Fp$ the family of QoIs
%  satisfying Relation~\eqref{eq:sub-Gaussianity}. We can now readily apply
%  Theorem~\ref{thm:sharpness-of-U} where we observe that
%  \eqref{eq:tightness:U:condition} is satisfied since
 % $$\Phip{c}=\exp(c^2\sib^2/2)=M_{\bar P}(c; \tilde g)\, \quad  \text{for} \quad \bar P=N(0,\sib^2) \quad \text{and} \quad g(x)=\tilde g(x)=x\, .$$
 }
\end{example}


























\section{Model Bias for Statistical Estimators}
\label{sec:scalability}

As discussed in Section \ref{sec:outline} a key challenge is 
to  control the risk involved in evaluating statistical estimator
using the baseline model $P$ rather than the true model $Q$. 
In addition it is important to control the bias of QoI
which are not necessarily  expected values, for example the 
bias in the variance, i.e, $\Vp{X}-\Vq{X}$, or other statistics such 
as correlation of skewness, or mean and quantiles, see~\cite{wasserman2004}. 
Generally, given data $\nn X$, we aim to control the bias of statistical 
estimator $\psi=\psi(\nn X)$, for example the sample 
variance~\eqref{eq:sample-var}. 

%RISK--One of the key challenges we are facing in controlling model bias, stems from the fact that we often need to compare performance on QoIs which are statistical estimators $\psi=\psi(x_1,..., x_n)$, for example, the sample variance in Equation~\eqref{eq:sample-var}. 

To obtain useful bounds on the bias of  statistical estimators 
$\psi$, we need to exhibit and control 
the dependence of the inequalities
in Sections~\ref{sec:bounded-obs} and~\ref{sec:unbounded-obs} on the amount of data available, i.e. the dependence on $n$. We 
will exhibit  a large and natural class of statistical estimators 
for which inequalities asymptotically independent on $n$. As 
demonstrated in \cite{ katsoulakisjcp2017} the Concentration/Information inequalities  of Sections \ref{sec:outline} and 
\ref{sec:conc-ineq} are the only known information equalities which 
scale properly with $n$. 



The main tool we shall use is the key result used in the  proof 
of the McDiarmid's inequality, see also the Hoeffding-Azuma bound, \cite{dembo2010large}. We refer to Chapter 2 of  \cite{raginsky2013concentration} or ~\cite{mcdiarmid1989method} for the proof.

\begin{proposition} \label{thm:McDiarmid}
Let $\nn X$ be independent random variables with joint distribution $P^n=P_1\times\cdots\times P_n$. 
Let $\psi(\nn x)$ satisfy the Lipschitz condition
%
%a QoI such that there exists $d_k$, $k=1,\ldots,n$ for which we have 
%
\begin{equation}
\label{eq:mcdiarmid-cond}
\begin{aligned}
    &\sup_{\nn x,x_k'}|\psi(x_1,\ldots,x_k,\ldots, x_n)-\psi(x_1,\ldots,x_k',\ldots, x_n)| 
    &\leq d_k \, .
  \end{aligned}
\end{equation}
for some constants $d_k$, $k=1,\ldots,n$. Then $\psi(\nn X)$ is 
a sub-Gaussian random variable and for all  $c \in \mathbb{R}$ 
we have
\begin{equation}
 \label{eq:mcdiarmid-res}
 \begin{aligned} 
    M_{P^n}(c; \tilde \psi)&=\E_{P^n}\left [\exp\left(c(\psi-\E_{P^n}[\psi])\right)\right]  &\leq \exp \left( \frac{c^2}{8}\sum_{k=1}^{n}d_k^2\right) \, . 
  \end{aligned} 
\end{equation}
\end{proposition}

By combining the bound in (\ref{eq:mcdiarmid-res})
with the definition of $\Upm \eta\Fp$ in 
Theorem~\ref{thm:generalized-go-bounds} for the sub-Gaussian 
case \eqref{eq:sub-Gaussianity} we obtain immediately

\begin{theorem}
\label{thm:McDiarmidConc}
For  $\nn X$ and  $\psi(\nn x)$ 
as in Proposition \ref{thm:McDiarmid} we have 
\begin{equation}
\begin{aligned}
&\left|\E_{P^n}[\psi(\nn X)]  - \E_{Q^n}[\psi(\nn X)]\right|  = & \left( \sum_{k=1}^{n}d_k^2\right )^{1/2} \sqrt{2 \sum_{k=1}^n\R{Q_i}{P_i}}\,.
\end{aligned}
\end{equation}
%
If $\nn X$ are identically distributed with  common distribution $P$ 
and if there exists a constant $C$ such that 
\begin{align*}
d_k\leq \frac{C}{n} \,,\quad k=1, \ldots, n 
\end{align*}
then we have for any $n$
%
\begin{equation}
\label{eq:upm-mcd-prod}
\begin{aligned}  
  &\left|\E_{P^n}[\psi(\nn X)]  - \E_{Q^n}[\psi(\nn X)]\right| 
  \le  &C\sqrt{2 \R{Q}{P}}.
\end{aligned}
\end{equation}
\end{theorem}

Next, we apply  these results towards obtaining model bias bounds for statistical estimators.  

\sepeq{CDF estimator:} If $X$ is a real-valued with cumulative distribution function (CDF) $F_P(x)=P\{X \le x\}$ then given 
i.i.d. data $\nn X$  
\begin{align}
{\hat F}_n(x) = \frac{1}{n}\sum_{k=1}^n I_{\{X_k \le x\}} \,,
\end{align}
where $I_A$ is the indicator function of the set $A$, is an 
estimator for the CDF $F_P=F_P(x)$. It is easily verified that the 
conditions of Theorem \ref{thm:McDiarmidConc} are satisfied with 
$C=1$. Since the bound is uniform in $x$, and ${\hat F}_n(x)$ is an unbiased estimator of $F_P(x)$, we obtain 
\begin{equation}
\label{eq:CDFest}
\begin{aligned}
 &{\sup_{x} \left| F_Q(x)-F_P(x)\right|}
 =&\sup_{x} \left| \E_{Q^n}\left[{\hat F}_n(x)\right]-\E_{P^n}\left[{\hat F}_n(x)\right]\right| 
 \le &\sqrt{2 \R QP} \, ,
\end{aligned}
\end{equation}
for any alternative model $Q$ to the baseline $P$. As we also note in the sample variance example below, the estimator does not need to be unbiased. % in fact we could have used any kernel-based estimator.
% Using \eqref{eq:CDFest}   we can also control 
% the bias of the p-th quantile  $F_Q^{-1}(p):=\inf \{x: F_Q(x) \ge p\}$ for any distribution $Q$,  with respect to the p-th quantile of the  baseline model $P$.

%\begin{remark}(Confidence Intervals and Model Bias)
%If we combine the bound \eqref{eq:CDFest} with the Dvoretzky-Kiefer-Wolfowitz (DKW)  Inequality \cite{wasserman2004,wasserman2010} we can readily obtain rigorous   non-parametric confidence bounds for the CDF when  we  use data from the baseline model $P$  for the purpose of estimation rather than data from  the ``true" model $Q$.  Due to the fact that the DKW inequality is valid for any data size $n$, these confidence intervals do not require any asymptotic normality assumptions and/or $n \gg 1$.
%\end{remark}


\sepeq{Sample variance and general statistical estimators:} The McDiarmid's inequality and the
condition \eqref{eq:mcdiarmid-cond} can be used to control bias 
of QoIs which are not simply expected values, for example the sample
variance 
\begin{equation}
\begin{aligned}
 V_n(\nn{X})&=\frac{1}{n-1}\sum_{i=1}^{n}\left(X_i-\frac{1}{n}\sum_{j=1}^n X_j\right)^2
 &=\frac{1}{2n(n-1)}\sum_{i,j=1}^{n}(X_i-X_j)^2.
\end{aligned}
 \label{eq:sample-var}
\end{equation}
%The quantity $\bar{x}$ denotes the sample mean of the $x_i$'s.
If we assume that $|X_i|\le M$ for some $M>0$ then we have 
\begin{align*}
  % \label{eq:McDiarmid-variance}
 \sup_{\substack{|x_i|\le M, \\ |x_k'|\le M}} |V_n(x_1,\ldots,x_k,\ldots,x_n)-V_n(x_1,\ldots,x_k',\ldots,x_n)|
 \leq  \frac{8M^2}{n-1} \,. 
 \end{align*}
Then the sample variance satisfies \eqref{eq:mcdiarmid-cond} with $d_k=8M^2/(n-1)$ for all $k$. Thus, we can bound the corresponding model bias by
%
\begin{equation}
  \label{eq:model-bias-sample-variance}
  \begin{aligned}
    |\Vp[X]-\Vq[X]|&=|\E_{P^n}[V_n]-\E_{Q^n}[V_n]| 
    &\leq 8M^2 \frac{n}{n-1}\sqrt{2\R{Q}{P}}.
  \end{aligned}
\end{equation}
valid for all $n>1$. Note that if take $n \to \infty$ we obtain 
the variance bound 
\begin{align*}
 |\Vp[X]-\Vq[X]|\leq 8M^2 \sqrt{2 \R QP}
\end{align*}
which shows how KL-divergence $\R{Q}{P}$ control the misspecification 
for QoIs beyond expected values.  The same analysis also applies to the (biased) plug-in estimator for the variance, namely
$$
\tilde V_n(\nn{X}):=\mbox{var}_{{\hat F}_n}[X]=\frac{1}{n}\sum_{i=1}^{n}\left(X_i-\frac{1}{n}\sum_{j=1}^n X_j\right)^2\, .
$$


Finally, we can easily generalize the sample variance calculation to more 
general QoIs and statistical estimators. The sample variance depends (up to a factor $\frac{n-1}{n}$) only on the two sample averages  $\frac{1}{n}\sum_{i=1}^n X_i$ and $\frac{1}{n}\sum_{i=1}^n X_i^2$. It is not difficult to 
see that if $|X_i|\le M$ and the QoI has the form 
\begin{equation}
\label{eq:plugin:general}
\begin{aligned}
\psi_n(\nn X) = g\left(\frac{1}{n}\sum_{i=1}^n f_1(X_i), \ldots,   \frac{1}{n}\sum_{i=1}^n f_k(X_i) \right)
\end{aligned}
\end{equation}
for some $f_1, \cdots f_k$ (say the the first $k$ moments),   
and for some Lipschitz continuous function $g$, then one can apply Theorem \ref{thm:McDiarmidConc} for a constant $C$ which depends on $M$, the Lipschitz constant for $g$ and $f_1, \cdots f_k$.  One important example 
of the type \eqref{eq:plugin:general} is the sample correlation, we refer to Example 2.16 in \cite{wasserman2010}.


\sepeq{Confidence Bands and 
Model Bias}
To further  illustrate our results we construct 
a non-parametric confidence band for the CDF
$F_Q(x)$.  We combine the bound 
\eqref{eq:CDFest} with the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality \cite{wasserman2004,wasserman2010}, 
i.e.  the  bound  
\begin{equation}
\label{eq:DKW:ineq}
P \left\{ \sup_{x}|{\hat F}_n(x) - F_P(x)|\ge \epsilon\right\} \le 2 e^{-2 n \epsilon^2} \, , 
\end{equation}
which itself is obtained though concentration inequalities.
For any $n$ and $\alpha > 0$, we set $\epsilon_n= \sqrt{\log(2/\alpha)/2n}$
and 
\begin{equation}
\begin{aligned}
L_n(x; \eta) = \max\{ {\hat F}_n(x) - \sqrt{2}\eta - \epsilon_n \,,\, 0\}\, \\ 
U_n(x; \eta) = \min\{ {\hat F}_n(x) + \sqrt{2}\eta + \epsilon_n \,,\, 1\} \, .
\end{aligned}
\end{equation}
%where $Q \in \mathcal{Q}_\eta$.
Since ${\hat F}_n(x)$ is an unbiased estimator for the baseline model $P$ 
rather than for the (unknown) ``true" model $Q$
we obtain the $\alpha$--confidence band for $F_Q(x)$:
\begin{equation}
\label{eq:confidence:bias}
\begin{aligned}
P \left\{ L_n(x;\eta) \le F_Q(x) \le U_n(x;\eta) \textrm{ for all } x \right\}  \ge   1- \alpha \,,\quad \mbox{for all} \quad Q \in \mathcal{Q}_\eta\, .
\end{aligned}
\end{equation}
Due to the fact that both our bound \eqref{eq:CDFest} and the DKW 
inequality \eqref{eq:DKW:ineq} are valid for any data size $n$, the confidence band \eqref{eq:confidence:bias} does not require any asymptotic normality assumptions or a large data set  $n \gg 1$.

\sepeq{Connections to the Vapnik-Chervonenkis inequality}
The DKW inequality is an effective  tool for controlling deviations from the average  for one dimensional distributions  and their corresponding CDFs. However, the Vapnik-Chervonenkis (VC)
theory~\cite{wasserman2010} allows us to address the same issues in a more general setting  that is applicable to higher-dimensional distributions,  by considering the empirical probability distribution instead of the CDF. In particular,  corresponding inequalities to    \eqref{eq:DKW:ineq}, but for the empirical probability distribution, can be derived based on the  VC theory, see for instance Theorem 2.41 and Theorem 2.43 in~\cite{wasserman2010}. In turn the VC inequalities, along with our concentration information bounds \eqref{eq:upm-mcd-prod}  can allow us to obtain 
confidence intervals for  higher dimensional  distributions, similarly to   \eqref{eq:confidence:bias}.


\begin{remark}
\label{rem:poor:scalab}
[Poor scalability of certain information inequalities]
{\rm
A notable feature of the concentration/information inequalities is that they scale independently of  the number of data/random variables $n$, at least for classes of QoIs that satisfy \eqref{eq:mcdiarmid-cond}, as   demonstrated  in Theorem~\ref{thm:McDiarmidConc} and the subsequent examples. Furthermore, the bias bound \eqref{eq:upm-mcd-prod} remains  discriminating even if  $n \to \infty$.
%in the sense that if distributions  $P$ and $Q$ are the same the bound is zero. 
The same scaling features are also shared with the GO divergence bounds \eqref{eq:intro:bias-bound-go:sec2}, see \cite{katsoulakisjcp2017}. 
%
On the other hand, classical information inequalities scale poorly with $n$. For example, in the case of the Pinsker inequality \cite{Cover2006ElementsofInformationTheory,tsybakov},  let us consider  the QoI (estimator)  \eqref{eq:plugin:general} for the i.i.d. random variables $\nn X$,  
$$
\psi_n(\nn X) = \frac{1}{n}\sum_{i=1}^n f(X_i)\, .
$$
Then, the Pinsker inequality becomes
\begin{equation}
\label{eq:Pinsker}
\begin{aligned}
& \left|\E_{P^n}[\psi(\nn X)]  - \E_{Q^n}[\psi(\nn X)]\right|  
 \le  & \| f \|_{\infty}\sqrt{2  R(Q^n \mid \mid P^n)}=O(\sqrt{n})\, ,  
\end{aligned}
\end{equation}
where we used that
$\| \psi \|_{\infty}=\| f \|_{\infty}$, and  
$
R(Q^n \mid \mid P^n)= n R(Q \mid \mid P)
$.
Therefore the Pinsker bound \eqref{eq:Pinsker} blows up
as $n>>1$, in contrast to the concentration/information inequality \eqref{eq:upm-mcd-prod} that remains discriminating and informative for any $n$.  
%
Other  model bias bounds  based on the  Renyi or  $\chi^2$ divergences (the latter known as the Chapman-Robbins inequality) or the Hellinger metric,   also scale poorly with   the size of data set   and/or with the number of variables $n$; we refer to  Sections~2.2--2.3 in \cite{katsoulakisjcp2017} for a complete discussion.
}
\end{remark}

\section{Elementary examples}
\label{ex:simple-examples}
Prior to discussing  applications involving more complex models in Section~\ref{sec:epistemic-UQ-conc}, here we demonstrate  the concentration/information inequalities we developed earlier to two  elementary  examples that allow easy analytic and computational implementations. 


\subsection{Exponential distribution}
\label{ex:expo-dist}
We first consider the model bias  bounds using the GO divergence in  Theorem~\ref{thm:GO-bounds}, contrasted to the concentration/information divergence in Theorem~\ref{thm:generalized-go-bounds}.
In our first example,  the baseline model $P$ is  an exponential distribution. The
models $Q$ can be any distributions which are  absolutely continuous with respect
to $P$, hence $\R QP < \infty$.
Let $P$ be an exponential distribution with parameter
$\lambda_P=1$. The QoI is $f(X)=X$. The MGF of $P$ is $\Mp{c;X}=1/(1-c)$ and
thus it is finite in $(0,1)$, while otherwise it is infinite. Next, we let  $\eta$  be a model  uncertainty threshold and $Q$ any
distribution, not necessarily exponential or in any parametric family,  such that $\R QP\leq \eta^2$. 
% Then,
% \begin{align}
%   \label{eq:constrained-go}
%   \gopm QPf \leq \inf_{c\in (0,1)}\left\{ \frac{\Cp{\pm c;\ti f}}{c}+\frac{\R QP}{c} \right\},
% \end{align}
% \tdi{formula not needed}
%
We note that the distribution $P$ exhibits sub-exponential behavior, namely 
\begin{align}
  \label{eq:sub-expo}
  \begin{aligned}
  \Mp{c;f}=1+c+\frac{c^2}{1-c}  
  \leq 1+c+2c^2  
  \leq \exp(c+c^2/(2\sib^2)) :=\Phip{c}\, , \quad c \in (-0.5,0.5)\, ,
  \end{aligned}
\end{align}
where $\sib=1/2$ and the interval $(-0.5,0.5)$ is selected so that the bounds remain finite.  In general,  if we different  information on the location of
$\lambda_P$, \eg from data, then we can adjust the interval that $c$ lies in
accordingly. Here, the  concentration/information bound \eqref{eq:U-divpm} is then adjusted according to \eqref{eq:sub-expo},  using Theorem~\ref{thm:generalized-go-bounds} and 
the general concentration bound
\eqref{eq:conc:mgf-bound:thm}.
Although the MGF is known in this particular example, the use of the
concentration bound \eqref{eq:sub-expo} allows us to quantify the worst-case model bias for all QoIs
$g \in \Fp$, where
\begin{equation}
\label{eq:Fp-expo}
\begin{aligned}
  \Fp=\{g: \Mp{c;\ti g}\leq \Phi(c), \
  %e^{c^2 \sib^2} 
%  \text{ for all } 
  c\in (-0.5,0.5),\ \sib^2\le 1/4\}.
\end{aligned}
\end{equation}
Figure~\ref{fig:expo-dist} is a comparison of the GO-divergence and the concentration/information bound based on 
\eqref{eq:sub-expo},
 along with the
exact model bias for the case that $Q$ is also an exponential distribution with $\R
QP\leq \eta^2$ and $\eta\in [0,1.6]$.
\begin{figure}[!t]
  \centering
  \includegraphics[width=0.499\textwidth]{figures/comparison}
  \caption{\label{fig:expo-dist} Comparison of model bias bounds
  based on   the GO divergence and the concentration/information 
\eqref{eq:sub-expo},
   with the exact model bias
    $1-\lambda_Q$, $\lambda_Q\in (1.01,10)$. The sub-exponential bound~(\ref{eq:sub-expo}) is less
    sharp as the KL divergence  increases, since  it  captures the worst-case
    performance over the family of QoIs $\Fp$. Although $\R QP$ is computed with
    $Q$ being an exponential distribution, the bounds to the  model bias are valid for
    any $Q$ that is absolutely continuous with respect to $P$ and has $\R QP$ in
    the range of the figure. }
  \label{fig:expo-comparison}
\end{figure}


Finally, we can consider other types of tail decay, and thus corresponding concentration inequalities,  besides the sub-Gaussian and the sub-exponential cases discussed thus far. 
For example, we can also consider   Poisson-type tail decay, see for instance  
\cite[Section 3.3.5]{raginsky2013concentration} 
and~\cite{boucheron2009concentration}.


\begin{remark}
{\rm
  The bias is an unbounded function of the KL divergence in this example---a
  consequence of the QoI $f(X)=X$ being unbounded under $P$. Therefore, any
  decrease in KL divergence translates to an improvement in worst-case model bias,
  see Figure~\ref{fig:expo-dist}; this fact is in
  sharp contrast with the truncated Normal example in 
  Section~\ref{ex:truncated-normal}, where even large   improvements to larger values of
  the KL divergence may not help much in reducing model bias, see Figure~\ref{ex:truncated-normal}.
}
\end{remark}










\subsection{Truncated Normal}
\label{ex:truncated-normal}

In this example the distributions we consider are bounded, allowing us to deploy the hierarchy of concentration/information bounds \eqref{eq:ordering}
developed in Section~\ref{sec:bounded-obs}.
%
We assume the random variable $X$ follows the truncated Normal distribution, $P=TN(0,1, -1, 1)$,
where $[-1,1]$ is the interval of support.  Here we will bound the model bias, $\bias$, for any $Q$
such that $\R QP=\eta^2$, where $\eta\in [0.01,1]$ and for any $f$ in a suitable family
of QoIs, $\Fp$. Apart from these, the bounds make no other assumptions on $Q$, $f$.
Figure~\ref{fig:compare-trunc-normal-bounds} contains a comparison of the
different concentration/information bounds \eqref{eq:ordering} from Section~\ref{sec:bounded-obs}. 
\begin{figure}[!t]
  \centering
  \includegraphics[width=0.5\textwidth]{figures/TN-approx-TN-linear}
  \caption{Comparison of the different bounds for the bias in the truncated
    Normal example (see Section~\ref{ex:truncated-normal}), assuming that the
    observable of interest is $f(X)=X$. This plot makes no assumptions on the
    form of $Q$ except that $\R QP=\eta^2\in (0.0,4.0)$.
    As in Figure~\ref{fig:expo-comparison}, here  the concentration/information bounds capture the worst-case
    performance over the family of QoIs $\Fp$, hence perform worse than the GO divergence bounds which are suitable only for a single QoI, see also \eqref{eq:ordering}.
    Notice that Bennett and
    Bennett-$(a,b)$  track  better the bound of the GO divergence for large
    values of the KL whereas the Hoeffding is  sufficient  only for small values of
    the KL, \ie at the linearized regime of the GO bounds. Only the upper bounds
    for the bias are shown here.}
  \label{fig:compare-trunc-normal-bounds}
\end{figure}




As a general observation, we notice that for large values $\eta=\sqrt{\R QP}$, small perturbations of
$\eta$ will not change the Bennett/GO (see Relations~(\ref{eq:intro:godiv:2})
and~(\ref{eq:bennet-mgf-ineq})) bounds significantly. Therefore, for some
QoIs, \eg $f(X)=X$, small improvements to large values of the KL will barely
improve the worst-case bias (as captured by the bounds, see
Figure~\ref{fig:compare-trunc-normal-bounds}). The existence of such QoIs is
guaranteed by the sharpness of the bounds demonstrated in
Section~\ref{sec:sharpness-and-robustness}. Finally, we not that even for the tighter concentration/information 
bounds, \ie the ones associated with the  two Bennett bounds  (\ref{eq:bennet-mgf-ineq}) and 
(\ref{eq:bennet-(a,b)}), there is some discrepancy with the GO divergence bound. This discrepancy is due to the fact that   the GO bound is applied only for a specific QoI, while the
concentration/information  bounds are tight over the broad classes of QoIs defined in  Section~\ref{sec:bounded-obs},
see also Remark~\ref{rem:size:Fp}.
 
%  --------comment out---------
 
%  specifically, the Bennett-(a,b)
% bound is applied   over the family of QoIs
% %
% \begin{align*}
%   \Fp=\{g: -1\leq  g(x)\leq 1 \text{ for all $x$}\}, 
% \end{align*}
% while  for the Bennett bound we have 
% \begin{align*}
%   \Fp=\{g: g(x)\leq 1 \text{ for all } x,\ \Vp[g]\leq 1\}, . 
% \end{align*}

%  --------comment out---------


\section{Epistemic Uncertainty Quantification via Concentration/Information Inequalities}
\label{sec:epistemic-UQ-conc}
In this Section, we apply the concentration/information inequalities to control model bias between baseline and alternative models in two
more complex examples. The  type of model bias considered here arises  in epistemic uncertainty quantification, where modelers are unsure if their baseline model included all necessary complexity or lacks sufficient data, \cite{Smith, Sullivan2015}. The KL divergence and in particular the GO divergence bounds provide a non-parametric framework to mathematically describe this type of epistemic uncertainties, as first shown in \cite{dupuis2011uq}.
Here, we consider two such examples that illustrate different aspects of epistemic uncertainty, namely a data-driven model for the lifetime of lithium batteries, as well as  a high-dimensional Markov Random Field model  subject to various localized uncertainties  such as local defects. 
%
A key aspect of our discussion in both examples 
%is when and why  
%  GO divergence bounds---in spite of their optimality for specific QoIs---become intractable, 
is the necessity and the (ease of) implementation of concentration/information model bias bounds,
see for instance Remark~\ref{battery_remark}.



\subsection{Epistemic Uncertainty for Failure Probabilities}
\label{ex:battery-example}


Here, we apply the   bounds of Theorem~\ref{thm:generalized-go-bounds}, and in particular
the inequalities in Section~\ref{sec:bounded-obs}, to the life-time  analysis of lithium secondary
batteries. Firstly, we introduce the Weibull distribution which is widely used
in for analyzing life-time data, see \cite{eom2007life} and references therein. The  probability density function of a Weibull random
variable is
\begin{equation}
  f(t)=\frac{\beta}{\xi}\left (\frac{t}{\xi}\right)^{\beta-1}e^{-(\frac{t}{\xi})^\beta}, t>0,
\end{equation}
where $\beta > 0$ is called a shape parameter and $\xi > 0$ is a scale parameter of the
distribution \cite{weibulldef}. The shape parameter explains the types of failure and the scale
parameter explains the characteristic life cycle of devices. The cumulative
distribution function $F$ can be expressed as:
$$F(T)=1-e^{-(\frac{T}{\xi})^\beta}\, ,$$
where $T$ denotes the time of failure (or the lifetime) of the battery.
\begin{table*}[!t]
  \caption{Failure times of test samples\cite{eom2007life} }
  \centering
  \begin{tabular}{c c c c c c c c c c c c c}
    \hline\hline                   %inserts double horizontal lines
    Specimen number& 01 & 02 & 03 & 04 & 05 & 06 & 07 & 08 & 
                                                             09 & 10 & 11 & 12 \\[0.5ex]  \hline      
    Failure time & 1373  & 1470  & 1520  & 1427  & 892  & 814  & 777  & 637 & 927  & 688  & 857  & 866 \\ [1ex] 
    \hline
    \hline
    
  \end{tabular}
  \label{Table: Battery_data}
\end{table*}
% \medskip
% \noindent

In Table~\ref{Table:
  Battery_data}, experimental data based on life cycle  tests are obtained from
\cite{eom2007life}. By fitting the data in Table~\ref{Table: Battery_data} to
the parameters of the Weibull distribution, we obtain the corresponding maximum
likelihood estimator (MLE) for
$\xi$ and $\beta$ are $\hat{\xi}=1138$ and $\hat{\beta}=3.55$, respectively.
Now, we consider this MLE Weibull distribution as the baseline model
$P$, which is a data-driven  approximation to the unknown true model.
%
Next we consider the family of alternative models within a fixed
tolerance $\eta^2$, namely the non-parametric family of models  $\efam$, see \eqref{Qfamily}. This family  accounts for unknown features not necessarily captured in
the baseline model which  was  arbitrarily assumed
to be Weibull.   Furthermore, the family $\efam$ can account for perturbations in the
baseline model---constructed based on the specific dataset in Table~\ref{Table: Battery_data}---due to additional data that may become available or for any errors in the  data used in the MLE step.

Next, we assess the impact of model uncertainty within the family of models $\efam$ on two QoIs associated with lifetime probabilities of the batteries:
%
\begin{align}
  f_1(t)&=1_{\{0\leq t\leq T\}}(t),t>0,\label{eq:ind-fun}\\
  % f_2(t;w)&=\frac{1}{1+e^{-wt}}-\frac{1}{1+e^{w(T-t)}}\label{eq:approx-ind-fun}.
              f_2(t;w)&=\frac{1}{1+e^{w(t-T)}}, t>0 \label{eq:approx-ind-fun}.
\end{align}
The function $f_2(t;w)$ is a commonly used smooth approximation to the indicator
function $f_1(t)$ and is usually referred as  the logistic function, see Section~39.1 of
\cite{MacKay:2003}). The parameter $w$, $w\geq 1$, controls the smoothness of
the approximation.
The QoI  for  the life-time probability is defined exactly as $F_P[T]:=E_P[f_1(t)]=P(0\le t \le
T)$ or through the smooth approximation $\Ep[f_2]$. 

% ----------
% By
% applying the  in Theorem~\ref{thm:GO-bounds} on the QoI $F_P[T]:=E_P[f_1(t)]$ we calculate  an uncertainty region
% for the failure probability over the family $\efam$:
% \begin{equation}
%   \label{eq:uq-bounds-fp}
%   -\inf_{c>0}\{\Phip{-c}/c+\eta^2/c\}+F_P(T)\le \inf_{Q\in \mathcal{Q}_\eta}F_Q(T)\le \sup_{Q\in \mathcal{Q}_\eta}F_Q(T) \le \inf_{c>0}\{\Phip{c}/c+\eta^2/c\}+F_P(T).
% \end{equation}
% We can reason similarly for an uncertainty region for $f_2$. % However, even
% % though $\Ep[f_1]$ can be computed explicitly with respect to the baseline
% % model $P$, the same cannot be said for $f_2$. Therefore, we will have to
% % estimate $\Ep[f_2]$ by sampling from $P$. , which will introduce uncertainty
% % to the bounds. To capture this uncertainty, we will use a $99\%$ confidence
% % interval for the estimate of $\Ep[f_2]$.
% --------------

Since the QoI $f_1(t)$ is bounded in  $[0,1 ]$, we can  apply the
Bennett~\eqref{eq:bennet-mgf-ineq}, Bennett-(a,b)~\eqref{eq:bennet-(a,b)} and Hoeffding bounds~\eqref{eq:Hoeffding}) to obtain the uncertainty region, where $a=0$,
$b=1$, $\tilde{a_1}=-F_P(T)$, $\tilde{b_2}= 1-F_P(T)$ and
$\sigma_B^2=Var_P[f_1(t)]$, the latter needed just in the Bennet bound. For $f_2$, we estimate $\Ep[f_2]$ by sampling from
$P$, thus computing  $\mu_2=\Ep[f_2]$, needed in both Bennett bounds. Then, $\ti a_2=-\mu_2$ and $\ti
b_2=1-\mu_2$. In Figure \ref{Fig:Battery} we  compare the lifetime
probabilities given by $f_1$ and $f_2$, where for the latter we set $w=5$. 
In this Figure, we also observe that  the logistic function $f_2$
gives a good approximation of the indicator function $f_1$ since lifetime
probabilities based on them are almost the same. Moreover, we set $\eta^2=0.1$
and also plot the GO divergence bounds of  Theorem~\ref{thm:GO-bounds} based on $f_1$ and Bennett-(a,b) bounds based on $f_2$. We
notice that the bounds almost coincide. We also consider the Bennett-(a,b) bounds
based on a smaller tolerance $\eta^2=0.01$. As we see in the figure, we obtain a significantly 
narrower model bias region.
\begin{figure}
  \centering
  \includegraphics[width=0.5\textwidth]{figures/Battery.pdf}
  \caption{ The blue line is the failure probability based on the logistic function
    $f_2$; The red line is the failure probability based on the indicator function $f_1$; The black
    lines are the GO bounds based on $f_1$ with $\eta^2=0.1$; The green lines
    are the Bennett-(a,b) bounds based on $f_2$ with model uncertainty $\eta^2=0.1$.
    The magenta lines
    are the Bennett-(a,b) bounds based on $f_2$ with $\eta^2=0.01$.}
  \label{Fig:Battery}
\end{figure}

\begin{remark}[Why concentration/information inequalities?]
  \label{battery_remark}
  {\rm 
  % Even though we can compute $\Ep[f_1]$ explicitly, this is not the case for a
  % general QoI. For example, bounding $\Eq[f_2]$ requires estimating
  % $\Ep[f_2]$.
  % In terms of estimator variance, this is a simpler than MGF estimation.
  As shown in Lemma~2.11, Equation~(2.28) of \cite{katsoulakisuq16}, the $c^*$
  that solves the optimization problem of the GO divergence bound in
  Equation~(\ref{eq:intro:godiv:2}) behaves like
  \begin{align}
    \label{eq:cstar}
    c^*=c_1\eta + O(\eta^2), 
  \end{align}
  for some explicit constant $c_1$ and $\eta^2=\R QP$. Due to~\eqref{eq:cstar} and since estimator variance for the MGF increases
  exponentially with $c$, a larger
  uncertainty threshold $\eta$ will quickly make the accurate estimation of $\Mp{c^*;f}$
  more demanding, as is readily clear from Table~\ref{tab:estimator-cost}
  and \eqref{eq:cstar}. This drawback becomes  especially problematic  when sampling from $P$ is
  computationally expensive, \eg requires MCMC sampling, $P$ is multi-modal,
  \etc, see also the Markov Random Field example in Section~\ref{sec:loc-pert-stat-mod}, where
  sampling challenges can become more pronounced in higher dimensions. Even when $P$ is simple to sample,
  as is the case with the baseline models in \cite{li2012computation} and
  here, %Section~\ref{ex:battery-example}, 
  avoiding the estimation of
  $\Mp{c^*;f}$ in the GO divergence can still save significant computational time, as Table~\ref{tab:estimator-cost} strongly suggests.  For instance, the Bennett-(a,b)
  bound in~(\ref{eq:bennet-(a,b)}) only requires
  \begin{enumerate*}
  \item[(a)]  the bounds of the QoI, $a,b$, and 
  \item[(b)]  the expected value of the QoI with respect to $P$.
  \end{enumerate*}
  }
\end{remark}


\subsection{Uncertainty Quantification for Markov Random Fields}
\label{sec:loc-pert-stat-mod}
%An important special case of applicability of our bounds arises when we consider
Here we consider the impact on QoIs of localized perturbations to statistical probability distributions of Markov
Random Fields \cite{MacKay:2003} such as Gibbs measures. Such distributions are inherently high-dimensional, allowing us to focus on this aspect of model bias bounds.
In particular,  we consider Gibbs
measures for particle systems defined on  a fixed finite subset $\Lambda_N$ of the infinite dimensional lattice $\mathbb{Z}^d$. Specifically we consider  $\Lambda_N=\{x\in \mathbb{Z}^d,
|x_i|\le n\}$  the square lattice with $N=(2n+1)^d$ lattice sites, where typically $n\gg 1$. 
%
Before we describe the model, we will specify some necessary notation: we let $S$ be the
configuration space of a single particle at a lattice  site $x \in \mathbb{Z}^d$. For example in a lattice gas model $S=\{0, 1\}$, i.e. the lattice site can be empty or occupied,  and in a Potts model $S=\{0, 1,..., q\}$, i.e. the site is empty or occupied by particles of $q$ different species. In Ising magnetization models studied below, we have that  $S=\{-1, 1\}$, corresponding to down or up spins respectively. 
Then $S^X$ is the configuration space for the particles in any subset  $X \subset
\mathbb{Z}^d$; we denote by $\sigma_X \,=\, \{ \sigma_x\}_{x\in X}$ an element
of $S^X$.
                     %
% We will be interested in large systems so we let $\Lambda_N=\{x\in \mathbb{Z}^d,
% |x_i|\le n\}$ denote the square lattice with $N=(2n+1)^d$ lattice sites. 
Next, in order to
define a Gibbs measure on $\Lambda_N$, we first specify the Hamiltonian $H_N(\sigma_{\Lambda_N})$ of a set
of particles in the region $\Lambda_N$. An interaction $\Phi= \{\Phi_X: X \subset \mathbb{Z}^d, X\;\; 
\textrm{finite}\}$  associates to any finite subset $X$ a function
$\Phi_X(\sigma_X)$ which depends only on the particle configuration in $X$ and accounts for all particle interactions within $X$, see
\cite{simon2014statistical} for details. Given an interaction $\Phi$ we then
define the Hamiltonian $H^\Phi_N$ (with free boundary conditions) by
\begin{equation}\label{Hamiltonian:Sec5}
  H_N^\Phi(\sigma_{\Lambda_N})=\sum_{X \subset \Lambda_N}\Phi_X(\sigma_X),
\end{equation}
and Gibbs measure $\mu_N^\Phi$ by
\begin{equation}
\label{eq:Gibbs_exp}
  d\mu_N^\Phi(\sigma_{\Lambda_N}) = \frac{1}{Z_N^\Phi} e^{ - H_N(\sigma_{\Lambda_N})} dP_N(\sigma_{\Lambda_N}) ,
\end{equation}
where $P_N$ is the counting measure on $S^{\Lambda_N}$ and $Z_N^\Phi= \sum_{
  \sigma_{\Lambda_N}} e^{ - H_N(\sigma_{\Lambda_N})}$ is the normalization
constant, also known as the partition function, \cite{simon2014statistical}.

Here we consider classes of perturbed  models with corresponding  interaction $\Psi$ that includes only local perturbations to the interaction
$\Phi$, e.g. \textit{local defects} encoded in the interaction potential $J$, or localized perturbations to the external field $h$ in the example of the 
Ising-type Hamiltonian \eqref{eq:Ising:Hamilt}. We also note that defects of finite temperature 
multi-scale probability distributions
are a continuous source of interest in the
computational materials science community, see, for instance, \cite{Ortiz}; in fact,  
lattice probability distributions such as \eqref{eq:Gibbs_exp}, constitute an important class of
simplified prototype problems. In the case of localized perturbations to the
interaction $\Phi$ in~\eqref{Hamiltonian:Sec5}, the Hamiltonians scale
as follows:
$$
H_N^\Psi(\sigma_{\Lambda_N})=H_N^\Phi(\sigma_{\Lambda_N})+O(1)\, .
$$
Thus the corresponding relative entropy satisfies
\begin{equation}
\begin{aligned}
 R(\mu^\Psi_N\mid\mid \mu^\Phi_N)&=\log E_{\mu_N^\Psi}(e^{\Delta H})+E_{\mu_N^\Psi}( -\Delta H)\\&=O(1)\, ,
  \label{eq:Isng_KL}
\end{aligned}
\end{equation}
uniformly in the system size $N$, where we define $\Delta H=H_N^\Psi - H_N^\Phi$. However,
in most cases, we do not know the exact local perturbation as well as the perturbed Gibbs
measure $\mu_\Psi$. Instead,  based on\eqref{eq:Isng_KL} we can consider a family of perturbed models:
$$\efam=\{\mu_\Psi: R(\mu_\Psi\|\mu_\Phi)\le \eta^2 \}\, .$$
This family   will include  any
perturbation \textit{within that tolerance} $\eta^2$, for example: defects
located at different lattice sites, and of different magnitudes, as the scaling \eqref{eq:Isng_KL} demonstrates rigorously.
\begin{figure}[b]
\centering
\subfloat[]{\includegraphics[width=0.5\textwidth]{figures/Ising_KL1.pdf}%
\label{Fig:Ising_KL1}}
\hfil
\subfloat[]{\includegraphics[width=0.5\textwidth]{figures/Ising_KL2.pdf}%
\label{Fig:Ising_KL2}}
\caption{\protect\subref{Fig:Ising_KL1}  The red line is the mean of the QoI \eqref{eq:Ising:observable} with $m=1$
for the baseline model \eqref{eq:Ising:Hamilt} with  $J=1$ and
    $\beta=1$.
    The green and blue lines are the Bennett bounds for $\eta^2=0.05$
    and $\eta^2=0.5$, respectively.
    %$\mathcal{F_P}=\{g: -1 \le g(\sigma)\le 1 \}$
\protect\subref{Fig:Ising_KL2} The red line is the mean of the same QoI 
for the baseline model \eqref{eq:Ising:Hamilt} with  $J=1$ and
    $\beta=1$ ; The green and blue lines are the Bennett-(a,b) bounds for $\eta^2=0.05$
    and $\eta^2=0.5$, respectively. In both figures the lattice size is N=100. }
\label{Fig:Ising_KL}
\end{figure}


As a concrete  example of a Hamiltonian\eqref{Hamiltonian:Sec5}, we consider $\mu_\Phi$ to be  a one-dimensional  Ising model probability
distributions on the one-dimensional lattice $\Lambda_N$, labeled
successively by $x=1,2,...,N$. To each site corresponds a spin $\sigma(x)$, with two
possible values: $+1$ or $-1$. The Hamiltonian is given by
\begin{equation}
\label{eq:Ising:Hamilt}
  H^\Phi_{N}(\sigma_{\Lambda_N})=-\beta \sum_{x=1}^{N-1}J(x)\sigma(x)\sigma(x+1)-\beta h\sum_{x=1}^N\sigma(x).
\end{equation}
Using the  concentration/information  inequalities developed in Section~\ref{sec:conc-ineq}, we can obtain model bias  bounds for 
QoIs, such as the localized average around any lattice site $x$,
\begin{equation}
  f(\sigma_{\Lambda_N})=\frac{1}{2m+1}\sum_{\{y: |y-x|\le m\}} \sigma(y)\, ,
  \label{eq:Ising:observable}
\end{equation}
for a fixed radius $m$. In the demonstration below we we pick $m=1$ for concreteness. 
%
Since the QoI $f$ \eqref{eq:Ising:observable} is bounded, $-1 \le f \le 1$, we can use
the Bennett-(a,b) bound~\eqref{eq:bennet-(a,b)}. Alternatively, we can use the   Bennett bound~\eqref{eq:bennet-mgf-ineq}), which however requires estimating in addition to 
$E_{\mu_N^\Phi}[f]$, the variance  $Var_{\mu_N^\Phi}[f]$ by sampling from $\mu_\Phi$, see also Section~\ref{sec:bounded-obs}. The latter is not unreasonable given that variance computations are necessary in many applications because  they ensure suitable confidence intervals for the averaged QoIs. 
%
In Figure \ref{Fig:Ising_KL}, we implement
both Bennett and Bennett-(a,b) bounds by considering two different KL divergence tolerances, $\eta^2=0.5$, $0.05$.
A comparisons between   Figure \ref{Fig:Ising_KL1} and Figure \ref{Fig:Ising_KL2} indicates that Bennett  and Bennett-(a,b) bounds are fairly close for this example.

Notable computational advantages  of these concentration/information inequalities over  direct numerical simulation of  alternative models  $Q=\mu_\Psi$, 
as well as over the  GO divergence bounds  in Theorem~\ref{thm:GO-bounds} are the following: (1) when using Theorem~\ref{thm:generalized-go-bounds} along with Bennett-type bounds  \eqref{eq:bennet-mgf-ineq} or \eqref{eq:bennet-(a,b)}, we can deploy computational resources to estimate
$E_{\mu_N^\Phi}[f]$ or possibly $\mbox{Var}_{\mu_N^\Phi}[f]$---see also Table~\ref{tab:MGF-bounds}---just  for the baseline model $P=\mu_\Phi$,
instead of simulating all alternative models $Q=\mu_\Psi$ models; (2) we do not need to use 
the  full GO divergence bounds  in Theorem~\ref{thm:GO-bounds}, which  require potentially expensive  full MGF calculations,  also recalling Remark
\ref{battery_remark}.
  
  



%%%%%%%%%%%%%%%%%%%%%%shan

\section{Conclusion}
In this paper we combined the uncertainty quantification  information  inequality of \cite{dupuis2011uq,katsoulakisuq16,katsoulakisjcp2017}  together with classical concentration inequalities \cite{concentration} to obtain  
easily implementable bounds for the model bias of quantities of interest (QoIs). The bounds control the model 
bias  in terms of the relative entropy 
between  different models and intrinsic statistical quantities associated to the QoIs in a baseline model, e.g. mean, variance,  $L^\infty$ bound. 
Our results improve substantially on  classical information bounds such as the Pinsker inequality. 
First, our bound scales correctly with the size of the data sets/number of degrees of freedom while 
classical inequalities do not, see Remark~\ref{rem:poor:scalab}. This scaling property is illustrated in Section \ref{sec:scalability} where we discuss  bias bounds for general statistical estimators.
In addition,  we demonstrate the tightness of our bounds in Sections \ref{sec:outline} and \ref{sec:sharpness-and-robustness}: given suitable families of QoIs and a family of models whose Kullback-Leibler divergence with respect to a given baseline   model is less than a tolerance $\eta^2$, there  always exists a QoI and models which saturate the upper and lower bounds. This demonstrates rigorously the precise  sense 
our model bias bound is optimal.  In forthcoming work we will apply and generalize our results to quantify model bias between different stochastic dynamics, e.g.  
Markov processes, in their  long-time regime,  bias   in  phase diagrams of Gibbs-Markov random fields, as well as model bias of coarse-grained models for  equilibrium and non-equilibrium molecular dynamics built via variational inference methods, \cite{Shell,KP2016}.





% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%


\appendices
\section{Proof of Theorem~\ref{thm:tightness}}
\label{sec:Appendix:tightness:GO}

While all the ingredients in the proof of 
Theorem~\ref{thm:tightness} are already  
present in~\cite{dupuis2011uq,katsoulakisuq16},
(see in particular \cite{katsoulakisuq16}[Theorem 2.9]), 
its formulation is new and we provide here a proof for completeness.  
Theorem~\ref{thm:tightness} follows immediately from following lemma

\begin{lemma}
%\label{aux:bound:func:gen:prop} 
Let $P$ be a probability measure and 
$f$ to be a non-constant function such 
that its moment generating 
function $\Mp{c;\ti f}$ is finite in a neighborhood of $0$. Let $Q$ be such that $\R QP=M$.  
\begin{enumerate}
\item For any $M \ge0$ the optimization problems
\begin{equation}
%\inf_{ \alpha>0} B^{\pm}(\alpha;M) = 
\go Q P {\pm f} =\inf_{c>0} \frac{\log M_P(\pm c; \ti f)+M}{c}
\end{equation}
have unique minimizers $c^{\pm}\in[0, + \infty]$. Moreover there exists
$0< M_{\pm}\le\infty$ such that the minimizers $c^{\pm}=c^{\pm}(M)$
are finite for $M \le M_{\pm}$ and $c^{\pm}(M) = + \infty$ if $M >
M_{\pm}$.

\item If $c^\pm=c^{\pm}(M)$ is finite
\begin{equation}
\label{eq:Bpmeqn}
\begin{aligned}
\go Q P {\pm f}  = \frac{\log M_P(\pm c^\pm; \ti f)+M}{c^\pm}
=\frac{d\log M_P}{dc}(\pm c^{\pm}; \ti f)  
=\pm(\E_{P^{\pm c^{\pm}}}[f]- \E_P[f])\,,
%
%
%\frac{\log M_P(\pm c^\pm; f)+M}{c^\pm}=\inf_{c>0} \frac{\log M_P(\pm c; f)+M}{c}
%=\partial_c \log M_P(\pm c^{\pm}; f)=\pm\mathbb{E}_{P^{\pm c^{\pm}}}[f]\,,
%\label{eq:Bpmeqn}%
\end{aligned}
\end{equation}
%\begin{equation}
%\frac{H(\pm\alpha_{\pm})+M}{\alpha_{\pm}}=
%\inf_{\alpha>0} \frac{H(\pm\alpha)+M}{\alpha}
%\,=\,H^{\prime}%
%(\pm\alpha_{+})=\pm\mathbb{E}_{P_{\pm\alpha_{\pm}}}[g]\,,\label{eq:Bpmeqn}%
%\end{equation}
where $c^{\pm}(M)$ is strictly increasing in $M$ and is determined by the
equation
\begin{equation}
\R  {P^{\pm c^{\pm}}}{P}
=M\,.\label{eq:cond:re}%
\end{equation}


\item If $M_{\pm}<\infty$ then $f$ is necessarily $P$ almost surely bounded above/bounded below respectively  with upper/lower bound $f_\pm$.
For $M>M_{\pm}$ we have that $c^{\pm}(M)=+\infty$ and 
\begin{equation}
\go Q P {\pm f}
= \pm (f_\pm - E_P[f])
\,.
\label{eq:fplus}
\end{equation}


\end{enumerate}
\end{lemma}
\begin{proof}
For notational ease, in the proof, let 
us set $H(c)=\log M_P(c; \ti f)$ 
and note that since $\ti f$ is 
centered we have $H(0)=H'(0)=0$. 
We have $H'(c)= \E_{P^c}[f]-\E_p[f]$ and
$H''(c)=\mathrm{Var}_{P^c}(f) >0$ since 
$f$ is not constant $P$ almost surely 

If $d_+ < \infty$ then we have 
$\lim_{c \to d_+} H(c)= \infty$ and 
$\lim_{c \to d_+} H'(c)= \infty$. 
If $d_+ = \infty$ then 
\begin{equation}
\lim_{c \to \infty} H'(c) = \left\{ 
\begin{array}{cl} f_+ - \E_P[f]& \textrm{ 
if }  f \textrm{ is bounded} \\
+\infty & \textrm{ otherwise} 
\end{array}
\right. \,.
\end{equation}
Since $c^{-1}H(c) = c^{-1}\int_0^c 
H'(t) dt$ and $H'(c)$ is strictly 
increasing $c^{-1} H(c)$ is a strictly 
increasing function and we have 
$\lim_{c\to \infty} c^{-1} H(c) = 
\lim_{c\to \infty} H'(c)$ 
which is finite if only if $f$ is bounded.   
Let us set 
\[
B(c; M)=\frac{\log M_P(c; f)+M} {c}=\frac{H(c)+M}{c}
\]
and then distinguish two cases: 

\smallskip 
\noindent
(a) If $d_+ \le \infty$ or if $d_+=\infty$ and $f$ is unbounded then we have $\lim_{c \to 0} B(c; M)= \lim_{c \to d_+} B(c; M) = +\infty$ \
and thus $B(c; M)$ has at least one 
minimum for some $0< c < d_+$. 
By calculus the minimum must be a solution of 
\[
0 = \frac{\partial}{\partial c} B(c;M)= \frac{c H'(c)- H(c) - M }{c^2}
\]
that is me must have $c H'(c)- H(c)= M$. 
Since $\frac{\partial}{\partial c}(c H'(c)- H(c)) = 
cH''(c)> 0$ the function $c H'(c)- H(c)$ is 
strictly increasing and thus there is a 
unique minimizer $c_+$ for $B(c;M)$.    

\smallskip 
\noindent
(b) If $d_+ =\infty$ but $f$ is bounded, since $c H'(c)- H(c)$ is strictly increasing we have $\lim_{c \to \infty} 
cH'(c)- H(c) =M_+$ which may or may not be finite depending on $P$. If $M \le M_+$ we can proceed as in (a) to find a unique minimizer for a finite $c_+$,  while if 
$M> M_+$, $B(c;M)$ is strictly decreasing and thus the minimizer is attained at $c_+=\infty$.   

To conclude the proof we note that if 
$c_+ < \infty$ then  
$c_+ H'(c_+)- H(c_+) =M$
and thus 
\[
B(c_+, M) = H'(c_+)
\]
which proves \eqref{eq:Bpmeqn}. On the other hand a simple computation shows that
for any $c$ 
\[
\R {P^c} P =  c H'(c)- H(c)
\]
and this establishes \eqref{eq:cond:re}. 
Finally if $c_+=\infty$ the infimum is equal to $\lim_{c\to \infty}\frac{H(c)}{c}$ and this establishes \eqref{eq:fplus}.

\end{proof}





% use section* for acknowledgment
\section*{Acknowledgment}
The research of KG and MAK  was partially supported by the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract No. DE-SC0010723.
The research of MAK and LRB was partially supported by the National Science Foundation (NSF) under the grant DMS-1515712. 
The research of JW was partially supported by the Defense Advanced Research Projects Agency (DARPA) EQUiPS program under the grant  W911NF1520122.

% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://mirror.ctan.org/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
\bibliography{commonRefs}
%
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
% \begin{thebibliography}{1}

% \bibitem{IEEEhowto:kopka}
% H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%   0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.

% \end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

% \begin{IEEEbiography}{Konstantinos
%     Gourgoulias }
% Biography text here.
% \end{IEEEbiography}

% % if you will not have a photo at all:
% \begin{IEEEbiographynophoto}{Markos A.
%     Katsoulakis}
% Biography text here.
% \end{IEEEbiographynophoto}

% % insert where needed to balance the two columns on the last page with
% % biographies
% %\newpage

% \begin{IEEEbiographynophoto}{Luc
%     Rey-Bellet}
% Biography text here.
% \end{IEEEbiographynophoto}

% \begin{IEEEbiographynophoto}{Jie
%     Wang}
% Biography text here.
% \end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}




symbols.tex
% symbols used in the main text

% \usepackage{float}
% \usepackage{color}
 \usepackage{amsmath,amssymb,amsthm}
 \usepackage{graphicx}
 \usepackage{xspace}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \newtheorem{theorem}{Theorem}
% \newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
 \newtheorem{remark}[theorem]{Remark}
 \newtheorem{proposition}[theorem]{Proposition}

% \newtheorem{question}[theorem]{Question}
% \newenvironment{answer}{\textbf{Answer:}}{}


\renewcommand{\eqref}[1]{(\ref{#1})}

\newcommand{\argmin}{\mathrm{argmin}}
\newcommand{\argmax}{\mathrm{argmax}}

\newcommand{\eb}{\eta_{B}}
\newcommand{\Q}{\mathcal{Q}_{\eb}}
\newcommand{\sib}{\sigma_{B}}

\newcommand{\supnorm}[1]{\| #1 \|_{\infty}}

\newcommand{\supp}[1]{\mathrm{supp}\{ #1 \}}

% expectations
\newcommand{\E}{\mathbb{E}}
\newcommand{\Ep}{\E_{P}}
\newcommand{\Eq}{\E_{Q}}
\newcommand{\Ex}[2]{\E_{#1}[#2]}
\newcommand{\ti}[1]{\tilde{#1}} % shorthand for tilde

% sigma symbols
\newcommand{\ssp}{\sigma_P}
\newcommand{\ssq}{\sigma_Q}

%variances
\newcommand{\var}{\mathrm{var}}
\newcommand{\Vp}{\var_{P}}
\newcommand{\Vq}{\var_{Q}}

% kurtosis
\newcommand{\kurt}{\mathrm{kurt}}
\newcommand{\Kp}{\kurt_{P}}
\newcommand{\Kq}{\kurt_{Q}}

% various acronyms
\newcommand{\eg}{e.g.,\xspace}
\newcommand{\bigeg}{E.g.,\xspace}
\newcommand{\etal}{\textit{et~al.\xspace}}
\newcommand{\etc}{etc.\@\xspace}
\newcommand{\ie}{i.e.,\xspace}
\newcommand{\bigie}{I.e.,\xspace}
\newcommand{\aka}{aka,\xspace}

% relative entropy and go bounds
\newcommand{\R}[2]{R(#1\|#2)} % relative entropy

\newcommand{\go}[3]{\Xi(#1\|#2;#3)} % go bound
\newcommand{\gop}[3]{\Xi_{+}(#1\|#2;#3)} % plus version of go
\newcommand{\gom}[3]{\Xi_{-}(#1\|#2;#3)} % minus version of go
\newcommand{\gopm}[3]{\Xi_{\pm}(#1\|#2;#3)} % minus version of go

\newcommand{\U}[3]{U(#1\|#2;#3)} % U bound
\newcommand{\Up}[2]{U_{+}(#1;#2)}
\newcommand{\Um}[2]{U_{-}(#1;#2)}
\newcommand{\Upm}[2]{U_{\pm}(#1;#2)}

\newcommand{\bias}[1][f]{\Eq[#1]-\Ep[#1]} % bias


\newcommand{\Phip}[1]{\Phi(#1)} % phi function -- bound to the mgf
\newcommand{\Mp}[1]{M_{P}(#1)} % MGF
\newcommand{\Ptil}[1]{P^{c_{#1}}} % tilted measures

\newcommand{\Cp}[1]{\log \Mp{#1}} % log-cumulant
\newcommand{\Lp}{\Lambda_{P}} % shorthand for the log-cumulant without arguments
\newcommand{\ccP}[1]{\cp{#1}} % centered log cumulant -- to be removed


\newcommand{\Hq}{H_Q}
\newcommand{\Hp}{H_P}
\newcommand{\Zp}{Z_P}
\newcommand{\Zq}{Z_Q}


\newcommand{\efam}{\mathcal{Q}_{\eta}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\Fp}{\mathcal{F}_{P}} % class of observables w.r.t P




% \nn{X} -> X_1,\ldots, X_n
\newcommand{\nn}[1]{#1_{1},\ldots,#1_{n}}










%%%%
\newcommand{\sepeq}[1]{
\medskip
\noindent 
{\bf #1} 
}





%%% Local Variables:
%%% TeX-master: "main.tex"
%%% End:
main.bbl
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@rmstyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand\BIBentrySTDinterwordspacing{\spaceskip=0pt\relax}
\providecommand\BIBentryALTinterwordstretchfactor{4}
\providecommand\BIBentryALTinterwordspacing{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand\BIBforeignlanguage[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}

\bibitem{Dakota}
M.~S. Eldred, B.~M. Adams, D.~M. Gay, L.~P. Swiler, K.~Haskell, W.~J. Bohnhoff,
  J.~P. Eddy, W.~E. Hart, J.~paul Watson, P.~D. Hough, and T.~G. Kolda,
  ``Dakota, a multilevel parallel object-oriented framework for design
  optimization, parameter estimation, uncertainty quantification, and
  sensitivity analysis: version 5.0 user’s manual,'' Tech. Rep.
  SAND2010-2183, Sandia National Laboratories, Tech. Rep., Dec. 2009.

\bibitem{Smith}
R.~C. Smith, \emph{Uncertainty quantification: theory, implementation, and
  applications}.\hskip 1em plus 0.5em minus 0.4em\relax Society for Industrial
  and Applied Mathematics, 2013.

\bibitem{Saltelli:global}
A.~Saltelli, M.~Ratto, T.~Andres, F.~Campolongo, J.~Cariboni, D.~Gatelli,
  M.~Saisana, and S.~Tarantola, \emph{Global sensitivity analysis: the
  primer}.\hskip 1em plus 0.5em minus 0.4em\relax John Wiley \& Sons, 2008.

\bibitem{dupuis2011uq}
K.~Chowdhary and P.~Dupuis, ``Distinguishing and integrating aleatoric and
  epistemic variation in uncertainty quantification,'' \emph{ESAIM:
  Mathematical Modelling and Numerical Analysis}, vol.~47, no.~03, pp.
  635--662, 2013.

\bibitem{Sullivan2015}
T.~J. Sullivan, \emph{Introduction to uncertainty quantification}.\hskip 1em
  plus 0.5em minus 0.4em\relax Springer, 2015.

\bibitem{tsybakov}
A.~B. Tsybakov, \emph{{Introduction to nonparametric estimation}}.\hskip 1em
  plus 0.5em minus 0.4em\relax Springer Science \& Business Media, 2008.

\bibitem{bishop}
C.~M. Bishop, \emph{Pattern recognition and machine learning}.\hskip 1em plus
  0.5em minus 0.4em\relax Springer-Verlag New York, Inc., 2006.

\bibitem{burnham}
K.~P. Burnham and D.~R. Anderson, \emph{Model selection and multimodel
  inference: a practical information-theoretic approach}.\hskip 1em plus 0.5em
  minus 0.4em\relax Springer Science \& Business Media, 2003.

\bibitem{Shell}
A.~Chaimovich and M.~S. Shell, ``Relative entropy as a universal metric for
  multiscale errors,'' \emph{Physical Review E}, vol.~81, no.~6, p. 060104,
  2010.

\bibitem{KP2013}
M.~A. Katsoulakis and P.~Plech{\'a}{\v{c}}, ``Information-theoretic tools for
  parametrized coarse-graining of non-equilibrium extended systems,'' \emph{The
  Journal of chemical physics}, vol. 139, no.~7, p. 074115, 2013.

\bibitem{Noid}
J.~F. Rudzinski and W.~G. Noid, ``Coarse-graining, entropy, forces and
  structures,'' \emph{Journal of Chemical Physics}, vol. 135, no.~21, 2011.

\bibitem{majdabook}
A.~J. Majda, R.~V. Abramov, and M.~J. Grote, \emph{{Information theory and
  stochastics for multiscale nonlinear systems}}, ser. {CRM monograph
  series}.\hskip 1em plus 0.5em minus 0.4em\relax Providence, R.I. American
  Mathematical Society, 2005.

\bibitem{Atkinson2007OptimumExperimentalDesignsWithSAS.}
A.~Atkinson, A.~Doney, and R.~Tobias, \emph{Optimum experimental designs, with
  SAS}.\hskip 1em plus 0.5em minus 0.4em\relax Oxford University Press, May
  2007, vol. (2007). Oxford science publications. Oxford.

\bibitem{majdauncertainty}
A.~J. Majda and B.~Gershgorin, ``{Quantifying uncertainty in climate change
  science through empirical information theory},'' \emph{Proceedings of the
  National Academy of Sciences}, vol. 107, no.~34, pp. 14\,958--14\,963, 2010.

\bibitem{majdafidelity}
------, ``Improving model fidelity and sensitivity for complex systems through
  empirical information theory,'' \emph{Proceedings of the National Academy of
  Sciences}, vol. 108, no.~25, pp. 10\,044--10\,049, 2011.

\bibitem{Komorowski}
M.~Komorowski, M.~J. Costa, D.~A. Rand, and M.~P. Stumpf, ``{Sensitivity,
  robustness, and identifiability in stochastic chemical kinetics models},''
  \emph{Proceedings of the National Academy of Sciences}, vol. 108, no.~21, pp.
  8645--8650, 2011.

\bibitem{PK2013}
Y.~Pantazis and M.~A. Katsoulakis, ``{A relative entropy rate method for path
  space sensitivity analysis of stationary complex stochastic dynamics},''
  \emph{The Journal of chemical physics}, vol. 138, no.~5, p. 054115, 2013.

\bibitem{Cover2006ElementsofInformationTheory}
T.~M. Cover and J.~A. Thomas, \emph{Elements of information theory}.\hskip 1em
  plus 0.5em minus 0.4em\relax Wiley-Interscience, July 2006.

\bibitem{katsoulakisjcp2017}
M.~A. Katsoulakis, L.~Rey-Bellet, and J.~Wang, ``Scalable information
  inequalities for uncertainty quantification,'' \emph{Journal of Computational
  Physics}, vol. 336, pp. 513--545, 2017.

\bibitem{katsoulakisuq16}
P.~Dupuis, M.~A. Katsoulakis, Y.~Pantazis, and P.~Plechac, ``Path-space
  information bounds for uncertainty quantification and sensitivity analysis of
  stochastic dynamics,'' \emph{SIAM/ASA Journal on Uncertainty Quantification},
  vol.~4, no.~1, pp. 80--111, 2016.

\bibitem{dupuisellis}
P.~G. Dupuis and R.~S. Ellis, \emph{A weak convergence approach to the theory
  of large deviations}, ser. Wiley series in probability and statistics.\hskip
  1em plus 0.5em minus 0.4em\relax New York: Wiley, 1997.

\bibitem{simon2014statistical}
B.~Simon, \emph{The statistical mechanics of lattice gases}.\hskip 1em plus
  0.5em minus 0.4em\relax Princeton University Press, 2014.

\bibitem{glasserman2014}
P.~Glasserman and X.~Xu, ``Robust risk measurement and model risk,''
  \emph{Quantitative Finance}, vol.~14, no.~1, pp. 29--58, 2014.

\bibitem{lam2016}
H.~Lam, ``Robust sensitivity analysis for stochastic systems,''
  \emph{Mathematics of Operations Research}, vol.~41, no.~4, pp. 1248--1275,
  Nov. 2016.

\bibitem{junliu}
J.~S. Liu, \emph{{Monte carlo strategies in scientific computing}}, ser.
  {Springer Series in Statistics}.\hskip 1em plus 0.5em minus 0.4em\relax New
  York: Springer-Verlag, 2001.

\bibitem{lelievre2010free}
T.~Leli{\`e}vre, G.~Stoltz, and M.~Rousset, \emph{Free energy computations: A
  mathematical perspective}.\hskip 1em plus 0.5em minus 0.4em\relax World
  Scientific, 2010.

\bibitem{delmoral2012}
P.~Del~Moral, A.~Doucet, and A.~Jasra, ``On adaptive resampling strategies for
  sequential monte carlo methods,'' \emph{Bernoulli}, vol.~18, no.~1, pp.
  252--278, Feb. 2012.

\bibitem{concentration}
S.~Boucheron, G.~Lugosi, P.~Massart, and M.~Ledoux, \emph{Concentration
  inequalities : a nonasymptotic theory of independence}.\hskip 1em plus 0.5em
  minus 0.4em\relax Oxford: Oxford University Press, 2013.

\bibitem{raginsky2013concentration}
M.~Raginsky, I.~Sason, \emph{et~al.}, ``Concentration of measure inequalities
  in information theory, communications, and coding,'' \emph{Foundations and
  Trends{\textregistered} in Communications and Information Theory}, vol.~10,
  no. 1-2, pp. 1--246, 2013.

\bibitem{ledoux2005concentration}
M.~Ledoux, \emph{The concentration of measure phenomenon}.\hskip 1em plus 0.5em
  minus 0.4em\relax American Mathematical Society, 2005.

\bibitem{dembo2010large}
A.~Dembo and O.~Zeitouni, ``Large deviations techniques and applications,''
  2010.

\bibitem{massart2007concentration}
P.~Massart, \emph{Concentration inequalities and model selection}.\hskip 1em
  plus 0.5em minus 0.4em\relax Springer, 2007.

\bibitem{tropp2015introduction}
J.~A. Tropp, ``An introduction to matrix concentration inequalities,''
  \emph{Foundations and Trends{\textregistered} in Machine Learning}, vol.~8,
  no. 1-2, pp. 1--230, 2015.

\bibitem{wasserman2004}
L.~Wasserman, \emph{All of statistics: a concise course in statistical
  inference}.\hskip 1em plus 0.5em minus 0.4em\relax Springer-Verlag, New York,
  2004.

\bibitem{bobkov1999exponential}
S.~G. Bobkov and F.~G{\"o}tze, ``Exponential integrability and transportation
  cost related to logarithmic sobolev inequalities,'' \emph{Journal of
  Functional Analysis}, vol. 163, no.~1, pp. 1--28, 1999.

\bibitem{hoeffding1963probability}
W.~Hoeffding, ``Probability inequalities for sums of bounded random
  variables,'' \emph{Journal of the American statistical association}, vol.~58,
  no. 301, pp. 13--30, 1963.

\bibitem{villani2008optimal}
C.~Villani, \emph{Optimal transport: old and new}.\hskip 1em plus 0.5em minus
  0.4em\relax Springer Science \& Business Media, 2008.

\bibitem{Carlier2010}
G.~Carlier, A.~Galichon, and F.~Santambrogio, ``From knothe's transport to
  brenier's map and a continuation method for optimal transport,'' \emph{SIAM
  Journal on Mathematical Analysis}, vol.~41, no.~6, pp. 2554--2576, 2010.

\bibitem{mcdiarmid1989method}
C.~McDiarmid, ``On the method of bounded differences,'' \emph{Surveys in
  combinatorics}, vol. 141, no.~1, pp. 148--188, 1989.

\bibitem{wasserman2010}
L.~Wasserman, \emph{All of nonparametric statistics}.\hskip 1em plus 0.5em
  minus 0.4em\relax Springer-Verlag New York, 2006.

\bibitem{boucheron2009concentration}
S.~Boucheron, G.~Lugosi, P.~Massart, \emph{et~al.}, ``On concentration of
  self-bounding functions,'' \emph{Electronic Journal of Probability}, vol.~14,
  no.~64, pp. 1884--1899, 2009.

\bibitem{eom2007life}
S.-W. Eom, M.-K. Kim, I.-J. Kim, S.-I. Moon, Y.-K. Sun, and H.-S. Kim, ``Life
  prediction and reliability assessment of lithium secondary batteries,''
  \emph{Journal of Power Sources}, vol. 174, no.~2, pp. 954--958, 2007.

\bibitem{weibulldef}
A.~Papoulis and S.~U. Pillai, \emph{Probability, random variables, and
  stochastic processes}.\hskip 1em plus 0.5em minus 0.4em\relax Tata
  McGraw-Hill Education, 2002.

\bibitem{MacKay:2003}
D.~J.~C. MacKay, \emph{Information theory, inference and learning
  algorithms}.\hskip 1em plus 0.5em minus 0.4em\relax Cambridge University
  Press, 2003.

\bibitem{li2012computation}
J.~Li and D.~Xiu, ``Computation of failure probability subject to epistemic
  uncertainty,'' \emph{SIAM Journal on Scientific Computing}, vol.~34, no.~6,
  pp. A2946--A2964, 2012.

\bibitem{Ortiz}
J.~Marian, G.~Venturini, B.~L. Hansen, J.~Knap, M.~Ortiz, and G.~H. Campbell,
  ``Finite-temperature extension of the quasicontinuum method using langevin
  dynamics: entropy losses and analysis of errors,'' \emph{Modelling and
  Simulation in Materials Science and Engineering}, vol.~18, no.~1, p. 015003,
  2010.

\bibitem{KP2016}
V.~Harmandaris, E.~Kalligiannaki, M.~Katsoulakis, and P.~Plech{\'a}\v{c},
  ``Path-space variational inference for non-equilibrium coarse-grained
  systems,'' \emph{Journal of Computational Physics}, vol. 314, no.~C, pp.
  355--383, June 2016.

\end{thebibliography}
