%
%\documentclass[10pt,conference,compsoc]{IEEEtran}
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:

%\newcommand{\CLASSINPUTtoptextmargin}{0.5in}
%\newcommand{\CLASSINPUTbottomtextmargin}{0.5in}
%\newcommand{\CLASSINPUTinnersidemargin}{0.5in}
%\newcommand{\CLASSINPUToutersidemargin}{0.5in} 
\documentclass[10pt,journal,cspaper,compsoc]{IEEEtran}

% %--------------- to make it tighter---------------
%\topskip 0in            %between header and text
%\parskip 0in            %gap between paragraphs
%\floatsep 0.1in           %space left between floats
%\textfloatsep 0.1in       %space between last top float or first bottom float and the text
%\intextsep 0.1in          %space left on top and bottom of an in-text float
%\dblfloatsep 0.1in        %floatsep for 2 column
%\dbltextfloatsep 0.1in    %space between last top float or first bottom float and the text
%\abovecaptionskip 0in   %space above caption
%\belowcaptionskip 0in   %space below caption
%%\abovedisplayskip 0.1in   %space before maths
%%\belowdisplayskip 0.1in   %space after maths
%% \arraycolsep 0.1in       %gap between columns of an array
%\partopsep 0.1in          %extra space added to \topsep when environment
% %--------------- to make it tighter---------------

% \usepackage[cm]{fullpage}
%\usepackage[margin=0.5in]{geometry}


\setlength{\belowcaptionskip}{0pt}


