In Table <ref>, we present results comparing performance of the Frank-Wolfe, GDA and ellipsoid algorithms with the plug-in and weighted logistic regression LMOs when run for 20 iterations. Appendix <ref> contains results of these experiments when the algorithms are allowed 100 iterations. The performance with the two LMOs are comparable on Abalone and SatImage. On PageBlocks and CovType, weighted logistic regression has a moderate to significant advantage. Interestingly, on MACHO, the plug-in based LMO, despite learning from a less flexible hypothesis class (post-hoc adjustments to a fixed model), is substantially better. This is because weighted logistic regression over-fits to the training set in this case.

Overall, we find that an LMO such as weighted logistic regression,
while being computationally expensive, does sometimes provide metric gains over a less-flexible plug-in type approach. However, this method can be prone to over-fitting because of its added flexibility.

§.§ Case Study: Image Classification with Imbalance and Label Noise

As case studies, we demonstrate two natural workflows our algorithms in  (i) tackling label imbalance in CIFAR-55 and (ii) mitigating label noise in a noisy version of CIFAR-10.

§.§.§ Class Imbalance with Large Number of Classes

One of the undesirable effects of learning with a class-imbalanced dataset is that the
learned classifier tends to over-predict classes that are more prevalent and under-predict classes that are rare. We consider two approaches to avoid this problem:  minimizing a loss such as the H-mean that emphasizes equal performance across all classes, and  constraining the proportions of predictions the classifier makes for each class to match the true prevalence of the class.

For this experiment, we use the  CIFAR-100 dataset <cit.>, which contains images labelled with one of 100 classes.
We create an imbalanced 55-class dataset by merging 50 classes in CIFAR-100 into 5 “super-classes” (see Appendix <ref> for details), and leaving the rest of the classes untouched.
In the resulting class distribution, 5 of the classes are 10 times more prevalent than the remaining 50.

All our methods use a plug-in based LMO which uses a pre-trained class probability estimator.
We train a ResNet-50 model for the class probability estimator, using SGD to minimize the standard cross-entropy loss. We use a batch size of 64, a base learning rate of 0.01
(with a warm-up cosine schedule), and a momentum of 0.9. We apply a weight decay of 0.01 and train for 39 epochs.

In Table <ref>, we analyze the  performance of a ResNet-50 model trained with the standard cross-entropy loss (Plugin [0-1]), where the class that receives the highest estimated probability is predicted as the output label, and report its 0-1 loss, its H-mean loss, and the deviation of its class prediction rates from the prior probabilities, i.e. its maximum coverage violation: $\max_{i\in[n]}|\sum_{j}C_{ji} \,-\, \pi_i|$.
We find that naïvely optimizing for the 0-1 loss yields a high coverage violation. Moreover, it yields high accuracies on the 5 super-classes, at the cost of a much lower accuracy on the 50 minority classes, resulting in a high H-mean loss. To emphasize better performance on the minority classes, we train classifiers to minimize the H-mean loss (FW [H-mean]), and minimize the 0-1 loss subject to the maximum coverage violation being within a tolerance of 0.01 (SplitFW [0-1]). We also consider a combination of both, i.e. minimizing the H-mean loss subject to the maximum coverage violation being within 0.01 (SplitFW [H-mean]). It can be seen that all three algorithms do only slightly worse than the Plugin [$\zo$] baseline in terms of 0-1 loss, but do significantly better in terms of both the H-mean loss and the coverage violation.

Results on CIFAR-55 imbalanced dataset. The train and test sets are imbalanced, with 5 classes being 10 times larger in size than the remaining 50 classes. We report the 0-1 loss, the H-mean loss, and the coverage violation $\max_{i\in[n]}|\sum_{j}C_{ji} \,-\, \pi_i| - 0.01$. Lower values are better.

3cTrain (Imbalanced)
3cTest (Imbalanced)

Plugin [$\zo$]         0.278     0.457     0.030     0.437     0.709     0.045

FW [H-mean]            0.307     0.323     0.026     0.481     0.564     0.029

SplitFW [$\zo$]        0.279     0.391     0.000     0.436     0.636     0.007

SplitFW [H-mean]       0.279     0.342     0.000     0.448     0.595     0.000

§.§.§ Class Imbalance with Label Noise
Our next experiment demonstrates how label noise can be mitigating by imposing coverage constraints on the classifier. We use a class-imbalanced version of the CIFAR-10 dataset <cit.>, where we sub-sample images from classes 1 to 5 by a factor of 10, with the resulting class priors are given by $\pi_y = \frac{2}{110}$ when $y\in\{1,2,3,4,5\}$ and $\pi_y=\frac{2}{11}$ otherwise. Our algorithms assume the knowledge of $\pi$.

In addition to class imbalance,
very often one has to work with noisy training labels to building a classifier that performs well on uncorrupted test data. We simulate this scenario by adding a label noise corruption to the training data, which is chosen such that classes 1 to 9 are left undisturbed, and the labels of images from class 10 are randomly chosen from 1 to 10. This effectively mimics a crowd-sourced label collection with 9 easy labels, and one difficult or incomprehensible label. Our algorithms do not have knowledge of this corruption.

Equipped with the knowledge of the class priors $\pi$, we propose constraining the proportion of predictions made for each class to match the priors $\pi$. While this is not necessarily equivalent to training the classifier with uncorrupted labels, we expect that these additional coverage constraints will dampen the effect of the noisy labels. As with the previous experiment, we evaluate the classifier on two criteria: (i) how well it performs on the (balanced) H-mean metric on the test data, and (ii) how well the class prediction rates match the priors $\pi$ on the test data. Our framework can be applied to this problem by minimizing the H-mean error on the corrupted training dataset, subject to a coverage constraint on the classifier forcing it to predict classes at a rate that matches $\pi$.

In addition to a  ResNet model baseline that optimizes the cross-entropy loss (Plugin [$\zo$]), we include the state-of-the-art method of <cit.>, which uses the predictions from Plugin [$\zo$] on the training data to compute an estimate of the label noise transition matrix, and re-trains the classifier with a (forward) correction computation applied to the loss (Noise Correction [Estimate]). For completeness, we also include an idealized version of this method, where the “exact” noise transition matrix is used for the forward correction (Noise Correction [Exact]). While this baseline is unrealistic, it provides us with an estimate best possible 0-1 loss achievable for this problem.

We provide the result of this experiment in Table <ref>,

where FW [H-mean] corresponds to a classifier that minimizes the H-mean loss on the corrupted training dataset, and
SplitFW [0-1] (resp. SplitFW [H-mean]), correspond to a classifier that minimizes the 0-1 loss (resp. H-mean loss) on the corrupted training dataset, while enforcing the coverage constraint to a tolerance of $0.01$. All three methods use the same underlying class probability model as Plugin [$\zo$].

It is seen that only SplitFW [0-1] and SplitFW [H-mean] achieve low coverage violations on the test set, and are still only moderately worse than the idealized Noise Correction [Exact] method in terms of their respective objective metrics. The FW [H-mean] algorithm achieves the best H-mean on clean test data despite being trained on the corrupted training labels.

Results on imbalanced CIFAR-10 dataset with label noise. The train set is imbalanced and has label noise, while the test set is imbalanced but clean. We report the 0-1 loss, the H-mean loss, and the  coverage violation $\max_{i\in[n]}|\sum_{j}C_{ji} \,-\, \pi_i| - 0.01$. Lower values are better.

3cTrain (Flipped)
3cTest (Imbalanced)

Plugin [$\zo$]
0.266     0.896     0.170     0.332     0.899      0.169

Noise Correction [Estimate]
0.174     0.370      0.054     0.179      0.430     0.055

FW [H-mean]
0.348     0.481     0.072     0.329     0.396     0.076

SplitFW [$\zo$]
0.272     0.609     0.001     0.196     0.610      0.004

SplitFW [H-mean]
0.292     0.523     0.003     0.221     0.471     0.003

Noise Correction [Exact]
0.196     0.394     0.022     0.151      0.358     0.018

§ CONCLUSIONS

We have developed a  framework for designing  consistent and efficient algorithms for multiclass performance metrics and constraints that are general functions of the confusion matrix. As instantiations of this framework, we provided four algorithms for optimizing unconstrained metrics, and four analogous counterparts for solving constrained learning problems. In each case, we have shown convergence guarantees for the algorithms under different assumptions on the performance metrics and constraints.

Our key idea was to reduce the complex learning problem into a sequence of linear minimization problems, for which we recommended an efficient plug-in based approach that applies a post-hoc transformations to a pre-trained class probability model. The results of these linear minimization problems are then combined to return a final classifier. One of the main challenges in instantiating this  idea was to identify optimization algorithms for different problem settings that only required access to a linear minimization oracle (LMO).

We also presented extensive experiments on a variety of multiclass and fairness datasets and demonstrated that the proposed algorithms (despite being limited to performing adjustments to a fixed model) are competitive or better than the state-of-the-art TFCO approach <cit.> which works with a more flexible hypothesis class. We additionally provided precise guidance for which of the proposed algorithms are best suited for a given multiclass problem, and highlighted scenarios where one might want to use a more expensive LMO that trains a new classifier from scratch at each iteration.

