# Distributionally Robust Safe Sample Screening

Hiroyuki Hanada Noriaki Hashimoto
Center for Advanced Intelligence Project
RIKEN
Chuo, Tokyo, 103-0027 Japan
<EMAIL_ADDRESS>
&Satoshi Akahane Tatsuya Aoyama Tomonari Tanaka Yoshito Okura
Graduate School of Engineering
Nagoya University
Nagoya, Aichi, 464-8603 Japan
{akahane.satoshi,aoyama.tatsuya,tanaka.tomonari,okura.yoshito}
<EMAIL_ADDRESS>
&Yu Inatsu
Department of Computer Science
Nagoya Institute of Technology
Nagoya, Aichi, 466-8555 Japan
<EMAIL_ADDRESS>
&Taro Murayama Lee Hanju Shinya Kojima
DENSO CORPORATION
Kariya, Aichi, 448-8661 Japan
<EMAIL_ADDRESS>
&Shion Takeno Ichiro Takeuchi11footnotemark: 1
Graduate School of Engineering
Nagoya University
Nagoya, Aichi, 464-8603 Japan
{takeno.shion.m6<EMAIL_ADDRESS>Co-corresponding
authorsAlso with Center for Advanced Intelligence Project, RIKEN

###### Abstract

In this study, we propose a machine learning method called _Distributionally
Robust Safe Sample Screening (DRSSS)_. DRSSS aims to identify unnecessary
training samples, even when the distribution of the training samples changes
in the future. To achieve this, we effectively combine the _distributionally
robust_ (DR) paradigm, which aims to enhance model robustness against
variations in data distribution, with the _safe sample screening_ (SSS), which
identifies unnecessary training samples prior to model training. Since we need
to consider an infinite number of scenarios regarding changes in the
distribution, we applied SSS because it does not require model training after
the change of the distribution. In this paper, we employed the _covariate
shift_ framework to represent the distribution of training samples and
reformulated the DR covariate-shift problem as a weighted empirical risk
minimization problem, where the weights are subject to uncertainty within a
predetermined range. By extending the existing SSS technique to accommodate
this weight uncertainty, the DRSSS method is capable of reliably identifying
unnecessary samples under any future distribution within a specified range. We
provide a theoretical guarantee for the DRSSS method and validate its
performance through numerical experiments on both synthetic and real-world
datasets.

##  1 Introduction

In practical applications of machine learning, there are cases where the data
distribution differs between the training and deployment phases. If the data
distribution at deployment is unknown, it becomes necessary to robustly handle
a certain range of distributional changes, which is referred to as
_distributionally robust (DR) learning_ (see, e.g., [1]). In standard DR
learning settings, the focus is on how robustly a model fixed at the training
phase behaves when the data distribution changes at deployment. However, in
practice, there are cases where fine-tuning or retraining of the model is
possible at deployment. In such settings, it is preferable to minimize the
data storage costs and the retraining costs at deployment. This issue becomes
more critical in scenarios such as continual learning (see, e.g., [2]), where
the model needs to be continually updated in response to environmental
changes. In this study, we propose a method called _distributionally robust
safe sample screening (DRSSS)_ method that allows for removing a set of
training samples in advance while ensuring the optimality of the retrained
model in the deployment phase where the data distribution changes within a
certain range.

The basic idea of the proposed DRSSS method is to extend an optimization
technique called _safe sample screening (SSS)_ to the DR learning setting. SSS
is an approach that allows the removal of some training instances in advance
for learning sparse models such as support vector machines (SVM) [3]. This
approach is termed _safe_ because it guarantees that the solution to the
optimization problem, even after removing those training samples, will be
exactly the same as the solution obtained with all training samples. Various
SSS methods have been developed for different models, demonstrating that they
can make the learning process of sparse models more efficient. However, our
goal in this study is not merely to improve efficiency, but to safely identify
unnecessary samples that are robust to distributional changes. We develop a
method that ensures optimality after data reduction, regardless of how the
data distribution varies within a certain range, by extending the SSS
technology to the DR learning setting. While traditional SSS only needs to
guarantee the optimality for a single optimal solution, DRSSS is challenging
because it requires guaranteeing optimality for an entire class (i.e., an
infinite number of optimization problems) across a certain range of
distribution changes.

In this study, we consider the _covariate shift_ setting as the distributional
change at deployment phases. Covariate shift is a scenario where the
distribution of input data changes between the training phase and the test
(deployment) phase [4, 5]. If the input data distribution during the
deployment phase is known, the problem of covariate shift can be addressed as
a weighted optimization problem by assigning weights to each training sample
(formal definition we employed is presented in Section 2.1). The weight of
each sample can be determined according to the ratio of the density in the
test (deployment) distribution to that in the training distribution. In the DR
learning setting of this study, we assume that the test input distribution is
unknown but exists within a certain range from the training input
distribution. This means that the problem of DR covariate shift can be
formulated as an optimization problem with DR weighting, where the weights of
each sample vary within a certain range. Our proposed DRSSS method enables SSS
for this DR weighting optimization problem (Section 3). Figure 1 illustrates
the proposed DRSSS method.

Figure 1:  Schematic illustration of the proposed DRSSS method in a toy binary
classification problem with a sample-sparse classifier such as SVM. (A)
Suppose that we have a dataset of binary classification (classes described by
colors), and we compute the proposed DRSSS in the initial training phase.
Then, it can identify a set of samples that do not influence the optimal
solutions in the deployment phase, regardless of any changes within a
specified range in the input distribution (points with thin colors). (B) This
means that, for any input distribution of the deployment phase within a
specified range (depicted by the differing sizes of points), the set of
samples screened out by the DRSSS method is always identified as no influence
(screened samples in a specific deployment is always a superset of that in
DRSSS).

#### Related works

The DR setting has been explored in various machine learning problems, aiming
to enhance model robustness against data distribution variations. A DR
learning problem is typically formulated as a worst-case optimization problem
since the goal is to ensure model performance under the worst-case data
distribution within a specified range. Consequently, a variety of optimization
techniques tailored to DR learning have been investigated within both the
machine learning and optimization communities [6, 7, 1]. The proposed DRSSS
method is one such DR learning method, focusing specifically on the problem of
sample reduction. The ability to identify unnecessary samples is of practical
significance. For example, in the context of continual learning (see, e.g.,
[2]), it is crucial to effectively manage data by selectively retaining and
discarding samples, especially in anticipation of changes in future data
distributions. Incorrect deletion of essential data can lead to _catastrophic
forgetting_ [8], a phenomenon where a model, after being trained on new data,
quickly loses information previously learned from older datasets. The proposed
DRSSS method addresses this challenge by identifying samples that, regardless
of future data distribution shifts, will not have any influence on all
possible newly trained models in the future.

Safe screening (SS) refers to optimization techniques in sparse learning that
identify and exclude unnecessary samples or features from the learning
process, thereby reducing computational cost without altering the final
trained model. Initially, safe _feature_ screening was introduced by [9] for
the Lasso, followed by safe _sample_ screening by [3] for the SVM. Among
various SS methods developed so far, the most commonly used is based on the
duality gap [10, 11, 12], which is also used for the proposed DRSSS method.
Over the past decade, SS has seen diverse developments, including
methodological improvements and expanded application scopes [12, 13, 14, 15,
16, 17, 18, 19]. Unlike other SSS studies that primarily focused on reducing
computational costs, this study adopts SSS for a different purpose. We employ
SSS to identify unnecessary samples from an infinitely large number of
learning problems, or more specifically, across infinitely large numbers of
scenarios where data distribution varies within a specified range. To our
knowledge, no existing studies have utilized SS within the DR learning
framework.

#### Contributions

Our contributions are summarized as follows. First, by effectively combining
distributionally robust (DR) learning and safe sample screening (SSS), we
propose a novel method called the DRSSS method that can identify samples that
do not affect the optimal solutions in the deployment phase, regardless of how
the distribution changes within a specified range. Although the DRSSS method
is developed for convex empirical risk minimization problems, we have extended
the proposed method through kernelization to be applicable to complex
nonlinear models. Using the neural tangent kernel, this extension enables the
application of DRSSS to practical deep learning models. Finally, through
numerical experiments, we verify the effectiveness of the proposed DRSSS
method.

The code for the experiment is available as supplementary information.

#### Notations

Notations used in this paper are described in Table 1.

Table 1: Notations used in the paper. $\mathbb{R}$: all real numbers, $\mathbb{N}$: all positive integers, $n,n^{\prime},p\in\mathbb{N}$, $f:\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$: convex function, $M\in\mathbb{R}^{n\times n^{\prime}}$: matrix, $\bm{v}\in\mathbb{R}^{n}$: vector. $m_{ij}\in\mathbb{R}$ (small case of matrix variable) | the element at the $i^{\mathrm{th}}$ row and the $j^{\mathrm{th}}$ column of $M$
---|---
$v_{i}\in\mathbb{R}$ (nonbold font of vector variable) | the $i^{\mathrm{th}}$ element of $\bm{v}$
$M_{i:}\in\mathbb{R}^{1\times n^{\prime}}$ | the $i^{\mathrm{th}}$ row of $M$
$M_{:j}\in\mathbb{R}^{n\times 1}$ | the $j^{\mathrm{th}}$ column of $M$
$[n]$ | $\\{1,2,\dots,n\\}$
$\mathbb{R}_{\geq 0}$ | all nonnegative real numbers
$\otimes$ | elementwise product
_diagonal matrix_ : $\mathrm{diag}(\bm{v})\in\mathbb{R}^{n\times n}$ |  $(\mathrm{diag}(\bm{v}))_{ii}=v_{i}$ and $(\mathrm{diag}(\bm{v}))_{ij}=0$ ($i\neq j$)
$\bm{v}{\raisebox{0.80002pt}{$\times$}\Box}M\in\mathbb{R}^{n\times n^{\prime}}$ | $\mathrm{diag}(\bm{v})M$
$\bm{0}_{n}\in\mathbb{R}^{n}$ |  $[0,0,\dots,0]^{\top}$ (vector of size $n$)
$\bm{1}_{n}\in\mathbb{R}^{n}$ |  $[1,1,\dots,1]^{\top}$ (vector of size $n$)
_$p$ -norm_: $\|\bm{v}\|_{p}\in\mathbb{R}_{\geq 0}$ | $(\sum_{i=1}^{n}v_{i}^{p})^{1/p}$
_subgradient_ : $\partial f(\bm{v})\subseteq\mathbb{R}^{n}$ | $\\{\bm{g}\in\mathbb{R}^{n}\mid\forall\bm{v}^{\prime}\in\mathbb{R}^{n}:~{}f(\bm{v}^{\prime})-f(\bm{v})\geq\bm{g}^{\top}(\bm{v}^{\prime}-\bm{v})\\}$
${\cal Z}[f]\subseteq\mathbb{R}^{n}$ | $\\{\bm{v}^{\prime}\in\mathbb{R}^{n}\mid\partial f(\bm{v}^{\prime})=\\{\bm{0}_{n}\\}\\}$
_convex conjugate_ : $f^{*}(\bm{v})\in\mathbb{R}\cup\\{+\infty\\}$ | $\sup_{\bm{v}^{\prime}\in\mathbb{R}^{n}}(\bm{v}^{\top}\bm{v}^{\prime}-f(\bm{v}^{\prime}))$
“$f$ is $\kappa$-strongly convex” ($\kappa>0$) |  $f(\bm{v})-(\kappa/2)\|\bm{v}\|_{2}^{2}$ is convex with respect to $\bm{v}$
“$f$ is $\mu$-smooth” ($\mu>0$) |  $\|f(\bm{v})-f(\bm{v}^{\prime})\|_{2}\leq\mu\|\bm{v}-\bm{v}^{\prime}\|_{2}$ for any $\bm{v},\bm{v}^{\prime}\in\mathbb{R}^{n}$

##  2 Preliminaries

###  2.1 Weighted regularized empirical risk minimization

We first present the class of machine learning problem that the covariate
shift setting is acceptable and SSS is applicable. As noted in Section 1, a
machine learning model applicable to the covariate shift setting can be
implemented by assigning weights to each training sample. Thus we employ the
class of the machine learning model called the _weighted regularized empirical
risk minimization (weighted RERM)_ , for linear predictions. We note that this
“linear prediction” includes the _kernel method_ , which is discussed in
Section 4.2.

######  Definition 2.1.

Given $n$ training samples of $d$-dimensional input variables, scalar output
variables and scalar sample weights, denoted by $X\in\mathbb{R}^{n\times d}$,
$\bm{y}\in\mathbb{R}^{n}$ and $\bm{w}\in\mathbb{R}_{\geq 0}^{n}$,
respectively, the training computation of weighted RERM for linear prediction
is formulated as follows:

$\displaystyle\bm{\beta}^{*(\bm{w})}:=\mathop{\rm
argmin}\limits_{\bm{\beta}\in\mathbb{R}^{d}}P_{\bm{w}}(\bm{\beta}),\quad\text{where}\quad
P_{\bm{w}}(\bm{\beta}):=\sum_{i=1}^{n}w_{i}\ell_{y_{i}}(\check{X}_{i:}\bm{\beta})+\rho(\bm{\beta}).$
(1)

Here, $\ell_{y}:\mathbb{R}\to\mathbb{R}$ is a convex loss function111For
$\ell_{y}(t)$, we assume that only $t$ is a variable of the function ($y$ is
assumed to be a constant) when we take its subgradient or convex conjugate.,
$\rho:\mathbb{R}^{d}\to\mathbb{R}$ is a convex regularization function, and
$\check{X}\in\mathbb{R}^{n\times d}$ is a matrix calculated from $X$ and
$\bm{y}$ and determined depending on $\ell_{y}$. In this paper, unless
otherwise noted, we consider binary classifications
($\bm{y}\in\\{-1,+1\\}^{n}$) with
$\check{X}:=\bm{y}{\raisebox{0.80002pt}{$\times$}\Box}X$. For regressions
($\bm{y}\in\mathbb{R}^{n}$) we usually set $\check{X}:=X$.

Here, $\bm{\beta}^{*(\bm{w})}$ is the linear prediction coefficients: given a
sample $\hat{\bm{x}}\in\mathbb{R}^{d}$, its prediction is assumed to be done
by $\hat{\bm{x}}^{\top}\bm{\beta}^{*(\bm{w})}$. Since $\ell_{y}$ and $\rho$
are convex, we can easily confirm that $P_{\bm{w}}(\bm{\beta})$ is convex with
respect to $\bm{\beta}$.

######  Remark 2.2.

We add that, we adopt the formulation $X_{:d}=\bm{1}_{n}$ so that
$\beta^{*(\bm{w})}_{d}$ (the last element) represents the common coefficient
for any sample (called the _intercept_).

Applying Fenchel’s duality theorem (Appendix B), we have the following dual
problem of (1):

$\displaystyle\bm{\alpha}^{*(\bm{w})}:=\mathop{\rm
argmax}\limits_{\bm{\alpha}\in\mathbb{R}^{n}}D_{\bm{w}}(\bm{\alpha}),\quad\text{where}\quad
D_{\bm{w}}(\bm{\alpha}):=-\sum_{i=1}^{n}w_{i}\ell^{*}_{y_{i}}(-\alpha_{i})-\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}).$
(2)

