Kernel Affine Hull Machines for Differentially Private Learning

Mohit Kumar<EMAIL_ADDRESS>
Faculty of Computer Science and Electrical Engineering

University of Rostock, Germany

Software Competence Center Hagenberg GmbH

A-4232 Hagenberg, Austria
Bernhard A. Moser<EMAIL_ADDRESS>
Software Competence Center Hagenberg GmbH

A-4232 Hagenberg, Austria

Institute of Signal Processing

Johannes Kepler University Linz, Austria
Lukas Fischer<EMAIL_ADDRESS>
Software Competence Center Hagenberg GmbH

A-4232 Hagenberg, Austria

This paper explores the use of affine hulls of points as a means of representing data via learning in Reproducing Kernel Hilbert Spaces (RKHS), with the goal of partitioning the data space into geometric bodies that conceal privacy-sensitive information about individual data points, while preserving the structure of the original learning problem. To this end, we introduce the Kernel Affine Hull Machine (KAHM), which provides an effective way of computing a distance measure from the resulting bounded geometric body. KAHM is a critical building block in wide and deep autoencoders, which enable data representation learning for classification applications. To ensure privacy-preserving learning, we propose a novel method for generating fabricated data, which involves smoothing differentially private data samples through a transformation process. The resulting fabricated data guarantees not only differential privacy but also ensures that the KAHM modeling error is not larger than that of the original training data samples. We also address the accuracy-loss issue that arises with differentially private classifiers by using fabricated data. This approach results in a significant reduction in the risk of membership inference attacks while incurring only a marginal loss of accuracy. As an application, a KAHM based differentially private federated learning scheme is introduced featuring that the evaluation of global classifier requires only locally computed distance measures. Overall, our findings demonstrate the potential of KAHM as effective tool for privacy-preserving learning and classification.

Kernel, learning, differential privacy, regularization, affine hull.

§ INTRODUCTION

Privacy-preserving data representation learning is the central problem of this study. Deep neural networks have gained significant attention in recent years, and have been successfully applied across a wide range of applications. However, there are three issues pertaining to deep neural networks: determination of the optimal model structure, gradient-based iterative nature of learning algorithms, and requirement of large training data. These issues have motivated an alternative kernel-based nonparametric approach to learning offering a unique advantage that kernel-based solutions can be computed analytically and analyzed using a broad range of mathematical techniques. Thus, kernels have been widely used in machine learning [Ghojogh et al., 2021, Hofmann et al., 2008] and can be scaled up for their applicability in large scale scenarios [Rudi et al., 2017]. Not only the parallels between the properties of deep neural networks and kernel methods have been established [Belkin et al., 2018], but also deep kernel machines have been introduced [Wilson et al., 2016, Nikhitha et al., 2021]. Kernel autoencoders are effective models for representation learning. The kernel formulation of an autoencoder has been considered in [Gholami and Hajisami, 2016] from a hashing perspective. A deep autoencoder, that aligns the latent code with a user-defined kernel matrix to learn similarity-preserving data representations, has been suggested [Kampffmeyer et al., 2018]. Further, a kernel autoencoder based on the composition of mappings from vector-valued reproducing kernel Hilbert spaces has been studied [Laforgue et al., 2019]. Recently, a fuzzy theoretic approach to kernel based wide and conditionally deep autoencoders has been introduced [Kumar and Freudenthaler, 2020, Kumar et al., 2021, Kumar et al., 2021, Zhang et al., 2022, Kumar et al., 2021, Kumar et al., 2021, Kumar et al., 2023], wherein analytical solutions are derived for the learning of models using variational optimization technique. This approach has been further extended to privacy-preserving learning under a differential privacy framework [Kumar, 2023, Kumar et al., 2021, Kumar et al., 2020].

Differential privacy [Dwork and Roth, 2014] is a standard framework to quantify the degree to which the data privacy of each individual in the dataset is preserved while releasing the output of any statistical analysis algorithm. Differential privacy, being a property of an algorithm's data access mechanism, automatically provides protection against arbitrary privacy-leakage risks. The goal of protecting sensitive information (that is embedded in training data) from any leakage through machine learning models has been addressed within the framework of differential privacy [Abadi et al., 2016, Phan et al., 2016]. A differentially private mechanism to approximate a real-valued function is to perturb the function output via adding noise calibrated to the global sensitivity of the function [Dwork et al., 2006]. An obvious effect of adding noise into an algorithm for preserving differential privacy is the loss in algorithm's accuracy. The iterative nature of machine learning algorithms causes a high cumulative privacy loss and thus a high amount of noise need to be added to compensate for the privacy loss. A moments accountant method [Abadi et al., 2016], based on the properties of a privacy loss random variable, has been suggested to keep track of the privacy loss incurred by successive iterations for composition analysis. As differential privacy remains immune to any post-processing of released output, the output data can be denoised using statistical estimation theory [Balle and Wang, 2018]. It is not surprising that efforts have been made to optimize the privacy-accuracy tradeoff, e.g., the studies [Kumar et al., 2019, Kumar et al., 2021] derive the probability density function of noise that minimizes the expected noise magnitude together with satisfying the sufficient conditions for $(\epsilon,\delta)-$differential privacy. The major limitation of the differentially private machine learning is that privacy is achieved at the considerable cost of accuracy.

Despite the kernel methods being studied [Jain and Thakurta, 2013, Chaudhuri et al., 2011, Zhang et al., 2019] in a differentially private setting, the state-of-art lacks geometrically inspired kernel machines for scalable learning solutions that remain accurate even after providing differential privacy guarantee. With the motivation of leveraging kernel learning for geometrically inspired data representation, this study aims to develop a methodology for privacy-preserving learning while mitigating the accuracy-loss issue of differential privacy. The main contributions and results of this study are stated in the following.

Kernel Affine Hull Machines: For given distinct data points $(y^i)_{i= 1, \ldots, N}$ in some vector space we study the sets of the affine form
ℒ     =     {y =  (w^1/∑_i=1^N w^i) y^1+ ⋯+ (w^N/∑_i=1^N w^i) y^N   |  w^i ∈ℝ },

and ask for reasonable conditions on the real-valued scalars $(w^{i})_i$ to serve our purposes of privacy-preserving machine learning. First of all, in our approach $(w^{i})_i$ are considered to be functions in a RKHS. By postulating that indicator functions (specifically, their RKHS approximations) define scalar-valued functions $(w^{i})_i$, the set $\mathcal{L}$ actually can be identified by functions defining a subset in RKHS that represents our data points. This way we introduce the concept of Kernel Affine Hull Machine (KAHM) to learn kernel-based representation of multivariate scattered data as follows.

Let $n,p,N$ be the positive integers and $\mathcal{X} \subset \mathbb{R}^n$ be a region. Let $\mathcal{H}_k(\mathcal{X})$ be the reproducing kernel Hilbert space of functions from $\mathcal{X}$ to $\mathbb{R}$ for a reproducing kernel $k : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$. For a finite set of ordered pairs $\{(x^i,y^i) \in \mathcal{X} \times \mathbb{R}^p \; \mid \; i \in \{1,\cdots,N \}\}$ such that $\{ x^1,\cdots,x^N\}$ are pairwise distinct points, a point $y^i$ can be represented using indicator functions as
y^i     =       1_{x^1}(x^i)   y^1 + ⋯+ 1_{x^N}(x^i)  y^N,

where $\mathbbm{1}_{\{x^i\}}$ is the indicator function of the set $\{ x^i\}$. We approximate the indicator function $\mathbbm{1}_{\{x^i\}}$ through a function in $ \mathcal{H}_{k}(\mathcal{X})$ that fits to the ordered pairs $\{ \left(x^j, \mathbbm{1}_{\{x^i\}}(x^j)\right) \; \mid \; j \in \{1,\cdots,N \} \}$. In the reproducing kernel Hilbert space (RKHS), the function $h^i$ approximating $\mathbbm{1}_{\{x^i\}}$ is given as the solution of the following kernel regularized least squares problem:
h^i     =       min_f ∈ℋ_k(𝒳)   ( ∑_j=1^N |1_{x^i}(x^j) - f(x^j) |^2 + λ f ^2_ℋ_k(𝒳) ),  λ∈ℝ_+,

where $\left \| f \right \|_{\mathcal{H}_k(\mathcal{X})} := \sqrt{\left < f, f \right>_{\mathcal{H}_k(\mathcal{X})}}$ is the norm induced by the inner product on $\mathcal{H}_k(\mathcal{X})$. The fact that $h^i $ is an approximation of $\mathbbm{1}_{\{x^i\}}$ (i.e. the value $h^i(x)$ represents kernel-smoothed “membership” of $x$ to the set $\{ x^i \}$) allows introducing a model based on the affine combination of $y^1,\cdots,y^N$ as in the following:
A(x)     =     h^1(x)/∑_i=1^N h^i(x) y^1 + ⋯+ h^N(x)/∑_i=1^N h^i(x)  y^N.

Let $\mathrm{aff}(\{y^1,\cdots,y^N \})$ denote the affine hull of $\{y^1,\cdots,y^N\}$. The function $A:\mathcal{X} \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N \})$ is referred to as kernel affine hull machine, since it maps a point $x \in \mathcal{X}$ onto the affine hull of $\{y^1,\cdots,y^N\}$ via learning representation of $x^1,\cdots,x^N$ through functions in reproducing kernel Hilbert space. The image of $A$,
A[𝒳]     :=     { A(x)   |  x ∈𝒳 }     ⊂    aff({y^1,⋯,y^N }),

defines a region in $\mathrm{aff}(\{y^1,\cdots,y^N \})$. Fig. <ref> displays a few examples of 3-dimensional samples and regions defined by KAHMs' images.

[first example] [second example] [third example]
A few examples of 3-dimensional samples $\{y^1,\cdots,y^N \}$ and regions in $\mathrm{aff}(\{y^1,\cdots,y^N \})$ defined by the images of corresponding KAHMs.

Regularization Parameter for Kernel Regularized Least Squares: Since indicator functions are approximated via solving a regularized least squares problem, the kernel regularized least squares problem is revisited in a deterministic setting with focus on the determination of regularization parameter. A reasonable choice for regularization parameter is to set it larger than the mean-squared-error on training samples. With this choice, the problem of determining regularization parameter can be reduced to an equivalent problem of finding the unique fixed point of a real-valued positive function. An iterative scheme, together with the mathematical proof of convergence, is provided to find the fixed point and thus to determine the regularization parameter.

Boundedness of KAHM: The KAHM mapping is a bounded function and thus the image of KAHM defines a bounded region in the affine hull of data samples. The boundedness of KAHM on data space is proven via deriving upper bounds on the Euclidean norm of KAHM output.

Distance Function Induced by KAHM: The KAHM induces a function on data space, referred to as distance function, which is defined on a data point as equal to the distance between that point and its image under KAHM. The distance of an arbitrary point from its image (by the KAHM onto the affine hull of given data samples) is a measure of the distance between that arbitrary point and the given data samples. This is proven via deriving upper bounds on the ratio of these two distances.

KAHM Compositions for Data Representation Learning: The KAHM could serve as the building block for deep models. A nested composition of KAHMs, referred to as Conditionally Deep Kernel Affine Hull Machine, is considered for data representation learning. The conditionally deep KAHM discovers layers of increasingly abstract data representation with lowest-level data features being modeled by first layer and the highest-level by end layer. Further, a parallel composition of conditionally deep KAHMs, referred to as Wide Conditionally Deep Kernel Affine Hull Machine, is considered to efficiently learn the representation of big data.

KAHM Based Classification: Similarly to the KAHM, both conditional deep KAHM and wide conditionally deep KAHM induce the distance function with value on a point indicating the distance of the point from data samples. This property of the distance function is leveraged to build a KAHM based classifier via modeling the region of each class through a separate KAHM based composition.

Membership-Inference Score for KAHM Based Classifier: Since the KAHM based classifier assigns a class-label to a data point based on the closeness of the point to the training data samples of that class, there is a possibility of an inference of the membership of a data point to the set of training data samples. To evaluate the potential of KAHM induced distance function in inferring the membership of a data point to the training dataset, a score, referred to as membership-inference score, is defined for evaluating the risk of membership inference attack. The membership-inference score is defined as the $L2$ distance between density of probability distribution on values of the distance function at training data points and the density of probability distribution on distance function values at test data points.

Differentially Private KAHM Based Classifier: To ensure that KAHM based classifier keeps the privacy of training data protected, an optimal differentially private noise adding mechanism [Kumar et al., 2019] is applied on training data samples. The considered noise adding mechanism is optimal in the sense that it minimizes the expected noise magnitude while ensuring $(\epsilon,\delta)-$differential privacy.

Data Smoother for Reduction in KAHM Modeling Error: The differentially private noise added training data samples are smoothed through a transformation such that the error in KAHM modeling of smoothed data is not larger than the error in KAHM modeling of original data. It is shown that the error in KAHM modeling of smoothed data can be reduced to an arbitrary low value.

Differentially Private Data Fabrication: The smoothed data samples, guaranteeing not only the differential privacy but also the modeling error not to be larger than that of original data samples, serve as the fabricated data.

Fabricated Data Based Classifier to Mitigate Accuracy-Loss Issue of Differential Privacy: The fabricated data samples are finally used to build the KAHM based differentially private classifier. The advantage of using fabricated data for classification is that fabricated data leads to a considerable reduction in the risk of membership inference attack with a marginal loss of accuracy. Hence, the accuracy-loss issue of differential privacy is mitigated. Fig. <ref> provides an example of differentially private classifier built with a 2-dimensional fabricated dataset with 3 classes.

[data samples and images of corresponding KAHMs] [differentially private fabricated data samples and images of corresponding KAHMs] [decision boundaries determined by KAHM based differentially private classifier with fabricated data]
An example of differentially private classifier built with a 2-dimensional fabricated dataset with 3 classes.

Application to Differentially Private Federated Learning: The different KAHMs built independently using different datasets can be combined together using the KAHM induced distance function. This allows introducing a federated learning scheme that combines together the local privacy-preserving KAHM based classifiers to build a global classifier. A significant feature of the scheme is that the evaluation of global classifier requires only locally computed distance measures.

A list of contributes and results.

Contributions     Results

1     $\begin{array}{c} \mbox{Determination of Regularization Parameter for}\\ \mbox{Kernel Regularized Least Squares} \end{array}$      Theorem <ref>
2     Concept of Kernel Affine Hull Machine (KAHM)     Definition <ref>
3     Boundedness of KAHM     Theorem <ref>
4     $\begin{array}{c}\mbox{KAHM Induced Function as}\\ \mbox{Measure of Distance from a Set of Points} \end{array}$        Theorem <ref>
5     KAHM Compositions for Data Representation Learning     Definition <ref>, Definition <ref>
6     $\begin{array}{c} \mbox{Functions Induced by KAHM Compositions as} \\ \mbox{Measure of Distance from a Set of Points} \end{array}$      Theorem <ref>, Theorem <ref>
7     Membership-Inference Score for KAHM Based Classifier     Eq. (<ref>)
8     $\begin{array}{c} \mbox{A Data Smoother with Guarantee of} \\ \mbox{Reduction in KAHM Modeling Error} \end{array}$       Definition <ref>, Theorem <ref>
9     Differentially Private Data Fabrication     Definition <ref>
10     $\begin{array}{c} \mbox{Fabricated Data Based Classifier to Mitigate} \\ \mbox{Accuracy-Loss Issue of Differential Privacy} \end{array}$      Definition <ref>
11     Differentially Private Federated Learning     Fig. <ref>

Table <ref> summarizes the main contributions and results of this study. The similarity of the current study with previous works is confined to the following two points:

* The wide and conditionally deep architecture consisting of the composition of kernel based models follows from [Kumar and Freudenthaler, 2020, Kumar et al., 2021, Kumar et al., 2021, Zhang et al., 2022, Kumar et al., 2021], wherein a kernel based variational fuzzy model (motivated by measure theoretic basis [Kumar et al., 2021]) is used. In contrast, the current study explores geometrically inspired kernel affine hull machines.

* The current study follows the federated learning architecture of [Kumar et al., 2021, Kumar et al., 2020, Kumar et al., 2023] with the difference that instead of fuzzy attributes, the KAHM induced distance measures are applied to aggregate the distributed local models for federated learning.

To our best knowledge, the proposed KAHM based differentially private learning approach is original. None of the previous studies has developed geometrically inspired kernel affine hull machines as effective means for differentially private data representation learning which is the novelty.

The paper is organized into sections. The mathematical notation used throughout the paper is provided in Section <ref>. Section <ref> introduces the concept of KAHM. KAHM based wide and deep models are presented in Section <ref> for data representation learning. Differentially private classification application is considered in Section <ref> followed by experimentation in Section <ref>. Finally, the concluding remarks are presented in Section <ref>.

§ NOTATIONS

The following notations are introduced:

* Let $N,n,p,M,S,C \in \mathbb{Z}_{+}$ be the positive integers.

* Let $\mu_{max}(K)$ and $\mu_{min}(K)$ denote the maximum eigenvalue and minimum eigenvalue respectively of a square matrix $K$.

