# Emergence of a stochastic resonance in machine learning

Zheng-Meng Zhai  School of Electrical, Computer and Energy Engineering,
Arizona State University, Tempe, AZ 85287, USA  Ling-Wei Kong  School of
Electrical, Computer and Energy Engineering, Arizona State University, Tempe,
AZ 85287, USA  Ying-Cheng Lai<EMAIL_ADDRESS>School of Electrical,
Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287,
USA  Department of Physics, Arizona State University, Tempe, Arizona 85287,
USA

###### Abstract

Can noise be beneficial to machine-learning prediction of chaotic systems?
Utilizing reservoir computers as a paradigm, we find that injecting noise to
the training data can induce a stochastic resonance with significant benefits
to both short-term prediction of the state variables and long-term prediction
of the attractor of the system. A key to inducing the stochastic resonance is
to include the amplitude of the noise in the set of hyperparameters for
optimization. By so doing, the prediction accuracy, stability and horizon can
be dramatically improved. The stochastic resonance phenomenon is demonstrated
using two prototypical high-dimensional chaotic systems.

The interplay between noise and nonlinear dynamics often leads to surprising
phenomena with potentially significant applications and thus has always been
an active area of interdisciplinary research. It has been well documented that
noise can be beneficial to applications of dynamical systems, e.g., enhancing
the response of a nonlinear system to weak periodic signals, through
mechanisms such as stochastic and coherence resonances [1, 2, 3, 4, 5, 6]. A
parallel development in nonlinear dynamics is the important but challenging
problem of model-free and data-based prediction of chaotic systems [7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30]. In general, there are two kinds of forecasting problems: short term
and long term. In short-term forecasting, the goal is to predict the detailed
dynamical evolution of the state variables from specific initial conditions,
typically for a few oscillation cycles (or Lyapunov times). In long term
prediction, the aim is to generate the attractor of the system with the
correct statistical behaviors. According to conventional wisdom, for solving
the prediction problems, typically noise is detrimental. For example, in
short-term prediction, because of the sensitive dependence on initial
conditions, noise will make the predicted state evolution diverge
exponentially from the true one. In long-term prediction, noise can induce the
trajectory to cross the basin boundary, leading to a wrong attractor.

In this paper, we report the counterintuitive phenomenon that, in model-free
prediction of chaotic systems with machine learning, a certain amount of noise
can significantly enhance the prediction accuracy and robustness. Similar to a
stochastic resonance, too little or too much noise is not useful and may even
downgrade the predictive power of the neural machine, but an optimal amount of
noise can be beneficial. A central issue is then to determine the optimal
noise level, which we solve using a generalized scheme of hyperparameter
optimization. To be concrete, we focus on reservoir computing [31, 32, 33, 34]
that has become a paradigm in machine-learning based prediction of nonlinear
dynamical systems [35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52] and inject noise into the input signal. A reservoir computer
contains a number of hyperparameters and the prediction performance depends
strongly on their values. Our simulations have revealed that, if the
hyperparameters are not optimized, noise in the training data can improve to
certain extent the prediction performance. However, in order to maximize the
predictive power of a reservoir computer, it is necessary to find the optimal
values of the hyperparameters, a task that can be accomplished through, e.g.,
Bayesian optimization [53, 54]. The key to the emergence of a stochastic
resonance is to treat the noise amplitude as one of the hyperparameters, i.e.,
to regard it as an intrinsic parameter of the reservoir computer. Bayesian
optimization can then yield the optimal noise level. We demonstrate using two
prototypical high-dimensional chaotic systems that noise with the so-
determined amplitude can generate more accurate, robust and stable predictions
in both short and long terms through a stochastic resonance.

The basic principle of reservoir computing and the optimization method are
described in Supplementary Information (SI) [55]. There are six
hyperparameters to be optimized: the spectral radius $\rho$ of the reservoir
network, the scaling factor $\gamma$ of the input weights, the leakage
parameter $\alpha$, the regularization coefficient $\beta$, the link
connection probability $p$ of the random network in the hidden layer, and the
noise amplitude $\sigma$. To determine the optimal hyperparameter values, we
use the _surrogateopt_ function in Matlab [56], a Bayesian optimization
procedure, and employ a surrogate approximation function to estimate the
objective function and to find the global minimum through sampling and
updating. Specifically, the _surrogateopt_ algorithm [57] first samples
several random points and evaluates the objective function at these trial
points. The algorithm then creates a surrogate model of the objective function
by interpolating a radial basis function through all the random trial points.
From the surrogate function, the algorithm identifies the potential minima and
samples the points about these minima to update the function.

We demonstrate the benefits of noise to both short-term and long-term
prediction using two prototypical chaotic systems: the Mackey-Glass (MG)
system described by a nonlinear delay differential equation and the
spatiotemporal chaotic Kuramoto-Sivashinsky (KS) system. We use the Bayesian
algorithm to obtain the optimal values of the six hyperparameters (including
the noise amplitude $\sigma$). We then choose a number of $\sigma$ values away
from the optimal value and test the prediction performance. For each such
fixed $\sigma$ value, we optimize the other five hyperparameters. For a
different value of $\sigma$, the set of the other five hyperparameters is then
different. As we will demonstrate, as the noise amplitude deviates from the
optimal value on either side, there is a gradual deterioration of the
prediction performance, signifying the emergence of a stochastic resonance.

Our first example is the MG system [58] described by
$\dot{s}(t)=as(t-\tau)/\left(1+\left[s(t-\tau)\right]^{c}\right)-bs(t)$, where
$\tau$ is the time delay, $a$, $b$ and $c$ are parameters. The state of the
system at time $t$ is determined by the entire prior state history within the
time delay, making the phase space of the system infinitely dimensional. To be
concrete, we use two values of the time delay: $\tau=17$ and $\tau=30$, and
fix the other three parameters as $a=0.2$, $b=0.1$, and $c=10$. For $\tau=17$,
the system exhibits a chaotic attractor with one positive Lyapunov exponent:
$\lambda_{+}\approx 0.006$. For $\tau=30$, the system has a chaotic attractor
with two positive Lyapunov exponents [59]: $\lambda_{+}\approx 0.011$ and
0.003. To generate the one-dimensional MG time series data, we integrate the
delay differential equation with the time step $h=0.01$ and generate the
training and testing data by sampling the time series every 100 steps: $\Delta
t=100h=1.0$, where $\Delta t$ is evolutionary time step of the dynamical
network in the hidden layer of the reservoir computer. To remove any transient
behavior, we disregard the first $10,000\Delta t$ in the training dataset. The
length of training data is $T=150,000\Delta t$. The step after the training
data marks the start of the testing data, whose length depends on whether the
task is to make short-term or long-term prediction. The time series data are
pre-processed by using $z$-score normalization:
$z(t)=\left[s(t)-\bar{s}\right]/\sigma_{s}$, where $s(t)$ is the original time
series, $\bar{s}$ and $\sigma_{s}$ are the mean and standard deviation of
$s(t)$, respectively. For $\tau=17$ and $\tau=30$ in the MG system, the
testing lengths for Bayesian optimization are $T_{\rm opt}=900\Delta t$ and
$300\Delta t$, respectively, which are also the testing lengths for short-term
prediction. The so obtained optimal hyperparameter values are listed in Tab.
1. Figure 1(a) shows, for $\tau=30$, representative results of short-term
prediction of the state evolution, where Gaussian noise with the optimal
amplitude is injected into the training time series. Results of long-term
prediction in terms of the attractors in the plane $\\{X\equiv s(t),Y\equiv
s(t-\tau)\\}$ are shown in Fig. 1(b). Visually and statistically, the
predicted attractor cannot be distinguished from the true attractor.
Prediction results for $\tau=17$ are presented in SI [55].

Figure 1: Short-term and long-term prediction of the MG system for $\tau=30$. The optimal noise amplitude is $10^{-1.97}$. (a) Machine predicted system evolution (red trace) in comparison with the ground truth (blue). The predicted state evolution agrees with the true evolution for a time period that contains about 15 local maxima ($T=500\Delta t$), a result that is significantly better than those without optimal noise. (b,c) Representation of the true and predicted attractor in the $\\{X\equiv s(t),Y\equiv s(t-\tau)\\}$ plane. The prediction time length is $T=10,000\Delta t$. Table 1:  Optimal hyperparameter values for MG and KS System | $\rho$ | $\gamma$ | $\alpha$ | $\beta$ | $p$ | $\sigma$
---|---|---|---|---|---|---
MG ($\tau=17$) | 1.62 | 0.55 | 0.64 | $10^{-6.0}$ | 0.99 | $10^{-3.42}$
MG ($\tau=30$) | 1.27 | 0.23 | 0.57 | $10^{-6.4}$ | 0.09 | $10^{-1.97}$
KS | 0.01 | 0.35 | 0.62 | $10^{-9.0}$ | 0.21 | $10^{-2.35}$

Our second example is the one-dimensional KS system [60, 61], a paradigm not
only in physics and chemistry but also in applications of reservoir computing
for demonstrating the predictive power for high-dimensional dynamical systems
[39]. The system equation is $\frac{\partial u}{\partial
t}+\mu\frac{\partial^{4}u}{\partial x^{4}}+\phi(\frac{\partial^{2}u}{\partial
x^{2}}+u\frac{\partial u}{\partial x})=0$, where $u(x,t)$ is a scalar field
defined in the spatial domain $0\leq x\leq L$, $\mu$ and $\phi$ are
parameters. We set $\mu=1$ and $\phi=1$, and use the periodic boundary
condition. As the domain size $L$ increases, the system becomes progressively
more high-dimensionally chaotic with the number of Lyapunov exponents
increasing linearly with the system size [62]. As a representative case of
high-dimensional chaos, we choose $L=60$, where the system has seven positive
Lyapunov exponents: $\lambda_{+}\approx 0.089$, 0.067, 0.055, 0.041, 0.030,
0.005, and 0.003. The length of the training data is about 1000 Lyapunov times
(after disregarding a transient of about 300 Lyapunov times), where a Lyapunov
time is defined as the inverse of the largest positive exponent. The testing
data for short-term and long-term prediction are taken immediately after the
training data of six and 100 Lyapunov times, respectively.

Figure 2: Short-term and long-term prediction of the KS system. (a,b) True
short-term (six Lyapunov times) and long-term (100 Lyapunov times)
spatiotemporal evolution of the nonlinear field $u(x,t)$, respectively, (c,d)
the predicted field $\hat{u}(x,t)$ in short and long terms, respectively. (e)
Difference between the predicted and true fields defined as
$D(x,t)\equiv\sqrt{\left[u(x,t)-\hat{u}(x,t)\right]^{2}}$. (f) Overlapped
image of the true and predicted attractors in terms of the 4th and 5th
dimension of the KS system. The values of the optimal hyperparameters
(including the optimal noise amplitude) are listed in Tab. 1. Figure 3:
Stochastic resonance associated with short-term prediction of chaotic systems.
Shown are three measures of short-term prediction versus the noise amplitude
for two examples: left column - MG system for $\tau=30$ ($r_{c}=0.1$, length
of prediction time window $=300\Delta t$), right column - KS system
($r_{c}=8.0$, length of prediction time window $=$ five Lyapunov times); top
row - RMSE, middle row - prediction stability $R_{s}(r_{c})$, bottom row -
prediction horizon $t_{s}$. The error bars are obtained from an ensemble of 80
performing reservoir computers. For each chaotic system, a specific and unique
noise level emerges at which each prediction measure is optimized, which is
characteristic of a stochastic resonance. Figure 4: Quantifying long-term
prediction through the deviation value DV. (a,b) Successful cases of attractor
prediction in the presence of optimal noise for the MG system for $\tau=30$
and KS system, respectively. (c,d) Unsuccessful cases of attractor prediction
without noise for the two systems. The two-dimensional phase space for the MG
system is $\\{X(t)\equiv s(t),Y(t)\equiv s(t-\tau)\\}$. For the KS system, the
space is $\\{X(t)\equiv u(4,t),Y(t)\equiv u(5,t)\\}$. (e,f) DV versus the
noise amplitude for the MG and KS systems, respectively. There exists an
optimal noise amplitude at which the DV value is minimized, which agrees with
the optimal noise level determined from the corresponding short-term
prediction results in Fig. 3.

Figure 2 shows the results of short-term and long-term predictions of the KS
system. It can be seen that the reservoir computing machine with the aid of
optimal noise not only can accurately predict the short-term spatiotemporal
evolution but also is able to replicate the long-term attractor with the
correct statistical behavior.