The relationship between the original problem (1) (called the _primal_
problem) and the dual problem (2) are described as follows:

$\displaystyle
P_{\bm{w}}(\bm{\beta}^{*(\bm{w})})=D_{\bm{w}}(\bm{\alpha}^{*(\bm{w})}),$ (3)
$\displaystyle\bm{\beta}^{*(\bm{w})}\in\partial\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\bm{w})}),$
(4) $\displaystyle\forall
i\in[n]:\quad-\alpha^{*(\bm{w})}_{i}\in\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\bm{w})}).$
(5)

######  Remark 2.3.

We should notice that, depending on $\bm{\alpha}$, $D_{\bm{w}}(\alpha)$ may be
infinite and therefore we may not use such $\bm{\alpha}$ when computing it.
This is because the convex conjugate $f^{*}$ (Table 1) may be infinite even
$f$ is finite. In this setup, since we do not use $\rho$ such that $\rho^{*}$
may be infinite (discussed in Corollary A.3 in Appendix A), we have to care
about only the condition when $\ell^{*}_{y_{i}}(-\alpha_{i})$ becomes
infinite. In the examples of loss functions in Table 2 we present conditions
for $\ell^{*}_{y_{i}}(-\alpha_{i})<+\infty$.

###  2.2 Sample-sparse loss functions

In weighted RERM, we call that a loss function $\ell_{y}$ induces _sample-
sparsity_ if elements in $\bm{\alpha}^{*(\bm{w})}$ are easy to become zero. As
implied from (4), if $\alpha^{*(\bm{w})}_{i}=0$, the $i^{\mathrm{th}}$ sample
(i.e., the $i^{\mathrm{th}}$ row of $\check{X}$) is unnecessary to represent
the primal model parameter $\bm{\beta}^{*(\bm{w})}$ and therefore we can
remove them. Due to (5), the sample-sparsity can be achieved by $\ell_{y}$
such that ${\cal
Z}[\ell_{y}]:=\\{t\in\mathbb{R}\mid\partial\ell_{y}(t)=\\{0\\}\\}$ is not a
point but an interval.

In case of binary classification problems ($y\in\\{-1,+1\\}$), the _hinge
loss_ $\ell_{y}(t)=\max\\{0,1-t\\}$ is a famous sample-sparse loss function.
In fact, ${\cal Z}[\ell_{y}]=(1,+\infty)$ for the hinge loss. Other examples
are presented in Table 2.

Table 2: Examples of sample-sparse loss functions. Calculation results used later are also presented. $\ell_{y}(t)$ | $y\in$ | $\phantom{\Bigl{[}}\check{X}\phantom{\Bigr{]}}$ | $\ell^{*}_{y}(t)$ |  $\ell^{*}_{y_{i}}(-\alpha_{i})<+\infty$ if | ${\cal Z}[\ell_{y}]$
---|---|---|---|---|---
$\max\\{0,1-t\\}$ | $\\{-1,+1\\}$ | $\bm{y}{\raisebox{0.80002pt}{$\times$}\Box}X$ |  $t$ ($-1\leq t\leq 0$) | $0\leq\alpha_{i}\leq 1$ | $(1,+\infty)$
(_Hinge loss_) |  |  $+\infty$ (otherwise) |  |
$(\max\\{0,1-t\\})^{2}$ | $\\{-1,+1\\}$ | $\bm{y}{\raisebox{0.80002pt}{$\times$}\Box}X$ |  $(t^{2}+4t)/4$ ($t\leq 0$) | $\alpha_{i}\geq 0$ | $[1,+\infty)$
(_Squared hinge loss_) |  |  $+\infty$ (otherwise) |  |
$\max\\{0,|t-y|-\varepsilon\\}$ | $\mathbb{R}$ | $X$ |  $t(y-\varepsilon)$ ($-1\leq t\leq 0$) | $-1\leq\alpha_{i}\leq 1$ | $(-\varepsilon,\varepsilon)$
(_$\varepsilon$ -insensitive loss_; |  |  $t(y+\varepsilon)$ ($0\leq t\leq 1$) |  |
$\varepsilon>0$: hyperparameter) |  |  $+\infty$ (otherwise) |  |
$(\max\\{0,|t-y|-\varepsilon\\})^{2}$ | $\mathbb{R}$ | $X$ | $(t^{2}+4yt)/4+|t|\varepsilon$ | $\alpha_{i}\in\mathbb{R}$ | $[-\varepsilon,\varepsilon]$
(_squared $\varepsilon$-insensitive loss_; |  |  |  |
$\varepsilon>0$: hyperparameter) |  |  |  |

##  3 Distributionally robust safe sample screening

In this section we show the condition of unnecessary samples identified by
DRSSS, which we call the _DRSSS rule_ , for weighted RERM with two steps.
First, in Sections 3.1 we show SSS rules for weighted RERM but not DR setup.
Here, “DR setup” means that the weight is assumed to be changed in a
predetermined range. To do this, we extended existing SSS rules in [11, 12].
Then we derive DRSSS rules in Section 3.2.

###  3.1 (Non-DR) safe sample screening

We consider identifying training samples that do not affect the learned primal
model parameter $\bm{\beta}^{*(\bm{w})}$. As discussed in Section 2.2, such
samples can be identified as $i\in[n]$ such that $\alpha^{*(\bm{w})}_{i}=0$.
However, since computing $\bm{\alpha}^{*(\bm{w})}$ is as costly as
$\bm{\beta}^{*(\bm{w})}$, we would like to judge whether
$\alpha^{*(\bm{w})}_{i}=0$ or not without computing exact
$\bm{\alpha}^{*(\bm{w})}$. To solve the problem, the SSS first considers
identifying the possible range ${\cal B}^{*(\bm{w})}\subset\mathbb{R}^{d}$
such that $\bm{\beta}^{*(\bm{w})}\in{\cal B}^{*(\bm{w})}$ is assured. Then,
with ${\cal B}^{*(\bm{w})}$ and (5), we can conclude that the
$i^{\mathrm{th}}$ training sample do not affect the training result
$\bm{\beta}^{*(\bm{w})}$ if $\bigcup_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta})=\\{0\\}$.

First we show how to compute ${\cal B}^{*(\bm{w})}$. In this paper we adopt
the computation methods that is available when the regularization function
$\rho$ in $P_{\bm{w}}$ (and also $P_{\bm{w}}$ itself) of (1) are strongly
convex.

######  Lemma 3.1.

Suppose that $\rho$ in $P_{\bm{w}}$ (and also $P_{\bm{w}}$ itself) of (1) are
$\kappa$-strongly convex. Then, for any $\hat{\bm{\beta}}\in\mathbb{R}^{d}$
and $\hat{\bm{\alpha}}\in\mathbb{R}^{n}$, we can assure that the following
${\cal B}^{*(\bm{w})}\subset\mathbb{R}^{d}$ must satisfy
$\bm{\beta}^{*(\bm{w})}\in{\cal B}^{*(\bm{w})}$:

$\displaystyle{\cal
B}^{*(\bm{w})}:=\\{\bm{\beta}\in\mathbb{R}^{d}\mid\|\bm{\beta}-\hat{\bm{\beta}}\|_{2}\leq
r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}})\\},$
$\displaystyle\text{where}\quad
r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}}):=\sqrt{(2/\kappa)[P_{\bm{w}}(\hat{\bm{\beta}})-D_{\bm{w}}(\hat{\bm{\alpha}})]}.$

