The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
134,421 characters
Binary Choice under Asymmetric Loss in a Data-Rich Environment: Theory and an Application to Algorithmic Fairness
\title{Binary Choice under Asymmetric Loss in a Data-Rich Environment:
Theory and an Application to Algorithmic Fairness\footnote{We are grateful to seminar and conference participants at the University of Pennsylvania, Brown University, Universit\'{e} de Montr\'{e}al, National University of Singapore, Singapore Management University, University of Notre Dame, Boston University, HU Berlin, UNC Wilmington, 2022 CEME Conference for Young Econometricians, 2022 AEA/ASSA Annual Meeting, IAAE webinar series, 2021 North American/Asian/China/Australasia/European Meetings of the Econometric Society, Bristol ESG 2021, and the 41st International Symposium on Forecasting for helpful comments.}
}
\author[1]{Andrii Babii\thanks{Department of Economics. Email: [email removed].}}
\author[1]{Xi Chen\thanks{Department of Statistics. Email: [email removed].}}
\author[1]{Eric Ghysels\thanks{Department of Economics and Department of Finance, Kenan-Flagler Business School. Email: [email removed].}}
\author[2]{Rohit Kumar\thanks{HSS, IITD. Email: [email removed].}}
\affil[1]{UNC Chapel Hill}
\affil[2]{IIT Delhi}
\maketitle
\begin{abstract}
We study the binary choice problem in a data-rich environment with asymmetric loss functions. The econometrics literature covers nonparametric binary choice problems but does not offer computationally attractive solutions in data-rich environments. The machine learning literature has many algorithms but is focused mostly on loss functions that are independent of covariates. We show that theoretically valid decisions on binary outcomes with general loss functions can be achieved via a very simple loss-based reweighting of logistic regression or state-of-the-art machine learning techniques. We apply our analysis to algorithmic fairness in pretrial detentions.
\end{abstract}
\keywords{binary outcomes, asymmetric losses, machine learning, cost-sensitive classification, deep learning, boosting, LASSO, pretrial detention.}
\thispagestyle{empty}
\setcounter{page}{0}
\newpage
\section{Introduction}
Many economic decisions are inherently binary. This includes life-changing decisions such as pretrial release, college admission, job hiring, medical testing and treatment---areas increasingly influenced by automated algorithmic processes based on vast data inputs. It also extends to routine tasks such as loan or credit card approvals, fraud detection, or spam filters. The topic has gained interest from a diverse set of fields, ranging from economics and computer science, to machine learning (ML), among others, and depending on the discipline is also known as classification or screening problems.
In this paper, we focus on data-driven binary decision problems characterized as a solution to the following risk-minimization problem:
\begin{equation}\label{eq:decision_problem}
\min_{f:\mathcal{X}\to\{-1,1\}}\ensuremath{\mathbb{E}}_{X,Y}[\ell(f(X),Y,X)],
\end{equation}
where $Y\in\{-1,1\}$ is a binary outcome, $X\in\mathcal{X}\subset\ensuremath{\mathbf{R}}^d$ is a vector of covariates, $f:\mathcal{X}\to\{-1,1\}$ is a binary decision (or prediction) function, $\ell:\{-1,1\}^2\times\mathcal{X}\to\ensuremath{\mathbf{R}}_+$ is a loss function, and the expected value $\ensuremath{\mathbb{E}}_{X,Y}$ is taken with respect to the distribution of $(X,Y)$. The problem in (\ref{eq:decision_problem}) is minimized over all measurable functions of covariates and the loss function $\ell$ describes the asymmetric consequences in different states of the world. For example, pretrial detention decisions may reflect the asymmetric cost of (a) keeping someone wrongly in jail before his/her trial, (b) releasing a recidivist, versus the social benefits of (a) keeping potential recidivists in jail, and (b) releasing non-recidivists who could be productive members of society. In the loan approval application, the losses may depend on loan size and other considerations such as equal credit opportunities.
The importance of asymmetries in economic decision problems has been recognized for a long time; see \cite{granger1969prediction}, \cite{manski1989estimation}, \cite{granger2000economic}, \cite{diebold1996optimal,diebold1997optimal}, \cite{elliott2016economic}, among others. The combination of high-dimensional data and general loss functions in binary decision problems is challenging and not well understood.\footnote{In contrast, the asymmetric decisions in the regression setting can be achieved via quantile regression, see \cite{koenker1978regression}, the asymmetric least-squares, see \cite{newey1987asymmetric}, or more generally with M-estimators based on a suitable asymmetric loss function; see \cite{elliott2016economic}.} Econometricians have studied nonparametric binary choice problems for a long time, but the literature does not offer computationally attractive solutions for high-dimensional datasets. For example, \cite{elliott2013predicting} consider the binary utility maximization problem similar to (\ref{eq:decision_problem}) and propose to solve its empirical counterpart by extending the maximum score estimator of \cite{manski1975maximum}. These examples typically involve \textit{non-smooth} and \textit{non-convex} combinatorial optimization which is known to be NP-hard and, hence, challenging to apply in modern data-rich environments.\footnote{Several efforts have been made to make these problems computationally feasible. For example, \cite{horowitz1992smoothed} proposes to use kernel smoothing which addresses the lack of smoothness, but not the lack of convexity. \cite{florios2008exact} considers the mixed-integer optimization that requires special solvers without guarantees of finding the global optimum.}
In this paper, we formally show that the valid binary decisions corresponding to the problem (\ref{eq:decision_problem}) can be obtained by solving simple weighted logistic regression or more generally weighted machine learning problems including deep learning, boosting, and LASSO, where the weights are computed directly from the loss function. Our approach can be understood as solving a convexified counterpart to the empirical utility maximization problem of \cite{elliott2013predicting} similarly to modern classification methods solving the convexified counterparts to the maximum score estimator of \cite{manski1975maximum}.
The practical implementation of our method is remarkably simple, which is why it can be discussed here. The first ingredient comes from a policy/decision-maker who has to provide a quartet of loss functions pertaining to (a) true positives, denoted by $\ell_{1,1}(x)$, (b) true negatives, $\ell_{-1,-1}(x)$, (c) false positives, $\ell_{-1,1}(x)$, and (d) false negatives, $\ell_{1,-1}(x)$, where we define $\ell_{f,y}(x):=\ell(f,y,x)$. This requires a careful selection of relevant covariates, $x\in\mathcal{X}$, and functional forms describing the economic decision problem. These are usually determined by either a cost/utility function of the social planner (policy/decision-maker), or are obtained through some type of cost-benefit analysis. Given these economic inputs, the task of the econometrician is to compute weights from $\omega(y,x)$ with $y\in\{-1,1\}$ and $x\in\mathcal{X}$ that will be applied to the appropriate classification procedures. We show that this very simple loss-based reweighting leads to valid binary decisions without strong distributional assumptions. In some cases, e.g., for carefully crafted deep learning architectures, these decisions are optimal from the minimax point of view.
Our methodology can incorporate various preferences through the loss function including the treatment of protected groups which is related to the ongoing debate about algorithmic biases. As more and more decisions affecting our daily lives have become digitized and automated by data-driven algorithms, concerns have been raised regarding such biases. The potential for ML algorithmic outcomes to reproduce and reinforce existing discrimination against legally protected groups has been of great concern. Gender and race are two leading examples. \cite{cowgill2019economics} discuss the case of computer scientists at Amazon who developed powerful new technology to screen resumes and discovered the algorithm placed a negative coefficient on terms associated with women and as a result appeared to be amplifying and entrenching male dominance in the technology industry. Another example of gender discrimination is discussed by \cite{datta2015automated} who studied AdFisher, an automated tool that explores how user behaviors, Google's ads, and Ad Settings interact. They found that setting the gender to female resulted in fewer instances of an ad related to high-paying jobs than setting it to male.
Related to our empirical illustration, journalists at the news website ProPublica reported on a commercial software used by judges in Broward County, Florida, that helps to decide whether a person charged with a crime should be released from jail prior to the trial. They have found that the software tool called Correctional Offender Management Profiling for Alternative Sanctions (COMPAS) resulted in a disproportionate number of false positives for African American defendants who were classified as high risk but subsequently not charged with another crime. We apply our covariate-driven classification methods to pretrial decisions with an emphasis on algorithmic fairness and show how these biases can be eliminated naturally when the decision-maker incorporates preferences for false positive mistakes for protected groups.\footnote{It is also worth mentioning that human decision-makers can also be biased. For example, \cite{posner2025judge} reports that large language models tend to rely more on legal arguments than human judges who may be influenced by sympathy and emotions.}
Therefore, we make contributions to different strands of the literature. First, our paper is related to the general social planner setting studied by \cite{rambachan2020economic} as well as the special cases studied by \cite{corbett2017algorithmic} and \cite{kleinberg2018algorithmic}, among others. \cite{rambachan2020economic} argue that the algorithmic fairness constraints can be addressed using the tools of welfare economics, where a social planner has group-specific welfare weights. Our paper adopts the same point of view, but we take a step further showing how to map these welfare functions to the specific ML methods. Note that \cite{corbett2017algorithmic} and \cite{menon2018cost} suggest incorporating fairness constraints in ML algorithms which is equivalent to using the plug-in classifiers, where the fitted probability is compared to race-specific thresholds. \cite{agarwal2018reductions} and \cite{cotter2019two} consider the symmetric classifiers with non-convex fairness constraints which are challenging to use in practice. In contrast, our work focuses on convexified asymmetric classifiers that do not require fitting the conditional probabilities. \cite{kitagawa2023constrained} use convexification techniques similar to ours and show that the standard symmetric binary classification can incorporate various constraints with a Hinge convexifying function. In contrast, our work focuses on incorporating fairness through the loss function similarly to \cite{rambachan2020economic} which can be also done with the logistic and exponential convexifying functions.
Second, our paper is related to the literature on empirical utility and welfare maximization; see \cite{manski2004statistical}, \cite{hirano2009asymptotics}, \cite{bhattacharya2012inferring}, \cite{zhao2012estimating}, \cite{kitagawa2018should}, \cite{athey2021policy}, \cite{mbakop2021model}, \cite{kallus2021more}, \cite{viviano2023fair}, \cite{adjaho2022externally} among others. This literature usually relies on the potential outcomes framework and deals with continuous outcomes. In contrast to this work, we consider the unconstrained asymmetric binary classification. Our paper is also related to \cite{su2021model,su2021utility} who highlights connections between \cite{elliott2013predicting} and the cost-sensitive classification literature. \cite{su2021model} studies the model selection problem for the non-smooth non-convex empirical utility maximization of \cite{elliott2013predicting} while \cite{su2021utility} considers the utility-maximizing nearest neighborhood method. In contrast, our work proposes to solve a convexified problem and establishes the performance guarantee for asymmetric Logit, deep learning, LASSO, and boosting which has not been done in the aforementioned papers.
Regarding deep learning for economic applications, our paper is related to the recent work of \cite{farrell2018deep} who show that under weak assumptions the deep learning estimators of the regression function can achieve sufficiently fast convergence rates for semiparametric inference and establish supporting non-asymptotic results; see also \cite{chen2007sieves} for an earlier review of shallow neural networks and \cite{dell2024deep} for economic applications of deep learning.
Lastly, we also contribute to classification literature in statistics and computer science; see \cite{zhang2004statistical}, \cite{bartlett2006convexity}, \cite{boucheron2005theory}, \cite{koltchinskii2011oracle}, for the theory of symmetric binary classification. The classification with asymmetric losses is also known as cost-sensitive or example-dependent classification and has been developing largely independently from the related econometric literature, e.g.\ see \cite{elkan2001foundations}. While this literature is quite large, few formal results exist justifying proposed methods. For example, \cite{bahnsen2014example} introduces weights in logistic regression heuristically without providing formal justifications that the weights actually correspond to the asymmetric decision problem. Several papers were written subsequently, see \cite{bahnsen2015example}, \cite{Mehta2020deepcatch} and \cite{xia2017cost} among others, mostly with practical computer science applications such as fraud detection, e-commerce, or marketing. There is also a body of literature on classification with imbalanced or corrupted classes, where weighting is also done heuristically to improve the accuracy of a classifier, which can be highly sensitive to over-represented and/or noisy classes; see \cite{ting1998inducing} and \cite{sun2007cost} among others. This literature considers weights that are different from ours, e.g., based on the empirical number of instances in a given class, or proportional to the inverse of expected costs that are simulated with the importance or rejection sampling. \cite{scott2011calibrated,scott2012calibrated}, and \cite{bao2020calibrated} are examples that attempt to deal rigorously with several instances of asymmetric classification problems. Neither of these papers address the problem (\ref{eq:decision_problem}) in full generality studied in our paper. For example, \cite{scott2012calibrated} covers a special case of our problem with \textit{covariate-independent} false positive/negative losses while \cite{scott2011calibrated} focuses on predicting a sign of a real-valued random variable. Moreover, these papers do not provide specific estimators and do not establish the supporting theoretical results. In contrast, our paper shows how the weights coming from the asymmetric loss function can be incorporated in the cost-sensitive asymmetric Logit, deep learning, boosting or LASSO.
The paper is organized as follows. Section \ref{sec:predicting} introduces notation, describes the binary decision problem in terms of risk/payoff, and illustrates a convenient characterization of the optimal binary decision. Examples of several asymmetric binary decision problems are also provided. Section \ref{sec:convexification} covers the main convexification theorem and provides examples of convexifying functions. In Section \ref{sec:riskbounds}, we provide the excess risk bounds for the binary decision rules constructed from the data and discuss several cases, including logistic regression, LASSO, and deep learning. Section~\ref{secapp:MCresults} presents Monte Carlo simulation results. Finally, we provide an empirical application to pretrial detention in Section \ref{sec:empirical} followed by conclusions. The proofs of key results appear in the Appendix, while the Online Appendix provides additional results for boosting, LASSO, and shallow learning as well as the detailed data description for the empirical application.
\section{Binary decisions \label{sec:predicting}}
Let $Y\in\{-1,1\}$ be the target variable and let $X\in\mathcal{X}\subset\ensuremath{\mathbf{R}}^d$ be covariates.\footnote{We use capitals for random variables and lowercase letters for realizations.} A measurable function $f:\mathcal{X}\to\{-1,1\}$ is called the binary decision/choice/prediction. The decision-making process amounts to minimizing a risk function that describes its consequences in different states of the world
\begin{equation*}
\mathcal{R}(f) = \ensuremath{\mathbb{E}}_{X,Y}[\ell(f(X), Y,X)],
\end{equation*}
where $\ell:\{-1,1\}^2\times\mathcal{X}\to\ensuremath{\mathbf{R}}$ is a loss function specified by the decision-maker. Note that the decision $f$ can be random and the expectation is taken with respect to the distribution of $(Y,X)$ only. The loss function can be asymmetric and may also depend on the covariates $X$, which is economically a more realistic scenario faced by the decision-maker than the one provided by the standard classification setting.
\subsection{Some examples}
In the Introduction, we alluded to many examples in economic decision-making. To motivate the first example, we can think of a credit risk application, where with the false negative mistakes ($f(X)=-1$ and $Y=1$) the bank suffers a loss from the borrower's default, while with the false positive mistakes ($f(X)=1$ and $Y=-1$), the bank simply foregoes its potential earnings. Moreover, the size of the loan and other economic factors may determine the loss, see also \cite{lieli2010construction}:
\begin{example}[Lending decisions]\label{ex:lending}
Let $y\in\{-1,1\}$ be the default status ($=1$ if defaulted) and $f\in\{-1,1\}$ be the lending decision ($=-1$ if approved). A lender's loss function is \begin{equation*}
\ell(f,y,s,z) = L(s,z)\ensuremath{\mathds{1}}_{f=-1,y=1} - \Pi(s,z)\ensuremath{\mathds{1}}_{f=-1,y=-1},
\end{equation*}
where $L(s,z)$ and $\Pi(s,z)$ be the loss and the profit functions, $s\geq 0$ is the size of the loan, and $z\in\ensuremath{\mathbf{R}}^{d-1}$ some other economic factors.
\end{example}
As noted in the Introduction, an important policy debate pertains to the fairness and the discrimination bias of machine learning algorithms towards, e.g., low income groups, gender, or race. The following example suggests that the unfair treatment of individuals can be eliminated if the social planner assigns group-specific weights in the loss function, see also \cite{rambachan2020economic}:
\begin{example}[Social planner with a disadvantaged group]\label{ex:fairness}
Let $y\in\{-1,1\}$ be the recidivism status ($=1$ if recidivist) and $f\in\{-1,1\}$ be a binary bail decision ($=-1$ if kept in prison). The social planner's loss function is
\begin{equation*}
\ell(f,y,g) = \psi_g\ensuremath{\mathds{1}}_{f=-1,y=1} + \varphi_g\ensuremath{\mathds{1}}_{f=1,y=-1},
\end{equation*}
where $g\in\{0,1\}$ is a binary indicator of a disadvantaged group, $\psi_g,\varphi_g>0$ are group-specific weights for false negative and false positive mistakes.\footnote{In criminal justice, the algorithm may be perceived as unfair when the false positive rates for African American and white defendants are different. For instance, \cite{larson2016surya} report that the widely used COMPAS software tends to make false positive predictions of the recidivism for African American individuals more frequently compared to white individuals.}
\end{example}
Computer scientists have focused on defining fairness-aware algorithms by imposing restrictions on $f$.\footnote{Alternatively, one could fit two different classifiers for two groups and use the plug-in approach with group-specific cut-off. This is not the route taken in our paper. We provide some comparisons to plug-in classifiers in simulations.} Often a formal criterion of fairness is defined, and a decision rule is developed to satisfy the criterion, e.g., the statistical parity across groups. We follow the economist's arguments that fairness is naturally defined through welfare/losses.
In the remainder of the paper, we will continue to work with settings involving a generic vector of covariates $X\in\ensuremath{\mathbf{R}}^d$ which may contain the binary group membership variable $G\in\{0,1\}$ and some other covariates $Z\in\ensuremath{\mathbf{R}}^{d-1}$. The point worth keeping in mind, however, is that our framework covers much discussed preference-based notions of fairness characterized by general covariate-driven loss functions.
\subsection{Optimal binary decision}
Following the decision-theoretic perspective, we define the optimal binary decision $f^*:\mathcal{X}\to\{-1,1\}$ as a solution to
\begin{equation*}
\inf_{f:\mathcal{X}\to\{-1,1\}}\ensuremath{\mathbb{E}}[\ell(f(X), Y,X)],
\end{equation*}
where the minimization is done over all measurable functions $f:\mathcal{X}\to\{-1,1\}$. We also use $\mathcal{R}^*=\mathcal{R}(f^*)$ to denote the corresponding smallest achievable risk. Note that this framework also covers the utility/welfare maximization problems, in which case, we can define $\ell(f(X), Y,X)=-U(f(X),Y,X)$, where $U(f(x),y,x)$ is a utility/welfare function of a binary decision $f(x)$ when the outcome is $Y=y$ and covariates are $X=x$.
The following proposition provides an alternative convenient for us characterization of the optimal binary decision, also known as the Bayes' decision; see Appendix for a proof.
\begin{proposition}\label{prop:risk_representation}
The optimal binary decision $f^*$ solves
\begin{equation*}
\inf_{f:\mathcal{X}\to \{-1,1\}}\ensuremath{\mathbb{E}}\left[\omega(Y,X)\ensuremath{\mathds{1}}_{-Yf(X)\geq 0}\right]
\end{equation*}
with $\omega(Y,X)\triangleq Ya(X)+b(X)$, $a(x) = \ell_{-1,1}(x)-\ell_{1,1}(x) + \ell_{-1,-1}(x) - \ell_{1,-1}(x)$, $b(x) = \ell_{-1,1}(x) - \ell_{1,1}(x) + \ell_{1,-1}(x) - \ell_{-1,-1}(x)$, and $\ell_{f,y}(x)\triangleq\ell(f,y,x)$.
\end{proposition}
Proposition~\ref{prop:risk_representation} is related to \cite{elliott2013predicting}, but in contrast to their work, it recasts the asymmetric classification problem in a way that is amenable to convexifiction. Note that $a$ can be interpreted as a difference of net losses $\ell_{-1,1}-\ell_{1,1}$ and $\ell_{1,-1}-\ell_{-1,-1}$ from wrong decisions when $Y=1$ and $Y=-1$ respectively. Similarly, $b$ can be interpreted as a sum of two net losses. Proposition~\ref{prop:risk_representation} shows that the optimal binary decision minimizes the objective function involving the indicator function $z\mapsto \ensuremath{\mathds{1}}_{z\geq 0}$, which is discontinuous and not convex. This leads to a difficult NP-hard empirical risk minimization problem
\begin{equation*}
\inf_{f:\mathcal{X}\to\{-1,1\}}\frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\ensuremath{\mathds{1}}_{-Y_if(X_i)\geq 0 }.
\end{equation*}
\section{Convexification \label{sec:convexification}}
\subsection{Convexified excess risk}
The purpose of this section is to convexify the binary decision problem with a generic loss function making it amenable to modern ML algorithms. It is easy to see that the risk function of a binary decision rule $f:\mathcal{X}\to\{-1,1\}$ can be written as
\begin{equation*}
\mathcal{R}(f) = 0.5\ensuremath{\mathbb{E}}\left[\omega(Y,X)\ensuremath{\mathds{1}}_{-Yf(X)\geq 0}\right] + \ensuremath{\mathbb{E}}[d(Y,X)]
\end{equation*}
with $d(y,x) = 0.25(\ell_{1,1}(x) + \ell_{-1,1}(x))(1+y) + 0.25(\ell_{1,-1}(x) + \ell_{-1,-1}(x))(1-y) - 0.25\omega(y,x)$; see the proof of Proposition 2.1 in the Appendix. Replacing the indicator function with a convex function $\phi:\ensuremath{\mathbf{R}}\to\ensuremath{\mathbf{R}}$, we obtain the convexified risk
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) & = 0.5\ensuremath{\mathbb{E}}[\omega(Y,X)\phi(-Yf(X))] + \ensuremath{\mathbb{E}}[d(Y,X)].
\end{aligned}
\end{equation*}
Therefore, minimizing the convexified risk amounts to solving
\begin{equation*}
\inf_{f:\mathcal{X}\to\ensuremath{\mathbf{R}}}\ensuremath{\mathbb{E}}[\omega(Y,X)\phi(-Yf(X))].
\end{equation*}
Let $f^*_\phi$ be a solution to the convexified problem and let $\mathcal{R}^*_\phi = \inf_{f:\mathcal{X}\to\ensuremath{\mathbf{R}}}\mathcal{R}_\phi(f)$ be the optimal convexified risk. Next, we can define the excess convexified risk of a decision $f:\mathcal{X}\to\{-1,1\}$ as
\begin{equation}\label{eq:excess_convex}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* = 0.5\ensuremath{\mathbb{E}}\left[\omega(Y,X)\left(\phi(-Yf(X)) - \phi(-Yf^*_\phi(X))\right)\right].
\end{equation}
The excess convexified risk measures the deviation of the convexified risk of a given decision rule $f:\mathcal{X}\to\{-1,1\}$ from the optimal convexified risk and can be controlled. Unfortunately, the convexified excess risk tells us little about the performance of the binary decision in terms of the actual excess risk that the decision-maker cares about, namely:
\begin{equation*}
\mathcal{R}(f) - \mathcal{R}^* = 0.5\ensuremath{\mathbb{E}}\left[\omega(Y,X)\left(\ensuremath{\mathds{1}}_{-Yf(X)\geq 0} - \ensuremath{\mathds{1}}_{-Yf^*(X)\geq 0}\right)\right].
\end{equation*}
In the following subsection, we show that the excess risk is bounded from above by the convexified excess risk, a result that we refer to as the main convexification theorem.
\subsection{Assumptions and main convexification theorem}
Let $\eta(x)=\Pr(Y=1|X=x)$ be the conditional probability. We impose the following assumption on the conditional probability $\eta$ and the loss function:
\begin{assumption}\label{as:losses}
(i) $\ell_{-1,1}(x)-\ell_{1,1}(x)\geq c_b$ and $\ell_{1,-1}(x)- \ell_{-1,-1}(x)\geq c_b$ a.s.\ over $x\in\mathcal{X}$ for some $c_b>0$; (ii) there exist $\epsilon>0$ such that $\epsilon\leq \eta(x)\leq 1-\epsilon$ a.s.\ over $x\in\mathcal{X}$; (iii) there exists $M<\infty$ such that $|\ell_{f,y}(x)|\leq M$ a.s.\ over $x\in\mathcal{X}$ for all $f,y\in\{-1,1\}$, where $\ell_{f,y}(x)=\ell(f,y,x)$.
\end{assumption}
Assumption~\ref{as:losses} (i) requires that the losses from wrong decisions exceed those of correct decisions. It ensures that weights are $\omega(Y,X)\geq 0$ a.s., so that the convexification is possible (ii) requires that $\eta(x)$ is non-degenerate for almost all states of the world $x\in\mathcal{X}$ and is often imposed in econometrics literature. (iii) requires that the loss function is bounded and is satisfied in our empirical application.
\noindent Next, we restrict the class of convexifying function $\phi$.
\begin{assumption}\label{as:phi}
(i) $\phi:\ensuremath{\mathbf{R}}\to[0,\infty)$ is a convex and nondecreasing function with $\phi(0)=1$; (ii) there exists some $L<\infty$ such that $|\phi(z)-\phi(z')|\leq L|z-z'|$ for all $z,z'$; (iii) there exist $C>0$ and $\gamma\in(0,1]$ such that for all $x,c\in(0,1)$, $\left|x - c\right|\leq C\left(x+c-2xc-\inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y)\right)^\gamma$, where $Q_c(x,y) = x(1-c)\phi(-y)+ (1-x)c\phi(y),x,y\in\ensuremath{\mathbf{R}}$.
\end{assumption}
Assumption~\ref{as:phi} (i) and (ii) are relatively mild restrictions imposed on the convexifying function. (iii) is a technical condition which we verify for the logistic, exponential, and hinge convexifications; see Lemmas~\ref{lemma:logistic}, \ref{lemma:hinge}, and \ref{lemma:exponential} in the Online Appendix. We focus on these three convexifications since they cover the majority of ML algorithms used in practice, including the (penalized) logistic regression, boosting, deep learning, and support vector machines. Note also that Assumption~\ref{as:phi} does not impose any restrictions on the loss function $\ell$.
\noindent We will also use the following covariate-driven threshold rule defined by the asymmetry of the loss function $\ell:$
\begin{equation*}
\label{eq:c-function}
c(x)= \frac{\ell_{1,-1}(x) - \ell_{-1,-1}(x)}{\ell_{-1,1}(x) - \ell_{1,1}(x) +\ell_{1,-1}(x) - \ell_{-1,-1}(x)},
\end{equation*}
where $\ell_{f,y}(x)=\ell(f,y,x)$.
For $z\in\ensuremath{\mathbf{R}}$, put $\ensuremath{\mathrm{sign}}(z)=\ensuremath{\mathds{1}}_{z\geq 0} - \ensuremath{\mathds{1}}_{z<0}$. Our first result establishes the link between the optimal decision $f^*$ and the solution to the convexified risk minimization problem $f^*_\phi.$
\begin{proposition}\label{prop:bayes}
Suppose that Assumption~\ref{as:losses} (i) is satisfied. Then the optimal decision is $f^*(x)=\ensuremath{\mathrm{sign}}(\eta(x)-c(x))$. Moreover, under Assumptions~\ref{as:losses} (ii) and \ref{as:phi} (i) if $\phi$ is differentiable,\footnote{The result also holds for the nondifferentiable hinge function, $\phi(z)=\max\{1+z,0\}$.} then $\ensuremath{\mathrm{sign}}(f^*_\phi(x))=f^*(x)$.
\end{proposition}
\noindent The optimal decision rule $f^*(x)=\ensuremath{\mathrm{sign}}(\eta(x)-c(x))$ is well known, see \cite{elliott2013predicting} and references therein.\footnote{For completeness of presentation, we provide a concise proof in the Online Appendix.} More importantly, Proposition~\ref{prop:bayes} shows that the optimal decision rule for the convexified problem that can be easily solved in practice coincides with $f^*$. The threshold $c(x)$ corresponds to the fraction of net losses from false positives in the total net losses, hence, the decision $f(x)=1$ is made whenever the choice probability $\Pr(Y=1|X=x)$ exceeds the fraction of false positive losses. Note that in the symmetric binary classification case $\ell_{1,-1}(x)=\ell_{-1,1}(x)=1$ and $\ell_{1,1}(x)=\ell_{-1,-1}(x)=0$, so that $c(x)=1/2$ and the optimal decision is $f^*(x)=1$ if $\Pr(Y=1|X=x)$ exceeds $\Pr(Y=0|X=x)$ and $f^*(x)=-1$ otherwise. Interestingly, the optimal decision rules depend on $\eta(x)=\Pr(Y=1|X=x)$, which is related to the heteroskedasticity $\ensuremath{\mathrm{Var}}(Y|X=x)=4\eta(x)(1-\eta(x))$ and all other moments; cf. \cite{diebold1996optimal,diebold1997optimal}.
It is worth mentioning that our starting point is a fixed decision problem described by the loss function $\ell$, which in conjunction with $\eta$ determines the boundary separating the two decisions $\{x\in\mathcal{X}:\; \eta(x)-c(x) = 0 \}$. The following condition generalizes the so-called Tsybakov noise or margin condition, see \cite{boucheron2005theory}, and quantifies the complexity of the decision problem.
\begin{assumption}\label{as:tsybakov}
Suppose that there exist $\alpha\geq 0$ and $C_m>0$ such that
\begin{equation*}
P_X\left(\{x:\; |\eta(x)-c(x)|\leq u\}\right)\leq C_mu^\alpha,\qquad \forall u>0,
\end{equation*}
where $P_X$ is the distribution of $X$.
\end{assumption}
Assumption~\ref{as:tsybakov} describes the complexity of the classification problem around the decision boundary $\{x:\eta(x)=c(x) \}$. If $\alpha=0$, then it does not impose any restrictions as we can always take $C_m=1$, while larger values of $\alpha$ are more advantageous for classification. In the special case of the symmetric binary classification, $c(x)=1/2$, and the extreme case of $\alpha=\infty$ corresponds to $\eta(x)=\Pr(Y=1|X=x)$ being bounded away from $1/2$ which roughly means that there are no observations close to the decision boundary. In this case, we can interpret this as a perfect separation between recidivists and non-recidivists in the space of covariates. We refer to \cite{boucheron2005theory}, Section 5.2, for additional discussion of the margin condition as well as for equivalent formulations in the special case of symmetric binary classification; see also \cite{ponomarev2024lower}.
Our next result relates the convexified excess risk to the excess risk of the binary decision problem a generic loss function under the margin condition.
\begin{theorem}\label{thm:convexified_risk_bound_margin}
Suppose that Assumptions~\ref{as:losses}, \ref{as:phi} (i) and (iii), and \ref{as:tsybakov} are satisfied. Then there exists $C_\phi<\infty$ such that for every measurable function $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \leq C_\phi\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right]^\frac{\gamma(\alpha + 1)}{\gamma\alpha + 1}.
\end{equation*}
\end{theorem}
\noindent The formal proof of this result with the explicit expression for the constant $C_\phi$ appears in the Appendix. It is worth noting that our result nests the symmetric binary classification as a special case; see e.g.\ \cite{zhang2004statistical}, Theorem 2.1. Theorem~\ref{thm:convexified_risk_bound_margin} relates the excess risk of the sign of $f$ to the convexified risk of $f$ (note that the convexified risk is well-defined for arbitrary $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$). Therefore, instead of solving the NP-hard empirical risk minimization problem, we can solve the following weighted classification problem
\begin{equation*}
\inf_{f\in\mathscr{F}}\frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\phi(-Y_if(X_i)),
\end{equation*}
where $\mathscr{F}$ is a class of measurable functions $f:\mathcal{X}\to[-1,1]$, called a soft decision. Note that we restrict the range of the soft decision to $[-1,1]$ since the risk is determined by the sign of $f$ only.
\subsection{Examples}\label{sec:examples}
We consider three examples of convexifying functions widely used in empirical applications. They are the logistic, exponential, and hinge functions. These convexifying functions appear in various ML algorithms including boosting, support vector machines, neural networks, and simple logistic regression; see Figure~\ref{fig:convexifications}. Applying Theorem \ref{thm:convexified_risk_bound_margin} allows us to implement suitably reweighted versions.
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{fig/fig_1.pdf}
\caption{Indicator function with convexifications corresponding to logistic regression (logistic), boosting (exponential), and support vector machines (hinge).}
\label{fig:convexifications}
\end{figure}
\begin{example}[Logistic convexification]
Lemma~\ref{lemma:logistic} in the Online Appendix shows that the function $\phi(z)$ = $\log_2(1 + e^{z})$ satisfies Assumption~\ref{as:phi} with $\gamma=1/2$ and $C=\sqrt{2\log 2}$. The convexified objective is to minimize
\begin{equation}\label{eq:logit}
f\mapsto \frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\log_2\left(1 + e^{-Y_if(X_i)}\right).
\end{equation}
\end{example}
\noindent For the symmetric loss function and linear function class, $f(X_i) = X_i^\top\theta$, the problem in equation~(\ref{eq:logit}) becomes the standard logistic regression. The deep learning consists of minimizing the problem in equation (\ref{eq:logit}) over the class of deep neural networks. Lastly, the state-of-the-art Extreme Gradient Boosting (XGBoost) algorithm of \cite{chen2016xgboost} can be understood as a functional gradient descent algorithm minimizing the problem in equation~(\ref{eq:logit}) with some additional regularization; see also \cite{friedman2001elements}, Ch. 10.
\begin{example}[Exponential convexification]
Lemma~\ref{lemma:exponential} in the Online Appendix shows that $\phi(z)$ = $\exp(z),$ the exponential convexifying function, satisfies Assumption~\ref{as:phi} on compact intervals with $\gamma = 1/2$ and $C = {2}$. The objective is to minimize
$$f\mapsto \frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)e^{-Y_if(X_i)}.$$
\end{example}
For the symmetric loss function, this objective function is usually minimized iteratively in the adaptive boosting (AdaBoost); see also \cite{friedman2001elements}, Ch. 10.
\begin{example}[Hinge convexification]
Lemma~\ref{lemma:hinge} in the Online Appendix shows that $\phi(z)$ = $(1+z)_+$,\footnote{For $a\in\mathbb{R}$, $(a)_+ = \max\{a,0\}$.} the hinge convexifying function, satisfies Assumption~\ref{as:phi} with $\gamma=1$ and $C=1$. The objective is to minimize $$f\mapsto \frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)(1-Y_if(X_i))_+.$$
\end{example}
For the symmetric loss function, this objective function is usually minimized subject to a reproducing kernel Hilbert space constraint within support vector machines; see \cite{friedman2001elements}, Ch. 12.
\section{Excess risk bounds \label{sec:riskbounds}}
The convexified empirical risk minimization problem consists of minimizing the empirical risk
\begin{equation*}
\widehat{\mathcal{R}}_{\phi}(f) = \frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\phi(-Y_if(X_i))
\end{equation*}
over some class of functions $f:\mathcal{X}\to[-1,1]$, denoted $\mathscr{F}_n$. Let $\hat f_n$ be a solution to $\inf_{f\in\mathscr{F}_n}\widehat{\mathcal{R}}_{\phi}(f)$, and let $f_n^*$ be a solution to $\inf_{f\in\mathscr{F}_n}{\mathcal{R}}_{\phi}(f)$. Put also $\|f\|_q = (\ensuremath{\mathbb{E}}|f(X)|^q)^{1/q}$ with $q\geq 1$ and $\|.\|_2=\|.\|$.
The following assumption requires that the risk function is sufficiently curved around the minimizer.
\begin{assumption}\label{as:loss_modulus}
There exist some $c_\phi>0$ and $\kappa\geq 1$ such that for every $f\in\mathscr{F}_n$
\begin{equation*}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* \geq c_\phi\|f-f^*_\phi\|^{2\kappa}.
\end{equation*}
\end{assumption}
\noindent It is worth mentioning that in light of Assumption~\ref{as:losses} imposed on the loss function $\ell$, Assumption~\ref{as:loss_modulus} is mainly about the curvature of the convexifying function $\phi$. In particular, it is typically satisfied with $\kappa=1$ when $\phi''$ is strictly positive, which is the case for the logistic and exponential convexifications; see Lemma~\ref{lemma:curvature_exp_log} in the Online Appendix. On the other hand, it holds with $\kappa=1 + 1/\alpha$ in the hinge case, where $\alpha$ is the margin parameter from the Assumption~\ref{as:tsybakov}; see Lemma~\ref{lemma:curvature_hinge}. It is worth mentioning that the curvature condition in Assumption~\ref{as:loss_modulus} is typically used to establish bounds on $\|f-f_\phi^*\|$ and may not be needed to establish the \textit{slow} convergence rates of the excess risk. However, this condition is typically used to obtain the \textit{fast} convergence rates for the excess risk in the symmetric classification and regression cases; see \cite{koltchinskii2011oracle}.
We first state the oracle inequality for the excess risk in terms of a fixed point of the \textit{local Rademacher complexity} of the class $\mathscr{F}_n$ defined as
\begin{equation*}
\psi_n(\delta;\mathscr{F}_n) \triangleq \ensuremath{\mathbb{E}}\left[\sup_{f\in\mathscr{F}_n:\|f - f^*_n\|^2\leq\delta}|R_n(f - f^*_n)|\right],
\end{equation*}
where $R_n(f-f_n^*) = \frac{1}{n}\sum_{i=1}^n\varepsilon_i(f(X_i)-f_n^*(X_i))$ is a Rademacher process, i.e., $(\varepsilon_i)_{i=1}^n$ are i.i.d. in $\{-1,1\}$ with probabilities $1/2$. An attractive feature of this complexity measure is that it only depends on the local complexity of the parameter space in the neighborhood of the minimizer and provides a sharp description of the learning problem; see \cite{koltchinskii2011oracle}. At the same time, the local Rademacher complexities are general enough to provide a unified theoretical treatment for different methods and can be used to deduce oracle inequalities in many interesting examples. For a function $\psi:\ensuremath{\mathbf{R}}_+\to\ensuremath{\mathbf{R}}_+$, put $\psi^\flat(\sigma) = \sup_{\delta\geq\sigma} [\psi(\delta)/\delta]$ and for a constant $\kappa\geq 1$, put $\psi_\kappa^{\sharp}(\epsilon) = \inf\left\{\sigma>0:\;\sigma^{1/\kappa-1}\psi^\flat(\sigma^{1/\kappa})\leq \epsilon \right\}$. The transform $\psi^\sharp_{\kappa}$ is a generalization of the $\sharp$-transform considered in \cite{koltchinskii2011oracle} and describes the fixed point of the local Rademacher complexity in our setting. The following result holds:\footnote{Proofs for all results in the Appendix.}
\begin{theorem}\label{thm:oracle inequality}
Suppose that Assumptions~\ref{as:losses}, \ref{as:phi}, \ref{as:tsybakov}, and \ref{as:loss_modulus} are satisfied and $(Y_i,X_i)_{i=1}^n$ is an i.i.d. sample. Then there exist constants $c>0,\epsilon>0$ such that for every $t>0$ with probability at least $1-ce^{-t}$
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^* \lesssim \left[\psi_{n,\kappa}^{\sharp}(\epsilon) + \left(\frac{t}{n}\right)^\frac{\kappa}{2\kappa - 1} + \frac{t}{n} + \inf_{f\in\mathscr{F}_n}{\mathcal{R}}_{\phi}(f) - \mathcal{R}_\phi^*\right]^\frac{\gamma(\alpha + 1)}{\gamma\alpha+1}.
\end{equation*}
\end{theorem}
\noindent The proof of this result appears in the Appendix and provides the explicit expression for all constants. Theorem~\ref{thm:oracle inequality} tells us that the accuracy of the binary decision $\ensuremath{\mathrm{sign}}(\hat f_n)$ depends on the fixed point of the local Rademacher complexity of the class, $\psi^\sharp_{n,\kappa}$, and the approximation error to the convexified risk of the optimal decision. In the remaining part of this section, we will specialize this result to parametric decisions and deep neural networks. In each case it can be seen that for a fixed $\epsilon$, we have $\psi_n^\sharp(\varepsilon)\to 0$ as long as $n\to\infty$ and the complexity of the class $\mathcal{F}_n$ does not increase ``too fast". Therefore, Theorem~\ref{thm:oracle inequality} illustrates the variance/bias trade-off, i.e. more complex classes of decision rules reduce the approximation error (bias) at costs of increasing the Rademacher complexity (variance) and vice versa. Note that in the special case when $\kappa=1$, Theorem~\ref{thm:oracle inequality} recovers \cite{koltchinskii2011oracle}, Proposition 4.1. In the following subsections, we illustrate this result for parametric and nonparametric binary decision rules. Additional results on boosting and LASSO are available in the Online Appendix.
\subsection{Parametric decisions and logistic regression \label{sec:param}}
We start with illustrating our risk bounds for parametric binary decision rules. The decision rule is defined $\ensuremath{\mathrm{sign}}(f_{\hat\theta})$ with $\hat\theta$ solving
\begin{equation*}
\inf_{\theta\in\Theta}\frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\phi(-Y_if_\theta(X_i)),
\end{equation*}
where $f_\theta(x)=\sum_{j=1}^p\theta_j\varphi_j(x)$, $\theta\in\Theta\subset\ensuremath{\mathbf{R}}^p$, and $(\varphi_j)_{j\geq 1}$ is a collection of functions in $L_2(P_X)$, called the dictionary. This covers the linear functions $f_\theta(x)=x^\top\theta$ as well as nonlinear functions of covariates provided that the dictionary $(\varphi_j)_{j\geq 1}$ contains nonlinear transformations. The most popular choice of convexifying function is the logistic function $\phi(z)=\log_2(1+e^z)$. More generally, we have the following result for any convexifying function satisfying Assumption~\ref{as:phi}.
\begin{theorem}\label{thm:parametric_predictions}
Under assumptions of Theorem~\ref{thm:oracle inequality}
\begin{equation*}
\ensuremath{\mathbb{E}}\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right] \lesssim \left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + \inf_{f\in\mathscr{F}_n}{\mathcal{R}}_{\phi}(f) - \mathcal{R}_\phi^*\right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1}.
\end{equation*}
\end{theorem}
\noindent It follows from Lemmas~\ref{lemma:logistic}, \ref{lemma:hinge}, \ref{lemma:exponential}, \ref{lemma:curvature_exp_log}, and \ref{lemma:curvature_hinge} that for the logistic and the exponential functions $\gamma=1/2$ and $\kappa=1$ while for the hinge function $\gamma=1$ and $\kappa=1+1/\alpha$. Therefore, in all three cases, for parametric decisions we obtain
\begin{equation*}
\ensuremath{\mathbb{E}}[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*] \lesssim \left(\frac{p}{n}\right)^\frac{1+\alpha}{2+\alpha} + \left[\inf_{f\in\mathscr{F}_n}{\mathcal{R}}_{\phi}(f) - \mathcal{R}_\phi^*\right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1},
\end{equation*}
uniformly over a set of distributions restricted in Theorem~\ref{thm:parametric_predictions}. For a fixed $p$ the convergence rate of the first term can be anywhere between $O(n^{-1/2})$ and $O(n^{-1})$ depending on margin parameter $\alpha$. Since this rate is independent of the convexification, one can use logistic regression reweighted for the asymmetries of the loss function when the signal-to-noise ratio is low and the approximation error is dominated by the first term. Besides simplicity, this choice is also attractive because: 1) the objective function is differentiable; 2) it recovers logistic MLE in the symmetric case; 3) it has a slightly better constant in Theorem~\ref{thm:convexified_risk_bound_margin} than the exponential function. However, from the nonparametric point of view, the choice of the convexifying function is more subtle and the hinge convexification can lead to a better rate of the approximation error as we shall see in the following section.
In the high-dimensional case, when $p$ can be large relative to $n$, we can consider the weighted empirical risk minimization problem with the LASSO penalty
\begin{equation*}
\min_{\theta\in\Theta}\frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)\phi(-Y_if_\theta(X_i)) + \lambda_n|\theta|_1,
\end{equation*}
where $|.|_1$ is the $\ell_1$ norm and $\lambda_n\downarrow 0$ is a tuning parameter. We can deduce from the Online Appendix, Theorem~\ref{thm:lasso} that for the hinge, logistic, and exponential convexifications with probability at least $1-\delta$
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(f_{\hat\theta})) - \mathcal{R}^* \lesssim \left(\frac{s\log(2p)}{n} + \frac{s\log(1/\delta)}{n} \right)^{\frac{\alpha+1}{\alpha+2}} + \left[\mathcal{R}_\phi(f_{\theta^*})-\mathcal{R}_\phi^*
\right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1}.
\end{equation*}
where $s$ is the number of non-zero coefficients in a certain oracle vector $\theta^*\in\ensuremath{\mathbf{R}}^p$. According to this bound: 1) the dimension $p$ may increase exponentially with the sample size if $s$ is small; 2) we can use the logistic convexification in the low signal-to-noise settings, where the approximation error is relatively small.
\subsection{Deep learning \label{sec:deep}}
In this final subsection, we discuss how to construct the asymmetric deep learning architecture and discuss the corresponding risk bounds; see \cite{farrell2018deep} and references therein for more details. The deep learning amounts to fitting a neural network with several hidden layers, also known as a deep neural network. Fitting a deep neural network requires choosing an activation function $\sigma:\ensuremath{\mathbf{R}}\to\ensuremath{\mathbf{R}}$ and a network architecture. We focus on the ReLU activation function, $\sigma(z) = \max\{z,0\}$, which is the most popular choice for deep networks.\footnote{Other activation functions used in the deep learning include: leaky ReLU, $\sigma(z)=\max\{\alpha z,0\},\alpha>0$; exponential linear unit (ELU), $\sigma(z) = \alpha(e^z - 1)\ensuremath{\mathds{1}}_{z<0} + z\ensuremath{\mathds{1}}_{z\geq 0}$; and scaled ELU.}
The architecture consists of $d$ neurons corresponding to covariates $X=(X_1,\dots,X_d)\in\ensuremath{\mathbf{R}}^d$, one output neuron corresponding to the soft prediction $f\in[-1,1]$, and a number of hidden neurons. The final decision is obtained with $\ensuremath{\mathrm{sign}}(f)\in\{-1,1\}$. Hidden neurons are grouped in $L$ layers, known as the \textit{depth} of the network. A hidden neuron $j\geq 1$ in a layer $l\geq 1$ operates as $z\mapsto \sigma(z^\top a_j^{(l)} + b_j^{(l)})$, where $z$ is the output of neurons from the layer $l-1$ and $a_j^{(l)},b_j^{(l)}$ are free parameters. The last layer and the output neuron produce together $z\mapsto \sigma(z + b^{(L)}c(x) + 1) - \sigma(z + b^{(L)}c(x) - 1) - 1\in\ensuremath{\mathbf{R}}$,
where $b^{(L)}$ is the parameter to be estimated and $c(x)$ is a known decision cut-off function. The network architecture $(L,\mathbf{w})$ is described by the number of hidden layers $L$ and a \textit{width} vector $\mathbf{w}=(w_1,\dots,w_{L})$, where $w_{l}$ denotes the number of hidden neurons at a layer $l=1,2,\dots,L$. For completeness, put also $w_0=d$ and $w_{L+1}=2$. Our final deep learning architecture $(L,\mathbf{w})$ is
\begin{equation*}
\begin{aligned}
\mathscr{F}_n^{\rm DNN} & = \left\{x\mapsto \sigma(\theta(x)+c(x)d+1) - \sigma(\theta(x)+c(x)d-1)-1:\; |d|\leq n,\; \theta\in\Theta_n^{\rm DNN}\right\},
\end{aligned}
\end{equation*}
where $\Theta_n^{\rm DNN} = \left\{\theta(x) = A_{L-1}\sigma_{\mathbf{b}_{L-1}}\circ \dots \circ A_1\sigma_{\mathbf{b}_1}\circ A_0x:\; \|\theta\|_\infty\leq F \right\}$,
each $A_l$ is $w_{l+1}\times w_{l}$ matrix of network weights and for two vectors $y=(y_1,\dots,y_r)$ and $\mathbf{b}=(b_1,\dots,b_r)$ (a bias vector), we put $\sigma_{\mathbf{b}}\circ y = (\sigma(y_1 + b_1), \dots,\sigma(y_r + b_r))^\top$. Our deep learning architecture can be arranged on a graph presented in Figure~\ref{fig:network}. Note that the asymmetries of the loss function are incorporated in the neural network architecture via the orange neuron which is fed directly to the last layer consisting of 2 ReLU neurons. Interestingly, this additional connection can be obtained using the so-called ``residual connection" which is also often used in Transformer models, such as ChatGPT and AlphaFold, cf. \cite{targ2016resnet}.
\begin{figure}[htp]
\centering
\resizebox{0.7\textwidth}{!}{
\begin{tikzpicture}[x=1.5cm, y=1.5cm]
\tikzset{
neuron/.style={
circle,
minimum size=0.9cm},
}
\foreach \m [count=\y] in {1,2,3,4}
\node [neuron, fill=teal!50] (input-\m) at (0,3-\y) {$X_\m$};
\foreach \m [count=\y] in {1,2,3,4}
\node [neuron, fill=blue!30] (hidden1-\m) at (2,3-\y) {$\sigma$};
\foreach \m [count=\y] in {1,2,3}
\node [neuron, fill=blue!30] (hidden2-\m) at (4,2.5-\y) {$\sigma$};
\foreach \m [count=\y] in {1,2,3,4,5}
\node [neuron, fill=blue!30] (hidden3-\m) at (6,3.5-\y) {$\sigma$};
\foreach \m [count=\y] in {1,2}
\node [neuron, fill=violet!40] (relu-\m) at (8,2-\y) {$\sigma$};
\foreach \m [count=\y] in {1}
\node [neuron, fill=red!60] (output-\m) at (10,1.5-\y) {$\hat f_n$};
\node [neuron, fill=orange!50] (c) at (2.2,-2.4) {$c$};
\foreach \i in {1,2,3,4}
\draw [gray, ->] (input-\i) -- (c);
\foreach \i in {1,2,3,4}
\foreach \j in {1,...,4}
\draw [gray, ->] (input-\i) -- (hidden1-\j);
\foreach \i in {1,2,3,4}
\foreach \j in {1,2,3}
\draw [gray, ->] (hidden1-\i) -- (hidden2-\j);
\foreach \i in {1,2,3}
\foreach \j in {1,...,5}
\draw [gray, ->] (hidden2-\i) -- (hidden3-\j);
\foreach \i in {1,...,5}
\foreach \j in {1,2}
\draw [gray, ->] (hidden3-\i) -- (relu-\j);
\foreach \i in {1,2}
\foreach \j in {1}
\draw [gray, ->] (relu-\i) -- (output-\j);
\foreach \i in {1,2}
\draw [gray, ->] (c) -- (relu-\i);
\foreach \l [count=\x from 0] in {Input, Layer 1, Layer 2, Layer 3, 2 ReLU, Output}
\node [align=center, above] at (\x*2,3) {\l };
\end{tikzpicture}}
\caption{Directed graph of our deep learning architecture with $d=4$ covariates, $L=3$ hidden layers of width $\mathbf{w}=(4,3,5)$ neurons, and 2 outer ReLU neurons. The orange neuron takes covariates $X\in\ensuremath{\mathbf{R}}^d$ as an input and produces $c(X)\in\ensuremath{\mathbf{R}}$, which is fed directly into 2 ReLU neurons.}
\label{fig:network}
\end{figure}
The following assumption restricts the smoothness of the conditional probability and imposes some assumptions on how the network architecture should scale with the sample size. For simplicity, we define the width of the network as the maximum width across all layers and denote it as $W_n = \max_{0\leq l\leq L}w_l$.
\begin{assumption}\label{as:deep_learning}
(i) $\eta\in W^{\beta,\infty}_R[0,1]^d$ for some $R>0$ and $\beta\in\ensuremath{\mathbf{N}}$; (ii) the neural network architecture is such that the depth is $L_n \leq C_LK_n\log K_n$ and the width is $W_n \leq C_WJ_n\log J_n$, for some $C_L,C_W>0$ and some $J_n\leq n^a$ and $K_n\leq n^b$ with $J_nK_n\leq \left(n/\log^6n\right)^{d/(2\beta(2+\alpha) + 2d)}$ for some $a,b\geq 0$.
\end{assumption}
\noindent It is worth mentioning that we allow for neural networks, where the product of the width and the depth increase at the rate specified in Assumption~\ref{as:deep_learning} (ii). Let $\mathscr{F}_n^{\rm DNN}$ be a set of neural networks with the architecture satisfying Assumption~\ref{as:deep_learning}, where weights and biases $\{A_0,A_l,b_l,l=1,\dots,L \}$ are allowed to take arbitrary real values.
The soft deep learning decision $\hat f_n$ is a solution to the empirical risk minimization problem with the hinge convexification
\begin{equation*}
\inf_{f \in \mathscr{F}_n^{\rm DNN}} \frac{1}{n}\sum_{i=1}^n\omega(Y_i,X_i)(1-Y_if(X_i))_+.
\end{equation*}
The following result holds for the binary decision estimated with the deep learning.
\begin{theorem}\label{thm:oracle inequality_dnn}
Suppose that $(Y_i,X_i)_{i=1}^n$ is an i.i.d. sample from a distribution satisfying Assumptions~\ref{as:losses}, \ref{as:phi}, \ref{as:tsybakov}, and \ref{as:deep_learning} with fixed constants, and denoted $\mathcal{P}(\alpha,\beta)$. Then
\begin{equation*}
\sup_{P\in\mathcal{P}(\alpha,\beta)}\ensuremath{\mathbb{E}}_P\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right] \lesssim \left(\frac{\log^6n}{n}\right)^{\frac{(1+\alpha)\beta}{(2+\alpha)\beta + d}}.
\end{equation*}
\end{theorem}
Note that in the special case of symmetric binary classification this result recovers the convergence rate recently obtained in \cite{kim2021fast}, Theorem 3.3, who in turn assume that the weights are bounded and allow for very slowly diverging depth of order $L_n = O(\log n)$. In particular, this rate matches the minimax lower bound up to the $\log n$ factor; see \cite{audibert2007fast}.
\section{Monte Carlo Simulations \label{secapp:MCresults}}
Anticipating the empirical application to the economic prediction of recidivism, we report on a simulation study pertaining to pretrial detention decisions. As explained in the next section, we present a design pertaining to judges who need to decide whether to release an offender, facing the possibility that the defendant might commit other crimes versus keeping in jail a defendant who would obey the law and the terms of the release. A first subsection describes the design and the second the simulation results.
\subsection{Simulation design \label{subsec:MCdesign}}
There are two groups, $G=0$ and 1, with one group assumed to be a protected segment of the population. We set $Y=-1$ if the person does not commit a crime upon pretrial release, and $Y=1$ otherwise. This is a much-studied topic and we approach it from a social planner point of view using a simplified stylized example with a loss function taken from Example~\ref{ex:fairness}:
\begin{center}
\begin{tabular}{lcccccc}
& \multicolumn{2}{c}{G = 0} & & & \multicolumn{2}{c}{G = 1} \\
& & & & & & \\
& $f(0,z) = 1$ & $f(0,z) = -1$ & & & $f(1,z) = 1$ & $f(1,z) = -1$ \\
& & & & & & \\
$Y = 1$ & $0$ & $\psi_0$ & & & $0$ & $\psi_1$ \\
& & & & & & \\
$Y=-1$ & $\varphi_0$ & $0$ & & & $\varphi_1$ & $0$ \\
\end{tabular}
\end{center}
\bigskip
\noindent where $z$ is a vector of observable characteristics and $\psi_g,\varphi_g>0$ for $g\in\{0,1\}$. From the above, we do not suffer any losses (or gains) when a defendant being released becomes a productive member of society or when a defendant who would commit another crime is kept in jail.
\medskip
Keeping someone in jail who does not intend to commit another crime comes with costs $\varphi_g$ depending on the group membership $g\in \{0,1\}$. If $\varphi_1>\varphi_0$, then the cost of keeping an individual in jail who does not intend to commit another crime is higher if that individual is in group $g=1$. Similarly, releasing a recidivist comes with costs $\psi_g,g\in\{0,1\}$, so that if $\psi_1\ne \psi_0$, the costs of releasing a recidivist are different for the protected group and everyone else.\footnote{It is worth mentioning that in credit risk applications, the bank might care more about the false negative mistakes (failing to predict defaults), while the social planner might be more concerned with the false positive mistakes (failing to predict that the loan will be repaid) and equal credit opportunities regardless of the group membership. Since our general framework can be applied to different binary prediction problems in economics, in this simulation study, we will look at how both mistakes change with $\varphi_g$ and $\psi_g$ for $g\in\{0,1\}$.}
\medskip
\noindent According to equation (\ref{eq:c-function}), the threshold between the two binary decisions is:
\begin{equation*}
c(g,z) = \frac{\varphi_g}{\varphi_g + \psi_g},\qquad g\in\{0,1\}
\end{equation*}
and according to Proposition~\ref{prop:bayes} the optimal decision rule is
$f^*(g,z)$ = $\ensuremath{\mathrm{sign}}(\eta(g,z) - c(g,z))$ with $\eta(g,z)=\Pr(Y=1|G=g,Z=z)$.
Note also that $a(g,z)=\psi_g - \varphi_g$ and $b(g,z)=-(\psi_g + \varphi_g)$.
The design of the data generating process is
\begin{equation*}
Y = 2\ensuremath{\mathds{1}}_{G + Z^\top\gamma + \tau\left(\frac{1}{d}\sum_{j=1}^dZ_j^2 + 2Z_1\sum_{j=2}^dZ_j\right) \geq \sigma\varepsilon } - 1,
\end{equation*}
where $\varepsilon\sim N(0,1)$, $G\sim \mathrm{Bernoulli}(\rho)$, and $Z_1,\dots,Z_d\sim_{i.i.d.} N(0,1)$. Therefore, the protected segment is a fraction $\rho$ of the population (determined by the Bernoulli distribution parameter) and the conditional probability is
\begin{equation}\label{eq:simrisk}
\begin{aligned}
\eta(g,z) & = \Pr(Y=1|G=g,Z=z) \\
& = \Phi_\sigma\left(G + Z^\top\gamma + \tau\left(\frac{1}{d}\sum_{j=1}^dZ_j^2 + 2Z_1\sum_{j=2}^dZ_j\right)\right),
\end{aligned}
\end{equation}
where $\Phi_\sigma$ is the CDF of $N(0,\sigma^2)$. Note that the DGP may feature a very simple example of nonlinearities with quadratic terms and interactions involving $Z_1.$ In addition, the DGP covers the linear model with $\tau = 0.$ Lastly, we also set $\gamma = (1,0.9,0.8,0,0,\dots,0)^\top$ and the dimension $d$ of covariates $Z$ is set to 15.
\medskip
Let $(Y_i,G_i,Z_i)_{i=1}^n$ be i.i.d.\ draws of $(Y,G,Z)$. To evaluate the performance of our approach, we split the sample into the training or estimation sample $(Y_i,G_i,Z_i)_{i=1}^{n_e}$ and the test sample $(Y_i,G_i,Z_i)_{i=n_e+1}^n$. For parametric predictions, we estimate the decision rule solving the weighted logistic regression over the class of linear functions $\{(g,z)\mapsto \theta_0 + \theta_1g + z^\top\gamma:\;\theta_0,\theta_1\in\ensuremath{\mathbf{R}},\;\gamma\in\ensuremath{\mathbf{R}}^{d} \}$. Note that according to our theory if $\tau=0$, then the weighted linear logistic regression provides valid binary predictions even if the choice probabilities are not logistic, cf.\ equation (\ref{eq:simrisk}). However, since in practice we typically do not know the parametric class that can capture all the relevant nonlinearities (i.e., that $\tau\ne 0$), we would often estimate the linear prediction rule
\begin{equation*}
\min_{(c,\gamma)\in\ensuremath{\mathbf{R}}^{1+d}}\frac{1}{n_e}\sum_{i=1}^{n_e}(Y_i(\psi_{G_i}-\varphi_{G_i}) + (\psi_{G_i}+\varphi_{G_i}))\log\left(1+e^{-Y_i(\theta_0 + \theta_1G + Z_i^\top\gamma)}\right).
\end{equation*}
Then the estimated prediction rule is $(g,z)\mapsto \ensuremath{\mathrm{sign}}(\hat \theta_0 + \hat\theta_1g + z^\top\hat\gamma)$, where $(\hat \theta_0,\hat\theta_1,\hat\gamma)$ are estimated above, and the binary predictions evaluated on the test sample are
\begin{equation*}
\ensuremath{\mathrm{sign}}(\hat \theta_0 + \hat\theta_1G_i + Z_i^\top\hat\gamma),\qquad i=n_e+1,\dots,n.
\end{equation*}
To obtain binary predictions with neural networks, we solve
\begin{equation*}
\min_{f\in\mathscr{F}_n^{\rm NN}}\frac{1}{n_e}\sum_{i=1}^{n_e}(Y_i(\psi_{G_i}-\varphi_{G_i}) + (\psi_{G_i}+\varphi_{G_i}))(1-Y_if(G_i,Z_i))_+,
\end{equation*}
where $\mathscr{F}_n^{\rm NN}$ is a relevant neural network class, see Figure~\ref{fig:network} and \cite{targ2016resnet}. Then the estimated prediction rule is $z\mapsto \ensuremath{\mathrm{sign}}(\hat f(z))$, and the binary predictions evaluated on the test data are
\begin{equation*}
\ensuremath{\mathrm{sign}}(\hat f(Z_i)),\qquad i=n_e+1,\dots,n.
\end{equation*}
We set the sample sizes $n$ = 1,000 and 10,000 with 30\% set aside as a test sample in the simulations. To benchmark our asymmetric binary choice approach, we focus first on the unweighted approach with logistic regression, gradient-boosted trees, shallow and deep learning, and support vector machines. For each method, we compute the group-specific false positive (FP) and false negative (FN) by mistakes estimating:
\begin{equation*}
\begin{aligned}
{\rm FP}_g & = \Pr(\ensuremath{\mathrm{sign}}(\hat f(X))=1|Y=-1,G=g), \\
{\rm FN}_g & = \Pr(\ensuremath{\mathrm{sign}}(\hat f(X))=-1|Y=1,G=g),
\end{aligned}
\end{equation*}
for $g\in\{0,1\}$ on the test sample. We also compute the total misclassification error by estimating
\begin{equation*}
{\rm Error} = \Pr(\ensuremath{\mathrm{sign}}(\hat f(X))\ne Y)
\end{equation*}
on the test sample. We use the TensorFlow, scikit-learn, and XGBoost packages in Python to implement the machine learning methods and consider simple linear Logit, Logit with quadratic polynomial features and LASSO, XGBoost, support vector machines, as well as shallow and deep learning.
\smallskip
The tuning parameters are computed using $5$-fold cross-validation, including the LASSO penalty, the SVM penalty, and the number of trees. All other parameters are kept at their default values in the XGBoost package. We also use the radial basis function and the default value of the scaling parameter in the scikit-learn package. The neural networks have a width of 15 neurons and all other parameters are set at their default values (batch size, number of epochs, etc.); i.e. we do not use additional regularization ($\ell_1$/$\ell_2$ or dropout). For shallow learning, we use the sigmoid activation function. The deep ReLU neural network has 5 hidden layers.
\smallskip
The simulation results appear in Table~\ref{tab:MCresults_mistakes}. We find that in terms of the total misclassification error, the ML methods outperform logistic regression in the nonlinear DGP case (except for shallow learning). The best performance is achieved by LASSO with nonlinearities with boosting and support vector machines coming in second. Importantly, we observe a disproportionate number of false positive and false negative mistakes across the two groups in many cases.
\begin{table}[H]
\caption{\label{tab:MCresults_mistakes} Monte Carlo Simulation Results: symmetric classification}
\rule[0mm]{0mm}{5mm}\noindent\footnotesize{\footnotesize
The Monte Carlo simulation design is presented in Section \ref{subsec:MCdesign}, which represents a stylized social planner facing a disproportionate number of false positive and false negative mistakes across the two groups with the standard ML classification approach. The population consists of two groups, $G$ = 0 and 1. Constituents of a group $G$ = 1 are a fraction $\rho.$ The dimension $d$ of covariates $Z$ is set to $15$ and the scale parameter is $\sigma=0.1$. FP and FN are false positive and false negative mistakes computed as a share in the corresponding group, Total = misclassification rate. Logit = logistic regression, GB = Gradient Boosted trees, SL = shallow learning, DL = deep learning, SVM = support vector machines. The results for $n=1,000$ are based on $5,000$ MC experiments. For $n=10,000$, we reduce the number of MC experiments to $1,000$ due to computational constraints.}
{\scriptsize
\begin{ctabular}{lccccccccccccc}
& &\multicolumn{6}{c}{Nonlinear DGP: $\tau = 1$} & \multicolumn{6}{c}{Linear DGP: $\tau=0$} \\
& &\multicolumn{3}{c}{$\rho=0.2$} & \multicolumn{3}{c}{$\rho = 0.5$} & \multicolumn{3}{c}{$\rho=0.2$} & \multicolumn{3}{c}{$\rho=0.5$} \\
& G& FP & FN & Error & FP & FN & Error & FP & FN & Error & FP & FN & Error \\
& & & & & & & & \\
& \multicolumn{13}{c}{Sample size $n$ = 10,000} \\
& & & & & & & & \\
Logit & 0 & 0.51 & 0.22 & 0.34 & 0.52 & 0.22 & 0.33 & 0.11 & 0.11 & 0.11 & 0.11 & 0.11 & 0.11 \\
& 1 & 0.71 & 0.11 & & 0.72 & 0.10 & & 0.16 & 0.08 & & 0.16 & 0.08 & \\
LASSO & 0 & 0.12 & 0.05 & 0.08 & 0.16 & 0.03 & 0.08 & 0.13 & 0.10 & 0.12 & 0.19 & 0.06 & 0.12 \\
& 1 & 0.04 & 0.11 & & 0.06 & 0.08 & & 0.04 & 0.21 & & 0.07 & 0.15 & \\
XGB & 0 & 0.16 & 0.10 & 0.12 & 0.17 & 0.10 & 0.12 & 0.13 & 0.12 & 0.13 & 0.14 & 0.12 & 0.12 \\
& 1 & 0.20 & 0.08 & & 0.20 & 0.07 & & 0.16 & 0.10 & & 0.16 & 0.10 & \\
SVM & 0 & 0.14 & 0.08 & 0.10 & 0.14 & 0.08 & 0.10 & 0.13 & 0.10 & 0.12 & 0.14 & 0.09 & 0.11 \\
& 1 & 0.17 & 0.06 & & 0.17 & 0.05 & & 0.12 & 0.11 & & 0.15 & 0.08 & \\
SL & 0 & 0.24 & 0.07 & 0.14 & 0.25 & 0.07 & 0.13 & 0.15 & 0.11 & 0.13 & 0.15 & 0.11 & 0.12 \\
& 1 & 0.25 & 0.05 & & 0.26 & 0.05 & & 0.19 & 0.08 & & 0.19 & 0.07 & \\
DL & 0 & 0.18 & 0.07 & 0.12 & 0.20 & 0.07 & 0.12 & 0.15 & 0.12 & 0.13 & 0.15 & 0.12 & 0.13 \\
& 1 & 0.19 & 0.06 & & 0.21 & 0.05 & & 0.19 & 0.09 & & 0.19 & 0.09 & \\
& & & & & & & & \\
& \multicolumn{13}{c}{Sample size $n$ = 1,000} \\
& & & & & & & \\
Logit & 0 & 0.51 & 0.24 & 0.35 & 0.52 & 0.24 & 0.34 & 0.12 & 0.12 & 0.12 & 0.12 & 0.12 & 0.12 \\
& 1 & 0.69 & 0.13 & & 0.70 & 0.13 & & 0.17 & 0.08 & & 0.16 & 0.08 & \\
LASSO & 0 & 0.17 & 0.07 & 0.11 & 0.22 & 0.05 & 0.12 & 0.14 & 0.10 & 0.13 & 0.19 & 0.07 & 0.13 \\
& 1 & 0.09 & 0.13 & & 0.13 & 0.10 & & 0.05 & 0.21 & & 0.08 & 0.16 & \\
XGB & 0 & 0.30 & 0.16 & 0.22 & 0.32 & 0.15 & 0.22 & 0.16 & 0.13 & 0.14 & 0.18 & 0.12 & 0.14 \\
& 1 & 0.32 & 0.15 & & 0.35 & 0.13 & & 0.14 & 0.15 & & 0.17 & 0.12 & \\
SVM & 0 & 0.26 & 0.15 & 0.20 & 0.27 & 0.15 & 0.19 & 0.16 & 0.11 & 0.14 & 0.19 & 0.09 & 0.13 \\
& 1 & 0.31 & 0.12 & & 0.32 & 0.11 & & 0.12 & 0.14 & & 0.18 & 0.10 & \\
SL & 0 & 0.73 & 0.10 & 0.36 & 0.79 & 0.07 & 0.35 & 0.17 & 0.12 & 0.14 & 0.21 & 0.09 & 0.14 \\
& 1 & 0.77 & 0.07 & & 0.82 & 0.05 & & 0.19 & 0.10 & & 0.23 & 0.08 & \\
DL & 0 & 0.42 & 0.18 & 0.27 & 0.45 & 0.16 & 0.27 & 0.19 & 0.15 & 0.17 & 0.21 & 0.13 & 0.16 \\
& 1 & 0.45 & 0.15 & & 0.48 & 0.13 & & 0.20 & 0.13 & & 0.22 & 0.12 & \\
\end{ctabular}}
\end{table}
\smallskip
Next, we investigate whether group-specific misclassification rates can be equalized across the two groups with weighted Logit and Boosting. For simplicity, we focus on the setting with $\tau=0$, $\rho=0.2$, and $n=1,000$, as in this case, we observe a disproportionate number of FP and FN across the two groups. Note that in this case Logit has larger FP rates for group $G=1$ while Boosting for group $G=0$. Figure~\ref{fig:fp_fn} shows that the asymmetric weighted logistic regression can equalize the FP probabilities across the two groups at $\varphi_1\approx 1.6$ and FN probabilities across the two groups for $\psi_0\approx 1.6$. Note that equalizing the FP probabilities comes with the increase in FN probabilities in the group $G=1$ and equalizing the FN probabilities comes with the increase in the FP probabilities in the group $G=0$. Therefore, the decision-maker or the social planner has to think carefully about all these trade-offs when calibrating the asymmetric loss function. The results for the gradient boosting are similar, except for the fact that larger weight factors are required to equalize FP/FN probabilities across groups.
\begin{figure}[h]
\centering
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_3a.pdf}
\caption{Logit: False Positives (FP)}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_3b.pdf}
\caption{Logit: False Negatives (FN)}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_3c.pdf}
\caption{Boosting: False Positives (FP)}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_3d.pdf}
\caption{Boosting: False Negatives (FN)}
\end{subfigure}
\caption{Asymmetric Binary Choice. Each subplot corresponds to changes in the FP cost (left) or FN cost (right) for Logit (top) and boosting (bottom). The figure shows that introducing asymmetries in the loss function can equalize the False Positive and the False Negative rates across groups. Setting: $\rho=0.2$, $\sigma=0.1$, $\tau=0$, $n=1,000$. Results based on $5,000$ Monte Carlo experiments.}
\label{fig:fp_fn}
\end{figure}
Next, we compare the performance of the standard logistic regression approach, which ignores the asymmetric loss function, with the asymmetric logistic regression in terms of the average loss of a social planner. The social planner loss for the former will be denoted by $\ell_{logit}$ while our new estimator yields $\ell_{w-logit}.$
\smallskip
The simulation results are reported in Table \ref{tab:MCresults}. We report several measures to appraise the findings. First, we report P($\ell_{logit}$ $>$ $\ell_{w-logit}$) which is the percentage that the standard logistic regressions generate larger social planner costs compared to our weighted regression. Hence, this measure reports how often our estimator outperforms the standard procedure, where the probabilities are computed from the Monte Carlo simulated samples. Next, we report summary statistics for the ratio $\ell_{logit}/\ell_{w-logit}.$ When the ratio is above 1.00 then the weighted logistic approach is better. We report the minimum, maximum, mean, and three quartiles of the simulation distribution. All simulations involve 5000 replications.
\smallskip
We start from a baseline case for the parameter setting, namely: $\psi_0$ = 3, $\psi_1$ = 1, $\varphi_0$ = 1.7, and finally $\varphi_1$ = 1. For the baseline case and $n$ = 1,000, P($\ell_{logit}$ $>$ $\ell_{w-logit}$) is 0.52, meaning that in more than 50\% of cases, our procedure is superior (lower social costs) to the standard logistic regression. A more detailed summary statistics is reported in the Online Appendix, Table~\ref{tab:MCresults_summary}. We also examine various deviations from the baseline case. For the larger sample size $n$ = 10,000 the gains are larger, which is now 0.62, meaning that the probability that the symmetric logistic regression leads to larger losses increases as we get more data.
\begin{table}[H]
\caption{\label{tab:MCresults} Monte Carlo Simulation Results: symmetric vs. asymmetric Logit}
\rule[0mm]{0mm}{5mm}\noindent\footnotesize{\footnotesize
The Monte Carlo simulation design is presented in Section \ref{subsec:MCdesign}, which represents a stylized social planner with a loss function from Example~\ref{ex:fairness} featuring asymmetries for false positives and false negatives. The population consists of two groups, $G$ = 0 and 1, with the former assumed to be a protected segment of the population. Constituents of a group $G$ = 1 are a fraction $\rho.$ The baseline case has the loss function with the following setting: $\psi_1=\varphi_1$ = 1, $\varphi_0=1.7$, and $\psi_0=3$. We also set $\rho = 0.2$, $\sigma=0.1$, and $\tau=0$. We compare the performance of a standard logistic regression approach, which ignores the asymmetric loss function, with our convexified weighted logistic model appearing in equation (\ref{eq:simrisk}). The social planner loss for the former will be denoted by $\ell_{logit}$ while our new estimator yields $\ell_{w-logit}.$ We report P($\ell_{logit}$ $>$ $\ell_{w-logit}$) which is the percentage that standard logistic regressions generate larger social planner costs compared to our weighted regression. Hence, this measure reports how often our estimator outperforms the standard procedure, where the probabilities are computed from the Monte Carlo simulated samples. Columns with $\varphi_0,\varphi_1,\psi_0$, or $\psi_1$ as headers represent deviations from the baseline case.}
\begin{ctabular}{lccccccccc}
& Baseline & $\rho$ & $\tau$ & $\varphi_0$ & $\varphi_1$ & $\varphi_1$ & $\psi_0$ & $\psi_1$ & $\psi_1$\\
& case & 0.5 & 1 & 2 & 2 &3 & 4 & 2 & 3 \\
& & & & & & & & & \\
& \multicolumn{9}{c}{P($\ell_{logit}$ $>$ $\ell_{w-logit}$) } \\
& & & & & & & \\
Sample, $n$ & \\
1,000 & 0.52 & 0.45 & 0.84 & 0.52 & 0.64 & 0.69 & 0.58 & 0.65 & 0.70 \\
5,000 & 0.57 & 0.51 & 0.93 & 0.52 & 0.64 & 0.70 & 0.62 & 0.64 & 0.69 \\
10,000 & 0.62 & 0.53 & 0.97 & 0.54 & 0.69 & 0.75 & 0.71 & 0.68 & 0.74 \\
\end{ctabular}
\end{table}
Next, we report two columns in Table \ref{tab:MCresults} where we change the fraction of the protected population $\rho$ from 0.2 to respectively 0.5, introducing nonlinearities with $\tau=1$, and changing the cost structure. We can see that in most of the cases, our approach is superior with a larger margin compared to the baseline case. Introducing more asymmetries in the loss function implies better performance of asymmetric logistic regression, as expected.
\medskip
Lastly, we compare the performance of the weighted ERM decisions to simple plug-in rules motivated by Proposition~\ref{prop:bayes}. The plug-in rules predict $\hat Y=1$ when $\hat\eta(x)\geq c(x)$, where $\hat\eta(x)$ is an estimator of $\eta(x)=\Pr(Y=1|X=x)$. Note that in the special case of the symmetric binary classification with the logistic convexification, the plug-in decisions are actually equivalent to the ERM decisions in population since
\begin{equation*}
\eta(x) = \frac{1}{1+e^{-f(x)}}>0.5 \iff f(x)>0.
\end{equation*}
However, this equivalence does not hold in our asymmetric setting.\footnote{It is known that the plug-in rules can be inferior or superior relative to ERM in the symmetric case depending on the distribution of the data; see \cite{audibert2007fast} for more detailed comparison.} In addition, some of the popular and successful ML techniques, e.g., support vector machines and neural networks with hinge convexification, are ERM-based and do not estimate $\eta$. For simplicity, we focus on the parametric case and compare the asymmetric Logit to the asymmetric plug-in rules based on the symmetric Logit. These results are presented in Table~\ref{tab:MCresults_plug_in}. In most of the cases, the plug-in rules are inferior to our approach, and the difference is more pronounced in small samples. Lastly, we provide more detailed summary statistics for the ratio $\ell_{plugin}/\ell_{w-logit}$ in the Online Appendix, Table~\ref{tab:MCresults_plug_in_summary}.
\medskip
\begin{table}
\caption{\label{tab:MCresults_plug_in} Monte Carlo Simulation Results: plug-in vs. asymmetric Logit}
\rule[0mm]{0mm}{5mm}\noindent\footnotesize{\footnotesize
The Monte Carlo simulation design is presented in Section \ref{subsec:MCdesign}, which represents a stylized social planner with a loss function from Example~\ref{ex:fairness} featuring asymmetries for false positives and false negatives. The population consists of two groups, $G$ = 0 and 1, with the former assumed to be a protected segment of the population. Constituents of a group $G$ = 1 are a fraction $\rho.$ The baseline case has the loss function with the following setting: $\psi_1=\varphi_1$ = 1, $\varphi_0=1.7$, and $\psi_0=3$. We also set $\rho = 0.2$, $\sigma=0.1$, and $\tau=0$. We compare the performance of a standard logistic regression approach, which ignores the asymmetric loss function, with our convexified weighted logistic model appearing in equation (\ref{eq:simrisk}). The social planner loss for the former will be denoted by $\ell_{plugin}$ while our new estimator yields $\ell_{w-logit}.$ We report P($\ell_{plugin}$ $>$ $\ell_{w-logit}$) which is the percentage that standard logistic regressions generate larger social planner costs compared to our weighted regression. Hence, this measure reports how often our estimator outperforms the standard procedure, where the probabilities are computed from the Monte Carlo simulated samples. Columns with $\varphi_0,\varphi_1,\psi_0$, or $\psi_1$ as headers represent deviations from the baseline case.}
\begin{ctabular}{lccccccccc}
& Baseline & $\rho$ & $\tau$ & $\varphi_0$ & $\varphi_1$ & $\varphi_1$ & $\psi_0$ & $\psi_1$ & $\psi_1$\\
& case & 0.5 & 1 & 2 & 2 &3 & 4 & 2 & 3 \\
& & & & & & & & & \\
& \multicolumn{9}{c}{P($\ell_{plugin}$ $>$ $\ell_{w-logit}$) } \\
& & & & & & & \\
Sample, $n$ & \\
1,000 & 0.76 & 0.64 & 0.00 & 0.55 & 0.80 & 0.84 & 0.90 & 0.81 & 0.83 \\
5,000 & 0.76 & 0.56 & 0.00 & 0.42 & 0.83 & 0.89 & 0.96 & 0.83 & 0.88 \\
10,000 & 0.52 & 0.30 & 0.00 & 0.18 & 0.66 & 0.76 & 0.92 & 0.66 & 0.75 \\
\end{ctabular}
\end{table}
\section{Pretrial Detention Decisions: Algorithmic Fairness and Recidivism Revisited \label{sec:empirical}}
The purpose of this section is to illustrate our novel econometric methods with an application to the problem of algorithmic fairness in pretrial detention. We will show how ML taking into account social planner preferences can be incorporated directly into the digital decision process.\footnote{Among economists, the idea to apply ML to pretrial detention decisions has recently been explored by \cite{kleinberg2018human}. } In particular, we will illustrate that valuing outcomes of protected groups allows us to reduce various forms of algorithmic discrimination.
\smallskip
Across the nation, judges are increasingly using algorithms to assess the risk of whether a defendant, if released, would fail to appear in court or be rearrested for a new crime, a term called recidivism. Journalists at ProPublica have investigated a commercial algorithm, called Correctional Offender Management Profiling for Alternative Sanctions (COMPAS), developed by Northpointe, Inc. The algorithm assigns defendants recidivism risk scores based on more than 100 factors, including age, sex, and criminal history.
\smallskip
COMPAS does not explicitly use race as an input, hence, there are no disparate treatment issues.\footnote{The legal scholars distinguish between the disparate treatment and the disparate impact and there is often a tension between these two. The \textit{disparate treatment} pertains to using race explicitly in various decisions and is often illegal, including bail, hiring, admission, loans, etc. However, even when the decision is carefully made to avoid the disparate treatment, it may still have unintended \textit{disparate impact} consequences with substantial legal implications. } Nevertheless, the aforementioned ProPublica article revealed that African American defendants are substantially more likely to be classified as high risk. Therefore, the ProPublica article pertains to the disparate impact issues, and remedying it would require using race explicitly. This bring us to the legal issues related to algorithmic affirmative action; see \cite{bent2019algorithmic} for further discussion. As a simple illustration of our methodology, we will focus on equalizing the false positive rates, computed as
\begin{equation}\label{eq:fp_g}
{\rm FP}_g = \Pr(\ensuremath{\mathrm{sign}}(\hat f(X))=1|Y=-1,G=g)
\end{equation}
or positive predictive values
\begin{equation}\label{eq:ppv_g}
{\rm PPV}_g = \Pr(Y=1|\ensuremath{\mathrm{sign}}(\hat f(X))=1,G=g)
\end{equation}
for African American versus other individuals, i.e. $g\in\{\mathrm{AF,O}\}$. Equalizing the false positive rates in equation~\eqref{eq:fp_g} achieving the error rate balance fairness while equalizing the positive predictive values in equation~\eqref{eq:ppv_g} achieves the predictive parity fairness; see \cite{mitchell2021algorithmic} for further discussion. Therefore, we will show that our methodology can mitigate the disparate impact problem. Note that it is not the purpose of our study to compare ML outcomes with human decisions (as in \cite{kleinberg2018human}) or to compare ML outcomes with COMPAS.
\smallskip
We use data from Broward County, Florida, originally collected by ProPublica. Following their analysis, we only consider defendants who were assigned COMPAS risk scores within 30 days of their arrest and define the recidivism as a new felony or misdemeanor charge within two years after the initial screening. In addition, we restrict our analysis to only those defendants who spent at least two years (after their COMPAS evaluation) outside a correctional facility without being arrested for a violent crime or were arrested for a violent crime within these two years. Following standard practice, we use this two-year violent recidivism metric and set $Y_i=1$ for those who re-offended within this window, and $Y_i = -1$ for those who did not. In the Online Appendix Section \ref{appsubsec:cleaning}, we provide a detailed description of data cleaning and report the summary statistics for the cleaned dataset.\footnote{As we explain in Online Section \ref{appsubsec:cleaning}, while working with the COMPAS data, we discovered several issues regarding how the dataset was constructed by ProPublica journalists. Ideally, for each defendant we should only have one entry included in the data set with that record containing all the information including current charges and past crimes, to predict recidivism. However, we found multiple records for the same arrest in the COMPAS data set, with only differences in charges. As a result we undertook a thorough cleaning process described in the Online Appendix.} The total number of individuals is 8,227 with 495 variables making the problem high-dimensional, hence, calling for ML techniques as it may not be clear what types of crimes are predictive of recidivism. A large number of these variables are dummies for different kinds of crimes from the criminal code. The rest include variables like age, sex, race, crime history, marriage status, etc. We have a demographic mix dominated by African Americans and Caucasians, respectively 4,109 and 2,797 in numbers. We stratify race along two groups, African American versus all other, which given our sample is roughly African American versus Caucasian. The binary outcome $is\_recid$ indicates that 31.3\% of cases resulted in a recidivism. The minimum age is 16 with a median of 29.
\begin{figure}[h]
\centering
\includegraphics[width=0.6\textwidth]{fig/fig_4.pdf}
\caption{Training and Test AUC of LASSO-Logit path. The figure shows that the highest test AUC is achieved for the model with 152 covariates.}
\label{fig:auc_application}
\end{figure}
To understand whether the high-dimensional machine learning methods are needed for this dataset, we fit a LASSO-Logit regression and plot the area under the curve (AUC) for the 20\% of the data left out as the test sample. The results appear in Figure~\ref{fig:auc_application}. We find that the highest test AUC, namely $0.74$, is achieved for the model with 152 covariates.\footnote{It is worth mentioning that simple linear Logit using all 495 covariates is not feasible because the matrix of covariates is close to singular. See also Online Appendix Table~\ref{tab:post_lasso} for the post-LASSO Logit estimates.}
\begin{table}[!htbp] \centering
\caption{Symmetric Classifiers: false positive/negative rates and AUC for test sample.}
\label{tab:symmetric}
\begin{tabular}{@{\extracolsep{5pt}} lccc}
\\[-1.8ex]\hline
\hline \\[-1.8ex]
& FP & FN & AUC \\
& \multicolumn{3}{c}{LASSO-Logit} \\
All & $0.049$ & $0.772$ & $0.734$ \\
Other & $0.026$ & $0.840$ & $0.733$ \\
African American & $0.075$ & $0.720$ & $0.719$ \\
& & & \\
& \multicolumn{3}{c}{Boosting} \\
All & $0.095$ & $0.695$ & $0.725$ \\
Other & $0.055$ & $0.763$ & $0.736$ \\
African American & $0.143$ & $0.644$ & $0.697$ \\
\hline \\[-1.8ex]
\end{tabular}
\end{table}
Next, we fit the standard symmetric LASSO-Logit and Boosting classifiers using 494 covariates (excluding the race dummy). We tune the penalty of LASSO-Logit and the learning rate of Boosting using 5-fold cross-validation on the training sample. The test errors of both classifiers are reported in Table~\ref{tab:symmetric}. The standard symmetric classifiers have disproportionate biases even though the race variable has not been used to fit these models. African American defendants have almost 3 times higher false positive rates compared to the rest of the population. We also note that false negative rates are enormously large compared to the false positive rates, and calling for additional balancing. The performance of boosting is slightly inferior to LASSO-Logit, suggesting the limited role of additional nonlinearities. This is probably not suprising given that our covariates already include interactions between various crime types and degrees as well as a quadratic age term.
\smallskip
To balance the false positive and false negative rates rates, we fit the asymmetric classifiers with a loss function
\begin{equation*}
\ell(f,y) = \psi\ensuremath{\mathds{1}}_{f=-1,y=1} + \ensuremath{\mathds{1}}_{f=1,y=-1},
\end{equation*}
where $f\in\{-1,1\}$ is recidivism prediction and $y\in\{-1,1\}$ recidivism outcome. The cost of false positive mistakes is normalized to $1$ and the costs of false negative mistakes denoted by $\psi$.
\smallskip
The performance of asymmetric classifiers for various values of $\psi\in[0,10]$ appears in Figure~\ref{fig:fp_fn_application}. We find that changing the cost of false negative mistakes allows us to achieve balanced false positive and false negative rates both for LASSO-Logit and Boosting. The false positive and false negative rates are equalized approximately at $\psi=2.25$ for both classifiers.
\begin{figure}[h]
\centering
\begin{subfigure}{0.49\textwidth}
\includegraphics[width=\textwidth]{fig/fig_5a.pdf}
\caption{LASSO-Logit: FP and FN rates}
\end{subfigure}
\begin{subfigure}{0.49\textwidth}
\includegraphics[width=\textwidth]{fig/fig_5b.pdf}
\caption{Boosting: FP and FN rates}
\end{subfigure}
\caption{Asymmetric Binary Choice: Penalizing False Negative Mistakes. The figure shows that increasing the cost of false negative mistakes in the loss function is enough to balance FP and FN rates.}
\label{fig:fp_fn_application}
\end{figure}
However, changing $\psi$ is not enough to balance the false positive rates across the two groups; see Online Appendix Figure~\ref{fig:fp_fn_application_race} and Table~\ref{tab:balanced} for more details.
\smallskip
To address the algorithmic fairness issue, we rely on a two-group setup also used in the previous section where the protected group ($G$ = 1) are African American offenders. We focus on the loss function from Example~\ref{ex:fairness}:
\begin{equation*}
\ell(f,y,g) = \psi\ensuremath{\mathds{1}}_{f=-1,y=1} + \varphi_g\ensuremath{\mathds{1}}_{f=1,y=-1},
\end{equation*}
where $f\in\{-1,1\}$ is a recidivism prediction, $y\in\{-1,1\}$ is a recidivism outcome, and $g\in\{0,1\}$ is the group membership. Therefore, $\varphi_1$ is a false positive cost for African Americans which we will vary while $\psi=2.25$ is a false negative cost calibrated to balance the false positive and false negative rates.
\begin{figure}[H]
\centering
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_6a.pdf}
\caption{LASSO-Logit: FP rates}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_6b.pdf}
\caption{LASSO-Logit: FN rates}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_6c.pdf}
\caption{Boosting: FP rates}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_6d.pdf}
\caption{Boosting: FN rates}
\end{subfigure}
\caption{Fairness: Balanced Error Rates. The figure shows that increasing the cost of false positive (FP) mistakes for African Americans allows us to balance FP rates across the two groups. We use the cost of false negatives $\psi=2.25$ and vary the cost of false positives for African American defendants $\varphi_1\in[0.5,2.5]$.}
\label{fig:fairness_fp}
\end{figure}
First, we look at balancing the false positive rates across the two groups by varying $\varphi_1$. The results appear in Figure~\ref{fig:fairness_fp}. We find that the false positive rates for African Americans and Others can be equalized if the decision-maker values the outcomes of African American defendants more highly, i.e., the costs of false positive mistakes for African Americans, $\varphi_1$, are sufficiently high. The two rates are equalized when $\varphi_1\approx 1.9$ (LASSO-Logit) and $\varphi_1\approx2.25$ (Boosting). Therefore, varying $\varphi_1$ allows us to mitigate the disparate impact problem highlighted by ProPublica, achieving balanced false positive rates for the two groups. We also note that this type of fairness comes with a cost of increased false negative rates for African Americans. In other words, to reduce the number of wrongly detained African American defendants, we have to accept a larger number of wrongly released African American defendants.
\begin{figure}[H]
\centering
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_7a.pdf}
\caption{LASSO-Logit: PPV}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_7b.pdf}
\caption{LASSO-Logit: NPV}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_7c.pdf}
\caption{Boosting: PPV}
\end{subfigure}
\begin{subfigure}{0.45\textwidth}
\includegraphics[width=\textwidth]{fig/fig_7d.pdf}
\caption{Boosting: NPV}
\end{subfigure}
\caption{Fairness: Balanced Positive Predictive Values (PPV). The figure shows that increasing the cost of false positive mistakes for African Americans allows us to balance PPV across the two groups. We use the cost of false negatives $\psi=2.25$ and vary the cost of false positives for African American defendants $\varphi_1\in[0.5,2.5]$.}
\label{fig:fairness_ppv}
\end{figure}
Next, we look at balancing the positive predictive values (PPV) across the two groups by varying $\varphi_1$. The results appear in Figure~\ref{fig:fairness_ppv}. We find that the PPV for African Americans and others can be equalized if the decision-maker imposes higher costs for false positive mistakes for African American defendants. The PPVs for two groups are equalized when $\varphi_1\approx 1.25$ for both methods.\footnote{This fairness measure roughly corresponds to what the COMPAS algorithm was originally designed to achieve; see \cite{dieterich2016compas} for Northpointe's reply to the ProPublica article.} Therefore, varying $\varphi_1$ allows us to mitigate the disparate impact problem, achieving balanced PPV for the two groups. We also note that this type of fairness comes with a cost of increased negative predictive values (NPV) for Others. In other words, to balance the PPVs, we need to increase the likelihood that an African American defendant predicted to reoffend actually does so, which leads to a larger likelihood that Other defendants predicted not to reoffend actually do so.\footnote{See \cite{liang2021algorithm} and \cite{liu2024inference} for recent work on quantifying the fairness-accuracy frontier.}
\smallskip
In conclusion, algorithmic fairness can be achieved by placing a higher value on the outcomes of protected groups within our loss-based framework. This approach is transparent and can be directly incorporated into the digital decision process. However, the exact value of the loss function parameters that achieves balancing depends on the classifier and the fairness notion used; hence, it should be carefully calibrated in practice. It is impossible to achieve all fairness notions simultaneously, cf. \cite{chouldechova2017fair}.
\section{Conclusions}
This paper provides a new perspective on data-driven binary decisions with losses/utilities/welfare driven by economic factors, and contributes more broadly to the growing literature at the intersection of econometrics and machine learning. We show that the economic costs and benefits lead to a very simple loss-based reweighting of logistic regression or state-of-the art ML techniques. Our approach constitutes a significant advantage relative to others previously considered in the literature and leads to theoretically justified binary decisions for high-dimensional datasets frequently encountered in practice. We adopt a distribution-free approach and show that the loss-based reweighted logistic regression may lead to valid binary decisions even when the choice probabilities are not logistic. We also show that the carefully crafted asymmetric deep learning architectures are optimal from the minimax point of view.
Our work opens several directions for future research. First, it calls for a more disciplined application of ML classification methods to economic decisions based on the costs/benefit considerations. For example, the false positive and false negative mistakes in pretrial detention decisions can be associated with different monetary costs for the society while the correct decisions may also have additional social benefits. In our empirical application we opted for a stylized cost differentiation scheme to make the empirical exercise transparent, but in practice one can use costs that are covariate-driven and based on a comprehensive cost-benefit analysis for the U.S.\ pretrial detention decision, such as in \cite{baughman2017costs}, to build a preference-based approach for this particular application. Second, various economic applications often involve multi-class decisions and to that end some of the results of \cite{farrell2018deep} could potentially be extended to the asymmetric case provided that a suitable convexification result is established for generic covariate-driven losses.
\newpage
\setcounter{page}{1}
\setcounter{section}{1}
\setcounter{equation}{0}
\setcounter{table}{0}
\setcounter{figure}{0}
\begin{center}
{\LARGE\textbf{APPENDIX}}
\end{center}
\bigskip
In this Appendix we provide the proofs of all the main theorems, lemmas, and propositions. We will use $a\lesssim b$ if $a\leq Cb$ for a constant $C<\infty$ that does not depend on a particular distribution in the class of distributions restricted by our assumptions.
\begin{proof}[Proof of Proposition~\ref{prop:risk_representation}]
Note that for every $f,y\in\{-1,1\}$ and $x\in\mathcal{X}$
\begin{equation*}
\begin{aligned}
\ell(f,y,x) & = \ell_{1,1}(x)\frac{(1+f)(1+y)}{4} + \ell_{1,-1}(x)\frac{(1+f)(1-y)}{4} \\
& \qquad + \ell_{-1,1}(x)\frac{(1-f)(1+y)}{4} + \ell_{-1,-1}(x)\frac{(1-f)(1-y)}{4} \\
& = -0.25(a(x) + yb(x))f + d_0(y,x)
\end{aligned}
\end{equation*}
with $d_0(y,x) \triangleq 0.25(\ell_{1,1}(x) + \ell_{-1,1}(x))(1+y) + 0.25(\ell_{1,-1}(x) + \ell_{-1,-1}(x))(1-y)$. Next, for every $(y,x)\in\{-1,1\}\times\mathcal{X}$ and every $f\in\{-1,1\}$
\begin{equation*}
\begin{aligned}
(a(x) + yb(x))f & = (ya(x) + b(x))(1-2\ensuremath{\mathds{1}}_{-yf\geq 0}) \\
& = -2(ya(x) + b(x))\ensuremath{\mathds{1}}_{-yf\geq 0} + ya(x) + b(x).
\end{aligned}
\end{equation*}
Therefore, for every measurable $f:\mathcal{X}\to\{-1,1\}$
\begin{equation}\label{eq:risk_app}
\mathcal{R}(f) = 0.5\ensuremath{\mathbb{E}}[(Ya(X)+b(X))\ensuremath{\mathds{1}}_{-Yf(X)\geq 0}] + \ensuremath{\mathbb{E}}[d(Y,X)].
\end{equation}
with $d(y,x)\triangleq d_0(y,x) - 0.25(ya(x) + b(x))$. The result follows because the second term does not depend on $f$.
\end{proof}
\begin{proof}[Proof of Proposition~\ref{prop:bayes}]
By the law of iterated expectations, $f^*(x)$ minimizes
\begin{equation*}
\ensuremath{\mathbb{E}}\left[\omega(Y,X)\ensuremath{\mathds{1}}_{-Yf\geq 0}|X=x\right] = \eta(x)\omega(1,x)\ensuremath{\mathds{1}}_{f\leq 0} + (1-\eta(x))\omega(-1,x)\ensuremath{\mathds{1}}_{f\geq 0}
\end{equation*}
over $f\in\{-1,1\}$. The solution to this problem is
\begin{equation*}
f^*(x) = \begin{cases}
1 & \text{if}\quad \eta(x)\omega(1,x) \geq (1-\eta(x))\omega(-1,x), \\
-1 & \text{if}\quad \eta(x)\omega(1,x) < (1-\eta(x))\omega(-1,x).
\end{cases}
\end{equation*}
Under Assumption~\ref{as:losses} (i), $\omega(Y,X) > 0$ a.s., whence we obtain the first statement with
\begin{equation*}
c(x) = \frac{\omega(-1,x)}{\omega(1,x) + \omega(-1,x)}.
\end{equation*}
For the second statement, note that $f_\phi^*(x)$ solves
$\inf_{f\in\ensuremath{\mathbf{R}}}\ensuremath{\mathbb{E}}[\omega(Y,X)\phi(-Yf)|X=x].$
By the law of iterated expectations, for every $f\in\ensuremath{\mathbf{R}}$, the objective function is
\begin{equation*}
\ensuremath{\mathbb{E}}[\omega(Y,X)\phi(-Yf)|X=x] = \eta(x)\omega(1,x)\phi(-f) + (1-\eta(x))\omega(-1,x)\phi(f).
\end{equation*}
Since $\phi$ is differentiable, the optimum $f^*_\phi$ solves
$-\eta(x)\omega(1,x)\phi'(-f^*_\phi(x))$ + $(1-\eta(x))\omega(-1,x)\phi'(f^*_\phi(x))$ = 0. Under Assumption~\ref{as:losses} (ii), $\eta\not\in\{0,1\}$, and therefore:
\begin{equation*}
\frac{\eta(x)\omega(1,x)}{(1-\eta(x))\omega(-1,x)} = \frac{\phi'(f^*_\phi(x))}{\phi'(-f^*_\phi(x))}.
\end{equation*}
Since $\phi$ is a convex function, its derivative $\phi'$ is non-decreasing. Therefore, the optimum satisfies
\begin{equation*}
\begin{aligned}
f_\phi^*(x) \geq 0 & \iff \frac{\eta(x)\omega(1,x)}{(1-\eta(x))\omega(-1,x)} \geq 1 \\
& \iff \eta(x) \geq \frac{\omega(-1,x)}{\omega(1,x) + \omega(-1,x)} = c(x).
\end{aligned}
\end{equation*}
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:convexified_risk_bound_margin}]
Since $\gamma\in(0,1]$, the function $g:x\mapsto x^{1/\gamma}$ is convex on $\ensuremath{\mathbf{R}}_+$. By \cite{bartlett2006convexity}, Lemma 1, $y^{1/\gamma}\leq x^{1/\gamma}y/x,\forall x\geq y\geq 0,x>0$. Setting $x=|\eta(X)-c(X)|$ and $y=\epsilon$ for some $\epsilon>0$, we obtain
\begin{equation}\label{eq:inequality_margin}
|\eta(X)-c(X)|\ensuremath{\mathds{1}}_{|\eta(X)-c(X)|\geq\epsilon} \leq \epsilon^{1-1/\gamma}|\eta(X)-c(X)|^{1/\gamma}.
\end{equation}
Under Assumption~\ref{as:losses} (i), by Online Appendix Lemma~\ref{lemma:risk_eta_c} for every $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$ and $\epsilon>0$,
\begin{equation*}
\begin{aligned}
& \mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* = \\
& = \ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|\right] \\
& = \ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|\ensuremath{\mathds{1}}_{|\eta(X)-c(X)|<\epsilon}\right] \\
& \qquad +\ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|\ensuremath{\mathds{1}}_{|\eta(X)-c(X)|\geq\epsilon}\right] \\
& \leq 4M\epsilon P_X(\{x:\; \ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0 \}) + \epsilon^\frac{\gamma - 1}{\gamma}\ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|^{1/\gamma}\right] \\
& \leq 4M c_b^{-\frac{\alpha}{1+\alpha}}(2C_m)^\frac{1}{1+\alpha}\epsilon\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \right]^\frac{\alpha}{1+\alpha} + \epsilon^\frac{\gamma - 1}{\gamma}C^{1/\gamma}\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right],
\end{aligned}
\end{equation*}
where the first inequality follows from $|b(X)|\leq 4M$ a.s.\ under Assumptions~\ref{as:losses} (iii) and inequality~(\ref{eq:inequality_margin}); and the second by Lemma~\ref{lemma:margin} under Assumptions~\ref{as:losses} (i) and \ref{as:tsybakov}, and
\begin{equation*}
\begin{aligned}
& \ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|^{1/\gamma}\right] \\
& \leq C^{1/\gamma}\ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)\left(\eta(X) + c(X) - 2\eta(X)c(X) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_{c(X)}(\eta(X),y)\right)\right] \\
& \leq C^{1/\gamma}\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right],
\end{aligned}
\end{equation*}
which in turn follows by Assumption~\ref{as:phi} (iii) and the Online Appendix equation (\ref{eq:convex_inequality}). Therefore,
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \leq 4M c_b^{-\frac{\alpha}{1+\alpha}}(2C_m)^\frac{1}{1+\alpha}\epsilon\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \right]^\frac{\alpha}{1+\alpha} + \epsilon^\frac{\gamma - 1}{\gamma}C^{1/\gamma}\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right].
\end{equation*}
Setting $\epsilon = 0.5(4M)^{-1}c_b^\frac{\alpha}{1+\alpha}(2C_m)^{-\frac{1}{1+\alpha}}\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^*\right]^{\frac{1}{1+\alpha}}$ and rearranging, we obtain
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \leq C_\phi\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right]^\frac{\gamma(1+\alpha)}{\gamma\alpha + 1}
\end{equation*}
with $C_\phi = (2^\gamma C)^\frac{1+\alpha}{\gamma\alpha+1}\left[c_b^\alpha/(2^{3\alpha+4}C_mM^{\alpha+1})\right]^\frac{\gamma-1}{\gamma\alpha+1}$.
\end{proof}
\begin{proof}[Proof of Theorem \ref{thm:oracle inequality_dnn}]
Under Assumption~\ref{as:deep_learning}, by \cite{lu2020deep}, Theorem 1.1, there exists a deep neural network $\eta_n\in\Theta^{\rm DNN}_n$, with width $W_n \leq 17\beta^{d+1}3^dd(J_n+2)\log_2(8J_n)$ and depth $L_n \leq 18\beta^2(K_n+2)\log_2 (4K_n) + 2d$ such that $\|\eta_n - \eta\|_\infty \leq 85(\beta+1)^d8^\beta R\left(\frac{\log^6 n}{n}\right)^\frac{\beta}{\beta(2+\alpha)+d}\triangleq \varepsilon_n,$ where we use that under Assumption~\ref{as:deep_learning} (ii) $J_nK_n\leq (n/\log^6n)^\frac{d}{2\beta(2+\alpha)+2d}$. Put $f_n(x) \triangleq \sigma\left(\frac{\eta_n(x)-c(x)}{\varepsilon_n} + 1 \right)
-\sigma\left(\frac{\eta_n(x)-c(x)}{\varepsilon_n} - 1\right) - 1.$ Then
\begin{equation*}
f_n(x) = \begin{cases}
1 & \text{if } \eta_n(x)-c(x)> \varepsilon_n, \\
\frac{\eta_n(x)-c(x)}{\varepsilon_n} & \text{if } |{\eta}_n(x) - c(x)|\leq \varepsilon_n, \\
-1 & \text{if } \eta_n(x)-c(x)<- \varepsilon_n.
\end{cases}
\end{equation*}
Then on the event $\{x\in\mathcal{X}:|\eta(x) - c(x)|>2\varepsilon_n\}$, we have $f_n(x)=f_\phi^*(x)$. To see this note that $f_\phi^*(x)=\ensuremath{\mathrm{sign}}(\eta(x)-c(x))$ and that if $\eta(x)> c(x)$, we have $\eta_n(x)-c(x) = (\eta(x)-c(x))-({\eta}(x)-\eta_n(x))\geq \varepsilon_n$ while if $\eta(x)<c(x)$, we have $\eta_n(x)-c(x)<-\varepsilon_n$. Therefore, by Lemma~\ref{lemma:equation_hinge}
\begin{equation*}
\begin{aligned}
\inf_{f\in\mathscr{F}_n^{\rm DNN}}{\mathcal{R}}_{\phi}(f) - \mathcal{R}_\phi^* & \leq {\mathcal{R}}_{\phi}(f_n) - \mathcal{R}_\phi^* = \int_\mathcal{X}b|\eta - c||f_n - f^*_\phi|\ensuremath{\mathrm{d}} P_X \\
& \leq 4M\int_{|\eta-c|\leq 2\varepsilon_n}|\eta - c||f_n - f^*_\phi|\ensuremath{\mathrm{d}} P_X \leq16M \varepsilon_n P_X(|\eta - c|\leq 2\varepsilon_n) \\
& \leq 2^{4+\alpha}MC_m\varepsilon_n^{1+\alpha},
\end{aligned}
\end{equation*}
where the third line follows since $|b(X)|\leq 4M$ under Assumption~\ref{as:losses} (iii); the fourth since $|f_n-f_\phi^*|\leq 2$ in the region of integration; and the last under Assumption~\ref{as:tsybakov}.
Let $p_n$ be the total number of free parameters in $\Theta_n^{\rm DNN}$ and let $U_n$ be the total number of nodes in $\Theta_n^{\rm DNN}$. Note that $U_n\leq L_nW_n$ and that $p_n = \sum_{l=1}^{L-1}(w_{l+1}\times w_l + w_l) + w_1\times w_0 \leq L_nW_n(W_n + 1) + W_n^2 \leq 3L_nW_n^2$. Then by \cite{bartlett2019nearly}, Theorem 7, there exist universal constant $C_0>0$ such that $V \leq C_0 p_nL_n\log(U_n) \leq 3C_0(L_nW_n)^2\log(W_nL_n)$. Therefore, by Online Appendix Lemmas~\ref{lemma:lrc_deep_learning} and \ref{lemma:lrc_fp}
\begin{equation*}
\begin{aligned}
\psi_{n,\kappa}^{\sharp}(\epsilon) & \leq C(3C_0)^\frac{1+\alpha}{2+\alpha}\left(\frac{(W_nL_n)^2\log (W_nL_n)}{n}\log\left(\frac{n}{3C_0(W_nL_n)^2\log (W_nL_n)}\right)\right)^\frac{1+\alpha}{2+\alpha}.
\end{aligned}
\end{equation*}
Since under Assumption~\ref{as:deep_learning} (ii), $W_nL_n\leq abC_LC_W(n/\log^6 n)^\frac{d}{2\beta(2+\alpha)+2d}\log^2n$, by Theorem~\ref{thm:oracle inequality} for every $t>0$ with probability at least $1-c_qe^{-t}$
\begin{align*}\small
\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^* & \leq K\left(\frac{\log^6 n}{n}\right)^\frac{\beta(1+\alpha)}{\beta(2+\alpha)+d} + \left(\frac{t}{n}\right)^\frac{1+\alpha}{2+\alpha} + \frac{t}{n} \\
&\qquad + 2^{4+\alpha}MC_m\left(85(\beta+1)^d8^\beta R\left(\frac{\log^6 n}{n}\right)^\frac{\beta}{\beta(2+\alpha)+d}\right)^{1+\alpha}
\end{align*}
where $K>0$ depends only on $\alpha,\beta,d,C_0,C_1,C>0$. Integrating the tail bound, we obtain the second claim.
\end{proof}
\begin{lemma}\label{lemma:risk_eta_c}
Suppose that Assumption~\ref{as:losses} (i) is satisfied. Then for every measurable $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$, the excess risk is
\begin{equation*}
\mathcal{R}(\mathrm{sign}(f)) - \mathcal{R}^* = \ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)\left|\eta(X)-c(X)\right|\right],
\end{equation*}
where for an event $A$ and a random variable $\xi$, we put $\ensuremath{\mathbb{E}}_A\xi = \ensuremath{\mathbb{E}}\ensuremath{\mathds{1}}_A\xi$.
\end{lemma}
\begin{proof}
By the law of iterated expectations
\begin{align*}
\ensuremath{\mathbb{E}}\left[(Ya(X)+b(X))\ensuremath{\mathds{1}}_{-Y\mathrm{sign}(f)\geq 0}\right] &= \ensuremath{\mathbb{E}}\left[\eta(X)(a(X)+b(X))\ensuremath{\mathds{1}}_{\mathrm{sign}(f)\leq 0}\right]\\
&\qquad+\ensuremath{\mathbb{E}}[(1-\eta(X))(b(X)-a(X))\ensuremath{\mathds{1}}_{\mathrm{sign}(f)\geq 0}]\\
&=\ensuremath{\mathbb{E}}[( a(X)-b(X) + 2\eta(X)b(X))\ensuremath{\mathds{1}}_{\mathrm{sign}(f)\leq 0}]\\
&\qquad + \ensuremath{\mathbb{E}}[(1-\eta(X))(b(X)-a(X))].
\end{align*}
Combining this observation with equation (\ref{eq:risk_app}) yields
\begin{equation*}\label{eq:risk_eta_c}
\begin{aligned}
2(\mathcal{R}(\mathrm{sign}(f)) - \mathcal{R}^*) & = \ensuremath{\mathbb{E}}\left[(Ya(X)+b(X))(\ensuremath{\mathds{1}}_{-Y\mathrm{sign}(f)\geq 0} - \ensuremath{\mathds{1}}_{-Yf^*(X)\geq 0})\right] \\
& = \ensuremath{\mathbb{E}}\left[( a(X)-b(X) + 2\eta(X)b(X))(\ensuremath{\mathds{1}}_{\mathrm{sign}(f)\leq 0} - \ensuremath{\mathds{1}}_{f^*(X)\leq 0})\right] \\
& = \ensuremath{\mathbb{E}}\left[2b(X)(\eta(X)-c(X))(\ensuremath{\mathds{1}}_{\mathrm{sign}(f)\leq 0} - \ensuremath{\mathds{1}}_{f^*(X)\leq 0})\right] \\
& = \ensuremath{\mathbb{E}}_{\mathrm{sign}(f)f^*<0}\left[2b(X)\left|\eta(X)-c(X)\right|\right],
\end{aligned}
\end{equation*}
where the last line follows since under Assumption~\ref{as:losses} (i), by Proposition~\ref{prop:bayes}
\begin{equation*}
f^*(x)\geq 0 \iff \eta(x) \geq \frac{b(x)-a(x)}{2b(x)} = c(x).
\end{equation*}
\end{proof}
\begin{lemma}\label{lemma:convexified_risk_bound}
Suppose that Assumptions~\ref{as:losses} and \ref{as:phi} are satisfied. Then for every measurable function $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^* \leq 2^{\frac{2}{\gamma}-2}CM^{\frac{1}{\gamma}-1} \left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right]^\gamma.
\end{equation*}
\end{lemma}
\begin{proof}
Under Assumption~\ref{as:losses} (i), by Lemma~\ref{lemma:risk_eta_c}
\begin{equation*}
\begin{aligned}
& \mathcal{R}(\ensuremath{\mathrm{sign}}(f)) - \mathcal{R}^*= \\
& = \ensuremath{\mathbb{E}}_{\mathrm{sign}(f)f^*<0}b(X)\left|\eta(X)-c(X)\right| \\
& \leq C\ensuremath{\mathbb{E}}_{\mathrm{sign}(f)f^*<0}\left[b(X)\left(\eta(X)+c(X)-2\eta(X)c(X) -\inf_{y\in\ensuremath{\mathbf{R}}}Q_{c}(\eta,y)\right)^\gamma\right] \\
& \leq C\left(\ensuremath{\mathbb{E}}_{\mathrm{sign}(f)f^*<0}\left[b(X)^{1/\gamma}\left( \eta(X)+c(X)-2\eta(X)c(X) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_{c}(\eta,y)\right)\right]\right)^\gamma\\
& \leq C(4M)^\frac{1-\gamma}{\gamma} \left(\ensuremath{\mathbb{E}}_{\mathrm{sign}(f)f^*<0}\left[b(X)\left(\eta(X)+c(X)-2\eta(X)c(X) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_{c}(\eta,y)\right)\right]\right)^\gamma,
\end{aligned}
\end{equation*}
where the second line follows under Assumption~\ref{as:phi} (iii) since $\eta,c\in(0,1)$ under Assumptions~\ref{as:losses} (i)-(ii); the third by Jensen's inequality since $\gamma\in(0,1]$ under Assumption~\ref{as:phi} (iii); and the last since $|b(X)|\leq 4M$ a.s. under Assumption~\ref{as:losses} (ii). Next, from equation~(\ref{eq:excess_convex}) in the paper, we have
\begin{equation*}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* = 0.5\ensuremath{\mathbb{E}}\left[(Ya(X) + b(X))\left(\phi(-Yf(X)) - \phi(-Yf^*_\phi(X))\right)\right].
\end{equation*}
Therefore, if we show that
\begin{equation}\label{eq:convex_inequality}
\begin{aligned}
& b(x)\ensuremath{\mathds{1}}_{\ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0}\left(\eta(x)+c(x)-2\eta(x)c(x) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_{c(x)}(\eta(x),y)\right) \\
& \qquad\leq 0.5\ensuremath{\mathbb{E}}[(Ya(X)+b(X))(\phi(-Yf(X)) - \phi(-Yf^*_\phi(X)))|X=x] \\
\end{aligned}
\end{equation}
the result will follow from integrating over $x$. To that end, if $\ensuremath{\mathrm{sign}}(f(x))f^*(x)<0$, then the inequality in equation (\ref{eq:convex_inequality}) follows trivially since by definition $f^*_\phi$ minimizes $f\mapsto \ensuremath{\mathbb{E}}[(Ya(X)+b(X))\phi(-Yf(X))]$. Suppose now that $\ensuremath{\mathrm{sign}}(f(x))f^*(x)\geq0$. Then by the law of iterated expectations and the definition of $Q$ in the Assumption~\ref{as:phi} (iii)
\begin{equation*}
\ensuremath{\mathbb{E}}[(Ya(X)+b(X))\phi(-Yf^*_\phi(X))|X=x] = 2b(x)\inf_{y\in\ensuremath{\mathbf{R}}}Q_{c(x)}(\eta(x),y).
\end{equation*}
Therefore, the inequality in equation (\ref{eq:convex_inequality}) follows if we can show that
$$2b(x)(\eta(x)+c(x)-2\eta(x)c(x))\leq \ensuremath{\mathbb{E}}[(Ya(X)+b(X))\phi(-Yf(X))|X=x].$$
But this follows from
\begin{equation*}
\begin{aligned}
&\ensuremath{\mathbb{E}}[(Ya(X)+b(X))\phi(-Yf(X))|X=x] \\
&=\eta(x)(a(x)+b(x))\phi(-f(x))+(1-\eta(x))(b(x)-a(x))\phi(f(x)) \\
&=2b(x)[\eta(x)(1-c(x))\phi(-f(x))+(1-\eta(x))c(x)\phi(f(x))] \\
& \geq 2b(x)(\eta(x)+c(x)-2\eta(x)c(x))\phi\left(\frac{f(x)(c(x)-\eta(x))}{\eta(x)+c(x)-2\eta(x)c(x)} \right) \\
& \geq 2b(x)(\eta(x)+c(x)-2\eta(x)c(x))\phi(0)\\
& = 2b(x)(\eta(x)+c(x)-2\eta(x)c(x)),
\end{aligned}
\end{equation*}
where the first inequality follows by the convexity of $\phi$ under Assumption~\ref{as:phi} (i) and since $\eta+c-2\eta c>0$ under Assumption~\ref{as:losses} (i)-(ii); the second inequality since $\phi$ is nondecreasing under Assumption~\ref{as:phi} (i) and $0\leq \ensuremath{\mathrm{sign}}(f(x))f^*(x) = \ensuremath{\mathrm{sign}}(f(x))\mathrm{sign}(c(x)-\eta(x))$ by Proposition~\ref{prop:bayes}; and the last line since $\phi(0)=1$ under Assumption~\ref{as:phi} (i).
\end{proof}
\begin{lemma}\label{lemma:logistic}
For the logistic convexifying function $\phi(z)=\log_2(1 + e^z)$,
\begin{equation*}
f_\phi^*(x) = \log\left(\frac{\eta(x)(1-c(x))}{(1-\eta(x))c(x)}\right).
\end{equation*}
Assumption~\ref{as:phi} is satisfied with $\gamma=1/2$ and $C=\sqrt{2\log 2}$.
\end{lemma}
\begin{proof}
Note that the minimum of $y\mapsto Q_{c}(x,y)$ is achieved at $y^*$ = $\log\left(\frac{x(1-c)}{(1-x)c}\right).$ Put $\eta_y\triangleq\frac{y(1-c)}{y(1-c)+(1-y)c}$ and $\eta \triangleq \eta_x$, and note that
\begin{align*}
\inf_{y\in\ensuremath{\mathbf{R}}} Q_{c}(x,y) & = x(1-c)\log_2(1+e^{-y^*}) + (1-x)c\log_2(1+e^{y^*})\\
& =-x(1-c)\log_2\frac{x(1-c)}{x(1-c)+(1-x)c}-(1-x)c\log_2 \frac{c(1-x)}{x(1-c)+(1-x)c}\\
& =(x(1-c)+(1-x)c)\left[-\eta\log_2\eta-(1-\eta)\log_2(1-\eta)\right].
\end{align*}
For every $y\in[0,1]$, put
{\footnotesize\begin{equation*}
\begin{aligned}
L(y) & \triangleq (x(1-c)+(1-x)c)\Big[\eta\log_2\left({\eta}\right) + (1-\eta)\log_2\left({1-\eta}\right)-\eta\log_2\left({\eta_y}\right) - (1-\eta)\log_2\left({1-\eta_y}\right)\Big] \\
& = (x(1-c)+(1-x)c)\frac1{\log 2}\left[\eta\log\left(\frac{\eta}{\eta_y}\right) + (1-\eta)\log\left(\frac{1-\eta}{1-\eta_y}\right)\right]
\end{aligned}
\end{equation*}}
and note that the equality in the first line implies that
$$
L(c)=(x+c-2xc) - \inf_{y\in\ensuremath{\mathbf{R}}} Q_{c}(x,y).
$$
By Taylor's theorem there exists $\eta'$ between $\eta$ and $\eta_y$ such that
\begin{align*}
\eta\log\left(\frac{\eta}{\eta_y}\right) + (1-\eta)\log\left(\frac{1-\eta}{1-\eta_y}\right) &= \frac{1}{2\eta'(1-\eta')}(\eta-\eta_y)^2\\
&\geq 2(\eta-\eta_y)^2,
\end{align*}
since $\eta'\in[0,1]$. This shows that for every $y\in[0,1]$
\begin{align*}
L(y)&\geq \frac{2}{\log 2}(x(1-c)+(1-x)c)(\eta-\eta_y)^2.
\end{align*}
In particular, for $y=c$,
\begin{align*}
L(c)&\geq \frac{2}{\log 2}(x(1-c)+(1-x)c)(\eta-\eta_c)^2\\
&= \frac{1}{2\log 2}(x(1-c)+(1-x)c)\left(\frac{x-c}{x(1-c) + (1-x)c}\right)^2 \\
&\geq \frac{1}{2\log 2}(x-c)^2.
\end{align*}
Therefore, Assumption is verified with $\gamma=1/2$ and $C=\sqrt{2\log 2}$.
\end{proof}
\begin{lemma}\label{lemma:hinge}
For the hinge convexifying function $\phi(z)=(1+z)_+$,
\begin{equation*}
f_\phi^*(x) = \begin{cases}
1 & \text{if }\; \eta(x)\geq c(x), \\
-1 & \text{if }\; \eta(x)<c(x).
\end{cases}
\end{equation*}
Assumption~\ref{as:phi} is satisfied with $\gamma=1$ and $C=1$.
\end{lemma}
\begin{proof}
Note that the minimum of $y\mapsto Q_c(x,y)$ is achieved at
\begin{equation*}
\begin{cases}
1 & \text{if }\; x>c, \\
-1 & \text{if }\; x<c.
\end{cases}
\end{equation*}
Then
\begin{equation*}
\begin{aligned}
\inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) & = \inf_{y\in\ensuremath{\mathbf{R}}} x(1-c)(1-y)_+ + c(1-x)(1+y)_+ \\
& = \min\{2x(1-c),2c(1-x)\}.
\end{aligned}
\end{equation*}
If $x\leq c$, then
\begin{equation*}
\begin{aligned}
(x+c-2xc) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) & = (x+c-2xc) - 2x(1-c) \\
& = (c-x).
\end{aligned}
\end{equation*}
If $x>c$, then
\begin{equation*}
\begin{aligned}
(x+c-2xc) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) & = (x+c-2xc) - 2c(1-x) \\
& = (x-c).
\end{aligned}
\end{equation*}
Therefore,
\begin{equation*}
(x+c-2xc) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) = |x-c|
\end{equation*}
and Assumption~\ref{as:phi} is satisfied with $\gamma=1$ and $C=1$.
\end{proof}
\begin{lemma}\label{lemma:exponential}
For the exponential convexifying function $\phi(z)=e^z$,
\begin{equation*}
f_\phi^*(x) = \frac{1}{2}\log\left(\frac{\eta(x)(1-c(x))}{(1-\eta(x))c(x)}\right).
\end{equation*}
Assumption~\ref{as:phi} is satisfied with $\gamma=1/2$ and $C=2$.
\end{lemma}
\begin{proof}
Note that the minimum of $y\mapsto Q_c(x,y)$ is achieved at
\begin{equation*}
y^* = \frac{1}{2}\log\left(\frac{x(1-c)}{(1-x)c}\right).
\end{equation*}
Then
\begin{equation*}
\begin{aligned}
\inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) & = \inf_{y\in\ensuremath{\mathbf{R}}} x(1-c)e^{-y} + c(1-x)e^y \\
& = 2\sqrt{xc(1-x)(1-c)}.
\end{aligned}
\end{equation*}
Then
\begin{equation*}
\begin{aligned}
(x+c-2xc) - \inf_{y\in\ensuremath{\mathbf{R}}}Q_c(x,y) & = (x+c-2xc)-2\sqrt{xc(1-x)(1-c)} \\
& =\left(\sqrt{x(1-c)}-\sqrt{c(1-x)}\right)^2 \\
& =\frac{(x-c)^2}{(\sqrt{x(1-c)}+\sqrt{c(1-x)})^2}\geq \frac{(x-c)^2}{4}.
\end{aligned}
\end{equation*}
where last line is due to the fact $x,c\in(0,1)$. Therefore, Assumption~\ref{as:phi} is satisfied with $\gamma=1/2$ and $C=2$.
\end{proof}
\begin{lemma}\label{lemma:margin}
Suppose that Assumptions \ref{as:losses} (i) and \ref{as:tsybakov} are satisfied. Then for every measurable $f:\mathcal{X}\to\ensuremath{\mathbf{R}}$
\begin{equation*}
\mathcal{R}(\mathrm{sign}(f)) - \mathcal{R}^* \geq c_b(2C_m)^{-1/\alpha} P_X^{\frac{1+\alpha}{\alpha}}\left(\{x:\;\ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0 \}\right).
\end{equation*}
\end{lemma}
\begin{proof}
By Lemma~\ref{lemma:risk_eta_c}
{\footnotesize
\begin{equation*}
\begin{aligned}
\mathcal{R}(\mathrm{sign}(f)) - \mathcal{R}^* & = \ensuremath{\mathbb{E}}_{\ensuremath{\mathrm{sign}}(f)f^*<0}\left[b(X)|\eta(X)-c(X)|\right] \\
& \geq 2c_b \int_\mathcal{X}\ensuremath{\mathds{1}}_{\ensuremath{\mathrm{sign}}(f(x))f^*(x)<0}|\eta(x)-c(x)|\ensuremath{\mathrm{d}} P_X(x) \\
& \geq 2c_b uP_X\left(\{x:\; \ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0\}\cap\{x:\; |\eta(x)-c(x)|>u \}\right) \\
& \geq 2c_b uP_X\left(\{x:\; \ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0\}\right) - 2c_b uP_X\left(\{x:\;|\eta(x)-c(x)|\leq u \}\right) \\
& \geq 2c_b uP_X\left(\{x:\; \ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0\}\right) - 2c_b C_mu^{1+\alpha},
\end{aligned}
\end{equation*}}
where the first inequality follows under Assumption~\ref{as:losses} (i); the second by Markov's inequality for every $u>0$; the third by $\Pr(A\cap B)\geq \Pr(A) - \Pr(B^c)$; and the fourth under Assumption~\ref{as:tsybakov}. The result follows from substituting $u$ solving
\begin{equation*}
P_X\left(\{x:\; \ensuremath{\mathrm{sign}}(f(x))f^*(x)< 0\}\right) = 2C_mu^\alpha
\end{equation*}
in the last equation.
\end{proof}
\begin{lemma}\label{lemma:curvature_exp_log}
Suppose that Assumptions~\ref{as:losses} (i)-(ii) are satisfied and that there exists a constant $F<\infty$ such that $|f|\leq F$ for all $f\in\mathscr{F}_n$. Then the exponential convexifying function satisfies Assumption~\ref{as:loss_modulus} with $\kappa = 1$ and $c_\phi=c_b\epsilon$, while for the logistic function we have $\kappa=1$ and $c_\phi = 2c_b\epsilon\phi''(F\vee \log((1-\epsilon)c_b/2\epsilon M))$.
\end{lemma}
\begin{proof}
First note that for every $f\in\mathscr{F}_n$ by the law of iterated expectations
{\footnotesize
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) & = 0.5\ensuremath{\mathbb{E}}\left[(Ya(X) + b(X))\phi(-Yf(X))\right] + \ensuremath{\mathbb{E}}[d(Y,X)] \\
& = 0.5\ensuremath{\mathbb{E}}\left[\eta(X)(a(X)+b(X))\phi(-f(X)) + (1-\eta(X) )(b(X)-a(X))\phi(f(X))\right] + \ensuremath{\mathbb{E}}[d(Y,X)] \\
& = \ensuremath{\mathbb{E}}\left[b(X)\eta(X)(1-c(X))\phi(-f(X)) + b(X)(1-\eta(X))c(X)\phi(f(X))\right] + \ensuremath{\mathbb{E}}[d(Y,X)].
\end{aligned}
\end{equation*}}
Then, since $f_\phi^*(x)$ minimizes $f\mapsto \eta(x)(1-c(x))\phi(-f) + (1-\eta(x) )c(x)\phi(f)$, by Taylor's theorem there exists $\tau\in[0,1]$ such that for $f_\tau \triangleq \tau f+(1-\tau)f_\phi^*$, we have
{\footnotesize
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* & = \frac{1}{2}\ensuremath{\mathbb{E}}\left[b(X)\left[\eta(X)(1-c(X))\phi''(-f_\tau(X)) + (1-\eta(X))c(X)\phi''(f_\tau(X))\right]|f(X) - f^*_\phi(X)|^2\right]
\end{aligned}
\end{equation*}}
Then for the exponential convexifying function since $\phi''(z)=e^{z}=\phi(z)$ and $f_\phi^*$ minimizes $f\mapsto \eta(1-c)\phi(-f) + (1-\eta)c\phi(f)$
{\footnotesize
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* & = \frac{1}{2}\ensuremath{\mathbb{E}}\left[b(X)\left[\eta(X)(1-c(X))\phi(-f_\tau(X)) + (1-\eta(X))c(X)\phi(f_\tau(X))\right]|f(X) - f^*_\phi(X)|^2\right] \\
& \geq \frac{1}{2}\ensuremath{\mathbb{E}}\left[b(X)\left[\eta(X)(1-c(X))e^{-f_\phi^*(X)} + (1-\eta(X))c(X)e^{f_\phi^*(X)}\right]|f(X) - f^*_\phi(X)|^2\right] \\
& = \ensuremath{\mathbb{E}}\left[b(X)\sqrt{\eta(X)(1-c(X))c(X)(1-\eta(X))}|f(X) - f^*_\phi(X)|^2\right] \\
& = \frac{1}{2}\ensuremath{\mathbb{E}}\left[\sqrt{\eta(X)(a(X)+b(X))(b(X)-a(X))(1-\eta(X))}|f(X) - f^*_\phi(X)|^2\right] \\
&\geq c_b\epsilon\|f - f^*_\phi\|^2,
\end{aligned}
\end{equation*}}
where the third line follows since $f_\phi^*=\frac1 2\log\left(\frac{\eta(1-c)}{c(1-\eta)}\right)$, see Lemma~\ref{lemma:exponential}; and the last since $a+b\geq 2c_b$ and $b-a\geq 2c_b$ under Assumption~\ref{as:losses} (i), and $\eta\geq \epsilon$ and $1-\eta \geq \epsilon$ under Assumption~\ref{as:losses} (ii).
Similarly, for the logistic convexifying function,
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* & \geq 2c_b\epsilon \ensuremath{\mathbb{E}}\left[\phi''(f_\tau(X))|f(X) - f^*_\phi(X)|^2\right]\\
& \geq 2c_b\epsilon \ensuremath{\mathbb{E}}\left[\phi''(F \vee f_\phi^*\vee -f^*_\phi)|f(X) - f^*_\phi(X)|^2 \right] \\
& \geq 2c_b\epsilon\phi''\left(F\vee \log\left(\frac{(1-\epsilon)c_b}{2\epsilon M}\right)\right) \|f - f^*_\phi\|^2 \\
\end{aligned}
\end{equation*}
where the first inequality uses $\phi''(z)=\frac{e^z}{(1+e^z)^2\log 2}$, so that $\phi''(-z)=\phi''(z)$; the second since $-F\wedge f^*_\phi \leq f_\tau\leq F\vee f_\phi^*$ and $\phi''$ is decreasing to zero; and the last since by Lemma~\ref{lemma:logistic}
\begin{equation*}
\log\left(\frac{2M\epsilon }{c_b(1-\epsilon)}\right) \leq f_\phi^* = \log\left(\frac{\eta(a + b)}{(1-\eta)(b - a)}\right) \leq \log\left(\frac{(1-\epsilon)c_b}{\epsilon 2M}\right),
\end{equation*}
which follows under Assumption~\ref{as:losses}.
\end{proof}
\begin{lemma}\label{lemma:equation_hinge}
Suppose that $|f|\leq 1$. Then the hinge convexifying function satisfies
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* &
& = \int_\mathcal{X}b\left|f - f_\phi^*\right||\eta-c|\ensuremath{\mathrm{d}} P_X.
\end{aligned}
\end{equation*}
\end{lemma}
\begin{proof}
Since, $|f|\leq 1$ and $f_\phi^*(x)=\ensuremath{\mathrm{sign}}(\eta(x)-c(x))$, see Lemma~\ref{lemma:hinge}, we have
\begin{equation*}
\begin{aligned}
\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* & = 0.5\ensuremath{\mathbb{E}}[(a(X)Y +b(X))Y(f_\phi^*(X) - f(X))] \\
& = 0.5\ensuremath{\mathbb{E}}[(a(X)-b(X)+2\eta(X)b(X))(f^*_\phi(X) - f(X))] \\
& = \ensuremath{\mathbb{E}}\left[b(X)(\eta(X)-c(X))(f^*_\phi(X) - f(X))\right] \\
& = \int_\mathcal{X}b\left|f - f_\phi^*\right||\eta-c|\ensuremath{\mathrm{d}} P_X.
\end{aligned}
\end{equation*}
\end{proof}
\begin{lemma}\label{lemma:curvature_hinge}
Suppose that Assumptions~\ref{as:losses} and \ref{as:tsybakov} are satisfied and that $|f|\leq 1$ for all $f\in\mathscr{F}_n$. Then the hinge convexifying function satisfies Assumption~\ref{as:loss_modulus} with $\kappa = 1+1/\alpha$ and $c_\phi=2^{-3/\alpha-1}c_bC_m^{-1/\alpha}$.
\end{lemma}
\begin{proof}
For every $u>0$,
\begin{equation*}
\begin{aligned}
\|f - f^*_\phi\|^2 & \leq 2\int_\mathcal{X}|f-f_\phi^*|\ensuremath{\mathrm{d}} P_X \\
& = 2\int_{|\eta-c|>u}\left|f - f_\phi^*\right|\ensuremath{\mathrm{d}} P_X + 2\int_{|\eta-c|\leq u}\left|f - f_\phi^*\right|\ensuremath{\mathrm{d}} P_X \\
& \leq \frac{1}{c_bu}\int_\mathcal{X}b\left|f - f_\phi^*\right||\eta-c|\ensuremath{\mathrm{d}} P_X + 4P_X(|\eta - c|\leq u) \\
& \leq \frac{1}{c_bu}[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*] +4C_m u^\alpha,
\end{aligned}
\end{equation*}
where the third line follows since $b\geq 2c_b$ under Assumption~\ref{as:losses}; and the last line by Lemma~\ref{lemma:equation_hinge} and Assumption~\ref{as:tsybakov}. To balance the two terms above, we shall take $u = \left([\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*]/(4c_bC_m)\right)^{1/(1+\alpha)}$, in which case
\begin{equation*}
\|f - f_\phi^*\|^2 \leq \frac{2}{c_b}(4c_bC_m)^{1/(1+\alpha)}[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*]^{\alpha/(1+\alpha)}.
\end{equation*}
yields the result with $c_\phi=2^{-3/\alpha-1}c_bC_m^{-1/\alpha}$ and $\kappa=1+\frac 1\alpha$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:oracle inequality}]
By Theorem~\ref{thm:convexified_risk_bound_margin}
\begin{equation}\label{eq:convexified_bound}
\begin{aligned}
\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^* & \leq C_\phi \left[\mathcal{R}_\phi(\hat f_n) - \mathcal{R}_\phi^*\right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1} \triangleq C_\phi\left[\mathcal{R}_\phi(\hat f_n) - \mathcal{R}_\phi(f_n^*) + \triangle_n \right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1}
\end{aligned}
\end{equation}
with $\triangle_n \triangleq \mathcal{R}_\phi(f_n^*) - \mathcal{R}_\phi^*$. We will bound the stochastic term by \cite{koltchinskii2011oracle}, Theorem 4.3. To that end, put $\mathscr{F}(\delta) = \left\{\ell\circ f:\; \mathcal{R}_\phi(f) - \mathcal{R}_\phi(f_n^*)\leq \delta, \;f\in\mathscr{F}_n\right\}$ for some $\delta>0$ and $(\ell\circ f)(y,x) = \omega(y,x)\phi(-yf(x))$. Then for every $f\in\mathscr{F}_n$ such that $\ell\circ f\in\mathscr{F}(\delta)$
\begin{equation}\label{eq:f-f_n^*}
\begin{aligned}
\|f - f_n^*\| & \leq \|f - f_\phi^*\| + \|f_n^* - f_\phi^*\| \leq c_\phi^{-\frac{1}{2\kappa}}\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^*\right]^{\frac{1}{2\kappa}} + c_\phi^{-\frac{1}{2\kappa}}\triangle_n^{\frac{1}{2\kappa}} \\
& \leq { 2^{1-\frac{1}{2\kappa}}}c_\phi^{-\frac{1}{2\kappa}}\left[\mathcal{R}_\phi(f) - \mathcal{R}_\phi^* + \triangle_n\right]^{\frac{1}{2\kappa}} \leq 2^{1-\frac{1}{2\kappa}}[c_\phi^{-1}(\delta + 2\triangle_n)]^{\frac{1}{2\kappa}},
\end{aligned}
\end{equation}
where the second inequality follows under Assumption~\ref{as:loss_modulus} and the third by Jensen's inequality since $x\mapsto x^{1/2\kappa}$ is concave on $\ensuremath{\mathbf{R}}_+$ for $\kappa\geq 1$. Therefore,
\begin{equation}\label{eq:class_inclusion}
\mathscr{F}(\delta) \subset \left\{\ell\circ f:\; \|f - {f_n^*}\| \leq 2[c_\phi^{-1}(\delta/2 + \triangle_n)]^\frac{1}{2\kappa},\; f\in\mathscr{F}_n \right\}.
\end{equation}
Under Assumptions~\ref{as:losses} (iii) and \ref{as:phi} (ii) for all $f_1,f_2\in\mathscr{F}_n$ and all $(y,x)\in\{-1,1\}\times\mathcal{X}$, we have $|(\ell\circ f_1)(y,x) - (\ell\circ f_2)(y,x)| \leq 4LM|f_1(x) - f_2(x)|$. In conjunction with inequalities in equations (\ref{eq:f-f_n^*}) and (\ref{eq:class_inclusion}) this shows that the $L_2$-diameter of $\mathscr{F}(\delta)$ satisfies $D(\delta) \triangleq \sup_{g_1,g_2\in\mathscr{F}(\delta)}\|g_1-g_2\| \leq 8LM[c_\phi^{-1}(\delta/2 + \triangle_n)]^{\frac{1}{2\kappa}}$, therefore,
\begin{equation*}
(D^2)^{\flat}(\sigma) \triangleq \sup_{\delta\geq\sigma}\frac{D^2(\delta)}{\delta} \leq (8LM)^2c_\phi^{-1/\kappa}\sup_{\delta \geq \sigma }\delta^{\frac{1}{\kappa}-1}[0.5+\triangle_n/\delta]^{\frac{1}{\kappa}} \leq (8LM)^2c_\phi^{-1/\kappa} \sigma^{\frac{1}{\kappa}-1}[0.5+\tau]^{\frac{1}{\kappa}},
\end{equation*}
where $\tau \triangleq \triangle_n/\sigma$. Likewise, it follows from the equation (\ref{eq:class_inclusion}) that
\begin{equation*}
\begin{aligned}
\phi_n(\delta) & \triangleq \ensuremath{\mathbb{E}}\left[\sup_{g_1,g_2\in\mathscr{F}(\delta)}|(P_n - P)(g_1-g_2)|\right] \leq 2\ensuremath{\mathbb{E}}\left[\sup_{g\in\mathscr{F}(\delta)}|(P_n - P)(g-\ell\circ f_n^*)|\right] \\
& \leq 2\ensuremath{\mathbb{E}}\left[\sup_{f\in\mathscr{F}_n:\|f -{f_n^*}\|\leq 2[c_\phi^{-1}(\delta/2 + \triangle_n)]^\frac{1}{2\kappa}}|(P_n - P)(\ell\circ f-\ell\circ f_n^*)|\right] \\
& \leq 4\ensuremath{\mathbb{E}}\left[\sup_{f\in\mathscr{F}_n:\|f - {f_n^*}\| \leq 2[c_\phi^{-1}(\delta/2 + \triangle_n)]^\frac{1}{2\kappa}}|R_n(\ell\circ f-\ell\circ f_n^*)|\right] \\
& \leq 8\ensuremath{\mathbb{E}}\left[\sup_{f\in\mathscr{F}_n:\|f - {f_n^*}\| \leq 2[c_\phi^{-1}(\delta/2 + \triangle_n)]^\frac{1}{2\kappa}}|R_n(f-f_n^*)|\right] \\
& = 8\psi_n\left({4[c_\phi^{-1}}(\delta/2 + \triangle_n)]^\frac{1}{\kappa};\mathscr{F}_n\right),
\end{aligned}
\end{equation*}
where we use the symmetrization and contraction inequalities, see \cite{koltchinskii2011oracle}, Theorems 2.1 and 2.3 since under Assumption~\ref{as:phi} (i), $\phi(0)=1$. This gives
\begin{align*}
\phi_n^\flat(\sigma) &=\sup_{\delta\geq\sigma}\frac{\phi_n(\delta)}{\delta} \leq \sup_{\delta\geq\sigma}\frac{8\psi_n\left(4\delta^\frac{1}{\kappa}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa};\mathscr{F}_n\right)}{\delta} \\
&\leq 32\sigma^{\frac{1}{\kappa}-1}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}\sup_{\delta\geq\sigma}\frac{\psi_n\left(4\delta^\frac{1}{\kappa}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa};\mathscr{F}_n\right)}{4\delta^\frac{1}{\kappa}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}}\\
& = 32\sigma^{\frac{1}{\kappa}-1}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}\psi_n^\flat\left(4\sigma^\frac{1}{\kappa}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}\right).
\end{align*}
Next, by \cite{koltchinskii2011oracle}, Theorem 4.3, there exists $q>1$ such that for every $t>0$
\begin{equation*}
\Pr\left(\mathcal{R}_\phi(\hat f_n) - \mathcal{R}_\phi(f_n^*) \leq \inf\left\{\sigma:\; V_n^t(\sigma) \leq 1 \right\}\right) \geq 1 - c_qe^{-t}
\end{equation*}
with $c_q = \frac{q}{q-1}\vee e$ and
{\footnotesize
\begin{equation*}
\begin{aligned}
V_n^t(\sigma) & \triangleq 2q\left[\phi_n^\flat(\sigma) + \sqrt{\frac{(D^2)^\flat(\sigma)t}{n\sigma}} + \frac{t}{n\sigma}\right] \\
& \leq 64q\sigma^{\frac{1-\kappa}{\kappa}}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}\psi_n^\flat\left(4\sigma^\frac{1}{\kappa}\left[c_\phi^{-1}(0.5+\tau)\right]^\frac{1}{\kappa}\right) + 16LMqc_\phi^\frac{-1}{2\kappa} \sqrt{\frac{[0.5+\tau]^\frac{1}{\kappa}t}{n\sigma^{2-\frac{1}{\kappa}}}} + \frac{2qt}{n\sigma},
\end{aligned}
\end{equation*}}
which follows from our computations above. Note that if $\sigma\geq \triangle_n$, then $\tau = \triangle_n/\sigma\leq 1$, and
\begin{equation*}
V_n^t(\sigma) \leq 16q\sigma^{\frac{1-\kappa}{\kappa}}\left(\frac {4^{\kappa}3 }{2c_\phi}\right)^\frac{1}{\kappa}\psi_n^\flat\left(\left[\frac{4^\kappa 3\sigma}{2c_\phi}\right]^{1/\kappa}\right) + 16qLM\left(\frac 3{2c_\phi}\right)^\frac{1}{2\kappa} \sqrt{\frac{t}{n\sigma^{2-\frac{1}{\kappa}}}} + \frac{2qt}{n\sigma}.
\end{equation*}
Since all functions in this upper bound are decreasing in $\sigma$, we have $V_n^t(\sigma)\leq 1$ as soon as
\begin{equation*}
\sigma\geq\frac{2c_\phi}{4^\kappa 3} \psi_{n,\kappa}^{\sharp}\left( \frac{c_\phi}{72q4^\kappa}\right)\vee \left(\frac{3(48qLM)^{2\kappa}t^\kappa}{2c_\phi n^\kappa}\right)^\frac{1}{2\kappa-1}\vee \frac{6qt}{n}.
\end{equation*}
Therefore, since $\inf\{\sigma \leq \triangle_n:\; V_n^t(\sigma)\leq 1\}\leq \triangle_n$, we obtain with $\epsilon= c_\phi/(72q4^\kappa)$
\begin{equation*}
\inf\{\sigma:\; V_n^t(\sigma)\leq 1 \}\leq \frac{2c_\phi}{4^\kappa3}\psi_{n,\kappa}^{\sharp}(\epsilon)\vee \left(\frac{3(48qLM)^{2\kappa}t^\kappa}{2c_\phi n^\kappa}\right)^\frac{1}{2\kappa-1}\vee \frac{6qt}{n} + \triangle_n.
\end{equation*}
This shows that in conjunction with the inequality in equation~(\ref{eq:convexified_bound}), for every $t>0$ with probability at least $1-c_qe^{-t}$
\begin{equation*}
\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^* \leq C_\phi\left[\frac{2c_\phi}{4^\kappa3}\psi_{n,\kappa}^{\sharp}(\epsilon)\vee \left(\frac{3(48qLM)^{2\kappa}t^\kappa}{2c_\phi n^\kappa}\right)^\frac{1}{2\kappa-1}\vee \frac{6qt}{n} + 2\triangle_n \right]^\frac{\gamma(\alpha+1)}{\gamma\alpha+1}.
\end{equation*}
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:parametric_predictions}]
By \cite{koltchinskii2011oracle}, Proposition 3.2, for the linear class $\mathscr{F}_n=\{f_\theta(x)=\sum_{j=1}^p\theta_j\varphi_j(x): \theta\in\ensuremath{\mathbf{R}}^p\}$, the local Rademacher complexity is bounded as $\psi_n(\delta;\mathscr{F}_n) \leq \sqrt{\delta p/n}$. This gives $\psi_n^\flat(\sigma) \leq \sqrt{p/(\sigma n)}$, and so $\psi^{\sharp}_{n,\kappa}(\epsilon) \leq \left(p/(n\epsilon^2)\right)^\frac{\kappa}{2\kappa - 1}$. Therefore, by Theorem~\ref{thm:oracle inequality} for every $t>0$,
\begin{equation*}
\Pr\left(\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right]^\frac{\gamma\alpha+1}{\gamma(\alpha+1)} > K\left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + tn^{-\frac{\kappa}{2\kappa - 1}} + \triangle_n \right]\right)\leq c_qe^{-t}.
\end{equation*}
where we use $t^{\kappa/(2\kappa - 1)} \leq p\vee t$ since $\kappa\geq 1$, $\epsilon,c_q,C_\phi>0,q>1\triangle_n$ as defined in the proof of Theorem~\ref{thm:oracle inequality}, and put $K\triangleq C_\phi^\frac{\gamma\alpha+1}{\gamma(\alpha+1)}\left(\frac{2c_\phi}{4^\kappa3}\epsilon^{-\frac{2\kappa}{2\kappa-1}}\vee\left[\frac{3(48qLM)^{2\kappa}}{2c_\phi}\right]^{1/(2\kappa-1)}\vee 6q\vee 2\right)$. Integrating the tail bound
\begin{equation*}
\begin{aligned}
\ensuremath{\mathbb{E}}\left[\left(\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right)^\frac{\gamma\alpha+1}{\gamma(\alpha+1)}\right] & = \int_0^\infty\Pr\left(\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right]^\frac{\gamma\alpha+1}{\gamma(\alpha+1)} > u\right)\ensuremath{\mathrm{d}} u \\
& \leq Kn^{-\frac{\kappa}{2\kappa - 1}}\left\{n^\frac{\kappa}{2\kappa - 1}\left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + \triangle_n\right] + \int_0^\infty c_qe^{-t}\ensuremath{\mathrm{d}} t\right\} \\
& \leq K\left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + \triangle_n\right] + Kc_qn^{-\frac{\kappa}{2\kappa - 1}},
\end{aligned}
\end{equation*}
where the second line follows by the change of variables $u = K\left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + tn^{-\frac{\kappa}{2\kappa - 1}} + \triangle_n \right]$ and bounding the probability by $1$ for $t<0$. Since $\gamma\in(0,1]$, by Jensen's inequality, this gives
\begin{equation*}
\begin{aligned}
\ensuremath{\mathbb{E}}\left[\mathcal{R}(\ensuremath{\mathrm{sign}}(\hat f_n)) - \mathcal{R}^*\right] & \leq \left\{K\left[\left(\frac{p}{n}\right)^\frac{\kappa}{2\kappa - 1} + \triangle_n\right] + Kc_qn^{-\frac{\kappa}{2\kappa - 1}} \right\}^\frac{\gamma(\alpha+1)}{\gamma\alpha+1}.
\end{aligned}
\end{equation*}
\end{proof}
\bibliographystyle{abbrvnat}
\bibliography{references}
\clearpage