Associated with a conventional stochastic resonance in nonlinear systems, some
performance measure such as the signal-to-noise ratio is maximized for an
optimal noise level. Can a similar phenomenon arise in machine-learning
prediction of chaotic systems, where the prediction performance reaches a
maximum for an optimal noise level and deteriorates as the noise amplitude
deviates from the optimal value? That is, how do we ascertain if the optimal
noise amplitude values from Bayesian optimization as listed in Tab. 1 are
indeed optimal?

To address these questions, we test the performance when the noise amplitude
deviates from the optimal value. For any such fixed noise amplitude, the five
other hyperparameters are optimized before training. In particular, we vary
the noise amplitude (uniformly on a logarithmic scale) in the range
$[10^{-8},10^{-0.5}]$. For each noise amplitude, we fix it during the Bayesian
optimization and optimize the other five hyperparameters ($\rho$, $\gamma$,
$\alpha$, $\beta$, and $k$). For different values of the noise amplitude, the
so obtained values of the other five hyperparameters are listed in three
Supplementary tables [55].

We demonstrate the emergence of a stochastic resonance for both short-term and
long-term predictions. To characterize the performance of short-term
prediction, besides the conventional RMSE (defined in SI [55]), we introduce
two additional measures: prediction horizon and stability, where the former
(denoted as $t_{s}$) is the maximal time interval during which the RMSE is
below a threshold and the latter is the probability that a reservoir computer
generates stable dynamical evolution of the target chaotic system in a fixed
time window, which is defined as $R_{s}(r_{c})=(1/n)\sum_{i=1}^{n}\left[{\rm
RMSE}<r_{c}\right]$, where $r_{c}$ is the RMSE threshold, $n$ is the number of
iterations, and $\left[\cdot\right]=1$ if the statement inside is true and
zero otherwise.

Figure 3 shows the RMSE, the prediction stability $R_{s}(r_{c})$, and the
prediction horizon versus the noise amplitude $\sigma$ for the MG system for
$\tau=30$ (left column, $r_{c}=0.1$), as well as the KS system (right column,
$r_{c}=8.0$). In both cases, an optimal noise level emerges in the sense that
a prediction measure versus the noise amplitude exhibits either a “bell shape”
or an “anti-bell shape” type of variation about an optimal point. Figure 3
thus provides strong evidence for a stochastic resonance associated with
short-term performance of machine-learning prediction of chaotic systems. The
results for MG for $\tau=17$ are presented in SI [55].

We now demonstrate the emergence of a stochastic resonance from long-term
prediction through a quantitative measure that we introduce to characterize
the corresponding performance, as shown in Fig. 4 for the MG system for
$\tau=30$ (left column) and the KS system (right column). The measure is the
deviation value (DV), which characterizes the ability for a trained reservoir
computer to capture the dynamical “climate” of the target system (its detailed
definition can be found in SI [55]). In each case, there is an optimal noise
amplitude at which the DV value is minimized [Figs. 4(e) and 4(f)], which
agrees with the optimal value of the noise amplitude from the short-term
prediction results in Fig. 3, providing additional support for the emergence
of a stochastic resonance in machine learning in terms of long-term prediction
of chaotic attractors. The emergence of such a stochastic resonance from long-
term prediction for the MG system for $\tau=17$ is treated in SI [55].

To summarize, we have uncovered the emergence of a stochastic resonance in
machine-learning prediction of chaotic systems. Focusing on reservoir
computing, we find that injecting noise into the training data can be
beneficial to both short- and long-term predictions. In particular, for short-
term prediction, a number of characterizing quantities such as the prediction
accuracy, stability, and horizon can be maximized by an optimal level of noise
that can be found through hyperparameter optimization. For long-term
prediction, optimal noise can significantly increase the chance for the
machine generated trajectory to stay in the vicinity of (or to shadow) the
true attractor of the target chaotic system. Intuitively, training with noise
can enhance the machine’s tolerance to random fluctuations, which can be
beneficial especially when the target system is chaotic. This argument
suggests that the optimal noise level should be on the same order of magnitude
as the one-step prediction error in noiseless prediction, which is indeed so
as verified by our numerical examples. Our work extends the ubiquitous
phenomenon of stochastic resonance in nonlinear dynamical systems to the realm
of machine learning, where deliberate noise combined with hyperparameter
optimization can be a practically feasible approach to enhancing the
predictive power of the neural machine.

We note that, previously the role of noise in neural network training was
studied, e.g., adding noise to the training data for convolutional neural
networks can play the role of regularization to reduce overfitting in the
learning models [63]. In reinforcement learning, injecting noise into the
signals can help the system reach the persistent excitation condition to
facilitate parameter estimation [64, 65]. How noise negatively affects the
prediction of chaotic systems has recently been considered [66], where long
short-term memory machines tend to be more resistant to noise than other
machine-learning methods. The beneficial role of noise in machine-learning
prediction has also been recognized [67, 68, 69, 70]. In spite of the previous
efforts, to our knowledge, the interplay between noise and machine-learning
prediction of dynamical systems was not systematically studied prior to our
work. The discovery of stochastic resonance in machine learning fills this
gap.

Finally, we remark that, in the vast literature on stochastic resonance, the
paradigmatic model of mechanical motion of a particle in a double-well
potential subject to stochastic forcing is often used to explain the observed
resonance phenomenon. However, it is difficult to apply this model to our
machine-learning system, as the dynamics of the high-dimensional neural
network in the hidden layer of a reservoir computer are extraordinarily
complicated. Nonetheless, the predictive ability of the reservoir computer can
be related to generalized synchronization (see Sec. IV in SI [55]). Previous
works in the past two decades demonstrated that noise can induce and enhance
synchronization in nonlinear and complex dynamical systems [71, 72, 73, 74,
75, 76, 77, 78, 79, 80, 81]. We speculate that the mechanism responsible for
the stochastic resonance phenomenon reported here is noise-enhance generalized
synchronization.

This work was supported by AFOSR under Grant No. FA9550-21-1-0438.