The proof is done by extending [11, 12] to our setup; see Appendix C.1. The
quantity $P_{\bm{w}}(\hat{\bm{\beta}})-D_{\bm{w}}(\hat{\bm{\alpha}})$ is known
as the _duality gap_ , which must be nonnegative due to (3). Then we obtain
the following SSS rule, which is referred to as the _gap safe screening rule_
[11]:

######  Lemma 3.2.

Under the same assumptions as Lemma 3.1, $\alpha_{i}^{*(\bm{w})}=0$ is assured
(i.e., the $i^{\mathrm{th}}$ training sample does not affect the training
result $\bm{\beta}^{*(\bm{w})}$) if there exists
$\hat{\bm{\beta}}\in\mathbb{R}^{d}$ and $\hat{\bm{\alpha}}\in\mathbb{R}^{n}$
such that

$\displaystyle[\check{X}_{i:}\hat{\bm{\beta}}-\|\check{X}_{i:}\|_{2}r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}}),~{}\check{X}_{i:}\hat{\bm{\beta}}+\|\check{X}_{i:}\|_{2}r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}})]\subseteq{\cal
Z}[\ell_{y_{i}}].$

The proof is presented in Appendix C.2.

######  Remark 3.3.

When we employ the intercept in the model (Remark 2.2), we often define that
the regularization function $\rho(\bm{\beta})$ do not regularize $\beta_{d}$
(the model parameter for the intercept), that is, $\rho(\bm{\beta})$ is
constant with respect to $\beta_{d}$. However, to apply Lemmas 3.1 and 3.2, we
need to define that $\rho(\bm{\beta})$ does regularize $\beta_{d}$, because
$\rho$ itself is required to be $\kappa$-strongly convex.

###  3.2 Extension of SSS to DR setup

With the conditions when samples are screened out proved in Section 3.1, we
then define the problem setup of DRSSS.

######  Definition 3.4 (Distributionally robust safe sample screening
(DRSSS)).

Given $X\in\mathbb{R}^{n\times d}$, $\bm{y}\in\mathbb{R}^{n}$ and ${\cal
W}\subset\mathbb{R}_{\geq 0}^{n}$, the _DRSSS for ${\cal W}$ in weighted RERM_
is defined as finding unnecessary samples for any $\bm{w}\in{\cal W}$, or more
specifically, finding $i\in[n]$ that satisfies Lemma 3.2 for any
$\bm{w}\in{\cal W}$.

To do this, if Lemma 3.2 is applicable, we have only to take the following
procedure:

######  Theorem 3.5.

If $\rho$ in $P_{\bm{w}}$ (1) is $\kappa$-strongly convex, DRSSS in Definition
3.4 is achieved as follows:

  1. 1.

Choose $\tilde{\bm{w}}\in{\cal W}$.

  2. 2.

Compute (1)&(5) or (2)&(4) for $\tilde{\bm{w}}$ to learn
$\bm{\beta}^{*(\tilde{\bm{w}})}$ and $\bm{\alpha}^{*(\tilde{\bm{w}})}$.

  3. 3.

Identify $i\in[n]$ that satisfies Lemma 3.2 with
$\hat{\bm{\beta}}\leftarrow\bm{\beta}^{*(\tilde{\bm{w}})}$ and
$\hat{\bm{\alpha}}\leftarrow\bm{\alpha}^{*(\tilde{\bm{w}})}$ and for any
$\bm{w}\in{\cal W}$. Such $i$ assures $\alpha_{i}^{*(\bm{w})}=0$
$\forall\bm{w}\in{\cal W}$.

Here, the last procedure can be computed as follows:

$\displaystyle[\check{X}_{i:}\bm{\beta}^{*(\tilde{\bm{w}})}-\|\check{X}_{i:}\|_{2}R,~{}\check{X}_{i:}\bm{\beta}^{*(\tilde{\bm{w}})}+\|\check{X}_{i:}\|_{2}R]\subseteq{\cal
Z}[\ell_{y_{i}}],$ (6) $\displaystyle\text{where}\quad R:=\max_{\bm{w}\in{\cal
W}}r(\bm{w},\kappa,\bm{\beta}^{*(\tilde{\bm{w}})},\bm{\alpha}^{*(\tilde{\bm{w}})})=\sqrt{(2/\kappa)\max_{\bm{w}\in{\cal
W}}[P_{\bm{w}}(\bm{\beta}^{*(\tilde{\bm{w}})})-D_{\bm{w}}(\bm{\alpha}^{*(\tilde{\bm{w}})})]}.$
(7)

In Theorem 3.5, the key point is the maximization in (7), which is a
maximization of convex function and therefore is difficult in general. In
fact,

$\displaystyle
P_{\bm{w}}(\bm{\beta}^{*(\tilde{\bm{w}})})-D_{\bm{w}}(\bm{\alpha}^{*(\tilde{\bm{w}})})$
$\displaystyle=\underbrace{\sum_{i=1}^{n}w_{i}[\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\tilde{\bm{w}})})+\ell^{*}_{y_{i}}(-\alpha^{*(\tilde{\bm{w}})}_{i})]}_{\text{linear
w.r.t.}~{}\bm{w}}+\rho(\bm{\beta}^{*(\tilde{\bm{w}})})+\underbrace{\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\tilde{\bm{w}})})}_{\text{convex
w.r.t.}~{}\bm{w}},$ (8)

is convex with respect to $\bm{w}$. (Note that $\rho^{*}$ is assured to be
convex.) However, depending on the choice of the regularization function
$\rho$ and the range of weight changes ${\cal W}$, it may be explicitly
computed. So, in Section 4 we show specific calculations for some typical
setups.

##  4 Specific computations of DRSSS for L2-regularization

In this section we discuss specific computations of DRSSS in Theorem 3.5,
which depends on the choice of the loss function $\ell_{y}$, the
regularization function $\rho$, and the distribution changes (i.e., range of
weight changes ${\cal W}$). Especially, we present how to compute the
quantities to conduct DRSSS: computation of (6) and maximization of (8) in the
theorem.

First we can see that the choice of the loss function does not affect the
required computations for DRSSS so much, since the terms including the loss
function $\ell_{y}$ and its convex conjugate $\ell^{*}_{y}$ in (6) and (8) are
calculated only by known quantities $\check{X}$,
$\bm{\beta}^{*(\tilde{\bm{w}})}$ and $\bm{\alpha}^{*(\tilde{\bm{w}})}$. So,
after determining $\ell_{y}$, we have only to apply functions described in
Table 2.

On the other hand, the choice of the regularization function and the range of
weight changes largely affect the difficulty of the computations. So we mainly
discuss the use of L2-regularization and show the algorithm to compute them.
Note that, it is not obvious to extend DRSSS for L2-regularization to other
regularization functions; discussions are presented in Appendix D.1.

###  4.1 DRSSS for L2-regularization and weight changes in L2-norm

As stated in Lemma 3.1, DRSSS requires the regularization function to be
$\kappa$-strongly convex. So the _L2-regularization_
$\rho(\bm{\beta}):=\frac{\lambda}{2}\|\bm{\beta}\|_{2}^{2}$ ($\lambda>0$) can
be applicable for DRSSS. In addition, we assume that the range of weight
changes ${\cal W}$ is defined by L2-norm ${\cal
W}:=\\{\bm{w}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S\\}$ ($S>0$).

With L2-regularization, since
$\rho^{*}(\bm{v})=\frac{1}{2\lambda}\|\bm{v}\|_{2}^{2}$, the duality gap (8)
is calculated as

$\displaystyle\sum_{i=1}^{n}w_{i}[\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\tilde{\bm{w}})})+\ell^{*}_{y_{i}}(-\alpha^{*(\tilde{\bm{w}})}_{i})]+\frac{\lambda}{2}\|\bm{\beta}^{*(\tilde{\bm{w}})}\|_{2}^{2}+\frac{1}{2\lambda}\bm{w}^{\top}(\bm{\alpha}^{*(\tilde{\bm{w}})}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})(\bm{\alpha}^{*(\tilde{\bm{w}})}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{w}.$
(9)

Since
$(\bm{\alpha}^{*(\tilde{\bm{w}})}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})(\bm{\alpha}^{*(\tilde{\bm{w}})}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}$
is positive semidefinite, we can see that (9) is a quadratic convex function
with respect to $\bm{w}$. As a method to solve a constrained maximization of
(9) in ${\cal W}:=\\{\bm{w}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S\\}$, let us
apply the _method of Lagrange multipliers_. Then we can prove that all
stationary points can be algorithmically computed, and therefore the
maximization can be also computed. In fact,

######  Theorem 4.1.

The following maximization can be solved algorithmically:

$\displaystyle\max_{\bm{w}\in{\cal
W}}\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w},$ (10)
$\displaystyle\text{where}\quad{\cal
W}:=\\{\bm{w}\in\mathbb{R}^{n}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S\\},$
$\displaystyle\phantom{\text{where}}\quad\tilde{\bm{w}}\in\mathbb{R}^{n},\quad\bm{b}\in\mathbb{R}^{n},\quad
S>0,$ $\displaystyle\phantom{\text{where}}\quad A\in\mathbb{R}^{n\times
n}:~{}\text{symmetric, positive semidefinite, nonzero}.$

See Appendix D.2 for the proof. Although the maximization requires $O(n^{3})$
time, the result is valuable since conventional SSS methods cannot derive SSS
rules for a range of $\bm{w}$. After maximizing (9) by Theorem 4.1, we can
compute (7) and therefore the DRSSS rule in Theorem 3.5 can be computed.

###  4.2 DRSSS for L2-regularization using kernels

In this section we show the condition to apply both the kernel method and
DRSSS, and show the explicit computations when L2-regularization is employed.

In this paper we omit the detailed definition of the kernel method; however,
within this context, we define it as the scenario where input variables for
any instance (e.g., elements of $X$) or primal model parameters (e.g.,
$\bm{\beta}^{*(\tilde{\bm{w}})}$) cannot be explicitly obtained, yet inner
products between samples (e.g., $X_{i:}X_{i^{\prime}:}^{\top}$) are
accessible. We call that weighted RERM in Section 2.1 can be _kernelized_ if
all necessary quantities can be computed even under the circumstances
described above. For detailed formulation of kernels, see Chapter 2 of [20]
for example. In Appendix D.1 we will discuss the condition of regularization
functions so that weighted RERM can accept both kernelization and SSS
(although it is not obvious to extend to DRSSS).

In this section, as an example, we show DRSSS computation when kernelized with
L2-regularization. To do this, we need to compute (6) and (9) with kernelized
setup. Noticing that the relationship (4) for L2-regularization is calculated
as
$\bm{\beta}^{*(\tilde{\bm{w}})}=\frac{1}{\lambda}(\tilde{\bm{w}}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\tilde{\bm{w}})}=\frac{1}{\lambda}\check{X}^{\top}(\tilde{\bm{w}}\otimes\bm{\alpha}^{*(\tilde{\bm{w}})})$,
we can compute (6) and (9) with kernelized as