Over the years, the conference versions of this paper have attracted several follow-up works, which have adapted our ideas to
optimizing multiclass extensions of the F-measure <cit.>,
to balancing accuracy with fairness objectives <cit.>,
to eliciting multi-class performance metrics <cit.>,
to training classifiers to optimize more general multi-output classification metrics <cit.>,
to imposing fairness constraints with overlapping protected groups <cit.>,
and to optimizing black-box evaluation metrics <cit.>.

A number of follow-up directions arise from the proposed framework. First, it would interesting to derive lower bounds on the number of calls to the LMO needed under different assumptions on the performance metrics and constraints.

Second, while the optimality (and feasibility) gap for most of our proposed algorithms depend linearly on the LMO approximation errors $\rho$ and $\rho'$, the split Frank-Wolfe method (Algorithm <ref> alone has a square-root dependence on these parameters. Are these dependencies on the LMO errors optimal or simply artifacts of the analysis?

Third, for algorithms where the  convergence rates have a linear (or quadratic) dependence on the dimension of the problem $d$ (which is typically the same order as the number of classes), how does one extend our framework to handle problems with an extremely large number classes (perhaps under additional structural assumptions on the classes, akin to <cit.>) and problems with an extremely large number of constraints <cit.>?

Fourth, our experiments in Section <ref> show that in some applications, using a flexible LMO that trains a classifier from scratch can yield significant gains over a plug-in based LMO, but this however comes at the cost of added computational time. Can one devise an intermediate approach, where each call to the LMO only needs to run a constant number of optimization steps on a surrogate loss (akin to the TFCO baseline of <cit.>), while still guaranteeing that the outer algorithm provably convergences to the optimal (feasible) classifier?

Finally,  except for the bisection method, all the  algorithms we propose rely on the use of a randomized classifier. In some applications, deploying a randomized classifier can be undesirable for  ethical reasons or because of the engineering difficulties it poses. In these scenarios, one could approximate the learned randomized classifier with a deterministic classifier using, for example, the approach of <cit.>. Understanding the loss in performance and constraint satisfaction as a result of such de-randomization procedures is an interesting direction for future work.

§ ACKNOWLEDGEMENTS

The authors thank Aadirupa Saha for providing helpful inputs and for running experiments for a conference version of this paper <cit.>. HG thanks the Robert Bosch Centre for Data Science and Artificial Intelligence for their support. HN thanks Pavlos Protopapas, IACS, Harvard University, for providing us access to the MACHO celestial object detection dataset.

Table of notations.

Notation     Description

$n$     Number of classes

$N$     Number of training examples

$m$     Number of protected groups

$K$     Number of constraints

$d$     Dimension of the vector representation for the confusion matrix

$T$     Number of iterations for the proposed iterative algorithms

$i,j$     Indices over $n$ classes

$a$     Index over $m$ protected groups

$k$     Index over $K$ constraints

$t$     Index over $T$ iterations

$\ell$     Index over $N$ training instances
$\C$     $n \times n$ Confusion matrix, or an equivalent vector representation of dimension $d=n^2$

$\L$     $n \times n$ Loss matrix, or an equivalent vector representation of dimension $d=n^2$

$\cC$     Set of achievable confusion matrices, represented by vectors of dimension $d=n^2$

$S$     Training sample with $N$ instances

§ PROOFS

§.§ Proof of Proposition <ref> (Bayes-optimal Classifier for Ratio-of-linear $\psi$)

[(Restated) Bayes optimal classifier for ratio-of-linear $\psi$]
Let the performance measure $\psi:[0,1]^{d}\>\R_+$ in <ref> be of the form $\psi^\rl(\C) = \frac{\langle \A,\C \rangle}{\langle \B, \C \rangle}$ for some $\A,\B\in\R^{d}$ with $\langle \B,\C \rangle > 0 ~\forall \C\in\cC$.
Let $t^*=\inf_{\C\in\cC} \psi(\C)$ and
$\L^* = \A - t^*\B$.
Then any classifier that is optimal for the linear metric $\langle \L^*, \C \rangle$ is also optimal for <ref>.

We will find the following lemma useful in the proof of the proposition.

Let $\psi:[0,1]^d\>\R_+$ be such that $\psi(\C) = \frac{\langle \A,\C \rangle}{\langle \B, \C \rangle},$
for some matrices $\A,\B\in\R^{d}$ with $\langle \B,\C \rangle > 0$ for all $\C\in\cC$. Let $t^*=\inf_{\C\in\cC} \psi(\C)$. Then $\inf_{\C\in\cC} \langle \A - t^* \B, \C \rangle = 0.$

Define $\varphi:\R\>\R$ as $\varphi(t) =\inf_{\C\in\cC} \langle \A - t\B, \C \rangle.$ It is easy to see that $\varphi$ (being a point-wise supremum of linear functions) is convex, and hence a continuous function over $\R$.
Let $t^*=\inf_{\C\in\cC} \psi(\C)$.
We then have for all $\C\in\cC$,

\begin{eqnarray*}
\frac{\langle \A,\C \rangle}{\langle \B, \C \rangle} \,\geq\, t^* ~~~\text{or equivalently}~~~
\varphi(t^*) \,=\, \langle \A - t^* \B , \C \rangle \,\geq \, 0.
\end{eqnarray*}

\begin{eqnarray}
\varphi(t^*)= \sup_{\C\in\cC} \langle \A - t^*\B, \C \rangle \geq 0 \;. \label{eqn:lem-ratio-lin-1}
\end{eqnarray}

Also, by continuity of $\frac{\langle \A,\C \rangle}{\langle \B, \C \rangle}$ in $\C$, for any $t<t^*$, there exists $\C\in\cC$ such that

\begin{eqnarray*}
\frac{\langle \A,\C \rangle}{\langle \B, \C \rangle} \,>\, t ~~~\text{or equivalently}~~~
\varphi(t) \,=\, \langle \A - t \B , \C \rangle \,<\, 0.
\end{eqnarray*}

Thus for all $t<t^*$,

$$\varphi(t)= \inf_{\C\in\cC} \langle \A - t\B, \C \rangle < 0 \;.$$

Next, by continuity of $\varphi$, for any monotonically increasing sequence of real numbers $\{t_i\}_{i=1}^\infty$ converging to $t^*$, we have that $\varphi(t_i)$ converges to $\varphi(t^*)$; since for each $t_i$ in this sequence $\varphi(t_i) < 0$, at the $t^*$, we have that $\varphi(t^*)\geq 0$. Along with (<ref>), this gives us

$$\inf_{\C\in\cC} \langle \A - t^*\B, \C \rangle = \varphi(t^*) = 0,$$

as desired.

We are now ready to prove Proposition <ref>.

Let $\h^*:\X\>\Delta_n$ be a classifier that is optimal for $\L^* = \A - t^*\B$, i.e.,

\[
\langle \A - t^* \B, \C[\h^*] \rangle
\,=\,
\inf_{\C\in\cC} \langle \A - t^* \B, \C \rangle.
\]

Note from Lemma <ref> that $\langle \A - t^* \B, \C[\h^*] \rangle  = 0$. Hence,

\begin{eqnarray*}
\frac{\langle \A, \C[\h^*]\rangle}{\langle \B, \C[\h^*] \rangle} \,=\, t^*,
\text{or equivalently},~~~~
\psi(\C[\h^*])
\,=\,
\inf_{\C\in\cC} \psi(\C),
\end{eqnarray*}

which shows that $h^*$ is also $\psi$-optimal.

§.§ Proof of Proposition <ref> (Bayes-optimal Classifier for Monotonic $\psi$)

[(Restated) Bayes-optimal classifier for monotonic $\psi$]
Let the performance measure $\psi:[0,1]^{d}\>\R_+$ in <ref> be differentiable and bounded, and be monotonically decreasing in $C_{ii}$ for each $i$ and non-decreasing in $C_{ij}$ for all $i,j$. Let   $\boldeta(X)$
be a continuous random vector.

Then there exists a loss matrix $\L^*$ (which depends on $\psi$ and $D$) such that any classifier that is optimal for the linear metric given by $\L^*$ is also optimal for <ref>.

Let $\overline{\cC}$ denote the closure of $\cC$.
We will find the following lemma crucial to our proof.

be a continuous random vector.

Let $\L\in\R^d$ be such that no two columns are identical. Then,

\[
\argmin_{\C\in\overline{\cC}}\, \langle \L, \C \rangle \,=\, \argmin_{\C\in\cC} \langle \L, \C \rangle.
\]

Moreover, the above set is a singleton.

The proof for the lemma is highly technical and can be found in the conference version of the paper, specifically Lemma 12 in <cit.>.

Let $\C^*=\argmin_{\C\in\overline{\cC}} \psi(\C)$. Such a $\C^*$ always exists by compactness of $\overline{\cC}$ and continuity of $\psi$.
By first order optimality, and convexity of $\overline{\cC}$, we have that for all $\C\in\overline{\cC}$

$$ \langle \nabla\psi(\C^*), \C^* \rangle \leq \langle \nabla\psi(\C^*), \C \rangle \;.$$

For $\L^* = \nabla\psi(\C^*)$,  we have that
$\C^* \in \argmin_{\C\in\overline{\cC}} \langle \L^*, \C \rangle.$

Due to the monotonicity condition on $\psi$ the diagonal elements of its gradient $\nabla\psi(\C^*)$ are positive, and the off-diagonal elements are non-positive, and hence no two columns of  $\L^*$ are identical. Thus by a direct application of Lemma <ref>, we have that $\C^*\in\cC$, and moreover $\C^*$ is the unique minimizer of $\langle \L^*, \C \rangle$ over all $\C \in \cC$.