## References

  * Benzi  _et al._ [1981] R. Benzi, A. Sutera, and A. Vulpiani, The mechanism of stochastic resonance, J. Phys. A 14, L453 (1981).
  * Benzi  _et al._ [1983] R. Benzi, G. Parisi, A. Sutera, and A. Vulpiani, A theory of stochastic resonance in climatic-change, J. Appl. Math. 43, 565 (1983).
  * McNamara and Wiesenfeld [1989] B. McNamara and K. Wiesenfeld, Theory of stochastic resonance, Phys. Rev. A 39, 4854 (1989).
  * Moss  _et al._ [1994] F. Moss, D. Pierson, and D. O’Gorman, Stochastic resonance - tutorial and update, Int. J. Bif. Chaos 4, 1383 (1994).
  * Gailey  _et al._ [1997] P. C. Gailey, A. Neiman, J. J. Collins, and F. Moss, Stochastic resonance in ensembles of nondynamical elements: The role of internal noise, Phys. Rev. Lett. 79, 4701 (1997).
  * Gammaitoni  _et al._ [1998] L. Gammaitoni, P. Hänggi, P. Jung, and F. Marchesoni, Stochastic resonance, Rev. Mod. Phys. 70, 223 (1998).
  * Farmer and Sidorowich [1987] J. D. Farmer and J. J. Sidorowich, Predicting chaotic time series, Phys. Rev. Lett. 59, 845 (1987).
  * Casdagli [1989] M. Casdagli, Nonlinear prediction of chaotic time series, Physica D 35, 335 (1989).
  * Sugihara  _et al._ [1990] G. Sugihara, B. Grenfell, R. M. May, P. Chesson, H. M. Platt, and M. Williamson, Distinguishing error from chaos in ecological time series, Phil. Trans. Roy. Soc. London B 330, 235 (1990).
  * Kurths and Ruzmaikin [1990] J. Kurths and A. A. Ruzmaikin, On forecasting the sunspot numbers, Solar Phys. 126, 407 (1990).
  * Grassberger and Schreiber [1990] P. Grassberger and T. Schreiber, Nonlinear time sequence analysis, Int. J. Bif. Chaos 1, 521 (1990).
  * Gouesbet [1991] G. Gouesbet, Reconstruction of standard and inverse vector fields equivalent to a Rössler system, Phys. Rev. A 44, 6264 (1991).
  * Tsonis and Elsner [1992] A. A. Tsonis and J. B. Elsner, Nonlinear prediction as a way of distinguishing chaos from random fractal sequences, Nature (London) 358, 217 (1992).
  * Baake  _et al._ [1992] E. Baake, M. Baake, H. G. Bock, and K. M. Briggs, Fitting ordinary differential equations to chaotic data, Phys. Rev. A 45, 5524 (1992).
  * Crutchfield and McNamara [1987] J. P. Crutchfield and B. McNamara, Equations of motion from a data series, Complex Sys. 1, 417 (1987).
  * Sauer [1994] T. Sauer, Reconstruction of dynamical systems from interspike intervals, Phys. Rev. Lett. 72, 3811 (1994).
  * Sugihara [1994] G. Sugihara, Nonlinear forecasting for the classification of natural time series, Philos. T. Roy. Soc. A. 348, 477 (1994).
  * Parlitz [1996] U. Parlitz, Estimating model parameters from time series by autosynchronization, Phys. Rev. Lett. 76, 1232 (1996).
  * Schiff  _et al._ [1996] S. J. Schiff, P. So, T. Chang, R. E. Burke, and T. Sauer, Detecting dynamical interdependence and generalized synchrony through mutual prediction in a neural ensemble, Phys. Rev. E 54, 6708 (1996).
  * Hegger  _et al._ [1999] R. Hegger, H. Kantz, and T. Schreiber, Practical implementation of nonlinear time series methods: The TISEAN package, Chaos 9, 413 (1999).
  * Bollt [2000] E. M. Bollt, Controlling chaos and the inverse frobenius-perron problem: global stabilization of arbitrary invariant measures, Int. J. Bif. Chaos 10, 1033 (2000).
  * Hegger  _et al._ [2000] R. Hegger, H. Kantz, L. Matassini, and T. Schreiber, Coping with nonstationarity by overembedding, Phys. Rev. Lett. 84, 4092 (2000).
  * Sello [2001] S. Sello, Solar cycle forecasting: a nonlinear dynamics approach, Astron. Astrophys. 377, 312 (2001).
  * Matsumoto  _et al._ [2001] T. Matsumoto, Y. Nakajima, M. Saito, J. Sugi, and H. Hamagishi, Reconstructions and predictions of nonlinear dynamical systems: a hierarchical bayesian approach, IEEE Trans. Signal Proc. 49, 2138 (2001).
  * Smith [2002] L. A. Smith, What might we learn from climate forecasts?, Proc. Nat. Acad. Sci. (USA) 19, 2487 (2002).
  * Judd [2003] K. Judd, Nonlinear state estimation, indistinguishable states, and the extended kalman filter, Physica D 183, 273 (2003).
  * Sauer [2004] T. D. Sauer, Reconstruction of shared nonlinear dynamics in a network, Phys. Rev. Lett. 93, 198701 (2004).
  * Tao  _et al._ [2007] C. Tao, Y. Zhang, and J. J. Jiang, Estimating system parameters from chaotic time series with synchronization optimized by a genetic algorithm, Phys. Rev. E 76, 016209 (2007).
  * Wang  _et al._ [2011] W.-X. Wang, R. Yang, Y.-C. Lai, V. Kovanis, and C. Grebogi, Predicting catastrophes in nonlinear dynamical systems by compressive sensing, Phys. Rev. Lett. 106, 154101 (2011).
  * Wang  _et al._ [2016] W.-X. Wang, Y.-C. Lai, and C. Grebogi, Data based identification and prediction of nonlinear and complex dynamical systems, Phys. Rep. 644, 1 (2016).
  * Jaeger [2001] H. Jaeger, The “echo state” approach to analysing and training recurrent neural networks-with an erratum note, Bonn, Germany: German National Research Center for Information Technology GMD Technical Report 148, 13 (2001).
  * Mass  _et al._ [2002] W. Mass, T. Nachtschlaeger, and H. Markram, Real-time computing without stable states: A new framework for neural computation based on perturbations, Neur. Comp. 14, 2531 (2002).
  * Jaeger and Haas [2004] H. Jaeger and H. Haas, Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication, Science 304, 78 (2004).
  * Manjunath and Jaeger [2013] G. Manjunath and H. Jaeger, Echo state property linked to an input: Exploring a fundamental characteristic of recurrent neural networks, Neur. Comp. 25, 671 (2013).
  * Haynes  _et al._ [2015] N. D. Haynes, M. C. Soriano, D. P. Rosin, I. Fischer, and D. J. Gauthier, Reservoir computing with a single time-delay autonomous Boolean node, Phys. Rev. E 91, 020801 (2015).
  * Larger  _et al._ [2017] L. Larger, A. Baylón-Fuentes, R. Martinenghi, V. S. Udaltsov, Y. K. Chembo, and M. Jacquot, High-speed photonic reservoir computing using a time-delay-based architecture: Million words per second classification, Phys. Rev. X 7, 011015 (2017).
  * Pathak  _et al._ [2017] J. Pathak, Z. Lu, B. Hunt, M. Girvan, and E. Ott, Using machine learning to replicate chaotic attractors and calculate Lyapunov exponents from data, Chaos 27, 121102 (2017).
  * Duriez  _et al._ [2017] T. Duriez, S. L. Brunton, and B. R. Noack,  _Machine Learning Control-Taming Nonlinear Dynamics and Turbulence_ (Springer, 2017).
  * Pathak  _et al._ [2018] J. Pathak, B. Hunt, M. Girvan, Z. Lu, and E. Ott, Model-free prediction of large spatiotemporally chaotic systems from data: A reservoir computing approach, Phys. Rev. Lett. 120, 024102 (2018).
  * Carroll [2018] T. L. Carroll, Using reservoir computers to distinguish chaotic signals, Phys. Rev. E 98, 052209 (2018).
  * Roland and Parlitz [2018] Z. S. Roland and U. Parlitz, Observing spatio-temporal dynamics of excitable media using reservoir computing, Chaos 28, 043118 (2018).
  * Griffith  _et al._ [2019] A. Griffith, A. Pomerance, and D. J. Gauthier, Forecasting chaotic systems with very low connectivity reservoir computers, Chaos 29, 123108 (2019).
  * Jiang and Lai [2019] J. Jiang and Y.-C. Lai, Model-free prediction of spatiotemporal dynamical systems with recurrent neural networks: Role of network spectral radius, Phys. Rev. Research 1, 033056 (2019).
  * Fan  _et al._ [2020] H. Fan, J. Jiang, C. Zhang, X. Wang, and Y.-C. Lai, Long-term prediction of chaotic systems with machine learning, Phys. Rev. Research 2, 012080 (2020).
  * Klos  _et al._ [2020] C. Klos, Y. F. K. Kossio, S. Goedeke, A. Gilra, and R.-M. Memmesheimer, Dynamical learning of dynamics, Phys. Rev. Lett. 125, 088103 (2020).
  * Vlachasa  _et al._ [2020] P. R. Vlachasa, P. J., B. R. Hunt, T. P. Sapsis, M. Girvan, E. Ott, and P. Koumoutsakos, Backpropagation algorithms and reservoir computing in recurrent neural networks for the forecasting of complex spatiotemporal dynamics, Neu. Net. 126, 191 (2020).
  * Kong  _et al._ [2021a] L.-W. Kong, H.-W. Fan, C. Grebogi, and Y.-C. Lai, Machine learning prediction of critical transition and system collapse, Phys. Rev. Research 3, 013090 (2021a).
  * Kim  _et al._ [2021] J. Z. Kim, Z. Lu, E. Nozari, G. J. Pappas, and D. S. Bassett, Teaching recurrent neural networks to infer global temporal structure from local examples, Nat. Machine Intell. 3, 316 (2021).
  * Fan  _et al._ [2021] H. Fan, L.-W. Kong, Y.-C. Lai, and X. Wang, Anticipating synchronization with machine learning, Phys. Rev. Resesearch 3, 023237 (2021).
  * Kong  _et al._ [2021b] L.-W. Kong, H.-W. Fan, C. Grebogi, and Y.-C. Lai, Emergence of transient chaos and intermittency in machine learning, J. Phys. Complex. 2, 035014 (2021b).
  * Bollt [2021] E. Bollt, On explaining the surprising success of reservoir computing forecaster of chaos? the universal machine learning dynamical system with contrast to VAR and DMD, Chaos 31, 013108 (2021).
  * Gauthier  _et al._ [2021] D. J. Gauthier, E. Bollt, A. Griffith, and W. A. S. Barbosa, Next generation reservoir computing, Nat. Commun. 12, 5564 (2021).
  * Snoek  _et al._ [2012] J. Snoek, H. Larochelle, and R. P. Adams, Practical Bayesian optimization of machine learning algorithms, in  _Advances in Neural Information Processing Systems_, Vol. 25, edited by F. Pereira, C. Burges, L. Bottou, and K. Weinberger (Curran Associates, Inc., 2012).
  * Yang and Shami [2020] L. Yang and A. Shami, On hyperparameter optimization of machine learning algorithms: Theory and practice, Neurocomp. 415, 295 (2020).
  * [55] Supplementary Information provides additional details of the results in the main text. It is helpful but not essential for understanding the main results of the paper. It contains the following materials: a brief description of the the principle of reservoir computing for predicting chaotic systems, the lists of optimized hyperparameter values used in demonstrating the emergence of a stochastic resonance for the numerical examples, and a number of pertinent issues such as the prediction time required for a stochastic resonance, its robustness against different scenarios of noise injection, and the benefits of noise to reducing the reservoir network size for predicting chaotic systems, as well as a plausible dynamical mechanism for the observed resonance phenomenon .
  * sur [a] Surrogate optimization for global minimization of time-consuming objective functions - MATLAB, https://www.mathworks.com/help/gads/surrogateopt.html (a).
  * sur [b] Surrogate optimization algorithm - MATLAB, https://www.mathworks.com/help/gads/surrogate-optimization-algorithm.html (b).
  * Mackey and Glass [1977] M. C. Mackey and L. Glass, Oscillation and chaos in physiological control systems, Science 197, 287 (1977).
  * Wernecke  _et al._ [2019] H. Wernecke, B. Sándor, and C. Gros, Chaos in time delay systems: An educational review, Phys. Rep. 824, 1 (2019).
  * Koramoto and Tsuzuki [1976] Y. Koramoto and T. Tsuzuki, Persistent propagation of concentration waves in dissipative media far from thermal equilibrium, Prof. Theor. Phys. 55, 356 (1976).
  * Sivashinsky [1977] G. I. Sivashinsky, Nonlinear analysis of hydrodynamic instability in laminar ames I. derivation of basic equations, Acta Astron. 4, 1177 (1977).
  * Edson  _et al._ [2019] R. A. Edson, J. E. Bunder, T. W. Mattner, and A. J. Roberts, Lyapunov exponents of the Kuramoto–Sivashinsky PDE, ANZIAM J. 61, 270 (2019).
  * Smilkov  _et al._ [2017] D. Smilkov, N. Thorat, B. Kim, F. Viégas, and M. Wattenberg, Smoothgrad: removing noise by adding noise, arXiv preprint arXiv:1706.03825 (2017).
  * Xu  _et al._ [2013] B. Xu, C. Yang, and Z. Shi, Reinforcement learning output feedback NN control using deterministic learning technique, IEEE Trans. Neu. Net. Learning Sys. 25, 635 (2013).
  * Kamalapurkar  _et al._ [2016] R. Kamalapurkar, P. Walters, and W. E. Dixon, Model-based reinforcement learning for approximate optimal regulation, Automatica 64, 94 (2016).
  * Sangiorgio  _et al._ [2021] M. Sangiorgio, F. Dercole, and G. Guariso, Forecasting of noisy chaotic systems with deep neural networks, Chaos Soli. Frac. 153, 111570 (2021).
  * Bishop [1995] C. M. Bishop, Training with noise is equivalent to tikhonov regularization, Neu. Comp. 7, 108 (1995).
  * Grandvalet  _et al._ [1997] Y. Grandvalet, S. Canu, and S. Boucheron, Noise injection: Theoretical prospects, Neural Computation 9, 1093 (1997).
  * Wyffels  _et al._ [2008] F. Wyffels, B. Schrauwen, and D. Stroobandt, Stable output feedback in reservoir computing using ridge regression, in  _International conference on artificial neural networks_ (Springer, 2008) pp. 808–817.
  * Jim  _et al._ [1996] K.-C. Jim, C. L. Giles, and B. G. Horne, An analysis of noise in recurrent neural networks: convergence and generalization, IEEE Trans. Neu. Net. 7, 1424 (1996).
  * Toral  _et al._ [2001] R. Toral, C. R. Mirasso, E. Hernandez-Garcia, and O. Piro, Analytical and numerical studies of noise induced synchronization of chaotic systems, Chaos 11, 665 (2001).
  * He  _et al._ [2003] D. He, P. Shi, and L. Stone, Noise-induced synchronization in realistic models, Phys. Rev. E 67, 027201 (2003).
  * Guan  _et al._ [2006] S. Guan, Y.-C. Lai, C.-H. Lai, and X. Gong, Understanding synchronization induced by common noise, Phys. Lett. A 353, 30 (2006).
  * Wang  _et al._ [2010] Y. Wang, Y.-C. Lai, and Z. Zheng, Route to noise-induced synchronization in an ensemble of uncoupled chaotic systems, Phys. Rev. E 81, 036201 (2010).
  * Nakao  _et al._ [2007] H. Nakao, K. Arai, and Y. Kawamura, Noise-induced synchronization and clustering in ensembles of uncoupled limit-cycle oscillators, Phys. Rev. Lett. 98, 184101 (2007).
  * Esfahani  _et al._ [2012] R. K. Esfahani, F. Shahbazi, and K. A. Samani, Noise-induced synchronization in small world networks of phase oscillators, Phys. Rev. E 86, 036204 (2012).
  * Lai and Porter [2013] Y. M. Lai and M. A. Porter, Noise-induced synchronization, desynchronization, and clustering in globally coupled nonidentical oscillators, Phys. Rev. E 88, 012905 (2013).
  * Kurebayashi  _et al._ [2014] W. Kurebayashi, T. Ishii, M. Hasegawa, and H. Nakao, Design and control of noise-induced synchronization patterns, EPL 107, 10009 (2014).
  * Russo and Shorten [2018] G. Russo and R. Shorten, On common noise-induced synchronization in complex networks with state-dependent noise diffusion processes, Physisca D 369, 47 (2018).
  * Touboul  _et al._ [2020] J. D. Touboul, C. Piette, L. Venance, and G. B. Ermentrout, Noise-induced synchronization and antiresonance in interacting excitable systems: Applications to deep brain stimulation in parkinson’s disease, Phys. Rev. X 10, 011073 (2020).
  * Shajan  _et al._ [2021] E. Shajan, M. P. Asir, S. Dixit, J. Kurths, and M. D. Shrimali, Enhanced synchronization due to intermittent noise, New J. Phys. 23, 112001 (2021).


# Simple Weak Coresets for Non-Decomposable Classification Measures

Jayesh Malaviya1, Anirban Dasgupta1, Rachit Chhaya2

###### Abstract

While coresets have been growing in terms of their application, barring few
exceptions, they have mostly been limited to unsupervised settings. We
consider supervised classification problems, and non-decomposable evaluation
measures in such settings. We show that stratified uniform sampling based
coresets have excellent empirical performance that are backed by theoretical
guarantees too. We focus on the F1 score and Matthews Correlation Coefficient,
two widely used non-decomposable objective functions that are nontrivial to
optimize for, and show that uniform coresets attain a lower bound for coreset
size, and have good empirical performance, comparable with “smarter” coreset
construction strategies.

##  1 Introduction

In typical classification tasks, multiple objective functions are often at
stake— one is the (surrogate) classification objective being optimized, and
the other is the real measure of performance. This “real measure” is non-
differentiable and, more importantly, often a non-decomposable function over
the set of input points, i.e., it cannot be written as a sum over the input
points. Popular examples include $F_{1}$ score, Matthews Correlation
Coefficient (MCC), area under the curve (AUC-ROC) measures, and various
variants of combinations of precision and recall measures e.g. H-mean, G-mean
etc. In spite of being non-differentiable and non-decomposable, such
classification measures are attractive since they help portray the tradeoffs
between precision and recall, help enable the handling of mild to severe label
imbalance, etc.

Such non-additive measures are generally optimized empirically by choosing a
surrogate decomposable measure, then optimizing the decision boundary
threshold using grid search. In recent years, a host of algorithms have been
developed for optimizing the non-decomposable measures directly (Joachims
2005; Nan et al. 2012; Narasimhan, Kar, and Jain 2015; Eban et al. 2017).
However, the main drawback remains that the algorithms developed are often not
very efficient in practice and, thereby, remain harder to scale over large
datasets.

For decomposable loss functions, such as for regression or matrix
factorization, one way in which this complexity of training has been
circumvented is by constructing coresets— summaries of the dataset that enable
an optimizer to optimize over the coreset only and give both a theoretically
guaranteed as well as empirically satisfying performance for the full data.
The major tool for coreset creation remains importance sampling, and that
relies crucially on the decomposability of the loss function in order to
deduce the importance weights. Indeed, in traditional classification coreset
literature, researchers have explored various coreset building mechanisms for
logistic loss (Munteanu et al. 2018), SVM (Tukan et al. 2021), etc. However,
again the main catch is their evaluation and bounds focus on the decomposable
surrogates such as the logistic loss function, hinge loss function, etc. (Mai,
Musco, and Rao 2021). For non-decomposable performance measures e.g. F1 score,
MCC score, AUC etc. there does not exist any such coreset creation mechanisms.