\usepackage{amssymb}
\usepackage{svg}
\usepackage[T1]{fontenc}% optional T1 font encoding
%\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
%\usepackage[ruled,vlined]{algorithm2e}
\usepackage{algorithmicx}
\usepackage[Algorithm,ruled]{algorithm}
\usepackage{paralist}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{xcolor}
\usepackage{enumerate}
\usepackage[color=yellow]{todonotes}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}{Definition}[section]
\usepackage{mathtools}  
\usepackage{tabulary}
\usepackage{booktabs}
\usepackage{nicefrac}
\usepackage{breqn}
\usepackage[inline]{enumitem}
\usepackage{enumitem}
\setlist{parsep=0pt,listparindent=\parindent}
\usepackage[font=small]{caption}
\makeatletter
\newcommand\footnoteref[1]{\protected@xdef\@thefnmark{\ref{#1}}\@footnotemark}
\makeatother
\usepackage{enumitem}
\allowdisplaybreaks

%\renewcommand{\theequation}{\alph{equation}}
% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % The IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  \usepackage[nocompress]{cite}
\else
  % normal IEEE
  \usepackage{cite}
\fi





% *** 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

% NOTE: PDF hyperlink and bookmark features are not required in IEEE
%       papers and their use requires extra complexity and work.
% *** IF USING HYPERREF BE SURE AND CHANGE THE EXAMPLE PDF ***
% *** TITLE/SUBJECT/AUTHOR/KEYWORDS INFO BELOW!!           ***
\newcommand\MYhyperrefoptions{bookmarks=true,bookmarksnumbered=true,
pdfpagemode={UseOutlines},plainpages=false,pdfpagelabels=true,
colorlinks=true,linkcolor={black},citecolor={black},urlcolor={black},
pdftitle={Bare Demo of IEEEtran.cls for Computer Society Journals},%<!CHANGE!
pdfsubject={Typesetting},%<!CHANGE!
pdfauthor={Michael D. Shell},%<!CHANGE!
pdfkeywords={Computer Society, IEEEtran, journal, LaTeX, paper,
             template}}%<^!CHANGE!
%\ifCLASSINFOpdf
%\usepackage[\MYhyperrefoptions,pdftex]{hyperref}
%\else
%\usepackage[\MYhyperrefoptions,breaklinks=true,dvips]{hyperref}
%\usepackage{breakurl}
%\fi
% One significant drawback of using hyperref under DVI output is that the
% LaTeX compiler cannot break URLs across lines or pages as can be done
% under pdfLaTeX's PDF output via the hyperref pdftex driver. This is
% probably the single most important capability distinction between the
% DVI and PDF output. Perhaps surprisingly, all the other PDF features
% (PDF bookmarks, thumbnails, etc.) can be preserved in
% .tex->.dvi->.ps->.pdf workflow if the respective packages/scripts are
% loaded/invoked with the correct driver options (dvips, etc.). 
% As most IEEE papers use URLs sparingly (mainly in the references), this
% may not be as big an issue as with other publications.
%
% That said, Vilar Camara Neto created his breakurl.sty package which
% permits hyperref to easily break URLs even in dvi mode.
% Note that breakurl, unlike most other packages, must be loaded
% AFTER hyperref. The latest version of breakurl and its documentation can
% be obtained at:
% http://www.ctan.org/pkg/breakurl
% breakurl.sty is not for use under pdflatex pdf mode.
%
% The advanced features offer by hyperref.sty are not required for IEEE
% submission, so users should weigh these features against the added
% complexity of use.
% The package options above demonstrate how to enable PDF bookmarks
% (a type of table of contents viewable in Acrobat Reader) as well as
% PDF document information (title, subject, author and keywords) that is
% viewable in Acrobat reader's Document_Properties menu. PDF document
% information is also used extensively to automate the cataloging of PDF
% documents. The above set of options ensures that hyperlinks will not be
% colored in the text and thus will not be visible in the printed page,
% but will be active on "mouse over". USING COLORS OR OTHER HIGHLIGHTING
% OF HYPERLINKS CAN RESULT IN DOCUMENT REJECTION BY THE IEEE, especially if
% these appear on the "printed" page. IF IN DOUBT, ASK THE RELEVANT
% SUBMISSION EDITOR. You may need to add the option hypertexnames=false if
% you used duplicate equation numbers, etc., but this should not be needed
% in normal IEEE work.
% The latest version of hyperref and its documentation can be obtained at:
% http://www.ctan.org/pkg/hyperref



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


\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{SafePredict: 
A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness  
}
%
%
% 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
%
%
%\IEEEcompsocitemizethanks is a special \thanks that produces the bulleted
% lists the Computer Society journals use for "first footnote" author
% affiliations. Use \IEEEcompsocthanksitem which works much like \item
% for each affiliation group. When not in compsoc mode,
% \IEEEcompsocitemizethanks becomes like \thanks and
% \IEEEcompsocthanksitem becomes a line break with idention. This
% facilitates dual compilation, although admittedly the differences in the
% desired content of \author between the different types of papers makes a
% one-size-fits-all approach a daunting prospect. For instance, compsoc 
% journal papers have the author affiliations above the "Manuscript
% received ..."  text while in non-compsoc journals this is reversed. Sigh.

\author{Mustafa~A.~Kocak,
        David~{R}amirez,~\IEEEmembership{Member,~IEEE,}
        Elza~Erkip,~\IEEEmembership{Fellow,~IEEE,}
        and~Dennis~E.~Shasha,~\IEEEmembership{Fellow,~ACM}% <-this % stops a space
\IEEEcompsocitemizethanks{
\IEEEcompsocthanksitem M. A. Kocak is with the Broad Institute of Harvard and MIT, Cambridge,
MA, 02142.\protect \quad 
% note need leading \protect in front of \\ to get a newline within \thanks as
% \\ is fragile and will error, could use \hfil\break instead.
E-mail: mkocak@broadinstitute.org

\IEEEcompsocthanksitem D. Ramirez and E. Erkip are with the Department
of Electrical and Computer Engineering, NYU Tandon School of Engineering, Brooklyn,
NY, 11201.\protect \quad
% note need leading \protect in front of \\ to get a newline within \thanks as
% \\ is fragile and will error, could use \hfil\break instead.
E-mail: dar550@nyu.edu, elza@nyu.edu
\IEEEcompsocthanksitem D. E. Shasha is with Courant Institute of Mathematical Sciences
New York University, New York, NY, 10012. \protect \quad E-mail: shasha@courant.nyu.edu}% <-this % stops a space
%\thanks{Manuscript received August 12, 2017; \textcolor{blue}{revised August 26, 2017.}}
}

% 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 Advanced Demo of IEEEtran.cls for IEEE Computer Society 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.



% The publisher's ID mark at the bottom of the page is less important with
% Computer Society journal papers as those publications place the marks
% outside of the main text columns and, therefore, unlike regular IEEE
% journals, the available text space is not reduced by their presence.
% 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}
% or like this to get the Computer Society new two part style.
%\IEEEpubid{\makebox[\columnwidth]{\hfill 0000--0000/00/\$00.00~\copyright~2015 IEEE}%
%\hspace{\columnsep}\makebox[\columnwidth]{Published by the IEEE Computer Society\hfill}}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark (Computer Society journal
% papers don't need this extra clearance.)



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



% for Computer Society papers, we must declare the abstract and index terms
% PRIOR to the title within the \IEEEtitleabstractindextext IEEEtran
% command as these need to go into the title area created by \maketitle.
% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\IEEEtitleabstractindextext{%
\begin{abstract}
\emph{SafePredict} is a novel meta-algorithm that works with any base prediction algorithm for online data to guarantee an arbitrarily chosen correctness rate, $1-\epsilon$, by allowing refusals. Allowing refusals means that the meta-algorithm may refuse to emit a prediction produced by the base algorithm so that the error rate on non-refused predictions does not exceed $\epsilon$. The SafePredict error bound does not rely on any assumptions on the data distribution or the base predictor. 
%Specifically, the error rate over non-refused data points is bounded by $\epsilon + O\left(\nicefrac{\sqrt{V^*}}{T^*}\right)$, where $T^*$ and $V^*$ are the expected value and the variance of the number of non-refused predictions computed with respect to the internal randomization of the meta-algorithm.  
When the base predictor happens not to exceed the target error rate $\epsilon$, SafePredict refuses only a finite number of times. When the error rate of the base predictor changes through time SafePredict makes use of a weight-shifting heuristic that adapts to these changes without knowing when the changes occur yet still maintains the correctness guarantee. Empirical results show that %(i) the error rate of SafePredict closely tracks the target error rate $\epsilon$ even in the face of abrupt changes to the error rate of the base predictor; (ii) weight-shifting reduces the number of refusals at only a slight cost in increased errors; (iii) 
(i) SafePredict compares favorably with state-of-the-art confidence-based refusal mechanisms which fail to offer robust error guarantees; and (ii) combining SafePredict with such refusal mechanisms can in many cases further reduce the number of refusals. Our software is included in the supplementary material.
\end{abstract}




% Note that keywords are not normally used for peerreview papers.
%\begin{IEEEkeywords}
%Computer Society, IEEE, IEEEtran, journal, \LaTeX, paper, template.
%\end{IEEEkeywords}
}


% make the title area
\maketitle


% To allow for easy dual compilation without having to reenter the
% abstract/keywords data, the \IEEEtitleabstractindextext text will
% not be used in maketitle, but will appear (i.e.,, to be "transported")
% here as \IEEEdisplaynontitleabstractindextext when compsoc mode
% is not selected <OR> if conference mode is selected - because compsoc
% conference papers position the abstract like regular (non-compsoc)
% papers do!
\IEEEdisplaynontitleabstractindextext
% \IEEEdisplaynontitleabstractindextext has no effect when using
% compsoc under a non-conference mode.


% 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


\ifCLASSOPTIONcompsoc

\IEEEraisesectionheading{\section{Introduction}\label{sec:introduction}}
\else
\section{Introduction}
\label{sec:introduction}
\fi
% Computer Society journal (but not conference!) papers do something unusual
% with the very first section heading (almost always called "Introduction").
% They place it ABOVE the main text! IEEEtran.cls does not automatically do
% this for you, but you can achieve this effect with the provided
% \IEEEraisesectionheading{} command. Note the need to keep any \label that
% is to refer to the section immediately after \section in the above as
% \IEEEraisesectionheading puts \section within a raised box.




% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps (small caps for compsoc).
% 
% 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.

%%%
%David suggestions in case things needs to get cut by a tiny bit
% Change "make a prediction" to "predict"
% Change "making a prediction" to "predicting"
% Switch "e.g.," to the (grammatically incorrect) "e.g."
% Change the wordy "in order to" to the plain "to"
%%%

Machine learning and statistical inference are the primary building blocks for systems that predict the future from the past. %\cite{abu2012machines,alpaydin2014introduction}. 
Prediction algorithms have been tailored to fit various applications ranging from analytics \cite{siegel2013predictive}, to health care \cite{dua2014machine,han2015building},
%wernick2010machine},
to judicial decision making \cite{harbert2013law,mit_tech}. One of the major concerns when utilizing prediction algorithms to automate risk-critical applications %(e.g., medical diagnosis, fraud detection, and legal decisions) 
is reliability. %In particular, a guarantee on the error rate of any automated system is highly desirable. 

To guarantee an error rate for an overall prediction system, a meta-algorithm should refuse to make a prediction when the meta-algorithm infers that the base prediction algorithm is likely enough to be in error. The implications of refusing to make a prediction may vary according to the application of interest. For example, in a medical diagnosis system, refusing to make a prediction may result in the collection of more information about the patient or a request to a human expert to make a decision based on a more thorough evaluation.

Inspired by the prediction-with-expert-advice framework \cite{cesa2006prediction}, we propose \textit{SafePredict}, an online meta-algorithm that accepts or refuses predictions of a base algorithm depending on the previous performance of the base algorithm. SafePredict asymptotically bounds the error to the desired level without any assumption on the data or the base predictor. %When the base predictor happens to meet the target error rate, the meta-algorithm will refuse to predict only a finite number of times.  
When the error rate of the base predictor varies over time, SafePredict adapts to those changes while preserving the error guarantee. %Empirical results on real and synthetic data show that SafePredict can more reliably follow a target error rate than the most prominent refusal algorithms. Furthermore, one can obtain yet fewer refusals by employing SafePredict on top of other refusal mechanisms.

\subsection{Prior Work}

The idea of allowing meta-algorithms to refuse to make predictions to reduce the error rate was first introduced by Chow \cite{chow1970optimum}. Chow mainly focused on the classification problem, where data points have an object-label pair independently sampled from a fixed and known probability distribution. Chow showed that the optimum error-refuse trade-off is achieved by a classifier that refuses to predict when the posterior probability of the estimated label given the object is less than a certain threshold. 

The major challenge in applying Chow's work is the need to know the data distribution, which is rarely available. The mainstream assumption is that the available data points are independently sampled from a fixed but unknown distribution. Given these data points, the most common approach is to estimate the underlying distribution and to use it in the  Chow framework. Estimating probability distributions in high dimensional and complex datasets can be harder even than classification itself, see e.g., \cite{friedman1997bias}. An alternative approach uses confidence-based refusals. One can train a classification algorithm with an arbitrary confidence score (e.g., distance to the decision boundary) and refuse to make a prediction for points with low confidence scores. Examples of this line of work are \cite{hellman1970nearest,landgrebe2006interaction, de2000reject, li2006confidence}. 
% fumera2000reject

Although many practical applications of the refusal framework exist in the literature, e.g., \cite{scheirer2014probability, golfarelli1997error,fumera2003classification,campi2010classification}, theoretical analyses of the suggested methods are relatively rare. {Some} notable exceptions are found in Wegkamp et al. \cite{bartlett2008classification,herbei2006classification,yuan2010classification}, El-Yaniv and Wiener \cite{el2010foundations,wiener2011agnostic} and Cortes et al. \cite{cortes2016learning} which approach the problem from a statistical learning theory perspective and suggest minimizing a linear combination of error and refuse probabilities. Alternatively, reliable agnostic learning, proposed by Kalai et al. \cite{kalai2012reliable}, posits an error threshold and searches for the least refusing predictor from a family of predictors that bounds the error to the error threshold, assuming such a predictor exists.

The related work discussed so far assumes a batch setup, i.e., the algorithm is trained on a fixed set of data points which are independently and identically distributed (i.i.d.). For a more comprehensive literature review of refusal algorithms in the batch setup, please see \cite{herbei2006classification,wiener2013theoretical,cortes2016learning,zhang2017reject} and the references therein. 

In contrast to the batch setup, a meta-algorithm in the online learning framework observes the true outcome after a prediction and then modifies its future behavior. 
In the conformal prediction framework of Vovk et al. \cite{vovk2005algorithmic}, a base algorithm generates confidence scores for each data point. Then the conformal predictor decides to predict or refuse based on these scores. A bound on the error probability and the independence between the error events are guaranteed under the assumptions that the data points are chosen from an exchangeable (essentially i.i.d.) distribution and the base predictor is invariant to the order of the observed data points. For recent developments regarding the classification with refusal problem in the conformal prediction framework we refer the reader to \cite{denis2015consistency,kocak2016conjugate ,lei2014classification} and Chapter 3 of \cite{vovk2005algorithmic}.
%One way to apply any refusing meta-algorithm in the online setting is to retrain the predictor after each new data point. 
Unfortunately, %any guarantees that might hold in the independent and identically distributed (i.i.d.) setting do not directly carry over, since 
in an online setting, the probability of making errors on consecutive predictions may be correlated or the data sequence may have a non-stationary or even an adversarial distribution. Thus, any guarantees that might hold in the independent and identically distributed setting do not directly carry over.

Another approach in the online setting starts with the KWIK (knows what it knows) framework \cite{li2008knows} which removes all assumptions about the data distributions. Instead, KWIK assumes the existence of a perfect predictor (i.e., a predictor that is always correct) among a set of predictors and aims to find this perfect predictor with a minimum number of refusals. Sayedi et al. \cite{sayedi2010trading} extend this framework by allowing a fixed error budget $k$ and characterizing the minimum number of refusals by keeping the number of errors below $k$. Finally, Zhang et al. \cite{zhang2016extended} relax the perfect predictor assumption to an $l$-bias assumption (i.e., predictor makes at most $l$ errors) and allow the algorithm to refuse in order to achieve an optimal error-refuse trade-off. 

\subsection{Contributions}

This paper makes the following main contributions:
\begin{compactenum}
\item The SafePredict online meta-algorithm can work with any base prediction algorithm to provide an asymptotic error guarantee on the non-refused predictions, without making any assumption about the data or
the base prediction algorithm(s).
\item All the variants of SafePredict meta-algorithm refuse at most a finite number of times when the base predictor's error rate is below the target error rate $\epsilon$.
\item Adaptive SafePredict meta-algorithm uses weight-shifting and other conventional adaptive procedures to track the error rate of the base predictor in changing environments, thus reducing the number of refusals while preserving the error guarantee.
\item Experiments show that the above theoretical guarantees are achieved in practice and translate to better error performance than other refusal algorithms. The experiments also show that combining SafePredict with previous meta-algorithms can lead to yet fewer refusals in many cases. %.\textcolor{blue}{We also showed that, using SafePredict on top of other refusal mechanisms, one can enjoy the same robust error guarantees and obtain higher adaptivity therefore fewer refusals by interpreting the excess refusals as a sign of abrupt changes in the environment.}
\end{compactenum}

The rest of the paper is organized as follows. Section $2$ presents the problem and provides a brief introduction to the exponentially weighted average forecasting (EWAF)  \cite{littlestone1989weighted,vavock1990aggregating} expert advice framework.  Section $3$ introduces SafePredict by recasting EWAF as a randomized refusal meta-algorithm and proves its theoretical properties. Section $4$ presents Adaptive SafePredict, a weight-shifting heuristic, to track changes in the error rate of the base algorithm and therefore reduce the number of refusals. Section $5$ presents experiments on real and synthetic data. Section $6$ concludes our work.

\subsection{Notation}

A summary of the notation introduced throughout the paper is given in Table 1. For each quantity, we provide the notation, a brief description, and a reference to the section where it is first introduced. 

\begin{table}[!htbp]\caption{Summary of the Notation \\ 
}
\centering % to have the caption near the table
\begin{tabular}{r p{5cm} c }
\toprule
Not. & Description & Def. in Sec. \\ 
\toprule
$\alpha_t, \beta_t$  & Adaptivity parameters, $\alpha_t \leq w_{P,t+1} \leq \beta_t$. & 4 \\  
% $\delta_t$  & Mixability gap, $\delta_t = l_t - m_t$. & 3.1 \\  
% $\varepsilon$ & Error rate for the meta-algorithm, $\nicefrac{L_{P,T}^*}{T^*}$.  & 2 \\
$\epsilon$ &   Target error rate. & 2 \\  
$\eta$ &  Learning rate, $\eta > 0$. & 2.1\\ 
$\rho_T$ &   Efficiency of the meta-algorithm, $\nicefrac{T^*}{T}$. & 2 \\
$D$ &   Dummy predictor, always refuses, $\hat{y}_{D,t} = \varnothing$ and $l_{D,t} = \epsilon$ for all $t$. & 3\\  
$l_t$ &   Expected loss at time $t$. & 2.1\\    
$L_T$ &  Cumulative expected loss, $\sum_{t=1}^T l_t$. & 2.1 \\ 
$l_{P,t}$ &   Loss of $P$ at time $t$, assume $l_{P,t} \in [0,1]$. & 2\\  
% $L_{P,T}$ &   $P$'s cumulative loss, $\sum_{t=1}^Tl_{P,t}$ . & 2 \\  
$L_{P,T,t_0}$ &  Partial cumulative loss of $P$ from $t_0$ to $T$, $\sum_{t=t_0+1}^T l_{P,t}$. The third index drops if $t_0=0$&  2 \\     
$L_{P,T}^*$ &   Expected cumulative loss for the meta-algorithm $\sum_{t=1}^Tw_{P,t}l_{P,t}$.  & 2 \\ 
%$M$ &   Meta-algorithm (see Figure 1). & 2 \\
%$m_t$ &   Mix-loss at time $t$. & 3.1 \\ 
%\bottomrule
%\end{tabular}
%~~
%\begin{tabular}{r p{5cm} c }
%\toprule
%Not. &  Description & Def. in Sec. \\ 
%\toprule  
%\vspace{4pt}
%$M_T$ & Cumulative mix-loss, $\sum_{t=1}^Tm_t$. & 3.1 \\
$P$ &  Base predictor. & 2 \\   
$P_i$ &  $i^{th}$ expert in the ensemble, has weight $w_{P_i,t}$ and loss $l_{P_i,t}$.& 2.1 \\ 
$T$ &  Time horizon. & 2\\ 
$T^*$ & Expected value of the number of (non-refused) predictions, $\sum_{t=1}^Tw_{P,t}$.  & 2 \\  
$V^*$ & Variance of the number of (non-refused) predictions, $\sum_{t=1}^Tw_{P,t}(1-w_{P,t})$.  & 2 \\  
% $V_{est}, V_{sum}$ & Current and running estimates of $V^*$, used in the doubling trick. & 3.3 \\ 
$w_{D,t}$ & Weight of the dummy, also the probability of refusal, $1-w_{P,t}$. & 3\\  
$w_{P,t}$ & Probability of making a prediction at time $t$. &  2 \\ 
% $\left(x_t, y_t\right)$ & (Object, Label) pair observed at time $t$. & 2\\  
$\hat{y}_{P,t}$  & Prediction of $P$ at time $t$. & 2 \\  
$\hat{y}_t$  & Filtered prediction, $\hat{y}_t = \hat{y}_{P,t}$ (predict) or  $\hat{y}_t = \varnothing$ (refuse) .& 2 \\  
\vspace{0pt} \\
\bottomrule
\end{tabular}
\label{tab:TableOfNotationForMyResearch}
\end{table}


\section{Problem Setup and Background}
This section introduces the mathematical formulation of the online prediction problem with a refusing meta-algorithm. Our method makes use of the prediction-within-the-expert-advice framework.

\subsection{Problem Formulation}
We assume access to a base predictor that produces a label prediction on an observed object. We denote the base predictor as $P$ and a sequence of (object, label) pairs by $(x_1,y_1), (x_2,y_2),\ldots, (x_T,y_T)$ where $T$ is an arbitrary horizon. At each time $t \in \{1,\ldots,T\}$ the base predictor does the following
\begin{compactenum} % [i.]
\item Observes the object $x_t$.
\item Predicts the corresponding label $\hat{y}_{P,t}$.
\item Observes the true label $y_t$, and suffers the loss $l_{P,t}$.
\end{compactenum}
In our formulation, we stay agnostic to the data sequence $(x_1,y_1), (x_2,y_2),\ldots, (x_T,y_T)$ and inner workings of the base predictor $P$ (which may for example be composed of an ensemble of predictors).  We  assume \emph{only} that the loss values are scaled to the unit interval, i.e., $0 \leq l_{P,t} \leq 1~ \forall~t$. 

For example, in a traditional classification task, the labels $y_t$ are  drawn from a finite set and 0-1 loss is used for the loss function, i.e., {$l_{P,t} = 0$ if $\hat{y}_{P,t} = y_t$ and $l_{P,t} = 1$ if $\hat{y}_{P,t} \neq y_t$}. 

Once the base predictor $P$ is chosen, our goal is to design a meta-algorithm $M$ which decides either to follow the prediction made by $P$ \emph{or} to refuse to make a prediction for each data point. 
We characterize this meta-algorithm by the following:
\begin{compactitem}
\item \textbf{Parameter}: Target error/loss rate, $\epsilon \in  (0,1)$, is the maximum average loss over time the user has specified.% can tolerate.
\item \textbf{Input}: In full generality, the input of $M$ at time $t$ consists of $x_i, \hat{y}_{P,i}~\forall~i \in \{1,...,t\},$ and $y_j, l_{P,j}~\forall~j \in \{1,...,t-1\}$. Note these are all the observed quantities \emph{before} the label $y_t$ is revealed.
\item \textbf{Output}: A randomized decision to predict (or refuse) at time $t$. We represent the output of $M$ as a probability value $w_{P,t} \in [0,1]$ that is used to decide the final prediction $\hat{y}_t$ as follows:
\[\hat{y}_{t} =   \left\{
\begin{array}{ll}
      \hat{y}_{P,t} & ~~~\textrm{with prob. }w_{P,t} \\
      \varnothing & ~~~\textrm{with prob. }1-w_{P,t} \\
\end{array} 
\right. ,\]
where $\varnothing$ denotes a refusal.
\end{compactitem}
A pictorial representation of this general framework is presented in Figure \ref{fig_1}.

%\textcolor{red}{Note that this setting implies that the labels could be generated by a potentially adversarial mechanism that has access to the previous predictions of the base predictor $P$, i.e., $\hat{y}_{P,t}$, but not the output of the meta-algorithm, i.e., $w_{P,t}$ or $\hat{y}_t$. }

This is a relaxed oblivious adversary model: the sequence of $x_i$, $y_i$, $\hat{y}_{P,i}$, and $w_{P,i}$ can be known to the adversary before generating $x_{i+1}, y_{i+1}$, but not $\hat{y}_{i}$. Intuitively, the adversary does not however know the output of the meta-algorithm.

The meta-algorithm $M$ calculates $w_{P,t}$ deterministically based on the observed data and then makes a randomized decision at each time point to refuse or predict. In the following definitions, we consider this randomness as the sole source of randomness within $M$ and compute all the expectations conditioned on the complete data sequence, i.e., $x_{t}, y_{t}, w_{P,t}$ $\forall~t$. 

Because $M$ makes a randomized decision at each time point, the number of (non-refused) predictions is a random variable and we compute the expected value $T^*$ of this quantity as \[T^* = \sum_{t=1}^T w_{P,t}.\]


%\textcolor{blue}{ Therefore, if $w_{P,t}$ is computed in a deterministic fashion from the previous data points, one can consider $x_{t}, y_{t}, w_{P,t}$ $\forall t$ as a predetermined sequence and the inner coins of the meta-algorithm $M$ as the sole source of randomness. In the following, we will take on this approach and refer all the expectations as if they are conditioned on the complete data sequence.}
%\todo[inline]{This sentence requires some more thinking and possibly moving to somewhere else! -Anil}


%We note that $M$ makes a randomized decision at each time point and therefore the number of (non-refused) predictions is a random variable. We compute the expected value $T^*$ of this quantity as \[T^* = \sum_{t=1}^T w_{P,t}.\]
We ascribe no loss from refusing to predict, so we define the expected cumulative loss of $M$ as
\[L_{P,T}^* = \sum_{t=1}^T w_{P,t}l_{P,t}.\]
Finally, we define the error rate for this randomized meta-algorithm by normalizing the cumulative expected loss via the expected number of non-refused predictions, i.e., $  {L_{P,T}^*}/{T^*}$.

Our top priority is to guarantee that the error rate of non-refused predictions made by the meta-algorithm does not exceed the target error rate $\epsilon$ as the number of predictions increases. Following nomenclature introduced by Tukey \cite{tukey1986sunset}, see also \cite{vovk2005algorithmic},	 we call this property  the \textit{validity} of the algorithm. Our goal is to satisfy validity without making any assumptions about the data. An asymptotic definition for the validity is given below.

\begin{definition}
A meta-algorithm $M$ with a given target error $\epsilon$ is called \emph{valid} if ${T^*} = O(1)$ or 
\[\limsup_{T^*\rightarrow \infty}\frac{L_{P,T}^* }{T^*}  \leq \epsilon . \]
\end{definition}

Next, among valid algorithms, we interpret the \textit{efficiency} of an algorithm as the fraction of the predicted data points and define it as follows.

\begin{definition}
The \textit{Efficiency} of a meta-algorithm $M$ is denoted by $\rho_T = T^*/T$ and $M$ is called \emph{efficient} if 
$T - T^* = o(T)$.  Furthermore, meta-algorithm $M$ is said to have the {\em finite refusal property} if $T-T^* = O(1)$.
%\[\lim\inf_{T\rightarrow \infty} \rho_T = 1. \]
\end{definition}

Note that $T-T^* = O(1)$ implies that there exists a finite $T_0$, such that the number of refusals is less than $T_0$ almost surely. This result directly follows from writing $T-T^*$ as $\sum_{t} \left(1 - w_{P,t}\right)$ and applying the Borel-Cantelli lemma directly (see Theorem 3.9 from \cite{krickeberg1965probability}). By contrast, $T^* = O(1)$ implies that we refuse almost all the time; thus efficiency approaches $0$ as ${T\rightarrow \infty}$.
%e.g., if the underlying machine learning algorithm never achieves the target correctness rate.

Though the discussion until now has defined validity and efficiency only asymptotically,  we will derive explicit bounds on the excess error rate, i.e., $L_{P,T}^*/ T^* - \epsilon$. %However, any non-trivial formal statement about the efficiency of $M$ has to depend on the performance of the base predictor $P$. To keep this dependence minimal, 
Below, we analyze the efficiency asymptotically for theoretical purposes for arbitrary base predictors. Experiments show that the efficiency is high for predictors that have an error rate below $\epsilon$. %{\em Anil: I've re-written a little.}


%\textcolor{green}{Furthermore, note that ``validity'' of an algorithm is only defined for the case $T^*\rightarrow \infty$, however, .... . This implies that the asymptotic limit holds, and in the scope of this paper we restrict our attention to the well-behaved cases assuming we can afford any finite number of predictions before the meta-algorithm chooses to refuse all the time. {\em Anil: I find this to be too vague (what does well-defined mean in this context and what does well-behaved mean?) and also we never refuse all the time because of weight-shifting. To me, we should be able to say something like this: The above definition will apply to all three cases of the base predictor's error rate: (i)  the base predictor's error rate is below $\epsilon$ almost everywhere (in which case $M$ will accept almost everywhere); (ii) the base predictor's error rate is above $\epsilon$ almost everywhere (in which case $M$ will refuse almost everywhere); and (iii) all cases in between. }}





\begin{figure}[!htbp] %[!t]
\centering
\includegraphics[width=0.85\linewidth]{Fig1.png}
\caption{\textit{The meta-algorithm, represented by $M$, makes a prediction equivalent to the recommendation of the base predictor $P$ or refuses to do so for data point $t$ while guaranteeing a target rate $\epsilon$. 
}}
\label{fig_1}
\end{figure}

For the sake of succinctness in the sequel, we introduce the following notation. First, we compute the variance $V^*$ of the number of non-refused predictions with respect to the randomness of the meta-algorithm (i.e., $w_{P,t}$) as
\[V^* = \sum_{t=1}^T w_{P,t}\left(1-w_{P,t}\right).\] 
Next, we denote the cumulative loss for any predictor $P$ (typically for the base predictor) as \[L_{P,T} = \sum_{t=1}^Tl_{P,t}.\] We also introduce a third sub-index $t_0$ for any cumulative quantity to represent that the corresponding sum starts from $t_0+1$, e.g., for the cumulative loss of $P$,  \[L_{P,T,t_0} = \sum_{t=t_0+1}^T l_{P,t}.\]


\subsection{Expert Advice and Exponentially Weighted Average Forecasting (EWAF)}

The prediction-with-expert-advice framework pertains to an online prediction scenario in which one has access to a fixed set of experts (predictors). The goal is to combine these experts' predictions such that the difference between the cumulative losses of the combined predictor and the best expert in the set is minimized. This difference is called \textit{regret}, and the algorithms that {guarantee a regret that grows sub-linearly with the number of predictions are defined as} \textit{Hannan consistent}. The appeal of the expert advice algorithms is the fact that the consistency can be guaranteed even in an adversarial setup. For a comprehensive treatment of the expert advice algorithms, we refer the reader to \cite{cesa2006prediction}.

Exponentially weighted average forecasting (EWAF), also known as ``multiplicative weights'' or ``randomized weighted majority,''  was first introduced by Littlestone and Warmuth \cite{littlestone1989weighted} and by Vovk \cite{vavock1990aggregating} for the expert advice prediction framework. Our meta-algorithm builds on EWAF to provide means to meet any target error rate. Among various expert advice algorithms, we focus on EWAF due to the simplicity of its analysis and strong theoretical guarantees. 

Consider $N$ predictors (experts) $P_1,P_2,\ldots, P_N$ each making a prediction $\hat{y}_{P_1,t}, \ldots, \hat{y}_{P_N,t}$ and each suffering a loss $l_{P_1,t}, \ldots, l_{P_N,t}$ at time $t$. At each time $t$, EWAF outputs one of these predictions as the combined prediction. To do so, EWAF starts with an initial probability distribution over the experts $\left(w_{P_1,1},\ldots, w_{P_N,1}\right)$ and a learning rate $\eta>0$. At each time point $t$, this probability distribution is used to choose an expert and consequently, use the prediction of that expert. The probability distribution is updated after the true label and corresponding losses are revealed. By denoting the probability that the predictor $P_i$ is chosen at time $t$ with $w_{P_i,t}$, the prediction $\hat{y}_t$ is obtained by 
\[\hat{y}_{t} = \hat{y}_{P_i,t}  ~ \textrm{with prob. }w_{P_i,t}, \qquad i=1,\ldots,N.\]
After the true label $y_t$ is revealed, we update these probabilities by multiplying them by an exponential factor that is scaled with the corresponding loss value  and the learning rate, i.e.,
\begin{eqnarray} w_{P_i,t+1} & = & \frac{w_{P_i,t} e^{-\eta l_{P_i,t}}}{\sum_{j=1}^N w_{P_j,t} e^{-\eta l_{P_j,t}}}. \label{ewaf_update} \end{eqnarray}
The pseudo-code of the EWAF algorithm is given in Algorithm 1. 
\begin{algorithm}[!htb]
\caption{ \textbf{Exp. Weighted Avg. Forecasting (EWAF)}\\
\textit{Initial weights}: $\left(w_{P_1,1},w_{P_2,1},\ldots, w_{P_N,1}\right)$ \\
\textit{Learning rate}: $\eta$}
\begin{algorithmic}[1]
\For {each $t=1,2,\ldots$}
\State Follow expert $P_i$ with probability $w_{P_i,t}$.
\State Update the weights :
\[ w_{P_i,t+1} = \frac{w_{P_i,t} e^{-\eta l_{P_i,t}}}{\sum_{j=1}^N w_{P_j,t} e^{-\eta l_{P_j,t}}} \]
\EndFor
\end{algorithmic}
\end{algorithm}
Given that EWAF randomly selects a predictor according to a known distribution, we can compute the expected loss for the combined prediction at time $t$ as
\[l_t = \sum_{i=1}^N w_{P_i,t}l_{P_i,t}\]
We denote the expected cumulative loss of the EWAF as \[L_T = \sum_{t=1}^Tl_t\] and the cumulative loss of expert $i, ~\forall~i$ as \[L_{P_i,T} = \sum_{t=1}^T l_{P_i,t}.\] 

The following well-known theorem establishes an upper bound to the expected loss for EWAF, implying that the regret of EWAF is bounded by $O(\sqrt{T \log N})$.

\begin{theorem} (Theorem 2.2 \cite{cesa2006prediction})
For any learning rate $\eta > 0$, and the initial weights $\left(w_{P_1,1},\ldots, w_{P_N,1}\right)$, we get the following bound for the expected cumulative loss of the EWAF
\begin{eqnarray}
L_T & \leq & L_{P_i,T} - \frac{\log w_{P_i,1}}{\eta} + \frac{\eta T}{8} \label{eq:b1}
\end{eqnarray}
for all $i= 1,\ldots, N$.

If we choose $w_{P_i,1} = 1/N$ for all $i$ and minimize the right-hand-side (RHS) of the bound above with respective to $\eta$, we get,
\begin{eqnarray}
 L_T & \leq & L_{P_i,T} + \sqrt{\frac{T\log N}{2}}
\label{eq:bound}
\end{eqnarray}
which is achieved for  $\eta = \sqrt{8\log(N) /T}$.
\end{theorem}
The bound given in eq. (\ref{eq:bound}) is optimal in the sense that there exists a matching lower bound in the worst case (see Chapter 3.7 \cite{cesa2006prediction}). Since the bound on the total sum of the expected loss holds for any predictor, it follows that the bound holds for the predictor with the least cumulative loss. Therefore, the bound in eq. (\ref{eq:bound}) limits how far EWAF is from optimality in terms of the sum of the expected loss.

%Applying the bound in eq. (\ref{eq:bound}) is insufficient to establish the validity of our algorithm, since eq. (\ref{eq:bound}) bounds regret only with $O\left(\sqrt{T}\right)$ while validity requires a sub-linear bound with $T^*$. In Section 3.1 we present a refined analysis with an appropriate learning rate to establish validity.



\section{Reliable Prediction with Refusals}

We now introduce our meta-algorithm, \textit{SafePredict}, which uses EWAF to convert any given base predictor $P$ into a refusing one with a guaranteed error bound.
Furthermore, we provide a theoretical analysis to establish the asymptotic validity and efficiency of SafePredict. Then, we employ the well-known doubling trick (see for instance Exercise 2.8 \cite{cesa2006prediction} or Theorem 7.7 \cite{mohri2012foundations}) to choose the learning rate and extend our validity analysis accordingly.

In order to achieve validity, we introduce a trivial predictor which can meet the target error rate by refusing to predict all the time. We refer to this particular predictor as the ``dummy predictor'' and denote it by $D$, i.e., $\hat{y}_{D,t}=\varnothing~\forall~t$. We also assume that the predictor $D$ suffers a constant loss $\epsilon$ for each time $t$, i.e., $l_{D,t}=\epsilon$ and $L_{D,t} = \epsilon t~\forall~t$. % \textcolor{orange}{While valid, the dummy algorithm achieves zero efficiency since it never predicts. }

SafePredict is obtained by employing an instance of the EWAF algorithm that runs on the ensemble $\{D,P\}$, to decide either to refuse or predict. Therefore at each step, SafePredict follows the base predictor with probability $w_{P,t}$ and computes the prediction probability for the next round after observing the corresponding loss of $P$ as
\begin{eqnarray}
w_{P,t+1} & = & \frac{w_{P,t}e^{-\eta l_{P,t}}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}}, \label{update_rule}
\end{eqnarray}
where $w_{D,t} = 1-w_{P,t}$ stands for the dummy's weight. 
The pseudo-code for SafePredict is given in Algorithm 2.

\begin{algorithm}[!htb]
\caption{ \textbf{SafePredict}\\
\textit{Base predictor}: $P$; ~\textit{Initial weight}: $w_{P,1} \in (0,1)$ \\
\textit{Learning rate}: $\eta > 0$; ~ \textit{Target error rate}: $\epsilon \in (0,1)$}
\begin{algorithmic}[1]
\For {each $t=1,2,\ldots$}
\State Predict with probability $w_{P,t}$, refuse otherwise, i.e.,
\[\hat{y}_{t} =   \left\{
\begin{array}{ll}
      \hat{y}_{P,t} & ~~~\textrm{with prob. } w_{P,t} \\
      \varnothing & ~~~\textrm{otherwise} \\
\end{array} 
\right. \]
\State Update the prediction probability:
\begin{eqnarray}
w_{P,t+1} & = & \frac{w_{P,t}e^{-\eta l_{P,t}}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}}, \nonumber \end{eqnarray}
\EndFor
\end{algorithmic}
\end{algorithm}

Note that Algorithm 2 requires no assumptions, e.g., i.i.d. assumptions, about the input data. The algorithm takes  \emph{only} the loss values as input.

\subsection{Validity}
%Recall that an algorithm is valid if the average loss does not exceed the target error rate. 
To bound the average loss of SafePredict one might be inclined to simply apply the bound presented in Theorem 2.1 with $N=2$, $P_1=P$,  $P_2=D$, and the optimal learning rate to minimize the RHS of eq. (\ref{eq:b1}) for $i=2$, which results in
\begin{eqnarray}
\frac{L_{P,T}^*}{ T^*} & \leq & \epsilon + \frac{1}{T^*}\sqrt{\frac{T\log (1/ w_{D,1})}{2}}.
\label{eq:badbound}
\end{eqnarray}
The problem with the bound in eq. (\ref{eq:badbound}) is that if the prediction probability decreases too quickly (i.e., for $T^*\ll\sqrt{T}$) the rightmost term can easily become vacuous, i.e., the excess error does not vanish. In particular, the bound is not sufficient to guarantee the validity of the algorithm for the case in which  $T^*$ the number of predictions made approaches infinity slower than $\sqrt{T}$ {where T is the number of data points presented}, i.e., $T^* = \omega \left(1\right)$ and  $T^* = O\left(\sqrt{T}\right)$. 

Further, even though the bound given in eq. (3) is tight in the worst case (i.e., adversarial scenario), \cite{cesa2007improved} introduces second-order adaptive techniques that perform better when the environment is more benign, e.g., pseudo-stationary. In particular, \cite{cesa2007improved} provides variance-based bounds with data-dependent learning rates (see Corollary 3.5.1 below). In the following, we develop a simpler bound based on the techniques introduced in \cite{de2014follow} to simplify our analysis in Section 4. The resulting bound has the same order of magnitude that we would have obtained using the methods of \cite{cesa2007improved}.

 
Particularly, in the following theorem, we present a refined bound for SafePredict that suggests a learning rate that decreases with the variance of the number of predictions, i.e., $V^*$, and guarantees the validity of our algorithm.

\begin{theorem} For any $P$, $\eta>0$, $\epsilon < 1/2$, and $0< w_{P,1} < 1$, SafePredict satisfies 
\begin{eqnarray}
\frac{ L_{P,T}^* }{T^*} & \leq & \epsilon - \frac{\log \left(w_{D,1}\right) }{\eta T^*} + \frac{\left(1 - \epsilon\right)^2\eta V^*}{T^*}. \label{valid_guarantee}
\end{eqnarray}
Consequently, by choosing the learning rate $\eta$ to minimize the RHS of this bound, we {get}
\begin{eqnarray}
\frac{L_{P,T}^*}{T^*} & \leq & \epsilon + \left(1 - \epsilon\right)\frac{2\sqrt{\log \left(1/w_{D,1}\right) V^*}}{T^*}  \label{valid_guarantee2}
\end{eqnarray}
for $\eta^* =\frac{\sqrt{{\log \left(1/w_{D,1}\right)}/{V^*}}}{1-\epsilon}$.
\end{theorem}

Before proving the statement given in the theorem, we define auxiliary quantities called ``mix-loss'' and ``mixability gap'', %as in \cite{de2014follow},
and present two important results from \cite{de2014follow} about EWAF in terms of these quantities. 

In the expert advice framework of Section 2.1, the \textit{mix-loss} $m_t$ is an alternative way of averaging the expert losses $l_{P_i,t},~\forall~i$ using the weights $w_{P_i,t},~\forall~i$. Formally, {\textit{mix-loss}} is defined as 
 \[m_t = -\frac{1}{\eta} \log \left(\sum_{i=1}^N w_{P_i,t} e^{-\eta l_{P_i,t}}\right)\]
 or equivalently $e^{-\eta m_t} = \sum_{i=1}^N w_{P_i,t} e^{-\eta l_{P_i,t}}$. Additionally, we denote the cumulative mix-loss as $M_T = \sum_{t=1}^Tm_t$.
 
One can bound the cumulative mix-loss in terms of the losses of the individual experts by the following lemma.
\begin{lemma} (\cite{de2014follow}, Lemma 1)
For the learning rate $\eta > 0$, and the initial weights $\left(w_{P_1,1},\ldots, w_{P_N,1}\right)$, the cumulative mix-loss of the EWAF satisfies the following inequality
\begin{eqnarray}
M_T & \leq & L_{P_i,T} - \frac{\log w_{P_i,1}}{\eta} 
\end{eqnarray}
for all $i= 1,\ldots, N$.
\end{lemma}

The bound on the cumulative mix-loss can be used to bound the cumulative expected loss by defining the \emph{mixability gap} as the difference between these two types of averages and bounding them with classical concentration inequalities. In particular, the mixability gap, $\delta_t = l_t - m_t$, can be bounded using the following lemma. 

\begin{lemma} (\cite{de2014follow}, Lemma 4)
The difference between the expected and mix losses obtained by EWAF algorithm is bounded by
\[\delta_t = l_t - m_t \leq \eta \sum_{i} w_{P_i,t} \left(l_t - l_{P_i,t}\right)^2 \] 
for all $t$.
\end{lemma}

Armed with these two lemmas, we can continue with the proof of Theorem 3.1
\begin{proof}[Proof of Theorem 3.1]
By definition of $\delta_t$ we have 
\begin{eqnarray}
L_T & = & M_T + \sum_{t=1}^T \delta_t. \nonumber
\end{eqnarray}
Then by applying Lemma 3.2. with $P_i = D$, we get
\begin{eqnarray}
\sum_{t=1}^T l_t & \leq & \epsilon T -\frac{\log \left(w_{D,1}\right) }{\eta} + \sum_{t=1}^T \delta_t. \label{first_step}
\end{eqnarray}



Next, we plug in the {definition} of the expected loss $l_t = w_{P,t} l_{P,t} + w_{D,t}\epsilon$, and divide both sides by the expected number of predictions, %noting that $w_{D,t} = 1-w_{P,t}$,
\begin{eqnarray}
\sum_{t=1}^T w_{P,t} l_{P,t}  & \leq & \sum_{t=1}^T (1-w_{D,t})\epsilon  -\frac{\log \left(w_{D,1}\right) }{\eta} + \sum_{t=1}^T \delta_t \nonumber \\
{L_{P,T}^*}  & \leq & \epsilon T^*   -\frac{\log \left(w_{D,1}\right) }{\eta } +{\sum_{t=1}^T \delta_t} \nonumber \\ 
\frac{L_{P,T}^*}{T^*}  & \leq & \epsilon -\frac{\log \left(w_{D,1}\right) }{\eta T^* } +\frac{1}{T^*}{\sum_{t=1}^T \delta_t}.
\label{last_step}
\end{eqnarray}

Finally, we obtain the desired result by bounding $\delta_t$:
\begin{align}
\delta_t ~ & \leq  ~ \eta\left( w_{P,t} \left(l_t - l_{P,t}\right)^2 + w_{D,t} \left(l_t - \epsilon \right)^2\right) \label{a1} \\
& = ~ {\eta}\left( w_{P,t} w_{D,t}^2  + w_{D,t} w_{P,t}^2 \right)\left(l_{P,t} - \epsilon \right)^2 \label{b1} \\
& = ~ {\eta} w_{P,t} w_{D,t}\left( l_{P,t} - \epsilon\right)^2  \label{c1} \\
& \leq ~ {\eta} w_{P,t} w_{D,t}\left( 1 - \epsilon\right)^2 \label{mix_gap_bound}
\end{align}
(\ref{a1}) follows from Lemma 3.3, while (\ref{b1}) and (\ref{c1}) follow from the definition of $l_t$ and $w_{D,t} + w_{P,t} = 1$, respectively.

Then, by summing up both sides of eq. (\ref{mix_gap_bound}) over $t$, we get
\begin{eqnarray}
\sum_{t=1}^T\delta_t & \leq & \frac{\eta V^*}{\left(1-\epsilon\right)^2}. \label{mix_gap_cum}
\end{eqnarray}https://www.overleaf.com/project/5bcc82f8278cd86e7cfd27d3

The desired result for the first part of the theorem, eq. (\ref{valid_guarantee}), follows by plugging eq. (\ref{mix_gap_cum}) into eq. (\ref{last_step}). Finally, the learning rate $\eta$ that minimizes the RHS of eq. (\ref{valid_guarantee}) can be found by basic calculus, and by plugging in the optimal learning rate we obtain {eq.} (\ref{valid_guarantee2}).
\end{proof}

Note that the essential difference between the bounds in eq. (\ref{eq:badbound}) and (\ref{valid_guarantee2}) lies in the choice of the learning rate $\eta$. While the optimal learning rate for the conventional use of EWAF is on the order of $1/\sqrt{T}$, Theorem 3.1 suggests choosing $\eta$ to be on the order of $1/\sqrt{V^*}$, which decreases much slower than $1/\sqrt{T}$, and leads to a sufficient condition for the validity of our algorithm.

Theorem 3.1 implies the excess error rate decreases with a rate ${\sqrt{V^*}}/{T^*}$, i.e., $L_{P,t}^*/T^* - \epsilon = O\left({\sqrt{V^*}}/{T^*}\right)$. Since $V^*$ is always less than or equal to $T^*$, this rate is bounded by
\[\frac{1}{T^*} \leq \frac{\sqrt{V^*}}{T^*} \leq \frac{1}{\sqrt{T^*}}.\]
Therefore our result implies that as more predictions are made (i.e., $T^*$ increases) the bound becomes tighter and guarantees the validity of SafePredict algorithm. 
\begin{corollary}
For any $P$, $\epsilon < 1/2$, $0< w_{P,1} < 1$, if one choose the learning rate $\eta$ in the order of $1/\sqrt{V^*}$, i.e., $\eta = \Theta\left(1/\sqrt{V^*}\right)$,  SafePredict is guaranteed to be valid.
\end{corollary}

Unfortunately, selecting a learning rate $\eta$ that depends on $V^*$ is infeasible because $V^*$ is unknown a priori. In Section 3.3 we describe a practical method for choosing a learning rate without knowledge of the expected number of refusals while still satisfying eq. (\ref{valid_guarantee2}) up to a constant factor. Having shown the validity of our algorithm, we now move to the efficiency.

\subsection{Efficiency}
In this section, we study the efficiency of the SafePredict meta-algorithm given in Algorithm 2. In contrast with validity which we addressed without requiring any assumptions on the base predictor, we must characterize the efficiency of a given algorithm with respect to the performance of the base predictor $P$. We show that SafePredict leads to efficient predictions if the base predictor $P$ has an asymptotic error rate smaller than the target error rate $\epsilon$, i.e., $\lim_{t\rightarrow \infty} L_{P,t}/t < \epsilon.$

The following lemma lower and upper bounds the probability of making a prediction at time $t+1$, i.e., $w_{P,t+1}$, in terms of the cumulative loss of the base predictor $P$. 

\begin{lemma} The probability of making a prediction at time $t+1$ for SafePredict, namely $w_{P,t+1}$, satisfies the following 
\begin{align}
1 - {\frac{w_{D,1}}{w_{P,1}} e^{ \eta  \left(L_{P,t} - \epsilon t\right)} } \leq w_{P,t+1}  \leq  {\frac{w_{P,1}}{w_{D,1}} e^{ \eta  \left(\epsilon t - L_{P,t}\right)} }. \label{dummy_bound}
\end{align}
%or equivalently in terms of the probability of refusal:
%\begin{align}
%1 - {\frac{w_{P,1}}{w_{D,1}} e^{ \eta  \left(\epsilon t - L_{P,t} \right)} } \leq w_{D,t+1}  \leq  {\frac{w_{D,1}}{w_{P,1}} e^{ \eta  \left(L_{P,t} - \epsilon t\right)} }. \label{refusal_bound}
%\end{align}
\end{lemma}

\begin{proof}
To prove the upper bound in eq. (\ref{dummy_bound}) we first note that the update rule given in eq. (\ref{update_rule}) can be written in terms of the mix-loss, and by induction we can obtain the prediction probability at time $t+1$ in terms of the cumulative losses $M_t$ and $L_{P,t}$ (see (\ref{a2}) and (\ref{b2}) below), i.e.,    
\begin{align}
w_{P,t+1}~ & = ~ \frac{w_{P,t}e^{-\eta l_{P,t}}}{e^{-\eta m_t}} ~  = ~  w_{P,t}e^{\eta \left(m_t - l_{P,t}\right)} \label{a2} \\
 ~ & =  ~  w_{P,1}e^{\eta \left(M_t - L_{P,t}\right)}  \label{b2} \\
 ~ & \leq ~ w_{P,1}e^{\eta \left(L_{D,t} - \log(w_{D,1})/\eta - L_{P,t}\right)} \label{c2} \\ 
& \leq ~  \frac{w_{P,1}}{w_{D,1}}e^{\eta \left(\epsilon t - L_{P,t}\right)}. \label{d2}
\end{align}

Next, (\ref{c2}) and (\ref{d2}) follows by applying Lemma 3.2 with $P_i = D$ to bound the cumulative mix loss in terms of the cumulative loss of the dummy, $L_{D,t} = \epsilon t$.

For the lower bound, we apply the same argument for $w_{D,t+1} = 1-w_{P,t+1}$. %Finally, for the lower bounds we simply plug in  $w_{D,t+1} = 1- w_{P,t+1}$ into the upper bounds we just derived, e.g.,
%\begin{eqnarray}
%w_{D,t+1} & \leq  & {\frac{w_{D,1}}{w_{P,1}} e^{  \eta  \left( L_{P,t} - \epsilon t \right)} } \nonumber \\
%1 - w_{P,t+1} & \leq  & {\frac{w_{D,1}}{w_{P,1}} e^{  \eta  \left(L_{P,t} - \epsilon t\right)} }. \nonumber 
%\end{eqnarray}
\end{proof}
Note that {Lemma 3.4 implies that} the probability of making a prediction decreases exponentially fast if the cumulative loss of the base predictor is increasing faster than the target error rate $\epsilon$. Next, we exploit this fact to show that if the base predictor satisfies the desired error requirement (i.e., its average loss is already below $\epsilon$), {our algorithm achieves a finite expected number of refusals.}

\begin{theorem}
If $\limsup L_{P,T} / T =\epsilon' < \epsilon$ and $\eta T \rightarrow \infty$ in the limit $T\rightarrow \infty$, then the expected number of refusals made by SafePredict is finite, i.e., 
\begin{eqnarray}
\lim_{T\rightarrow \infty} T-T^* & = & \sum_{t=1}^\infty w_{D,t} ~ < ~ \infty. \label{finite}
\end{eqnarray}
\end{theorem}
\begin{proof} 

Since $\epsilon' < \epsilon$, there exists a $t_0 < \infty $ such that for all $t > t_0$:
\begin{eqnarray}\frac{L_{P,t}}{t} & \leq & \epsilon' + \frac{\epsilon - \epsilon'}{2}. \label{lim}\end{eqnarray}
Then, 

\begin{align}
\sum_{t=1}^\infty w_{D,t} ~ & = ~ \sum_{t=1}^{t_0} w_{D,t} + \sum_{t=t_0+1}^\infty w_{D,t}  \\
& \leq ~ t_0 +  \sum_{t=t_0+1}^\infty \left( 1-w_{P,t} \right) \label{a3} \\
& \leq  t_0 + \frac{1- w_{P,1}}{w_{P,1}} \sum_{t=t_0+1}^\infty  e^{\eta t \left(L_{P,t}/t - \epsilon\right)} \label{b3} \\
& \leq  t_0 +  \lim_{t'\rightarrow \infty} \frac{w_{D,1}}{w_{P,1}} \sum_{t=t_0+1}^{t'} e^{\eta t \left(\epsilon' - \epsilon\right)/2}  \label{c3} \\
& \leq  t_0 +  \lim_{t'\rightarrow \infty} \frac{w_{D,1}}{w_{P,1}} \frac{e^{\eta (t_0+1) \left(\epsilon' - \epsilon\right)/2} - e^{\eta t' \left(\epsilon' - \epsilon\right)/2}}{1-e^{\eta \left(\epsilon' - \epsilon\right)/2}} ~  \label{d3} \\
& \leq  t_0 +  \frac{w_{D,1}}{w_{P,1}} \frac{e^{\eta (t_0+1) \left(\epsilon' - \epsilon\right)/2}}{1-e^{\eta \left(\epsilon' - \epsilon\right)/2}} ~ < ~ \infty, \label{e3}
\end{align}

where  (\ref{a3}) follows from the fact that $w_{D,t} \leq 1$, (\ref{b3}) follows from Lemma 3.4, (\ref{c3}) follows from eq. (\ref{lim}), (\ref{d3}) follows from the sum of a geometric series and from the fact $e^{\eta \left(\epsilon' - \epsilon\right)/2} < 1$, finally (\ref{e3}) follows from the hypothesis $\eta T \rightarrow \infty$.
\end{proof}
 
Theorem 3.5 shows that when the base predictor is already valid, SafePredict is not only efficient but also satisfies the \textit{finite refusal property}. Furthermore, as mentioned in Section 2, the finite refusal property implies a finite number of refusals almost surely beyond the expected value. %the theorem shows the expected number of refusals is finite even over an infinite data stream. The following corollary strengthens the operational insight from the expected value to an \emph{almost sure} statement.}

%\begin{corollary}
%If $L_{P,t}/t < \epsilon$ in the limit $t\rightarrow \infty$ and $\eta = \omega \left(T^{-1}\right)$, i.e., $\eta T \rightarrow \infty$, then SafePredict \textcolor{red}{is guaranteed to have the finite refusual property }  i.e., $T^{*} = O(1).$
%\[\liminf_{T \rightarrow \infty} \rho_T 
%= \liminf_{T \rightarrow \infty} 1 - \frac{\sum_{t=1}^T w_{D,t}}{T}  = 1.\]


%\end{corollary}
%\begin{proof}
%The first part of the corollary is a direct consequence of  Theorem 3.5, and the second part follows from the Borel-Cantelli Lemma, see e.g., Theorem 3.9 from \cite{krickeberg1965probability}.
%\end{proof}

Note that the finite refusal property
%Corollary 3.5.1 
depends on the assumption that the predictor $P$ can (eventually) predict accurately enough to obtain a valid algorithm. If the predictor is highly inaccurate, i.e., $l_{P,t} > \epsilon$ with high probability, then the SafePredict meta-algorithm will refuse almost all the time, as it should, and the hypothesis $\eta T \rightarrow \infty$. The meta-algorithm does not need to know in advance how well the base predictor will behave to achieve this desirable outcome. Further, we can make SafePredict adaptive when the base predictor sometimes is valid and sometimes is not, as we show in Section 4.

\subsection{Choosing the Learning Rate}

Corollary 3.3.1 and 3.5.1 establish the validity and efficiency of SafePredict once the learning rate $\eta$ is chosen to be on the order of $1/\sqrt{V^*}$, %(note $T/\sqrt{V^*}\rightarrow \infty$),
but $V^*$ cannot be known a priori. One classical method of addressing the issue of estimating unknown quantities in an online scenario is known as the \emph{doubling trick} (cf. Chapter 2.3 of \cite{cesa2006prediction} or Theorem 7.7 of \cite{mohri2012foundations}).
Sophisticated  methods to choose $\eta$ include the approach of Theorem 5 from \cite{cesa2007improved} to provide the following validity bound:
\begin{corollary}[to Theorem 5 of \cite{cesa2007improved}] For any $P$, $\epsilon < 1/2$, and $0< w_{P,1} < 1$, SafePredict (Alg. 2) with a data dependent learning rate \[\eta_t = min\left\{\frac{1}{2}, \frac{0.894}{\sqrt{\sum_{i=1}^{t-1}\left(l_{P,i} - \epsilon\right)^2w_{P,i}w_{D,i}}}\right\},\] satisfies the following  validity bound:
%\todo{anil to double check the constants}
\begin{eqnarray}
\frac{L_{P,T}^* }{T^*} & \leq & \epsilon + \frac{25}{T^*} + 4 \frac{\sqrt{V^*}}{T^*}. \label{doubling_trick}  \end{eqnarray}
\end{corollary}
%\textcolor{blue}{The proof of the corollary is omitted due to  space limitations, but it  follows from a direct application of Theorem 5 \cite{cesa2007improved} to SafePredict.} 
To keep the analysis in Section 4 simple, we nevertheless apply the doubling trick to our problem and derive a validity bound having the same order of magnitude as  Corollary 3.5.1. 

%\todo[inline]{here or at the end of the subsection?}

In an iterative fashion, the doubling trick starts with an initial estimate of the unknown quantity and compares it with the observed value of this quantity at each time step. When the measured value exceeds the estimate, the estimate is doubled and the algorithm is reset. 

%We use the doubling trick to choose $\eta$. 
Procedurally, to estimate $V^*$ for a fixed horizon $T$, start with an initial estimate of $V_{est}$ (typically $V_{est}= 1$) and a running sum $V_{sum} = 0$. Then  invoke Theorem 3.1. by replacing $V^*$ with $V_{est} = 1$, i.e., $\eta = \sqrt{{\log \left(1/w_{D,1}\right)}}/{\left(1-\epsilon\right) }$ and run Algorithm 2. At each time $t$  update $V_{sum}$ by incrementing it by $w_{P,t+1}w_{D,t+1}$ and check if it exceeds the current estimate. If it does,  do the following:
\begin{compactenum}% [i.]
\item Double the estimated value $V_{est} \gets 2 V_{est}$.
\item Update the learning rate according to the new $V_{est}$, i.e., $\eta \gets \eta / \sqrt{2}$.
\item Reset the prediction probability $w_{P,t+1} \gets w_{P,1}$.
\item Reset the running sum $V_{sum} \gets 0$. 
\end{compactenum}

The complete pseudo-code for the modified algorithm is given in Algorithm 3.
\begin{algorithm}[!htb]
\caption{ \textbf{SafePredict with Doubling Trick}\\
\textit{Base predictor}: $P$; ~\textit{Initial weight}: $w_{P,1} \in (0,1)$ \\
\textit{Target error rate}: $\epsilon \in (0,1)$}
\begin{algorithmic}[1]
\State Initialize $t = 1$
\For {each $k=1,2,\ldots$}
\State Reset $w_{P,t} = w_{P,1}$, ~ $V_{sum} = 0$, ~ and 
\[\eta = \sqrt{\log(1/w_{D,1})/\left(1-\epsilon \right)^2/2^{k}}\]
\While {$V_{sum} \leq 2^k$}
\State Predict with probability $w_{P,t}$, refuse otherwise,
\[\hat{y}_{t} =   \left\{
\begin{array}{ll}
      \hat{y}_{P,t} & ~~~\textrm{with prob. $w_{P,t}$}  \\
      \varnothing & ~~~\textrm{otherwise} \\
\end{array} 
\right. \]
\State Update the prediction probability:
\begin{eqnarray}
w_{P,t+1} & = & \frac{w_{P,t}e^{-\eta l_{P,t}}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}}, \nonumber \end{eqnarray}
\State Compute $V_{sum} \gets V_{sum} + w_{P,t+1}w_{D,t+1}$
\State Increment $t$ by $1$, i.e., $t \gets t+1$
\EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}


%In the following theorem, we show that for SafePredict with the doubling trick, given in Algorithm 3, has a validity bound that has the same order of magnitude as that presented in Theorem 3.1, i.e., it differs only by a constant multiplicative factor of $\sqrt{2}/(\sqrt{2}-1)$.% \simeq 3.41$.

\begin{theorem} For any $P$, $\epsilon < 1/2$, and $0< w_{P,1} < 1$, SafePredict with the doubling trick given in Algorithm 3 satisfies 
\begin{eqnarray}
\frac{L_{P,T}^* }{T^*} & \leq & \epsilon + \left(1 - \epsilon\right)\frac{2 \sqrt{2}}{\sqrt{2}-1}\frac{\sqrt{\log \left(1/w_{D,1}\right)V^*}}{T^*}. \label{doubling_trick}  \end{eqnarray}
\end{theorem}

\begin{proof}
Denote the time for the $K^{th}$ reset of the algorithm with $T_{K}$, i.e., $T_K$ is the largest $\tau$ such that $\sum_{t=1}^{\tau} w_{P,t} w_{D,t} \leq 2^{K}$. Additionally, assume $T_0 = 0$ and $K^*$ is the integer that satisfies 
$T_{K^*-1} < T \leq T_{K^*} $.

Then, we can rewrite the sum 
\begin{eqnarray}
L_{P,T}^* - \epsilon T^* & = & \sum_{t=1}^T w_{P,t}\left(l_{P,t} - \epsilon\right) \nonumber \\
 &   \leq & \sum_{K=1}^{K^*}\sum_{t=T_{K-1}+1}^{T_K}w_{P,t} \left(l_{P.t} - \epsilon\right). \label{step1}
\end{eqnarray}

Next, we can bound each summand in the RHS using eq. (\ref{valid_guarantee2}) from Theorem 3.1, i.e., for all $K$ we plug the estimated $V_{est} = 2^K$ value instead of $V^*$ in the learning rate and the corresponding bound,
\begin{align}
\sum_{t=T_{K-1}+1}^{T_{K}}w_{P,t} \left(l_{P,t} - \epsilon\right)  & \leq  ~ \left(1-\epsilon\right) 2\sqrt{2^{K} \log \left({1}/{w_{D,1}}\right)}. \label{step2} 
\end{align}
Combining eq. (\ref{step1}) and (\ref{step2}), we obtain
\begin{align}
L_{P,T}^* - \epsilon T^* & \leq ~\left(1-\epsilon\right)2 \sum_{K=1}^{K^*}\sqrt{2^{K} \log \left(1/w_{D,1}\right)}  \nonumber \\
& = ~ \left(1-\epsilon\right)2 \sqrt{2^{K^*} \log \left(1/w_{D,1}\right)}\sum_{K=1}^{K^*} \sqrt{2^{K-K^*}} \nonumber \\
& \leq ~ \left(1-\epsilon\right) \frac{2\sqrt{2}}{\sqrt{2}-1} \sqrt{2^{K^*} \log \left(1/w_{D,1}\right)} \label{a4} \\
& \leq ~ \left(1-\epsilon\right) \frac{2\sqrt{2}}{\sqrt{2}-1} \sqrt{\log \left(1/w_{D,1}\right) V^*} \label{b4} 
\end{align}
where (\ref{a4}) follows from the sum of a geometric series and (\ref{b4}) follows from the definition of $K^*$.

Finally, the desired result is obtained by dividing both sides by $T^*$.
\end{proof}

Both Corollary 3.5.1 and Theorem 3.6 suggest methods to bound the order of excess error rate to the same level ($\sqrt{V^*}/T^*$) as stated in Theorem 3.1 where we assumed the use of an optimal learning rate value for $\eta^*$. %without any prior knowledge about the optimal learning rate $\eta^*$. 



Additionally, even though we decrease the learning rate $\eta$ as $T$ increases, it is always greater than $\eta^*/2$ of Theorem 3.1 and satisfies $\eta T \rightarrow \infty$. Thus, Theorem 3.5 holds for Algorithm 3 using the same arguments in the proof. We omit the details of the proof due to the space restrictions.
%\todo{supplementary?}


\section{Adaptive SafePredict}
We now consider the practical scenario in which the error rate of the base predictor changes over time. Our meta-algorithm should reduce the probability of making a prediction when the base predictor suffers a large error and predict more often when the base predictor does well. Inspired by the Fixed Share algorithm \cite{herbster1998tracking}, we introduce Adaptive SafePredict, a weight-shifting extension to SafePredict. Adaptive SafePredict tracks changes in the error rate of the base predictor while preserving validity, thus improving efficiency even when there are periods of poor predictions.  

The base predictor may endure spikes in its error rate for a variety of reasons. For example, most predictors have a high error rate at the beginning of the prediction task; their error rate decreases as they see more examples and learn from the mistakes. Sometimes, the underlying data distribution may abruptly change, and thus the performance of the base predictor degrades significantly until the predictor learns the new data distribution. Such scenarios might lead to long sequences of bad predictions for the base algorithm $P$, and force the prediction probability to tend to zero. To ensure that the prediction probability does not decrease too quickly due to a long sequence of bad predictions, we shift a small portion of the dummy's  ``weight'' (refusal probability) towards the base predictor. This weight shift allows Adaptive SafePredict to recover quickly when the base predictor performs well again.

%As an example, suppose $P$ has a constant error rate $3\epsilon$ for $t \leq T/2$ and $\epsilon/2$ for $T/2 <t\leq T$. Ideally, we would like  $w_{P,t} = 0$ for $t\leq T/2$ and $w_{P,t}=1$ for $t> T/2$ to achieve efficiency $\rho_T = 1/2$. However, Lemma 3.4 implies the probability of making a prediction decreases quickly till time $T/2$ and reaches $\approx e^{-\eta \epsilon T}$. Even though it starts to increase afterwards, at time $T$ the probability of making a prediction is still bounded by $\approx e^{\eta \left(\epsilon T - L_{P,T}\right) } = e^{-\eta \epsilon 3T /4}$, which is far below the ideal probability of $1$.

Proposals to make generic EWAF adaptive against such changing environments include Chapter 5.2 of \cite{cesa2006prediction}.
A  popular way among these techniques is called "sharing the weights" which leads to the \textit{fixed share algorithm} \cite{herbster1998tracking}. The fixed share algorithm simply adds a mixing step to the weight update rule in the EWAF. In particular, following the notation from Section 2.1, the fixed share update rule becomes
\[w_{P_i,t+1} = \frac{\alpha}{N} + \left(1-\alpha\right)\frac{w_{P_i,t}e^{-\eta l_{i,t}}}{\sum_{j=1}^Nw_{P_j,t}e^{-\eta l_{j,t}}}\]
for some $\alpha \in [0,1)$. 
The mixing step ensures that no weight falls below a predefined value $\alpha/N$, and guarantees a sub-linear regret against roughly $\alpha T$ abrupt changes in the underlying statistics (e.g., the error rate). For a detailed analysis of the fixed share algorithm, please see %the reader 
 \cite{adamskiy2012closer,herbster1998tracking}.

We apply a similar idea to SafePredict by modifying the EWAF update rule eq. (\ref{update_rule}) to guarantee that the prediction probabilities do not get too small or too large. The net result is to track the changes in the error rate efficiently while preserving the validity guarantees established in Section 3.1. To constrain the prediction probability at time $t+1$ to lie within an arbitrary interval $\alpha_t \leq w_{P,t+1} \leq \beta_t$, we  modify our update rule as follows 
\begin{eqnarray}
w_{P,t+1} & = & \alpha_t + \left(\beta_t-\alpha_t \right)\frac{w_{P,t}e^{-\eta l_{P,t}}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}}.
\label{ws_update_rule}
\end{eqnarray}
We call $\alpha_t$ and $\beta_t$ the \textit{adaptivity parameters} and let them change with time for the sake of generality. In Algorithm 4, we give the pseudo-code for Adaptive SafePredict with adaptivity parameters $\alpha_t$ and $\beta_t$.
\begin{algorithm}[!htb]
\caption{ \textbf{Adaptive SafePredict}\\
\textit{Base predictor}: $P$; ~\textit{Initial weight}: $w_{P,1} \in (0,1)$ \\
\textit{Learning rate}: $\eta > 0$; ~ \textit{Target error rate}: $\epsilon \in (0,1)$\\
\textit{Min. prediction prob.}: $\alpha_1,\ldots, \alpha_T\in [0,1)$ \\  \textit{Max. prediction prob.}: $\beta_1, \ldots, \beta_T \in (0,1]$}
\begin{algorithmic}[1]
\For {each $t=1,2,\ldots$}
\State Predict with probability $w_{P,t}$, refuse otherwise, i.e.,
\[\hat{y}_{t} =   \left\{
\begin{array}{ll}
      \hat{y}_{P,t} & ~~~\textrm{with prob. } w_{P,t} \\
      \varnothing & ~~~\textrm{otherwise} \\
\end{array} 
\right. \]
\State Update the prediction probability:
\begin{eqnarray}
w_{P,t+1} & = & \alpha_t + \left(\beta_t-\alpha_t\right)\frac{
w_{P,t}e^{-\eta l_{P,t}} 
}{
w_{P,t}e^{-\eta l_{P,t}} +  w_{D,t}
e^{-\eta\epsilon}} \nonumber
\end{eqnarray}
\EndFor
\end{algorithmic}
\end{algorithm}

A good setting for the adaptivity parameters provides resilience against changes while preserving validity. From our analysis in Section 3.1, we observe that validity is preserved as long as $\alpha_t$ is on the order of $1/T$, regardless of the choice of $\beta_t$. By noting $w_{P,t+1}$ is an increasing function of $\beta_t$, we choose  $\beta_t = 1$ to maximize the efficiency of this adaptive algorithm (Alg. $4$) under this restriction on $\alpha_t$. In particular, we derive an upper bound to the probability of refusal that depends only on the loss sequence of $P$ starting from an arbitrary time point $t_0$, i.e., $L_{P,t,t_0}$ instead of $L_{P,t}$. As a result, efficiency increases whenever $P$ starts to make better predictions after $t_0$.

\subsection{Validity}
To quantify the effect of the adaptivity parameters $\alpha_t, \beta_t$ on our validity guarantees, we first show that Adaptive SafePredict is equivalent to the usual EWAF with a larger set of experts. In particular, we consider a virtual ensemble, where each expert in the ensemble chooses to follow either the dummy predictor $D$, or the base predictor $P$. In the following lemma, we show that for an appropriately chosen set of initial weights, the EWAF on this virtual ensemble (i.e., Algorithm $1$) becomes equivalent to Adaptive SafePredict as outlined in Algorithm $4$. Next, we use this equivalence to extend our analysis from Section $3$.

\begin{lemma}{(Equivalence lemma)}  \label{equivalence}
Suppose we have a base predictor $P$. Consider an ensemble of $2^T$ experts, $\mathcal{P} = \{P_0,P_1,\ldots,P_{2^T-1}\}$, defined as follows:
\begin{compactitem}
\item Denote the $t^{th}$ bit of the binary expansion of integer $i$ with $b_{i,t}$, and define the notation $\bar{x} = 1- x$.
\item Fix the predictions and the losses of each expert $P_i$ as follows:
\[ \hat{y}_{P_i,t} =   \left\{
\begin{array}{ll}
      \varnothing & b_{i,t} = 0  \\
      \hat{y}_{P,t} & b_{i,t} = 1  \\
\end{array} 
\right. \textrm{ and } l_{P_i,t} =   \left\{
\begin{array}{ll}
      \epsilon &  b_{i,t} = 0  \\
      l_{P,t} & b_{i,t} = 1 \\
\end{array} 
\right. .\]
\item Set the initial weights for each expert as
\begin{align*}
w_{P_i,1} ~ =  &   w_{P,1}^{b_{i,1}} w_{D,1}^{\bar{b}_{i,1}} \ldots \\ & \quad \prod_{t=1}^{T-1}  \alpha_t^{\bar{b}_{i,t}{b}_{i,t+1}}\bar{\alpha}_t^{\bar{b}_{i,t}\bar{b}_{i,t+1}}  \beta_t^{{b}_{i,t}{b}_{i,t+1}}\bar{\beta}_t^{{b}_{i,t}\bar{b}_{i,t+1}}.
\end{align*}
\end{compactitem}

Then the EWAF algorithm (Alg. 1) using the expert ensemble $\mathcal{P}$ with the learning rate $\eta$ is equivalent to Adaptive SafePredict (Alg. 4) using the base predictor $P$, in terms of the prediction probability  
\[w_{P,t} = \sum_{i: b_{i,t}=1} w_{P_i,t}.\]
\end{lemma}

\begin{proof} 
%The proof follows by induction over $t$ by  recognizing 
%\begin{align*}
%\sum_{i:b_{i,t}b_{i,t+1}=1}w_{P_i,t} & = ~ \beta_{t} \sum_{i:b_{i,t}=1}w_{P_i,t}, ~\textrm{and}  \\
%\sum_{i:\bar{b}_{i,t}b_{i,t+1}=1}w_{P_i,t} & = ~ \alpha_{t} %\sum\limits_{i:\bar{b}_{i,t}=1}w_{P_i,t}. 
%\end{align*} The details are presented in  Supplementary Material.
The proof is in the Supplementary Material.
\end{proof}

Because Lemma 4.1 reduces the adaptive algorithm to an instance of EWAF, we can obtain the following validity guarantee by modifying the proof of Theorem 3.1.

\begin{corollary} For any $P$, $\eta>0$, $\epsilon < 1/2$, $0< w_{P,1} < 1$, and $0 \leq \alpha_t, \beta_t, \leq 1$, $\forall t$ Adaptive SafePredict meta-algorithm given in Algorithm 4 satisfies 
\begin{eqnarray}
\frac{ L_{P,T}^* }{T^*} & \leq & \epsilon - \frac{\log \left(w_{D,1} \Delta_T\right) }{\eta T^*} + \frac{\left(1 - \epsilon\right)^2\eta V^*}{T^*},
\end{eqnarray}
where  $\Delta_T$ is defined as $\prod_{t=1}^{T-1} \left(1-\alpha_t\right)$.

By choosing the learning rate $\eta$ to minimize the RHS of this bound, we {get}
\begin{eqnarray}
\frac{L_{P,T}^*}{T^*} & \leq & \epsilon + \left(1 - \epsilon\right)\frac{2\sqrt{  \log \left(1/\left(w_{D,1}\Delta_T\right)\right) V^*}}{T^*}  \label{leak_bound}
\end{eqnarray}
for $\eta^* =\frac{\sqrt{{\log \left(1/\left(w_{D,1}\Delta_T\right)\right)}/{V^*}}}{1-\epsilon} $.
\end{corollary}

\begin{proof}
The proof of the corollary follows from the same steps given in the proof of Theorem 3.1, except instead of choosing $P_i = D$ while applying Lemma 3.2 in eq. (\ref{first_step}), we choose $P_i = P_0$ from the equivalent virtual ensemble given in Lemma 4.1. Note that $P_0$ always refuses and is essentially identical to $D$, except its initial weight is 

\vspace{3pt}
$\displaystyle w_{P_0,1} ~=~ w_{D,1} \prod_{t=1}^{T-1} \left(1-\alpha_t\right) ~=~ w_{D,1}\Delta_T.$
\end{proof}

\begin{corollary}
For $\alpha_t = \alpha < 1/2~ \forall t$, the validity bound given in eq. (\ref{leak_bound}) becomes
\begin{eqnarray}
\frac{L_{P,T}^*}{ T^*}   & \leq & \epsilon + \left(1 - \epsilon\right)\frac{2\sqrt{ V^*\left(\log \left( 1/{w_{D,1}}\right) +T \alpha + T\alpha^2\right)}}{T^*}. \nonumber
\end{eqnarray}

Thus setting $\alpha = O\left(1/T\right)$ is a sufficient condition to guarantee the validity of Adaptive SafePredict given in Alg. 4.
\end{corollary}
\begin{proof}
Proof directly follows from setting $\alpha_t = \alpha$ in eq. (\ref{leak_bound}) and using Taylor series expansion of $\Delta_T$,

\vspace{3pt}
%\begin{align*}
$\displaystyle \log \left(\Delta_T\right) ~ = ~ (T-1) \log(1-\alpha) ~ \geq ~ -T \left(\alpha + \alpha^2\right).$
%\end{align*}
\end{proof}

Corollary 4.1.2 implies that by choosing $\alpha_t = \alpha = O\left(1/T\right)$, we can preserve the same convergence rate for the excess error rate from Theorem 3.1, i.e., $L_{P,T}^*/T^* - \epsilon = O\left(\sqrt{V^*}/T^*\right)$. In other words, as long as $\alpha$ is small, the whole effect of the weight shifting on our validity bound can be interpreted as starting with a smaller initial refusal probability, by reducing  $w_{D,1}$ by a multiplicative factor of $\Delta_T \approx e^{\alpha T}$ which is essentially a constant for $\alpha = O\left(1/T\right)$.

Furthermore, note that the bound given in eq. (\ref{leak_bound}) depends only on $\alpha_t$ and is totally agnostic to the choice of $\beta_t$. Therefore, once $\alpha_t$ values are chosen to preserve the validity, i.e., on the order of $1/T$, we are free to choose $\beta_t$ to maximize the prediction probability, and therefore efficiency, by choosing $\beta_t = 1$ at all time points $t$. In the next subsection, we analyze the efficiency of this special case and argue it provides resilience against changes in the data distribution. 

\subsection{Weight-Shifting SafePredict}
%In Section 3.2, we showed that the 	prediction probability of SafePredict increases or decreases exponentially quickly depending on the cumulative loss of the base predictor $P$. As mentioned in the beginning of Section 4, this may cause a high refusal rate when the performance of the base predictor deteriorates abruptly. 
In this section, we exploit a special case of Adaptive SafePredict to show that it provides resilience against changes in the data distribution while preserving the validity of the algorithm. This special case, obtained for $\alpha_t = \alpha = \Theta\left(1/T\right)$ and $\beta_t = 1$, is called \textit{Weight-Shifting SafePredict}.

As motivated by  Corollary 4.1.2, we first set $\alpha_t$ for all $t$ equal to some constant $ \alpha$, where $\alpha$ is on the order of $1/T$. This will  guarantee validity. Next, we choose to maximize $w_{P,t+1}$ over $\beta_t$ in order to maximize the efficiency. Therefore, from eq. (\ref{ws_update_rule}) we obtain $\beta_t = 1,~\forall~t$. Note that this particular choice of adaptivity parameters simplifies the update rule given in eq. (\ref{ws_update_rule}) to
\begin{eqnarray}
w_{P,t+1} & = & \alpha + \left(1-\alpha \right)\frac{w_{P,t}e^{-\eta l_{P,t}}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}}. \label{ws_simplified}
\end{eqnarray}
An intuitive way of looking at this rule is that at each time point we use the EWAF rule first and then shift an $\alpha$ portion of the weight of the dummy to towards the base predictor $P$, thus performing \textit{weight shifting}. 

The following result implies an exponentially diminishing refusal probability in terms of the partial cumulative loss $L_{P,t,t_0}$, for an arbitrary $t_0 < t$, which implies that Weight-Shifting SafePredict can quickly recover to make predictions if the base predictor performs well starting time $t_0$. 

\begin{lemma} The probability of refusing to predict at time $t+1$, $w_{D,t+1}$, by  using the Weight-Shifting SafePredict (Algorithm 4 with $\beta_t = 1$ and $\alpha_t = \alpha$,  $\forall~t$) satisfies the following inequality
\begin{align}
 w_{D,t+1}  \leq  \frac{1-\alpha}{\alpha} e^{ \eta  \left(L_{P,t,t_0} - \epsilon' (t-t_0) \right)} \label{adapt_eff}
\end{align}
for $\epsilon' = \epsilon + \alpha/\eta$.
\end{lemma}

\begin{proof}
First, write the update rule eq. (\ref{ws_simplified}) in terms of the probability of refusal by noting $w_{D,t} = 1- w_{P,t}$
\begin{align}
w_{D,t+1} & = ~ w_{D,t} \left(1-\alpha \right)\frac{e^{-\eta \epsilon}}{w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}e^{-\eta \epsilon}} \nonumber \\ 
 & = ~ w_{D,t} \left(1-\alpha \right)e^{\eta \left(m_t - \epsilon\right)} \label{a5}  \\
& = ~ w_{D,t_0+1} \left(1-\alpha \right)^{t - t_0} e^{\eta \left(\sum_{\tau = t_0+1}^t m_\tau - \epsilon(t-t_0)\right)} \label{b5}  \\
& \leq ~ w_{D,t_0+1}  e^{\eta \left(\sum_{\tau = t_0+1}^t m_\tau - \epsilon'(t-t_0)\right)}. \label{mid_step}
\end{align}
Where (\ref{a5}) follows by replacing the denominator with the definition of mix-loss from Section 3.1, (\ref{b5}) follows by recursing this update rule $t-t_0$ time, and the final step  follows from the inequality $1-\alpha \leq e^{-\alpha}$ for $0\leq \alpha \leq 1 $ and  $\epsilon' = \epsilon + \alpha/\eta$.

By Lemma 4.1, the mix-loss suffered by Algorithm 4 is equal to the one suffered by the EWAF over the virtual ensemble described in the the lemma. Note that we can consider all the virtual experts that follow $P$ from time $t_0+1$ to $t$ as a single super-expert since they suffer the same loss sequence, namely $l_{P,t_0+1}, \ldots, l_{P,t}$, within this interval. By denoting this super expert as $Q$, we can compute its total weight at time $t_0+1$ as
\[w_{Q,t_0+1} = \sum_{i: b_{i,t_0+1}=1}w_{P_i,t_0+1} ~ = ~ w_{P,t_0+1},\]
where equality to $w_{P,t_0+1}$ again follows from the Lemma 4.1. 
Then we can bound the sum in the eq. (\ref{mid_step}) using Lemma 3.2 for virtual expert $Q$, 
\begin{eqnarray}
\sum_{\tau = t_0+1}^t m_\tau & \leq & L_{Q,t,t_0} - \frac{\log (w_{Q,t_0+1})}{\eta} \nonumber \\ & = & L_{P,t,t_0} - \frac{\log (w_{P,t_0+1})}{\eta}. \label{part_mix}
\end{eqnarray}
Finally, we conclude the proof by employing eq. (\ref{part_mix}) in eq. (\ref{mid_step}) and noting $w_{P,t_0+1} \geq \alpha$ and $w_{D,t_0+1} \leq 1-\alpha$, i.e.,
\begin{eqnarray}
w_{D,t+1} 
& \leq & w_{D,t_0+1}  e^{\eta \left(L_{P,t,t_0} - \epsilon'(t-t_0)\right) - \log (w_{P,t_0+1})} \nonumber \\ 
& = & \frac{w_{D,t_0+1}}{w_{P,t_0+1}}  e^{\eta \left(L_{P,t,t_0} - \epsilon'(t-t_0)\right)} \nonumber \\
& \leq & \frac{1-\alpha}{\alpha}  e^{\eta \left(L_{P,t,t_0} - \epsilon'(t-t_0)\right)}. \nonumber
\end{eqnarray}
\end{proof}

We note that the dominant term of the RHS of eq. (\ref{adapt_eff}) is the exponential term since the preceding term $(1-\alpha)/\alpha$ for $\alpha = \Theta\left(1/T\right)$ increases only linearly with $T$. Therefore,  Lemma 4.2 implies that if $P$ starts to do well at time $t_0$, i.e., if its error rate starting from $t_0$ becomes less than the target rate $\epsilon$, the prediction probability will increase to $1$ exponentially fast.

\begin{algorithm}[!htb]
\caption{ \textbf{Weight-Shifting SafePredict 
with Doub. Trick}\\
\textit{Base predictor}: $P$; ~\textit{Initial weight}: $w_{P,1} \in (0,1)$ \\
\textit{Target error rate}: $\epsilon \in (0,1)$; \textit{Adaptivitiy Parameter}: $\alpha \in [0,1)$}
\begin{algorithmic}[1]
\State Initialize $t = 1$
\For {each $k=1,2,\ldots$}
\State Reset $w_{P,t} = w_{P,1}$, ~ $V_{sum} = 0$, ~ and 
\[\eta = \sqrt{-\log\left(w_{D,1}\left(1-\alpha\right)^{T-1}\right)/\left(1-\epsilon \right)^2 / 2^{k}}\]
\While {$V_{sum} \leq 2^k$}
\State Predict with probability $w_{P,t}$, refuse otherwise,
\[\hat{y}_{t} =   \left\{
\begin{array}{ll}
      \hat{y}_{P,t} & ~~~\textrm{with prob. $w_{P,t}$}  \\
      \varnothing & ~~~\textrm{otherwise} \\
\end{array} 
\right. \]
\State Update the prediction probability:
\begin{eqnarray}
w_{P,t+1} & = &  \alpha + \left(1-\alpha\right) \frac{
w_{P,t}e^{-\eta l_{P,t}}}{
w_{P,t}e^{-\eta l_{P,t}} + w_{D,t}
e^{-\eta\epsilon}} \nonumber
\end{eqnarray}
\State Compute $V_{sum} \gets V_{sum} + w_{P,t+1}w_{D,t+1}$
\State Increment $t$ by $1$, i.e., $t \gets t+1$
\EndWhile
\EndFor
\end{algorithmic}
\end{algorithm}

As in Section 3, the proposed learning rates for Adaptive SafePredict and therefore the Weight-Shifting SafePredict depend on $V^*$, and can be estimated using the doubling trick as described in Section 3.3. For the sake of completeness, pseudo-code for the Weight-Shifting SafePredict with the doubling trick is given in Algorithm 5. We can also extend the validity bound given in Corollary 4.1.2 by following the same steps we used in the proof of Theorem 3.6. 

\begin{corollary} For any $P$, $\epsilon < 1/2$, $0< w_{P,1} < 1$, and $0 \leq \alpha < 1$ Weight-Shifting SafePredict with the doubling trick given in Algorithm 5 satisfies 
\begin{eqnarray}
\frac{L_{P,T}^* }{T^*} & \leq & \epsilon + \left(1 - \epsilon\right)\frac{2\sqrt{2 V^*}}{\sqrt{2}-1}\frac{\sqrt{\log \left(1/w_{D,1}\right) + T\alpha + T\alpha^2}}{T^*}. \nonumber \end{eqnarray}

\end{corollary}

Note that for $\alpha = 0$, Algorithm 5 reduces to the original SafePredict (Alg. 3). Increasing $\alpha$, i.e., the adaptivity, increases the efficiency, since we increase the likelihood to make a prediction at each step. Furthermore, validity is guaranteed as long as $\alpha$ is on the order of $1/T$. In the next section, the impact of $\alpha$ is numerically evaluated.

\section{Experiments}

In this section, we investigate the performance of the proposed meta-algorithms on both synthetic and standard machine learning datasets.\footnote{For the sake of reproducibility, the code used to generate our results, tabulated results on the synthetic data, and the experiments on other datasets are provided in the supplementary material.}
 In Section 5.1, we randomly generate loss sequences and verify the validity of our algorithms empirically for various loss statistics and various degrees of adaptivity. The experiments show that the Weight-Shifting SafePredict boosts the number of predictions in changing environments while preserving the validity of the algorithm.

In Section 5.2, we compare SafePredict with popular confidence-based refusal methods on three well-known and varied machine learning datasets, namely, MNIST digit recognition\cite{lecun-mnisthandwrittendigit-2010} (a vision application),
IMDB sentiment analysis \cite{maas-EtAl:2011:ACL-HLT2011} (a natural language problem), and Reuters topic recognition \cite{Reuters21578} (text classification). SafePredict increases the efficiency relative to other refusal mechanisms while guaranteeing validity.

In the following, for the sake of brevity, we refer to Weight-Shifting SafePredict (Alg. 5) as simply SafePredict by noting that $\alpha=0$ corresponds to the original SafePredict (Alg. 3).

\subsection{Synthetic Data}
In this subsection, we generate a binary sequence of loss-values with varying error probabilities. The subsection examines the validity and efficiency of SafePredict. In particular, we restrict the adaptivity parameter of the SafePredict to have the form $\alpha = k/T$, per Corollary 4.1.2, and observe the trade-off in choosing the parameter $k$. %Note that for $\alpha = 0$ the Weight-shifting SafePredict reduces to the original SafePredict (Alg. 3), and remains valid as long as $\alpha =  O\left(1/T\right)$. 
% The experiments generate only the loss sequences for the base predictor, i.e., $l_{P,1}, l_{P,2}, \ldots$ rather than particular data points, because SafePredict uses only the loss values to update the prediction probabilities. %Because SafePredict uses only the loss values to update the prediction probabilities we generate only the loss sequences for the base predictor, i.e., $l_{P,1}, l_{P,2}, \ldots$ rather than particular data points. 
% \textcolor{blue}{The exact numerical results of our experiments are tabulated in Table 1 of the supplementary material.}


\begin{figure}[!h] %[!t]
\centering
\includegraphics[width=\linewidth]{Fig2.png}
%\includegraphics[width=0.92\linewidth]{fig_2__11_.png}
\caption{\textit{Efficiency Experiments on Synthetic Data: The efficiency ($T^*/T$) of SafePredict with respect to increasing choices of $\alpha$. (top) If the base predictor has a constant error rate which is higher than the target, SafePredict almost always refuses. The number of predictions, in this case, increases with $\alpha$. (bottom) On the other hand, when the error rate of the base predictor fluctuates around the target, the efficiency of SafePredict increases as $\alpha$ increases and achieves nearly the same efficiency as the oracle, which predicts if only if $\epsilon_t \leq \epsilon$. So, in all cases, asymptotic validity is preserved.
}}\label{fig_2}
\end{figure}

\textbf{Parameters:} We fix the time horizon $T = 50000$, initial weight $w_{P,1} = 0.5$ and the target error rate $\epsilon = 0.05$. Then we evaluate our results  for $\alpha \in \{ 0, 1/T, 5/T, 10/T\}$. 

\textbf{Data Generation:} 
To evaluate the performance of the meta-algorithm, we assume the existence of a base predictor $P$ with a time-varying error rate, and generate the loss sequence corresponding to its predictions randomly. To model the changes in the error-rate we employ a simple change point model. % \cite{brodsky2013non}. 
The statistical properties of the generated loss sequence $l_{P,1}, \ldots, l_{P,T}$ are characterized by the following three parameters: low error level ($\epsilon_{low}$), high error level ($\epsilon_{hi}$), and the number of changepoints ($numChange$). 
To generate a particular loss sequence, we first split the time horizon into $numChange+1$ non-overlapping, consecutive, equal length blocks. Then we assume the error rate of $P$ to be constant within each block and alternates between $\epsilon_{low}$ and $\epsilon_{hi}$ for consecutive blocks. Formally, we generate each $l_{P,t}$ as an independent Bernoulli random variable as follows:
\[l_{P,t} =   \left\{
\begin{array}{ll}
      1 & ~~~\textrm{with prob. }\epsilon_{t} \\
      0 & ~~~\textrm{with prob. }1-\epsilon_{t} \\
\end{array} 
\right. ,\]
where 
\[\epsilon_{t} =   \left\{
\begin{array}{ll}
      \epsilon_{low} & ~~~\textrm{if } \left\lceil {t(numChange+1)}/{T} \right\rceil \textrm{ is even} \\
      \epsilon_{hi} & ~~~\textrm{otherwise} \\
\end{array} 
\right. .\]

\textbf{Results:} We generate 12 distinct loss sequences with different $numChange$, $\epsilon_{low}$ and $\epsilon_{hi}$ values and evaluate the error rate and efficiency of Algorithm 5 for various values of $\alpha$. The complete numerical results are presented in the supplementary material, but the key observations about the efficiency of SafePredict are summarized in Figures $2$ and $3$. 


As a baseline for comparison, the results of an idealized oracle are also included. We assume the oracle has access to the true error rate of $P$, i.e., $\epsilon_t$, at each time point and decides to predict if and only if $\epsilon_t \leq \epsilon$. In other words, its prediction probability is equal to
\[w_{P,t} =   \left\{
\begin{array}{ll}
      1 & ~~~\textrm{if } \epsilon_t \leq \epsilon \\
      0 & ~~~\textrm{otherwise} \\
\end{array} 
\right. .\]

By contrast, in all our experiments, SafePredict does not know the number or location in time  of the change points. So the oracle enjoys a significant advantage. 

\begin{figure}[!htb] %[!t]
\centering
\includegraphics[width=\linewidth]{Fig3.png}
\caption{\textit{Synthetic Data, Evolution of Efficiency:
Note $\alpha = 0$ corresponds to the original SafePredict (Alg. 3) and has no adaptivity.  For $\alpha>0$, SafePredict can track the change points and boost efficiency. Larger $\alpha$ implies better tracking. 
As the number of change points increases, SafePredict does a poorer job tracking the performance of the base predictor (relative to the oracle that knows the error rate), thus the efficiency drops. All the predictors in the figures are valid.}  
}
\label{fig_3}
\end{figure}



These simulations reveal two main issues:
%\begin{compactenum}
%\item 

\textit{1) Bound on Validity:} Following Corollary 4.1.2, for all $\alpha = O\left(1/T\right)$, the excess error rate is $O\left( {\sqrt{V^*}}/{T^*}\right)$. However, the constants are hidden by the big-oh notation increase with $\alpha$, and become significant when $T^*$ is small. This effect can be observed most prominently in experiments where the error rate of the base algorithm is consistently higher than the target rate. In these cases, the oracle always refuses as it should whereas SafePredict refuses often but not always. Asymptotically, SafePredict is still valid, but its error rate may exceed the target for finite sequences. 
%Further, large values of $\alpha$ lead to a slower convergence of the prediction probability to $0$, so more errors result. (ANIL: We don't really observe this.) 
On the other hand, in the experiments where the base predictor achieves the target for significant periods of time, the excess error rate of SafePredict stays within $7\%$ of the target error rate (below $0.0035$ for $\epsilon = 0.05$) and the efficiency increases with $\alpha$, see Table 1 in Supplementary Material.

%\item 
\textit{2) Efficiency via adaptivity:} As expected from the theoretical analysis in Section 4 and empirically observed in Figure 2, the efficiency of SafePredict increases with $\alpha$. SafePredict performs nearly as well as the oracle, even though the oracle knows the true error probabilities and SafePredict does not. However, as the number of change points increases, SafePredict must refuse more to be able to adapt to the changes, and therefore suffers a drop in efficiency. %This effect is most pronounced when there are $10$ change points and $\epsilon_{low}/\epsilon = 0.9$. Ideally, SafePredict should recognize the drops in the error rate of the base predictor and respond accordingly. 
As can be seen in Figure 3, the efficiency of SafePredict decreases with the number of change points while the tracking ability of SafePredict increases with $\alpha$, sometimes approaching the efficiency achieved by the oracle. 
%\end{compactenum}




\subsection{Real Data}
We now explore the validity and efficiency of SafePredict on the three datasets mentioned above: MNIST, IMDB  and Reuters topic classification with neural nets as the base predictor. The neural nets are implemented using the Keras library %\cite{keras}
in the R programming language.%\cite{R}. 
For a brief description of the datasets and the neural network architectures please refer to Table 1 of the supplementary material. Furthermore, to demonstrate the simplicity and the generality of our method, the supplementary material also includes a Python %\cite{python} 
implementation using a random forest as the base predictor with six datasets from the UCI repository \cite{Lichman:2013} along with both R and Python implementations of our algorithm. 

% Do we REALLY need to cite Keras, R, and Python...?

%\begin{table}[!htbp]\caption{List of Datasets\\ }
%\centering % to have the caption near the table
%\begin{tabular}{r p{5cm} c }
%\toprule
%Not. & Description & $#$ of Classes \\ 
%\toprule
%IMDB   & Sentiment classification & 2 \\  
%Reuters & Topic classification from text &  ? \\   MNIST   & Digit recognition  & 10 \\
%\vspace{0pt} \\
%\bottomrule
%\end{tabular}
%\label{tab:datasets}
%\end{table}




We also compare SafePredict with a natural confidence-based refusal mechanism.  
This method is widely used in practice, e.g.,  \cite{zhang2013vehicle,hanczar2008classification,de2000reject}, and similar methods are used as baselines in the literature, see e.g., \cite{cortes2017line,bartlett2008classification}. Furthermore, one can conveniently make a fair comparison with SafePredict since both are meta-algorithms that can be used on top of (almost) any predictor.
Finally, we investigate a heuristically promising method of combining SafePredict with the confidence-based mechanism to improve efficiency.

%The MNIST dataset consists of $70000$ samples of handwritten digits where each sample is represented by a $784$ dimensional integer vector and labeled with a digit from $0$ to $9$. 

For each of the datasets, we randomly permute the data and choose the first $10000$ data points to use in our experiments. 
Artificial change points are introduced at every $2000$ data points by applying a random label permutation\footnote{For the IMDB dataset, we simply toggled the labels instead of randomly permuting them since there are only two labels.} to  all the data points after the change point, i.e.,  we effectively change the data distribution (the mapping from features to target) at each change point. Finally, we fix the target error rate as $\epsilon = 0.05$ in our experiments.
 
%Random forests are chosen due to their outstanding performance on a very broad set of tasks \cite{fernandez2014we} and robustness to the choice of parameters. We used a Python implementation of Random Forests from the Scikit-learn package \cite{pedregosa2011scikit} with default parameters. In the scope of this experiment, we retrain the random forest once every $100$ new data points in order to mitigate the computational burden.

Neural networks enjoy high predictive accuracy for such high dimensional data. % flexible application  on a very broad set of tasks. 
For the MNIST dataset, we use a simple three-layer feed-forward fully connected multilayer perceptron as on the intensity values of the $784$ gray-tone pixels. For the IMDB and Reuters datasets, we used a word-of-bags representation of each data point, restricting ourselves to the most common $20000$ words in the corpus as the input of the FastText architecture \cite{joulin2016bag}. Please see the supplementary material for the implementation details. In the scope of this experiment, we retrain the base predictor once at every $200$ data points on all the data points observed so far and use its predictions for the next $200$ data points, to track changes in labeling.


The confidence-based refusal method we consider in this paper starts with a base predictor that outputs a confidence score for each prediction, and a refusal threshold. The meta-algorithm decides to refuse if the confidence score does not exceed the threshold value.
In our experiments, we used the maximum probability estimate produced by the base predictor as the confidence score for each prediction.
As in the case of retraining the base predictors, we update the refusal threshold once every $200$ data points. In particular, to update the threshold at time $t$ we re-train the base predictor using the first $t-200$ data points and choose the smallest threshold (i.e., the one refuses the least) that gives an error rate  smaller than $\epsilon$ over the non-refused predictions in the last $200$ data points ($t-200$ to $t-1$).

We show the results using the SafePredict meta-algorithm (Alg. 5) with fixed parameters $\alpha = 0.0005$ ($5/T$) and $w_{P,1} = 0.5$. SafePredict is used on top of the neural nets either by itself or in a pipeline base predictor then confidence-based refusal meta-algorithm then SafePredict. In the latter multi-meta-algorithm scenario, SafePredict uses the losses suffered by the confidence-based algorithm as input. When the confidence-based meta-algorithm refuses to make a prediction for data point at time $t$, SafePredict also refuses to predict and does not update the weights, i.e., ignores the data point at time $t$. 

Finally, we include an ``amnesic adaptive'' version of the combined meta-algorithm and base predictor that considers excessive refusals of SafePredict as a sign that adaptation is needed. To do so, the amnesic adaptive version monitors the average prediction probability of the SafePredict over the predictions made by the base predictor within the last epoch (i.e., $200$ data points). If the average is less than $0.01$ the amnesic adaptive version ignores all training data observed so far, and restart the base predictor (i.e., the neural net and the confidence-based meta-algorithm) using only the most recent $200$ (epoch size) data points. 
%use only the most recent $200$ data points to  points from before the current epoch {\em Anil: how long is that epoch?} while both (i) training the base predictor (e.g., neural net) and (ii) any underlying confidence-based meta-algorithm. 
The evaluation of efficiency ($T^*/T$) and error rate ($L_{P,T}^*/T^*$) versus time is plotted for each of these predictors in Fig. 4, 5, and 6. 


\begin{figure}[!htbp] %[!t]
\centering

%\missingfigure[figwidth=\linewidth]{Place-holder}
%\includegraphics[width=\linewidth]{figure_2000_05_n2.png}
%\includegraphics[width=\linewidth]{fig3_n.png}
%\includegraphics[width=\linewidth]{MNIST_absolute.png}
\includegraphics[width=\linewidth]{Fig4.png}
\caption{\textit{MNIST Dataset: Efficiency is 1.0 for the base predictor but lower for the various refusing meta-algorithms. %All the SafePredict variants fall at or below the target error rate., also the change points are marked with dashed lines. 
However, the base predictor has a poor error rate (way over $\epsilon$). All the SafePredict variants rapidly approach an error rate value below the target error rate $0.05$ as they make predictions. The confidence-based meta-algorithm cannot guarantee asymptotic validity due to the changes in the underlying distribution (marked by vertical dashed lines). Two forms of adaptivity help reduce the number of refusals: weight-shifting especially with a high $\alpha$ value and amnesic adaptivity. Combining both leads to the highest efficiency while preserving validity. }
}
\end{figure}


\begin{figure}[!htbp] %[!t]
\centering

%\missingfigure[figwidth=\linewidth]{Place-holder}
%\includegraphics[width=\linewidth]{figure_2000_05_n2.png}
%\includegraphics[width=\linewidth]{fig3_n.png}
%\includegraphics[width=\linewidth]{MNIST_absolute.png}
\includegraphics[width=\linewidth]{Fig5.png}
\caption{\textit{IMDB Dataset: Similar to Fig. 4, except in this case, the experiment consists of a randomly chosen  10000 data points used from  the IMDB sentiment analysis dataset \cite{maas-EtAl:2011:ACL-HLT2011} instead of MNIST. 
}}
\end{figure}

\begin{figure}[!htbp] %[!t]
\centering

%\missingfigure[figwidth=\linewidth]{Place-holder}
%\includegraphics[width=\linewidth]{figure_2000_05_n2.png}
%\includegraphics[width=\linewidth]{fig3_n.png}
%\includegraphics[width=\linewidth]{MNIST_absolute.png}
\includegraphics[width=\linewidth]{Fig6.png}
\caption{\textit{Reuters Dataset: 
Similar to Fig. 4, except randomly chosen 10000 data points used from  Reuters dataset \cite{Reuters21578} instead of MNIST. Note the error rate for SafePredict (SP) is way above the target error rate for the first $10,000$ points. Ideally, SafePredict should refuse always. In fact, the expected number of predictions ($T^*$) is only $16.44$.
}
}
\end{figure}

Experimental results lead to the following observations:

%\begin{compactenum}%[leftmargin=*]
%\item 
\textit{1) Validity:}  The confidence-based refusal mechanism fails to satisfy the validity requirement of keeping the error rate below $\epsilon$ (top subfigures of Figure 4, 5 and 6). The reason is that confidence-base refusal requires data points to be (at least approximately) exchangeable to achieve the required error guarantee. This assumption fails after the change point. 
On the other hand, SafePredict establishes validity by refusing when the base predictor cannot achieve the error rate without making any assumptions about the data points. Note that for the Reuters dataset (Figure 6), the base predictor never reaches the target error rate $0.05$. Thus, SafePredict refuses to make a prediction almost all the time, $T^* = 16.44$. % achieves correctness guarantees whether combined directly on top of random forests or with confidence-based refusals, because the error guarantee of SafePredict depends simply on the losses and not on the data generation process.


%\item 
\textit{2) Efficiency: } 
 Generally, the confidence-based refusal method has a higher efficiency than SafePredict due to the nature of the refusal strategies (confidence-based methods make stronger (e.g., i.i.d.) assumptions so predict more often, but fail to be valid when assumptions do not hold). %In particular, the confidence-based refusal mechanism uses the estimated confidence scores to determine which predictions are likely to be correct, \textcolor{blue}{but fail to preserve validity after the change point}. On the other hand, SafePredict depends only on the losses suffered by the base predictor and therefore it waits till the base predictor starts to perform well on average. 
However, the discrepancy in the efficiency can be mitigated by employing the three-way pipeline: base predictor then confidence-based mechanism then SafePredict. This method implies a two-layered refusal mechanism, but as we discussed in Section 3.2 and
4.2, the second layer (SafePredict) will seldom refuse as long as the first layer (confidence-based algorithm) has a validity rate as high as the desired correctness rate. As can be seen from Figure 4-6, this method (%denoted by
SP+CBR) combines the best of confidence-based refusals and SafePredict by performing almost as efficiently as confidence-based refusals before the change point and achieving validity throughout.

 
%\item 
\textit{3) Amnesic Adaptivity: } SafePredict following the confidence-based predictor remains valid throughout, but refusals increase after the change point since the confidence-based mechanism is not valid anymore and thus causes excessive errors. In the amnesic adaptive variant, we use the excessive refusals to trigger an update of the base algorithm. Specifically, if the number of data points predicted by the confidence-based predictor but refused by SafePredict is large, the amnesic approach concludes that the confidence-based algorithm is no longer well-calibrated, so earlier data points should be ignored. We denote this adaptive method as ``Amnesic CBR+SP''. As seen in the plots, Amnesic CBR+SP gives the most favorable performance in our experiments by preserving validity thanks to SafePredict and achieving better efficiency after the change point by forcing the confidence-based algorithm to forget early data points.
%\end{compactenum}


\section{Conclusion}
We have introduced a meta-algorithm, SafePredict, that works with any base prediction algorithm (including ensembles of prediction algorithms) and asymptotically guarantees an upper bound on the error rate for non-refused predictions. The error guarantee achieved by SafePredict does not depend on any assumption on the data or the base prediction algorithm. To achieve this, we refined the regret notion from the expert advice framework and recast the exponentially weighted average forecasting algorithm to be used as a method to manage refusals. 

To avoid too many refusals in changing environments, we introduced a weight-shifting heuristic that encourages predictions when  the quality of the base predictor improves. We have also used an amnesic adaptation mechanism to improve versatility in the face of occasional change points.  Our experiments show that these methods ensure validity even in challenging environments and seldom refuse whenever the base predictor achieves a high enough correctness rate.

%Future work includes the investigation of alternative ways of handling changes in the environment to improve the efficiency of our predictors. For example,  amnesic adaptivity as described in Section 5.2 is only one way of using the excessive refusals to detect a change point and adapt accordingly. However, for other type of non-stationarities, e.g., gradually changing environments, alternative methods may be more useful. Exploring such heuristic modifications to SafePredict for particular application areas promises to be a rich direction of research.







% use section* for acknowledgment
\ifCLASSOPTIONcompsoc
  % The Computer Society usually uses the plural form
  \section*{Acknowledgments}
\else
  % regular IEEE prefers the singular form
  \section*{Acknowledgment}
\fi
Work supported in part by NYU Seed Grant, NYU WIRELESS, and the United States National Science Foundation grants CNS-1302336, MCB-1158273, IOS-1339362, and MCB-1412232. This support is greatly appreciated.
We would also like to thank the editor and the reviewers for their suggestions and criticisms.

% 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}
%
% <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)
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{ref}

 \begin{IEEEbiography}[{\includegraphics[width=25mm,height=32mm,clip,keepaspectratio]{anil.jpg}}]{Mustafa A. Kocak}
is a computational biologist in Broad Institute of MIT and Harvard, %Ph.D. candidate at NYU Tandon School of Engineering, with ECE department. 
His research interests include machine learning applications applications, information theory, and bio-statistics. Kocak
received a B.Sc. in electrical engineering  from Bilkent University (Ankara, Turkey) and his Ph.D. from NYU School of Engineering. Contact him at mkocak@broadinstitute.org.
 \end{IEEEbiography}

% % if you will not have a photo at all:
\begin{IEEEbiography}[{\includegraphics[width=25mm,height=32mm,clip,keepaspectratio]{david.jpg}}]{David Ramirez} 
received a B.S. with honors in Engineering Physics from Tecnologico de Monterrey (ITESM), and M.S. and Ph.D. degrees in Electrical and Computer Engineering from Rice University. He is currently a Postdoctoral Researcher at New York University and a Visiting Postdoctoral Researcher at Princeton University. His research interests are in wireless networks, communication theory, \& optimization. 

\end{IEEEbiography}







\begin{IEEEbiography}[{\includegraphics[width=25mm,height=32mm,clip,keepaspectratio]{elza.png}}]{Elza Erkip} received the B.S. degree in Electrical and Electronics Engineering from Middle East Technical University, Ankara, Turkey, and the M.S. and Ph.D. degrees in Electrical Engineering from Stanford University, Stanford, CA, USA. 
Currently, she is an Institute Professor in the Electrical and Computer Engineering Department at New York University Tandon School of Engineering, Brooklyn, NY, USA. 
Her research interests are in information theory, communication theory, and wireless communications.

Dr. Erkip is a member of the Science Academy of Turkey and is among Clarivate Highly Cited Researchers. She received the NSF CAREER award in 2001, the IEEE Communications Society WICE Outstanding Achievement Award in 2016, and the IEEE Communications Society Communication Theory Technical Committee (CTTC) Technical Achievement Award in 2018. Her paper awards include the IEEE Communications Society Stephen O. Rice Paper Prize in 2004,  the IEEE Communications Society Award for Advances in Communication in 2013 and  the IEEE Communications Society Best Tutorial Paper Award in 2019.  She has been a member of the Board of Governors of the IEEE Information Theory Society since 2012 where she was the Society President in 2018.   She was a Distinguished Lecturer of the IEEE Information Theory Society from 2013 to 2014.

%Dr. Erkip has had many editorial and conference organization responsibilities. Some recent ones include Asilomar Conference on Signals, Systems and Computers, MIMO Communications and Signal Processing Track Chair in 2017, IEEE Wireless Communications and Networking Conference Technical Co-Chair in 2017, IEEE Journal on Selected Areas in Communications Guest Editor in 2015, and IEEE International Symposium of Information Theory General Co-Chair in 2013.
\end{IEEEbiography}


\begin{IEEEbiography}[{\includegraphics[width=25mm,height=32mm,clip,keepaspectratio]{dennis.jpg}}]{Dennis E. Shasha}
 is a Julius Silver Professor of Computer Science at the Courant Institute of New York University. His research interests include data science, biological computing, wireless communication and concurrent data structures. Shasha 
received a PhD in applied math from Harvard University. He is an ACM Fellow and the recipient of an INRIA Internaional Chair. He is co-editor in chief of Information Systems, and is or has been the puzzle columnist for several magazines, including CACM and Scientific American. Contact shasha@courant.nyu.edu
\end{IEEEbiography}


% 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}



\end{document}