* Let $\sigma_{max}(K)$ and $\sigma_{min}(K)$ denote the maximum singular value and minimum singular value of a matrix $K$.

* Let $\mathrm{aff}(\mathbf{Y})$ denote the affine hull of a set $\mathbf{Y} \subset  \mathbb{R}^p$.

* For a vector $y \in \mathbb{R}^p$, $\| y\|$ denotes the Euclidean norm of $y$.

* For a matrix $Y \in \mathbb{R}^{N \times p}$, $\|Y\|_2$ denotes the spectral norm, $\| Y \|_F$ denotes the Frobenius norm, $\|Y\|_1$ denotes the 1-norm, $\|Y\|_{\mathrm{max}}$ denotes the max norm, $(Y)_{i,:}$ denotes the $i-$th row, $(Y)_{:,j}$ denotes the $j-$th column, and $(Y)_{i,j}$ denotes the $(i,j)-$th element of $Y$.

* Let $\circ$ denote the Hadamard product.

* Let $I_N$ denote the identity matrix of the size $N$ and $\mathbf{1}_N$ denotes the $N \times 1$ vector of ones.

* Let $\mathbbm{1}_{\mathbf{Y}}$ denote the indicator function of the set $\mathbf{Y}$.

* Let $\mathcal{X} \subset \mathbb{R}^n$ be a region.

* $ K \succ 0$ denotes that a symmetric matrix $K$ is positive definite.

* A Reproducing Kernel Hilbert Space (RKHS), $\mathcal{H}_{k}(\mathcal{X})$, is a Hilbert space of functions $f: \mathcal{X} \rightarrow \mathbb{R}$ on a non-empty set $\mathcal{X}$ with a reproducing kernel $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ satisfying $\forall x \in \mathcal{X}$ and $\forall f \in \mathcal{H}$,

* $k(\cdot,x) \in \mathcal{H}_k(\mathcal{X})$,

* $\left < f, k(\cdot,x)  \right>_{\mathcal{H}_k(\mathcal{X})} = f(x)$,

where $\left < \cdot, \cdot \right>_{\mathcal{H}_k(\mathcal{X})} : \mathcal{H}_k(\mathcal{X}) \times \mathcal{H}_k(\mathcal{X}) \rightarrow \mathbb{R}$ is an inner product on $\mathcal{H}_k(\mathcal{X})$.

* Let $\left \| f \right \|_{\mathcal{H}_k(\mathcal{X})} := \sqrt{\left < f, f \right>_{\mathcal{H}_k(\mathcal{X})}}$ denote the norm induced by the inner product on $\mathcal{H}_k(\mathcal{X})$.

§ KERNEL AFFINE HULL MACHINES

The computation of KAHM requires solving a kernel regularized least squares problem. Therefore the kernel regularized problem is revisited (in Section <ref>) with focus on the determination of regularization parameter (in Section <ref>). The obtained solution is applied (in Section <ref>) to learn data representation in RKHS facilitating the definition of KAHM (in Section <ref>).

§.§ Kernel Regularized Least Squares

Given a training data set $\left\{ (x^i,y^i) \in \mathcal{X} \times \mathbb{R}^p \; \mid \; i \in \{1,\cdots,N \} \right\}$ such that $\{ x^1,\cdots,x^N\}$ are pairwise distinct points, consider a positive-definite real-valued kernel $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ on $\mathcal{X}$ with a corresponding RKHS $\mathcal{H}_k(\mathcal{X})$. Assuming that $\mathcal{X} \subset \mathbb{R}^n$, real-valued matrices $X \in \mathbb{R}^{N \times n}$ and $Y \in \mathbb{R}^{N \times p}$ are defined as
X     =     [[][c],c/c/c, x^1     ⋯    x^N  ]^T

Y     =     [[][c],c/c/c, y^1     ⋯    y^N ]^T.

Let $(Y)_{:,j}$ denote the $j-$th column of $Y$, i.e.,
(Y)_:,j     =        [[][c],c/c/c, y^1_j     ⋯    y^N_j ]^T,

where $j \in \{1,\cdots,p \}$ and $y^i_j$ is the $j-$th element of $i-$th output sample $y^i$. The solution of the following regularized least squares problem:
f^*_k,X,(Y)_:,j,λ     =       min_f ∈ℋ_k(𝒳)   ( ∑_i=1^N |y^i_j - f(x^i) |^2 + λ f ^2_ℋ_k(𝒳) ),  λ∈ℝ_+,

using the representer theorem [Schölkopf et al., 2001], can be written as
f^*_k,X,(Y)_:,j,λ(x)     =      [[][c],c/c/c, k(x,x^1)     ⋯    k(x,x^N) ] (K_X + λI_N )^-1 (Y)_:,j

where $I_N$ is the identity matrix of size $N$ and $K_{X}$ is $N \times N$ kernel matrix whose $(i,j)-$th entry is given as
(K_X)_ij     =     k(x^i, x^j).

The regularized least squares problem can be solved for each output dimension resulting in a vector-valued function $\mathbf{f}^*_{k,X,Y,\lambda}: \mathcal{X} \rightarrow \mathbb{R}^p$ defined as
𝐟^*_k,X,Y,λ(x)     :=      [[][c],c/c/c, f^*_k,X,(Y)_:,1,λ(x)     ⋯    f^*_k,X,(Y)_:,p,λ(x)  ]^T

=     Y^T (K_X + λI_N )^-1 [[][c],c/c/c, k(x,x^1)     ⋯    k(x,x^N) ]^T.

§.§ Determination of Regularization Parameter

To compute the kernel regularized least squares solution (<ref>), a choice for regularization parameter $\lambda \in \mathbb{R}_+$ need to be made. A possible choice could be of setting $\lambda$ larger than the mean squared error on training data. The mean squared error on training data, which obviously depends on the choice of regularization parameter $\lambda$, is given as
e(λ)     =     1/pN ∑_j=1^p ∑_i=1^N |y_j^i - f^*_k,X,(Y)_:,j,λ(x^i)  |^2

=        1/pN ∑_j=1^p (Y)_:,j - K_X (K_X + λI_N )^-1 (Y)_:,j ^2.

We choose $\lambda$ to be larger than $e$. That is, there exists a constant $\tau \in \mathbb{R}_{+}$ such that
λ    =      e(λ)  + τ,

λ    =     1/pN ∑_j=1^p (Y)_:,j - K_X (K_X + λI_N )^-1 (Y)_:,j ^2 + τ.

Eq. (<ref>) can be solved for $\lambda$ via applying the following result:

Let $\mathcal{R}_{k,X,Y}: \mathbf{R}_{+} \times \mathbf{R}_{+} \rightarrow \mathbf{R}_{+}$ be a function defined as
ℛ_k,X,Y(e,τ)    :=       1/pN ∑_j=1^p (Y)_:,j- K_X (K_X + (e+τ) I_N )^-1 (Y)_:,j ^2.

We have followings:

* For $e, \tau \in \mathbf{R}_{+}$,
ℛ_k,X,Y(e,τ)    ∈     ( 0,Y ^2_F/pN ).

* For $e,\tau \in \mathbf{R}_{+}$,
ℛ_k,X,Y(e,τ)/e     ∈     (0, 2/(e+τ) Y ^2_F/pN   ).

* For a given $\tau \in \mathbf{R}_{+}$, $\mathcal{R}_{k,X,Y}(e,\tau)$ has at least one fixed point in $(0, \|Y \|^2_F/pN )$.

* If we choose
τ    ≥    2/pNY ^2_F,

then the iterations
e|_it+1     =     ℛ_k,X,Y(e|_it,τ),  it ∈{0,1,⋯}

e|_0     ∈    (0,Y ^2_F/pN )

converge to the unique fixed point of $\mathcal{R}_{k,X,Y}(e,\tau)$.

The proof is provided in Appendix <ref>.

It follows from Theorem <ref> that the iterations (<ref>)-(<ref>) converge to the unique fixed point of $\mathcal{R}_{k,X,Y}(e,\tau)$ for any $\tau$ satisfying (<ref>). Let $\hat{e}$ be the unique fixed point corresponding to the minimum possible value of $\tau$ satisfying (<ref>) (which is equal to $\frac{2}{pN}\|Y \|^2_F$), i.e.,
ê     =     ℛ_k,X,Y(ê,2/pNY ^2_F).

Now, the value of regularization parameter $\lambda$ satisfying (<ref>) for $\tau = \frac{2}{pN}\|Y \|^2_F$ is given as
λ^*     =      ê + 2/pNY ^2_F.

§.§ Learning Representation of Data Points in RKHS

Given a finite number of pairwise distinct points: $X = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} x^1 & \cdots & x^N \end{IEEEeqnarraybox*} \right]^T$ with $x^1,\cdots,x^N \in \mathcal{X} \subset \mathbb{R}^n$, a data point $x^i$ can be represented using indicator functions as
x^i     =       1_{x^1}(x^i)   x^1 + ⋯+ 1_{x^N}(x^i)  x^N,  .

For a kernel-based representation of data points, the indicator functions $\mathbbm{1}_{\{x^1\}},\cdots,\mathbbm{1}_{\{x^N\}}$ are approximated through functions in RKHS $\mathcal{H}_{k}(\mathcal{X})$. To approximate $\mathbbm{1}_{\{x^i\}}$, a function is fitted on the ordered pairs $\{ \left(x^j, \mathbbm{1}_{\{x^i\}}(x^j)\right) \; \mid \; j \in \{1,\cdots,N \} \}$ via solving the following kernel regularized least squares problem:
h^i_k,X,λ      =       min_f ∈ℋ_k(𝒳)   ( ∑_j=1^N |1_{x^i}(x^j) - f(x^j) |^2 + λ f ^2_ℋ_k(𝒳) ),  λ∈ℝ_+.

Using the representer theorem [Schölkopf et al., 2001], the solution of (<ref>) is as follows:
h^i_k,X,λ(x)      =     (I_N)_i,: (K_X + λI_N )^-1 [[][c],c/c/c, k(x,x^1)     ⋯    k(x,x^N) ]^T,

where $K_{X}$ is kernel matrix defined as in (<ref>) and $(I_N)_{i,:}$ denotes the $i-$th row of identity matrix of size $N$. The function $ h^i_{k,X,\lambda}: \mathcal{X} \rightarrow \mathbb{R}$ is a kernel-smoothed approximation of $\mathbbm{1}_{\{x^i\}}:\mathcal{X} \rightarrow \{0,1 \}$, and thus $ h^i_{k,X,\lambda}(x)$ represents the kernel-smoothed “membership” of $x$ to the set $\{ x^i\}$. Given a response variable $y^i \in \mathbb{R}^p$ associated to data point $x^i$, a regression model based on the affine combination of response variables can be defined as in the following:
A(x)     =      h^1_k,X,λ(x)/∑_i=1^N  h^i_k,X,λ(x)y^1 + ⋯+   h^N_k,X,λ(x)/∑_i=1^N  h^i_k,X,λ(x)y^N,

where $ h^i_{k,X,\lambda}(x)/\sum_{i=1}^N  h^i_{k,X,\lambda}(x)$ represents kernel-smoothed relative membership of $x$ to the set $\{x^i\}$. The regression model $A:\mathcal{X} \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N \})$ maps a point $x \in \mathcal{X}$ onto the affine hull of $\{y^1,\cdots,y^N\}$ through an affine combination where the coefficients are computed from the functions in RKHS $\mathcal{H}_{k}(\mathcal{X})$. The model $A$ is referred to as a kernel affine hull machine in this study.

§.§ An Affine Hull Machine

For a finite set $\{y^1,\cdots,y^N\} \subset \mathbb{R}^p$ of $N$ pairwise distinct points, we aim to learn representation of data points in RKHS. For this, we consider a special case of the regression model $A:\mathcal{X} \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N \})$ (defined as in (<ref>)) for $\mathcal{X}  =  \{ Py \; \mid \; y \in \mathbb{R}^p \}$, where $P \in \mathbb{R}^{n \times p}\: (n \leq p)$ is an encoding matrix such that product $Py$ is a lower-dimensional encoding for $y$. In this case, the indicator function $\mathbbm{1}_{\{Py^i\}}$ is approximated through a function in RKHS fitted on the ordered pairs $\{ \left(Py^j, \mathbbm{1}_{\{Py^i\}}(Py^j)\right) \; \mid \; j \in \{1,\cdots,N \} \}$. This leads to the development of a kernel affine hull machine defined formally in Definition <ref>.

Given a finite number of samples: $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$ with $y^1,\cdots,y^N \in \mathbb{R}^p$ and a subspace dimension $n \leq p$; a kernel affine hull machine $\mathcal{A}_{Y,n}: \mathbb{R}^p \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N \})$ maps an arbitrary point $y \in \mathbb{R}^p$ onto the affine hull of $\{y^1,\cdots,y^N\}$ such that
𝒜_Y,n(y)     :=     h_k_θ,YP^T,λ^*^1(Py)/∑_i=1^Nh_k_θ,YP^T,λ^*^i(Py)y^1 + ⋯+ h_k_θ,YP^T,λ^*^N(Py)/∑_i=1^Nh_k_θ,YP^T,λ^*^i(Py)y^N.

* $P \in \mathbb{R}^{n \times p}\: (n \leq p)$ is an encoding matrix such that product $Py$ is a lower-dimensional encoding for $y$. For a given subspace dimension $n$, $P$ is defined by setting the $i-$th row of $P$ as equal to transpose of eigenvector corresponding to $i-$th largest eigenvalue of sample covariance matrix of dataset $\{y^1,\cdots,y^N \}$.

* $k_{\theta}: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ is a positive-definite real-valued kernel on $\mathcal{X}$ with a corresponding reproducing kernel Hilbert space $\mathcal{H}_{k_{\theta}}(\mathcal{X})$ where
𝒳     =     { Py   |  y ∈ℝ^p }.

The kernel function $k_{\theta}$ is chosen of Gaussian type:
k_θ(x^i,x^j)     :=     exp(-0.5(x^i-x^j)^Tθ^-1(x^i-x^j))

where $\theta$ is sample covariance matrix of dataset $\{Py^1,\cdots,Py^N \}$ defined as
θ     =     1/N-1P(Y - 1_N ∑_i=1^N(y^i)^T/N)^T(Y - 1_N ∑_i=1^N(y^i)^T/N)P^T.

* The function $h^i_{k_{\theta},YP^T,\lambda}: \mathcal{X} \rightarrow \mathbb{R}$, such that $h^i_{k_{\theta},YP^T,\lambda} \in \mathcal{H}_{k_{\theta}}(\mathcal{X})$, approximates the indicator function $\mathbbm{1}_{\{Py^i\}}: \mathcal{X} \rightarrow \{0,1 \}$ as the solution of following kernel regularized least squares problem:
h^i_k_θ,YP^T,λ     =       min_f ∈ℋ_k_θ(𝒳)   ( ∑_j=1^N |1_{Py^i}(Py^j) - f(Py^j) |^2 + λ f ^2_ℋ_k(𝒳) ),  λ∈ℝ_+.
The solution follows as
h^i_k_θ,YP^T,λ(·)     =     (I_N)_i,: (K_YP^T + λI_N )^-1  [[][c],c/c/c, k_θ(·,Py^1)     ⋯    k_θ(·,Py^N) ]^T

where $(I_N)_{i,:}$ denotes the $i-$th row of identity matrix of size $N$ and $K_{YP^T}$ is $N \times N$ kernel matrix with its $(i,j)-$th element defined as
(K_YP^T)_ij    :=     k_θ(Py^i,Py^j).

The value $ h^i_{k_{\theta},YP^T,\lambda}(Py)$ represents the kernel-smoothed membership of point $Py$ to the set $\{ Py^i\}$.

* The regularization parameter $\lambda^* \in \mathbb{R}_+$ is given as
λ^*     =      ê + 2/pNY ^2_F,

where $\hat{e}$ is the unique fixed point of $\mathcal{R}_{k_{\theta},YP^T,Y}$ such that
ê     =     ℛ_k_θ,YP^T,Y(ê,2/pNY ^2_F),

with $\mathcal{R}_{k_{\theta},YP^T,Y}: \mathbf{R}_{+} \times \mathbf{R}_{+} \rightarrow \mathbf{R}_{+}$ defined as
ℛ_k_θ,YP^T,Y(e,τ)    :=       1/pN ∑_j=1^p (Y)_:,j - K_YP^T (K_YP^T + (e+τ) I_N )^-1 (Y)_:,j^2.

The following iterations
e|_it+1     =     ℛ_k_θ,YP^T,Y(e|_it,2/pNY ^2_F),  it ∈{0,1,⋯}

e|_0     ∈    (0,1/pN Y ^2_F)

converge to $\hat{e}$.

* The image of $\mathcal{A}_{Y,n}$ defines a region in the affine hull of $\{y^1,\cdots,y^N\}$. That is,
𝒜_Y,n[ℝ^p]    :=     { 𝒜_Y,n(y)   |  y ∈ℝ^p  }      ⊂    aff({y^1,⋯,y^N }).

Fig. <ref> provides examples of two dimensional datasets and their corresponding KAHMs' images.