Our paper is the first step along this direction. In this work, we show that
for F1-score and MCC, applying stratified uniform sampling is enough to obtain
a (weak) coreset that preserves the value of these measures up to a small
additive error for an interesting set of queries that contains the optimal. We
also show a lower bound for strong coresets for the F1 and the MCC scores,
implying that we cannot do much better than uniform sampling. We provide
experimental evidence of our results on real datasets and for various
classifiers and sampling techniques. Even though we formally prove our bounds
and theory for F1-score and MCC, it applies to most contingency table-based
measures.

Following are our main contributions:

  1. 1.

We provide lower bounds against construction of strong coresets for both MCC
and F1 score measures.

  2. 2.

We show that sampling uniformly from each class in a stratified manner gives a
weak coreset for the F1 score and a weak coreset with a small additive error
for MCC. Here weak signifies that our coreset works for a set of a large
number of ’important’ classifiers, including the optimal.

  3. 3.

We provide empirical results for a number of different classifiers and real
data sets comparing uniform sampling with other well-known sophisticated
coreset construction strategies.

The rest of the paper is organized as follows: Sections 2 and 3 give the
necessary background and related work. Section 4 provides lower
bounds(negative results) for coresets for both MCC and F1 scores. Sections 5
and 6 give the analysis of our weak coreset construction guarantees for F1
score and MCC. We discuss the experiments and comparison of uniform sampling
on real data sets with a variety of sampling algorithms in section 7 and
conclude in section 8.

##  2 Background

A coreset can be considered to be a weighted subset of data from the original
dataset or some different small-sized representation of the original dataset.
In designing a coreset, the main challenge is to build one with provable
tradeoffs between the approximation error and the coreset size.

We interchangeably refer to classifiers as "query" and denote them by $q$. $Q$
denotes the set of all possible classifiers.

######  Definition 2.1.

(Coreset) (Agarwal et al. 2005) Given a weighted dataset $X$, let $x\in X$ and
$\mu_{X}(x)$ be its corresponding nonnegative weight. Let $Q$ be a set of
solutions known as query space and $q\in Q$ be a query. For each $q\in Q$, let
$f_{q}:X\rightarrow\mathbb{R}_{\geq 0}$ be a non-negative function. Define
$cost(X,q)=\sum_{x\in X}\mu_{X}(x)f_{q}(x).$ For $\epsilon>0$, a weighted-set
$(C,w)$ is an $\epsilon$-coreset of $X$ for the cost function $\\{f_{q}\\}$,
if $\forall q\in Q$,

$\left|cost(X,q)-cost(C,q)\right|\leq\epsilon\;cost(X,q).$

For coresets with a $\theta$ additive error, the above guarantee becomes the
following– for all $q$.

$\left|cost(X,q)-cost(C,q)\right|\leq\epsilon\;cost(X,q)+\theta.$

Though stated in terms of decomposable loss functions, this definition also
applies to measures which are not decomposable but are rather functions of
entire dataset as a whole. We will also be dealing with weak coresets, i.e.
our coresets will satisfy the above guarantees for a specific subset of the
solution space, that contains the optimal.

In this text, we mainly deal with uniform sampling, and with two non-
decomposable loss functions, the F1 score and the MCC score. For a particular
classifier $q$, let $tp(q),tn(q),fp(q)$ and $fn(q)$ denote the true-positive,
the true-negative, the false positive and false negative respectively. We will
sometimes drop the $(q)$ notation when it is clear from context.

The F1 score is defined as the following. For a classifier $q$,

$F_{1}(q)=2\cdot\frac{precision\cdot
recall}{precision+recall}=\frac{tp}{tp+\frac{1}{2}(fp+fn)}$

The MCC score is defined as the following (we leave off the "$(q)$" for lack
of space).

$\displaystyle MCC(q)$ $\displaystyle=\frac{tp\cdot tn-fp\cdot
fn}{\sqrt{(tp+fp)(tp+fn)(tn+fp)(tn+fn)}}$
$\displaystyle=\frac{\frac{tp}{n}-T^{{}^{\prime}}P^{{}^{\prime}}}{\sqrt{T^{{}^{\prime}}P^{{}^{\prime}}(1-T^{{}^{\prime}})(1-P^{{}^{\prime}})}}$

where $T^{\prime}$ denotes the fraction of ground truth positives and
$P^{\prime}=(tp+fp)/n$ denotes the fraction of predicted positives. We will
use $Y^{+}$ and $Y^{-}$ to denote the set of all positive and negatively
labeled points. Sometimes we will also use the same notation to denote the
total number of positive and negatively labeled points.

##  3 Related Work

(Joachims 2005) formulated the non-decomposable measures as a structural
prediction problem and gave a direct optimization algorithm using multivariate
SVM formulation. The primary idea is to reduce the number of constraints in
multivariate SVM by finding the most violated constraint in each iteration,
preparing the candidate set, and applying multivariate SVM over that small set
only. But in their algorithm for calculation of the argmax for most violated
constraints, the algorithm must go over all possible configurations of the
contingency table, which amounts to $n^{2}$ different contingency tables.

(Kar, Narasimhan, and Jain 2014) extend the existing online learning models
for point-loss functions to non-decomposable loss functions. They also develop
scalable SGD solvers for non-decomposable loss functions. Their work uses the
previous result of representing the non-decomposable loss function as
structural SVMs (Joachims 2005) and optimizing them. Deep learning based
methods for optimizing non-decomposable losses have also been explored in
(Sanyal et al. 2018). We note that our work on coresets is orthogonal to the
work on optimizing such losses, any such optimizer could be used in parallel
with our coreset technique.

(Eban et al. 2017) proposed an alternative formulation based on simple direct
bounds on per-sample quantities indicating whether each sample is a true
positive or a false positive. Using these bounds, they constructed global
bounds on ranking-based measures such as precision at fixed recall, recall at
fixed precision, and F1 score, among others. From these global bounds, they
derived the surrogate objective function and the closed-form alternate
optimization problem, which is then optimized. However, they did not discuss
empirical results for the F1 score and MCC. (Bénédict et al. 2022) try to
maximize a surrogate loss in place of the F1 score. There has been some work
in active sampling to estimate F1 score using optimal subsampling (Sawade,
Landwehr, and Scheffer 2010) or iterative importance sampling (Poms et al.
2021) ,however, both the motivation and guarantees are different from the
coreset guarantees.

Coresets have been studied since (Agarwal et al. 2005). One of the popular
ways to create coreset is to construct a probability distribution, called
sensitivity, over the set of input points (Langberg and Schulman 2010; Feldman
and Langberg 2011). Sampling points proportional to their sensitivities and
appropriately reweighing them gives a coreset with high probability (Langberg
and Schulman 2010; Feldman and Langberg 2011). However, the major technical
challenge in this method is to figure out computationally inexpensive upper
bounds to the sensitivity scores for each cost function. More details about
the construction of coresets using the sensitivity framework can be found in
(Feldman and Langberg 2011; Bachem, Lucic, and Krause 2017, 2018; Braverman et
al. 2016; Mai, Musco, and Rao 2021; Feldman 2020) and references within. While
coresets using this framework have theoretical guarantees , it has been shown
that for some problems you can not do much better than uniform sampling
(Samadian et al. 2020). Our paper also has similar results. It has been shown
by (Braverman et al. 2022) that using uniform sampling with some careful
analysis can also give coreset guarantees for clustering problems.
Additionally empirically uniform sampling has been shown to be comparable to
other techniques for many real data sets (Lu, Raff, and Holt 2023).

##  4 Lower Bounds

In this section we first present lower bounds for strong coresets for $F_{1}$
score and MCC.

### Lower bound for Strong $F_{1}$ coresets

######  Theorem 4.1.

Let $F_{1}(q)$ be the $F_{1}$ score on full dataset $D$ with fixed query $q$
and $\tilde{F_{1}}(q)$ be the $F_{1}$ score on coreset $C$. Then, there does
not exist a strong coreset $C$ with a size less than $n$ that satisfies
relative error approximation i.e. $\tilde{F_{1}}(q)\in(1\pm\epsilon)F_{1}(q)$
for all queries $q\in Q$.

###### Proof.

Let $d$ be any non-negative even integer. Let ${\cal S}$ be the set of all
sets of size $d/2$. We define the set $P$ of points as follows: In order to
generate each point $p$, choose $B_{p}\in{\cal S}$, and $y_{p}\in\\{\pm 1\\}$.
The vector $p$ is defined as following— $p_{i}=-y_{p}$ for all $i\in B_{p}$,
and $p_{i}=0$ for all $i\in[d]\setminus B_{p}$, $p_{d+1}=y_{p}/2$. The label
of the point $p$ is also $y_{p}$.

For each point $p$, we also define a corresponding classifier $w_{p}$ in the
following way— $w_{p}[i]=0$ if $i\in B_{p}$, $w_{p}[i]=1$ if $i\in[d]\setminus
B_{p}$, and $w_{p}[d+1]=1$.

By the above construction, for every point

$\displaystyle p\cdot w_{p}=y_{p}/2.$

Hence $sign(p\cdot w_{p})=y_{p}$, and hence $p$ is correctly classified. For
any point $q\neq p$, $B_{p}\neq B_{q}$. Hence,

$\displaystyle q\cdot w_{p}=-y_{q}|B_{q}\cap\bar{B_{p}}|+y_{q}/2$

Since $|B_{q}\cap\bar{B_{p}}|\geq 1$, $sign(q\cdot w_{p})=-y_{q}$, i.e. $q$ is
misclassified.

So for a point $p$ with $y_{p}=+1$, for the query $w_{p}$ the $F_{1}$ score is
$\frac{1}{1+(n-2)/2}$. However, if the coreset does not sample the point $p$,
the $F_{1}$ score for $w_{p}$ would be zero, which is not a relative error
approximation. Since this is true for every point $p$, the coreset has to be
of size $n$.

∎

### Lower bound for strong $MCC$ coresets

######  Theorem 4.2.

Let $MCC(q)$ be the $MCC$ score on full dataset $D$ with fixed query $q$ and
$\widetilde{MCC}(q)$ be the $MCC$ score on coreset $C$. Then, there does not
exist a strong coreset $C$ with a size less than $n$ that satisfies relative
error approximation i.e. $\widetilde{MCC}(q)\in(1\pm\epsilon)MCC(q)$ for all
queries $q\in Q$.

###### Proof.

Let $d\geq 4$ be any non-negative even integer. Let ${\cal S}$ be the set of
all sets of size $d/2$. Let $n={d\choose d/2}$. Let $y_{p}\in\\{\pm 1\\}$ be
such that exactly $n/2$ points have $y_{p}=+1$. We define the set $P$ of $n$
points as follows: in order to generate each point $p\in\mathbb{R}^{d+1}$,
choose $B_{p}\in{\cal S}$. The vector $p$ is defined as follows: $p_{i}=X_{p}$
for all $i\in B_{p}$, and $p_{i}=0$ for all $i\in[d]\setminus B_{p}$,
$p_{d+1}=y_{p}/2$. The label of the point $p$ is also $y_{p}$.

Now, lets define $X_{p}$ for points, $1\leq p\leq n$ as follows. If the true
label of point $p$ is $y_{p}\in Y^{+}$ then, $X_{p}=y_{p}$ for $1\leq
p\leq\frac{Y^{+}}{2}$, and $-y_{p}$ else. Similarly, for $p\in Y^{-}$,
$X_{p}=y_{p}$ for $1\leq p\leq\frac{Y^{-}}{2}$ and $-y_{p}$ else.

For each point $p$, we also define a corresponding classifier $w_{p}$ in the
following way— $w_{p}[i]=0$ if $i\in B_{p}$, $w_{p}[i]=1$ if $i\in[d]\setminus
B_{p}$, and $w_{p}[d+1]=1$.

By the above construction, for every point

$\displaystyle p\cdot w_{p}=y_{p}/2.$

Hence $sign(p\cdot w_{p})=y_{p}$, and hence $p$ is correctly classified. For
any point $q\neq p$, $B_{p}\neq B_{q}$. Hence,

$\displaystyle q\cdot w_{p}=X_{q}|B_{q}\cap\bar{B_{p}}|+y_{q}/2$

Since $|B_{q}\cap\bar{B_{p}}|\geq 1$, $sign(q\cdot w_{p})=X_{q}$, i.e. $q$ is
classified as per the sign of $X_{q}$.

Therefore, for the classifier $w_{p}$, all of the points, except point $p$,
classify according to $X_{q}$.