$\displaystyle\check{X}_{i:}\bm{\beta}^{*(\tilde{\bm{w}})}\pm\|\check{X}_{i:}\|_{2}R=\frac{1}{\lambda}\dashuline{\check{X}_{i:}\check{X}^{\top}}(\tilde{\bm{w}}\otimes\bm{\alpha}^{*(\tilde{\bm{w}})})\pm\sqrt{\dashuline{\check{X}_{i:}\check{X}_{i:}^{\top}}}R,$
$\displaystyle
P_{\bm{w}}(\bm{\beta}^{*(\tilde{\bm{w}})})-D_{\bm{w}}(\bm{\alpha}^{*(\tilde{\bm{w}})})=\sum_{i=1}^{n}w_{i}\left[\ell_{y_{i}}\left(\frac{1}{\lambda}\dashuline{\check{X}_{i:}\check{X}^{\top}}(\tilde{\bm{w}}\otimes\bm{\alpha}^{*(\bm{w})})\right)+\ell^{*}_{y_{i}}(-\alpha^{*(\tilde{\bm{w}})}_{i})\right]$
$\displaystyle\phantom{P_{\bm{w}}(\bm{\beta}^{*(\tilde{\bm{w}})})-D_{\bm{w}}(\bm{\alpha}^{*(\tilde{\bm{w}})})=}+\frac{1}{2\lambda}(\bm{w}-\tilde{\bm{w}})^{\top}\mathrm{diag}(\bm{\alpha}^{*(\tilde{\bm{w}})})\dashuline{\check{X}\check{X}^{\top}}\mathrm{diag}(\bm{\alpha}^{*(\tilde{\bm{w}})})(\bm{w}-\tilde{\bm{w}}).$

Here, expressions with dashed lines denote that the quantities that can be
computed even when kernelized, that is, without using
$\bm{\beta}^{*(\tilde{\bm{w}})}$ or $X$ except for inner products between
samples $X_{i:}X_{i^{\prime}:}^{\top}$. This concludes that DRSSS rules can be
computed even kernelized with L2-regularization.

##  5 Numerical experiment

###  5.1 Experimental settings

We evaluate the performances of DRSSS across different values of acceptable
weight changes $S$ and hyperparameters for regularization strength $\lambda$.
Performance is measured by _safe screening rate_ , representing the ratio of
the number of screened samples to that of all samples. We examined DRSSS
performances with SVM (Hinge loss + L2-regularization) under three setups:

  * •

Tabular data, linear prediction (no kernel)

  * •

Tabular data, _radial basis function (RBF) kernel_ [20]

  * •

Image data, _neural tangent kernel (NTK)_ (see Section 1)

In these experiments, we set the initial sample weights ($\tilde{\bm{w}}$ in
Theorem 3.5) as $\tilde{\bm{w}}=\bm{1}_{n}$, and learn
$\bm{\alpha}^{*(\tilde{\bm{w}})}$ by solving (2)222 Since the experiments do
not employ validation or test dataset, we use all samples in the dataset for
training. . If no kernel is employed, we compute
$\bm{\beta}^{*(\tilde{\bm{w}})}$ from $\bm{\alpha}^{*(\tilde{\bm{w}})}$ by
(4). Then, we set the range of weights as ${\cal
W}:=\\{\bm{w}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S\\}$ (Section 4), where
$S$ is specified as follows: First we assume the weight change that the
weights for positive samples ($\\{i\mid y_{i}=+1\\}$) from $1$ to $a$, while
retaining the weights for negative samples ($\\{i\mid y_{i}=-1\\}$) as $1$.
Then, we defined $S$ as the size of weight change above; specifically, we set
$S=\sqrt{n^{+}}|a-1|$ ($n^{+}$: number of positive samples in the training
dataset). We vary $a$ within the range $0.95\leq a\leq 1.05$, assuming a
maximum change of up to 5% per sample weight. Finally we apply DRSSS in
Section 4.

Also, we demonstrate the difficulty of conventional SSS to achieve DRSSS in
Section 5.2. Since conventional SSS can handle only specific weight change, we
consider “simulating” the maximization computation $\max_{\bm{w}\in{\cal W}}$
in (7) (Theorem 3.5) by repeatedly choosing $\bm{w}$ from
$\|\bm{w}-\tilde{\bm{w}}\|_{2}=S$ at random and regarding the largest one
among chosen $\bm{w}$ as $R$. As a result, $R$ is underestimated and therefore
samples that should not be screened out may be incorrectly screened out.

###  5.2 Safe screening rates for tabular data

Datasets for DRSSS experiments. All are binary classification datasets from LIBSVM dataset [21]. Name $n$ $n^{+}$ $d$ australian 690 307 15 breast-cancer 683 239 11 heart 270 120 14 ionosphere 351 225 35 sonar 208 97 61 splice (train) 1000 517 61 svmguide1 (train) 3089 2000 5 |  (Model: Linear) (Model: RBF kernel) Figure 2: Ratio of screened samples by DRSSS for dataset “breast-cancer”.
---|---

First, we present safe screening rates for two SVM setups: linear prediction
(no kernel) and the RBF kernel [20]. The RBF kernel is a famous kernel
function for finite-dimensional vectors to achieve nonlinear predictions.
Given the original dataset $Z\in\mathbb{R}^{n\times d^{\prime}}$ with $n$
samples and $d^{\prime}$ features, the RBF kernel can be computed as
$X_{i:}X_{i^{\prime}:}^{\top}=\exp(-\|Z_{i:}-Z_{i^{\prime}:}\|_{2}/\zeta)$,
where $\zeta>0$ is a hyperparameter. The datasets used in these experiments
are detailed in Table 2. In this experiment, we adapt the regularization
hyperparameter $\lambda$ based on the characteristics of the data. These
details are described in Appendix E.1.

As an example, for the “breast-cancer” dataset, we show the DRSSS result in
Figure 2 for setups of no kernel and RBF kernel. Results for other datasets
are presented in Appendix E.3.

These plots allow us to assess the tolerance for changes in sample weights.
Since $a=1$ means no weight change, the screening rates fall as $a$ becomes
apart from 1. We can also see that the screening rates tend to be large for
small $\lambda$ if $a$ is near to 1, while the falls of screening rates is
slower for large $\lambda$. The former means that smaller $\lambda$ tends to
have more unnecessary samples ($\alpha^{*(\tilde{\bm{w}})}_{i}=0$) if we do
not consider the change of weights. On the other hand, the behavior of the
latter is accounted for by Lemma 3.1 since larger $\lambda$ reduces
$r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}})$. For instance, with
$a=0.98$ (weight of each positive sample is reduced by two percent, or
equivalent weight change in L2-norm), the sample screening rates are 0.82
(linear) and 0.27 (RBF kernel) for SVM with $\lambda=\mathrm{68.3}$. This
implies that, even if the weights are changed in such range, a number of
samples are still identified as redundant in the sense of prediction.

Then we show the result of simulated DRSSS by repeatedly applying conventional
SSS. In Figure 4 we presented the number of unscreened samples for the dataset
“breast-cancer”, $\lambda=6.83$ and $a=1.02$. By the proposed DRSSS, we
identified that 198 samples are needed to be kept. However, by the simulation,
even if we choose $\bm{w}$ for 1,024 times at random, only 71 samples are
identified to be needed on average (the right end of the blue line), which
demonstrates the difficulty of conventional SSS to apply to our DRSSS setup.
Experimental details and results for other datasets are presented in Appendix
E.2.

###  5.3 Safe screening rates with neural tangent kernel

Figure 3: Number of unscreened samples by DRSSS and by the simulation of repeating conventional SSS, for the dataset “breast-cancer”, linear prediction, $\lambda=6.83$ and $a=1.02$. Error bars are presented but very short; see Appendix E.2 for details. |  Figure 4: Ratio of screened samples by DRSSS for dataset “CIFAR-10” using neural tangent kernel (NTK).
---|---

As noted in the beginning of the section, we experimented DRSSS with NTK by
approximating the a neural network for images. First, we composed 5,000-sample
binary classification dataset from “CIFAR-10” dataset [22], by choosing from
classes “airplane” (2,529) and ‘’automobile” (2,471). Then, as a neural
network for images, we set up a convolutional network of input width 1,024
(same as the number of pixels in an image), three layers of $3\times 3$
convolution filters, followed by a linear fully connected layer. With these
setups, we trained NTK and obtained the kernel values for all pairs of samples
by a Python library “Neural Tangents” [23]. Finally, similar to tabular
datasets, we trained a weighted RERM with the hinge loss and the
L2-regularization and applied DRSSS.

The result is presented in Figure 4. We can confirm a similar tendency to the
ones discussed in Section 5.2, which demonstrates the validity of the proposed
method.

##  6 Conclusions, limitations and future works

In this study, we propose the DRSSS method as a robust data reduction method
for situations where the data distribution at deployment is unknown. This
method effectively reduces data storage and model update costs in DR learning
settings. Our technical contribution extends the SSS technique, originally
developed for accelerating a single optimization problem, to be applicable
across an entire class of optimization problems within a specific category.
The current limitation of the proposed method is that the applicability of
DRSSS, similar to SSS, is confined to convex optimization problems of a
specific class. Therefore, applying it to complex models such as deep learning
requires using kernel methods based on NTK, meaning it cannot be directly
applied to deep learning models. Additionally, there may be cases where the
removable data volume by DRSSS is insufficient, since DRSSS identifies
unnecessary samples under a stringent condition that exactly the same model
parameter should be obtained even when they are removed. It is, therefore,
crucial to develop a framework that relaxes these requirements and allows for
the removal of more data.

## Acknowledgments and Disclosure of Funding

This work was partially supported by MEXT KAKENHI (20H00601, 24K15080), JST
CREST (JPMJCR21D3 including AIP challenge program, JPMJCR22N2), JST Moonshot
R&D (JPMJMS2033-05), JST AIP Acceleration Research (JPMJCR21U2), NEDO
(JPNP18002, JPNP20006) and RIKEN Center for Advanced Intelligence Project.