[first example] [second example] [third example]
A few examples of two dimensional data sets and regions in affine hulls defined by KAHMs' images.

The computational complexity of the KAHM is asymptotically dominated by the computation of inverse of the $N \times N$ dimensional matrix $\left(K_{YP^T} + \lambda I_N \right)$. Therefore, computational complexity of the KAHM is given as $\mathcal{O}(N^3)$.

KAHM is a bounded function as stated in Theorem <ref> in the following.

The KAHM $\mathcal{A}_{Y,n}$,  associated to $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$ with $y^1,\cdots,y^N \in \mathbb{R}^p$,  is a bounded function on $\mathbb{R}^p$ such that for any $y \in \mathbb{R}^p$,
𝒜_Y,n(y)     <     Y _2 λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )    <      Y _2(1 + pN^2/2Y_F^2 )

where $\lambda^*  \in \mathbb{R}_+$ is defined as in (<ref>) and $K_{YP^T}$ is defined as in (<ref>). Thus, the image of $\mathcal{A}_{Y,n}$ is bounded such that
𝒜_Y,n[ℝ^p]    ⊂   { y ∈ℝ^p   |    y < Y _2 λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T ) }.

The proof is provided in Appendix <ref>.

A distance function can be associated to KAHM as in Definition <ref>:

Given a KAHM $\mathcal{A}_{Y,n}$, the distance of an arbitrary point $y\in \mathbb{R}^p$ from its image under $\mathcal{A}_{Y,n}$ is given as
Γ_𝒜_Y,n(y)     :=      y - 𝒜_Y,n(y) .

A significant property of the distance function is that its value at a point can not be arbitrary large provided that the point is sufficiently close to the samples represented by KAHM. This property is being stated by Theorem <ref> in the following.

The ratio of the distance of a point $y\in \mathbb{R}^p$ from its image under $\mathcal{A}_{Y,n}$ to the distance of $y$ from $\{y^1,\cdots,y^N\}$ evaluated as $\left \|\left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y - y^1 & \cdots & y - y^N \end{IEEEeqnarraybox*} \right] \right \|_2$ remains upper bounded as
Γ_𝒜_Y,n(y) /[[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _2     <     λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )      <      1 + p N^2/2 Y_F^2

where $\lambda^*  \in \mathbb{R}_+$ is defined as in (<ref>), $K_{YP^T}$ is defined as in (<ref>), and $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$.

The proof is provided in Appendix <ref>.

Theorem <ref> signifies that if a point $y$ is close to points $\{y^1,\cdots,y^N\}$, then the value $\Gamma_{\mathcal{A}_{Y,n}}(y)$ can not be large. Thus, a large value of the distance function at a point $y$ indicates that $y$ is at far distance from $\{y^1,\cdots,y^N\}$.

§ KAHM FOR DATA REPRESENTATION LEARNING

For data representation learning, KAHM based models are introduced (in Section <ref>) and applied to the classification problem (in Section <ref>). To evaluate the risk of membership inference attack through KAHM based classifier, a membership-inference score is defined (in Section <ref>).

§.§ Wide and Conditionally Deep KAHMs

Given a finite number of samples: $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$ with $y^1,\cdots,y^N \in \mathbb{R}^p$, a subspace dimension $n \leq p$, and number of layers $L \leq n$; a conditionally deep kernel affine hull machine $\mathcal{D}_{Y,n,L}:\mathbb{R}^p \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N\})$ maps an arbitrary point $y \in \mathbb{R}^p$ onto the affine hull of $\{y^1,\cdots,y^N\}$ through a nested composition of kernel affine hull machines (as illustrated in Fig. <ref>) such that
𝒟_Y,n,L(y)     =      ℳ_Y,n,l̂(y)(y),

ℳ_Y,n,l(y)     =     (𝒜_ Y,n-l+1 ∘⋯∘𝒜_ Y,n-1 ∘𝒜_ Y,n)(y),

l̂(y)     =       min_l ∈{1,2,⋯,L }   y - ℳ_Y,n,l(y) ,

where $\mathcal{A}_{Y,\cdot}$ is a KAHM (Definition <ref>) and $\mathcal{M}_{Y,n,l}(y)$ is the image of $y$ onto the affine hull of $\{y^1,\cdots,y^N\}$ by the $l-$th layer and the output $\mathcal{D}_{Y,n,L}(y)$ is equal to the image of $y$ onto the affine hull of $\{y^1,\cdots,y^N\}$ by $\hat{l}-$th layer (which is the layer resulting in minimum Euclidean distance between input vector $y$ and its image onto the affine hull of $\{y^1,\cdots,y^N\}$). The deep KAHM discovers layers of increasingly abstract data representation with lowest-level data features being modeled by first layer and the highest-level by end layer. Fig. <ref> illustrates through an example the data representation learning at varying abstraction levels across different layers such that $\mathcal{M}_{Y,n,1}(y)$ is least abstract representation and $\mathcal{M}_{Y,n,L}(y)$ is most abstract representation of the input vector $y$.

[fill=gray!5] (0.5,-4.5) rectangle (12.5,1);
[arrows=->](0,0)–(1.5,0) node[below,pos=0]$y$;
(1.5,-0.5) rectangle (3,0.5) node[pos=0.5]$\mathcal{A}_{Y,n}$;
(7,-0.5) rectangle (8.75,0.5) node[pos=0.5]$\mathcal{A}_{Y,n-L+1}$;
[arrows=->](8.75,0)–(10.5,0) node[above, pos = 0.5]$\mathcal{M}_{Y,n,L}(y)$;
(10.5,-4.1) rectangle (12,0.5) node[pos=0.5]$\begin{array}{c}\mbox{output} \\ \mbox{layer} \end{array}$;
[arrows=->](3.5,-3)–(10.5,-3) node[above, pos = 0.875]$\mathcal{M}_{Y,n,1}(y)$;
[arrows=->](1,-3.75)–(10.5,-3.75) node[above, pos = 0.935]$y$;
[arrows=->](12,-1.8)–(13.5,-1.8) node[below, pos = 1]$\mathcal{D}_{Y,n,L}(y)$;

(5.5,-7.5) rectangle (7.5,-6.5) node[pos=0.5]$\mathcal{D}_{Y,n,L}$;

[arrows=->](4,-7)–(5.5,-7) node[left,pos=0]$y$;
[arrows=->](7.5,-7)–(8.5,-7) node[right, pos = 1]$\mathcal{D}_{Y,n,L}(y)$;

The structure of conditionally deep $L-$layered kernel affine hull machine.

A dataset $Y$ consisting of 1000 randomly chosen samples of digit 8 from MNIST dataset was considered. Corresponding to an input sample $y$ (displayed at extreme left of the figure), the outputs of different layers (i.e. $\mathcal{M}_{Y,n,1}(y), \cdots,\mathcal{M}_{Y,n,20}(y)$) have been displayed. The output of conditionally deep KAHM (i.e. $\mathcal{D}_{Y,n,20}(y)$) has been displayed at extreme right of the figure.

Given a conditionally deep KAHM $\mathcal{D}_{Y,n,L}$, the distance of an arbitrary point $y\in \mathbb{R}^p$ from its image under $\mathcal{D}_{Y,n,L}$ is given as
Γ_𝒟_Y,n,L(y)     :=      y - 𝒟_Y,n,L(y) .