Notice that we have designed $X_{p}$ for all $p$ such that for $Y^{+}$ and
$Y^{-}$, it will classify half points positive and half points as negative.

Therefore for a point $p$ with $y_{p}=+1$ and classifier $w_{p}$, we have
$tp=\frac{n-1}{4}+1$, $tn=\frac{n-1}{4}$, $fn=\frac{n-1}{4}$ and
$fp=\frac{n-1}{4}$ respectively for balanced setup i.e.
$Y^{+}=Y^{-}=\frac{n}{2}$.

For above setup $MCC$ score is,

$\displaystyle MCC$ $\displaystyle=\frac{tp\cdot tn-fp\cdot
fn}{\sqrt{(tp+fp)(tp+fn)(tn+fp)(tn+fn)}}$ $\displaystyle=\frac{tp\cdot tn-
fp\cdot fn}{\sqrt{(tp+fp)Y^{+}Y^{-}(tn+fn)}}$
$\displaystyle=\frac{(\frac{n-1}{4}+1)\cdot(\frac{n-1}{4})-(\frac{n-1}{4})\cdot(\frac{n-1}{4})}{\frac{n}{2}\sqrt{(\frac{n+1}{2})(\frac{n-1}{2})}}$
$\displaystyle=\theta\left(\frac{1}{n}\right)$

However, if the coreset does not sample the point $p$, then we have
$tp=\frac{n-1}{4}$, $tn=\frac{n-1}{4}$, $fn=\frac{n-1}{4}$ and
$fp=\frac{n-1}{4}$ respectively, thus $MCC$ score for $w_{p}$ would be zero,
which is not a relative error approximation. Since this is true for every
point $p$, the strong coreset has to be of size $n$.

∎

##  5 Weak coreset for queries with high $F_{1}$ score

We will be using the following result of (Li, Long, and Srinivasan 2001) to
get our coreset guarantees for all queries in the query set of our interest.

######  Theorem 5.1.

(Li, Long, and Srinivasan 2001)

Let, $\alpha>0$, $v>0$ and $\delta>0$. Fix a countably infinite domain $X$ and
let $q(\cdot)$ be any probability distribution over $X$. Let $F$ be a set of
functions from $X$ to $\left[0,1\right]$ with $Pdim(F)=d^{{}^{\prime}}$.
Denote by $C$ a sample of $m$ points from $X$ sampled independently according
to $q(\cdot)$. Then, for $m\in\Omega\left(\frac{1}{\alpha^{2}\cdot
v}\left(d^{{}^{\prime}}\log(1/v)+\log(1/\delta)\right)\right)$, with
probability at least $1-\delta$ it holds that,

$\forall f\in F;d_{v}\left(\sum_{x\in X}q(x)f(x),\frac{1}{|C|}\sum_{x\in
C}f(x)\right)\leq\alpha$

where, $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$.

Now we state our theorem for bounding the coreset size and performance for
$F_{1}$ score.

######  Theorem 5.2.

Let $\epsilon>0$ and $c>1$. Consider an instance where number of positive
samples are $Y^{+}$ and number of negative samples are $Y^{-}$, and
$n=Y^{+}+Y^{-}$. We consider $Q_{\gamma}$ to be the set of queries such that
$F_{1}(q)\geq\gamma$ and $tp\geq
max\left(\frac{n(1-c\cdot\epsilon)}{2c\cdot(1-\epsilon)},\frac{n(1+c\cdot\epsilon)}{2c\cdot(1+\epsilon)}\right)$
for $q\in Q_{\gamma}$. Let $d=$ vc-dimension$(Q_{\gamma})$.

Stratified uniform sampling with a total of
$\left(\frac{(2-\gamma)^{2}}{\gamma^{2}\epsilon^{2}}+\frac{1}{\epsilon^{2}}+\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\frac{1}{\epsilon^{2}}\right)\cdot\left(d+\log\frac{1}{\delta}\right)$
samples would be able to give a coreset for $Q_{\gamma}$ that satisfies
$\tilde{F_{1}}(q)\in(1\pm c\cdot\epsilon)F_{1}(q)$ for all queries $q\in
Q_{\gamma}$ with probability at least $1-3\delta$, for a suitable $c>1$.

###### Proof.

We have, $\frac{tp}{tp+\frac{1}{2}(fp+fn)}=F_{1}\geq\gamma$, and hence
$\frac{tp}{\frac{1}{2}(fp+fn)}\geq\frac{\gamma}{1-\gamma}$. Also,
$tp+fp+fn\geq Y^{+}$. We now find the minimum value of $tp$ satisfying these
two inequalities.

From above,
$tp=\left(\frac{\gamma}{1-\gamma}\right)\cdot\frac{1}{2}(fp+fn)+k$, where
$k\geq 0$. Then,
$\left(\frac{\gamma}{1-\gamma}\right)\frac{1}{2}(fp+fn)+k+(fp+fn)\geq Y^{+}$
and hence
$\frac{1}{2}(fp+fn)\geq(Y^{+}-k)/\left(\frac{\gamma}{1-\gamma}+2\right)$. Thus
$tp=\frac{\left(\frac{\gamma}{1-\gamma}\right)Y^{+}}{\left(\frac{\gamma}{1-\gamma}+2\right)}+\frac{2k}{\frac{\gamma}{1-\gamma}+2}\geq\frac{\gamma\cdot
Y^{+}}{(2-\gamma)}$.

Let $\widetilde{tp}$ and $\widetilde{fn}$ be the true positive and false
negative counts obtained from the sampled set. Let all the negative samples be
given a weight of $\frac{Y^{-}}{Y^{+}}$. Hence, let
$\widetilde{\widetilde{fp}}$ defined as following—
$\widetilde{\widetilde{fp}}=\left(\frac{Y^{-}}{Y^{+}}\right)\widetilde{fp}.$
Similarly, let $\widetilde{\widetilde{tn}}$ defined as following—
$\widetilde{\widetilde{tn}}=\left(\frac{Y^{-}}{Y^{+}}\right)\widetilde{tn}.$
Our algorithm uses the four estimates $\widetilde{tp}$,
$\widetilde{\widetilde{fp}}$, $\widetilde{\widetilde{tn}}$ and
$\widetilde{fn}$ to estimate the F1 score. We first show the quality of each
of these estimates by applying Theorem 5.1 individually.

For $tp$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x},\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}\right)\leq\alpha_{1}$

where, $\delta_{x}={1}(x\in tp)$ is indicator variable and
$d_{v}(a,b)=\frac{|a-b|}{a+b+v}$

$\displaystyle=\frac{\left|\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x}-\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}\right|}{\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x}+\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}+v}\leq\alpha_{1}$
$\displaystyle=\frac{\left|\frac{tp}{Y^{+}}-\frac{\widetilde{tp}}{|S_{1}|}\right|}{\frac{tp}{Y^{+}}+\frac{\widetilde{tp}}{|S_{1}|}+v}\leq\alpha_{1}$
$\displaystyle=\left|\frac{tp}{Y^{+}}-\frac{\widetilde{tp}}{|S_{1}|}\right|\leq
3\alpha_{1}$

Since, $\frac{tp}{Y^{+}}$ and $\frac{\widetilde{tp}}{|S_{1}|}$ is less than
one, lets take $v=\frac{1}{2}$.

$\widetilde{tp}\in tp\left(\frac{S_{1}}{Y^{+}}\right)\pm
S_{1}\cdot(3\alpha_{1})$

$\frac{Y^{+}}{S_{1}}\widetilde{tp}\in tp\pm Y^{+}\cdot(3\alpha_{1})$

Since, $tp\geq\frac{\gamma\cdot Y^{+}}{(2-\gamma)}$, we have
$Y^{+}\leq\frac{tp\cdot(2-\gamma)}{\gamma}$.

$\frac{Y^{+}}{S_{1}}\widetilde{tp}\in
tp\pm(3\alpha_{1})\cdot\frac{tp\cdot(2-\gamma)}{\gamma}$

$\frac{Y^{+}}{S_{1}}\widetilde{tp}\in\left(1\pm(3\alpha_{1})\cdot\frac{(2-\gamma)}{\gamma}\right)tp$

$\widetilde{tp}\in\left(1\pm\epsilon\right)tp\frac{S_{1}}{Y^{+}}$

where, $\epsilon=(3\alpha_{1})\cdot\frac{(2-\gamma)}{\gamma}$

Therefore, $\alpha_{1}=\frac{\gamma\cdot\epsilon}{3(2-\gamma)}$.