## References

  * [1] Ruidi Chen and Ioannis Ch. Paschalidis.  Distributionally robust learning.  arXiv Preprint, 2021.
  * [2] Liyuan Wang, Xingxing Zhang, Kuo Yang, Longhui Yu, Chongxuan Li, Lanqing HONG, Shifeng Zhang, Zhenguo Li, Yi Zhong, and Jun Zhu.  Memory replay with data compression for continual learning.  In International Conference on Learning Representations, 2022.
  * [3] Kohei Ogawa, Yoshiki Suzuki, and Ichiro Takeuchi.  Safe screening of non-support vectors in pathwise svm computation.  In Proceedings of the 30th International Conference on Machine Learning, pages 1382–1390, 2013.
  * [4] Hidetoshi Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  Journal of statistical planning and inference, 90(2):227–244, 2000\.
  * [5] Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert Müller.  Covariate shift adaptation by importance weighted cross validation.  Journal of Machine Learning Research, 8(35):985–1005, 2007.
  * [6] Joel Goh and Melvyn Sim.  Distributionally robust optimization and its tractable approximations.  Operations Research, 58(4-1):902–917, 2010.
  * [7] Erick Delage and Yinyu Ye.  Distributionally robust optimization under moment uncertainty with application to data-driven problems.  Operations Research, 58(3):595–612, 2010.
  * [8] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell.  Overcoming catastrophic forgetting in neural networks.  Proceedings of the National Academy of Sciences, 114(13):3521–3526, 2017.
  * [9] Laurent El Ghaoui, Vivian Viallon, and Tarek Rabbani.  Safe feature elimination for the lasso and sparse supervised learning problems.  Pacific Journal of Optimization, 8(4):667–698, 2012.
  * [10] Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon.  Mind the duality gap: safer rules for the lasso.  In Proceedings of the 32nd International Conference on Machine Learning, pages 333–342, 2015.
  * [11] Eugene Ndiaye, Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon.  Gap safe screening rules for sparse multi-task and multi-class models.  In Advances in Neural Information Processing Systems, pages 811–819, 2015.
  * [12] Atsushi Shibagaki, Masayuki Karasuyama, Kohei Hatano, and Ichiro Takeuchi.  Simultaneous safe screening of features and samples in doubly sparse modeling.  In International Conference on Machine Learning, pages 1577–1586, 2016.
  * [13] Shota Okumura, Yoshiki Suzuki, and Ichiro Takeuchi.  Quick sensitivity analysis for incremental data modification and its application to leave-one-out cv in linear classification problems.  In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 885–894, 2015.
  * [14] Kazuya Nakagawa, Shinya Suzumura, Masayuki Karasuyama, Koji Tsuda, and Ichiro Takeuchi.  Safe pattern pruning: An efficient approach for predictive pattern mining.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1785–1794. ACM, 2016.
  * [15] Shaogang Ren, Shuai Huang, Jieping Ye, and Xiaoning Qian.  Safe feature screening for generalized lasso.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(12):2992–3006, 2018.
  * [16] Jiang Zhao, Yitian Xu, and Hamido Fujita.  An improved non-parallel universum support vector machine and its safe sample screening rule.  Knowledge-Based Systems, 170:79–88, 2019.
  * [17] Zhou Zhai, Bin Gu, Xiang Li, and Heng Huang.  Safe sample screening for robust support vector machine.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6981–6988, 2020.
  * [18] Hongmei Wang and Yitian Xu.  A safe double screening strategy for elastic net support vector machine.  Information Sciences, 582:382–397, 2022.
  * [19] Takumi Yoshida, Hiroyuki Hanada, Kazuya Nakagawa, Kouichi Taji, Koji Tsuda, and Ichiro Takeuchi.  Efficient model selection for predictive pattern mining model by safe pattern pruning.  Patterns, 4(12):100890, 2023.
  * [20] Bernhard Schölkopf, Koji Tsuda, and Jean-Philippe Vert, editors.  Kernel Methods in Computational Biology.  The MIT Press, 2004.
  * [21] Chih-Chung Chang and Chih-Jen Lin.  Libsvm: A library for support vector machines.  ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011.  Datasets are provided in authors’ website: https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.
  * [22] Alex Krizhevsky.  The cifar-10 dataset, 2009.
  * [23] Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz.  Neural tangents: Fast and easy infinite neural networks in python.  In International Conference on Learning Representations, 2020.
  * [24] Ralph Tyrell Rockafellar.  Convex analysis.  Princeton university press, 1970.
  * [25] Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal.  Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods.  Springer, 1993.
  * [26] Hui Zou and Trevor Hastie.  Regularization and variable selection via the elastic net.  Journal of the Royal Statistical Society, Series B, 67:301–320, 2005.
  * [27] Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola.  A generalized representer theorem.  In International conference on computational learning theory, pages 416–426. Springer, 2001.
  * [28] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.

##  Appendix A Proofs of general lemmas

In this appendix we show several lemmas used in other appendices.

######  Lemma A.1.

_(Fenchel-Moreau theorem)_ For a convex function
$f:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$, $f^{**}$ is equivalent to
$f$ if $f$ is convex, proper (i.e.,
$\exists\bm{v}\in\mathbb{R}^{d}:~{}f(\bm{v})<+\infty$) and lower-
semicontinuous.

###### Proof.

See Section 12 of [24] for example. ∎

As a special case of Lemma A.1, it holds if $f$ is finite
($\forall\bm{v}\in\mathbb{R}^{d}:~{}f(\bm{v})<+\infty$) and convex.

######  Lemma A.2.

For a convex function $f:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$,

  * •

$f^{*}$ is $(1/\nu)$-strongly convex if $f$ is proper and $\nu$-smooth.

  * •

$f^{*}$ is $(1/\kappa)$-smooth if $f$ is proper, lower-semicontinuous and
$\kappa$-strongly convex.

###### Proof.

See Section X.4.2 of [25] for example. ∎

######  Corollary A.3.

Suppose that the regularization function $\rho$ in (1) is $\kappa$-strongly
convex, which is required to apply SSS (Lemma 3.1). Then, from Lemma A.2,
$\rho^{*}$ must be $(1/\kappa)$-smooth. This implies that, in this case,
$\rho^{*}$ cannot be infinite.

######  Lemma A.4.

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}\cup\\{+\infty\\}$ is a
$\kappa$-strongly convex function, and let $\bm{v}^{*}={\rm
argmin}_{\bm{v}\in\mathbb{R}^{d}}f(\bm{v})$ be the minimizer of $f$. Then, for
any $\bm{v}\in\mathbb{R}^{d}$, we have

$\displaystyle\|\bm{v}-\bm{v}^{*}\|_{2}\leq\sqrt{\frac{2}{\kappa}[f(\bm{v})-f(\bm{v}^{*})]}.$

###### Proof.

See [11] for example. ∎

######  Lemma A.5.

For any vector $\bm{a},\bm{c}\in\mathbb{R}^{n}$ and $S>0$,

$\displaystyle\min_{\bm{v}\in\mathbb{R}^{n}:~{}\|\bm{v}-\bm{c}\|_{2}\leq
S}\bm{a}^{\top}\bm{v}=\bm{a}^{\top}\bm{c}-S\|\bm{a}\|_{2},$
$\displaystyle\max_{\bm{v}\in\mathbb{R}^{n}:~{}\|\bm{v}-\bm{c}\|_{2}\leq
S}\bm{a}^{\top}\bm{v}=\bm{a}^{\top}\bm{c}+S\|\bm{a}\|_{2}.$

###### Proof.

By Cauchy-Schwarz inequality,

$\displaystyle-\|\bm{a}\|_{2}\|\bm{v}-\bm{c}\|_{2}\leq\bm{a}^{\top}(\bm{v}-\bm{c})\leq\|\bm{a}\|_{2}\|\bm{v}-\bm{c}\|_{2}.$

Noticing that the first inequality becomes equality if
$\exists\omega>0:~{}\bm{a}=-\omega(\bm{v}-\bm{c})$, while the second
inequality becomes equality if
$\exists\omega^{\prime}>0:~{}\bm{a}=\omega^{\prime}(\bm{v}-\bm{c})$. Moreover,
since $\|\bm{v}-\bm{c}\|_{2}\leq S$,

$\displaystyle-S\|\bm{a}\|_{2}\leq\bm{a}^{\top}(\bm{v}-\bm{c})\leq
S\|\bm{a}\|_{2}$

also holds, with the equality holds if $\|\bm{v}-\bm{c}\|_{2}=S$.

On the other hand, if we take $\bm{v}$ that satisfies both of the equality
conditions of Cauchy-Schwarz inequality above, that is,

  * •

(for the first inequality being equality)
$\bm{v}=\bm{c}-(S/\|\bm{a}\|_{2})\bm{a}$,

  * •

(for the second inequality being equality)
$\bm{v}=\bm{c}+(S/\|\bm{a}\|_{2})\bm{a}$,

then the inequalities become equalities. This proves that $-S\|\bm{a}\|_{2}$
and $S\|\bm{a}\|_{2}$ are surely the minimum and maximum of
$\bm{a}^{\top}(\bm{v}-\bm{c})$, respectively. ∎

##  Appendix B Proofs of Section 2

As the formulation of Fenchel’s duality theorem, we follow the one in Section
31 of [24].

######  Lemma B.1 (A special case of Fenchel’s duality theorem:
$f,g<+\infty$).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ and $g:\mathbb{R}^{d}\to\mathbb{R}$ be
convex functions, and $A\in\mathbb{R}^{n\times d}$ be a matrix. Moreover, we
define

$\displaystyle\bm{v}^{*}:=\min_{\bm{v}\in\mathbb{R}^{d}}[f(A\bm{v})+g(\bm{v})],$
(11)
$\displaystyle\bm{u}^{*}:=\max_{\bm{u}\in\mathbb{R}^{n}}[-f^{*}(-\bm{u})-g^{*}(A^{\top}\bm{u})].$
(12)

Then Fenchel’s duality theorem assures that

$\displaystyle
f(A\bm{v}^{*})+g(\bm{v}^{*})=-f^{*}(-\bm{u}^{*})-g^{*}(A^{\top}\bm{u}^{*}),$
$\displaystyle-\bm{u}^{*}\in\partial f(A\bm{v}^{*}),$
$\displaystyle\bm{v}^{*}\in\partial g^{*}(A^{\top}\bm{u}^{*}).$

###### Proof.

Introducing a dummy variable $\bm{\psi}\in\mathbb{R}^{n}$ and a Lagrange
multiplier $\bm{u}\in\mathbb{R}^{n}$, we have

$\displaystyle\min_{\bm{v}\in\mathbb{R}^{d}}[f(A\bm{v})+g(\bm{v})]=\max_{\bm{u}\in\mathbb{R}^{n}}\min_{\bm{v}\in\mathbb{R}^{d},~{}\bm{\psi}\in\mathbb{R}^{n}}[f(\bm{\psi})+g(\bm{v})-\bm{u}^{\top}(A\bm{v}-\bm{\psi})]$
(13)
$\displaystyle=-\min_{\bm{u}\in\mathbb{R}^{n}}\max_{\bm{v}\in\mathbb{R}^{d},~{}\bm{\psi}\in\mathbb{R}^{n}}[-f(\bm{\psi})-g(\bm{v})+\bm{u}^{\top}(A\bm{v}-\bm{\psi})]$
$\displaystyle=-\min_{\bm{u}\in\mathbb{R}^{n}}\max_{\bm{v}\in\mathbb{R}^{d},~{}\bm{\psi}\in\mathbb{R}^{n}}[\\{(-\bm{u})^{\top}\bm{\psi}-f(\bm{\psi})\\}+\\{(A^{\top}\bm{u})^{\top}\bm{v}-g(\bm{v})\\}]$
$\displaystyle=-\min_{\bm{u}\in\mathbb{R}^{n}}[f^{*}(-\bm{u})+g^{*}(A^{\top}\bm{u})]=\max_{\bm{u}\in\mathbb{R}^{n}}[-f^{*}(-\bm{u})-g^{*}(A^{\top}\bm{u})].$
(14)

Moreover, by the optimality condition of a problem with a Lagrange multiplier
(13), the optima of it, denoted by $\bm{v}^{*}$, $\bm{\psi}^{*}$ and
$\bm{u}^{*}$, must satisfy

$\displaystyle A\bm{v}^{*}=\bm{\psi}^{*},\quad A^{\top}\bm{u}^{*}\in\partial
g(\bm{v}^{*}),\quad-\bm{u}^{*}\in\partial f(\bm{\psi}^{*})=\partial
f(A\bm{v}^{*}).$

On the other hand, introducing a dummy variable $\bm{\phi}\in\mathbb{R}^{d}$
and a Lagrange multiplier $\bm{v}\in\mathbb{R}^{d}$ for (14), we have