The ratio of the distance of a point $y\in \mathbb{R}^p$ from its image under $\mathcal{D}_{Y,n,L}$ to the distance of $y$ from $\{y^1,\cdots,y^N\}$ evaluated as $\left \|\left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y - y^1 & \cdots & y - y^N \end{IEEEeqnarraybox*} \right] \right \|_2$ remains upper bounded as
Γ_𝒟_Y,n,L(y) /[[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _2     ≤     Γ_𝒜_Y,n(y) /[[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _2      <      1 + p N^2/2 Y_F^2

where $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$.

The proof is provided in Appendix <ref>.

For big datasets, the total data can be partitioned into subsets and corresponding to each data-subset a separate KAHM can be built to avoid computational challenges associated to big datasets. This motivates to introduce a wide condition deep KAHM in the following:

Given a big but finite number of samples: $Y = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^1 & \cdots & y^N \end{IEEEeqnarraybox*} \right]^T$ with $y^1,\cdots,y^N \in \mathbb{R}^p$, a subspace dimension $n \leq p$, number of layers $L \leq n$, and number of branches $S \leq N$; a wide conditionally deep kernel affine hull machine $\mathcal{W}_{Y,n,L,S}:\mathbb{R}^p \rightarrow \mathrm{aff}(\{y^1,\cdots,y^N\})$ maps an arbitrary point $y \in \mathbb{R}^p$ onto the affine hull of $\{y^1,\cdots,y^N\}$ through a parallel composition of conditionally deep $L-$layered kernel affine hull machines such that
𝒲_Y,n,L,S(y)     =     𝒟_Y_ŝ(y),n,L(y),

ŝ(y)     =       min_s ∈{1,2,⋯,S }   y - 𝒟_Y_s,n,L(y) ,

Y_s     =     [[][c],c/c/c, y^1,1     ⋯    y^N_s,s  ]^T

{{y^1,1,⋯,y^N_1,1},⋯, {y^1,S,⋯,y^N_S,S}}     =     clustering({y^1,⋯,y^N}, S),

where $\mathcal{D}_{Y_{\cdot},n,L}$ is the conditionally deep KAHM (Definition <ref>) and $ \mathrm{clustering}(\{y^1,\cdots,y^N\}, S)$ represents $k-$means clustering into $S$ subsets, where $S$ can be chosen e.g. as equal to rounding of $N/1000$ towards nearest integer i.e.
S     =     ⌈N/1000 ⌉.

Each of $S$ data clusters leads to a separate conditionally deep KAHM and the output $\mathcal{W}_{Y,n,L,S}(y)$ is equal to the image of $y$ onto the affine hull of $\{y^1,\cdots,y^N\}$ by $\hat{s}-$th conditionally deep KAHM (which is the KAHM resulting in minimum Euclidean distance between input vector $y$ and its image onto the affine hull of $\{y^1,\cdots,y^N\}$).

[fill=gray!5] (1,-4.5) rectangle (10.5,1);
[arrows=->](3.5,-7)–(5,-7) node[left,pos=0]$y$;
[arrows=->](7,-7)–(8,-7) node[right, pos = 1]$\mathcal{W}_{Y,n,L,S}(y)$;
(5,-7.5) rectangle (7,-6.5) node[pos=0.5]$\mathcal{W}_{Y,n,L,S}$;
[arrows=->](0,-2)–(1.5,-2) node[below,pos=0]$y$;
(5.5,-4) rectangle (7.5,-3) node[pos=0.5]$\mathcal{D}_{Y_S,n,L}$;
(5.5,-1) rectangle (7.5,0) node[pos=0.5]$\mathcal{D}_{Y_1,n,L}$;
(8.5,-4.1) rectangle (10,0.5) node[pos=0.5]$\begin{array}{c}\mbox{output} \\ \mbox{layer} \end{array}$;
[arrows=->](10,-1.8)–(11.5,-1.8) node[below, pos = 1]$\mathcal{W}_{Y,n,L,S}(y)$;

The structure of $S-$branches wide conditionally deep $L-$layered kernel affine hull machine.

Given a wide conditionally deep KAHM $\mathcal{W}_{Y,n,L,S}$, the distance of an arbitrary point $y\in \mathbb{R}^p$ from its image under $\mathcal{W}_{Y,n,L,S}$ is given as
Γ_𝒲_Y,n,L,S(y)     :=      y - 𝒲_Y,n,L,S(y) .

The ratio of the distance of a point $y\in \mathbb{R}^p$ from its image under $\mathcal{W}_{Y,n,L,S}$ to the distance of $y$ from $\{y^1,\cdots,y^N\}$ evaluated as $\left \|\left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y - y^1 & \cdots & y - y^N \end{IEEEeqnarraybox*} \right] \right \|_F$ remains upper bounded as
Γ_𝒲_Y,n,L,S(y) /[[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _F     <     min_s ∈{1,2,⋯,S }    ( 1 + p N_s^2/2 Y_s_F^2 )

where $Y_s$ is given as in (<ref>).

The proof is provided in Appendix <ref>.

§.§ Classification Applications

The KAHM induced distance function, with a property as stated in Theorem <ref>, can be leveraged to define a classifier. The significance of inequality (<ref>) is that if a data point $y \in \mathbb{R}^p$ is close to samples $\{y^1,\cdots,y^N \}$, then the value $ \Gamma_{\mathcal{W}_{Y,n,L,S}}(y)$ remains small. This allows to define a classifier, as in Definition <ref>, via modeling each class's region through a separate wide conditionally deep KAHM and assigning to a point the label of the class with the minimum distance function value.

Given a multi-class labelled dataset $\{ \left(Y_i,\mathrm{cl}^i \right) \; \mid \; Y_i = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,} y^{1,i} & \cdots & y^{N_i,i} \end{IEEEeqnarraybox*} \right]^T,\;y^{\cdot,i} \in \mathbb{R}^p,\;\mathrm{cl}^i \in \{1,2,\cdots,C \},\; i \in \{1,2,\cdots,C \} \}$, a KAHM based classifier $\mathcal{C}:\mathbb{R}^p \rightarrow \{1,2,\cdots,C \}$ is defined as
𝒞(y;𝒲_Y_1,n,L,S_1,⋯,𝒲_Y_C,n,L,S_C)     =        min_c ∈{1,2,⋯,C }    Γ_𝒲_Y_c,n,L,S_c(y),

where $\mathcal{W}_{Y_c,n,L,S_c}$ is the wide conditionally deep KAHM (Definition <ref>) modeling the $c-$th class labelled data points and $\Gamma_{\mathcal{W}_{Y_c,n,L,S_c}}(\cdot)$ is the distance function (Definition <ref>) induced by $\mathcal{W}_{Y_c,n,L,S_c}$. The classifier assigns to an arbitrary point $y \in \mathbb{R}^p$ the label of the class which has the minimum distance between $y$ and $y$'s image onto the affine hull of samples of that class.

[$Y_1$ and $\Gamma_{\mathcal{W}_{Y_1,2,5,1}}(\cdot)$] [$Y_2$ and $\Gamma_{\mathcal{W}_{Y_2,2,5,1}}(\cdot)$] [$Y_3$ and $\Gamma_{\mathcal{W}_{Y_3,2,5,1}}(\cdot)$]  [decision boundaries determined by the classifier (<ref>)]
An example of KAHM based classifier built with a 2-dimensional dataset with 3 classes. The data samples have been displayed using `+' marker and the distance function $ \Gamma_{\mathcal{W}_{Y,n,L,S}}(\cdot)$ has been displayed as color plot.

Fig. <ref> shows an example of a KAHM based classifier built with a 2-dimensional dataset with 3 classes.

The distance function can be further used to define a class-matching score as in Definition <ref>.

Given the set $\{ \mathcal{W}_{Y_c,n,L,S_c}\}_{c=1}^C$ (where $\mathcal{W}_{Y_c,n,L,S_c}$ is the wide conditionally deep KAHM (Definition <ref>) modeling the $c-$th class labelled data points), the matching-score of a point $y \in \mathbb{R}^p$ to $c-$th class is defined as
ms(y;𝒲_Y_1,n,L,S_1,⋯,𝒲_Y_C,n,L,S_C)    =     exp(-|Γ_𝒲_Y_c,n,L,S_c(y) |^2/∑_c=1^C|Γ_𝒲_Y_c,n,L,S_c(y) |^2)

where $\Gamma_{\mathcal{W}_{Y_c,n,L,S_c}}(\cdot)$ is the distance function (Definition <ref>) induced by $\mathcal{W}_{Y_c,n,L,S_c}$.

§.§ Membership-Inference Score For KAHM Based Classifier

The KAHM based classifier (Definition <ref>) is built using the training dataset,
𝐃_trn     =     {y^j,i   |  j ∈{1,2,⋯,N_i },  i ∈{1,2,⋯,C } }.

As observed in (<ref>), the classifier assigns a label to a vector $y$ based on distance function values: $\{\Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}(y)\}_{c = 1}^C$. It is obvious that a point either belonging to or lying close to points represented by matrix $Y_c$ (i.e. $\{y^{1,c},  \cdots , y^{N_c,c} \}$) will have the value of distance function $\Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ smaller than the value corresponding to a point lying away from points $\{y^{1,c},  \cdots , y^{N_c,c} \}$. So the distance function $\Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ carries an information about the membership of a point to the set of points represented by $Y_c$. Similarly, the value $\min_{c \in \{1,\cdots,C \}} \;  \Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}(y)$ carries an information about the membership of $y$ to the training dataset $\mathbf{D}_{trn}$. To evaluate the potential of function $\min_{c \in \{1,\cdots,C \}} \;  \Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ in inferring the membership of a data point to training dataset $\mathbf{D}_{trn}$, a score, referred to as “membership-inference score”, is defined. For this we define, for a given small positive number $\mathrm{o} \in \mathbb{R}_{\geq 0}$, sets $\mathbf{T}_{\mathrm{o}}, \mathbf{T}_{\mathrm{o}}^{\prime}  \subset \mathbb{R}_{\geq 0}$ as
𝐓_o     =     { y ∈ℝ^p
|   min_y^' ∈𝐃_trn  y - y^'  ≤o  },  o ∈ℝ_≥0,

𝐓_o^'     =     { y ∈ℝ^p
|   min_y^' ∈𝐃_trn  y - y^'  > o  },  o ∈ℝ_≥0.

Further define two non-negative functions, $\mathbf{r}_{\mathrm{o}}:\mathbf{T}_{\mathrm{o}} \rightarrow \mathbb{R}_{\geq 0}$ and $\mathbf{r}_{\mathrm{o}}^{\prime}:\mathbf{T}_{\mathrm{o}}^{\prime} \rightarrow \mathbb{R}_{\geq 0}$, as
𝐫_o(y)     =     min_c ∈{1,2,⋯,C }    Γ_𝒲_Y_c,n,L,S_c(y),  y ∈𝐓_o,

𝐫_o^'(y^')     =     min_c ∈{1,2,⋯,C }    Γ_𝒲_Y_c,n,L,S_c(y^'),  y^' ∈𝐓_o^'.

Let $f_{\mathbf{r}_{\mathrm{o}}}$ and $f_{ \mathbf{r}_{\mathrm{o}}^{\prime}}$ denote the densities of probability distributions on $\mathbf{r}_{\mathrm{o}}$ and $ \mathbf{r}_{\mathrm{o}}^{\prime}$ respectively. It is obvious that $f_{\mathbf{r}_{\mathrm{o}}}$ characterizes the distribution of values taken by the function $\min_{c \in \{1,2,\cdots,C \}} \;  \Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ over data points lying within the distance of $\mathrm{o}$ from any data point included in the set $\mathbf{D}_{trn}$. Similarly, $f_{ \mathbf{r}_{\mathrm{o}}^{\prime}}$ characterizes the distribution of values taken by the function $\min_{c \in \{1,2,\cdots,C \}} \;  \Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ over data points lying away from the training dataset. Thus, the difference between $f_{\mathbf{r}_{\mathrm{o}}}$ and $f_{ \mathbf{r}_{\mathrm{o}}^{\prime}}$ is a measure of the potential of function $\min_{c \in \{1,\cdots,C \}} \;  \Gamma_{\mathcal{W}_{Y_c,\cdot,\cdot,\cdot}}$ in inferring the membership of a datapoint to training dataset $\mathbf{D}_{trn}$. Hence, the membership-inference score is defined as the $L2$ distance between $f_{\mathbf{r}_{\mathrm{o}}}$ and $f_{ \mathbf{r}_{\mathrm{o}}^{\prime}}$:
mis     :=     ∫(f_𝐫_o(r) - f_ 𝐫_o^'(r))^2 r   .

Taking $\mathrm{o} = 0$, training dataset $\mathbf{D}_{trn}$ can be used to generate samples from $f_{\mathbf{r}_{0}}$, i.e., $\{ \mathbf{r}_{0}(y) \; \mid \; y \in \mathbf{D}_{trn} \}$ is the set of samples generated from $f_{\mathbf{r}_{0}}$. Similarly, test dataset (which is typically used to evaluate the classifier's performance), $\mathbf{D}_{tst}$, can be used to generate samples from $f_{\mathbf{r}_{0}}^{\prime}$, i.e., $\{ \mathbf{r}_{0}^{\prime}(y^{\prime}) \; \mid \; y^{\prime} \in \mathbf{D}_{tst} \}$ is the set of samples generated from $f_{\mathbf{r}_{0}}^{\prime}$. Now, the membership-inference score can be computed by approximating the $L2$ distance between $f_{\mathbf{r}_{0}}$ and $f_{ \mathbf{r}_{0}^{\prime}}$ from the samples $\{ \mathbf{r}_{0}(y) \; \mid \; y \in \mathbf{D}_{trn} \}$ and $\{ \mathbf{r}_{0}^{\prime}(y^{\prime}) \; \mid \; y^{\prime} \in \mathbf{D}_{tst} \}$ using a density-difference estimation method [Sugiyama et al., 2013].

§ PRIVACY-PRESERVING LEARNING

Assuming that training dataset is private, KAHM based classification problem is considered under differential privacy framework. For this, an optimal differentially private noise adding mechanism is reviewed (in Section <ref>) and a novel differentially private data fabrication method is developed for classification applications (in Section <ref>). The application of KAHM to differentially private federated learning is considered (in Section <ref>).

§.§ An Optimal $(\epsilon,\delta)-$Differentially Private Noise Adding Mechanism

A given computational algorithm, operating on a data matrix $Y \in \mathbb{R}^{N \times p}$, can be represented by a mapping, $alg: \mathbb{R}^{N \times p} \rightarrow Range(alg)$. The privacy of data matrix $Y$ can be preserved via adding a suitable random noise to $Y$ before the application of algorithm $alg$ on the data matrix. This will result in a private version of algorithm $alg$ which is formally defined by Definition <ref>.

Given a computational algorithm $alg: \mathbb{R}^{N \times p} \rightarrow Range(alg)$, a private version of $alg$, $alg^+ : \mathbb{R}^{N \times p} \rightarrow Range(alg^+)$, is defined as
alg^+(Y)     :=     alg(Y^+ ),

Y^+     =     Y + V,   V ∈ℝ^N ×p,

where $\mathrm{V}$ is a random noise matrix with $f_{\mathrm{v}_j^i}(v)$ being the probability density function of its $(i,j)-$th element $\mathrm{v}_j^i$; $\mathrm{v}_j^i$ and $\mathrm{v}_j^{i^{\prime}}$ are independent from each other for $i \neq i^{\prime}$; and $alg: \mathbb{R}^{N \times p} \rightarrow Range(alg)$ is a given mapping representing a computational algorithm. The range of $alg^+$ is as
Range(alg^+)     =     { alg(Y + V)  |    Y ∈ℝ^N ×p, V ∈ℝ^N ×p }.

We consider a threat scenario that an adversary seeks to gain an information about the data matrix $Y$ from an analysis of the change in output of algorithm $alg$ as a result of a change in data matrix. In particularly, we seek to attain differential privacy for algorithm $alg^+$ against the perturbation in an element of $Y$, say $(i_0,j_0)-$th element, such that magnitude of the perturbation is upper bounded by a scalar $d$.

Two matrices $Y,Y^{\prime} \in \mathbb{R}^{N \times p}$ are $d-$adjacent if for a given $d  \in \mathbb{R}_{+}$, there exist $i_0 \in \{1,2,\cdots,N\}$ and $j_0 \in \{1,2,\cdots,p\}$ such that $\forall i \in \{1,2,\cdots,N\},\; j \in \{1,2,\cdots,p\}$,
| (Y)_i,j - (Y^')_i,j |     ≤    {

where $(Y)_{i,j}$ and $(Y^{\prime})_{i,j} $ denote the $(i,j)-$th element of $Y$ and $Y^{\prime}$ respectively. Thus, $Y$ and $Y^{\prime}$ differ by only one element and the magnitude of the difference is upper bounded by $d$.

The algorithm $alg^+\left(Y\right)$ is $(\epsilon,\delta)-$differentially private if
Pr{ alg^+(Y) ∈𝒪 }     ≤    exp(ϵ) Pr{ alg^+(Y^')) ∈𝒪 } + δ
for any measurable set $\mathcal{O} \subseteq  Range(alg^+) $ and for $d-$adjacent matrices pair $(Y,Y^{\prime})$.

Definition <ref> implies that changing the value of an element in the matrix $Y$ by an amount upper bounded by $d$ can change the distribution of output of the algorithm $alg^+$ only by a factor of $\exp(\epsilon)$ with probability at least $1-\delta$. Thus, the lower value of $\epsilon$ and $\delta$ lead to a higher amount of privacy.
[An Optimal $(\epsilon,\delta)-$Differentially Private Noise [Kumar et al., 2019]]
The probability density function of noise, that minimizes the expected noise magnitude together with satisfying the sufficient conditions for $(\epsilon,\delta)-$differential privacy for $alg^+$, is given as
f_v_j^i^*(v;ϵ,δ,d)      =     {  δ  Diracδ(v),     v = 0

(1- δ)ϵ/2 d exp(-ϵ/d |v|),     v ∈ℝ ∖{0}

where $Dirac\delta(v)$ is Dirac delta function satisfying $\int_{-\infty}^{\infty}Dirac\delta(v)\: \dd v = 1$.

The method of inverse transform sampling can be used to generate random samples from cumulative distribution function. The cumulative distribution function of $  f_{\mathrm{v}_j^i}^*$ is given as
F_v_j^i(v;ϵ,δ,d)     =     {  1-δ/  2 exp(ϵ/d v),     v < 0

1 + δ/  2,      v = 0

1 -  1 - δ/  2exp(-ϵ/d v),     v > 0

The inverse cumulative distribution function is given as
F_v_j^i^-1(t^i_j;ϵ,δ,d)     =     { d/ϵ log(2t^i_j/1 - δ),     t^i_j <  1- δ/2

0,      t^i_j ∈[ 1- δ/2, 1+ δ/2]

-d/ϵ log(2(1-t^i_j)/1-δ),     t^i_j > 1+δ/2
.,  t^i_j ∈(0,1).

Thus, via generating random samples from the uniform distribution on $(0,1)$ and using (<ref>), the noise additive mechanism can be implemented.

Differentially private approximation of a data matrix [Kumar, 2023]

[1]
Data matrix $Y \in \mathbb{R}^{N \times p}$; differential privacy parameters: $d  \in \mathbb{R}_{+}$,  $\epsilon  \in \mathbb{R}_{+}$, $\delta \in (0,1)$.
Compute $\forall \; i \in \{1,2,\cdots,N\},\; j \in \{1,2,\cdots,p\}$,
(Y^+_ϵ)_i,j      =     (Y)_i,j+ F_v_j^i^-1(t^i_j;ϵ,δ,d),  t^i_j ∈(0,1),

where $t^{i}_j $ is chosen from the uniform distribution on $(0,1)$ and $ F_{\mathrm{v}_j^{i}}^{-1}$ is given by (<ref>).
$Y^+_{\epsilon}$ (where the subscript $\epsilon$ indicates the given privacy-loss bound $\epsilon$).

For a given value of $(\epsilon,\delta,d)$, Algorithm <ref> is stated for the differentially private approximation of a data matrix.

§.§ Differentially Private Data Fabrication and Classification

A computational algorithm can be made to ensure differential privacy (i.e. inequality (<ref>)) via applying the algorithm on the data matrix returned by Algorithm <ref>. Hence, a KAHM based differentially private classifier can be built as in Definition <ref>.

Given a multi-class labelled differentially private dataset $\{ (Y_{\epsilon, i}^+,\mathrm{cl}^i ) \; \mid \; Y_{\epsilon,i}^+ \in \mathbb{R}^{N_i \times p},\;\mathrm{cl}^i \in \{1,2,\cdots,C \} \}$, a KAHM based differentially private classifier $\mathcal{C}:\mathbb{R}^p \rightarrow \{1,2,\cdots,C \}$ is defined as
𝒞(y;𝒲_Y_ϵ,1^+,n,L,S_1,⋯,𝒲_Y_ϵ,C^+,n,L,S_C)     =        min_c ∈{1,2,⋯,C }    Γ_𝒲_Y_ϵ,c^+,n,L,S_c(y),

where $\mathcal{W}_{Y_{\epsilon,c}^+,\cdot,\cdot,\cdot}$ is the wide conditionally deep KAHM (Definition <ref>) modeling the $c-$th class labelled data points and $\Gamma_{\mathcal{W}_{Y_{\epsilon,c}^+,\cdot,\cdot,\cdot}}(\cdot)$ is the distance function (Definition <ref>) induced by $\mathcal{W}_{Y_{\epsilon,c}^+,\cdot,\cdot,\cdot}$, and $Y_{\epsilon,c}^+$ is differentially private data matrix obtained by Algorithm <ref>. The classifier assigns to an arbitrary point $y \in \mathbb{R}^p$ the label of the class which has the minimum distance between $y$ and $y$'s image onto the affine hull of differentially private samples of that class.

Since a differentially private algorithm operates on noise added data, the algorithm's performance is adversely affected. An obvious effect of adding noise to data matrix is an increase in the modeling error of data samples by a KAHM. Typically, we have
∑_i=1^N y^+i_ϵ -  𝒜_Y^+_ϵ,n(y^+i_ϵ)     >     ∑_i=1^N y^i -  𝒜_Y,n(y^i)  ,

where $y^{+i}_{\epsilon} = ((Y^+_{\epsilon})_{i,:})^T$. Thus, an approach to alleviate the effect of added noise on the performance of a KAHM based algorithm is of processing the noise added data matrix through a data smoother such that the smoothed data matrix leads to a KAHM with modeling error not larger than the modeling error on original data samples. One such smoother is defined as in Definition <ref>.

Given a differentially private matrix $Y^+_{\epsilon}  \in \mathbb{R}^{N \times p}$, a subspace dimension $n \leq p$, and a positive integer $M \in \mathbb{Z}_+$; $Y^+_{\epsilon}$ is transformed into $\hat{Y}_{M-1} \in \mathbb{R}^{N \times p}$ through following recursions run from $m=0$ to $m = M-1$:
ŷ^i,0     =     ((Y^+_ϵ)_i,:)^T,  ∀i ∈{1,2,⋯,N },

ŷ^i,m+1     =      (∑_j=1^Nh_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^i,m) ) ×𝒜_Ŷ_m,n(ŷ^i,m ),

Ŷ_m     =     [[][c],c/c/c,  ŷ^1,m      ⋯    ŷ^N,m   ]^T,

* $P_m$ is defined by setting the $i-$th row of $P_m$ as equal to transpose of eigenvector corresponding to $i-$th largest eigenvalue of sample covariance matrix of dataset $\{\hat{y}^{1,m},\cdots,\hat{y}^{N,m} \}$.

* $\theta_m$ is sample covariance matrix of dataset $\{P_m\hat{y}^{1,m},\cdots,P_m\hat{y}^{N,m} \}$, i.e.,
θ_m      =     1/N-1_mP_m(Ŷ_m - 1_N ∑_i=1^N(ŷ^i,m)^T/N)^T(Ŷ_m - 1_N ∑_i=1^N(ŷ^i,m)^T/N)P_m^T.

* $\lambda^*_m \in \mathbb{R}_+$ is given as
λ^*_m     =      ê_m + 2/pNŶ_m ^2_F,

where $\hat{e}_m$ is the unique fixed point of the function $\mathcal{R}_{k_{\theta_m},\hat{Y}_mP_m^T,\hat{Y}_m}$ (which is defined as in (<ref>)).

* $k_{\theta_m}(\cdot,\cdot)$ and $h_{k_{\theta_m},\hat{Y}_mP^T_m,\lambda^*_m}^i(\cdot)$ are defined as in (<ref>) and (<ref>) respectively.

The transformation of $Y^+_{\epsilon}$ into $\hat{Y}_{M-1} $ is represented as
Ŷ_M-1     =       T_n,M(Y^+_ϵ).

The transformation of $Y^+_{\epsilon}$ into $\hat{Y}_{M-1}$ has been defined in a particular way to ensure a property related to the error in KAHM modeling of data samples. This property is sated in Theorem <ref>.

The error in KAHM modeling of smoothed data matrix $\hat{Y}_{M-1}  =    \mathrm{T}_{n,M}(Y^+_{\epsilon})$ converges asymptotically with an increasing value of $M$ to zero, i.e.,
lim_M →∞ ∑_i=1^N  ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)       =     0.

where $\hat{Y}_{M-1} = \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c,}  \hat{y}^{1,M-1}  & \cdots & \hat{y}^{N,M-1}  \end{IEEEeqnarraybox*} \right]^T$ is computed using recursions (<ref>-<ref>) from $m=0$ to $m = M-1$.

The proof is provided in Appendix <ref>.

It follows from Theorem <ref> that the KAHM modeling error of smoothed data samples can be reduced to an arbitrary low value by choosing a sufficiently large value of $M$. Thus, it is possible to find the smallest number, say $\tilde{M} \in \mathbb{Z}_+$, ensuring that
∑_i=1^N  ŷ^i,M̃-1 - 𝒜_Ŷ_M̃-1,n(ŷ^i,M̃-1)      ≤    r,

where $r$ is the error in KAHM modeling of original data matrix $Y$ defined as
r     =     ∑_i=1^N y^i - 𝒜_Y,n(y^i) .

That is, error in KAHM modeling of smoothed data matrix $\hat{Y}_{\tilde{M}-1}$ is lower than the error in KAHM modeling of original data matrix $Y$, which suggests that applying a KAHM based computational algorithm on $\hat{Y}_{\tilde{M}-1}$ (instead of $Y^+_{\epsilon}$) may alleviate the effect of added noise on the performance of a KAHM based computational algorithm. This motivates to use the KAHM associated to $\hat{Y}_{\tilde{M}-1}$, i.e. $\mathcal{A}_{\hat{Y}_{\tilde{M}-1},n}$, for fabricating data samples meant for building KAHM based models.

Given a differentially private matrix $Y^+_{\epsilon}  \in \mathbb{R}^{N \times p}$ ensuring the privacy-loss bound $\epsilon \in \mathbb{R}_+$, a subspace dimension $n \leq p$, and error in KAHM modeling of original data matrix $Y$ evaluated as $r = \sum_{i=1}^N  \|y^i - \mathcal{A}_{Y,n}(y^i) \|$; a differentially private fabricated data matrix $\tilde{Y} \in \mathbb{R}^{N \times p}$ is defined as
Ỹ      =     [[][c],c/c/c, 𝒜_Ŷ_M̃-1,n( ŷ^1,M̃-1)      ⋯    𝒜_Ŷ_M̃-1,n( ŷ^N,M̃-1)    ]^T,

ŷ^i,M̃-1     =     ( (Ŷ_M̃-1)_i,:)^T,

Ŷ_M̃-1     =     T_n,M̃(Y^+_ϵ),

where smoother $\mathrm{T}_{n,\tilde{M}}$ (Definition <ref>) computes $ \hat{Y}_{\tilde{M}-1}$ through recursions (<ref>-<ref>) from $m= 0$ to $m = \tilde{M}-1$, and $\tilde{M}$ is defined as
M̃    =    min{ m ∈ℤ_+  |   ∑_i=1^N  ŷ^i,m-1 - 𝒜_Ŷ_m-1,n(ŷ^i,m-1)  ≤r   }.
The computing of $\tilde{Y}$ is represented as
Ỹ     =     ℱ_n(Y^+_ϵ;r).

The fabricated data matrix $\tilde{Y}$ is computed from $Y^+_{\epsilon}$ (which is a differentially private approximation of $Y$) and not from original data matrix $Y$, and thus $\tilde{Y}$ remains differentially private.

A dataset $Y$ consisting of 1000 randomly chosen samples of digit 8 from MNIST dataset was considered. For 10 randomly selected samples from $Y$ (displayed at top row of the figure), the corresponding samples from differentially private fabricated data $\tilde{Y} = \mathcal{F}_{n}(Y^+_{\epsilon};\sum_{i=1}^{1000} \|y^i - \mathcal{A}_{Y,n}(y^i) \|)$ have been displayed for different values of privacy-loss bound $\epsilon$ and subspace dimension $n$.

Fig. <ref> displays a few examples of fabricated data samples corresponding to different choices for privacy-loss bound $\epsilon$ and subspace dimension $n$. As expected and also observed in Fig. <ref>, more and more features of original data samples get masked in the fabricated data with a decrease in $\epsilon$ and/or $n$.

For the big datasets with large $N$, the data can be divided into subsets via e.g. k-means clustering and fabricated data matrix is computed from each subset independently. That is, $\tilde{Y}$ is fabricated as follows:
Ỹ     =      [[][c],c/c/c, (ℱ_n(Y_1^+;r_1))^T      ⋯    (ℱ_n(Y_S^+;r_S))^T    ]^T,

Y_s^+     ←    Algorithm <ref>(Y_s,d,ϵ,δ),

r_s     =     ∑_i=1^N_s  y^i,s - 𝒜_Y_s,n(y^i,s) ,

Y_s     =     [[][c],c/c/c, y^1,1     ⋯    y^N_s,s  ]^T,

{y^1,s,⋯,y^N_s,s}_s=1^S     =     clustering({y^1,⋯,y^N}, S),

S     =     ⌈N/1000 ⌉,

where $ \mathrm{clustering}(\{y^1,\cdots,y^N\}, S)$ represents $k-$means clustering into $S$ subsets

As the fabricated data remain differentially private, a KAHM based classifier can be built using fabricated data to ensure differential privacy in the sense of inequality (<ref>).

Given a multi-class labelled differentially private fabricated dataset $\{ (\tilde{Y}_i,\mathrm{cl}^i ) \; \mid \; \tilde{Y}_i \in \mathbb{R}^{N_i \times p},\;\mathrm{cl}^i \in \{1,2,\cdots,C \} \}$, a classifier $\mathcal{C}:\mathbb{R}^p \rightarrow \{1,2,\cdots,C \}$ is defined as
𝒞(y;𝒲_Ỹ_1,n,L,S_1,⋯,𝒲_Ỹ_C,n,L,S_C)     =        min_c ∈{1,2,⋯,C }    Γ_𝒲_Ỹ_c,n,L,S_c(y),

where $\mathcal{W}_{\tilde{Y}_c,\cdot,\cdot,\cdot}$ is the wide conditionally deep KAHM (Definition <ref>) modeling the $c-$th class labelled data points and $\Gamma_{\mathcal{W}_{\tilde{Y}_c,\cdot,\cdot,\cdot}}(\cdot)$ is the distance function (Definition <ref>) induced by $\mathcal{W}_{\tilde{Y}_c,\cdot,\cdot,\cdot}$, and $\tilde{Y}_c$ is differentially private fabricated data matrix (Definition <ref>). The classifier assigns to an arbitrary point $y \in \mathbb{R}^p$ the label of the class which has the minimum distance between $y$ and $y$'s image onto the affine hull of differentially private fabricated samples of that class.

§.§ Application to Differentially Private Federated Learning

[images of three different KAHMs built independently using three different datasets] [image of the global KAHM combining together KAHMs built independently using three different datasets]
An example of combining three different KAHMs together to build a global KAHM.

[green,line width = 0.25mm](-3,-8.25)–(3,-8.25)–(3,1.5)–(-3,1.5)–cycle;
(0,-7.75) node[]$\begin{array}{c} \mbox{\scriptsize Party 1} \end{array}$;
(0,-6.25) node[rounded corners,draw=red,fill=red!5](n1)$\begin{array}{c}\mbox{local training data} \\ \mbox{to be protected} \\ \mbox{\small $\{ Y^1_1,\cdots, Y^1_C \}$} \end{array}$;
(0,-4) node[rounded corners,draw](nadd1)$\begin{array}{c}\mbox{differentially private} \\ \mbox{fabricated data} \\ \mbox{\small $\{ \tilde{Y}^1_1,\cdots, \tilde{Y}^1_C \}$}\end{array}$;
[-latex,line width=0.2mm] (n1) to [out=90,in=-90] (nadd1);
(0,-1.9) node[rounded corners,draw](n2) $\begin{array}{c}\mbox{local models} \\ \mbox{\small  $ \{ \mathcal{W}_{\tilde{Y}_1^1,n,L,S_1^1},\cdots, \mathcal{W}_{\tilde{Y}_C^1,n,L,S_C^1} \}$} \end{array}$;
[-latex,line width=0.2mm] (nadd1) to [out=90,in=-90] (n2);
(0,0.05) node[rounded corners,draw](n4) $\begin{array}{c}\mbox{inference} \\ \mbox{\small $\{  \Gamma_{\mathcal{W}_{\tilde{Y}_c^1,n,L,S_c^1}}(y) \}_{c=1}^C$} \end{array}$;
[-latex,line width=0.2mm] (n2) to [out=90,in=-90] (n4);
[yellow,line width = 0.25mm](9,-8.25)–(15,-8.25)–(15,1.5)–(9,1.5)–cycle;
(11.75,-7.75) node[]$\begin{array}{c} \mbox{\scriptsize Party Q} \end{array}$;
(12,0.05) node[rounded corners,draw](n11) $\begin{array}{c}\mbox{inference} \\ \mbox{\small $\{  \Gamma_{\mathcal{W}_{\tilde{Y}_c^Q,n,L,S_c^Q}}(y) \}_{c=1}^C$} \end{array}$;
(12,-1.9) node[rounded corners,draw](n14) $\begin{array}{c}\mbox{local models} \\ \mbox{\small $ \{ \mathcal{W}_{\tilde{Y}_1^Q,n,L,S_1^Q},\cdots, \mathcal{W}_{\tilde{Y}_C^Q,n,L,S_C^Q} \}$} \end{array}$;
[-latex,line width=0.2mm] (n14) to [out=90,in=-90] (n11);
(12,-4) node[rounded corners,draw](nadd2)$\begin{array}{c}\mbox{differentially private} \\ \mbox{fabricated data} \\ \mbox{\small $\{ \tilde{Y}^Q_1,\cdots, \tilde{Y}^Q_C \}$}\end{array}$;
[-latex,line width=0.2mm] (nadd2) to [out=90,in=-90] (n14);
(12,-6.25) node[rounded corners,draw=red,fill= red!5](n15)$\begin{array}{c}\mbox{local training data} \\ \mbox{to be protected} \\ \mbox{\small $\{ Y^Q_1,\cdots, Y^Q_C \}$} \end{array}$;
[-latex,line width=0.2mm] (n15) to [out=90,in=-90] (nadd2);
[blue!40,line width = 0.25mm](4,-8.25)–(8,-8.25)–(8,1.5)–(4,1.5)–cycle;
(6,-7.75) node[]$\begin{array}{c} \mbox{\scriptsize User} \end{array}$;
(6,-3.5) node[](n20) $\begin{array}{c}\mbox{input} \\ \mbox{\small $y$} \end{array}$;
[thick,line width=0.2mm](n20) – (6,-2.5);
[thick,line width=0.2mm](3.5,-2.5) – (8.5,-2.5);
[-latex,thick,line width=0.2mm] (3.5,-2.5) to [out=90,in=0] (n4);
[-latex,thick,line width=0.2mm] (8.5,-2.5) to [out=90,in=180] (n11);
draw = gray,
fill = cyan!5,
minimum width = 11cm,
minimum height = 3.5cm,
cloud puffs = 18] (c) at (6,4) ;
(6,3.85) node[rounded corners,draw, fill=gray!5](n8) $\begin{array}{c} \mbox{\small $ \arg \; \min_{c \in \{1,2,\cdots,C \}}\; \left( \min_{q \in \{1,2,\cdots,Q \}}\;\Gamma_{ \mathcal{W}_{\tilde{Y}^q_c,n,L,S^q_c}}(y) \right)$}  \end{array}$;
[-latex,line width=0.2mm,cyan] (n4) to [out=90,in=180] (n8);
(6,4.8) node[]$\begin{array}{c} \mbox{global aggregator} \end{array}$  ;
[-latex,line width=0.2mm,cyan] (n11) to [out=90,in=0] (n8);
(6,0.5) node[rounded corners,draw, fill = gray!5](n17) $\begin{array}{c}\mbox{output} \\ \mbox{\small $\mathcal{GC}(y) $} \end{array}$;
[-latex,line width=0.2mm,cyan] (n8) to [out=-90,in=90] (n17);

The structural representation of the KAHM based differentially private federated learning scheme.

The multi-class classification problem is considered under the scenario of data being distributed amongst different parties. For the case of data being privately owned by local parties, our federated learning approach is of combining together the local privacy-preserving KAHM based classifiers using the distance functions induced by local KAHMs. For this, a combination of different KAHMs is considered using the distance measure. Given $Q$ different wide conditionally deep KAHMs $\mathcal{W}_{Y^1,n,L,S^1},\cdots,\mathcal{W}_{Y^Q,n,L,S^Q}$ built independently using datasets $Y^1,\cdots,Y^Q$ respectively, a possible way to combine together the KAHMs is as follows:
𝒢𝒲(y;{ 𝒲_Y^q,n,L,S^q}_q=1^Q)     =     𝒲_Y^q̂(y),n,L,S^q̂(y)(y),

q̂(y)     =       min_q ∈{1,2,⋯,Q } Γ_ 𝒲_Y^q,n,L,S^q(y),

where $\mathcal{GW}$ is the global KAHM (that combines together the individual KAHMs) and $\Gamma_{\mathcal{W}_{Y^q,n,L,S^q}}$ is the distance function (Definition <ref>) induced by $\mathcal{W}_{Y^q,n,L,S^q}$. For an input $y \in \mathbb{R}^p$, the global KAHM output is equal to the output of $\hat{q}-$th KAHM (which is the KAHM resulting in minimum Euclidean distance between input vector $y$ and its image onto the affine hull of data samples). A 2-dimensional data example where three different KAHMs are combined to build a global KAHM is provided in Fig. <ref>. Fig. <ref> shows the images of individual KAHMs (in Fig. <ref>) and the image of global KAHM (in Fig. <ref>).

The local KAHMs modeling a specific class can be combined together to build a global KAHM (that models the region (in data space) of that class) and a global classifier can be built from all class-specific global KAHMs. Mathematically, the global classifier, $\mathcal{GC}:\mathbb{R}^p \rightarrow \{1,2,\cdots,C \}$, is defined as
𝒢𝒞(y)     =        min_c ∈{1,2,⋯,C }  y - 𝒢𝒲(y;{ 𝒲_Ỹ^q_c,n,L,S^q_c}_q=1^Q)  ,

where $\tilde{Y}_c^q$ represents the $c-$th class labelled differentially private data samples fabricated locally by the $q-$th party and $\mathcal{GW}$ is the global KAHM (<ref>). The global classifier (<ref>) assigns to an arbitrary point $y \in \mathbb{R}^p$ the label of the class which has the minimum distance between $y$ and $y$'s image onto the affine hull of differentially private fabricated samples of that class. (<ref>) can be alternatively expressed as
𝒢𝒞(y)     =        min_c ∈{1,2,⋯,C }  ( min_q ∈{1,2,⋯,Q } Γ_ 𝒲_Ỹ^q_c,n,L,S^q_c(y) ).

An important feature of the global classifier evaluation using (<ref>) is that the evaluation doesn't require individual KAHMs (that are owned by different parties) but only the distance measures. This allows to design a KAHM based differentially private federated learning scheme as illustrated in Fig. <ref>.

If the $q-$th party has zero $c-$th labelled data samples, the global classifier (<ref>) is evaluated taking $\Gamma_{ \mathcal{W}_{\tilde{Y}^q_c,n,L,S^q_c}}(y) = \infty$.

§ EXPERIMENTS

The aim of the experiments is to

* investigate the performance of KAHM based classifier (in Section <ref>);

* evaluate the proposed privacy-preserving learning method in-terms of both accuracy and risk of membership inference attack (in Section <ref>);

* investigate the performance of the proposed differentially private federated learning scheme (in Section <ref>); and

* study the computational time of KAHM in relation to increasing data dimension, subspace dimension, and data sample size (in Section <ref>).

§.§ KAHM Based Classification of High-Dimensional Feature Vectors

The “Freiburg Groceries Dataset” [Jund et al., 2016] is considered to evaluate the performance of KAHM based classifier (Definition <ref>). This dataset has around 5000 labeled images of grocery products commonly sold in Germany. The images have been divided into 25 different categories of grocery products. A few samples of the dataset have been displayed in Fig. <ref>.

A few samples of Freiburg groceries dataset [Jund et al., 2016]

Following the previous studies [Kumar and Freudenthaler, 2020, Kumar et al., 2021] on this dataset, image features were extracted from “AlexNet” and “VGG-16” networks (which are pre-trained Convolutional Neural Networks). The activations of the fully connected layer “fc6” in AlexNet constitute a $4096-$dimensional feature vector. Also, the activations of the fully connected layer “fc6” in VGG-16 constitute another $4096-$dimensional feature vector. The features extracted by both networks were joined together to form a $8192-$dimensional vector. The feature vectors were scaled along each dimension to lie their values between -1 and 1.

Experiments on 5 different train-test splits of Freiburg groceries data: I

2*methods     6caccuracy (in %) on test images

1       2       3       4       5      mean

KAHM Classifier (Definition <ref>)     89.29     87.16     87.00     86.73     87.09     87.46
$\begin{array}{c} \mbox{membership-mappings} \\ \mbox{[Kumar et~al., 2021]} \end{array}$     87.82     87.06      85.88      85.63     86.19     86.52
$\begin{array}{c} \mbox{nonparametric fuzzy} \\ \mbox{image mapping}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     88.21     86.64      85.36      85.13     85.79       86.23
$\begin{array}{c} \mbox{Gaussian fuzzy-mapping} \\ \mbox{[Kumar et~al., 2021]} \end{array}$     83.50      81.52      79.73      79.60      80.48      80.97
SVM [Kumar et al., 2021]     77.90       79.54        77.17        76.98         76.98     77.71
$1$-NN [Kumar et al., 2021]     78.00       77.97        77.38        76.58        76.28     77.24
$\begin{array}{c} \mbox{Back-propagation} \\ \mbox{training of a deep network} \\ \mbox{[Kumar et~al., 2021]} \end{array}$     75.25     77.24     72.67      73.37     71.57     74.02
$2$-NN [Kumar et al., 2021]     73.48      73.38      70.11      70.05      70.57     71.52
$4$-NN [Kumar et al., 2021]     72.50     73.39      68.89      71.16      70.87     71.36
Random Forest [Kumar et al., 2021]      63.17     62.63     59.47     59.50      59.76     60.90
Naive Bayes [Kumar et al., 2021]     56.78      56.78          53.74       55.08         56.26     55.73
Ensemble Learning [Kumar et al., 2021]     38.31      39.35     38.89       37.69        38.34     38.51
Decision Tree [Kumar et al., 2021]     31.34       30.59        32.14        31.06        30.73     31.17

Experiments on 5 different train-test splits of Freiburg groceries data: II

2*methods     5carea under ROC curve (averaged per class)

1      2       3       4       5

KAHM (Definition <ref>)     0.9901       0.9925       0.9970       0.9969       0.9945
$\begin{array}{c} \mbox{nonparametric fuzzy} \\ \mbox{image mapping}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.9818       0.9775        0.9754     0.9767     0.9761
$\begin{array}{c} \mbox{deep fuzzy nonparametric} \\ \mbox{model [Zhang et~al., 2022]} \end{array}$     0.9612     0.9574     0.9601     0.9582     0.9531
$\begin{array}{c} \mbox{SVM}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.9806        0.9766         0.9711         0.9777     0.9760
$\begin{array}{c} \mbox{Random Forest}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.9489      0.9510       0.9372       0.9437       0.9466
$\begin{array}{c} \mbox{$4$-NN}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.9425      0.9336       0.9325       0.9378       0.9280
$\begin{array}{c} \mbox{$2$-NN}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.9219        0.9125       0.9118       0.9117       0.9048
$\begin{array}{c} \mbox{Naive Bayes}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.8999      0.9100       0.8866       0.9013       0.8908
$\begin{array}{c} \mbox{$1$-NN}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.8881        0.8802         0.8803         0.8837        0.8752
$\begin{array}{c} \mbox{Ensemble Learning}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.8856      0.8896       0.8813       0.8818       0.8776
$\begin{array}{c} \mbox{Decision Tree}\\ \mbox{[Kumar and Freudenthaler, 2020]} \end{array}$     0.6591      0.6473       0.6528       0.6539       0.6443

The authors of [Jund et al., 2016] provide five different train-test splits of images to evaluate the classification performance. For each of the five train-test data splits, training feature vectors of each class are modeled through a separate wide conditionally deep KAHM taking subspace dimension $n = 20$, number of layers $L = 5$, and number of branches $S$ as given in (<ref>). The performance of the proposed KAHM based classifier is compared in Table <ref> with previous studies on this dataset. A related application is of detecting the presence of an individual grocery category in an image based on the value of KAHM based class-matching score (i.e. Definition <ref>). To study the application potential of proposed class-matching score, the receiver operating characteristic (ROC) curves are plotted for test images taking a particular image category as positive class. Table <ref> reports the performances of different methods evaluated in-term of area under ROC curve.

The best performance of the KAHM based classifier on each of the five train-test data splits is observed in Table <ref> and Table <ref>. The proposed KAHM based classifier is more competitive than the previously studied methods on this dataset.

§.§ KAHM Based Differentially Private Classification with Fabricated Data

The proposed KAHM based approach to privacy-preserving classification is studied on different datasets where the performance of the classifier is evaluated in-terms of both accuracy on test data and the value of membership-inference score. The membership-inference score, $mis$ (<ref>), is computed using a density-difference estimation method [Sugiyama et al., 2013].

§.§.§ MNIST Dataset

[comparison of accuracies]  [comparison of $mis$ values]
A comparison between fabricated data based classifier with the classifier without using fabricated data.

[histograms of distances of training and test data points from the affine hull of training samples]  [histograms of distances of training and test data points from the affine hull of fabricated samples]
An illustration of the reduction in $mis$ value through data fabrication on MNIST dataset.

A handwritten digits recognition problem is considered with the widely used MNIST dataset. The dataset contains $28 \times 28$ sized images divided into training set of 60000 images and testing set of 10000 images. The images' pixel values are divided by 255 to normalize the values in the range from $0$ to $1$. The $28 \times 28$ normalized values of each image are flattened to an equivalent $784-$dimensional data point.

Results of privacy-preserving learning experiments on MNIST dataset

$\begin{array}{c}\mbox{privacy-loss}\\ \mbox{bound $\epsilon$} \end{array}$     $\begin{array}{c}\mbox{subspace}\\ \mbox{dimension $n$} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$     $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$      $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$
1.0     20     0.9491     0.9453     0.00000     0.00017
1.5     20     0.9644     0.9645     0.00025     0.00035
2.0     20     0.9711     0.9709     0.00074     0.00076
3.0     20     0.9779     0.9776     0.00299     0.00589
4.0     20     0.9802     0.9796     0.00687     0.01605
5.0     20     0.9820     0.9805     0.01275     0.03361
8.0     20     0.9833     0.9845     0.02968     0.11685
16.0     20     0.9854     0.9858     0.05459     0.30601
32.0     20     0.9851     0.9858     0.06171     0.35388
32.0     5     0.9680     0.9676     0.00503     0.01225
32.0     10     0.9799     0.9810     0.01794     0.08117
32.0     15     0.9851     0.9861     0.03501     0.20903
32.0     20     0.9851     0.9854     0.06145     0.35451
32.0     25     0.9845     0.9854     0.09111     0.49186

The performances of both differentially private classifier (Definition <ref>) and differentially private classifier based on fabricated data (Definition <ref>) are evaluated for different values of privacy-loss bound $\epsilon$ and subspace dimension $n$ while keeping the number of layers $L = 5$ and number of branches $S$ as given in (<ref>). Table <ref> reports the obtained results. For a visualization of the results, Fig. <ref> compares the accuracy and $mis$ values obtained by the two methods. It is observed in Fig. <ref> that while both classifiers (with and without using fabricated data) achieve nearly the same level of accuracy (as observed in Fig. <ref>), the membership-inference score is much lower in the case of fabricated data (as observed in Fig. <ref>). This is further illustrated through an example in Fig. <ref>. Fig. <ref> shows the histograms of distances of training and test points from the affine hull of training samples (in Fig. <ref>) and from the affine hull of fabricated samples (in Fig. <ref>). The use of fabricated data reduces considerably the membership-inference score from 0.35919 to 0.05377 with much less loss of accuracy from 0.9858 to 0.9849.

§.§.§ Freiburg Groceries Dataset

The plots of % reduction in accuracy and $mis$ values as a result of the use of fabricated data for Freiburg groceries dataset.

[histograms of distances of training and test data points from the affine hull of training samples]  [histograms of distances of training and test data points from the affine hull of fabricated samples]
An illustration of the reduction in $mis$ value through data fabrication on Freiburg groceries dataset.

The Freiburg groceries dataset is revisited to study the KAHM based differentially private classifiers. The $8192-$dimensional feature vectors, extracted as stated in Section <ref>, are considered to study both differentially private classifier (Definition <ref>) and differentially private classifier based on fabricated data (Definition <ref>) for different values of privacy-loss bound $\epsilon$ and subspace dimension $n$ while keeping the number of layers $L = 5$ and number of branches $S$ as given in (<ref>).

Results of privacy-preserving learning experiments on Freiburg groceries dataset

$\begin{array}{c}\mbox{privacy-loss}\\ \mbox{bound $\epsilon$} \end{array}$     $\begin{array}{c}\mbox{subspace}\\ \mbox{dimension $n$} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$     $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$      $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$
5.0     20     0.8016     0.8153     0.02600     0.04207
8.0     20     0.8556     0.8733     0.12512     0.20650
16.0     20     0.8792     0.8919     0.27377     0.51909
32.0     20     0.8811     0.8919     0.25753     0.40348
32.0     5     0.7996     0.8212     0.04019     0.08048
32.0     10     0.8595     0.8694     0.12220     0.24263
32.0     15     0.8752     0.8841     0.19986     0.34380
32.0     20     0.8811     0.8919     0.25753     0.40348
32.0     25     0.8782     0.8929     0.29724     0.45099

The experimental results, as reported in Table <ref>, are illustrated in Fig. <ref> via plotting the % reduction in both accuracy and $mis$ values due to the use of fabricated data. It is observed from Fig. <ref> that the use of fabricated data leads to considerable a decrease in $mis$ value, however, without much reduction in accuracy. This is demonstrated through an example in Fig. <ref> where the histograms of distances of training and test points from the affine hull of training samples (in Fig. <ref>) and from the affine hull of fabricated samples (in Fig. <ref>) are plotted. As the result of using fabricated data, the $msi$ value can be reduced considerably from 0.51320 to 0.12286 together with smaller loss of accuracy from 0.8880 to 0.8615.

§.§.§ A Real Biomedical Dataset

The plots of % reduction in accuracy and $mis$ values as a result of the use of fabricated data for heart rate variability dataset.

Results of privacy-preserving learning experiments on a heart rate variability dataset

$\begin{array}{c}\mbox{privacy-loss}\\ \mbox{bound $\epsilon$} \end{array}$     $\begin{array}{c}\mbox{subspace}\\ \mbox{dimension $n$} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$     $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier})} \end{array}$      $\begin{array}{c}\mbox{$mis$ by}\\ \mbox{classifier}\\ \mbox{(Def. \ref{def_diff_priv_KAHM_classifier_ref})} \end{array}$
8.0     5     0.8485     0.9074     0.02773     0.04903
16.0     5     0.8817     0.9484     0.06739     0.15790
24.0     5     0.8925     0.9557     0.07625     0.21036
32.0     5     0.8964     0.9572     0.08310     0.23319
32.0     1     0.8608     0.9058     0.00973     0.02259
32.0     3     0.8777     0.9457     0.04045     0.12006
32.0     5     0.8931     0.9568     0.07603     0.22235
32.0     7     0.8960     0.9599     0.11834     0.33322
32.0     10     0.8938     0.9566     0.17230     0.48887
32.0     15     0.8795     0.9451     0.24173     0.68009

A dataset related to the mental stress detection problem [Kumar et al., 2021, Kumar et al., 2023] is considered to evaluate the proposed differentially private classifier based on fabricated data. This dataset consists of heart rate interval measurements of different subjects together with a stress-score on a scale from 0 to 100. The aim is to detect stress on an individual based on the analysis of recorded sequence of R-R intervals, $\{RR^i\}_i$. The R-R data vector at $i-$th time-index, $y^i$, is defined as $y^i  =  \left[\begin{IEEEeqnarraybox*}[][c]{,c/c/c/c,} RR^i & RR^{i-1} & \cdots & RR^{i-d}\end{IEEEeqnarraybox*} \right]^T$. That is, the current interval and history of previous $d$ intervals constitute the data vector. Assuming an average heartbeat of 72 beats per minute, $d$ is chosen as equal to $72 \times 3 = 216$ so that R-R data vector consists of on an average 3-minutes long R-R intervals sequence. Following [Kumar et al., 2021, Kumar et al., 2023], a dataset, say $\{y^i\}_{i}$, is built via 1) preprocessing the R-R interval sequence $\{RR^i\}_i$ with an impulse rejection filter for artifacts detection, and 2) excluding the R-R data vectors containing artifacts from the dataset. A class-label of either “no-stress” or “under-stress” is assigned to each data sample $y^i$ based on the stress-score. For each subject, 50% of the data samples serve as training data while remaining as test data. Both differentially private classifier (Definition <ref>) and differentially private classifier based on fabricated data (Definition <ref>) are considered for the stress detection problem for different values of privacy-loss bound $\epsilon$ and subspace dimension $n$ while keeping the number of layers $L = 5$ and number of branches $S$ as given in (<ref>).

Table <ref> reports the experimental results which have been visualized in Fig. <ref> via plotting the % reduction in both accuracy and $mis$ values due to the use of fabricated data. It is observed from Fig. <ref> that the use of fabricated data reduces considerably the $mis$ value at the cost of much smaller loss in accuracy.

§.§ Federated Learning

MNIST dataset (containing the samples of 10 classes) is reconsidered under the following federated learning scenarios:

* Scenario 1: The training data are distributed among 10 parties such that all samples of a class are possessed by only a single party. That is, a party has all the samples of a class.

* Scenario 2: The training data are distributed among 20 parties such that samples of a class are shared equally between two parties. That is, a party has 50% samples of a class.

* Scenario 3: The training data are distributed randomly independent of the classes among $Q$ number of parties where $Q \in \{2, 5, 10, 20, 50, 100\}$.

For all of the considered scenarios, the local classifiers are built for privacy-loss bound $\epsilon \in \{1,1,5,2,3,4,5,8,16\}$, subspace dimension $n = 20$, number of layers $L = 5$, and number of branches $S$ as given in (<ref>). The performance of the global classifier (<ref>) is evaluated on test data. As a reference, the performance in the case of non-federated learning (i.e. in the case of centralized data) is also evaluated using classifier (<ref>).

Results of federated learning experiments under Scenario 1 on MNIST dataset

$\begin{array}{c}\mbox{privacy-loss}\\ \mbox{bound $\epsilon$} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier (\ref{eq_300320231343})} \\ \mbox{(distributed data)}  \end{array}$      $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier (\ref{eq_030220231011})} \\ \mbox{(centralized data)}  \end{array}$     $\begin{array}{c}\mbox{change in accuracy}\\ \mbox{due to data} \\ \mbox{being distributed} \end{array}$
1     0.9460     0.9478     -0.0018
1.5     0.9633     0.9629     0.0004
2     0.9710     0.9707     0.0003
3     0.9783     0.9779     0.0004
4     0.9790     0.9798     -0.0008
5     0.9813     0.9819    -0.0006
8     0.9829     0.9837     -0.0008
16     0.9847     0.9851     -0.0004

Results of federated learning experiments under Scenario 2 on MNIST dataset

$\begin{array}{c}\mbox{privacy-loss}\\ \mbox{bound $\epsilon$} \end{array}$     $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier (\ref{eq_300320231343})} \\ \mbox{(distributed data)}  \end{array}$      $\begin{array}{c}\mbox{accuracy by}\\ \mbox{classifier (\ref{eq_030220231011})} \\ \mbox{(centralized data)}  \end{array}$     $\begin{array}{c}\mbox{change in accuracy}\\ \mbox{due to data} \\ \mbox{being distributed} \end{array}$
1     0.9384      0.9478     -0.0094
1.5     0.9603      0.9629     -0.0026
2     0.9670      0.9707     -0.0037
3     0.9733      0.9779     -0.0046
4     0.9758     0.9798     -0.0040
5     0.9778     0.9819     -0.0041
8     0.9803     0.9837     -0.0034
16     0.9813      0.9851     -0.0038

Results of 10 independent federated learning experiments under Scenario 3 on MNIST dataset for privacy-loss bound $\epsilon = 16$

$\begin{array}{c}\mbox{number of}\\ \mbox{parties $Q$} \end{array}$     $\begin{array}{c}\mbox{mean accuracy by}\\ \mbox{classifier (\ref{eq_300320231343})} \\ \mbox{(distributed data)}  \end{array}$      $\begin{array}{c}\mbox{change in mean accuracy}\\ \mbox{due to data} \\ \mbox{being distributed} \end{array}$
2     0.9817         -0.0030
5     0.9770        -0.0077
10     0.9752        -0.0095
20     0.9734        -0.0113
50     0.9728        -0.0119
100     0.9717        -0.0130

[Scenario 1] [Scenario 2]
[Scenario 3]
The plots for the results of federated learning experiments on MNIST dataset.

The obtained results are reported in Table <ref> and Fig. <ref> for Scenario 1, in Table <ref> and Fig. <ref> for Scenario 2, and in Table <ref> and Fig. <ref> for Scenario 3. Following observations are made from the obtained results:

* In Scenario 1 (when samples of a class are not shared by parties), the federated learning performance is not different from that of learning with centralized data. This is expected, as for each class there exists only one local KAHM that serves as the global KAHM for that class as well. Since there remains no difference between the class specific global and local KAHMs, the performance in the federated setting remains unaffected. Thus, the change in accuracy due to data being distributed, as reported in Table <ref>, remains less than 0.0018.

* In Scenario 2 (when samples of a class are shared by two parties), the performance under federated setting reduces slightly across the whole range of privacy-loss bound. It is observed from Table <ref> that the change in accuracy due to data being distributed, averaged over the considered range of privacy-loss bound, is equal to $-0.0044$. The accuracy loss of 0.0044 on an average  due to distributed data is marginal indicating a good performance.

* In Scenario 3 (when samples of a class are shared by up to 100 parties), it is observed from Table <ref> that the decrease in performance due to data being distributed is not significantly high. Specifically, the data distribution among 100 parties did not cause a loss in accuracy of more than 0.013. This verifies the application potential of the proposed federated learning scheme.

§.§ Computational Time

[against data dimension $p$]  [against subspace dimension $n$]
[against number of samples $N$] [against data size $N \times p$]
The plots for the computational time of KAHM.

To deal with the big data when the number of data samples $N$ is large (say $N > 1000$), the data points are suggested to be divided into $S$ number of subsets (where $S$ is given as in (<ref>)) and for each subset a separate conditionally deep KAHM is built leading to a wide conditionally deep KAHM (Definition <ref>). Since each data subset can be processed independently, a large number of data samples can be computationally managed using parallel and distributed computing. So we study the effect of sample size $N$ only up to $1000$ on the computational time of KAHM, as samples more than 1000 are divided into subsets and processed in parallel. Further, the effects of data dimension $p$ and subspace dimension $n$ are studied on the computational time of KAHM. For this, MATLAB R2017b simulations have been made on a MacBook Pro machine with a 2.2 GHz Intel Core i7 processor and 16 GB of memory. The simulations are made on the randomly generated data from the Gaussian distribution with mean 0 and variance 1 with
p     ∈    {10, 100, 500, 1000, 2500, 5000, 7500, 10000, 12500, 15000, 17500, 20000 },

n     ∈    {5, 10, 20, 50, 75, 100, 200, 300, 400, 500},

N     ∈    {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 }.

Fig. <ref> plots the computational time of KAHM in relation to increasing data dimension $p$, subspace dimension $n$, sample size $N$, and data size $N \times p$. The results verify that KAHM remains computationally practical for a wide range of these parameters. Since the data dimension could be very high, simulations include the range of data dimension up to $20000$. The results verify that

* a higher data dimension does not pose a major computational challenge as it took around 1600 seconds to compute a KAHM from 1000 samples of 20000-dimensional data points,

* KAHM is computationally practical as it took around 133 seconds for a dataset with $10^7$ entries (i.e. $N \times p = 10^7$).

§.§ Summary of Inferences

Following inferences are drawn from the experiments:

* KAHM based classifier improves the existing results on Freiburg groceries dataset indicating a highly competitive performance in modeling and thus classifying 8192-dimensional data points by means of KAHMs.

* The proposed fabricated data based differentially private classification reduces considerably the risk of membership inference attack with a marginal loss of accuracy. This is demonstrated through experiments on three different dataset: MNIST dataset, Freiburg groceries dataset, and a real biomedical dataset.

* The application potential of the KAHM based differentially private federated learning scheme is verified by the observation that the accuracy-loss due to data being distributed is either marginal or not significantly high.

* The computational issues arising from a large number of data samples are addressed automatically by design via splitting the dataset into subsets and processing each subset independently by a branch of the wide conditionally deep KAHM. Simulations verify that KAHM remains computationally practical and a higher data dimension does not pose a major computational challenge.

§ CONCLUSION

Having learned the representation of data samples in RKHS via solving a kernel regularized least squares problem with a meaningful choice of regularization parameter, KAHM defines a bounded region in the affine hull of data samples. KAHM and KAHM based models (consisting of series and parallel compositions of KAHMs) induce a distance function that measures the distance of an arbitrary data point from the data samples. Modeling the region of each class in data space through a separate KAHM allows building a classifier. An optimal differentially private noise adding mechanism is applied on training data samples to build a differentially private classifier. The smoothing of noise added samples through a carefully defined transformation (that ensures reducing the KAHM modeling error of smoothed samples below of that of original samples) mitigates the accuracy-loss issue of the differentially private classifier.

The theoretical results obtained in this study are related to the determination of regularization parameter for the kernel regularized least squares problem, boundedness of KAHM, distance functions induced by KAHMs, and smoothing of data for reduction in KAHM modeling error. KAHMs can be applied to a wide range of machine learning problems and this study has considered the differentially private federated learning problem as an application example. The practical significance of the theory is demonstrated through numerous experiments performed to verify the application potential of the KAHMs. A significant feature of our approach is that mathematical analysis has been carried out in a pure deterministic setting without making any statistical assumption. Our future work includes further analysis of KAHMs with application to semi-supervised transfer learning.

The research reported in this paper has been supported by the Austrian Research Promotion Agency (FFG) COMET-Modul S3AI (Security and Safety for Shared Artificial Intelligence); FFG Grant SMiLe (Secure Machine Learning Applications with Homomorphically Encrypted Data); FFG Grant PRIMAL (Privacy Preserving Machine Learning for Industrial Applications); FFG Sub-Project PETAI (Privacy Secured Explainable and Transferable AI for Healthcare Systems); and the Austrian Ministry for Transport, Innovation and Technology, the Federal Ministry for Digital and Economic Affairs, and the State of Upper Austria in the frame of the SCCH competence center INTEGRATE [(FFG grant no. 892418)] part of the FFG COMET Competence Centers for Excellent Technologies Programme.

§ PROOF OF THEOREM <REF>

The proof is split into four parts.

Part 1:
(Y)_:,j - K_X (K_X + (e+τ) I_N )^-1 (Y)_:,j     =     (I_N + 1/(e+τ) K_X  )^-1 (Y)_:,j

and thus
ℛ_k,X,Y(e,τ)     =     1/pN ∑_j=1^p ((Y)_:,j)^T ( I_N + 1/(e+τ)  K_X  )^-2 (Y)_:,j

Since $ K_{X}$ is a positive definite matrix and $(e+\tau) > 0$,
μ_min(I_N + 1/(e+τ) K_X )     >     1

where “$\mu_{min}(\cdot)$” denotes the minimum eigenvalue. Thus,
μ_max((I_N + 1/(e+τ) K_X )^-2 )     <     1

where “$\mu_{max}(\cdot)$” denotes the maximum eigenvalue. This results in
ℛ_k,X,Y(e,τ)     <     1/pN ∑_j=1^p (Y)_:,j ^2

=      1/pN  Y _F^2.

It is obvious that $\mathcal{R}_{k,X,Y}(e,\tau)  > 0$, hence (<ref>) follows.

Part 2:
The derivative of $\mathcal{R}_{k,X,Y}$ w.r.t. $e$ is given as
ℛ_k,X,Y(e,τ)/e     =     2/pN∑_j=1^p {(e+τ) ((Y)_:,j)^T ((e+τ) I_N + K_X   )^-2  (Y)_:,j .

. -   (e+τ)^2 ((Y)_:,j)^T ( (e+τ) I_N + K_X   )^-3  (Y)_:,j }.

(e+τ)^2 ((Y)_:,j)^T ( (e+τ) I_N + K_X  )^-3  (Y)_:,j

≤    (e+τ)^2  ( (e+τ) I_N + K_X   )^-1 _2 ((Y)_:,j)^T ( (e+τ) I_N + K_X   )^-2 (Y)_:,j

=     (e+τ)  ( I_N + 1/(e+τ) K_X   )^-1 _2 ((Y)_:,j)^T ( (e+τ) I_N + K_X   )^-2 (Y)_:,j

=     (e+τ) 1/σ_min( I_N + 1/(e+τ) K_X )((Y)_:,j)^T ( (e+τ) I_N + K_X   )^-2 (Y)_:,j

where “$\sigma_{min}(\cdot)$” denotes the minimum singular value. Observing that $(e+\tau) > 0$ and $K_{X}$ is a positive definite matrix, we have
σ_min( I_N + 1/(e+τ) K_X )     =     1 + σ_min(1/(e+τ)  K_X )

>     1.

(e+τ)^2 ((Y)_:,j)^T ( (e+τ) I_N + K_X  )^-3 (Y)_:,j

<    (e+τ) ((Y)_:,j)^T ((e+τ) I_N + K_X   )^-2 (Y)_:,j

resulting in
ℛ_k,X,Y(e)/e       >     0.

Since $(e+\tau) > 0$ and $K_{X}$ is a positive definite matrix,
(e+τ)^2 ((Y)_:,j)^T ( (e+τ) I_N + K_X    )^-3   (Y)_:,j     >     0,

and therefore
ℛ_k,X,Y(e,τ)/e      <     2/pN (e+τ) ∑_j=1^p  ((Y)_:,j)^T  ((e+τ) I_N + K_X   )^-2   (Y)_:,j

=     2/(e+τ)  ℛ_k,X,Y(e)

<       2/(e+τ) 1/pN  Y _F^2.

Inequalities (<ref>) and (<ref>) lead to (<ref>).

Part 3:
For a given $\tau \in \mathbf{R}_{+}$, introduce $m_{\tau}(e)  =  \mathcal{R}_{k,X,Y}(e,\tau) - e$, and observe that $m_{\tau}(0) > 0$ and $m_{\tau}(\frac{1}{pN}\|Y \|_F^2) < 0$. By the intermediate value theorem, there is a $\hat{e} \in (0, \frac{1}{pN}\|Y \|_F^2  )$ such that $m_{\tau}(\hat{e}) = 0$, i.e., $\hat{e}  =\mathcal{R}_{k,X,Y}(\hat{e},\tau)$. Thus, $\hat{e}$ is a fixed point of $\mathcal{R}_{k,X,Y}(e,\tau)$.

Part 4:
It follows from (<ref>) and (<ref>) that
ℛ_k,X,Y(e,τ)/e     ∈     (0, 1 ).

That is, there exists a constant $c$ such that
0     <     ℛ_k,X,Y(e|_it,τ)/e      ≤    c     < 1,  ∀it ∈{0,1,2,⋯}.

Let $\hat{e}$ be a fixed point of $\mathcal{R}_{k,X,Y}(e,\tau)$. Now, consider
| e |_it -  ê |     =      | ℛ_k,X,Y(e|_it-1,τ) - ℛ_k,X,Y(ê,τ) |     ≤    c | e |_it-1 -  ê |

≤    c^2 | e|_it-2 -  ê |

≤    c^it | e|_0 - ê |,

that leads to
lim_it →∞ | e|_it -  ê |     ≤    lim_it →∞ c^it | e |_0 -  ê |     =     0.

Hence the iterations (<ref>)-(<ref>) converge to a fixed point of $\mathcal{R}_{k,X,Y}(e,\tau)$. The uniqueness of the fixed point can be seen via assuming by contradiction that there exists another fixed point, say $\tilde{e}$. Now consider
| ẽ -  ê |     =     |ℛ_k,X,Y(ẽ,τ) -  ℛ_k,X,Y(ê,τ) |     ≤    c | ẽ -  ê |     <     | ẽ -  ê |.

This implies that $\tilde{e}  =  \hat{e} $. Hence, the result follows.

§ PROOF OF THEOREM <REF>

Define a diagonal matrix $D_y$ as
D_y     =     diag(k_θ(Py,Py^1),⋯,k_θ(Py,Py^N)),

k_y      =     max_i ∈{1,2,⋯,N} k_θ(Py,Py^i).

Further define a vector $G_y$ as
G_y     =     [[][c],c/c/c, k_θ(Py,Py^1)     ⋯    k_θ(Py,Py^N) ]^T.

It is obvious that $D_y^{-1} - (\overline{k}_y )^{-1}I$ is symmetric positive semi-definite, i.e.,
D_y^-1 - (k_y )^-1I_N     ≽    0.

Since $K_{YP^T}$ is symmetric positive definite and $\lambda^* > 0$,
(K_YP^T + λ^* I_N)^-1     ≻    0.

It follows from (<ref>) and (<ref>) that
(D_y^-1 - (k_y )^-1I_N ) (K_YP^T + λ^* I_N)^-1        ≽    0,

D_y^-1(K_YP^T + λ^* I_N)^-1 - (k_y )^-1 (K_YP^T + λ^* I_N)^-1       ≽    0,

G_y^T ( D_y^-1(K_YP^T + λ^* I_N)^-1 - (k_y )^-1 (K_YP^T + λ^* I_N)^-1   ) G_y     ≥    0.

G_y^T  D_y^-1(K_YP^T + λ^* I_N)^-1  G_y     ≥    (k_y )^-1 G_y^T (K_YP^T + λ^* I_N)^-1 G_y.

∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py)      =     (1_N)^T (K_YP^T + λI_N )^-1 G_y

=     G_y^T  D_y^-1 (K_YP^T + λI_N )^-1 G_y

≥    (k_y )^-1 G_y^T (K_YP^T + λ^* I_N)^-1 G_y

≥    (k_y )^-1 μ_min( (K_YP^T + λ^* I_N )^-1  )  G_y^2.

As $\left(K_{YP^T} + \lambda^* I_N \right)^{-1} $ is real symmetric positive definite,
>     0.

[[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T  /| ∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) |     =       (K_YP^T + λ^* I_N )^-1 G_y /∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py)

≤    k_y / G_y  (K_YP^T + λ^* I_N )^-1  _2/μ_min( (K_YP^T + λ^* I_N )^-1  ).

Since $\left(K_{YP^T} + \lambda^* I_N \right)^{-1} $ is real symmetric positive definite,
k_y / G_y  (K_YP^T + λ^* I_N )^-1  _2/μ_min( (K_YP^T + λ^* I_N )^-1  )     =     k_y / G_y μ_max( (K_YP^T + λ^* I_N )^-1  )/μ_min( (K_YP^T + λ^* I_N )^-1  )

=     k_y / G_y λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )

=       max_i ∈{1,2,⋯,N} k_θ(Py,Py^i) /√(∑_i=1^N |k_θ(Py,Py^i)|^2) λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )

<     λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T ).

[[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T  /| ∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) |     <       λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T ).

Since $K_{YP^T}$ is positive definite (i.e. $\mu_{min}(K_{YP^T}) > 0$) and $\mathrm{tr}(K_{YP^T} ) = N$ (i.e. $\mu_{max}(K_{YP^T} ) < N$), we have
λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )      <      λ^* + N/λ^* .

Using (<ref>) with the observation that $\hat{e} > 0$, we have
λ^*     >      2/pNY ^2_F,

λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )     <      1 + p N^2/2 Y_F^2.

It is observed from (<ref>) that
𝒜_Y,n(y)     =     1/∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) [[][c],c/c/c, y^1     ⋯    y^N ] [[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T.
𝒜_Y,n(y)     ≤     [[][c],c/c/c, y^1     ⋯    y^N  ]  _2   [[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T  /| ∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) | .

Using (<ref>) and (<ref>) in (<ref>) leads to
𝒜_Y,n(y)     <      Y  _2 λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )     <       Y  _2 ( 1 + p N^2/2 Y_F^2 ).

Hence, (<ref>) follows.

§ PROOF OF THEOREM <REF>

It is observed from (<ref>) that
y - 𝒜_Y,n(y)

=     1/∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) [[][c],c/c/c, y-y^1     ⋯    y-y^N ] [[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T.
y - 𝒜_Y,n(y)      ≤     [[][c],c/c/c, y-y^1     ⋯    y-y^N ]  _2   [[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T  /| ∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) | .
That is,
Γ_𝒜_Y,n(y)/ [[][c],c/c/c, y-y^1     ⋯    y-y^N ]  _2     ≤       [[][c],c/c/c, h^1_k_θ,YP^T,λ^*(Py)     ⋯    h^N_k_θ,YP^T,λ^*(Py)  ]^T  /| ∑_i=1^Nh^i_k_θ,YP^T,λ^*(Py) | .

Using (<ref>) and (<ref>) leads to
Γ_𝒜_Y,n(y)/ [[][c],c/c/c, y-y^1     ⋯    y-y^N ]  _2     <     λ^* + μ_max(K_YP^T )/λ^* + μ_min(K_YP^T )     <     1 + p N^2/2 Y_F^2.

Hence, (<ref>) follows.

§ PROOF OF THEOREM <REF>

It is observed from the definition of $\mathcal{D}_{Y,n,L}$ (i.e. (<ref>-<ref>)) that
Γ_𝒟_Y,n,L(y)     ≤     Γ_𝒜_Y,n(y).

Using (<ref>) in (<ref>) leads to (<ref>).

§ PROOF OF THEOREM <REF>

Γ_𝒲_Y,n,L,S(y)     =     min_s ∈{1,2,⋯,S }   Γ_𝒟_Y_s,n,L(y)

≤    min_s ∈{1,2,⋯,S }    Γ_𝒜_Y_s,n(y)

<     min_s ∈{1,2,⋯,S }   { ( 1 + p N_s^2/2 Y_s_F^2 ) [[][c],c/c/c, y - y^1,s     ⋯    y - y^N_s,s  ] _2 }

≤    min_s ∈{1,2,⋯,S }   { ( 1 + p N_s^2/2 Y_s_F^2 ) [[][c],c/c/c, y - y^1,s     ⋯    y - y^N_s,s  ] _F }.

Since $\{y^{1,s}, \cdots, y^{N_s,s} \} \subset \{y^1,\cdots,y^N \}$,
[[][c],c/c/c, y - y^1,s     ⋯    y - y^N_s,s  ] _F     <      [[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _F,

and thus
Γ_𝒲_Y,n,L,S(y)     <     [[][c],c/c/c, y - y^1     ⋯    y - y^N  ] _F ×min_s ∈{1,2,⋯,S }    ( 1 + p N_s^2/2 Y_s_F^2 )

leading to (<ref>).

§ PROOF OF THEOREM <REF>

Define a $N \times N$ matrix $H_m$ and a $p \times N$ matrix $O_m$ as
H_m     =     [[][c],c/c/c, h_k_θ_m,Ŷ_mP^T_m,λ^*_m^1(P_mŷ^1,m)      ⋯    h_k_θ_m,Ŷ_mP^T_m,λ^*_m^1(P_mŷ^N,m)
⋮        ⋮
h_k_θ_m,Ŷ_mP^T_m,λ^*_m^N(P_mŷ^1,m)     ⋯    h_k_θ_m,Ŷ_mP^T_m,λ^*_m^N(P_mŷ^N,m)   ],

O_m    =     [[][c],c/c/c, ∑_j=1^Nh_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^1,m)      ⋯    ∑_j=1^Nh_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^N,m)
⋮        ⋮
∑_j=1^Nh_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^1,m)     ⋯    ∑_j=1^Nh_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^N,m)   ]_p ×N.

It can be seen using (<ref>) that
H_m     =     (K_Ŷ_mP^T_m + λ^*_m I_N)^-1 K_Ŷ_mP^T_m,

I_N - H_m     =     (I_N + 1/λ^*_mK_Ŷ_mP^T_m)^-1,

I_N - H_m _2     =     1/σ_min(I_N + 1/λ^*_mK_Ŷ_mP^T_m).

As $\lambda^*_m > 0$ and $K_{\hat{Y}_mP^T_m}$ is a positive definite matrix,
I_N - H_m _2     =     1/1 + σ_min(1/λ^*_m K_Ŷ_mP^T_m)     <     1.

As the r.h.s. of (<ref>) is a positive definite matrix, we have
μ_min(I_N - H_m)     >     0,

μ_max(H_m)     <     1.

As $H_m$ is a real symmetric matrix, it follows immediately from (<ref>) that $\sigma_{max}(H_m) < 1$, and thus
H_m _2     <     1,

H_m _1     <     √(N),

max_i ∈{1,2,⋯,N }  ∑_j=1^N | h_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^i,m) |     <     √(N),

∑_j=1^N  h_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^i,m)      <     √(N), ∀i ∈{1,2,⋯,N }.

In view of (<ref>), we have
0    <   ∑_j=1^N  h_k_θ_m,Ŷ_mP^T_m,λ^*_m^j(P_mŷ^i,m)      <     √(N), ∀i ∈{1,2,⋯,N }.

It follows from (<ref>) that
O_m ∘[[][c],c/c/c, 𝒜_Ŷ_m,n(ŷ^1,m)      ⋯    𝒜_Ŷ_m,n(ŷ^N,m)   ]      =      [[][c],c/c/c, ŷ^1,m      ⋯    ŷ^N,m   ]   H_m,

Ŷ_m+1^T     =     Ŷ_m^T H_m,

Ŷ_m^T -  Ŷ_m+1^T     =     Ŷ_m^T (I_N - H_m).

Using (<ref>) for $m = M-1$, we have
Ŷ_M-1^T -  Ŷ_M^T     =     Ŷ_M-1^T (I_N - H_M-1).

Using (<ref>) recursively from $m = 0$ to $m = M-2$, we have
Ŷ_M-1^T     =      Ŷ_0^T H_0H_1 ⋯H_M-2.

Combining (<ref>) and (<ref>) leads to
Ŷ_M-1^T -  Ŷ_M^T     =      Ŷ_0^T H_0H_1 ⋯H_M-2 (I_N - H_M-1),

Ŷ_M-1 -  Ŷ_M     =     (I_N - H_M-1)H_M-2 ⋯H_1 H_0 Ŷ_0,

Ŷ_M-1 -  Ŷ_M _F     ≤      (I_N - H_M-1)H_M-2 ⋯H_1 H_0 _2   Ŷ_0_F,

Ŷ_M-1 -  Ŷ_M _F     ≤     I_N - H_M-1 _2  H_M-2 _2 ⋯H_1 _2   H_0 _2     Ŷ_0 _F.

β    =     max  (    I_N - H_M-1 _2,  H_M-2 _2, ⋯,  H_1 _2,   H_0 _2 ).

Since $\|  H_m \|_2  <  1$ (i.e. (<ref>)) and also $\| I_N - H_m \|_2 < 1$ (i.e. (<ref>)), we must have
0   <   β    <     1.

It follows from (<ref>) that
Ŷ_M-1 -  Ŷ_M _F     ≤     (β)^M  Ŷ_0 _F.

Considering that $\hat{Y}_0 = Y^+_{\epsilon}$ and $\hat{y}^{i,m}$ is the $i-$th column of $\hat{Y}_m^T$, we have
ŷ^i,M-1 -  ŷ^i,M      ≤     (β)^M  Y^+_ϵ _F.

ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 )

=     ( ∑_j=1^Nh_k_θ_M-1,Ŷ_M-1P^T_M-1,λ^*_M-1^j(P_M-1ŷ^i,M-1) - 1 ) 𝒜_Ŷ_M-1,n(ŷ^i,M-1 ),

ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 )

=     | ∑_j=1^Nh_k_θ_M-1,Ŷ_M-1P^T_M-1,λ^*_M-1^j(P_M-1ŷ^i,M-1) - 1 |   𝒜_Ŷ_M-1,n(ŷ^i,M-1 ) .

Using (<ref>) in (<ref>), we have
ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 )      <     (√(N)-1)   𝒜_Ŷ_M-1,n(ŷ^i,M-1 ) .

The inequality (<ref>) leads to
ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 )      <     (√(N)-1) Ŷ_M-1  _2 λ^*_M-1 + μ_max(K_Ŷ_M-1P^T_M-1 )/λ^*_M-1 + μ_min(K_Ŷ_M-1P^T_M-1 )

<      (√(N)-1) Ŷ_M-1  _F λ^*_M-1 + μ_max(K_Ŷ_M-1P^T_M-1 )/λ^*_M-1 + μ_min(K_Ŷ_M-1P^T_M-1 ).

It follows from (<ref>) that
Ŷ_M-1 _F     ≤    H_M-2 _2 ⋯H_1_2  H_0_2  Ŷ_0_F,

Ŷ_M-1 _F     ≤    (β)^M-1  Y^+_ϵ _F.

ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 )      <      (√(N)-1) (β)^M-1  λ^*_M-1 + μ_max(K_Ŷ_M-1P^T_M-1 )/λ^*_M-1 + μ_min(K_Ŷ_M-1P^T_M-1 )  Y^+_ϵ _F.

ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)      ≤     ŷ^i,M-1 -  ŷ^i,M  +    ŷ^i,M - 𝒜_Ŷ_M-1,n(ŷ^i,M-1 ) .

Using (<ref>) and (<ref>) in (<ref>), we finally obtain
ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)

<     (β)^M-1  Y^+ _F ( β+   λ^*_M-1 + μ_max(K_Ŷ_M-1P^T_M-1 )/λ^*_M-1 + μ_min(K_Ŷ_M-1P^T_M-1 ) (√(N)-1) ).

Since $ \mu_{min}(K_{\hat{Y}_{M-1}P^T_{M-1}} ) > 0$, $\mu_{max}(K_{\hat{Y}_{M-1}P^T_{M-1}})  <  N$, $\lambda^*_{M-1} > 0$, and $0<\beta<1$, we have
0   <    ( β+   λ^*_M-1 + μ_max(K_Ŷ_M-1P^T_M-1 )/λ^*_M-1 + μ_min(K_Ŷ_M-1P^T_M-1 ) (√(N)-1) )     <     1 + λ^*_M-1 + N/λ^*_M-1 (√(N)-1).

0   ≤    ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)  /(β)^M-1     <      Y^+ _F ( 1 + λ^*_M-1 + N/λ^*_M-1 (√(N)-1) )     <     ∞
Further, it is observed from (<ref>) that
lim_M →∞ (β)^M-1     =     0,

lim_M →∞  ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)       =     0.

Since (<ref>) holds for all $i \in \{1,2,\cdots,N \}$, we must have
lim_M →∞ ∑_i=1^N  ŷ^i,M-1 - 𝒜_Ŷ_M-1,n(ŷ^i,M-1)       =     0.

Hence, the result is proved.

[Abadi et al., 2016]
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal
Talwar, and Li Zhang.
Deep learning with differential privacy.
In Proceedings of the 2016 ACM SIGSAC Conference on Computer
and Communications Security, CCS '16, pages 308–318, New York, NY, USA,
2016. ACM.
ISBN 978-1-4503-4139-4.
URL <http://doi.acm.org/10.1145/2976749.2978318>.

[Balle and Wang, 2018]
Borja Balle and Yu-Xiang Wang.
Improving the gaussian mechanism for differential privacy: Analytical
calibration and optimal denoising.
In Jennifer G. Dy and Andreas Krause, editors, Proceedings of
the 35th International Conference on Machine Learning, ICML 2018,
Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of
Proceedings of Machine Learning Research, pages 403–412. PMLR,

[Belkin et al., 2018]
Mikhail Belkin, Siyuan Ma, and Soumik Mandal.
To understand deep learning we need to understand kernel learning.
In Jennifer Dy and Andreas Krause, editors, Proceedings of the
35th International Conference on Machine Learning, volume 80 of
Proceedings of Machine Learning Research, pages 541–549. PMLR, 10–15
Jul 2018.

[Chaudhuri et al., 2011]
K. Chaudhuri, C. Monteleoni, and A.D. Sarwate.
Differentially private empirical risk minimization.
Journal of Machine Learning Research, 12:0 1069–1109,

[Dwork and Roth, 2014]
Cynthia Dwork and Aaron Roth.
The algorithmic foundations of differential privacy.
Foundations and Trends in Theoretical Computer Science,
90 (3-4):0 211–407, 2014.
URL <https://doi.org/10.1561/0400000042>.

[Dwork et al., 2006]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.
Calibrating noise to sensitivity in private data analysis.
In Shai Halevi and Tal Rabin, editors, Theory of Cryptography,
pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.

[Ghojogh et al., 2021]
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley.
Reproducing kernel hilbert space, mercer's theorem, eigenfunctions,
nyström method, and use of kernels in machine learning: Tutorial and
ArXiv, abs/2106.08443, 2021.

[Gholami and Hajisami, 2016]
Behnam Gholami and Abolfazl Hajisami.
Kernel auto-encoder for semi-supervised hashing.
In 2016 IEEE Winter Conference on Applications of Computer
Vision (WACV), pages 1–8, 2016.

[Hofmann et al., 2008]
Thomas Hofmann, Bernhard Schölkopf, and Alexander J. Smola.
Kernel methods in machine learning.
The Annals of Statistics, 360 (3):0 1171 –
1220, 2008.
URL <https://doi.org/10.1214/009053607000000677>.

[Jain and Thakurta, 2013]
Prateek Jain and Abhradeep Thakurta.
Differentially private learning with kernels.
In Sanjoy Dasgupta and David McAllester, editors, Proceedings
of the 30th International Conference on Machine Learning, volume 28 of
Proceedings of Machine Learning Research, pages 118–126, Atlanta,
Georgia, USA, 17–19 Jun 2013. PMLR.

[Jund et al., 2016]
Philipp Jund, Nichola Abdo, Andreas Eitel, and Wolfram Burgard.
The freiburg groceries dataset.
CoRR, abs/1611.05799, 2016.
URL <http://arxiv.org/abs/1611.05799>.

[Kampffmeyer et al., 2018]
Michael Kampffmeyer, Sigurd Løkse, Filippo M. Bianchi, Robert Jenssen, and
Lorenzo Livi.
The deep kernelized autoencoder.
Applied Soft Computing, 71:0 816–825, 2018.

[Kumar et al., 2019]
M. Kumar, M. Rossbory, B. A. Moser, and B. Freudenthaler.
Deriving an optimal noise adding mechanism for privacy-preserving
machine learning.
In Gabriele Anderst-Kotsis, A Min Tjoa, Ismail Khalil, Mourad
Elloumi, Atif Mashkoor, Johannes Sametinger, Xabier Larrucea, Anna Fensel,
Jorge Martinez-Gil, Bernhard Moser, Christin Seifert, Benno Stein, and
Michael Granitzer, editors, Proceedings of the 3rd International
Workshop on Cyber-Security and Functional Safety in Cyber-Physical (IWCFS
2019), August 26-29, 2019, Linz, Austria, pages 108–118, Cham, 2019.
Springer International Publishing.

[Kumar et al., 2021]
M. Kumar, M. Rossbory, B. A. Moser, and B. Freudenthaler.
An optimal $(\epsilon,\delta)-$differentially private learning of
distributed deep fuzzy models.
Information Sciences, 546:0 87–120,

[Kumar, 2023]
Mohit Kumar.
Differentially private transferrable deep learning with
Advances in Computational Intelligence, 30
(1):0 1–27, 2023.

[Kumar and Freudenthaler, 2020]
Mohit Kumar and Bernhard Freudenthaler.
Fuzzy membership functional analysis for nonparametric deep models of
image features.
IEEE Transactions on Fuzzy Systems, 280 (12):0
3345–3359, 2020.

[Kumar et al., 2020]
Mohit Kumar, Michael Rossbory, Bernhard A. Moser, and Bernhard Freudenthaler.
Differentially private learning of distributed deep models.
In Adjunct Publication of the 28th ACM Conference on User
Modeling, Adaptation and Personalization, UMAP '20 Adjunct, pages 193–200,
New York, NY, USA, 2020. Association for Computing Machinery.
ISBN 9781450379502.

[Kumar et al., 2021]
Mohit Kumar, Bernhard Moser, Lukas Fischer, and Bernhard Freudenthaler.
Membership-mappings for data representation learning: Measure
theoretic conceptualization.
In Gabriele Kotsis, A. Min Tjoa, Ismail Khalil, Bernhard Moser, Atif
Mashkoor, Johannes Sametinger, Anna Fensel, Jorge Martinez-Gil, Lukas
Fischer, Gerald Czech, Florian Sobieczky, and Sohail Khan, editors,
Database and Expert Systems Applications - DEXA 2021 Workshops, pages
127–137, Cham, 2021b. Springer International Publishing.

[Kumar et al., 2021]
Mohit Kumar, Bernhard Moser, Lukas Fischer, and Bernhard Freudenthaler.
Membership-mappings for data representation learning: A bregman
divergence based conditionally deep autoencoder.
In Gabriele Kotsis, A. Min Tjoa, Ismail Khalil, Bernhard Moser, Atif
Mashkoor, Johannes Sametinger, Anna Fensel, Jorge Martinez-Gil, Lukas
Fischer, Gerald Czech, Florian Sobieczky, and Sohail Khan, editors,
Database and Expert Systems Applications - DEXA 2021 Workshops, pages
138–147, Cham, 2021c. Springer International Publishing.

[Kumar et al., 2021]
Mohit Kumar, Sukhvir Singh, and Bernhard Freudenthaler.
Gaussian fuzzy theoretic analysis for variational learning of nested
International Journal of Approximate Reasoning, 131:0
1–29, 2021d.
ISSN 0888-613X.

[Kumar et al., 2021]
Mohit Kumar, Weiping Zhang, Matthias Weippert, and Bernhard Freudenthaler.
An explainable fuzzy theoretic nonparametric deep model for stress
assessment using heartbeat intervals analysis.
IEEE Transactions on Fuzzy Systems, 290 (12):0
3873–3886, 2021e.

[Kumar et al., 2023]
Mohit Kumar, Weiping Zhang, Lukas Fischer, and Bernhard Freudenthaler.
Membership-mappings for practical secure distributed deep learning.
IEEE Transactions on Fuzzy Systems, pages 1–14, 2023.

[Laforgue et al., 2019]
Pierre Laforgue, Stéphan Clémençon, and Florence d'Alche Buc.
Autoencoding any data through kernel autoencoders.
In Kamalika Chaudhuri and Masashi Sugiyama, editors,
Proceedings of the Twenty-Second International Conference on Artificial
Intelligence and Statistics, volume 89 of Proceedings of Machine
Learning Research, pages 1061–1069. PMLR, 16–18 Apr 2019.

[Nikhitha et al., 2021]
Nair K. Nikhitha, A. L. Afzal, and S. Asharaf.
Deep kernel machines: A survey.
Pattern Anal. Appl., 240 (2):0 537–556, may

[Phan et al., 2016]
NhatHai Phan, Yue Wang, Xintao Wu, and Dejing Dou.
Differential privacy preservation for deep auto-encoders: An
application of human behavior prediction.
In Proceedings of the Thirtieth AAAI Conference on Artificial
Intelligence, AAAI'16, pages 1309–1316. AAAI Press, 2016.
URL <http://dl.acm.org/citation.cfm?id=3015812.3016005>.

[Rudi et al., 2017]
Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco.
Falkon: An optimal large scale kernel method.
In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus,
S. Vishwanathan, and R. Garnett, editors, Advances in Neural
Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

[Schölkopf et al., 2001]
Bernhard Schölkopf, Ralf Herbrich, and Alex J. Smola.
A generalized representer theorem.
In David Helmbold and Bob Williamson, editors, Computational
Learning Theory, pages 416–426, Berlin, Heidelberg, 2001. Springer Berlin

[Sugiyama et al., 2013]
Masashi Sugiyama, Takafumi Kanamori, Taiji Suzuki, Marthinus Christoffel du
Plessis, Song Liu, and Ichiro Takeuchi.
Density-Difference Estimation.
Neural Computation, 250 (10):0 2734–2775, 10

[Wilson et al., 2016]
Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P. Xing.
Deep kernel learning.
In Arthur Gretton and Christian C. Robert, editors, Proceedings
of the 19th International Conference on Artificial Intelligence and
Statistics, volume 51 of Proceedings of Machine Learning Research,
pages 370–378, Cadiz, Spain, 09–11 May 2016. PMLR.

[Zhang et al., 2022]
Weiping Zhang, Mohit Kumar, Weiping Ding, Xiujuan Li, and Junfeng Yu.
Variational learning of deep fuzzy theoretic nonparametric model.
Neurocomputing, 506:0 128–145, 2022.

[Zhang et al., 2019]
Yaling Zhang, Zhifeng Hao, and Shangping Wang.
A differential privacy support vector machine classifier based on
dual variable perturbation.
IEEE Access, 7:0 98238–98251, 2019.