Now, size of samples required to satisfy the above approximation using Theorem
5.1 is, $S_{1}=\Omega\left(\frac{1}{\alpha_{1}^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\frac{(2-\gamma)^{2}}{\gamma^{2}\cdot\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q_{\gamma}\subset Q$ .

For $fn$ approximation, we can similarly show that

$\widetilde{fn}\in fn\left(\frac{S_{2}}{Y^{+}}\right)\pm
S_{2}\cdot(3\alpha_{2}).$

Using $\epsilon=(3\alpha_{2})$, we have the additive error to be $\epsilon
S_{2}$.

Now, size of samples required to satisfy the above approximation using Theorem
5.1 is, $S_{2}=\Omega\left(\frac{1}{\alpha_{2}^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q_{\gamma}\subset Q$ .

For $fp$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{z\in
Y^{-}}\frac{1}{Y^{-}}\delta_{z},\frac{1}{|S_{3}|}\sum_{z\in
S_{3}}\delta_{z}\right)\leq\alpha_{3}$

where, $\delta_{z}=1(z\in fp)$ and $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$. Again,
using similar arguments, we can show that

$\widetilde{fp}\in fp\left(\frac{S_{3}}{Y^{-}}\right)\pm S_{3}\cdot\epsilon,$

where again $\epsilon\geq 3\alpha_{3}$.

For $\widetilde{\widetilde{fp}}$, we get the following bound.

$\widetilde{\widetilde{fp}}=\left(\frac{Y^{-}}{Y^{+}}\right)\widetilde{fp}\in
fp\left(\frac{S_{3}}{Y^{+}}\right)\pm
S_{3}\cdot(3\alpha_{3})\left(\frac{Y^{-}}{Y^{+}}\right)$

After applying reweighing our modified $\alpha_{3}$ is defined as,
$\alpha_{3}^{{}^{\prime}}=\frac{\epsilon}{3}\left(\frac{Y^{+}}{Y^{-}}\right)$.

Now, size of samples require to satisfy the above approximation using Theorem
5.1 is, $S_{3}=\Omega\left(\frac{1}{(\alpha_{3}^{{}^{\prime}})^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q$ where $Q_{\gamma}\subset Q$ .

Thus, in-order to satisfy all three approximations viz. $tp$, $fn$ and $fp$ we
would require total sample size,

$\displaystyle S$ $\displaystyle=S_{1}+S_{2}+S_{3}$
$\displaystyle=\left(\frac{(2-\gamma)^{2}}{\gamma^{2}\epsilon^{2}}+\frac{1}{\epsilon^{2}}+\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\frac{1}{\epsilon^{2}}\right)\cdot\left(d+\log\frac{1}{\delta}\right)$

Thus, with probability $1-3\delta$, above approximation for $tp$, $fn$ and
$fp$ holds.

Now, for the coreset left hand side guarantee,

$\displaystyle\tilde{F_{1}}$
$\displaystyle=\frac{\tilde{tp}}{\tilde{tp}+\frac{1}{2}(\tilde{fn}+\widetilde{\widetilde{fp}})}$
$\displaystyle\geq\frac{(1-\epsilon)\frac{S\cdot
tp}{Y^{+}}}{(1-\epsilon)\frac{S\cdot tp}{Y^{+}}+\frac{1}{2}\left[\frac{S\cdot
fn}{Y^{+}}+\frac{S\cdot fp}{Y^{+}}+(\epsilon\cdot
S)\left(1+\frac{Y^{-}}{Y^{+}}\right)\right]}$
$\displaystyle=\frac{(1-\epsilon)tp}{(1-\epsilon)tp+\frac{1}{2}\left[fn+fp+(\epsilon)\left(Y^{+}+Y^{-}\right)\right]}$
$\displaystyle=\frac{(1-\epsilon)tp}{(1-\epsilon)tp+\frac{1}{2}\left[fn+fp+(\epsilon\cdot
n)\right]}$
$\displaystyle=\frac{(1-\epsilon)tp}{tp+\frac{1}{2}(fn+fp)-\left[\epsilon\cdot
tp-\frac{\epsilon\cdot n}{2}\right]}$

If the number of samples belongs to $tp$ is chosen to satisfy
$tp\geq\frac{n(1-c\cdot\epsilon)}{2c\cdot(1-\epsilon)}$, then we have that

$\displaystyle\tilde{F_{1}}$
$\displaystyle\geq\frac{(1-\epsilon)tp}{tp+\frac{1}{2}(fn+fp)-\left[\epsilon\cdot
tp-\frac{\epsilon\cdot n}{2}\right]}$
$\displaystyle\geq\frac{(1-c\cdot\epsilon)tp}{tp+\frac{1}{2}(fn+fp)}=(1-c\cdot\epsilon)F_{1}$

Similarly, for the coreset right hand side guarantee,

$\displaystyle\tilde{F_{1}}$
$\displaystyle=\frac{\tilde{tp}}{\tilde{tp}+\frac{1}{2}(\tilde{fn}+\widetilde{\widetilde{fp}})}$
$\displaystyle\leq\frac{(1+\epsilon)\frac{S\cdot
tp}{Y^{+}}}{(1+\epsilon)\frac{S\cdot tp}{Y^{+}}+\frac{1}{2}\left[\frac{S\cdot
fn}{Y^{+}}+\frac{S\cdot fp}{Y^{+}}-(\epsilon\cdot
S)\left(1+\frac{Y^{-}}{Y^{+}}\right)\right]}$
$\displaystyle=\frac{(1+\epsilon)tp}{(1+\epsilon)tp+\frac{1}{2}\left[fn+fp-(\epsilon)\left(Y^{+}+Y^{-}\right)\right]}$
$\displaystyle=\frac{(1+\epsilon)tp}{(1+\epsilon)tp+\frac{1}{2}\left[fn+fp-(\epsilon\cdot
n)\right]}$
$\displaystyle=\frac{(1+\epsilon)tp}{tp+\frac{1}{2}(fn+fp)+\left[\epsilon\cdot
tp-\frac{\epsilon\cdot n}{2}\right]}$

Again, using the similar assumptions on $tp$, we have that for
$tp\geq\frac{n(1+c\cdot\epsilon)}{2c\cdot(1+\epsilon)}$, we get

$\displaystyle\tilde{F_{1}}$
$\displaystyle\leq\frac{(1+\epsilon)tp}{tp+\frac{1}{2}(fn+fp)+\left[\epsilon\cdot
tp-\frac{\epsilon\cdot n}{2}\right]}$
$\displaystyle\leq\frac{(1+c\cdot\epsilon)tp}{tp+\frac{1}{2}(fn+fp)}=(1+c\cdot\epsilon)F_{1}$

∎

##  6 Weak coreset for $MCC$

######  Theorem 6.1.

Let $\epsilon>0$. Consider an instance where number of positive samples are
$Y^{+}$ and number of negative samples are $Y^{-}$, and $n=Y^{+}+Y^{-}$. Let
$T$ to be the ground truth positive $0/1$ labels and $P$ to be the predicted
positive $0/1$ labels. Let $tp,fp,fn$ be the true positive, false positive and
false negative on the full data,
$T^{{}^{\prime}}=\frac{\sum_{i}T_{i}}{n}=\frac{tp+fn}{n}=\frac{\left|Y^{+}\right|}{n}$
and $P^{{}^{\prime}}=\frac{\sum_{i}P_{i}}{n}=\frac{tp+fp}{n}$. We consider
$Q_{\gamma}$ to be the set of queries such that $tp\geq\gamma\cdot n$ and
$tn\geq\gamma\cdot n$ for $q\in Q_{\gamma}$. Let $d=vc-
dimension\left(Q_{\gamma}\right)$. We claim that uniform sampling with
$\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\left(2+2\cdot\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\right)\right)$
samples would be able to give a coreset for $Q_{\gamma}$ that satisfies
$\frac{MCC(q)}{\left(1+\frac{\epsilon}{\gamma}\right)}-2\cdot\epsilon\cdot
C\leq\widetilde{MCC}(q)\leq\frac{MCC(q)}{\left(1-\frac{\epsilon}{\gamma}\right)}+2\cdot\epsilon\cdot
C^{{}^{\prime}}$ for all queries $q\in Q_{\gamma}$ with probability at least
$1-4\delta$, where
$C\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1+\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$
and
$C^{{}^{\prime}}\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1-\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$.

The proof can be found in the appendix.

Coreset Algorithm | CoverType Time (in sec) | Adult Time (in sec) | KDD Cup ’99 Time (in sec)
---|---|---|---
uniform | 0.01418 | 0.003462 | 0.01028
leverage score | 0.1331 | 0.01132 | 0.0909
lewis score | 2.4918 | 0.19029 | 1.9072
k-means | 0.05942 | 0.007611 | 0.0400
Table 1: Time taken to prepare coreset of 10% of full dataset for different
datasets.

(a) CovType Logistic

(b) CovType SVM

(c) CovType MLP

Figure 1: $MCC$ Score on CovType

(a) CovType Logistic

(b) CovType SVM

(c) CovType MLP

Figure 2: $F_{1}$ Score on CovType

(a) KDDCup Logistic

(b) KDDCup SVM MCC

(c) KDDCup MLP MCC

Figure 3: $MCC$ Score on KDDCup

(a) KDDCup Logistic

(b) KDDCup SVM

(c) KDDCup MLP

Figure 4: $F_{1}$ Score on KDDCup

##  7 Experiments

All experiments were run on a computer with Nvidia Tesla V100 GPU with 32 GB
memory and 28 CPUs. We used Python and its frameworks to implement our
experiments.

#### Data Sets:

The COVERTYPE (Blackard 1998) data consists of 581, 012 cartographic
observations of different forests with 54 features. The task is to predict the
type of trees at each location (49% positive). We selected in a stratified way
50,000 samples from the real data and used them as our training data. The
KDDCUP ’99 (Stolfo et al. 1999) data comprises of 494,021 network connections
with 41 features, and the task is to detect network intrusions (20% positive).
In our experiments, we selected in a stratified way 50,000 samples from the
real data and used them as training data. The Adult (Becker and Kohavi 1996)
dataset is a widely-used dataset containing information about individuals from
the 1994 U.S. Census Bureau database. It consists of approximately 32,000
instances with 14 attributes, including age, education, and occupation. The
dataset aims to predict whether an individual’s income exceeds $50,000 per
year.

Our experiment created binary classification datasets by converting a
multiclass dataset into a binary by flipping labels. Our final binary dataset
class ratios for the CoverType dataset are [31770, 18230], for the Adult
dataset [24294, 7706], and for the KDDCup dataset, it is [40154, 9846]. Here
in $[a,b]$, $a$ is the number of points of positive class, and $b$ represents
a number of points with negative class.

#### Experimental Assessment :

To verify our theoretical claims, we tested a uniform sampling coreset with
some of the sophisticated coresets like leverage score (Drineas, Mahoney, and
Muthukrishnan 2006), $l_{1}$-lewis score (Cohen and Peng 2015), and k-means
coreset by (Bachem, Lucic, and Krause 2018).

As our classifier models, we used SVM classifier with linear kernel; vanilla
logistic regression model from the sklearn library is used with default
hyperparameters and a multilayer perceptron(MLP). For MLP experiments, we
considered a simple MLP classifier with two hidden layers of size 100 each and
the final output layer of size two, as we are dealing with binary
classification. The optimizer used for the MLP is Adam, and the activation
function used is ReLU.

We first prepared different coresets from the full datasets. Then we train our
classifier models: logistic regression, SVM, and Feed Forward Neural Network
on our coreset as well as on the full dataset.

For testing the performance of our coresets, we took models trained using the
coresets and tested them on the entire training dataset. We report the
evaluation measures (F1 and MCC) obtained and compare it with the original
value obtained on full data(using model trained on full data). For all our
experiments, plotted values are means taken over five independent repetitions
of each experiment.

Figures 1 through 4 clearly show that uniform sampling gives superior or
comparable performance to other sophisticated methods for both F1 score and
MCC. Also it can be seen that with increasing coreset size, the performance of
model trained on the coreset also improves as expected. We also measure the
time required to prepare coreset using these techniques on the different
datasets. The times are reported in Table 1. It is clear that uniform sampling
is many times faster than the other methods. Hence at much lower computation
times we get better or comparable performances to other coreset construction
strategies. Some additional experiments can be found in the appendix.

##  8 Conclusion

We initiated the study of coresets for non-decomposable classification
measures, specifically for the F1 score and MCC. We showed lower bounds for
strong coresets and construction of weak coresets using stratified uniform
sampling. It would be interesting to see whether coresets with better additive
guarantees and lesser assumptions on the query vector can be developed.
Similarly, algorithm-specific subset selection strategies could be explored
for more efficiency. The question of tackling other measures, e.g., AUC-ROC,
also remains open.

##  9 Acknowledgments

Anirban Dasgupta would like to acknowledge the support received from Google,
DST(SERB) and Cisco as well as the N Rama Rao Chair position at IIT
Gandhinagar. Jayesh Malaviya and Rachit Chhaya would like to acknowledge the
support from IIT- Gandhinagar and Dhirubhai Ambani Institute of Information
and Communication Technology (DA-IICT) , Gandhinagar, India.

## References

  * Agarwal et al. (2005) Agarwal, P. K.; Har-Peled, S.; Varadarajan, K. R.; et al. 2005.  Geometric approximation via coresets.  _Combinatorial and computational geometry_ , 52(1): 1–30.
  * Bachem, Lucic, and Krause (2017) Bachem, O.; Lucic, M.; and Krause, A. 2017.  Practical coreset constructions for machine learning.  _arXiv preprint arXiv:1703.06476_.
  * Bachem, Lucic, and Krause (2018) Bachem, O.; Lucic, M.; and Krause, A. 2018.  Scalable k-means clustering via lightweight coresets.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 1119–1127.
  * Becker and Kohavi (1996) Becker, B.; and Kohavi, R. 1996.  Adult.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C5XW20.
  * Bénédict et al. (2022) Bénédict, G.; Koops, H. V.; Odijk, D.; and de Rijke, M. 2022.  sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification.  _Transactions on Machine Learning Research_.
  * Blackard (1998) Blackard, J. 1998.  Covertype.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C50K5N.
  * Braverman et al. (2022) Braverman, V.; Cohen-Addad, V.; Jiang, H.-C. S.; Krauthgamer, R.; Schwiegelshohn, C.; Toftrup, M. B.; and Wu, X. 2022.  The power of uniform sampling for coresets.  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , 462–473. IEEE.
  * Braverman et al. (2016) Braverman, V.; Feldman, D.; Lang, H.; Statman, A.; and Zhou, S. 2016.  New frameworks for offline and streaming coreset constructions.  _arXiv preprint arXiv:1612.00889_.
  * Cohen and Peng (2015) Cohen, M. B.; and Peng, R. 2015.  Lp row sampling by lewis weights.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , 183–192.
  * Drineas, Mahoney, and Muthukrishnan (2006) Drineas, P.; Mahoney, M. W.; and Muthukrishnan, S. 2006.  Sampling algorithms for l 2 regression and applications.  In _Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm_ , 1127–1136.
  * Eban et al. (2017) Eban, E.; Schain, M.; Mackey, A.; Gordon, A.; Rifkin, R.; and Elidan, G. 2017.  Scalable learning of non-decomposable objectives.  In _Artificial intelligence and statistics_ , 832–840. PMLR.
  * Feldman (2020) Feldman, D. 2020.  Core-sets: Updated survey.  _Sampling Techniques for Supervised or Unsupervised Tasks_ , 23–44.
  * Feldman and Langberg (2011) Feldman, D.; and Langberg, M. 2011.  A unified framework for approximating and clustering data.  In _Proceedings of the forty-third annual ACM symposium on Theory of computing_ , 569–578.
  * Joachims (2005) Joachims, T. 2005.  A support vector method for multivariate performance measures.  In _Proceedings of the 22nd international conference on Machine learning_ , 377–384.
  * Kar, Narasimhan, and Jain (2014) Kar, P.; Narasimhan, H.; and Jain, P. 2014.  Online and stochastic gradient methods for non-decomposable loss functions.  _Advances in Neural Information Processing Systems_ , 27.
  * Langberg and Schulman (2010) Langberg, M.; and Schulman, L. J. 2010.  Universal $\varepsilon$-approximators for integrals.  In _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_ , 598–607. SIAM.
  * Li, Long, and Srinivasan (2001) Li, Y.; Long, P. M.; and Srinivasan, A. 2001.  Improved bounds on the sample complexity of learning.  _Journal of Computer and System Sciences_ , 62(3): 516–527.
  * Lu, Raff, and Holt (2023) Lu, F.; Raff, E.; and Holt, J. 2023.  A Coreset Learning Reality Check.  _arXiv preprint arXiv:2301.06163_.
  * Mai, Musco, and Rao (2021) Mai, T.; Musco, C.; and Rao, A. 2021.  Coresets for classification–simplified and strengthened.  _Advances in Neural Information Processing Systems_ , 34: 11643–11654.
  * Munteanu et al. (2018) Munteanu, A.; Schwiegelshohn, C.; Sohler, C.; and Woodruff, D. 2018.  On coresets for logistic regression.  _Advances in Neural Information Processing Systems_ , 31.
  * Nan et al. (2012) Nan, Y.; Chai, K. M.; Lee, W. S.; and Chieu, H. L. 2012.  Optimizing F-measure: A tale of two approaches.  _arXiv preprint arXiv:1206.4625_.
  * Narasimhan, Kar, and Jain (2015) Narasimhan, H.; Kar, P.; and Jain, P. 2015.  Optimizing non-decomposable performance measures: A tale of two classes.  In _International Conference on Machine Learning_ , 199–208. PMLR.
  * Poms et al. (2021) Poms, F.; Sarukkai, V.; Mullapudi, R. T.; Sohoni, N. S.; Mark, W. R.; Ramanan, D.; and Fatahalian, K. 2021.  Low-shot validation: Active importance sampling for estimating classifier performance on rare categories.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 10705–10714.
  * Samadian et al. (2020) Samadian, A.; Pruhs, K.; Moseley, B.; Im, S.; and Curtin, R. 2020.  Unconditional coresets for regularized loss minimization.  In _International Conference on Artificial Intelligence and Statistics_ , 482–492. PMLR.
  * Sanyal et al. (2018) Sanyal, A.; Kumar, P.; Kar, P.; Chawla, S.; and Sebastiani, F. 2018.  Optimizing non-decomposable measures with deep networks.  _Machine Learning_ , 107: 1597–1620.
  * Sawade, Landwehr, and Scheffer (2010) Sawade, C.; Landwehr, N.; and Scheffer, T. 2010.  Active estimation of f-measures.  _Advances in Neural Information Processing Systems_ , 23.
  * Stolfo et al. (1999) Stolfo, S.; Fan, W.; Lee, W.; Prodromidis, A.; and Chan, P. 1999.  KDD Cup 1999 Data.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C51C7N.
  * Tukan et al. (2021) Tukan, M.; Baykal, C.; Feldman, D.; and Rus, D. 2021.  On coresets for support vector machines.  _Theoretical Computer Science_ , 890: 171–191.

##  Appendix A Weak coreset for $MCC$

######  Theorem A.1.

Let $\epsilon>0$. Consider an instance where number of positive samples are
$Y^{+}$ and number of negative samples are $Y^{-}$, and $n=Y^{+}+Y^{-}$. Let
$T$ to be the ground truth positive $0/1$ labels and $P$ to be the predicted
positive $0/1$ labels. Let $tp,fp,fn$ be the true positive, false positive and
false negative on the full data,
$T^{{}^{\prime}}=\frac{\sum_{i}T_{i}}{n}=\frac{tp+fn}{n}=\frac{\left|Y^{+}\right|}{n}$
and $P^{{}^{\prime}}=\frac{\sum_{i}P_{i}}{n}=\frac{tp+fp}{n}$. We consider
$Q_{\gamma}$ to be the set of queries such that $tp\geq\gamma\cdot n$ and
$tn\geq\gamma\cdot n$ for $q\in Q_{\gamma}$. Let $d=vc-
dimension\left(Q_{\gamma}\right)$. We claim that uniform sampling with
$\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\left(2+2\cdot\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\right)\right)$
samples would be able to give a coreset for $Q_{\gamma}$ that satisfies
$\frac{MCC(q)}{\left(1+\frac{\epsilon}{\gamma}\right)}-2\cdot\epsilon\cdot
C\leq\widetilde{MCC}(q)\leq\frac{MCC(q)}{\left(1-\frac{\epsilon}{\gamma}\right)}+2\cdot\epsilon\cdot
C^{{}^{\prime}}$ for all query $q\in Q_{\gamma}$ with probability $1-4\delta$,
where
$C\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1+\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$
and
$C^{{}^{\prime}}\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1-\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$.

###### Proof.

We consider MCC(matthews correlation coefficient) is defined in the follwing
form,

$\displaystyle MCC$
$\displaystyle=\frac{\frac{tp}{n}-T^{{}^{\prime}}P^{{}^{\prime}}}{\sqrt{T^{{}^{\prime}}P^{{}^{\prime}}(1-T^{{}^{\prime}})(1-P^{{}^{\prime}})}}$
$\displaystyle=\frac{\frac{tp}{n}-T^{{}^{\prime}}\left(\frac{tp+fp}{n}\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(\frac{tp+fp}{n}\right)\left(1-\left(\frac{tp+fp}{n}\right)\right)}}$
$\displaystyle=\frac{tp-T^{{}^{\prime}}\left(tp+fp\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(tp+fp\right)\left(tn+fn\right)}}$

Now, we would require approximation for all four quantity viz. $tp$, $tn$,
$fp$ and $fn$ for all query, and for that we would use Theorem 5.1,

For $tp$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x},\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}\right)\leq\alpha_{1}$

where, $\delta_{x}=1(x\in tp)$ and $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$

$\displaystyle=\frac{\left|\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x}-\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}\right|}{\sum_{x\in
Y^{+}}\frac{1}{Y^{+}}\delta_{x}+\frac{1}{|S_{1}|}\sum_{x\in
S_{1}}\delta_{x}+v}\leq\alpha_{1}$
$\displaystyle=\frac{\left|\frac{tp}{Y^{+}}-\frac{\widetilde{tp}}{|S_{1}|}\right|}{\frac{tp}{Y^{+}}+\frac{\widetilde{tp}}{|S_{1}|}+v}\leq\alpha_{1}$
$\displaystyle=\left|\frac{tp}{Y^{+}}-\frac{\widetilde{tp}}{|S_{1}|}\right|\leq
3\alpha_{1}$