$\displaystyle\max_{\bm{u}\in\mathbb{R}^{n}}[-f^{*}(-\bm{u})-g^{*}(A^{\top}\bm{u})]=\min_{\bm{v}\in\mathbb{R}^{d}}\max_{\bm{u}\in\mathbb{R}^{n},\bm{\phi}\in\mathbb{R}^{d}}[-f^{*}(-\bm{u})-g^{*}(\bm{\phi})-\bm{v}^{\top}(A^{\top}\bm{u}-\bm{\phi})]$
(15)
$\displaystyle=\min_{\bm{v}\in\mathbb{R}^{d}}\max_{\bm{u}\in\mathbb{R}^{n},\bm{\phi}\in\mathbb{R}^{d}}[\\{(A\bm{v})^{\top}(-\bm{u})-f^{*}(-\bm{u})\\}+\\{\bm{v}^{\top}\bm{\phi}-g^{*}(\bm{\phi})\\}]$
$\displaystyle=\min_{\bm{v}\in\mathbb{R}^{d}}[f^{**}(A\bm{v})+g^{**}(\bm{v})]=\min_{\bm{v}\in\mathbb{R}^{d}}[f(A\bm{v})+g(\bm{v})].\quad(\because~{}\text{Lemma
\ref{lem:fenchel-moreau}})$

Likely above, by the optimality condition of a problem with a Lagrange
multiplier (15), the optima of it, denoted by $\bm{u}^{*}$, $\bm{\phi}^{*}$
and $\bm{v}^{*}$, must satisfy

$\displaystyle A^{\top}\bm{u}^{*}=\bm{\phi}^{*},\quad\bm{v}^{*}\in\partial
g^{*}(\bm{\phi}^{*})=\partial g^{*}(A^{\top}\bm{u}^{*}),\quad
A\bm{v}^{*}\in\partial f(-\bm{u}^{*}).$

∎

######  Lemma B.2 (Dual problem of weighted regularized empirical risk
minimization (weighted RERM)).

For the minimization problem

$\displaystyle\bm{\beta}^{*(\bm{w})}:=\mathop{\rm
argmin}\limits_{\bm{\beta}\in\mathbb{R}^{d}}P_{\bm{w}}(\bm{\beta}),\quad\text{where}\quad
P_{\bm{w}}(\bm{\beta}):=\sum_{i=1}^{n}w_{i}\ell_{y_{i}}(\check{X}_{i:}\bm{\beta})+\rho(\bm{\beta}),$
((1) restated)

we define the dual problem as the one obtained by applying Fenchel’s duality
theorem (Lemma B.1), which is defined as

$\displaystyle\bm{\alpha}^{*(\bm{w})}:=\mathop{\rm
argmax}\limits_{\bm{\alpha}\in\mathbb{R}^{n}}D_{\bm{w}}(\bm{\alpha}),\quad\text{where}\quad
D_{\bm{w}}(\bm{\alpha}):=-\sum_{i=1}^{n}w_{i}\ell^{*}_{y_{i}}(-\alpha_{i})+\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}).$
((2) restated)

Moreover, $\bm{\beta}^{*(\bm{w})}$ and $\bm{\alpha}^{*(\bm{w})}$ must satisfy

$\displaystyle
P_{\bm{w}}(\bm{\beta}^{*(\bm{w})})=D_{\bm{w}}(\bm{\alpha}^{*(\bm{w})}),$ ((3)
restated)
$\displaystyle\bm{\beta}^{*(\bm{w})}\in\partial\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\bm{w})}),$
((4) restated) $\displaystyle\forall
i\in[n]:\quad-\alpha^{*(\bm{w})}_{i}\in\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\bm{w})}).$
((5) restated)

###### Proof.

To apply Fenchel’s duality theorem, we have only to set $f$, $g$ and $A$ in
Lemma B.1 as

$\displaystyle f(\bm{u}):=\sum_{i=1}^{n}w_{i}\ell_{y_{i}}(u_{i}),\quad
g(\bm{\beta}):=\rho(\bm{\beta}),\quad A:=\check{X}.$

Here, noticing that

$\displaystyle
f^{*}(\bm{u})=\sup_{\bm{u}^{\prime}\in\mathbb{R}^{n}}[\bm{u}^{\top}\bm{u}^{\prime}-\sum_{i=1}^{n}w_{i}\ell_{y_{i}}(u^{\prime}_{i})]=\sup_{\bm{u}^{\prime}\in\mathbb{R}^{n}}\sum_{i=1}^{n}\left[u_{i}u^{\prime}_{i}-w_{i}\ell_{y_{i}}(u^{\prime}_{i})\right]$
$\displaystyle=\sup_{\bm{u}^{\prime}\in\mathbb{R}^{n}}\sum_{i=1}^{n}w_{i}\left[\frac{u_{i}}{w_{i}}u^{\prime}_{i}-\ell_{y_{i}}(u^{\prime}_{i})\right]=\sum_{i=1}^{n}w_{i}\ell_{y_{i}}^{*}\left(\frac{u_{i}}{w_{i}}\right),$

from (12) we have

$\displaystyle-f^{*}(-\bm{u})-g^{*}(A^{\top}\bm{u})=-\sum_{i=1}^{n}w_{i}\ell_{y_{i}}^{*}\left(-\frac{u_{i}}{w_{i}}\right)-\rho^{*}(\check{X}^{\top}\bm{u}).$

Replacing $u_{i}\leftarrow w_{i}\alpha_{i}$, that is,
$\bm{u}\leftarrow(\bm{w}\otimes\bm{\alpha})$, we have the dual problem (2).

The relationships between the primal and the dual problem are described as
follows:

$\displaystyle-\bm{u}^{*}\in\partial
f(A\bm{v}^{*})~{}\Rightarrow~{}-\bm{w}\otimes\bm{\alpha}^{*(\bm{w})}\in\partial
f(\check{X}\bm{\beta}^{*(\bm{w})})~{}\Rightarrow~{}-w_{i}\alpha^{*(\bm{w})}_{i}\in
w_{i}\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\bm{w})})$
$\displaystyle\Rightarrow-\alpha^{*(\bm{w})}_{i}\in\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\bm{w})}),$
$\displaystyle\bm{v}^{*}\in\partial
g^{*}(A^{\top}\bm{u}^{*})~{}\Rightarrow~{}\bm{\beta}^{*(\bm{w})}\in\partial
g^{*}(\check{X}^{\top}\bm{w}\otimes\bm{\alpha}^{*(\bm{w})})=\partial
g^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\bm{w})}).$

∎

##  Appendix C Proofs of Section 3

###  C.1 Proof of Lemma 3.1

###### Proof.

[11]

$\displaystyle\|\hat{\bm{\beta}}-\bm{\beta}^{*(\bm{w})}\|_{2}$
$\displaystyle\leq\sqrt{\frac{2}{\lambda}[P_{\bm{w}}(\hat{\bm{\beta}})-P_{\bm{w}}(\bm{\beta}^{*(\bm{w})})]}$
($\because$ setting $f\leftarrow P_{\bm{w}}$ in Lemma A.4)
$\displaystyle=\sqrt{\frac{2}{\lambda}[P_{\bm{w}}(\hat{\bm{\beta}})-D_{\bm{w}}(\bm{\alpha}^{*(\bm{w})})]}$
($\because$ (3))
$\displaystyle\leq\sqrt{\frac{2}{\lambda}[P_{\bm{w}}(\hat{\bm{\beta}})-D_{\bm{w}}(\hat{\bm{\alpha}})]}.$
($\because$ $\bm{\alpha}^{*(\bm{w})}$ is a maximizer of $D_{\bm{w}}$)

∎

###  C.2 Proof of Lemma 3.2

###### Proof.

Due to (5), if
$\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta}^{*(\bm{w})})=\\{0\\}$ is
assured, then $\alpha_{i}^{*(\bm{w})}=0$ is assured. Since we do not know
$\bm{\beta}^{*(\bm{w})}$ but know ${\cal B}^{*(\bm{w})}$ (Lemma 3.1), we can
assure $\alpha_{i}^{*(\bm{w})}=0$ if $\bigcup_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta})=\\{0\\}$ is
assured. Noticing that $\partial\ell_{y_{i}}$ is monotonically
increasing333Since $\partial\ell_{y_{i}}$ is a multi-valued function, the
monotonicity must be defined accordingly: we call a multi-valued function
$F:\mathbb{R}\to 2^{\mathbb{R}}$ is monotonically increasing if, for any
$t<t^{\prime}$, $F$ must satisfy “$\forall s\in F(t)$, $\forall s^{\prime}\in
F(t^{\prime})$: $s\leq s^{\prime}$”., we have

$\displaystyle\bigcup_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\partial\ell_{y_{i}}(\check{X}_{i:}\bm{\beta})=\\{0\\}\quad\Leftrightarrow\quad\bigcup_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\check{X}_{i:}\bm{\beta}\subseteq{\cal
Z}[\ell_{y_{i}}]\quad\Leftrightarrow\quad[\min_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\check{X}_{i:}\bm{\beta},\max_{\bm{\beta}\in{\cal
B}^{*(\bm{w})}}\check{X}_{i:}\bm{\beta}]\subseteq{\cal Z}[\ell_{y_{i}}]$
$\displaystyle\Leftrightarrow\quad\left[\check{X}_{i:}\hat{\bm{\beta}}-\|\check{X}_{i:}\|_{2}r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}}),~{}\check{X}_{i:}\hat{\bm{\beta}}+\|\check{X}_{i:}\|_{2}r(\bm{w},\kappa,\hat{\bm{\beta}},\hat{\bm{\alpha}})\right]\subseteq{\cal
Z}[\ell_{y_{i}}].$ ($\because$ Lemma A.5)

∎

##  Appendix D Proofs and additional discussions of Section 4

###  D.1 Use of strongly-convex regularization functions other than
L2-regularization

Let us discuss using regularization functions other than L2-regularization, on
condition that it is $\kappa$-strongly convex to apply DRSSS (Lemma 3.1). In
case of L2-regularization, as seen in (9), the term
$\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\tilde{\bm{w}})})$
in the duality gap (8) becomes a quadratic function with respect to $\bm{w}$.
However, this may largely differ for other regularization functions, even if
it is $\kappa$-strongly convex (to apply DRSSS; Lemma 3.1).

As a famous example, let us see the case of the _elastic net_ regularization
[26]: with hyperparameters $\lambda>0$ and $\lambda^{\prime}>0$, the
regularization function is defined and its convex conjugate is calculated as

$\displaystyle\rho(\bm{\beta}):=\frac{\lambda}{2}\|\bm{\beta}\|_{2}^{2}+\lambda^{\prime}\|\bm{\beta}\|_{1},$
$\displaystyle\rho^{*}(\bm{v})=\frac{1}{2\lambda}\sum_{j=1}^{d}\left[\max\\{0,|v_{j}|-\lambda^{\prime}\\}\right]^{2}.$

Here, we can see that the maximization of
$\rho^{*}((\bm{w}{\raisebox{0.80002pt}{$\times$}\Box}\check{X})^{\top}\bm{\alpha}^{*(\tilde{\bm{w}})})=(1/2\lambda)\sum_{j=1}^{d}\left[\max\\{0,|\bm{w}\otimes\bm{\alpha}^{*(\tilde{\bm{w}})}\otimes\check{X}_{:j}|-\lambda^{\prime}\\}\right]^{2}$
with respect to $\bm{w}$ seems not to be easy.