§.§ Proof of Proposition <ref> (Bayes-optimal Classifier for Continuous $\psi, \phi_1,\ldots, \phi_K$)

[Bayes optimal classifier for continuous $\psi, \phi_1,\ldots, \phi_K$]
Let the performance measure $\psi: [0,1]^{d}\>\R_+$ and the constraint functions $\phi_1, \ldots, \phi_K: [0,1]^{d}\>\R$ in <ref> be continuous and bounded. Then there exists $d+1$ loss matrices $\L^*_1, \L^*_2, \ldots, \L^*_{d+1}$ (which can depend on $\psi, \phi_k$'s and $D$)
such that an optimal classifier for <ref> can be expressed as a randomized combination of the deterministic classifiers $h_1, h_2, \ldots, h_{d+1}$, where $h_i$ is optimal for the linear metric
given by $\L^*_i$.

We first note that $\cC$ is a compact set, and as a result there exists an optimal-feasible solution $\C^*$ for <ref> in $\cC$. It is straightforward to see that $\cC$ is bounded. To see that $\cC$ is closed,
note that from Proposition <ref>,  any linear function over $\cC$ is minimized by some confusion matrix in $\cC$. Since every extreme point is a unique minimizer of a linear function in $\cC$, every extreme point of  $\cC$ is also in $\cC$. It follows that all convex combinations of the extreme points of $\cC$ are also in $\cC$ and as a result, so are all its limit points.

Now to prove the characterization in the proposition, let us use $\cE$ to denote the set of extreme points of $\cC$. By Krein–Milman theorem, we have that because $\cC$ is a compact convex set, it is equal to the convex hull of $\cE$ <cit.>. We further have from Carathéodory's theorem that any $\C \in \cC$ can be the be expressed as a convex combination of $d+1$ points in $\cE$ <cit.>. Since $\C^*$ is in $\cC$, we have that there exists $d+1$ confusion matrices $\C^*_1, \ldots, \C^*_{d+1} \in \cE$ and coefficients $\balpha \in \Delta_{d+1}$ such that $\C^* = \sum_{i=1}^{d+1}\alpha_i\,\C^*_i$.

Next, because each $\C^*_i$ is an extreme point of $\cC$, there exists a supporting hyperplane $\L^*_i$ for $\cC$ at $\C^*_i$ such that $\langle \L^*_i, \C^*_i \rangle \leq \langle \L^*_i, \C \rangle,\, \forall \C \in \cC$. Moreover, owing to $\C^*$ being an extreme point, it is also the unique minimizer of the linear function $\langle \L^*_i, \C \rangle$. Furthermore, because Proposition <ref> tells us that there exists a deterministic classifier $h_i$ that is optimal for the linear metric $\langle \L^*_i, \C \rangle$, it follows that  $\C[h^*_i] = \C^*_i$. Consequently, we have that the randomized classifier $h^* = \sum_{i=1}^m \alpha_i h_i$ is an optimal feasible solution for <ref>, i.e. $\C[h^*] = \sum_{i=1}^m\alpha_i \C[h_i] = \sum_{i=1}^m\alpha_i \C^*_i = \C^*$.

§.§ Proof of Theorem <ref> (Frank-Wolfe for Unconstrained Problems)

[(Restated) Convergence of FW algorithm]
Fix $\epsilon \in (0,1)$.
Let $\psi: [0,1]^d \> [0,1]$ be convex, and $\beta$-smooth and $L$-Lipschitz w.r.t. the $\ell_2$-norm. Let $\Omega$ in Algorithm <ref> be a $(\rho , \rho', \delta)$-approximate LMO for sample size $m$.
Let $\bar{h}$ be a classifier returned by Algorithm <ref> when run for $T$ iterations.
Then with probability $\geq 1 - \delta$ over draw of $S \sim D^N$, after $T = \cO(1/\epsilon)$ iterations:

\[
\psi(\C[\bar{h}]) \,\leq\, \min_{\C \in \cC}\,\psi(\C) \,+\,\cO\left(\beta\epsilon \,+\, L\rho +\beta\sqrt{d}\rho'\right).
\]

We first prove an important lemma where we bound the approximation error of the linear minimization oracle used in the algorithm. This result coupled with the standard convergence analysis for the Frank-Wolfe method <cit.> will then allow us to prove the above theorem.

Let $\psi: [0, 1]^d \> \R_+$ be convex over $\cC$, and $L$-Lipschitz and $\beta$-smooth w.r.t. the $\ell_2$ norm. Let classifiers $\tilde h^1,\ldots,\tilde h^T$, and $h^0,h^1,\ldots,h^T$ be as defined in Algorithm <ref>. Then for any $\delta \in (0, 1]$, with probability at least $1-\delta$ (over draw of $S$ from $D^N$), we have for all $1\leq t \leq T$

\begin{eqnarray*}
\langle \nabla\psi(\C[h^{t-1}]), \C[\tilde h^t] \rangle \leq \min_{\g:\X:\>\Delta_n} \langle \nabla\psi(\C[h^{t-1}]), \C[\g] \rangle + L\rho + 2\beta\sqrt{d}\rho'.
\end{eqnarray*}

For any $1\leq t \leq T$, let
$\g^{t,*}\in \argmin_{\g:\X\>\Delta_n} \langle \nabla\psi(\C[h^{t-1}]), \C[\g] \rangle.$ We then have

\begin{eqnarray*}
\lefteqn{
\min_{\g:\X:\>\Delta_n} \langle \nabla\psi(\C[h^{t-1}]), \C[\g] \rangle
\,-\,
\langle \nabla\psi(\C[h^{t-1}]), \C[\tilde h^t] \rangle}
\hspace{1cm}
\\
\langle \nabla\psi(\C[h^{t-1}]), \C[\g^{t,*}] \rangle
\,-\,
\langle \nabla\psi(\C[h^{t-1}]), \C[\tilde h^t] \rangle
\\
\underbrace{
\langle \nabla\psi(\C[h^{t-1}]), \C[\g^{t,*}] \rangle
\,-\,
\langle \nabla\psi(\C^{t-1}), \C[ g^{t,*}] \rangle
&& \hspace{2cm}
\,+\,
\underbrace{
\langle \nabla\psi(\C^{t-1}), \C[ g^{t,*}] \rangle
\,-\,
\langle \nabla\psi(\C^{t-1}), \C[\tilde h^t] \rangle
&& \hspace{2cm}
\,+\,
\underbrace{
\langle \nabla\psi(\C^{t-1}), \C[\tilde h^t] \rangle
\,-\,
\langle \nabla\psi(\C[h^{t-1}]), \C[\tilde h^t] \rangle}
\end{eqnarray*}

We next bound each of these terms. We start with $\text{term}_2$. For any $1\leq t \leq T$, let $\L^t$ be as defined in Algorithm <ref>.

For all $1\leq t \leq T$,

\begin{eqnarray*}
\langle \nabla\psi(\C^{t-1}), \C[\g^{t,*}] \rangle - \langle \nabla\psi(\C^{t-1}), \C[\tilde h^t] \rangle
\|\nabla\psi(\C^{t-1})\|_\infty ( \langle \L^t, \C[\tilde h^t] \rangle - \langle \L^t, \C[\g^{t,*}] \rangle ) \nonumber \\
\|\nabla\psi(\C^{t-1})\|_2 ( \langle \L^t, \C[\tilde h^t] \rangle - \langle \L^t, \C[\g^{t,*}] \rangle ) \nonumber \\
L\rho, \label{eqn:lem-apx-1}
\end{eqnarray*}

which follows from the property of the LMO (in Definition <ref>) and from $L$-Lipchitzness of $\psi$, and holds with probability at least $1-\delta$ (over draw of $S$).

Next, for $\text{term}_1$, we have by an application of Holder's inequality

\begin{eqnarray*}
\lefteqn{\langle \nabla\psi(\C[h^{t-1}]), \C[\g^{t,*}] \rangle
\,-\,
\langle \nabla\psi(\C^{t-1}), \C[ g^{t,*}] \rangle}
\hspace{3cm}
\\
\big\|\nabla\psi(\C^{t-1}) - \nabla\psi(\C[h^{t-1}]) \big\|_\infty
\|\C[\g^{t,*}]\|_1\\
&=& \big\|\nabla\psi(\C^{t-1}) - \nabla\psi(\C[h^{t-1}]) \big\|_\infty (1)\\
&=& \big\|\nabla\psi(\C^{t-1}) - \nabla\psi(\C[h^{t-1}]) \big\|_2\\
\beta \big\| \C^{t-1} - \C[h^{t-1}] \big\|_2 \nonumber \\
\beta \sqrt{d}\big\| \C^{t-1} - \C[h^{t-1}] \big\|_\infty \nonumber \\
\beta \sqrt{d} \rho', \label{eqn:lem-apx-2}
\end{eqnarray*}

where the third step follows from $\beta$-smoothness of $\psi$; the last step uses the property of the LMO and holds with probability at least $1-\delta$ (over draw of $S$).
One can similarly bound $\text{term}_3$. We thus have for all $1\leq t \leq T$, with probability at least $1-\delta$ (over draw of $S$),

\begin{eqnarray*}
{\max_{\g:\X\>\Delta_n} \langle \nabla\psi(\C[h^{t-1}]), \C[\g] \rangle  - \langle \nabla\psi(\C[h^{t-1}]), \C[\tilde h^t] \rangle }
L \rho + 2\beta\sqrt{d}\rho',
\end{eqnarray*}

as desired.

We are now ready to prove Theorem <ref>.

Our proof shall make use of
the standard convergence result for the Frank-Wolfe algorithm for minimizing a convex function over a convex set <cit.>. We will find it useful to first define the following quantity, referred to as the curvature constant in <cit.>.

\begin{eqnarray*}
\sup_{\C_1,\C_2\in\cC, \gamma\in[0,1]} \frac{2}{\gamma^2} \Big( \psi\big(\C_1+\gamma(\C_2-\C_1)\big) -\psi\big(\C_1\big) - \gamma \big\langle \C_2-\C_1,\nabla\psi(\C_1) \big\rangle \Big).
\end{eqnarray*}

Also, define two positive scalars $\epsilon_S$ and $\delta_\text{apx}$ required in the analysis of <cit.>:

\begin{eqnarray*}
\epsilon_S &=& L\rho + 2\beta\sqrt{d}\rho'\\
\delta_\text{apx} &=& \frac{(T+1)\epsilon_S}{C_\psi},
\end{eqnarray*}

where $\delta \in (0, 1]$ is as in the theorem statement. Further, let the classifiers $\tilde h^1,\ldots,\tilde h^T$, and $h^0,\ldots,h^T$ be as defined in Algorithm <ref>.
We then have from Lemma <ref> that the following holds with probability at least $1-\delta$, for all $1\leq t \leq T$,

\begin{eqnarray}
\left\langle \nabla\psi\left(\C[h^{t-1}]\right), \C[\tilde h^t] \right\rangle
&\leq& \min_{\g:\X:\>\Delta_n} \left\langle \nabla\psi\left(\C\left[h^{t-1}\right]\right), \C\left[\g\right] \right\rangle + \epsilon_S \nonumber \\
&=& \min_{\C\in\cC} \left\langle \nabla\psi\left(\C\left[h^{t-1}\right]\right), \C \right\rangle + \epsilon_S \nonumber \\
%  &=& \min_{\C\in\ocC} \left\langle \nabla\psi\left(\C\left[h^{t-1}\right]\right), \C \right\rangle - \epsilon_S \nonumber \\
&=& \min_{\C\in\ocC} \left \langle \nabla\psi\left(\C\left[h^{t-1}\right]\right), \C \right \rangle + \frac{1}{2}\delta_\text{apx} \frac{2}{T+1} C_\psi \nonumber \\
&\leq& \min_{\C\in\ocC} \langle \nabla\psi\left(\C\left[h^{t-1}\right]\right), \C \rangle + \frac{1}{2}\delta_\text{apx} \frac{2}{t+1} C_\psi \;. \label{eqn:FW-iterates-prop-2}
\end{eqnarray}

Also observe that for the two sequences of iterates given by the confusion matrices of the above classifiers,

\begin{eqnarray}
\C[h^t] &=& \left(1-\frac{2}{t+1}\right)\C[h^{t-1}] + \frac{2}{t+1} \C[\tilde h^t], \label{eqn:FW-iterates-prop-1} \;.
\end{eqnarray}

for all $1\leq t \leq T$. Based on (<ref>) and (<ref>), one can now apply the result of <cit.>.

In particular, the sequence of iterates $\C[h^0],\C[h^1],\ldots,\C[h^T]$ can be considered as the sequence of iterates arising from running the Frank-Wolfe optimization method to minimize $\psi$ over $\overline\cC$ with a linear optimization oracle that is $\frac{1}{2}\delta_\text{apx} \frac{2}{t+1} C_\psi$ accurate at iteration $t$. Since $\psi$ is a convex function over the convex constraint set $\ocC$, one has from  Theorem 1 in <cit.> that the following convergence guarantee holds with probability at least $1-\delta$:

\begin{eqnarray}
\psi(\C[\bar{h}]) ~=~ \psi(\C[h^T])
&\leq& \min_{\C\in\ocC} \psi(\C) + \frac{2C_\psi}{T+2} (1+\delta_\text{apx})  \nonumber\\
&=& \min_{\C\in\ocC} \psi(\C) + \frac{2C_\psi}{T+2} + \frac{2\epsilon_S (T+1)}{T+2}  \nonumber \\
&\leq& \min_{\C\in\ocC} \psi(\C) + \frac{2C_\psi}{T+2} +2\epsilon_S  \label{eqn:jaggi}
\end{eqnarray}

We can further upper bound $C_\psi$
in terms of the the smoothness parameter of $\psi$:

\begin{eqnarray*}
\sup_{\C_1,\C_2\in\cC, \gamma\in[0,1]} \frac{2}{\gamma^2} \Big( \psi\big(\C_1+\gamma(\C_2-\C_1)\big) -\psi\big(\C_1\big) - \gamma \big\langle \C_2-\C_1,\nabla\psi(\C_1) \big\rangle \Big)\\
\sup_{\C_1,\C_2\in\cC, \gamma\in[0,1]} \frac{2}{\gamma^2} \Big( \frac{\beta}{2} \gamma^2||\C_1-\C_2||^2_2 \Big)
%  \\
%  &=&
\end{eqnarray*}

where the second step follows from the $\beta$-smoothness of $\psi$. Substituting back in (<ref>), we finally have with probability at least $1-\delta$,

\begin{eqnarray*}
\psi(\C[\bar{h}])
&\leq& \min_{\C\in\ocC} \psi(\C) + \frac{8\beta}{T+2} + 2\epsilon_S
~=~ \min_{\C\in\ocC} \psi(\C)  + \frac{8\beta}{T+2} + 2L\rho + 4\beta\sqrt{d}\rho'.
\end{eqnarray*}

Setting $T = 1/\epsilon$ completes the proof.

§.§ Proof of Theorem <ref> (GDA for Unconstrained Problems)

§.§ Proof of Theorem <ref> (Ellipsoid For Unconstrained Problems)

Theorem <ref> follows from Theorem <ref> under the special case of $K=0$. The algorithms for the constrained and unconstrained case become identical and the same bounds apply with $r=\infty$. Please see Appendix <ref> for proof of Theorem <ref>.

§.§ Proof of Theorem <ref> (Bisection For Unconstrained Problems)

Theorem <ref> follows from Theorem <ref> under the special case of $K=0$ and $T' = 1$.  Please see Appendix <ref> for proof of Theorem <ref>.

§.§ Proof of Theorem <ref> (SplitFW for Constrained Problems)

§.§ Proof of Theorem <ref> (GDA for Constrained Problems)

§.§ Proof of Theorem <ref> (Ellipsoid for Constrained Problems)

§.§ Proof of Theorem <ref> (Bisection for Constrained Problems)

[(Restated) Convergence of ConBisection algorithm]
Fix $\epsilon \in (0,1)$.
Let $\psi: [0,1]^d \> [0,1]$ be such that $\psi(\C) \,=\, \frac{\langle \A, \C \rangle}{\langle \B, \C \rangle}$, where $\A, \B \in [0,1]^{d}$,
and $\min_{\C \in \cC} {\langle \B, \C \rangle} \,=\, b$ for some $b > 0$. Let $\phi_1,\ldots,\phi_K: [0,1]^d\>[-1,1]$ be convex and $L$-Lipschitz w.r.t. the $\ell_2$-norm. Let $\Omega$ in Algorithm <ref> be a $(\rho , \rho', \delta)$-approximate LMO for sample size $N$.
Suppose the strict feasibility condition in Assumption <ref> holds for radius $r>0$.
Let $\Lambda$, $\Xi$, $\eta$ and $\eta'$ in the call to Algorithm <ref> be set as in Theorem <ref> with Lipschitz constant $L' = \max\{L, \|\A\|_2 + \|\B\|_2\}$.
Let $\bar{h}$ be a classifier returned by Algorithm <ref> when run for $T$ outer iterations and $T'$ inner iterations.
Then with probability $\geq 1 - \delta$ over draw of $S \sim D^N$, after $T = \log(1/\epsilon)$ outer iterations and $T'=\cO(K/\epsilon^2)$ inner iterations:

\[
\textbf{Optimality}:~~\psi(\C[\bar{h}]) \,\leq\, \min_{\C\in\cC:\, \bphi(\C) \leq \0}\,\psi(\C) \,+\,\cO\left(\kappa(\epsilon + \rho^\eff)\right);
% \vspace{-5pt}
\]

\[
\textbf{Feasibility}:~~\phi_k(\C[\bar{h}]) \,\leq\, \cO\left(L'(\epsilon + \rho^\eff)\right),~\forall k \in [K],
\]

where $\kappa = L'/b$ and  $\rho^\eff =  {\rho} + \sqrt{d}{\rho'}$.

The proof follows similar steps as that for Theorem <ref>.
We will first state a couple of lemmas:

Under the assumptions made in Theorem <ref>, the following invariant is true at the end of each iteration $0 \leq t \leq T$ of Algorithm <ref>:

\[
\alpha^t  - \cO\left(\kappa (\epsilon + \rho^\eff)\right) \,\leq\, \min_{\C\in\cC:\, \phi_k(\C) \leq 0,\forall k} \psi(\C) \,\leq\, \psi(\C[h^t])  \,<\, \beta^t + \cO\left(\kappa (\epsilon + \rho^\eff)\right);
\]

\[
\phi_k(\C[\bar{h}]) \,\leq\, \cO\left(L'(\epsilon + \rho^\eff)\right),~\forall k \in [K].
\]

where $L'$, $\kappa$, and $\rho^\eff$ are defined as in Theorem <ref>.

We shall prove this lemma by mathematical induction on the iteration number $t$. For $t=0$, the invariant holds trivially as $0 \leq \psi(\C[h^0]) \leq 1$ and $h^0$ satisfies the constraints. Assume the invariant holds at the end of iteration $t-1 \in \{0, \ldots, T-1\}$; we shall prove that the invariant holds at the end of iteration $t$.

First note that the
linear function $\psi'(\C) =  \langle \A - \gamma^t\B, \,\C \rangle$
in step 6 of the algorithm is Lipschitz w.r.t. the $\ell_2$-norm with Lipschitz parameter of at most $\|\A - \gamma^t\B\|_2 \leq \|\A\|_2 + \|\B\|_2 \leq  L'$. We then have from Theorem <ref> that the
classifier $g^t$ returned by the ConGDA algorithm (Algorithm <ref>) after $T' = \cO(K/\epsilon^2)$ runs enjoys the following guarantee:

\begin{eqnarray}
\langle \A - \gamma^t\B,\,\C[{g}^t]) \rangle
&\leq& \min_{\C\in\cC:\, \phi_k(\C) \leq 0,\forall k}\, \langle \A - \gamma^t\B, \,\C \rangle \,+\, \cO\left(L'(\epsilon + \rho^\eff)\right);
\label{eq:bs-splitfw-obj}
\\
\phi_k(\C[g^t]) &\leq& \cO\left(L'(\epsilon + \rho^\eff)\right),~\forall k \in [K],
\label{eq:bs-splitfw-con}
\end{eqnarray}

where we have used the fact that both $\psi'(\C) = \langle \A - \gamma^t\B, \,\C \rangle$ and $\phi_k(\C)$s are $L'$-Lipschitz w.r.t. the $\ell_2$-norm.
We further have that from the property of the LMO (Definition <ref>) used in turn by Algorithm <ref> that:

\begin{equation}
\|\C^t - \C[g^t]\|_\infty \leq \rho'
\label{eq:bs-lmo}
\end{equation}

We now consider two cases at iteration $t$. In the first case, $\psi(\C^t) \leq \gamma^t$, leading to the assignments $\alpha^t = \alpha^{t-1}$, $\beta^{t} = \gamma^t$, and $h^{t} = g^t$. We have from (<ref>) that:

\begin{eqnarray*}
\langle \A - \gamma^t\B,\,\C[{g}^t]) \rangle
&\leq& \langle \A - \gamma^t\B, \,\C^t \rangle
\,+\, \|\A - \gamma^t\B\|_1\rho'\\
&\leq& \langle \B,\,\C^t \rangle \big(\psi^\rl(\C^t) \,-\, \gamma^t\big)
\,+\, \|\A - \gamma^t\B\|_1\rho'\\
&\leq& 0 \,+\, \|\A - \gamma^t\B\|_1\rho'\\
&\leq& (\|\A\|_2 + \|\B\|_2)\sqrt{d}\rho'
\,\leq\, L'\sqrt{d}\rho'
\,<\, L'(\epsilon + \rho^\eff),
\end{eqnarray*}

where the third step follows from our case assumption that $\psi^\rl(\C^t) \leq \gamma^t$ and $\langle \B,\,\C^t \rangle > 0$, and the last step follows from triangle inequality and $0 \leq \gamma^t \leq 1$.

The above inequality further gives us

\begin{eqnarray*}
\frac{\langle  \A,\, \C[{g}^t] \rangle}{\langle \B,\, \C[{g}^t] \rangle}
\,<\, \gamma^t \,+\, \cO\left(\frac{L'}{b}(\epsilon + \rho^\eff)\right)
\,<\, \beta^t \,+\, \cO(\kappa (\epsilon + \rho^\eff)).
\end{eqnarray*}

In other words,

\[
\psi^\rl\big(\C[h^{t}]\big) \,=\, \psi^\rl(\C[{g}^t]) \,=\, \frac{\langle \A,\, \C^D[{g}^t] \rangle}{\langle \B,\, \C^D[{g}^t] \rangle}  \,<\, \beta^t \,+\, \cO(\kappa (\epsilon + \rho^\eff)).
\]

Moreover, by our assumption that the invariant holds at the end of iteration $t-1$, we have

\[
\alpha^{t} \,-\, \cO\left(\kappa(\epsilon + \rho^\eff)\right) \,=\, \alpha^{t-1} \,-\, \cO\left(\kappa(\epsilon + \rho^\eff)\right)  \,\leq\, \min_{\C \in \cC}\psi^\rl(\C) \,\leq\, \psi^\rl(\C[h^{t}]) \,<\, \beta^t \,+\, \cO(\kappa(\epsilon + \rho^\eff)).
\]

Further, from (<ref>), $\phi_k(\C[h^t]) = \phi_k(\C[g^t]) \leq \cO(L'\bar{\rho}), \forall k$.
Thus under the first case, the invariant holds at the end of iteration $t$.

In the second case, $\psi^\rl(\C^t) > \gamma^t$ at iteration $t$, which would lead to the assignments $\alpha^t = \gamma^{t}$, $\beta^{t} = \beta^{t-1}$, and $h^{t} = h^{t-1}$. Since the invariant is assumed to hold at the end of iteration $t-1$, we have

\begin{equation}
\label{eqn:case-2-partial-con}
\beta^t + \cO\left(\kappa(\epsilon + \rho^\eff)\right) \,=\, \beta^{t-1} + \cO(\kappa(\epsilon + \rho^\eff))  \,>\, \psi^\rl(\C[h^{t-1}]) \,=\, \psi^\rl(\C[h^{t}]).
\end{equation}

Next for $\C^* \,\in\, \underset{\C\in\cC:\, \bphi(\C) \leq \0}{\argmin}\,\, \langle \A - \gamma^t\B, \,\C \rangle$, we have from (<ref>),

\begin{eqnarray*}
\langle \A - \gamma^t\B, \,\C^* \rangle
% &=& a_t\langle {\L}^t, \,\C^* \rangle\\
% &\geq& a_t\langle {\L}^t, \C[h^t] \rangle \,-\, a_t \rho\\
% &=&a_t\langle {\L}^t, \C[h^t] \rangle \,-\, \|\A - \gamma^t\B\|_2 \rho\\
&=& \langle \A - \gamma^t\B, \,\C[h^t] \rangle  \,-\, \cO(L'(\epsilon + \rho^\eff))\\
%&=& \frac{1}{\|\A - \gamma^t\B\|_\infty}\langle \A - \gamma^t\B, \,\conf(\widetilde{h}^j, D) \rangle \,+\, \epsilon\\
%&=& \langle \A - \gamma^t\B, \,\conf(\widetilde{h}^j,D) \rangle \,+\, \|\A - \gamma^t\B\|_\infty \epsilon\\
&\geq& \langle \A - \gamma^t\B, \,\C^t \rangle \,-\, \|\A - \gamma^t\B\|_1\|\C^t - \C[h^t]\|_\infty \,-\, \cO(L'(\epsilon + \rho^\eff))\\
&\geq& \langle \A - \gamma^t\B, \,\C^t \rangle \,-\, \|\A - \gamma^t\B\|_1\rho'
\,-\, \cO(L'(\epsilon + \rho^\eff))\\
&=& \langle\B, \, \C^t\rangle(\psi(\C^t) - \gamma^t)
\,-\, \|\A - \gamma^t\B\|_1\rho' \,-\, \cO(L'(\epsilon + \rho^\eff))\\
&\geq& \langle\B, \, \C^t\rangle(0)
\,-\, \|\A - \gamma^t\B\|_1\rho' \,-\, \cO(L'(\epsilon + \rho^\eff))\\
&\geq& -(\|\A\|_2 + \|\B\|_2)\sqrt{d}\rho'
\,-\, \cO(L'(\epsilon + \rho^\eff)) \,=\, -\cO(L'(\epsilon + \rho^\eff)),
\end{eqnarray*}

where the second step follows from the property of the LMO, the second step follows from Holder's inequality, the third step using (<ref>), the forth step follows from our case assumption that $\psi^\rl(\C^t) \geq \gamma^t$ and $\langle\B, \, \C^t\rangle > 0$, the last step follows
from the fact that $\|\mathbf{z}\|_1 \geq \|\mathbf{z}\|_2$ and from the triangle inequality and that $0 \leq \gamma^t \leq  1$.

In particular, we have for all $\C \in \cC$ such that $\bphi(\C) \leq \0$,

\[
\langle \A - \gamma^t\B, \,\C \rangle  \,\geq\, -\cO(L'(\epsilon + \rho^\eff)),
\]

\[
\frac{\langle \A, \,\C \rangle}{\langle \B, \,\C \rangle} \,\geq\, \gamma^t
-\cO\left(\frac{L'}{\langle \B, \,\C \rangle}(\epsilon + \rho^\eff)\right)
\,\geq\,
\gamma^t
-\cO\left(\frac{L'}{b}(\epsilon + \rho^\eff)\right)
\,=\,
\gamma^t
-\cO\left(\kappa(\epsilon + \rho^\eff)\right).
\]

\[
\psi^\rl(\C) \,\geq\, \gamma^t \,-\, \cO\left(\kappa(\epsilon + \rho^\eff)\right) \,=\, \alpha^t -\cO\left(\kappa(\epsilon + \rho^\eff)\right).
\]

By combining the above with (<ref>), we can see that the invariant holds in iteration $t$ under this case as well.
We also have $\phi_k(\C[h^t]) = \phi_k(\C[h^{t-1}]) \leq \cO\left(L'(\epsilon + \rho^\eff)\right), \forall k$.
This completes the proof of the lemma.

Let $\psi$ be as defined in Theorem <ref>. Then the following is true in each iteration $1 \leq t \leq T$ of Algorithm <ref>:

\[
\beta^t - \alpha^t ~=~ \frac{1}{2}\big(\beta^{t-1} - \alpha^{t-1}\big)	.
\]

We consider two cases in each iteration of Algorithm <ref>. If in an iteration $t \in \{1, \ldots, T\}$,
$\psi^\rl(\C^t) \leq \gamma^t$, leading to the assignment $\beta^t = \gamma^t$, then

\begin{eqnarray*}
\beta^t - \alpha^t &=& \gamma^t - \alpha^{t-1}
% \\
% &=&
\frac{\alpha^{t-1} + \beta^{t-1}}{2} - \alpha^{t-1}
% \\
% &=&
\frac{1}{2}(\beta^{t-1} - \alpha^{t-1}).
\end{eqnarray*}

On the other hand, if
$\psi^\rl(\C^t) > \gamma^t$, leading to the assignment $\alpha^t = \gamma^t$, then

\begin{eqnarray*}
\beta^t - \alpha^t &=& \beta^{t-1} - \gamma^t
% \\
% &=&
\beta^{t-1} - \frac{\alpha^{t-1} + \beta^{t-1}}{2}
% \\
% &=&
\frac{1}{2}\big(\beta^{t-1} - \alpha^{t-1}\big).
\end{eqnarray*}

Thus in both cases, the statement of the lemma is seen to hold.

We are now ready to prove Theorem <ref>.

For the classifier $\bar{h} = h^T$ output by Algorithm <ref> after $T$ iterations, we have from lem:lower-upper-bounds-con,

\begin{eqnarray*}
\psi^\rl\big(\C[h^T]\big) \,-\,
\min_{\C \in \cC} \psi^\rl(\C)
&< &
% (\beta^t \,+\, \kappa\rho^\eff) \,-\, (\alpha^t \,-\, \kappa\rho^\eff)
% \\
% &=&
% ~=\,
\beta^t - \alpha^t \,+\, \cO(\kappa(\epsilon + \rho^\eff))
\\
&\leq& 2^{-T}\big(\beta^0 - \alpha^0\big) \,+\, \cO(\kappa(\epsilon + \rho^\eff))
\\
&=& 2^{-T}\big(1 - 0\big) \,+\, \cO(\kappa(\epsilon + \rho^\eff))\\
&=& 2^{-T} \,+\, \cO(\kappa(\epsilon + \rho^\eff)),
\end{eqnarray*}

the second step  follows from Lemma <ref>. We additionally have from Lemma <ref>,
$\phi_k(\C[\bar{h}]) \,\leq\, \cO\left(L'(\epsilon + \rho^\eff)\right),~\forall k \in [K].$ Setting $T = \log(1/\epsilon)$ completes the proof.

§.§ Proof of Theorem <ref>

[(Restated) Regret bound for plug-in LMO]
Fix $\delta \in (0, 1)$. Then with probability $\geq 1 - \delta$ over draw of sample $S \sim D^N$, for any  loss matrix $\L \in \R_+^d$ with $\|\L\|_\infty = 1$, the classifier and confusion matrix $(\widehat{g}, \widehat{\boldsymbol{\Gamma}})$ returned by Algorithm <ref> satisfies:

\begin{equation*}
\langle \L, \C[\widehat{g}]\rangle \,\leq\, \min_{h:\X\>\Delta_n}\langle \L, \C[h] \rangle + \E_X\big[\big\|\widehat{\boldeta}(X) \,-\, \boldeta(X)\big\|_1\big];
\vspace{-5pt}
\label{eq:lmo1}
\end{equation*}

\begin{equation*}
\|\C[\widehat{g}] \,-\, \hat{\bGamma}\|_\infty \,\leq\, \cO\bigg(\sqrt{\displaystyle\frac{d\log(n)\log(N) + \log(d/\delta)}{N}}\bigg).
\label{eq:lmo2}
\end{equation*}

For simplicity, we will represent both $\L$ and $\C$ as $n \times n$ matrices instead of flattened $n^2$-dimensional vectors.
Let us denote the columns of $\L$ by  $\bell_1, \ldots, \bell_n$, where $\ell_j = [L_{1, j}, L_{2, j}, \ldots, L_{n, j}]^\top$.

We can then re-write:

\begin{align*}
\langle \L , \C[{h}] \rangle
\sum_{i,j}  L_{ij} \,C_{ij}[h]
\sum_{i,j} \E_{X}\left[
\eta_i(X)\, L_{ij}\, \1(h(X) = j)
\right]\\
&=\, \sum_{j=1}^n \E_{X}\left[\1(h(X) = j)\,\boldeta(X)^\top \bell_j\right]
~=\,  \E_{X}\left[\boldeta(X)^\top \bell_{h(X)}\right].
\end{align*}

Let $h^*$ be the Bayes-optimal classifier for the linear metric $\langle \L , \C[\widehat{h}] \rangle$.
For the first part, we bound the $\L$-regret as follows:

\begin{eqnarray*}
\lefteqn{\langle \L , \C[\widehat{g}] \rangle - \langle \L , \C[h^*] \rangle }\\
\E_X\big[
\boldeta(X)^\top \bell_ {\widehat g(X)}\big]  - \E_X  \big[\boldeta(X)^\top \bell_ {h^*(X)}\big] \\[0.1em]
\E_X  \big[\hat\boldeta(X)^\top \bell_ {\widehat g(X)}\big] + \E_X  \big[(\boldeta(X)-\hat\boldeta(X)^\top \bell_ {\widehat g(X)}\big] - \E_X  \big[\boldeta(X)^\top \bell_ {h^*(X)}\big] \\[0.1em]
\E_X  \big[\hat\boldeta(X)^\top \bell_ {h^*(X)}\big] + \E_X  \big[(\boldeta(X)-\hat\boldeta(X)^\top \bell_ {\widehat g(X)}\big] - \E_X  \big[\boldeta(X)^\top \bell_ {h^*(X)}\big] \\[0.1em]
\E_X  \big[(\boldeta(X)-\hat\boldeta(X))^\top (\bell_ {\widehat g(X)}-\bell_ {h^*(X)})\big]  \\[0.1em]
\E_X \big[\big\|\boldeta(X)-\hat\boldeta(X)\big\|_1 \cdot\big\|\bell_ {\widehat g(X)}-\bell_ {h^*(X)}\big\|_\infty\big] \\[0.1em]
\E_X \big[\big\|\boldeta(X)-\hat\boldeta(X)\big\|_1\big],
\end{eqnarray*}

where in the
third step, we use the fact that
$\widehat{g}(x) \,=\, \argmin^*_{j\in[n]}  \widehat{\boldeta}(x)^\top \bell_j$; in the
last step, we have use the fact that $\|\L\|_\infty =  1$.

For the second part, we denote the class of all plug-in classifiers constructed from a fixed class-probability estimator $\widehat{\eta}$ by:

\[\H = \left\{h:\X\>[n],\, h(x)\,=\, \argmin^*_{y\in[n]} \bell_y^\top \widehat{\boldeta}(x) \,|\,\L \in [0,1]^{n\times n}\right\},\]

and provide a uniform convergence bound over all classifiers in $\H$, and in turn applies to the classifier $g$ output by Algorithm \ref{alg:plug-in}.

For any  $a,b∈[n]$, we have
\begin{eqnarray*}
\sup_{h\in\H_\q}\left| \hat{C}^S_{a,b}[h] - C_{a,b}[h] \right|
\sup_{h\in\H}\left| \frac{1}{m}\sum_{i=1}^{m} \left(\1(y_i=a, h(x_i)=b) - \E [\1(Y=a,h(X)=b)] \right) \right| \\
\sup_{h\in\H^b}\left| \frac{1}{m}\sum_{i=1}^{ m} \left(\1(y_i=a, h(x_i)=1) - \E [\1(Y=a,h(X)=1)] \right) \right|\;, \\
\end{eqnarray*}
where for a fixed $b ∈[n]$,
$$\H^b \,=\, \left\{h:\X\>\{0,1\}: \exists \L\in [0,1]^{n\times n}, \forall x\in\X,\, h(x)=\1\left(b= \argmin^*_{y\in[n]}\bell_y^\top \widehat{\boldeta}(x)\right) \right\}.$$
The set $^̋b$ can be seen as hypothesis class whose concepts are the intersection of $n$ halfspaces in $^n$ (corresponding to $(x)$) through the origin.  Hence we have from Lemma 3.2.3 of  \citet{Blumer+89} that the VC-dimension of $^̋b$ is at most $2n^2log(3n)$.

From standard uniform convergence arguments we have that for each $a, b ∈[n]$, the following holds with at least probability $1-δ$ (over draw of $S ∼D^N$),
\begin{eqnarray*}
\sup_{h\in\H}\left| \hat{C}^S_{a,b}[h] - C_{a,b}[h] \right|
\,\leq\,
\cO\left(\sqrt{\frac{n^2\log(n)\log( N ) + \log(\frac{1}{\delta})}{ N} }\right).
\end{eqnarray*}
Applying union bound over all $a,b ∈[n]$, we have that the following holds with probability $≥1-δ$:
\begin{eqnarray*}
\left|\left| \hat\C^S[\hat{g}]  -  \C[\hat{g}]  \right|\right|_\infty \,\leq\, \sup_{h\in\H}\left|\left| \hat\C^S[h]  -  \C[h]  \right|\right|_\infty
\,\leq\,
\cO\left(\sqrt{\frac{n^2\log(n)\log( N ) + \log(\frac{n^2}{\delta})}{ N } }\right).
\end{eqnarray*}
Plugging $d= n^2$ completes the proof.
\end{proof}

\section{Additional Experimental Details}
\label{app:expts}
% \subsection{Post-processing}
% \label{app:post-processing}
% We now present additional details about our experimental setup and additional experimental results.

\subsection{Hyper-parameter Selection}
\label{app:hparam}
We run the Frank-Wolfe and GDA algorithms  for 5000 LMO calls, and the ellipsoid algorithm for 1000 LMO calls. We run the constrained algorithms for 10000, 10000 and 1000 LMO calls respectively.  The unconstrained Frank-Wolfe algorithm has no other hyper-parameters to tune.
The GDA algorithm has two step-size parameters $η$ and $η'$, which we tune using a two-dimensional grid-search over  ${0.001, 0.01, 0.1}^2$, picking the parameters that yield the lowest objective on the training set. For the ellipsoid algorithm, we fix %find it sufficient to fix %the approximation error bound $\tau$ to 0 and
the initial ellipsoid radius $a$ to 1000.

%\todoshiv{Add bisection algo hyper-parameters} - No hyper params

The constrained counterpart to the Frank-Wolfe algorithm (SplitFW) in Algorithm \ref{alg:FW-con} has two additional hyper-parameters: the weight on the quadratic penalty $ζ$, which we set to 10, and the step-size $η$, for which, we adopt the same schedule used by \cite{Gidel2018}, and set it to 0.5 for first $T/3$ iterations, 0.1 for the next $T/3$ iterations, and 0.001 for the final $T/3$ iterations. Additionally, we find it sufficient to avoid the explicit line search for $γ^t$ in line 7 and instead set to $2/t+2$, akin to the standard Frank-Wolfe setup. For the constrained version of GDA algorithm, we set the step-sizes $η_ =η_ = η'$, and tune $η_$ and $η'$ using the same the two-dimensional grid search used for unconstrained GDA, picking among those that satisfy the constraints on the training set, the ones with the least training objective (When none of the parameters satisfy the constraints, we pick the one with the minimum constraint violation). The hyper-parameters for the constrained ellipsoid algorithm were chosen in the same way as the unconstrained version. For TFCO, we tuned the learning rates for the model and constraint from ${0.001, 0.01, 0.1}$ and ran it for $5000$ iterations.
% \subsection{Simplifications to GDA}
% \label{app:gda-simplifications}

%.\todoshiv{Add TFCO hparam details}

% \subsection{Bayes-optimal Classifier for H-mean}
% \label{app:h-mean-opt}

\subsection{Additional Details for CIFAR Case Studies}
\label{app:case-studies}
Below, we list the five super-classes in the CIFAR-55 dataset described in Section \ref{sec:expts-cifar}, and the 10 classes that each of them comprise of:
% \begin{itemize}
%     \item
(i) \textbf{Flowers and Fruits:} Orchid, Poppy, Rose, Sunflower, Tulip, Mushroom, Orange, Pear, Apples, and Sweet Pepper.
% \item
(ii) \textbf{Aquatic Animals:} Beaver, Dolphin, Otter, Aquarium Fish, Ray, Flat Fish, Shark, Trout, Whale, and Seal.
% \item
(iii) \textbf{Household Items:} Clock, Bed, Chair, Couch, Keyboard, Telephone, Television, Wardrobe, Table, and Lamp.
% \item
(iv) \textbf{Large Outdoor Scenes:} Bridge, Castle, House, Road, Mountain, Skyscraper, Cloud, Forest, Plain, and Sea.
% \item
\textbf{Mammals:} Camel, Cattle, Chimpanzee, Elephant, Kangaroo, Porcupine, Possum, Raccoon, Fox, and Skunk.
% \end{itemize}
%\textbf{Hyperparameters Choices.}
% \todoshiv{Batch size, number of epochs, momentum, learning rate schedule, image size}
We employ standard data augmentation techniques on the CIFAR datasets by applying  random crops and horizontal flips.\footnote{The learning rate schedules %and other hyper-parameters
were adopted from: \url{https://github.com/huyvnphan/PyTorch_CIFAR10}.}
% We use a batch size of 64, a constant learning rate of 0.01 and weight decay of 0.01 with early stopping criterion (patience=25) to avoid overfitting. The code and hyper parameters such as mean, std-dev for normalization are largely adopted from the repository PyTorch.\textunderscore{}CIFAR\footnote{Github URL: \url{https://github.com/huyvnphan/PyTorch_CIFAR10}}.

\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/Constraint/abalone_test_hmeanscore_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Constraint/abalone_test_cov_barplot.pdf}
\label{fig:app-abalone}
\caption{Abalone}
%% TODO SHIV Less Strict Constraint
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/Constraint/MACHO_test_hmeanscore_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Constraint/MACHO_test_cov_barplot.pdf}
\label{fig:app-macho}
\caption{MACHO}
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\vspace{3pt}
\includegraphics[width=0.48\linewidth]{Figs/Constraint/covtype_test_hmeanscore_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Constraint/covtype_test_cov_barplot.pdf}
\label{fig:app-covtype}
\caption{CovType}
\end{subfigure}
% \vspace{1em}
\caption{Optimizing the H-mean loss subject to the coverage constraint $\max_i|\sum_{j}C_{ji} \,-\, \pi_i| \leq 0.01$. The plots on the left show the H-mean loss on the test set and those on the right show the coverage violation $\max_i|\sum_{j}C_{ji} \,-\, \pi_i| - 0.01$ on the test set.
\textit{Lower} H-mean value are \textit{better}, and the constraint values need to be $\leq 0$.
%The results are averaged over 10 random train-test splits. The error bars indicate 95\% confidence intervals.
\label{fig:app-hmean-cov}
\vspace{-3pt}
\end{figure}

\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/Fairness/adult_test_gmean_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Fairness/adult_test_eopp_barplot.pdf}
\label{fig:app-adult}
\caption{Adult}
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/Fairness/crimes_test_gmean_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Fairness/crimes_test_eopp_barplot.pdf}
\label{fig:app-crimes}
\caption{Crimes}
% \vspace{-10pt}
\end{subfigure}
% \vspace{1em}
% \caption{Optimizing the G-mean loss subject to the Equal Opportunity constraint $\leq 0.01$. The plots on the left show the G-mean loss on the test set and those on the right show the Equal Opportunity Violation on the test set.
% \textit{Lower} G-mean values are \textit{better}, and the constraint values need to be $\leq 0$.
% The results are averaged over 10 random train-test splits. The error bars indicate 95\% confidence intervals.}
% \label{fig:app-gmean-eqopp-1}
% \end{figure}
% \begin{figure}[t]
% \centering
% \begin{subfigure}[b]{0.48\linewidth}
% \centering
% \includegraphics[width=0.48\linewidth]{Figs/Fairness/compas_test_gmean_barplot.pdf}
% \includegraphics[width=0.48\linewidth]{Figs/Fairness/compas_test_eopp_barplot.pdf}
% \label{fig:app-compas}
% \caption{Compas}
% \end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\vspace{3pt}
\includegraphics[width=0.48\linewidth]{Figs/Fairness/default_test_gmean_barplot.pdf}
\includegraphics[width=0.48\linewidth]{Figs/Fairness/default_test_eopp_barplot.pdf}
\label{fig:app-default}
\caption{Default}
\end{subfigure}
% \vspace{1em}
\caption{Optimizing the G-mean loss subject to the Equal Opportunity constraint $\leq 0.01$. The plots on the left show the G-mean loss on the test set and those on the right show the equal opportunity violation (needs to be $\leq 0$) on the test set.
\textit{Lower} G-mean values are \textit{better}.
%, and the constraint needs to be $\leq 0$.
%The results are averaged over 10 random train-test splits. The error bars indicate 95\% confidence intervals.
\label{fig:app-gmean-eqopp-2}
\vspace{-10pt}
\end{figure}

% \subsection{Practical Guidance: Additional Results}
% \label{app:guidance}
\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/MinMax/satimage_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/MinMax/satimage_test_score.pdf}
\label{fig:lmo-satimage-train-minmax}
\caption{SatImage}
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/MinMax/MACHO_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/MinMax/MACHO_test_score.pdf}
\label{fig:lmo-macho-train-minmax}
\caption{MACHO}
\end{subfigure}
% \vspace{1em}
\caption{Optimizing the \emph{Min-max} loss: Comparison of performance of the Frank-Wolfe, GDA and ellipsoid methods as a function of the number of LMO calls. The plot on the left is for train data and on the right is for test data. \textit{Lower} values are \textit{better}. Because the min-max loss is non-smooth, Frank-Wolfe is seen to converge to a sub-optimal classifier.}
\label{fig:app-min-max}
\vspace{-6pt}
\end{figure}

% ----- Hmean Unconstraint

\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/HmeanUncon/satimage_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/HmeanUncon/satimage_test_score.pdf}
\label{fig:lmo-satimage-train-hmean-uncon}
\caption{SatImage}
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/HmeanUncon/MACHO_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/HmeanUncon/MACHO_test_score.pdf}
\label{fig:lmo-macho-train-hmean-uncon}
\caption{MACHO}
\end{subfigure}
% \vspace{1em}
\caption{Optimizing the \emph{Hmean} loss: Comparison of performance of the Frank-Wolfe, GDA and ellipsoid methods as a function of the number of LMO calls. The plot on the left is for Train data and on the right is for Test data. \textit{Lower} values are \textit{better}.}
\label{fig:app-hmean-uncon}
\vspace{-10pt}
\end{figure}

% \subsection{app:lmo-calls}
\begin{figure}[t]
\centering
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/LMOCalls/adult_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/LMOCalls/adult_train_cons.pdf}
\label{fig:app-lmo-adult-train}
\caption{Adult}
\end{subfigure}
\begin{subfigure}[b]{0.48\linewidth}
\centering
\includegraphics[width=0.48\linewidth]{Figs/LMOCalls/abalone_train_score.pdf}
\includegraphics[width=0.48\linewidth]{Figs/LMOCalls/abalone_train_cons.pdf}
\label{fig:app-lmo-macho-train}
\caption{Abalone}
\end{subfigure}
% \vspace{1em}
\caption{Optimizing the H-mean loss subject to the coverage constraint $\max_i|\sum_{j}C_{ji} \,-\, \pi_i| \leq 0.01$. The plots on the left show the H-mean loss on the train set and those on the right show the coverage violation $\max_i|\sum_{j}C_{ji} \,-\, \pi_i| - 0.01$ on the train set.
\textit{Lower} H-mean value are \textit{better}, and the constraint values need to be $\leq 0$.
%The results are averaged over 10 random train-test splits.
\label{fig:app-lmo-hmean-cov}
\vspace{-15pt}
\end{figure}

% \subsection{Choice of LMO}
% \label{app:expts-lmo}
\begin{table}[t]
\centering
\caption{Comparison of the plug-in and weighted logistic regression (WLR) based LMOs on the task of optimizing the (convex) H-mean loss. The number of iterations, i.e.\ calls to the LMO, is fixed at \emph{100}. \textit{Lower} values are \textit{better}. The results are averaged over 10 random train-test splits}
\label{tab:cost-sen-100}
\begin{footnotesize}
\begin{tabular}{ccccccc}
\hline
\multirow{2}{*}{\textbf{Dataset}} &
\multicolumn{2}{c}{\textbf{FW}} &
\multicolumn{2}{c}{
\textbf{Ellipsoid}} &
\multicolumn{2}{c}{\textbf{GDA}}
\\
\textbf{Plugin} &
\textbf{WLR} & \textbf{Plugin} & \textbf{WLR}  & \textbf{Plugin} & \textbf{WLR} \\
\hline
% Abalone - Train   & 0.275 (0.005) & 0.243 (0.004) & 0.241 (0.006) & 0.239 (0.008) & 0.154 (0.023) & 0.216 (0.011) \\
Aba  & $0.812 \pm 0.017$ & $\textbf{0.798} \pm \textbf{0.013}$ & $\textbf{0.815} \pm \textbf{0.017}$     & $0.817 \pm 0.012$  & $0.841 \pm 0.032$   & $\textbf{0.837} \pm \textbf{0.035}$ \\
% Adult - Train    & 0.824 (0.001) & 0.827 (0.001) & 0.829 (0.001)    & 0.83 (0.001)  & 0.83 (0.001)   & 0.822 (0.002) \\
%% REMOVE
% Adult    & 0.178 (0.002) & 0.175 (0.002) & 0.173 (0.001)    & 0.173 (0.001) & 0.173 (0.001)  & 0.181 (0.002) \\
% PageBlock - Train & 0.912 (0.036) & 0.949 (0.007) & 0.931 (0.027) & 0.954 (0.006) & 0.912 (0.042) & 0.949 (0.007) \\
PgB & $0.127 \pm 0.039$  & $\textbf{0.079} \pm \textbf{0.015}$ & $0.111 \pm 0.026$     & $\textbf{0.079} \pm \textbf{0.018}$  & $0.122 \pm 0.032$  & $\textbf{0.084} \pm \textbf{0.018}$ \\
% MACHO - Train    & 0.934 (0.005) & 0.987 (0.001) & 0.945 (0.004)    & 0.989 (0.001) & 0.944 (0.005)  & 0.978 (0.003) \\
MAC    & $\textbf{0.124} \pm \textbf{0.017}$  & $0.245 \pm 0.027$ & $\textbf{0.125} \pm \textbf{0.017}$    & $0.247 \pm 0.027$ & $\textbf{0.124} \pm \textbf{0.016}$  & $0.206 \pm 0.029$ \\
Sat    & $0.171 \pm 0.007$  & $\textbf{0.170} \pm \textbf{0.007}$ & $0.170 \pm 0.006$  & $\textbf{0.167} \pm \textbf{0.006}$ & $0.171 \pm 0.007$  & $\textbf{0.170} \pm \textbf{0.006}$ \\
Cov & $0.466 \pm 0.001$ & $\textbf{0.450} \pm \textbf{0.001}$ & $0.466 \pm 0.001$ & $\textbf{0.451} \pm \textbf{0.001}$ & $0.463 \pm 0.001$ & $\textbf{0.447} \pm \textbf{0.001}$\\
\hline
\end{tabular}
\end{footnotesize}
\vspace{-10pt}
\end{table}

% \subsection{Performance of Trivial Classifiers}
% We report the H-mean Loss and micro-F measures of a random classifier on our datasets in Table~\ref{tab:trivial-classifier-datasets}.

\label{app:trivial-classifier}
\begin{table}[t]
\centering
\caption{Performance metrics of a Random Classifiers on the Dataset. \textit{Lower Values are better.}}
\label{tab:trivial-classifier-datasets}
\begin{footnotesize}
\begin{tabular}{ccccccc}
\hline
Dataset & H-mean Loss & micro-F1
\\
\hline
Communities \& Crime & 0.506 & 0.503
\\
COMPAS & 0.501 & 0.504
\\
Law School & 0.501 & 0.499
\\
Default & 0.499 & 0.498
\\
Adult & 0.499 & 0.499
\\
Abalone & 0.940 & 0.918
\\
Pgblk & 0.839 & 0.794
\\
MACHO & 0.914 & 0.874
\\
SatImage & 0.835 & 0.832
\\
CovType & 0.858 & 0.857
\\
\hline
\end{tabular}
\end{footnotesize}
\end{table}

\subsection{Additional Experimental Results}
\label{app:expts-additional}
We report the H-mean Loss and micro-F measures of a random classifier on our datasets in Table~\ref{tab:trivial-classifier-datasets}.
We also present additional results for the experiments described in Section \ref{sec:experiments}:
% \begin{itemize}
(i) \textbf{Performance on Constrained Problems} (Section \ref{sec:experiments-cons}): See Figures \ref{fig:app-hmean-cov}-- \ref{fig:app-gmean-eqopp-2}.
(ii) \textbf{Practical Guidance on Algorithm Choice} (Section \ref{sec:expts-practical}): See Figures \ref{fig:app-min-max}--\ref{fig:app-lmo-hmean-cov}.
(iii) \textbf{Choice of LMO: Plug-in vs. Weighted Logistic Regression} (Section \ref{sec:expts-LMO}): See Table \ref{tab:cost-sen-100}.
% \end{itemize}

% \begin{figure}
% \centering
% \begin{subfigure}[b]{0.45\linewidth}
% \includegraphics[width=\linewidth]{Figs/LMOCalls/glass_train_score.pdf}
% % \caption{X|Y is uniform with different overlapping ranges. $P(Y=1)=\frac{1}{3}$}
% \caption{H-mean Score. Higher Values are better.}
% \label{fig:lmo-glass-hmean}
% \end{subfigure}
% \hspace{15pt}
% \begin{subfigure}[b]{0.45\linewidth}
% \centering
% \includegraphics[width=\linewidth]{Figs/LMOCalls/glass_train_cons.pdf}
% \caption{Green Shaded region satisfies the constraints.}
% \label{fig:lmo-glass-cons}
% \end{subfigure}
% % \vspace{1em}
% \caption{No. LMO Calls vs H-mean Score and Coverage Constraint on Glass Dataset}
% \end{figure}

% \subsection{..}
% \label{app:micro-F1-details}

% \subsection{..}

% \section{...}
% \label{app:COCO}

% \section{...}
% \subsection{...}
% \label{app:plug-in-group}
% \subsection{...}
% \label{app:generalized-conf}

% \subsection{Bayes-optimal classifiers}
% \label{app:bayes-opt-synthetic}

\end{document}