Since, $\frac{tp}{Y^{+}}$ and $\frac{\widetilde{tp}}{|S_{1}|}$ is less than
one, lets take $v=\frac{1}{2}$.

$\widetilde{tp}\in tp\left(\frac{S_{1}}{Y^{+}}\right)\pm
S_{1}\cdot(3\alpha_{1})$

where, $\epsilon=(3\alpha_{1})$ for above additive error epsilon, and
therefore, $\alpha_{1}=\frac{\epsilon}{3}$

Now, size of samples require to satisfy the above approximation using Theorem
5.1 is, $S_{1}=\Omega\left(\frac{1}{\alpha_{1}^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q$ where $Q_{\gamma}\subset Q$ .

For $fn$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{y\in
Y^{+}}\frac{1}{Y^{+}}\delta_{y},\frac{1}{|S_{2}|}\sum_{y\in
S_{2}}\delta_{y}\right)\leq\alpha_{2}$

where, $\delta_{y}=1(y\in fn)$ and $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$

$\displaystyle=\frac{\left|\sum_{y\in
Y^{+}}\frac{1}{Y^{+}}\delta_{y}-\frac{1}{|S_{2}|}\sum_{y\in
S_{2}}\delta_{y}\right|}{\sum_{y\in
Y^{+}}\frac{1}{Y^{+}}\delta_{y}+\frac{1}{|S_{2}|}\sum_{y\in
S_{2}}\delta_{y}+v}\leq\alpha_{2}$
$\displaystyle=\frac{\left|\frac{fn}{Y^{+}}-\frac{\widetilde{fn}}{|S_{2}|}\right|}{\frac{fn}{Y^{+}}+\frac{\widetilde{fn}}{|S_{2}|}+v}\leq\alpha_{2}$
$\displaystyle=\left|\frac{fn}{Y^{+}}-\frac{\widetilde{fn}}{|S_{2}|}\right|\leq
3\alpha_{2}$

Since, $\frac{fn}{Y^{+}}$ and $\frac{\widetilde{fn}}{|S_{2}|}$ is less than
one, lets take $v=\frac{1}{2}$.

$\widetilde{fn}\in fn\left(\frac{S_{2}}{Y^{+}}\right)\pm
S_{2}\cdot(3\alpha_{2})$

where, $\epsilon=(3\alpha_{2})$ for above additive error epsilon, and
therefore, $\alpha_{2}=\frac{\epsilon}{3}$

Now, size of samples require to satisfy the above approximation using Theorem
5.1 is, $S_{2}=\Omega\left(\frac{1}{\alpha_{2}^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q$ where $Q_{\gamma}\subset Q$ .

For $fp$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{z\in
Y^{-}}\frac{1}{Y^{-}}\delta_{z},\frac{1}{|S_{3}|}\sum_{z\in
S_{3}}\delta_{z}\right)\leq\alpha_{3}$

where, $\delta_{z}=1(z\in fp)$ and $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$

$\displaystyle=\frac{\left|\sum_{z\in
Y^{-}}\frac{1}{Y^{-}}\delta_{z}-\frac{1}{|S_{3}|}\sum_{z\in
S_{3}}\delta_{z}\right|}{\sum_{z\in
Y^{-}}\frac{1}{Y^{-}}\delta_{z}+\frac{1}{|S_{3}|}\sum_{z\in
S_{3}}\delta_{z}+v}\leq\alpha_{3}$
$\displaystyle=\frac{\left|\frac{fp}{Y^{-}}-\frac{\widetilde{fp}}{|S_{3}|}\right|}{\frac{fp}{Y^{-}}+\frac{\widetilde{fp}}{|S_{3}|}+v}\leq\alpha_{3}$
$\displaystyle=\left|\frac{fp}{Y^{-}}-\frac{\widetilde{fp}}{|S_{3}|}\right|\leq
3\alpha_{3}$

Since, $\frac{fp}{Y^{-}}$ and $\frac{\widetilde{fp}}{|S_{3}|}$ is less than
one, lets take $v=\frac{1}{2}$.

$\widetilde{fp}\in fp\left(\frac{S_{3}}{Y^{-}}\right)\pm
S_{3}\cdot(3\alpha_{3})$

where, $\epsilon=(3\alpha_{3})$ for above additive error epsilon, and
therefore, $\alpha_{3}=\frac{\epsilon}{3}$

Let, $\widetilde{\widetilde{fp}}$ defined as following,

$\widetilde{\widetilde{fp}}=\left(\frac{Y^{-}}{Y^{+}}\right)\widetilde{fp}\in
fp\left(\frac{S_{3}}{Y^{+}}\right)\pm
S_{3}\cdot(3\alpha_{3})\left(\frac{Y^{-}}{Y^{+}}\right)$

Basically we are reweighing all negative class data points by
$\left(\frac{Y^{+}}{Y^{-}}\right)$ and thus this term will also comes in the
calculation of the size to satisfy $\widetilde{\widetilde{fp}}$.

After applying reweighing our modified $\alpha_{3}$ is defined as,
$\alpha_{3}^{{}^{\prime}}=\frac{\epsilon}{3}\left(\frac{Y^{+}}{Y^{-}}\right)$.

Now, size of samples require to satisfy the above approximation using Theorem
5.1 is, $S_{3}=\Omega\left(\frac{1}{(\alpha_{3}^{{}^{\prime}})^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q$ where $Q_{\gamma}\subset Q$ .

For $tn$ approximation,

$\forall q\in Q;d_{v}\left(\sum_{w\in
Y^{-}}\frac{1}{Y^{-}}\delta_{w},\frac{1}{|S_{4}|}\sum_{w\in
S_{4}}\delta_{w}\right)\leq\alpha_{4}$

where, $\delta_{w}=1(w\in tn)$ and $d_{v}(a,b)=\frac{|a-b|}{a+b+v}$

$\displaystyle=\frac{\left|\sum_{w\in
Y^{-}}\frac{1}{Y^{-}}\delta_{w}-\frac{1}{|S_{4}|}\sum_{w\in
S_{4}}\delta_{w}\right|}{\sum_{w\in
Y^{-}}\frac{1}{Y^{-}}\delta_{w}+\frac{1}{|S_{4}|}\sum_{w\in
S_{4}}\delta_{w}+v}\leq\alpha_{4}$
$\displaystyle=\frac{\left|\frac{tn}{Y^{-}}-\frac{\widetilde{tn}}{|S_{4}|}\right|}{\frac{tn}{Y^{-}}+\frac{\widetilde{tn}}{|S_{4}|}+v}\leq\alpha_{4}$
$\displaystyle=\left|\frac{tn}{Y^{-}}-\frac{\widetilde{tn}}{|S_{4}|}\right|\leq
3\alpha_{4}$

Since, $\frac{tn}{Y^{-}}$ and $\frac{\widetilde{tn}}{|S_{4}|}$ is less than
one, lets take $v=\frac{1}{2}$.

$\widetilde{tn}\in tn\left(\frac{S_{4}}{Y^{-}}\right)\pm
S_{4}\cdot(3\alpha_{4})$

where, $\epsilon=(3\alpha_{4})$ for above additive error epsilon, and
therefore, $\alpha_{4}=\frac{\epsilon}{3}$

Let, $\widetilde{\widetilde{tn}}$ defined as following,

$\widetilde{\widetilde{tn}}=\left(\frac{Y^{-}}{Y^{+}}\right)\widetilde{tn}\in
tn\left(\frac{S_{4}}{Y^{+}}\right)\pm
S_{4}\cdot(3\alpha_{4})\left(\frac{Y^{-}}{Y^{+}}\right)$

Basically we are reweighing all negative class data points by
$\left(\frac{Y^{+}}{Y^{-}}\right)$ and thus this term will also comes in the
calculation of the size to satisfy $\widetilde{\widetilde{tn}}$.

After applying reweighing our modified $\alpha_{4}$ is defined as,
$\alpha_{4}^{{}^{\prime}}=\frac{\epsilon}{3}\left(\frac{Y^{+}}{Y^{-}}\right)$.

Now, size of samples require to satisfy the above approximation using Theorem
5.1 is, $S_{4}=\Omega\left(\frac{1}{(\alpha_{4}^{{}^{\prime}})^{2}\cdot
v}\left(d\log\frac{1}{v}+\log\frac{1}{\delta}\right)\right)=\Omega\left(\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\right)$,
with probability $1-\delta$ for all $q\in Q$ where $Q_{\gamma}\subset Q$ .

Thus, in-order to satisfy all four approximations viz. $tp$, $tn$, $fn$ and
$fp$ we would require total sample size,

$\displaystyle S$ $\displaystyle=S_{1}+S_{2}+S_{3}+S_{4}$
$\displaystyle=\left(\frac{1}{\epsilon^{2}}\left(d+\log\frac{1}{\delta}\right)\left(2+2\cdot\left(\frac{Y^{-}}{Y^{+}}\right)^{2}\right)\right)$

Thus, with probability $1-4\delta$, above approximation for $tp$, $tn$, $fn$
and $fp$ holds.

Now, for the MCC coreset left hand side guarantee,

$\displaystyle\begin{split}&\widetilde{MCC}=\frac{\tilde{tp}-T^{{}^{\prime}}\left(\tilde{tp}+\tilde{\tilde{fp}}\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(\tilde{tp}+\tilde{\tilde{fp}}\right)\left(\tilde{\tilde{tn}}+\tilde{fn}\right)}}\\\
&\geq\frac{\frac{tp\cdot
S}{Y^{+}}-(S\cdot\epsilon)-T^{{}^{\prime}}\left(\frac{tp\cdot
S}{Y^{+}}+(S\cdot\epsilon)+\frac{fp\cdot
S}{Y^{+}}+(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left[\frac{tp\cdot
S}{Y^{+}}+(S\cdot\epsilon)+\frac{fp\cdot
S}{Y^{+}}+(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}\right]\left[\frac{tn\cdot
S}{Y^{+}}+(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}+\frac{fn\cdot
S}{Y^{+}}+(S\cdot\epsilon)\right]}}\\\
&=\frac{\frac{S}{Y^{+}}\left[tp-(\epsilon\cdot
Y^{+})-T^{{}^{\prime}}\left(tp+fp+(\epsilon\cdot Y^{+})+(\epsilon\cdot
Y^{-})\right)\right]}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\frac{S}{Y^{+}}\left[tp+fp+(\epsilon\cdot
Y^{+})+(\epsilon\cdot Y^{-})\right]\frac{S}{Y^{+}}\left[tn+fn+(\epsilon\cdot
Y^{-})+(\epsilon\cdot Y^{+})\right]}}\\\
&=\frac{\frac{S}{Y^{+}}\left[tp-T^{{}^{\prime}}(tp+fp)-\left[\epsilon\cdot
Y^{+}+T^{{}^{\prime}}\cdot\epsilon\cdot
n\right]\right]}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\frac{S}{Y^{+}}\left[tp+fp+\epsilon\cdot
n\right]\frac{S}{Y^{+}}\left[tn+fn+\epsilon\cdot n\right]}}\\\
&=\frac{tp-T^{{}^{\prime}}(tp+fp)-2\cdot\epsilon\cdot
Y^{+}}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left[tp+fp+\epsilon\cdot
n\right]\left[tn+fn+\epsilon\cdot n\right]}}\\\
&\geq\frac{tp-T^{{}^{\prime}}(tp+fp)-2\cdot\epsilon\cdot
n}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(1+\frac{\epsilon}{\gamma}\right)\left(tp+fp\right)\left(1+\frac{\epsilon}{\gamma}\right)\left(tn+fn\right)}};tp,tn\geq\gamma\cdot
n\\\
&\geq\frac{\left(1-\frac{2\cdot\epsilon}{\gamma}\right)tp-T^{{}^{\prime}}(tp+fp)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(1+\frac{\epsilon}{\gamma}\right)\left(tp+fp\right)\left(1+\frac{\epsilon}{\gamma}\right)\left(tn+fn\right)}}\\\
&=\frac{tp-T^{{}^{\prime}}(tp+fp)-\left(\frac{2\cdot\epsilon}{\gamma}\right)\cdot
tp}{\left(1+\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(tp+fp\right)\left(tn+fn\right)}}\\\
&\geq\frac{MCC}{\left(1+\frac{\epsilon}{\gamma}\right)}-2\cdot\epsilon\cdot
C\end{split}$