Then we discuss a (sufficient) condition of regularization functions so that
weighted RERM can accept both kernelization and SSS.

######  Lemma D.1.

In weighted RERM of Definition 2.1, if $\rho$ is described as follows, it can
accept both SSS in Lemma (3.2) and kernelization in Section 4.2: $\rho$ is
described by an increasing function ${\cal H}:\mathbb{R}_{\geq
0}\to\mathbb{R}$ and a positive constant $\kappa$ as
$\rho(\bm{\beta})=(\kappa/2)\|\bm{\beta}\|_{2}^{2}+{\cal
H}(\|\bm{\beta}\|_{2})$.

###### Proof.

According to the _generalized representer theorem_ [27], weighted RERM can be
kernelized if $\rho$ is described by a strictly increasing function ${\cal
G}:\mathbb{R}_{\geq 0}\to\mathbb{R}$ as $\rho(\bm{\beta})={\cal
G}(\|\bm{\beta}\|_{2})$.

Combining the condition to apply SSS (Lemma 3.1) that $\rho$ should be
$\kappa$-strongly convex, we have the conclusion. ∎

However, we have to notive that, in order to extend it to DRSSS, the same
problem as the example of the elastic net will appear.

###  D.2 Maximizing Linear and Convex Quadratic Functions in Hyperball
Constraint

First we present Theorem 4.1 in more specific descriptions.

######  Theorem D.2.

The maximization problem in Theorem 4.1:

$\displaystyle\max_{\bm{w}\in{\cal
W}}\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w},$ ((10) restated)
$\displaystyle\text{where}\quad{\cal
W}:=\\{\bm{w}\in\mathbb{R}^{n}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S\\},$
$\displaystyle\phantom{\text{where}}\quad\tilde{\bm{w}}\in\mathbb{R}^{n},\quad\bm{b}\in\mathbb{R}^{n},\quad
S>0,$ $\displaystyle\phantom{\text{where}}\quad A\in\mathbb{R}^{n\times
n}:~{}\text{symmetric, positive semidefinite, nonzero}$

can be achieved by the following procedure. First, we define
$Q\in\mathbb{R}^{n\times n}$ and
$\Phi:=\mathrm{diag}(\phi_{1},\phi_{2},\dots,\phi_{n})$ as the
eigendecomposition of $A$ such that $A=Q^{\top}\Phi Q$, $Q$ is orthogonal
($QQ^{\top}=Q^{\top}Q=I$). Also, let $\bm{\xi}:=-\Phi
Q\tilde{\bm{w}}-Q\bm{b}\in\mathbb{R}^{n}$, and

$\displaystyle{\cal
T}(\nu)=\sum_{i=1}^{n}\left(\frac{\xi_{i}}{\nu-\phi_{i}}\right)^{2}.$ (16)

Then, the maximization (10) is equal to the largest value among them:

  * •

For each $\nu$ such that ${\cal T}(\nu)=S^{2}$ (see Lemma D.4), the value $\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}Q^{\top}(\Phi-\nu
I)^{-1}\bm{\xi}+\bm{b}^{\top}\tilde{\bm{w}}$, and

  * •

For each $\nu\in\\{\phi_{1},\phi_{2},\dots,\phi_{n}\\}$ (duplication removed)
such that “$\forall i\in[n]:~{}\phi_{i}=\nu\Rightarrow\xi_{i}=0$”, the value

$\displaystyle\max_{\bm{\tau}\in\mathbb{R}^{n}}[\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}Q^{\top}\bm{\tau}+\bm{b}^{\top}\tilde{\bm{w}}],$
$\displaystyle\text{subject to}\quad\forall i\in{\cal
F}_{\nu}:\quad\tau_{i}=\frac{\xi_{i}}{\phi_{i}-\nu},$
$\displaystyle\phantom{\text{subject to}}\quad\sum_{i\in{\cal
U}_{\nu}}\tau_{i}^{2}=S^{2}-\sum_{i\in{\cal F}_{\nu}}\tau_{i}^{2},$
$\displaystyle\text{where}\quad{\cal U}_{\nu}:=\\{i\mid
i\in[n],~{}\phi_{i}=\nu\\},\quad{\cal F}_{\nu}:=[n]\setminus{\cal U}_{\nu}.$

(Note that the maximization is easily computed by Lemma A.5.)

The computation can be done in $O(n^{3})$ time.

This can be proved as follows.

######  Lemma D.3.

For the optimization problem (10), its stationary points are obtained as the
solution of the following equations with respect to $\bm{w}$ and
$\nu\in\mathbb{R}$:

$\displaystyle A\bm{w}+\bm{b}-\nu(\bm{w}-\tilde{\bm{w}})=\bm{0},$ (17)
$\displaystyle\|\bm{w}-\tilde{\bm{w}}\|_{2}=S.$ (18)

Also, when both (17) and (18) are satisfied, the function to be maximized is
calculated as

$\displaystyle\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w}=\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}(\bm{w}-\tilde{\bm{w}})+\tilde{\bm{w}}^{\top}\bm{b}.$
(19)

###### Proof.

First, $\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w}$ is convex and not constant.
Then we can show that (10) is optimized in
$\\{\bm{w}\in\mathbb{R}^{n}\mid\|\bm{w}-\tilde{\bm{w}}\|_{2}=S\\}$, that is,
at the surface of the hyperball ${\cal W}$ (Theorem 32.1 of [24]). This proves
(18). Moreover, with the fact, we write the Lagrangian function with Lagrange
multiplier $\nu\in\mathbb{R}$ as:

$\displaystyle
L(\bm{w},\nu):=\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w}-\nu(\|\bm{w}-\tilde{\bm{w}}\|_{2}^{2}-S^{2}).$

Then, due to the property of Lagrange multiplier, the stationary points of
(10) are obtained as

$\displaystyle\frac{\partial
L}{\partial\bm{w}}=2A\bm{w}+2\bm{b}-2\nu(\bm{w}-\tilde{\bm{w}})=0,$
$\displaystyle\frac{\partial
L}{\partial\nu}=\|\bm{w}-\tilde{\bm{w}}\|_{2}^{2}-S^{2}=0,$

where the former derives (17).

Finally we show (19). If both (17) and (18) are satisfied,

$\displaystyle\bm{w}^{\top}A\bm{w}+2\bm{b}^{\top}\bm{w}$
$\displaystyle=\bm{w}^{\top}(\nu(\bm{w}-\tilde{\bm{w}})-\bm{b})+2\bm{b}^{\top}\bm{w}$
($\because$ (17))
$\displaystyle=\nu\bm{w}^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\bm{w}$
$\displaystyle=\nu(\bm{w}-\tilde{\bm{w}})^{\top}(\bm{w}-\tilde{\bm{w}})+\nu\tilde{\bm{w}}^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\tilde{\bm{w}}$
$\displaystyle=\nu
S^{2}+\nu\tilde{\bm{w}}^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\tilde{\bm{w}}$
($\because$ (18)) $\displaystyle=\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\tilde{\bm{w}}$
((19) restated)

∎

######  Lemma D.4.

Under the same definitions as Theorem D.2, The equation ${\cal T}(\nu)=S^{2}$
can be solved by the following procedure: Let
$\bm{e}:=[e_{1},e_{2},\dots,e_{N}]$ ($N\leq n$, $k\neq k^{\prime}\Rightarrow
e_{k}\neq e_{k^{\prime}}$) be a sequence of indices such that

  1. 1.

$e_{k}\in[n]$ for any $k\in[N]$,

  2. 2.

$i\in[n]$ is included in $\bm{e}$ if and only if $\xi_{i}\neq 0$, and

  3. 3.

$\phi_{e_{1}}\leq\phi_{e_{2}}\leq\dots\leq\phi_{e_{N}}$.

Note that, if $\phi_{e_{k}}<\phi_{e_{k+1}}$ ($k\in[N-1]$), then ${\cal
T}(\nu)$ is a convex function in the interval $(\phi_{e_{k}},\phi_{e_{k+1}})$
with $\lim_{\nu\to\phi_{e_{k}}+0}=\lim_{\nu\to\phi_{e_{k+1}}-0}=+\infty$.
Then, unless $N=0$, each of the following intervals contains just one solution
of ${\cal T}(\nu)=S^{2}$:

  * •

Intervals $(-\infty,\phi_{e_{1}})$ and $(\phi_{e_{N}},+\infty)$.

  * •

Let $\nu^{\\#(k)}:={\rm argmin}_{\phi_{e_{k}}<\nu<\phi_{e_{k+1}}}{\cal
T}(\nu)$. For each $k\in[N-1]$ such that $\phi_{e_{k}}<\phi_{e_{k+1}}$,

    * –

intervals $(\phi_{e_{k}},\nu^{\\#(k)})$ and $(\nu^{\\#(k)},\phi_{e_{k+1}})$ if
${\cal T}(\nu^{\\#(k)})<S^{2}$,

    * –

interval $[\nu^{\\#(k)},\nu^{\\#(k)}]$ (i.e., point) if ${\cal
T}(\nu^{\\#(k)})=S^{2}$.

It follows that ${\cal T}(\nu)=S^{2}$ has at most $2n$ solutions.

By Lemma D.4, in order to compute the solution of ${\cal T}(\nu)=S^{2}$, we
have only to compute $\nu^{\\#(k)}$ by Newton method or the like, and to
compute the solution for each interval by Newton method or the like. We show
an example of ${\cal T}(\nu)$ in Figure 5.

###### Proof of Lemma D.4.

We show the statements in the lemma that, if $\phi_{e_{k}}<\phi_{e_{k+1}}$
($k\in[N-1]$), then ${\cal T}(\nu)$ is a convex function in the interval
$(\phi_{e_{k}},\phi_{e_{k+1}})$ with
$\lim_{\nu\to\phi_{e_{k}}+0}=\lim_{\nu\to\phi_{e_{k+1}}-0}=+\infty$. Then the
conclusion immediately follows.

The latter statement clearly holds. The former statement is proved by directly
computing the derivative.

$\displaystyle\frac{d}{d\nu}{\cal
T}(\nu)=\frac{d}{d\nu}\sum_{i=1}^{n}\left(\frac{\xi_{i}}{\nu-\phi_{i}}\right)^{2}=-2\sum_{i=1}^{n}\frac{\xi_{i}^{2}}{(\nu-\phi_{i})^{3}}.$

It is an increasing function with respect to $\nu$, as long as $\nu$ does not
match any of $\\{\phi_{i}\\}_{i=1}^{n}$ such that $\xi_{i}\neq 0$. So it is
convex in the interval $\phi_{e_{k}}<\nu<\phi_{e_{k+1}}$. ∎

Figure 5: An example of the expression ${\cal T}(\nu)$ (black solid line) in
Lemmas D.2 and D.4. Colored dash lines denote terms in the summation
$(\xi_{e_{k}}/(\nu-\phi_{e_{k}}))^{2}$. We can see that, given an interval
$(\phi_{e_{k}},\phi_{e_{k+1}})$ ($k\in[N-1]$), the function is convex.

Now we are prepared to prove Theorem D.2.

###### Proof of Theorem D.2.

The condition (17) is calculated as

$\displaystyle A\bm{w}+\bm{b}=\nu(\bm{w}-\tilde{\bm{w}}),$
$\displaystyle(A-\nu I)(\bm{w}-\tilde{\bm{w}})=-A\tilde{\bm{w}}-\bm{b}.$

Here, let us apply eigendecomposition of $A$, denoted by $A=Q^{\top}\Phi Q$,
where $Q\in\mathbb{R}^{n\times n}$ is orthogonal ($QQ^{\top}=Q^{\top}Q=I$) and
$\Phi:=\mathrm{diag}(\phi_{1},\phi_{2},\dots,\phi_{n})$ is a diagonal matrix
consisting of eigenvalues of $A$. Such a decomposition is assured to exist
since $A$ is assumed to be symmetric and positive semidefinite. Then,

$\displaystyle(Q^{\top}\Phi Q-\nu I)(\bm{w}-\tilde{\bm{w}})=-Q^{\top}\Phi
Q\tilde{\bm{w}}-\bm{b},$ $\displaystyle Q^{\top}(\Phi-\nu
I)Q(\bm{w}-\tilde{\bm{w}})=-Q^{\top}\Phi Q\tilde{\bm{w}}-\bm{b},$
$\displaystyle(\Phi-\nu
I)\bm{\tau}=\bm{\xi},\quad(\text{where}\quad\bm{\tau}:=Q(\bm{w}-\tilde{\bm{w}}),\quad\bm{\xi}:=-\Phi
Q\tilde{\bm{w}}-Q\bm{b}\in\mathbb{R}^{n},)$ $\displaystyle\forall
i\in[n]:\quad(\phi_{i}-\nu)\tau_{i}=\xi_{i}.$ (20)

Note that we have to be also aware of the constraint

$\displaystyle
S=\|\bm{\tau}\|_{2}=\sqrt{\bm{\tau}^{\top}\bm{\tau}}=\sqrt{(\bm{w}-\tilde{\bm{w}})^{\top}Q^{\top}Q(\bm{w}-\tilde{\bm{w}})}=\|\bm{w}-\tilde{\bm{w}}\|_{2}.$
(21)

Here, we consider these two cases.

  1. 1.

First, consider the case when $(\Phi-\nu I)$ is nonsingular, that is, when
$\nu$ is different from any of $\phi_{1},\phi_{2},\dots,\phi_{n}$. Then, from
(21) we have

$\displaystyle
S^{2}=\|\bm{\tau}\|_{2}=\sum_{i=1}^{n}\tau_{i}^{2}=\sum_{i=1}^{n}\left(\frac{\xi_{i}}{\nu-\phi_{i}}\right)^{2}\quad\bigl{(}=:{\cal
T}(\nu)\bigr{)}.$ (22)

So, values of (10) for all stationary points with respect to $\bm{w}$ and
$\nu$ (on condition that $(\Phi-\nu I)$ is nonsingular) can be obtained by
computing (19) for each $\nu$ satisfying (22), that is,

     * •

for such $\nu$ computing $\bm{\tau}$ by (20), and

     * •

computing (19) as $\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\tilde{\bm{w}}=\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}Q^{\top}\bm{\tau}+\bm{b}^{\top}\tilde{\bm{w}}$.

  2. 2.

Secondly, consider the case when $(\Phi-\nu I)$ is nonsingular, that is, when
$\nu$ is equal to one of $\phi_{1},\phi_{2},\dots,\phi_{n}$. First, given
$\nu$, let ${\cal U}_{\nu}:=\\{i\mid i\in[n],~{}\phi_{i}=\nu\\}$ be the
indices of $\\{\phi_{i}\\}_{i}$ equal to $\nu$ (this may include more than one
indices), and ${\cal F}_{\nu}:=[n]\setminus{\cal U}_{\nu}$. Note that, by
assumption, ${\cal U}_{\nu}$ is not empty. Then, all stationary points of (10)
with respect to $\bm{w}$ and $\nu$ (on condition that $(\Phi-\nu I)$ is
singular) can be found by computing the followings for each
$\nu\in\\{\phi_{1},\phi_{2},\dots,\phi_{n}\\}$ (duplication excluded):

     * •

If $\xi_{i}\neq 0$ for at least one $i\in{\cal U}_{\nu}$, the equation (20)
cannot hold.

     * •

If $\xi_{i}=0$ for all $i\in{\cal N}_{\nu}$, the equation (20) may hold. So we
calculate $\bm{\tau}$ that maximizes (10) as follows:

       * –

Fix $\tau_{i}=\xi_{i}/(\phi_{i}-\nu)$ for $i\in{\cal F}_{\nu}$.

       * –

Set the constraint $\sum_{i\in{\cal
U}_{\nu}}\tau_{i}^{2}=S^{2}-\sum_{i\in{\cal F}_{\nu}}\tau_{i}^{2}$ (due to
(21)).

       * –

Maximize (10) with respect to $\\{\tau_{i}\\}_{i\in{\cal U}_{\nu}}$ under the
constraints above. Here, by (19) we have only to calculate

$\displaystyle\max_{\bm{\tau}\in\mathbb{R}^{n}}[\nu
S^{2}+(\nu\tilde{\bm{w}}+\bm{b})^{\top}(\bm{w}-\tilde{\bm{w}})+\bm{b}^{\top}\tilde{\bm{w}}],$
(23) $\displaystyle\text{subject to}\quad\forall i\in{\cal
F}_{\nu}:\quad\tau_{i}=\frac{\xi_{i}}{\phi_{i}-\nu},$
$\displaystyle\phantom{\text{subject to}}\quad\sum_{i\in{\cal
U}_{\nu}}\tau_{i}^{2}=S^{2}-\sum_{i\in{\cal F}_{\nu}}\tau_{i}^{2},$

which is easily computed by Lemma A.5. The value of the maximization result is
equal to that of (10) on condition that $\nu$ is specified above.

So, collecting these result and taking the largest one, the maximization (on
condition that $(\Phi-\nu I)$ is singular) is completed.

Taking the maximum of the two cases, we have the maximization result of (10).

Finally we show the computational cost. All matrix multiplications in the
computation process can be done in at most $O(n^{2})$ time, and we
additionally need the following computations: the eigendecomposition of $A$
and the solution of ${\cal T}(\nu)=S^{2}$ using Newton method or the like
(Lemma D.4). The former can be done in $O(n^{3})$ time. The latter requires
Newton method computations for $O(n)$ time, and each of Newton method
computation requires evaluations of ${\cal T}(\nu)$ that requires $O(n^{2})$
time. So, if we assume that the number of repetition of Newton method is
constant, it can be done in $O(n^{2})$ time. This concludes that the
computational cost is $O(n^{3})$. ∎

##  Appendix E Details of experiments

###  E.1 Data and Learning Setup

The criteria of selecting datasets (Table 2) and detailed setups are as
follows:

  * •

All of the datasets are downloaded from LIBSVM dataset [21]. We used training
datasets only if test datasets are provided separately (“splice”, “svmguide1”
and “madelon”).

  * •

We selected datasets from LIBSVM dataset containing 100 to 10,000 samples, 100
or fewer features, and the area under the curve (AUC) of the receiver
operating characteristic (ROC) is 0.9 or higher for the regularization
strengths ($\lambda$) we examined so that they tend to facilitate more
effective sample screening.

  * •

In the table, the column “$d$” denotes the number of features including the
intercept feature (Remark 2.2).

The choice of the regularization hyperparameter $\lambda$, based on the
characteristics of the data, is as follows: We set $\lambda$ as $n$, $n\times
10^{-0.5}$, $n\times 10^{-1.0}$, $\ldots$, $n\times 10^{-3.0}$. (For DRSSS
with DL, we set 1000 instead of $n$.) This is because the effect of $\lambda$
gets weaker for larger $n$.

The choice of the hyperparameter in RBF kernel is fixed as follows: we set
$\zeta=d^{\prime}*\mathbb{V}(Z)$ as suggested in sklearn.svm.SVC of _scikit-
learn_ [28], where $\mathbb{V}$ denotes the elementwise sample variance.

###  E.2 Simulation Setup

In Section 5.2, the experiment of the “simulated” maximization of
$\max_{\bm{w}\in{\cal W}}$ in (7) (Theorem 3.5) is computed as follows.

  * •

First, we chose a vector $\bm{w}$ from $\|\bm{w}-\tilde{\bm{w}}\|_{2}=S$ (not
$\|\bm{w}-\tilde{\bm{w}}\|_{2}\leq S$; see (18) in Lemma D.3) with the
following procedure: first we draw $\bm{v}$ from a standard normal
distribution, then we set $\bm{w}\leftarrow S\bm{v}/\|\bm{v}\|_{2}$.

  * •

We repeated this for specified number of trials ${\cal Q}$, which we denote by
$\bm{w}^{[1]}$, $\bm{w}^{[2]}$, $\ldots$, $\bm{w}^{[{\cal Q}]}$.

  * •

We define the “simulated” maximization of $\max_{\bm{w}\in{\cal W}}f(\bm{w})$
($f$: any function) as $\max_{q\in[{\cal Q}]}f(\bm{w}^{[q]})$.

In the experiment, for each experimental setup, we tried this for 10 times,
and in the plot of the result we draw its average and standard deviation.

###  E.3 All Experimental Results of Section 5.2

First, we show all experimental results of safe sample screening rates for
linear and RBF-kernel SVMs in Figure 6.

Then, we show experimental results of unscreened samples of DRSSS by the
proposed method and simulations in Figure 7. Note that, because we have the
same plot as 4 for each choice of $\lambda$, $a$ and the kernel function, it
is difficult to present all results. So we present for only these setups:
$\lambda\in\\{n,0.01n\\}$, $a=1.02$ and no kernel function (linear
prediction).

Dataset: australian, Model: Linear |  Dataset: australian, Model: RBF kernel
---|---
Dataset: breast-cancer, Model: Linear |  Dataset: breast-cancer, Model: RBF kernel
Dataset: heart, Model: Linear |  Dataset: heart, Model: RBF kernel
Dataset: ionosphere, Model: Linear |  Dataset: ionosphere, Model: RBF kernel
Dataset: sonar, Model: Linear |  Dataset: sonar, Model: RBF kernel
Dataset: splice, Model: Linear |  Dataset: splice, Model: RBF kernel
Dataset: svmguide1, Model: Linear |  Dataset: svmguide1, Model: RBF kernel
Figure 6: Safe sample screening rates for linear and RBF-kernel SVMs, under the settings described in Section 5 and Appendix E.1. Dataset: australian, $\lambda=0.01n=6.9$ |  Dataset: australian, $\lambda=n=690.0$
---|---
Dataset: breast-cancer, $\lambda=0.01n=6.83$ |  Dataset: breast-cancer, $\lambda=n=683.0$
Dataset: heart, $\lambda=0.01n=2.7$ |  Dataset: heart, $\lambda=n=270.0$
Dataset: ionosphere, $\lambda=0.01n=3.51$ |  Dataset: ionosphere, $\lambda=n=351.0$
Dataset: sonar, $\lambda=0.01n=2.08$ |  Dataset: sonar, $\lambda=n=208.0$
Dataset: splice, $\lambda=0.01n=10.0$ |  Dataset: splice, $\lambda=n=1000.0$
Dataset: svmguide1, $\lambda=0.01n=30.89$ |  Dataset: svmguide1, $\lambda=n=3089.0$
Figure 7: Numbers of samples not screened out, with proposed DRSSS and the
simulated ones (see Appendix E.2 for details). Error bars are standard
deviations of 10 trials.