Where, $C=\frac{\left(\frac{1}{\gamma}\right)\cdot
tp}{\left(1+\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(tp+fp\right)\left(tn+fn\right)}}$,
, which can be upper bounded by the following,

$C\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1+\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$

We can have similar guarantee for the right hand side as follows.

$\displaystyle\begin{split}&\widetilde{MCC}=\frac{\tilde{tp}-T^{{}^{\prime}}\left(\tilde{tp}+\tilde{\tilde{fp}}\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(\tilde{tp}+\tilde{\tilde{fp}}\right)\left(\tilde{\tilde{tn}}+\tilde{fn}\right)}}\\\
&\leq\frac{\frac{tp\cdot
S}{Y^{+}}+(S\cdot\epsilon)-T^{{}^{\prime}}\left(\frac{tp\cdot
S}{Y^{+}}-(S\cdot\epsilon)+\frac{fp\cdot
S}{Y^{+}}-(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}\right)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left[\frac{tp\cdot
S}{Y^{+}}-(S\cdot\epsilon)+\frac{fp\cdot
S}{Y^{+}}-(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}\right]\left[\frac{tn\cdot
S}{Y^{+}}-(S\cdot\epsilon)\frac{Y^{-}}{Y^{+}}+\frac{fn\cdot
S}{Y^{+}}-(S\cdot\epsilon)\right]}}\\\
&=\frac{\frac{S}{Y^{+}}\left[tp+(\epsilon\cdot
Y^{+})-T^{{}^{\prime}}\left(tp+fp-(\epsilon\cdot Y^{+})+(\epsilon\cdot
Y^{-})\right)\right]}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\frac{S}{Y^{+}}\left[tp+fp-(\epsilon\cdot
Y^{+})+(\epsilon\cdot Y^{-})\right]\frac{S}{Y^{+}}\left[tn+fn-(\epsilon\cdot
Y^{-})+(\epsilon\cdot Y^{+})\right]}}\\\
&=\frac{\frac{S}{Y^{+}}\left[tp-T^{{}^{\prime}}(tp+fp)+\left[\epsilon\cdot
Y^{+}+T^{{}^{\prime}}\cdot\epsilon\cdot
n\right]\right]}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\frac{S}{Y^{+}}\left[tp+fp-\epsilon\cdot
n\right]\frac{S}{Y^{+}}\left[tn+fn-\epsilon\cdot n\right]}}\\\
&=\frac{tp-T^{{}^{\prime}}(tp+fp)+2\cdot\epsilon\cdot
Y^{+}}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left[tp+fp-\epsilon\cdot
n\right]\left[tn+fn-\epsilon\cdot n\right]}}\\\
&\leq\frac{tp-T^{{}^{\prime}}(tp+fp)+2\cdot\epsilon\cdot
n}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(1-\frac{\epsilon}{\gamma}\right)\left(tp+fp\right)\left(1-\frac{\epsilon}{\gamma}\right)\left(tn+fn\right)}};tp,tn\geq\gamma\cdot
n\\\
&\leq\frac{\left(1+\frac{2\cdot\epsilon}{\gamma}\right)tp-T^{{}^{\prime}}(tp+fp)}{\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(1-\frac{\epsilon}{\gamma}\right)\left(tp+fp\right)\left(1-\frac{\epsilon}{\gamma}\right)\left(tn+fn\right)}}\\\
&=\frac{tp-T^{{}^{\prime}}(tp+fp)+\left(\frac{2\cdot\epsilon}{\gamma}\right)\cdot
tp}{\left(1-\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(tp+fp\right)\left(tn+fn\right)}}\\\
&\leq\frac{MCC}{\left(1-\frac{\epsilon}{\gamma}\right)}+2\cdot\epsilon\cdot
C^{{}^{\prime}}\end{split}$

Where, $C^{{}^{\prime}}=\frac{\left(\frac{1}{\gamma}\right)\cdot
tp}{\left(1-\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\left(tp+fp\right)\left(tn+fn\right)}}$,
which can be upper bounded by the following,

$C^{{}^{\prime}}\leq\frac{\left(\frac{1}{\gamma}\right)}{\left(1-\frac{\epsilon}{\gamma}\right)\sqrt{T^{{}^{\prime}}(1-T^{{}^{\prime}})\cdot\gamma}}$

∎

##  Appendix B More Experimental Results

Some more experiments with Adult dataset and MCC loss function are shown in
the Figure 5. In that also, we can notice uniform sampling performs better or
comparable with some computationally complex methods.

(a) Adult Logistic

(b) Adult SVM

(c) Adult MLP

Figure 5: $MCC$ Score on Adult dataset for different classifiers and different
coreset strategies.

The following tables show F1 score and MCC respectively for different coreset
sizes and strategies for some other classifiers also. Here LR represents
Logistic Regression, GB represents Gradient Boosting, and DT represents
Decision Tree classifiers, respectively.

Model Name | F1 Score | MCC Score
---|---|---
Logistic Regression | 0.5088 | 0.4394
Decision Tree | 0.5487 | 0.4862
Gradient Boosting | 0.5360 | 0.4716
Table 2: F1-Score and MCC-Score on Bank Marketing Full Dataset Model | Coreset | 2% | 5% | 8% | 10%
---|---|---|---|---|---
LR | uniform | 0.4331 | 0.4335 | 0.4412 | 0.4400
LR | leverage | 0.3125 | 0.3356 | 0.3366 | 0.3323
LR | lewis | 0.4346 | 0.4260 | 0.4342 | 0.4282
LR | kmeans | 0.4002 | 0.3861 | 0.3922 | 0.3842
DT | uniform | 0.4623 | 0.5171 | 0.5322 | 0.5290
DT | leverage | 0.4482 | 0.4879 | 0.4880 | 0.4898
DT | lewis | 0.4889 | 0.5124 | 0.5217 | 0.5216
DT | kmeans | 0.4429 | 0.4819 | 0.5126 | 0.5184
GB | uniform | 0.5623 | 0.5830 | 0.5932 | 0.5972
GB | leverage | 0.5475 | 0.5769 | 0.5865 | 0.5862
GB | lewis | 0.5654 | 0.5834 | 0.5931 | 0.5946
GB | kmeans | 0.5377 | 0.5700 | 0.5775 | 0.5822
Table 3: F1-Score on Bank Marketing Dataset Model | Coreset | 2% | 5% | 8% | 10%
---|---|---|---|---|---
LR | uniform | 0.3512 | 0.3516 | 0.3609 | 0.3593
LR | leverage | 0.2237 | 0.2536 | 0.2508 | 0.2460
LR | lewis | 0.3531 | 0.3434 | 0.3530 | 0.3463
LR | kmeans | 0.3123 | 0.2978 | 0.3032 | 0.2937
DT | uniform | 0.3926 | 0.4523 | 0.4686 | 0.4638
DT | leverage | 0.3748 | 0.4171 | 0.4191 | 0.4206
DT | lewis | 0.4219 | 0.4475 | 0.4569 | 0.4549
DT | kmeans | 0.3742 | 0.4146 | 0.4480 | 0.4538
GB | uniform | 0.5030 | 0.5293 | 0.5416 | 0.5466
GB | leverage | 0.4847 | 0.5196 | 0.5313 | 0.5315
GB | lewis | 0.5071 | 0.5297 | 0.5413 | 0.5433
GB | kmeans | 0.4734 | 0.5119 | 0.5232 | 0.5273
Table 4: MCC-Score on Bank Marketing Dataset