††thanks<EMAIL_ADDRESS>
# Approximating Excited States using Neural Networks

Yimeng Min  Department of Computer Science
Cornell University
Ithaca, NY 14853, United States

###### Abstract

Recently developed neural network-based wave function methods are capable of
achieving state-of-the-art results for finding the ground state in real space.
In this work, a neural network-based method is used to compute excited states.
We train our network via variational principle, along a further penalty term
that imposes the orthogonality with lower-energy eigenfunctions. As a
demonstration of the effectiveness of this approach, results from numerical
calculations for one-dimensional and two-dimensional harmonic oscillators are
presented.

††preprint: APS/123-QED

##  I Introduction

Neural networks (NNs), inspired by biological processes of neurons in a brain,
have become pioneering methods in pattern recognition and machine learning in
recent years [1][2]. Recently, NN-based models have shown great promise in
physical science, such as identifying phases and phase transitions, designing
quantum experiments and simulating the ground state of a quantum system
[3][4][5]. These models can be categorized into two different types: data-
driven and data-free methods.

Most applications of NN-based models to physical sciences use data-driven
methods, where the models are trained using external data (training data) and
the predictions are performed separately on test data [6][7]. The inputs can
be configurations sampled with Monte Carlo [3], datasets compiled from
existing computational methods like density functional theory (DFT) [6][8] or
exact solutions on a lattice [9]. For date-free NN-based models, motivated by
the fact that NNs are universal function approximators [10], people tend to
use NNs as wave function ansatzes and minimize the energy expectation value.
This is known as the variational method: if the NN-based wave function is
close enough to the true ground state, so is the minimum energy expectation
value.

Recently, Carleo and Troyer propose NN-based representations for discrete spin
lattice systems and train their networks via the variational principle [5].
Besides spin lattice systems, NN-based representations are also demonstrated
to significantly reduce the relative energy error of variational ground state
in real space [11][12][13].

So far, these NN-based variational methods have focused on the ground-state
properties only. For spin lattice systems, the excited states provide
information such as ground state degeneracy, size of the excitation gap, and
low-lying dispersion of excitations [14][15][16]. Different types of NN-based
variational approaches have been utilized to model the excited states of spin
systems, for example, Choo $et$ $al.$ take advantage of Abelian spatial
symmetries and orthogonality between wave function with respect to the ground
state to obtain the energy gap between the ground state and the first excited
state [14], Nomura further extends the this method using a smaller number of
variational parameters [15], Vieijra $et$ $al.$ construct a variational wave
function that transforms as an irreducible representation of SU(2) and
provides direct access to the construction of excited states in spin systems
[16].

Though researchers have been trying to use NN-based variational methods for
simulating the excited states in spin systems, in real space, data-driven
methods are dominant approaches to approximate the excited states [9][17].
These NN-based data-driven approaches avoid the solution of the Schrödinger
equation at the price of requiring preexisting solutions such as spectrum
datasets [18] and photodynamics datasets [19]. Furthermore, data-driven
methods highly depend on the generalization ability of the NN structures and
the size of training datasets. For improving the simulation accuracy
(generalization ability), researchers need to simulate a very large dataset or
design complicated and handcrafted NN structures to encode the input
information. However, the first strategy is very challenging as the dataset
can subject to a heavy-tailed distribution, which means it is unrealistic to
cover all the instances. For the latter one, it is also very difficult to
determine the key parameters which control the approximation accuracy because
these complicated structures typically involve a huge number of parameters.

In this paper, we propose a NN-based penalty method to simulate single
particle excited states in real space using variational method, where no
external data are required. Similar techniques are used in density matrix
renormalization group (DMRG) calculations and variational Monte Carlo (VMC)
[20][21], but to our knowledge have not been applied in the NN-based wave
function ansatz context.

We add orthogonal penalty with lower-energy eigenfunctions into the
variational loss. This additional penalty enables us to efficiently
approximate the excited states. We construct the wave function using a fully
connected neural network with one hidden layer, which is among one of the
simplest NN structures. We further study how the parameters of neural networks
can affect the approximation accuracy.

This paper is organized as follows. In section II, we introduce network
structures and review variational theory , we show the orthogonal penalty can
lead to the rearrangement of the eigenvalues. Section III presents our results
on one-dimensional and two-dimensional quantum harmonic oscillators. In
section IV and V, we conclude our method and perform error analysis, we
further compare the number of parameters used in our model with NN-based data-
driven methods.

##  II Methods

###  II.1 Neural network representation

We start by building a neural network to represent the real part of the wave
function $\ket{\psi(\bm{\vec{x}})}$:111We assume the phase of wave function is
zero.

$\ket{\psi(\bm{\vec{x}})}=f_{nn}(\bm{\theta})(\bm{\vec{x}}),$ (1)

where $\bm{\vec{x}}\in\mathbb{R}^{d}$ is the coordinate,
$f_{nn}(\bm{\theta}):\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the neural
network function which maps the input coordinate to the wave function. The
input consists of $d$ neurons, followed by $l$ hidden layers and each hidden
layer has $\sigma$ neurons. The hyperbolic tangent function ($Tanh$) is used
as a nonlinear activation after each hidden layer. The output layer has
connections to all activated neurons in the previous layer. Let $\bm{\theta}$
represent the parameters in the neural network. Figure 1 illustrates the
neural network structure we used for two-dimensional quantum harmonic
oscillators .

Figure 1: Neural network architecture for 2D cases. The network takes the
coordinates as the input and the output is the wave function.

In our simulation, the plane is discretized into $M_{x}$ by $M_{y}$ points and
the expectation value of the Hamiltonian is evaluated on these coordinates.

###  II.2 Variational method

Variational computations have mostly been used to investigate the ground-state
properties of various systems. Consider a Hamiltonian operator
$\hat{\bm{H}}\in\mathbb{R}^{N\times N}$ whose eigenstates are
$\ket{\psi_{0}}$, $\ket{\psi_{1}}$, $\ket{\psi_{2}}$…$\ket{\psi_{N-1}}$ and
whose eigenvalues are $e_{0}\leq e_{1}\leq e_{2}...\leq e_{N-1}$. For
approximating the ground state, we minimize the energy expectation

$\bm{E_{0}}(\bm{\theta})=\frac{\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}}{\braket{\psi(\bm{\theta})}{\psi(\bm{\theta})}}.$
(2)

Here $\ket{\psi(\bm{\theta})}$ is the neural network representation of the
wave function and $\bm{\theta}$ represents the parameters to be optimized. For
the simplicity of notation, let $\ket{\psi(\bm{\theta})}$ denote the
normalized wave function
$\frac{\ket{\psi(\bm{\theta})}}{\sqrt{\braket{\psi(\bm{\theta})}{\psi(\bm{\theta})}}}$,
and equation 2 becomes:

$\bm{E_{0}}(\bm{\theta})=\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}.$
(3)

We then optimize $\bm{\theta}$ using variational principle,

$\tilde{\bm{\theta}}=\operatornamewithlimits{argmin}_{\bm{\theta}}\bm{E_{0}}(\bm{\theta})=\operatornamewithlimits{argmin}_{\bm{\theta}}\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}.$
(4)

Let $\ket{\bm{\tilde{\psi_{0}}}}$ denote the corresponding wave function
$\ket{\psi(\tilde{\bm{\theta}})}$. $\ket{\bm{\tilde{\psi_{0}}}}$ approximates
$\ket{\psi_{0}}$ because the minimum of the energy occurs when
$\ket{\bm{\tilde{\psi_{0}}}}$ is the ground-state wave function of
$\hat{\bm{H}}$. For approximating the first excited state,222 We assume the
systems are not degenerate at ground energy level. we minimize the following:

$\bm{E_{1}}(\bm{\theta})=\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}+\lambda\braket{\psi(\bm{\theta})}{\bm{\tilde{\psi_{0}}}}^{2}.$
(5)

$\bm{E_{1}}(\bm{\theta})$ consists of two parts: the expectation value of the
energy $\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}$ and the
orthogonal penalty
$\lambda\braket{\psi(\bm{\theta})}{\bm{\tilde{\psi_{0}}}}^{2}$, $\lambda>0$.
Our training minimizes the energy under the orthogonal constraint between
$\ket{\psi(\bm{\theta})}$ and previously converged ground state
$\ket{\bm{\tilde{\psi_{0}}}}$. Here, the orthogonal penalty parameter
$\lambda$ governs the magnitude of the orthogonal penalty and determines the
extent of how much the previous eigenvalue $e_{0}$ is lifted up. We rewrite
equation 5:

$\displaystyle\bm{E_{1}}(\bm{\theta})=\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}+\lambda\braket{\bm{\tilde{\psi_{0}}}}{\psi(\bm{\theta})}^{2}$
$\displaystyle=\bra{\psi(\bm{\theta})}\big{(}\sum_{i=0}^{N-1}e_{i}\ket{\psi_{i}}\bra{\psi_{i}}+\ket{\bm{\tilde{\psi_{0}}}}\lambda\bra{\bm{\tilde{\psi_{0}}}}\big{)}\ket{\psi(\bm{\theta})}.$
(6)

Since $\ket{\bm{\tilde{\psi_{0}}}}$ can be regarded as the approximation of
$\ket{\psi_{0}}$, the effective Hamiltonian
$\hat{\bm{H}}_{1}=\sum_{i=0}^{N-1}e_{i}\ket{\psi_{i}}\bra{\psi_{i}}+\lambda\ket{\bm{\tilde{\psi_{0}}}}\bra{\bm{\tilde{\psi_{0}}}}$
can be expressed in terms of the same basis set:

$\hat{\bm{H}}_{1}=\sum_{i=1}^{N-1}e_{i}\ket{\psi_{i}}\bra{\psi_{i}}+(e_{0}+\lambda)\ket{\psi_{0}}\bra{\psi_{0}}.$
(7)

As long as $\lambda>e_{1}-e_{0}$, then the lowest eigenvalue of
$\hat{\bm{H}}_{1}$ becomes $e_{1}$. By minimizing $\bm{E_{1}}(\bm{\theta})$,
the variational method finds the new ground state $\ket{\psi_{1}}$.

We can now generalize this penalty-based optimization scheme to $k$-$th$
excited state, let
$p_{i}(\bm{\theta})$=$\braket{\psi(\bm{\theta})}{\bm{\tilde{\psi_{i}}}}$
represent the orthogonal penalty between the wave function
$\ket{\psi(\bm{\theta})}$ and $i$-${th}$ excited state
$\ket{\bm{\tilde{\psi_{i}}}}$.
$\bm{p}_{i}(\bm{\theta})=\big{(}p_{0}(\bm{\theta}),p_{1}(\bm{\theta}),p_{2}(\bm{\theta})...p_{i-1}(\bm{\theta})\big{)}$.
For the $k$-${th}$ excited state, we minimize the following:

$\bm{E_{k}}(\bm{\theta})=\bra{\psi(\bm{\theta})}\hat{\bm{H}}\ket{\psi(\bm{\theta})}+\lambda||\bm{p}_{k}(\bm{\theta})||_{2}^{2}.$
(8)

Let $\hat{\bm{H}}_{k}$ be the effective Hamiltonian for $k$-$th$ excited
state. The orthogonal penalty lifts up the eigenvalues of
$\ket{\psi_{0}},\ket{\psi_{1}}...\ket{\psi_{k-1}}$ and one can express
$\hat{\bm{H}}_{k}$ as:

$\hat{\bm{H}}_{k}=\sum_{i=k}^{N-1}e_{i}\ket{\psi_{i}}\bra{\psi_{i}}+\sum_{i=0}^{k-1}(e_{i}+\lambda)\ket{\psi_{i}}\bra{\psi_{i}},$
(9)

when $\lambda>e_{k}-e_{0}$, the orthogonal penalty will rearrange the
eigenvalues. In other words, $\ket{\psi_{k}}$ becomes the new ground state
because $e_{k}<e_{0}+\lambda\leq e_{1}+\lambda\leq e_{2}+\lambda\leq
e_{k-1}+\lambda$. Thus, the neural network will no longer converge to previous
states using this penalty-based optimization scheme. In order to approximate
$k$-$th$ excited state, $\lambda$ should be greater than $e_{k}-e_{0}$. This
iterative training method enables us to find the $k$-$th$ excited states.
However, the gap between eigenvalues can be unknown under some circumstances
and we are unable to determine the threshold value $e_{k}-e_{0}$. In this
condition, the penalty method still works but takes more iterations. Take the
first excited state as an example, let $\Delta$ denote the gap between $e_{1}$
and $e_{0}$, when $\lambda$ is smaller than $\Delta$, it will take at least
$\lceil\frac{\Delta}{\lambda}\rceil$ iterations to approximate $e_{1}$ and
$\ket{\psi_{1}}$. In our simulation, we set $\lambda=1000$ to ensure $e_{0}$,
$e_{1}$, …, $e_{k-1}$ are lifted up.

###  II.3 Optimizing the wave function

In this paper, we simulate the eigenstates of one-dimensional and two-
dimensional harmonic oscillators. In one-dimensional condition, the $x$-axis
is discretized into $M_{x}$ points ranging from $-L_{x}$ to $L_{x}$, The
neural network takes the discrete coordinate as the input and the output is
the wave function. The algorithm is shown in Algorithm 1. The Hamiltonian is

$\hat{\bm{H}}=-\frac{\hbar^{2}}{2m}\hat{\bm{\nabla}}^{2}+\frac{m^{2}\omega^{2}}{2}\hat{\bm{x}}^{2},$

and the eigenstates are

$\psi_{n}(x)=\frac{1}{\sqrt{2^{n}n!}}(\frac{m\omega}{\pi\hbar})^{1/4}e^{-\frac{-m\omega
x^{2}}{2\hbar}}\mathcal{H}_{n}(\sqrt{\frac{m\omega}{\hbar}}x),$

where $\mathcal{H}_{n}$ represents $n$-${th}$ Hermite polynomial. In our
simulation, we take $\hbar=m=\omega=1$.

Algorithm 1 Computing the $k$-${th}$ excited states (1D)

1:Input: A neural network function $f_{\theta}$; $M_{x}$ grid points on
$x$-axis {$x_{1}$…$x_{M_{x}}$}; orthogonal penalty parameter $\lambda$.

2:Output: $k$-${th}$ excited state $\ket{\psi_{k}}$ = ($f_{\theta}(x_{1})$ …
$f_{\theta}(x_{M_{x}})$)

3:for $i$ in $0,1,...,k$ do

4:
$\ket{\psi_{i}(\bm{\theta})}\leftarrow\frac{\ket{\psi_{i}(\bm{\theta})}}{\sqrt{\braket{\psi_{i}(\bm{\theta})}{\psi_{i}(\bm{\theta})}}}$

5: $\bm{p}_{i}(\bm{\theta})=\\{\\}$

6: for $j$ in $0,1,...,i-1$ do

7: append $\braket{\psi_{i}(\bm{\theta})}{\bm{\tilde{\psi_{j}}}}$ to
$\bm{p}_{i}(\bm{\theta})$

8: end for

9:
$\bm{\tilde{\theta}}\leftarrow\operatornamewithlimits{argmin}\\{\bra{\psi_{i}(\bm{\theta})}\hat{\bm{H}}\ket{\psi_{i}(\bm{\theta})}$
\+ $\lambda$ $||\bm{p}_{i}(\bm{\theta})||_{2}^{2}\\}$

10: save the converged $\ket{\psi_{i}(\bm{\tilde{\theta}})}$ as
$\ket{\bm{\tilde{\psi_{i}}}}$

11:end for

12:return $\ket{\bm{\tilde{\psi_{k}}}}$

The Hamiltonian of two-dimensional quantum harmonic oscillator is:

$\hat{\bm{H}}=-\frac{1}{2}\hat{\bm{\nabla}}^{2}+\frac{1}{2}(\hat{\bm{x}}^{2}+\hat{\bm{y}}^{2}),$

and the eigenstates are:

$\psi_{n}(x,y)=\psi_{n_{x}}(x)\psi_{n_{y}}(y),$

where $\psi_{n_{x}}$ is the $n_{x}$-$th$ one-dimensional eigenstate along $x$
direction and $\psi_{n_{y}}$ is the $n_{y}$-$th$ one-dimensional eigenstate
along $y$ direction.

Similar to one-dimensional condition, we first mesh the $xy$ plane using
$M_{x}\times M_{y}$ points ranging from $(-L_{x},-L_{y})$ to $(L_{x},L_{y})$.
The neural network takes the discrete coordinate $(x_{i},y_{j})$ as the input
and the output is $\psi(x_{i},y_{j})$. The kinetic energy operator is

$-\frac{1}{2}\hat{\bm{\nabla}}^{2}=-\frac{1}{2}(\widehat{\bm{L_{xx}}}\otimes\hat{\bm{I}}+\hat{\bm{I}}\otimes\widehat{\bm{L_{yy}}}),$
(10)

where $\widehat{\bm{L_{xx}}}$ and $\widehat{\bm{L_{yy}}}$ are one-dimensional
discrete Laplacian operators in the $x$ and $y$ direction, respectively.

##  III Results

###  III.1 One-dimensional quantum harmonic oscillator

The corresponding variational energy levels are shown in Table. 1. Fig. 2, 3
and 4 show the simulated ground state and first to $5$-${th}$ excited states.
We use a neural network with 8 hidden layers and each layer has 16 neurons,
$M_{x}$ = 50,000, $L_{x}=10$. The eigenvalues are $(n+\frac{1}{2})$, where $n$
is the quantum number. Our results agree well with exact results.

Figure 2: Predicted $\ket{\psi}$ of one-dimensional harmonic oscillator. Left:
ground state; right: first excited state.

Figure 3: Predicted $\ket{\psi}$ of one-dimensional harmonic oscillator. Left:
second excited state; right: third excited state.

Figure 4: Predicted $\ket{\psi}$ of one-dimensional harmonic oscillator. Left: $4$-${th}$ excited state; right: $5$-${th}$ excited state. Table 1: Comparison between variational energy levels with analytical energy levels (one-dimensional quantum harmonic oscillator).  State | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
Simulated $E$ | 0.5000 | 1.500 | 2.500 | 3.502 | 4.500 | 5.501
Analytical $E$ | 0.5000 | 1.500 | 2.500 | 3.500 | 4.500 | 5.500

###  III.2 Two-dimensional quantum harmonic oscillator

The predicted variational eigenvalues on two-dimensional quantum harmonic
oscillator are shown in Table 2, for simplicity, we set $L_{x}=L_{y}$ and
$M_{x}=M_{y}$ during simulation. The eigenvalues are $(n_{x}+n_{y}+1)$, where
$n_{x}$ and $n_{y}$ are the quantum numbers along $x$ and $y$ direction. The
results agree with exact solutions. Figure 5, 6 and 7 describe the
corresponding wave functions listed in Table 2.

Figure 5: Predicted $\ket{\psi}$ of two-dimensional harmonic oscillator. Left:
ground state; right: first excited state.

Figure 6: Predicted $\ket{\psi}$ of two-dimensional harmonic oscillator. Left:
second excited state; right: third excited state.

Figure 7: Predicted $\ket{\psi}$ of two-dimensional harmonic oscillator. Left: 4-$th$ excited state; right: 5-$th$ excited state. Table 2: Comparison between variational energy levels with analytical energy levels (two-dimensional quantum harmonic oscillator). The neural network has 8 hidden layers and each layer has 16 neurons, $M_{x}=M_{y}=500$, $L_{x}=10$. State | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
Simulated $E$ | 1.000 | 2.000 | 2.001 | 3.001 | 3.001 | 3.001
Analytical $E$ | 1.000 | 2.000 | 2.000 | 3.000 | 3.000 | 3.000

We further study how the parameters affect the approximation accuracy using a
neural network wave function ansatz. Let $\Delta E=|E_{var}-E_{ana}|$ denote
the approximation error between variational energy $E_{var}$ and analytical
solution $E_{ana}$. As discussed before, since the evaluation of the
Hamiltonian depends on the input coordinates, we anticipate that a denser
discretization will result in improved accuracy. We here study relationship
between $\Delta E$ and mesh size $M_{x}$.

Figure 8: Approximation error with discretization parameter $M_{x}$. Left: 1D
harmonic oscillator ($L_{x}=10,\sigma=512$, $l=1$); Right: 2D harmonic
oscillator ($L_{x}=10,\sigma=2048$, $l=1$).

We use a neural network with only one hidden layer. Although we are using a
simple set up, our neural network ansatz has enough expressivity for any wave
function, given that one hidden layer with sufficient hidden units is capable
of approximating any wave function [10].

Figure 8 illustrates how $\Delta E$ depends on $M_{x}$. We increase $M_{x}$ in
powers of 2 and we observe a linear trend between $\Delta E$ and $M_{x}$ from
the log-log plot. Our results suggest that $\Delta E$ decreases as mesh size
$M_{x}$ increases. We refer more error analysis to supplementary material.

##  IV Conclusion

In this letter, we demonstrate the success of a variational approach, based on
a neural network wave function ansatz, for approximating the single-particle
ground state and excited states. Our method enforces orthogonality to
previously converged states, which leads to the rearrangement of eigenvalues.
We achieve high accuracy in the description of excited states. This method can
be generalized to any Hermitian operator.

## References

  * Schmidhuber [2015] J. Schmidhuber, Neural networks 61, 85 (2015).
  * LeCun  _et al._ [2015] Y. LeCun, Y. Bengio, and G. Hinton, Nature 521, 436 (2015).
  * Carrasquilla and Melko [2017] J. Carrasquilla and R. G. Melko, Nature Physics 13, 431 (2017).
  * Melnikov  _et al._ [2018] A. A. Melnikov, H. P. Nautrup, M. Krenn, V. Dunjko, M. Tiersch, A. Zeilinger, and H. J. Briegel, Proceedings of the National Academy of Sciences 115, 1221 (2018).
  * Carleo and Troyer [2017] G. Carleo and M. Troyer, Science 355, 602 (2017).
  * Schütt  _et al._ [2019] K. Schütt, M. Gastegger, A. Tkatchenko, K.-R. Müller, and R. J. Maurer, Nature communications 10, 1 (2019).
  * Rupp  _et al._ [2012] M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. Von Lilienfeld, Physical review letters 108, 058301 (2012).
  * Gilmer  _et al._ [2017] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, in  _International Conference on Machine Learning_ (PMLR, 2017) pp. 1263–1272.
  * Mills  _et al._ [2017] K. Mills, M. Spanner, and I. Tamblyn, Physical Review A 96, 042113 (2017).
  * Hornik  _et al._ [1989] K. Hornik, M. Stinchcombe, and H. White, Neural networks 2, 359 (1989).
  * Hermann  _et al._ [2020] J. Hermann, Z. Schätzle, and F. Noé, Nature Chemistry 12, 891 (2020).
  * Pfau  _et al._ [2020] D. Pfau, J. S. Spencer, A. G. Matthews, and W. M. C. Foulkes, Physical Review Research 2, 033429 (2020).
  * Teng [2018] P. Teng, Physical Review E 98, 033305 (2018).
  * Choo  _et al._ [2018] K. Choo, G. Carleo, N. Regnault, and T. Neupert, Physical review letters 121, 167204 (2018).
  * Nomura [2020] Y. Nomura, Journal of the Physical Society of Japan 89, 054706 (2020).
  * Vieijra  _et al._ [2020] T. Vieijra, C. Casert, J. Nys, W. De Neve, J. Haegeman, J. Ryckebusch, and F. Verstraete, Physical review letters 124, 097201 (2020).
  * Westermayr and Marquetand [2020] J. Westermayr and P. Marquetand, Chemical Reviews (2020).
  * Kiyohara  _et al._ [2020] S. Kiyohara, M. Tsubaki, and T. Mizoguchi, npj Computational Materials 6, 1 (2020).
  * Westermayr  _et al._ [2020] J. Westermayr, M. Gastegger, and P. Marquetand, The journal of physical chemistry letters 11, 3828 (2020).
  * Stoudenmire and White [2012] E. M. Stoudenmire and S. R. White, Annu. Rev. Condens. Matter Phys. 3, 111 (2012).
  * Pathak  _et al._ [2021] S. Pathak, B. Busemeyer, J. N. Rodrigues, and L. K. Wagner, The Journal of Chemical Physics 154, 034101 (2021).
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, arXiv preprint arXiv:1412.6980 (2014).

##  V Supplementary Material

###  V.1 Computational details

Code repository: https://github.com/yimengmin/vmc.

We train our model for 200,000 steps using Adam optimizer [22]. The initial
learning rate is 0.01 and we decrease the learning rate by a factor of 0.9
every 20,000 steps.

###  V.2 Error analysis

Figure S1 demonstrates how $L_{x}$ affects the approximation accuracy. Our
results suggest there exists an optimal scale. Small $L_{x}$ is not capable to
provide enough support for the wave function, while a larger $L_{x}$
corresponds to the reduction of $M_{x}$, which also weakens the simulation
accuracy.

Figure S1: Approximation error with scale parameter $L_{x}$. Left: 1D harmonic
oscillator ($M_{x}=12800$, $\sigma=512$, $l=1$); Right: 2D harmonic oscillator
($M_{x}=320$, $\sigma=2048$, $l=1$).

Figure S2: Approximation error with depth parameter $l$. Left: 1D harmonic
oscillator ($M_{x}=12800$, $\sigma=16$, $L_{x}=10$); Right: 2D harmonic
oscillator ($M_{x}=320$, $\sigma=16$, $L_{x}=10$).

Figure S2 shows how layer depth parameter $l$ affects $\Delta E$. As $l$
increases, $\Delta E$ decreases first and then maintains at the same level. We
observe a slight increase when we further deepen the network in 2D condition,
suggesting that a very deep neural network is not necessary. Figure S3 shows
how the width parameter $\sigma$ affects $\Delta E$. Our results suggest that
a very wide neural network is also unnecessary.

Figure S3: Approximation error with width parameter $\sigma$. Left: 1D
harmonic oscillator ($L_{x}=10,M_{x}=12800$, $l=1$); Right: 2D harmonic
oscillator ($L_{x}=10,M_{x}=320$, $l=1$).

###  V.3 Comparison of number of parameters

The NN-based variational method has fewer parameters comparing to data-driven
methods. For example, Mills $et\leavevmode\nobreak\ al.$ study the two-
dimensional single electron system using a convolutional deep neural network
[9] with error $\sim 1e^{-3}$. The convolutional deep neural network has seven
layers and the final convolutional layer is fed into a fully connected layer
of width 1024, this operation creates $4\times 4\times 16\times 1024=262,144$
parameters. In our simulation, we use a single-layer neural network with 2048
hidden units for Figure 8 and the total number of parameters is 6144. To
further reduce the number of parameters, we use 8 hidden layers and each
hidden layer has a width of 16, then the total number of parameters for two-
dimensional case is 2096 (Figure 5, 6, 7). Our data-free method has fewer
parameters than the data-driven counterpart.


# Classification Protocols with Minimal Disclosure

Jinshuo Dong Northwestern University. Email<EMAIL_ADDRESS>Jason
Hartline Northwestern University. Email<EMAIL_ADDRESS>Aravindan
Vijayaraghavan Northwestern University. Email<EMAIL_ADDRESS>
###### Abstract

We consider multi-party protocols for classification that are motivated by
applications such as e-discovery in court proceedings. We identify a protocol
that guarantees that the requesting party receives all responsive documents
and the sending party discloses the minimal amount of non-responsive documents
necessary to prove that all responsive documents have been received. This
protocol can be embedded in a machine learning framework that enables
automated labeling of points and the resulting multi-party protocol is
equivalent to the standard one-party classification problem (if the one-party
classification problem satisfies a natural independence-of-irrelevant-
alternatives property). Our formal guarantees focus on the case where there is
a linear classifier that correctly partitions the documents.

##  1 Introduction

This paper considers the multi-party classification problem that arises in
document review for discovery in legal proceedings. The plaintiff (henceforth:
Bob) issues a request for production to the defendant (henceforth: Alice). The
legal team of Alice is then accountable for reviewing all documents and
provides the responsive ones. Grossman and Cormack, (2010) show this manual
process can be significantly improved by automation. A potential issue with
the adoption of this technology, however, is that automation could reduce
transparency and accountability, and the accuracy and completeness of this
process relies critically on the accountability of Alice’s legal team and its
obligations under the rules of professional responsibility.

In addition to accountability, Gelbach and Kobayashi, (2015) identify
significant problems with the above method for discovery. First, the defendant
(Alice) bears most of the cost of reviewing and selecting the responsive
documents and this asymmetry could lead the plaintiff (Bob) to exploit such
costly requests. Second, it misaligns the incentives of the Alice’s legal team
and causes the team, on the grounds of professional responsibility, to conduct
work to benefit its adversary.

Another possible way to implement requests for production places the effort
and accountability on the plaintiff. Bob issues a request for production to
Alice. Alice delivers all the documents to Bob’s legal team. Bob’s legal team
identifies the responsive documents (and discards the non-responsive ones). Of
course, there is now a risk that Bob’s legal team might learn facts from the
documents not specified in the request for production. Alice and Bob may enter
into a confidentiality agreement under the order of the court to protect the
disclosure of Alice’s private information and Bob’s legal team should operate
under its obligations under the rules of professional responsibility.

$-$$-$$-$$-$$-$$-$$+$$+$$+$$+$ $-$$-$$-$$-$$+$$-$$+$$+$$+$$+$
$-$$-$$-$$-$$-$$+$$+$$+$$+$$+$

Figure 1: Left: The labeled points are linearly separable; Middle: The labeled
points are linearly separable when the right-most negative point is relabeled
as positive; Right: The labeled points are not linearly separable when the
center negative point is relabeled as positive. The right-most negative point
is critical; the center negative point is non-critical.

This paper aims to understand multi-party binary classification protocols that
rely as little as possible on external means of accountability. We aim for
protocols that satisfy three main properties:

  1. 1.

(Correct) Bob receives all responsive documents.

  2. 2.

(Minimal) Alice minimizes privacy loss (as few non-responsive documents as
possible are revealed to Bob).

  3. 3.

(Computationally Efficient): Algorithms run by all parties are computationally
efficient.

We will also be interested in a fourth property which our protocol will
satisfy:

  1. (4)

(Truthful) Alice’s best strategy in the protocol is to truthfully reveal the
set of relevant documents.

Our protocols will make use of a trusted third party, Trent. Trusted third
parties are common in the design of protocols, and can often be replaced with
secure multi-party computation (Yao,, 1986; Goldreich et al.,, 1987). For
e-discovery of electronic mail, many companies already use third parties for
email storage, and perhaps these third parties can take on the role of the
trusted third party in our protocol. Alternatively, the court system could
provide the trusted third party.

After introducing a trusted third party, there is now a third possible
protocol: Bob communicates a classifier to Trent and Trent uses the classifier
identify the responsive documents, checks these documents with Alice, and then
communicates them to Bob. The problem with this approach is that, while we
assume Bob’s legal team can identify whether or not any given document is
responsive, we do not assume that Bob can succinctly communicate such a
labeling strategy in the form of a machine executable classifier. For Bob to
produce such a classifier Bob needs real documents that only Alice possesses.
We furthermore do not assume that Trent is capable of non-mechanical tasks.

Our protocol is based on two assumptions on the environment. First, we assume
that Alice can and will provide Trent with all documents before the protocol
begins. We view this assumption as much weaker than the current standard
assumption of the leading paragraph where Alice is required to provide only
the relevant documents. Providing all documents is a weaker requirement than
providing the relevant documents because there is no potential discretion
involved. Alice’s legal team cannot claim to think an document was not
responsive as a justification for not providing it. Our second assumption is
that both Alice and Bob can determine responsiveness of documents and if there
is a disagreement in responsiveness, that this disagreement can be resolved by
the court.

Our problem is one of multi-party classification, dividing the documents
(henceforth: points) into responsive (positive points) and non-responsive
(negative points). We assume that there is a classifier that is consistent
with the labeling of the documents (See Figure 1). A key construct in the
protocol is, given a set of alleged positive points and a set of alleged
negative points that are separable, identifying all the other points that
could be labeled as positive by a consistent classifier. We will refer to
these points as leaked. A key quantity for our protocol is the critical
points: negative points that are leaked when all other points are known. It is
easy to see that there is no way Trent can be convinced that a critical point
is negative without confirming its negative label with Bob.

With these constructs we define the critical points protocol:

  1. (0)

Alice discloses all points to Trent.

  2. 1.

Alice discloses to Trent which of the points she alleges as positive.

  3. 2.

Trent assumes that all remaining points are negative and computes the alleged
critical points.

  4. 3.

Trent sends the alleged positive and alleged critical points to Bob.

  5. 4.

Bob labels these points and sends the labels to Trent.

  6. 5.

Trent checks Bob’s and Alice’s labels agree (resolving any disagreement in
court).

  7. 6.

Trent sends the leaked points corresponding to the correctly labeled points to
Bob.

Our main protocol and results will be for binary classification with linear
classifiers (See Figure 1). In these settings there is a projection from
document space into a high-dimensional space of real numbers. Classifiers are
given by hyperplanes that partition the space into two parts, the positives
and the negatives. The assumption that there exists such a consistent
classifier is known as the realizable setting or the (linearly) separable
setting. Our main result is that for linear classification in the realizable
setting, the critical points protocol is correct, minimal, and computationally
efficient. (See Section 2 for formal definitions and theorem statements.)

While we focus on linear classification for exposition, our main result also
extends to more powerful kernel-based classifiers like kernel support vector
machines. Kernel methods embed the input space into a feature space that is
higher-dimensional (potentially infinite dimensional), where the data is
potentially linearly separable. Hence they capture more expressive hypothesis
classes like polynomial threshold functions111The label of $x$ is given by the
sign of a polynomial $p(x)$; linear classifiers correspond to the special case
of degree-$1$ polynomials., and even neural networks in some settings
(Scholkopf and Smola,, 2001; Shalev-Shwartz and Ben-David,, 2014; Jacot et
al.,, 2018). See Section 4 for details.

We can also show that the basic critical points protocol can be embedded
within a machine learning framework that includes several of the technology-
assisted review processes studied by Cormack and Grossman, (2014). In this
framework, there is a large universe of documents. This large universe of
documents is sampled. The critical points protocol is run on the sample with
labels provided by hand by the legal teams of Bob and Alice as specified. When
the protocol terminates with Bob possessing both the critical negative points
and the positive points, Bob selects a classifier that is consistent with
these points. Bob reports this classifier to Trent who checks that it is
consistent with the labeled points and then applies it to the universe of
points and gives Bob all the points that are classified as positive. We prove
that if Bob’s classification algorithm satisfies independence of irrelevant
alternatives, i.e., if the classifier selected is only a function of the set
of consistent classifiers for the labeled points, then the outcome of this
process is equivalent to the outcome of an analogous single-party
classification procedure. In the case of linear classification and kernel-
based classifiers, this can be instantiated with the support vector machine
(SVM) algorithm that we prove satisfies the IIA property. (See Section 3 for
formal statements.)

#### Related Work.

Our work contributes to a growing literature on the theory of machine learning
for social contexts. In this literature it is not enough for the algorithm to
have good performance in terms of error, but it must also satisfy key
definitions to be usable. Like a number of problems in this space, the gold-
standard result is a reduction from the learning problem with societal
concerns to the learning problem without such concerns. For example, Dwork et
al., (2012) construct fair classifiers from non-fair classifiers. A key
perspective of this approach is it enables the machine learning algorithm
designers to plug in their favorite algorithms, but results in a system with
the desired societal properties, in their case, fairness. Our results for the
machine learning framework in Section 3 are of a similar flavor: our protocol
can be used in conjunction with any learning algorithm satisfying the IIA
property to extend it to the multi-party setting.

Goldwasser et al., (2021) consider interactive protocols for PAC (provably
approximately correct) learning. They ask whether a verifier can be convinced
that a classifier is approximately correct with far fewer labeled data points
than it takes to identify a correct classifier. In the realizable case, the
answer is yes. More generally, they show that there are classification
problems where it is significantly cheaper in terms of labeled data points;
and there are classification problems where it is no cheaper. Connecting to
our model, their prover corresponds to Alice, their verifier corresponds to
Bob. The big difference between their model and ours is that they assume that
Bob (the verifier) can freely sample labeled data points. In our model Bob
does not have access to the data without getting it from Alice. Moreover the
main challenge in our setting is for Alice and Trent to convince Bob that no
relevant documents were left out.

##  2 Critical Points Protocol: Definitions, Protocol and Guarantees

There are three parties: Alice (defendant), Bob (plaintiff) and Trent who is a
trusted third party. Alice has a set of data points $S\subset\mathbb{R}^{n}$
(potentially the training samples), that is comprised of positive examples
$S_{+}$ and negative examples $S_{-}$ with their disjoint union denoted by
$S_{+}\sqcup S_{-}=S$. Alternately, each data point corresponds to a labeled
example of the form $(x,y)$ where $x\in\mathbb{R}^{n}$ and $y\in\\{\pm 1\\}$,
where $y=+1$ if $x\in S_{+}$ and $y=-1$ if $x\in S_{-}$. These labeled
examples are assumed to be (strictly) linearly separable i.e., there exists
$d\in{\mathbb{R}}^{n}$ and $c\in\mathbb{R}$ such that
$y=h(x)=\text{sign}(d\cdot x-c)$.

There are potentially several rounds of interaction between Alice, Bob and
Trent. We will adhere to the revelation principle (Section 2.1) and restrict
attention to protocols where Alice only interacts once and is asked to specify
the positive labels $S_{+}$ (the other labels $S\setminus S_{+}$ are assumed
to be the negative points $S_{-}$). For a truthful mechanism ${\mathcal{M}}$,
we will denote by ${\mathcal{M}}(A_{+},S_{+})\subset S$ the set of points that
are revealed to Bob eventually when Alice reports $A_{+}$ and the true labels
are $S_{+}\subset S$. Here ${\mathcal{M}}(A_{+},S_{+})$ is the output of the
protocol. We aim for a protocol which satisfies the following four properties.

######  Definition 1.

Protocol ${\mathcal{M}}$ properties on all data sets $S=S_{+}\sqcup S_{-}$ and
all reports $A_{+}\subset S$:

  1. 1.

(Correct) The positive points are revealed to Bob,
i.e., ${\mathcal{M}}(A_{+},S_{+})\supseteq S_{+}.$

  2. 2.

(Minimal) (If Alice reports truthfully) the protocol minimizes the number of
negative points revealed, i.e.,
$|{\mathcal{M}}(S_{+},S_{+})\setminus S_{+}|$ is minimized.

  3. 3.

(Computational Efficiency) The algorithms run by all parties are
computationally tractable.

  4. 4.

(Truthful) Alice’s best strategy is to truthfully reveal the set of relevant
documents, i.e., $A_{+}=S_{+}$ minimizes ${\mathcal{M}}(A_{+},S_{+})$.

In the protocol we will define, Alice and Bob will be expected simply to label
points. The complex computations will be mechanically performed by Trent, the
trusted third party. The basic computation performed by Trent is the
$\mathrm{Leak}$ operator which, given a subset of linearly separable points
labeled as positives and negatives $A_{+}\sqcup A_{-}=A$, determines the set
of all the points $S$ that are labeled as positive by some classifier
consistent with the labels of $A$. Let $\mathcal{H}=\\{h(x)=\text{sign}(d\cdot
x-c):d\in{\mathbb{R}}^{n},c\in{\mathbb{R}}\\}$ denote the set of all linear
classifiers over ${\mathbb{R}}^{n}$.

######  Definition 2.

The consistent classifiers for points $A_{+}\sqcup A_{-}=A$ is
${\mathcal{H}}(A_{+},A_{-})=$

$\\{h\in\mathcal{H}:\forall x_{+}\in A_{+},\ h(x_{+})=+1\text{ and }\forall
x_{-}\in A_{-},\ h(x_{-})=-1\\}.$

######  Definition 3.

The leak operator $\mathrm{Leak}(A_{+},A_{-})$ is all the points in $S$ are
classified by positive by some consistent classifier.

$\mathrm{Leak}(A_{+},A_{-})=\\{x\in S:\exists h\in{\mathcal{H}}(A_{+},A_{-}),\
h(x)=+1\\}\cup A_{-}$

######  Lemma 4.

For linear classification, whether or not a point $x\in S$ is in
$\mathrm{Leak}(A_{+},A_{-})$ is a linear classification problem (and can be
computed in polynomial time).

###### Proof.

We first check if $x\in A_{-}$; if yes, $x\in\mathrm{Leak}(A_{+},A_{-})$. If
not, the goal is to check if there is a linear classifier $h\in\mathcal{H}$
that assigns a label $+1$ to all points in $A_{+}\cup\\{x\\}$, and assigns the
label $-1$ to all points in $A_{-}$. This is clearly a linear classification
problem. This can be solved in polynomial time using the SVM algorithm (see
Fact 22 in Section 3.2) or using a linear program. ∎

In the introduction the critical points were defined as the points that could
are ambiguous with respect to the consistent classifiers when Alice reports
positives as $A_{+}$ and all other points not labeled as positive by Alice are
negatives. The definition of critical points requires that $A_{+}$ is linearly
separable from $S\setminus A_{+}$.

######  Definition 5.

The critical points for set $A_{+}\subset S$ are

${\mathcal{C}}^{*}(A_{+})=\\{x\in S:x\in\mathrm{Leak}(A_{+},S\setminus
A_{+}\setminus\\{x\\})\\}~{}\big{\backslash}A_{+}.$

We refer to the following algorithm as the critical points protocol because,
as we will subsequently prove (in Theorem 7),

$\mathrm{Leak}(A_{+},{\mathcal{C}}^{*}(A_{+}))=A_{+}\cup{\mathcal{C}}^{*}(A_{+}).$
(1)

Thus, if Alice truthfully reports $A_{+}=S_{+}$ then the protocol terminates
with the only negative points disclosed being ${\mathcal{C}}^{*}(A_{+})$.

Algorithm 1 Critical Points Protocol (CPP)

1:Alice sends all points $S$ to Trent.

2:Alice sends alleged positive points $A_{+}\subset S$ to Trent.

3:if $A_{+}$ and $S\setminus A_{+}$ are not separable then

4: Trent sends $S$ to Bob and the protocol ends.

5:Trent computes critical points ${\mathcal{C}}^{*}(A_{+})$ and sends
$A_{+}\cup{\mathcal{C}}^{*}(A_{+})$ to Bob.

6:Bob labels the points and sends labels to Trent.

7:Trent checks that Bob and Alice’s labels are consistent sending any disputed
labels to be resolved by the court. Denote the resulting labeled points by
$A_{+}^{\prime}\sqcup A_{-}^{\prime}$

8:Trent sends $\mathrm{Leak}(A_{+}^{\prime},A_{-}^{\prime})$ to Bob and the
protocol ends.

######  Theorem 6.

When the data points $S$ with positive samples $S_{+}$ and negative samples
$S_{-}$ are linearly separable, the critical points protocol (Algorithm 1) is
(1) Correct, (2) Minimal i.e., for all $A_{+}$
${\mathcal{M}}(A_{+},S_{+})\supseteq S_{+}\cup{\mathcal{C}}^{*}(S_{+})$, and
if Alice is truthful and reports $S_{+}$ to Trent, then
${\mathcal{M}}(S_{+},S_{+})=S_{+}\cup{\mathcal{C}}^{*}(S_{+})$. Furthermore
this protocol is (3) Computationally efficient and (4) Truthful.

We remark that minimality of the CPP protocol holds in a stronger sense: in
every correct protocol, Bob observes $S_{+}\cup{\mathcal{C}}^{*}(S_{+})$; see
Theorem 17 for a proof. Please also see Section 2.1 for a revelation
principle.

We now proceed to the proof of Theorem 6. Note that Bob either sees all of
$S$, or he sees $\mathrm{Leak}(A^{\prime}_{+},A^{\prime}_{-})$ for some
appropriate sets $A_{+}^{\prime}\subset S_{+}$ and $A_{-}^{\prime}\subset
S_{-}$.

###### Proof of Theorem 6.

The proof of the theorem follows from the following three claims for any
$A_{+}\sqcup A_{-}\subset S$:

  1. 1.

$\mathrm{Leak}(A_{+},A_{-})$ is non-increasing in $A_{+}$.

For fixed $A_{-}$, and consider $A_{+}^{\prime}\supset A_{+}$ that is
separable from $A_{-}$. Separability of $A_{+}^{\prime}\sqcup A_{-}$ implies
that the new points $A_{+}^{\prime}\setminus A_{+}$ were also previously
leaked in $\mathrm{Leak}(A_{+},A_{-})$. Moreover, for other points in $S$,
there are now more constraints on separating hyperplanes so only fewer of them
will be leaked. In total, no more points are leaked by
$\mathrm{Leak}(A_{+}^{\prime},A_{-})$.

  2. 2.

$\mathrm{Leak}(A_{+},A_{-})$ always contains ${\mathcal{C}}^{*}(A_{+})$.

Fix $A_{+}$, whether or not point $x$ is leaked is monotone decreasing in
$A_{-}\not\ni\mathbf{x}$. Adding points to $A_{-}$ only adds constraints on
separating hyperplanes making it only harder for $x$ to be leaked. Since
$x\in{\mathcal{C}}^{*}(A_{+})$ is leaked by $\mathrm{Leak}(A_{+},S\setminus
A_{+}\setminus\\{x\\})$ then by monotonicity $x$ is leaked by
$\mathrm{Leak}(A_{+},A_{-})$ on all $A_{-}$ separable from $A_{+}$.

  3. 3.

Nothing additional is leaked on $A_{-}={\mathcal{C}}^{*}(A_{+})$,
i.e.,
$\mathrm{Leak}(A_{+},{\mathcal{C}}^{*}(A_{+}))=A_{+}\cup{\mathcal{C}}^{*}(A_{+})$.
This claim will be argued separately by Theorem 7, below.

These claims combine to give the theorem as follows. In the protocol,
$A_{+}^{\prime}\subset S_{+}$ and $A_{-}^{\prime}\subset S_{-}$. By the first
claim we have
$\mathrm{Leak}(A_{+}^{\prime},A_{-}^{\prime})\supset\mathrm{Leak}(S_{+},A_{-}^{\prime})$.
However, $\mathrm{Leak}(S_{+},A_{-}^{\prime})\supset S_{-}\cup A_{-}^{\prime}$
and by the second claim
$\mathrm{Leak}(S_{+},A_{-}^{\prime})\supset{\mathcal{C}}^{*}(S_{+})$;
thus, $\mathrm{Leak}(S_{+},A_{-}^{\prime})\supset S_{-}\cup
A_{-}^{\prime}\cup{\mathcal{C}}^{*}(S_{+})$ which, of course, is a superset of
$S_{+}\cup{\mathcal{C}}^{*}(S_{+})$ which is equal to
$\mathrm{Leak}(S_{+},{\mathcal{C}}^{*}(S_{+}))$ by the third claim. This
latter minimal outcome is obtained by truthtelling. ∎

$-$$-$$-$$-$$-$$-$$-$$+$$+$$+$$+$ $-$$-$$-$$-$$-$$-$$-$$+$$+$$+$$+$
$-$$-$$-$$-$$-$$-$$-$$+$$+$$+$$+$

Figure 2: Left: Extreme separating hyperplanes are depicted. Center: all
separating hyperplanes are depicted. Right: the space
$\text{Safe}(A_{+},A_{-})$ is depicted where $A_{+}=S_{+}$ and
$A_{-}={\mathcal{C}}^{*}(S_{+})$ are the circled minuses. Note that
$\text{Verts}(\text{Safe}(A_{+},A_{-}))={\mathcal{C}}^{*}(S_{+})$. All circled
points are disclosed by the protocol when Alice reports $A_{+}=S_{+}$.

In the remainder of this section we prove equation (1) as Theorem 7.

######  Theorem 7.

For any $A_{+}\subset S$,
$\mathrm{Leak}(A_{+},{\mathcal{C}}^{*}(A_{+}))=A_{+}\cup{\mathcal{C}}^{*}(A_{+}).$

We have already argued that
$\mathrm{Leak}(A_{+},{\mathcal{C}}^{*}(A_{+}))\supset
A_{+}\cup{\mathcal{C}}^{*}(A_{+})$, it suffices to show that no other points
in $x\in S\setminus A_{+}\setminus{\mathcal{C}}^{*}(A_{+})$ are in
$\mathrm{Leak}(A_{+},{\mathcal{C}}^{*}(A_{+}))$. To do so, we identify from
$A_{+}$ a polyhedron $S^{\prime}$ that contains all of $S\setminus A_{+}$ and
show that (a) its vertices $V^{\prime}$ are exactly ${\mathcal{C}}^{*}(A_{+})$
and (b) $\mathrm{Leak}(A_{+},V^{\prime})=A_{+}+V^{\prime}$. Specifically, when
the vertices of this polyhedron are disclosed, the other negative points,
which are all within the polyhedron, are not leaked.

The polyhedron, $\text{Safe}(A_{+},A_{-})$ is defined as follows. Denote the
maximum in direction $d\in{\mathbb{R}}^{n}$ in a set $X$ by
$\max_{d}(X)=\max_{x\in X}d\cdot x$ and, respectively, the minimum by
$\min_{d}(X)$. Denote the (weakly) separating directions (See Figure 2) for
linearly separable points $A_{+}$ and $A_{-}$ by ${\mathcal{D}}(A_{+},A_{-})$
defined as

${\mathcal{D}}(A_{+},A_{-})=\\{d\in{\mathbb{R}}^{n}:\max\nolimits_{d}(A_{-})\leq\min\nolimits_{d}(A_{+})\\}.$
(2)

Define the convex subspace of points (a polyhedron) that would not be leaked
by disclosing $A_{+}\sqcup A_{-}$ as safe points (see Figure 2) and denote
this subspace by

$\text{Safe}(A_{+},A_{-})=\\{x\in{\mathbb{R}}^{n}:\forall
d\in{\mathcal{D}}(A_{+},A_{-}),d\cdot x\leq\max\nolimits_{d}(A_{-})\\}.$ (3)

I.e., a point is safe if in all separating directions there is a negative
point disclosed in $A_{-}$ that is at least as big (in this direction).

In what follows $\text{Verts}(X)$ denotes the vertices of convex set $X$;
these are the points that are unique maximizers in any direction. The
following lemma extends the fundamental theorem of linear programming to
polyhedra like $\text{Safe}(A_{+},A_{-})$ that are defined by the separating
hyperplanes between finite point sets. It shows that, if it is finite, the
optimal point in some direction is attained at a vertex. Recall that the
definition of separable for $A_{+}\sqcup A_{-}$ is strict. This strictness is
important. For example if all points in $A_{+}$ and $A_{-}$ lie on the same
hyperplane then $A_{+}$ is weakly on one side and $A_{-}$ is weakly on the
other, in a sense, they are weakly separated. In this case,
$\text{Safe}(A_{+},A_{-})$ is a halfspace and halfspaces have no vertices.
Moreover, if $S_{+}\sqcup S_{-}$ are on the same hyperplane then there are no
critical points ${\mathcal{C}}^{*}(S_{+})=\emptyset$. Thus, the strictness of
separation will play an important role in the proof of the main theorem.

######  Lemma 8.

For separable $A_{+}\sqcup A_{-}$ and $S^{\prime}=\text{Safe}(A_{+},A_{-})$,
if direction $d\in{\mathbb{R}}^{n}$ has a finite optimizer in $S^{\prime}$
then $d$ is optimized in $S^{\prime}$ at a vertex
$v\in\text{Verts}(S^{\prime})$.

###### Proof.

The proof follows because $\text{Safe}(A_{+},A_{-})$ does not contain a line
(of infinite length) and the fundamental theorem of linear programming which
states that for polyhedra that do not contain any line, every direction with a
finite optimizer is optimized at a vertex (see Theorems 2.6 and 2.7 in
Bertsimas and Tsitsiklis,, 1997).

Suppose the convex hulls of $A_{+}$ and $A_{-}$ are strictly separated at
distance $2\varepsilon>0$ apart and consider a hyperplane $h$ that separates
them with distance $\varepsilon$ from each. Because $A_{+}$ and $A_{-}$ are
both finite, their convex hulls are bounded and it is possible to rotate $h$
small amount in any direction while still separating $A_{+}$ and $A_{-}$. A
line intersects a hyperplane if and only if the line and hyperplane are not
parallel. For any line, one of the small rotations of $h$ is not parallel and,
thus, is intersecting. This line, therefore, does not lie completely within
$\text{Safe}(A_{+},A_{-})$. ∎

We now observe that ${\mathcal{D}}$ and Safe behave the same way on second
parameter given by any of $A_{-}$, $S^{\prime}=\text{Safe}(A_{+},A_{-})$, and
$\text{Verts}(S^{\prime})$.

######  Lemma 9.

Let $S^{\prime}=\text{Safe}(A_{+},A_{-})$, then

  * •

${\mathcal{D}}(A_{+},A_{-})={\mathcal{D}}(A_{+},S^{\prime})={\mathcal{D}}(A_{+},\text{Verts}(S^{\prime}))$,
and

  * •

$\max_{d}(A_{-})=\max_{d}(S^{\prime})=\max_{d}(\text{Verts}(S^{\prime}))$ for
all directions $d\in{\mathcal{D}}(A_{+},A_{-})$.

###### Proof.

For the first bullet: For the first equality, all points in $A_{-}$ are safe
so $S^{\prime}\supset A_{-}$. ${\mathcal{D}}(A_{+},\cdot)$ is bigger when its
second argument is smaller. But every $d\in{\mathcal{D}}(A_{+},A_{-})$ is also
in ${\mathcal{D}}(A_{+},S^{\prime})$ as the only points we add in $S^{\prime}$
are smaller than the largest point in $A_{+}$ in direction $d$. For the second
equality, Lemma 8 implies
${\mathcal{D}}(A_{+},S^{\prime})={\mathcal{D}}(A_{+},\text{Verts}(S^{\prime}))$.

For the second bullet: By the definition of safe,
$\max_{d}(A_{-})=\max_{d}(S^{\prime})$. Specifically, all points we add are
worse than points in $A_{-}$ in all relevant directions, but points in $A_{-}$
are also contained in $S^{\prime}$ so the maximum values over these sets in
direction $d$ direction are equal. Lemma 8 implies
$\max_{d}(S^{\prime})=\max_{d}(\text{Verts}(S^{\prime}))$. ∎

######  Corollary 10.

Let $S^{\prime}=\text{Safe}(A_{+},A_{-})$, then

$\text{Safe}(A_{+},A_{-})=\text{Safe}(A_{+},S^{\prime})=\text{Safe}(A_{+},\text{Verts}(S^{\prime})).$

###### Proof.

By Lemma 9 all the terms in the definition of Safe that depend on the second
parameter are the same. ∎

We conclude that if the vertices of Safe are disclosed, then no other negative
points are leaked.

######  Lemma 11.

For $S^{\prime}=\text{Safe}(A_{+},S\setminus A_{+})$ and
$V^{\prime}=\text{Verts}(S^{\prime})$, then

$\mathrm{Leak}(A_{+},V^{\prime})=A_{+}\cup V^{\prime}.$

###### Proof.

$A_{+}\cup V^{\prime}$ are leaked by definition. By Corollary 10,
$\text{Safe}(A_{+},V^{\prime})=\text{Safe}(A_{+},S\setminus A_{+})$. By the
definition of Safe, no other points in $\text{Safe}(A_{+},S\setminus
A_{+})\supset S\setminus A_{+}$ are leaked. ∎

With a view towards characterizing the vertices of Safe, the following lemma
shows that all directions with finite maximizers within Safe are contained in
${\mathcal{D}}$. In what follows $\mathrm{cone}(X)$ denotes the set of points
obtained by taking non-negative linear combinations of points in $X$. A set
$X$ is a convex cone if and only if $\mathrm{cone}(X)=X$; it is said to be
finitely generated if there exists a finite set of points $v_{1},\dots,v_{m}$
such that $X=\mathrm{cone}(\\{v_{1},\dots,v_{m}\\})$.

######  Lemma 12.

For any $A_{+},A_{-}$, ${\mathcal{D}}(A_{+},A_{-})$ is a convex cone. Moreover
for any direction $d\in\mathbb{R}^{n}$,
$\max_{x\in\text{Safe}(A_{+},A_{-})}d\cdot x$ is finite if and only if
$d\in{\mathcal{D}}(A_{+},A_{-})$.

###### Proof.

We first observe that ${\mathcal{D}}(A_{+},A_{-})$ defined in (2) can
equivalently be described as

${\mathcal{D}}(A_{+},A_{-})=\big{\\{}d:\forall a_{-}\in A_{-},a_{+}\in
A_{+},~{}d\cdot(a_{-}-a_{+})\leqslant 0\big{\\}},$ (4)

which corresponds to the solution set of a system of homogenous linear
inequalities. Hence ${\mathcal{D}}(A_{+},A_{-})$ is a convex cone since it is
closed under non-negative combinations.

We now prove the second part. One direction is easy: if
$d\in{\mathcal{D}}(A_{+},A_{-})$, then by the definition of Safe, we have
$\max_{x\in\text{Safe}(A_{+},A_{-})}\leqslant\max_{d}(A_{-})$ which is
bounded.

The other direction is more challenging and involves proving that the every
direction with a finite maximizer over $\text{Safe}(A_{+},A_{-})$ is in
${\mathcal{D}}(A_{+},A_{-})$. We would like to use linear programming (LP)
duality to prove that every direction is in the cone
${\mathcal{D}}(A_{+},A_{-})$. However, it is not clear that Safe is a
polyhedron to apply LP duality i.e., described by a finite set of linear
inequalities. Note that from (4), we see that ${\mathcal{D}}(A_{+},A_{-})$ is
described by a finite number of constraints. Hence by Weyl’s theorem on
polyhedral cones (see Schrijver, (1999)), ${\mathcal{D}}(A_{+},A_{-})$ is also
a finitely generated cone. However this does not suffice since the constraint
for each direction is of the form $d\cdot x\leqslant\max_{d}(A_{-})$. 222For
example even if $d=v_{1}+v_{2}$, the RHS of the constraint $\max_{d}(A_{-})$
could be smaller than $\max_{v_{1}}(A_{-})+\max_{v_{2}}(A_{-})$; hence some of
the constraints that define Safe are not necessarily implied by constraints on
just the generators of the cone ${\mathcal{D}}(A_{+},A_{-})$.

We first show that Safe can indeed be described by a finite number of linear
inequalities, and then use LP duality to complete the argument. Let
$\ell=|A_{-}|$ and $A_{-}=\\{a_{1},a_{2},\dots,a_{\ell}\\}$. We define convex
sets ${\mathcal{D}}_{i}$ and $\text{Safe}_{i}$ (here we suppress the arguments
$A_{+},A_{-}$ for easier notation) as follows :

$\displaystyle\forall i\in[\ell],~{}{\mathcal{D}}_{i}$
$\displaystyle\coloneqq\\{d\in{\mathcal{D}}(A_{+},A_{-}):d\cdot
a_{i}=\max_{d}(A_{-})\\}.$ (5) $\displaystyle\text{Safe}_{i}$
$\displaystyle\coloneqq\Big{\\{}x:\forall d\in{\mathcal{D}}_{i},~{}d\cdot
x\leqslant d\cdot a_{i}\Big{\\}}$ (6) $\displaystyle\text{Then,
}\text{Safe}(A_{+},A_{-})$
$\displaystyle=\bigcap_{i\in[\ell]}\text{Safe}_{i}.$ (7)

We now show that each of the convex sets $\text{Safe}_{i}$ (and hence Safe) is
polyhedral i.e., described by a finite set of constraints. For each
$i\in[\ell]$, ${\mathcal{D}}_{i}$ is also a convex cone that is finitely
generated. This is because ${\mathcal{D}}_{i}$ is described exactly by the
finite set of linear constraints as ${\mathcal{D}}_{i}=\\{d:\forall
j\in[\ell],~{}d\cdot(a_{j}-a_{i})\leqslant 0\\}$. Hence by the Weyl theorem
for polyhedral cone duality (see Schrijver, (1999)), there exists finite
$r_{i}\in\mathbb{N}$ such that the set of vectors $v_{i1},\dots,v_{ir_{i}}$
such that ${\mathcal{D}}_{i}=\mathrm{cone}(v_{i1},\dots,v_{ir_{i}})$. Now we
see that

$\text{Safe}_{i}=\\{x:\forall j\in[r_{i}],~{}v_{ij}\cdot x\leqslant
v_{ij}\cdot a_{i}\\}.$ (8)

The subset inclusion in (8) is obvious. The other direction just follows
because $v_{i1},\dots,v_{ir_{i}}$ generate the cone. This shows that for each
$i\in[\ell]$, $\text{Safe}_{i}$ is polyhedral i.e., described by a finite set
of linear constraints. Hence from (7) we have

$\text{Safe}(A_{+},A_{-})=\\{x:\forall i\in[\ell],\forall
j\in[r_{i}],v_{ij}\cdot x\leqslant b_{ij}\\},$ (9)

which is described by a finite number of constraints
$r_{\text{tot}}\coloneqq\sum_{i=1}^{\ell}r_{i}$.

Finally, we now use linear programming duality to show that $d$ has a finite
maximum over Safe if and only if $d\in{\mathcal{D}}(A_{+},A_{-})$. Consider
the linear program (LP) given by $\max_{x\in\mathbb{R}^{n}}d\cdot x$ such that
$x$ satisfies the constraints in (9). By LP duality, this LP has a finite
maximum (i.e., bounded) if and only if its dual LP is feasible i.e., there
exists a non-negative vector $y\geqslant 0$ in $r_{\text{tot}}$ dimensions
with such that

$\sum_{i=1}^{\ell}\sum_{j=1}^{r_{i}}y_{ij}v_{ij}=c.$

In other words, if $\max_{d}(\text{Safe}(A_{+},A_{-}))$ is finite (bounded),
then
$d\in\mathrm{cone}(\\{v_{ij}:i\in[\ell],j\in[r_{i}]\\})\subset{\mathcal{D}}(A_{+},A_{-})$.
∎

Now we show that the vertices of Safe are equal to the critical points.

######  Lemma 13.

For any linearly separable set $S_{+}\sqcup S_{-}=S$, the critical points are
the vertices of the safe points, i.e.,

${\mathcal{C}}^{*}(S_{+})=\text{Verts}(\text{Safe}(S_{+},S_{-})).$

###### Proof.

Let $S^{\prime}=\text{Safe}(S_{+},S_{-})$ and
$V^{\prime}=\text{Verts}(S^{\prime})$. The proof follows from the following
two statements that we establish:

$\displaystyle V^{\prime}$ $\displaystyle\subseteq S_{-}$ (10) $\displaystyle
V^{\prime}$ $\displaystyle\subseteq{\mathcal{C}}^{*}(S_{+}).$ (11)
$\displaystyle V^{\prime}$ $\displaystyle\supseteq{\mathcal{C}}^{*}(S_{+}).$
(12)

Consider any vertex $x^{\prime}\in S^{\prime}$, and let
$d^{\prime}\in\mathbb{R}^{n}$ be the direction that it uniquely maximizes
within $S^{\prime}$. From Lemma 12 we have that
$d^{\prime}\in{\mathcal{D}}(S_{+},S_{-})$ since $d^{\prime}$ has a finite
maximizer in $\text{Safe}(S_{+},S_{-})$. From the definition of
$\text{Safe}(S_{+},S_{-})$, for every direction
$d\in{\mathcal{D}}(S_{+},S_{-})$ (and in particular $d^{\prime}$), there
exists an element of $S_{-}$ that achieves $\max_{x\in S^{\prime}}d\cdot x$.
Hence $x^{\prime}\in S_{-}$ since $x^{\prime}$ is the unique maximizer in
$S^{\prime}$. This establishes (10).

We now show $V^{\prime}\subseteq{\mathcal{C}}^{*}(S_{+})$. As before let
$x^{\prime}\in V^{\prime}$ and $d^{\prime}$ be a direction that it uniquely
maximizes within $S^{\prime}\supseteq S_{-}$. Hence there is a linear
classifier consistent with $S_{+}\cup\\{x^{\prime}\\}$ labeled positive, and
$S_{-}\setminus\\{x^{\prime}\\}$ labeled negative. Hence
$x^{\prime}\in{\mathcal{C}}^{*}(S_{+})$ as required for (11).

Finally to show (12), suppose $x^{\prime}\in{\mathcal{C}}^{*}(S_{+})$. By
definition, there is a linear classifier separating
$S_{+}\cup\\{x^{\prime}\\}$ (as positives) and
$S_{-}\setminus\\{x^{\prime}\\}$ (as negatives). Moreover, $S_{+}$ and $S_{-}$
are also separable (in particular it labels $x^{\prime}\in S_{-}$ as a
negative example). Hence by convexity, there exists a direction $d^{\prime}$
such that $x^{\prime}$ is the unique maximizer among the $S_{-}$, and
$d^{\prime}\cdot x^{\prime}<\min_{d}(S_{+})$. Hence
$d^{\prime}\in{\mathcal{D}}(S_{+},S_{-})$ and from (10), we have that
$x^{\prime}$ is a unique maximizer in $S^{\prime}$ of $d^{\prime}$. Hence
(12). This concludes the proof. ∎

###### Proof of Theorem 7.

By Lemma 13, the critical points of ${\mathcal{C}}^{*}(S_{+})$ are equal to
the vertices of $\text{Safe}(S_{+},S_{-})$. Plugging this equivalence into
Lemma 11, we have
$\mathrm{Leak}(S_{+},{\mathcal{C}}^{*}(S_{+}))=S_{+}\cup{\mathcal{C}}^{*}(S_{+})$.
∎

###  2.1 Truthful Protocols

In protocols for e-discovery Alice desires to (a) hide positive data points
and (b) reduce the disclosure of negative data points. In a correct protocol,
all positive data points are revealed, thus, Alice faces only the problem of
reducing the discosure of negative data points. Following the standard
framework from mechanism design in economics and computer science, we define
the protocol properties of direct and truthful and provide a revelation
principle. For this discussion we view Alice’s interaction in the protocol.
Note that all correct protocols disclose all of the positive points $S_{+}$;
thus, minimizing the number of points disclosed in a correct protocol is
equivalent to minimizing the number of negative points disclosed.

######  Definition 14.

Given a known set of points $S$, a direct protocol ${\mathcal{M}}:2^{S}\times
2^{S}\to 2^{S}$ maps the sets of alleged positives (of Alice) and true
positives (as can be verified by Bob) to a set of disclosed points (to Bob).

######  Definition 15.

A direct protocol is truthful if for all $S_{+}\sqcup S_{-}=S$, Alice’s
optimal strategy is to truthfully report $S_{+}$.

######  Proposition 16 (Revelation Principle).

For any protocol ${\mathcal{M}}$ and optimal strategy $\sigma$ of Alice
mapping positive points to messages in the protocol (which minimizes the total
number of data points disclosed), there is a truthful and direct protocol
${\mathcal{M}}^{R}$ with the same outcome under truthtelling (as under
protocol ${\mathcal{M}}$ with strategy $\sigma$).

###### Proof.

Define the revelation protocol as ${\mathcal{M}}^{R}(A_{+},S_{+})$ as follows:

  1. 1.

Simulate strategy $\sigma(A_{+})$ in ${\mathcal{M}}$ assuming $A_{+}$ are the
true positives.

  2. 2.

Given the transcript of this simulation, attempt the same interaction as
$\sigma(A_{+})$ with the real true positives $S_{+}$.

  3. 3.

If the behavior of ${\mathcal{M}}$ with true positives $S_{+}$ is ever
deviates from the simulated transcript, then reveal the full dataset $S$ to
Bob. (Otherwise, the outcome is identical to
${\mathcal{M}}(\sigma(A_{+}),A_{+})$.)

We now argue that the optimal strategy in ${\mathcal{M}}^{R}$ is to report
$A_{+}=S_{+}$. Suppose some $A_{+}\neq S_{+}$ gives a strictly better outcome.
Note: it must be that the outcomes of ${\mathcal{M}}(\sigma(A_{+}),A_{+})$ and
${\mathcal{M}}(\sigma(A_{+}),S_{+})$ are the same, otherwise, the difference
would be detected and the full set $S$ would be disclosed to Bob. In this
case, however, with true positives $S_{+}$ following $\sigma(A_{+})$ rather
than $\sigma(S_{+})$ in ${\mathcal{M}}$ gives a strictly better outcome, which
contradicts the optimality of $\sigma$ for ${\mathcal{M}}$. ∎

###  2.2 Minimal Protocol

In this section we prove that every correct protocol discloses the critical
points ${\mathcal{C}}^{*}(S_{+})$ on dataset $S_{+}\sqcup S_{-}=S$; thus, the
critical points protocol is optimal.

######  Theorem 17.

Every correct protocol ${\mathcal{M}}$ on dataset $S_{+}\sqcup S_{-}=S$
discloses a set of points that contains ${\mathcal{C}}^{*}(S_{+})$.

###### Proof.

By Proposition 16, it is without loss to assume ${\mathcal{M}}$ is truthful.
By the definition of truthful protocols, Alice cannot have fewer points
disclosed by reporting non-truthfully. Suppose for a contradiction that a
point $x^{*}\in{\mathcal{C}}^{*}(S_{+})$ is not disclosed in $S_{+}\sqcup
A_{-}={\mathcal{M}}(S_{+},S_{+})$, i.e., $x^{*}\in S_{-}$ but $x^{*}\not\in
A_{-}$.

Recall ${\mathcal{C}}^{*}(S_{+})=\\{x\in S:\mathrm{Leak}(S_{+},S\setminus
S_{+}\setminus\\{x\\})\\}$ is the points that are each labeled as positive by
some consistent classifier with respect to positives $S_{+}$ and negatives
$S\setminus S_{+}\setminus\\{x\\}$. Monotonicity of $\mathrm{Leak}$ implies
that $x^{*}$ is in $\mathrm{Leak}(S_{+},A_{-})$ as $A_{-}\subseteq S\setminus
S_{+}\setminus\\{x^{*}\\}$. By the definition of $\mathrm{Leak}$ there is a
consistent classifier that labels $S_{+}\cup\\{x^{*}\\}$ as positive and
$A_{-}$ as negative.

Since $x^{*}$ is in $\mathrm{Leak}(S_{+},A_{-})$, there exists a separating
hyperplane for $S_{+}\cup X$ (with $X\ni x^{*}$) and the remaining points
(which contains $A_{-}$). Thus, Lemma 18 (below) can be applied where
$S_{+}\cup X$ is separable but $x^{*}\in X$ is not disclosed on
${\mathcal{M}}(S_{+},S_{+}\cup X)$, a contradiction to the correctness of
${\mathcal{M}}$ as $x^{*}\in X$ is considered a positive point in the
execution of ${\mathcal{M}}(S_{+},S_{+}\cup X)$ ∎

######  Lemma 18.

In any direct protocol ${\mathcal{M}}$, if $X\sqcup S_{+}$ is separable and
$X\cap{\mathcal{M}}(A_{+},S_{+})=\emptyset$ (i.e., $X$ is not disclosed by
${\mathcal{M}}$ with $X$ are negative) then
${\mathcal{M}}(A_{+},S_{+})={\mathcal{M}}(A_{+},S_{+}\cup X)$ (i.e.,
${\mathcal{M}}$ on $A_{+}$ discloses the same points when points $X$ are all
positive or all negative).

###### Proof.

Separability of $X\cup S_{+}$ implies that ${\mathcal{M}}(A_{+},S_{+}\cup X)$
is well defined. By definition a protocol is only a function of its input, in
this case, $A_{+}$ and the points that it discloses. Since $X$ is not
disclosed in ${\mathcal{M}}(A_{+},S_{+})$ then ${\mathcal{M}}(A_{+},S_{+}\cup
X)$ has the same result, and $X$ is not disclosed by it as well. ∎

##  3 Machine Learning Guarantees

In this section we consider the machine learning framework related to multi-
party e-discovery (MPeD). We show how the protocol defined in the previous
section (for linear classification), when instantiated with any training
algorithm that satisfies a natural property, that we call the independence of
irrelevant alternatives (IIA), achieves the same learning guarantees as
single-party e-discovery (SPeD). We provide a reduction from MPeD to SPeD;
this shows that our protocol suffers no loss in generalization or sample
complexity compared to the standard single-party setting. Finally, we
instantiate this reduction using the classic support vector machine (SVM)
algorithm, by showing that it satisfies the IIA property.

###  3.1 Machine learning framework

We start by recalling the single party e-discovery (SPeD) framework which
corresponds to a standard machine learning pipeline, involving a training
algorithm run on the training set $S$ to find a good classifier $\hat{h}$, and
then applying this classifier on the entire dataset $U$.
$\text{Alg}_{\mathcal{H}}$ will denote a learning algorithm for the hypothesis
class $\mathcal{H}$ that takes in labeled samples as input, and outputs a
hypothesis in $\mathcal{H}$ consistent with the labeled samples.

Algorithm 2 ML framework for Single-Party e-Discovery (SPeD)

1:Unlabeled dataset $U$ and the hypothesis class $\mathcal{H}$.

2:Data points with positive labels $U_{+}\subseteq U$.

3:Sample the training data set $S\subseteq U$ (likely with $|S|\ll|U|$ ).

4:(Hand-)Label $S$ to get $S_{+}$ and $S_{-}$.

5:Use $\text{Alg}_{\mathcal{H}}$ to learn classifier $\hat{h}\in\mathcal{H}$
on the labeled data with positives $S_{+}$ and negatives $S_{-}$.

6:Apply classifier $\hat{h}$ on $U$ to get $U_{+}$

In the Multi-Party e-Discovery (MPeD) framework, there are three parties
Alice, Bob and Trent that perform different functions. Alice first sends the
entire dataset $U$ to Trent. Trent generates the training samples $S\subseteq
U$ and sends it to Alice. Alice, Trent and Bob engage in a protocol as in
Section 2. At the end of the protocol, Bob is given a set of positive examples
$S^{\prime}_{+}$ (which is hopefully $S_{+}$) and some other negative samples
$S^{\prime}_{-}$ (which is hopefully much smaller than $S_{-}$), which he then
uses to train a classifier $\hat{h}$ that is used to classify the entire
dataset $U$.

Algorithm 3 ML framework for Multi-Party e-Discovery (MPeD)

1:Alice has unlabeled data points $U$. The hypothesis class is $\mathcal{H}$
is known publicly.

2:Bob receives data points with positive labels $U_{+}\subseteq U$.

3:Alice sends entire dataset $U$ to Trent.

4:Trentsamples the training data set $S\subseteq U$ (likely with $|S|\ll|U|$).

5:Trent sends $S$ to Alice.

6:Alice, Trent, Bob participate in the critical points protocol (Algorithm 1)
of Section 2. At the end of it, Bob receives labeled samples $S^{\prime}_{+}$
and $S^{\prime}_{-}$.

7:Bob uses $\text{Alg}_{\mathcal{H}}$ to learn a classifier
$\hat{h}\in\mathcal{H}$ consistent with the labeled data $S^{\prime}_{+}$ and
$S^{\prime}_{-}$, and sends $\hat{h}$ to Trent.

8:Trent checks the consistency of $\hat{h}$ with
$S^{\prime}_{+},S^{\prime}_{-}$ and applies $\hat{h}$ on $U$ to get $U_{+}$
and sends it to Bob.

We want the classifier that is output in multi-party ML framework to be as
good as the classifier in the single-party setting, irrespective of Alice’s
actions; ideally, it also maintains the same statistical properties (e.g.,
sample complexity) as the single-party setting. However, the choice of the
learning algorithm is important, since the algorithm is trained on a different
set of labeled samples ($(S^{\prime}_{+},S^{\prime}_{-})$ as opposed to
$(S_{+},S_{-})$). The following property of the learning algorithm will play a
crucial role. Recall that $\mathcal{H}(S_{+},S_{-})$ denotes the set of
hypothesis in $\mathcal{H}$ consistent with the labeled data given by
positives $S_{+}$ and negatives $S_{-}$; also for a linearly separable data
set $S_{+}\sqcup S_{-}$, the critical points are denoted by
${\mathcal{C}}^{*}(S_{+})$.

######  Definition 19.

(IIA property) A learning algorithm $\text{Alg}_{\mathcal{H}}$ is said to
satisfy _independence of irrelevant alternatives_ (IIA) if for any $S_{+}$ and
$S_{-}\supseteq{\mathcal{C}}^{*}(S_{+})$ that is separable and for any
$S^{\prime}_{-}\supseteq{\mathcal{C}}^{*}(S_{+})$, we have that
$\text{Alg}_{\mathcal{H}}(S_{+},S_{-})=\text{Alg}_{\mathcal{H}}(S_{+},S^{\prime}_{-})$.

One can also define a potentially stronger notion of IIA where
$\mathcal{H}(S_{+},S_{-})=\mathcal{H}(T_{+},T_{-})\implies\text{Alg}_{\mathcal{H}}(S_{+},S_{-})=\text{Alg}_{\mathcal{H}}(T_{+},T_{-})$,
but the above weaker notion suffices for our purposes.

We focus on the setting where the data set $U$ is linearly separable i.e.,
$\mathcal{H}$ is the set of linear classifiers, and there is an
$h^{*}\in\mathcal{H}$ that is consistent with the true labels of $U$. We now
show that we can use our protocol from Section 2 in Step 4 of the above
framework, along with any algorithm that satisfies the IIA property to achieve
the same statistical guarantees as the single-party ML setting. Note that the
IIA property pertains only to the learning algorithm that is employed by Bob
in Step 6 of the Algorithm 3.

######  Theorem 20.

Suppose the data set $U$ is linearly separable and the learning algorithm
$\text{Alg}_{\mathcal{H}}$ satisfies the IIA property. Then with the same
sampling procedure (to produce $S$), the outputs of Algorithm 2 (SPeD) and
Algorithm 3 (MPeD) are identical.

We remark that there can be randomness in the sampling procedure and potential
random choices in the learning algorithm $\text{Alg}_{\mathcal{H}}$; so
$U_{+}$ is a random set. The guarantee of Theorem 20 is that the distributions
of $U_{+}$ are the same. Alternatively, fixing the random choices in the
sampling, and in the algorithm $\text{Alg}_{\mathcal{H}}$, the set $U_{+}$ is
the same.

###### Proof of Theorem 20.

The proof follows easily by combining the guarantees of Theorem 6 and the IIA
property of $\text{Alg}_{\mathcal{H}}$. First, from Theorem 6, we know that
irrespective of the actions of Alice, Bob receives $S_{+}$ and $C^{*}(S_{+})$,
where $C^{*}(S_{+})$ denotes the critical points. Hence, from the IIA property
of $\text{Alg}_{\mathcal{H}}$, the classifier $\hat{h}$ that is produced is
identical (for the same random choices of the algorithm
$\text{Alg}_{\mathcal{H}}$. Hence $U_{+}$ is identical in both cases. ∎

For a given linearly separable dataset there may be several potential linear
classifiers consistent with it (and so too for $(S_{+},S_{-})$). Furthermore,
not all algorithms for linear classification may satisfy the IIA property
(e.g., the popular Perceptron algorithm does not satisfy IIA). However, the
well-known SVM algorithm that finds the maximum margin classifier for the
given linearly-separable dataset satisfies the IIA property (see Lemma 24 in
the next section). Hence we can instantiate Theorem 20 for linear classifiers
by using the SVM algorithm as follows. (The proof just follows by combining
Theorem 20 and Lemma 24.)

######  Theorem 21.

Suppose the data set $U$ is linearly separable and the learning algorithm
$\text{Alg}_{\mathcal{H}}$ is the SVM algorithm given in Section 3.2. Then
with the same sampling procedure (to produce $S$), the outputs of Algorithm 2
(SPeD) and Algorithm 3 (MPeD) are identical.

This theorem shows that the multi-party e-discovery protocol given in
Algorithm 3 incurs no loss compared to the single-party setting (Algorithm 2)
in terms of properties of the output classifier $\hat{h}$. In particular, any
statistical property (like test error or generalization guarantee) of the
classifier $\hat{h}$ transfer over to the multi-party setting with no loss in
the statistical efficiency. See Section 4 for the extension to kernel
classifiers.

###  3.2 Support Vector Machines (SVM) and Properties

We now describe the support vector machine (SVM) algorithm which is used for
learning linear classifiers for a given set of labeled samples in high-
dimensional spaces. We will also prove the IIA property and see some facts
about the SVM algorithm that will be useful in the next section.

The setting is as follows. We are given a set of labeled samples
$T=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\\}\subset\mathbb{R}^{n}\times\\{\pm
1\\}$. The goal is to find a linear classifier
$(w,b)\in\mathbb{R}^{n}\times\mathbb{R}$ such that $\forall
i\in[m],~{}y_{i}({w\cdot x_{i}}+b)>0$ if such a classifier exists i.e., it is
linearly separable.

The Hard-SVM algorithm finds the linear classifier that separates the positive
and negative samples with the largest possible margin (if the data is linearly
separable). For a classifier $(w,b)$ with $\|w\|_{2}=1$, the margin of a
sample $(x,y)$ is the distance between a point $x$ and the hyperplane $(w,b)$
and is given by $\max\big{\\{}y({w\cdot x}+b),0\big{\\}}$. Note that a linear
classifier does not change by scaling. The following claim shows that the
Hard-SVM problem of finding maximum margin linear classifier can be
reformulated in either of the following two ways.

######  Fact 22.

(See e.g., chapter 15 of Shalev-Shwartz and Ben-David,, 2014) Given a set of
linearly separable labeled samples
$\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\\}\subset\mathbb{R}^{n}\times\\{\pm
1\\}$, consider the following optimization problems:

$\displaystyle w^{*},b^{*}$
$\displaystyle=\operatorname*{arg\,max}_{(w,b):\|w\|_{2}=1}\min_{i\in[m]}\lvert
w\cdot x_{i}+b\rvert$ (13) s.t. $\displaystyle\forall
i\in[m],~{}~{}y_{i}\big{(}w\cdot x_{i}+b\big{)}>0$ $\displaystyle
w^{\dagger},b^{\dagger}$
$\displaystyle=\operatorname*{arg\,min}_{(w,b)}\|w\|_{2}^{2}$ (14) s.t.
$\displaystyle\forall i\in[m],~{}~{}y_{i}\big{(}{w\cdot
x_{i}}+b\big{)}\geqslant 1.$

The optimization problems (13) and (14) are essentially equivalent, with the
optimizers related as
$w^{*}=\frac{w^{\dagger}}{\|w^{\dagger}\|_{2}},b^{*}=\frac{b^{\dagger}}{\|w^{\dagger}\|_{2}}$.
Moreover (14) is a convex program that can be solved in polynomial time.

While (13) more directly captures the maximum margin formulation, (14) more
clearly illustrates why it is a convex program that can be solved in
polynomial time. When the data is not linearly separable, the linear
constraints that define the convex program in (14) just become infeasible.

We have the following characterization that the solution of the Hard-SVM
problem can be expressed as a linear combination of points which are all at
the minimum distance (of exactly $1/\|w^{\dagger}\|_{2}$) from the separating
hyperplane (these points are called the support vectors). Note that the
optimal solution of (14) when it exists, is always unique (the objective is
strongly convex).

######  Fact 23.

(Theorem 15.8 in Shalev-Shwartz and Ben-David,, 2014)] Let
$w^{\dagger},b^{\dagger}$ denote the optimal solution of (14), and let
$I=\\{i\in[m]:y_{i}(w^{\dagger}\cdot x_{i})=1\\}$. Then there exists
coefficients $\alpha_{1},\dots,\alpha_{m}\in\mathbb{R}$ such that
$w^{\dagger}=\sum_{i\in I}\alpha_{i}x_{i}$.

The above fact can be used to reformulate the objective (14) in terms of the
unknowns $\alpha_{1},\dots,\alpha_{m}$ and the inner products between the
points $\\{x_{i}\cdot x_{j}:i,j\in[m]\\}$ (as opposed to the points
$\\{x_{i}:i\in[m]\\}$ themselves).

######  Lemma 24.

(SVM satisfies IIA property) The Hard-SVM procedure given by (14) is IIA (as
per Definition 19) i.e., for any $S_{+}$ and $S^{\prime}_{-}\supseteq
C^{*}(S_{+})$ (so that
$\mathcal{H}(S_{+},S^{\prime}_{-})=\mathcal{H}(S_{+},S_{-})$), the solution
$w^{\prime},b^{\prime}$ on the labeled examples given by
$(S_{+},S^{\prime}_{-})$ is identical to the solution $w,b$ on the labeled
examples $(S_{+},S_{-})$.

We remark that SVM satisfies a stronger notion of IIA, where the positives can
also be a subset $S^{\prime}_{+}\subseteq S_{+}$ such that the set of
consistent hypothesis remains the same. However the above version suffices for
our purposes.

###### Proof.

Consider the SVM solution $w,b$ (for (14)) on labeled data $S_{+},S_{-}$. This
solution is unique: if there are two minimizing solutions
$(w,b),(w^{\prime},b^{\prime})$ then the solution
$(\tfrac{1}{2}(w+w^{\prime}),\tfrac{1}{2}(b+b^{\prime}))$ also satisfies all
the constraints of (14) but attains a smaller objective value due to strong
convexity.

Consider the classifier $w^{\prime},b^{\prime}$ that attains the optimum
margin for the dataset $S_{+},S^{\prime}_{-}$. From Corollary 10 (and Theorem
7) classifier $(w^{\prime},b^{\prime})\in\mathcal{H}(S_{+},S_{-})$. Moreover
the (minimum) margin over $S_{+},S_{-}$ is attained by a point in $S_{+}\cup
S^{\prime}_{-}$ i.e., $\min_{x\in S_{+}\cup S^{\prime}_{-}}|w^{\prime}\cdot
x+b^{\prime}|=\min_{x\in S_{+}\cup S_{-}}|w^{\prime}\cdot
x+b^{\prime}|\eqqcolon\tau$.333Note that not all of the support vectors from
Fact 23 need to be in $S_{+}\cup S^{\prime}_{-}$.  Suppose not. There exists a
point $x^{\prime}\notin S_{+}\cup S^{\prime}_{-}$ with label $y^{\prime}$ (say
$y^{\prime}=-1$) such that $y^{\prime}(w^{\prime}\cdot
x^{\prime}+b^{\prime})=\tau$, but for all labeled examples $(x,y)$ given by
$S_{+}\cup S^{\prime}_{-}$, $y(w^{\prime}\cdot x+b^{\prime})>\tau$. Then
$x^{\prime}\in S_{+}\cup C^{*}(S_{+})\subseteq S_{+}\cup S^{\prime}_{-}$ (if
$y=-1$, $x^{\prime}\in C^{*}(S_{+})$) which gives a contradiction.

Hence $w^{\prime},b^{\prime}$ also achieves the same margin on $S_{+},S_{-}$
(as it does on $S_{+},C^{*}(S_{+})$). This implies that
$w^{\prime},b^{\prime}$ is also a optimum margin classifier on $S_{+},S_{-}$
(since it had a larger margin than $w,b$ on $A^{*}_{+},A^{*}_{-}$). Since the
solution to (14) is unique, we conclude that $(w,b)=(w^{\prime},b^{\prime})$.
∎

##  4 Extensions to Kernel Classifiers

Our results for linear classifiers in the previous section naturally extend to
kernel-based classifiers like kernel support vector machines. Kernel-based
classifiers can be much more expressive than linear classifiers as they embed
the input space into a feature space that is high-dimensional (potentially
infinite dimensional), where the data is potentially linearly separable.
Popular kernels include the polynomial kernel, that can capture any polynomial
threshold function (a classifier of the form $\text{sign}(p(x))$ where $p(x)$
is any polynomial of $x$), radial basis kernels (e.g., Gaussian kernels) etc.

We start by recalling some notation and facts about kernels. In what follows,
$\psi:\mathcal{X}\to\mathcal{V}$ embeds points in the input space
$\mathcal{X}$ into a Hilbert space $\mathcal{V}$. The kernel function is given
by the inner product
$K(x,x^{\prime})=\langle\psi(x),\psi(x^{\prime})\rangle_{\mathcal{V}}$, and we
assume that this can be computed in polynomial time given $x,x^{\prime}$.
Given a set of points $x_{1},\dots,x_{m}\in\mathcal{X}$, the $m\times m$
matrix formed with the $(i,j)$th entry $K(x_{i},x_{j})$ is positive semi-
definite. The following standard theorem states that one can find the maximum
margin classifier in the feature space $\psi(\mathcal{X})$ for a given set of
$m$ samples, by solving a simpler convex optimization problem over $m$
dimensions.

######  Theorem 25 (see e.g., Chapter 16 of Shalev-Shwartz and Ben-David,
(2014)).

For a given set of samples
$(x_{1},y_{1}),\dots,(x_{m},y_{m})\in\mathcal{X}\times\\{\pm 1\\}$, consider
the Hard-SVM problem (or the maximum margin classifier problem):

$\min_{w\in\mathcal{V},b\in\mathbb{R}}\|w\|_{2}^{2},\text{ s.t. }~{}\forall
i\in[m],~{}~{}y_{i}\Big{(}{w\cdot\psi(x_{i})}+b\Big{)}\geqslant 1.$ (15)

An optimal solution $(w^{*},b^{*})$ to (15) can be obtained in polynomial time
by finding an optimal solution to the following convex optimization problem
and setting $w^{*}=\sum_{i=1}^{m}\alpha^{*}_{i}\psi(x_{i})$:

$\displaystyle(\alpha^{*},b^{*})$
$\displaystyle=\operatorname*{arg\,min}_{\alpha\in\mathbb{R}^{m},b\in\mathbb{R}}\sum_{i,j\in[m]}K(x_{i},x_{j})\alpha_{i}\alpha_{j},$
s.t. $\displaystyle\forall
i\in[m],~{}~{}y_{i}\Big{(}\sum_{j\in[m]}K(x_{i},x_{j})\alpha_{j}+b\Big{)}\geqslant
1.$ (16)

Moreover the corresponding linear classifier is given by
$h(x)=\text{sign}\big{(}\sum_{j\in[m]}\alpha_{j}K(x_{j},x)+b\big{)}$.

Our main observation is that implementing the protocol in the previous section
only involves solving a set of linear classification problems. These include
the computation of the set $C^{*}(A_{+})$ by Trent (one problem for each point
in $S_{-}$), and the computation of the set $\mathrm{Leak}(A_{+},A_{-})$ by
Trent (one problem for each point in $S$). These linear classification
problems are solved using the Hard-SVM problem (maximum margin linear
classifier), which also satisfies the IIA property. We can carry out the same
arguments as in the previous sections on the points
$\\{(\psi(x_{i}),y_{i}):i\in[m]\\}$ by only accessing inner products
$\\{\psi(x_{i})\cdot\psi(x_{j}):i,j\in[m]\\}$ (through the kernel function).
Hence from Theorem 25 we immediately obtain the generalization of our
guarantees to kernel-based classifiers.

######  Theorem 26.

Suppose a kernel function $K:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ is
specified as above and efficiently computable (and known to Alice, Bob and
Trent). Given a set of points $S=(S_{+},S_{-})$ that is realizable (w.r.t. to
linear classifiers over the space $\psi(\mathcal{X})$), there is a protocol
(the critical points protocol implemented using kernel SVM) that is correct,
minimal, computationally efficient and truthful. Moreover, if the data set $U$
is realizable (w.r.t. linear classifiers over the space $\psi(\mathcal{X})$),
Bob uses the kernel SVM algorithm in Step 6 of Algorithm 3 (MPeD), then the
outputs of Algorithm 2 (SPeD) and Algorithm 3 (MPeD) are identical assuming
the same sampling procedure (for generating $S$ from $U$).

##  5 Discussion and Open Questions

In this paper, we considered a multi-party classification problem that is
motivated by e-discovery. We designed a protocol (critical points protocol) in
the realizable setting of linear classifiers and kernel SVMs, that is correct,
minimal, computationally efficient and truthful. Moreover this protocol fits
into a machine learning framework along with any classifier that satisfies the
a natural property called IIA; we provide a reduction to the standard single-
party setting, thereby demonstrating that there is no loss in statistical
efficiency.

The most natural direction for future research is to generalize to the non-
realizable setting, where there is no perfect classifier from the hypothesis
class. Here we may need to relax our requirement of computational efficiency,
as the problem of learning a linear classifier in the non-realizable setting
(also called agnostic learning) is known to be computationally intractable
even in the single-party setting Shalev-Shwartz and Ben-David, (2014). However
one may be able to obtain efficient protocols assuming access to an efficient
(single-party) learning algorithm.

### Acknowledgements

This work began during the IDEAL Special Quarter on Data Science and Law
organized by Jason Hartline and Dan Linna. Many thanks to Dan Linna for legal
context and feedback on the project. The work was supported in part by NSF
award CCF-1934931.

## References

  * Bertsimas and Tsitsiklis, (1997) Bertsimas, D. and Tsitsiklis, J. (1997).  Introduction to linear optimization.  Athena Scientific.
  * Cormack and Grossman, (2014) Cormack, G. V. and Grossman, M. R. (2014).  Evaluation of machine-learning protocols for technology-assisted review in electronic discovery.  In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, pages 153–162.
  * Dwork et al., (2012) Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012).  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226.
  * Gelbach and Kobayashi, (2015) Gelbach, J. B. and Kobayashi, B. H. (2015).  The law and economics of proportionality in discovery.  Ga. L. Rev., 50:1093.
  * Goldreich et al., (1987) Goldreich, O., Micali, S., and Wigderson, A. (1987).  How to solve any protocol problem.  In Proc. of STOC.
  * Goldwasser et al., (2021) Goldwasser, S., Rothblum, G. N., Shafer, J., and Yehudayoff, A. (2021).  Interactive proofs for verifying machine learning.  In 12th Innovations in Theoretical Computer Science Conference. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Grossman and Cormack, (2010) Grossman, M. R. and Cormack, G. V. (2010).  Technology-assisted review in e-discovery can be more effective and more efficient than exhaustive manual review.  Rich. JL & Tech., 17:1.
  * Jacot et al., (2018) Jacot, A., Gabriel, F., and Hongler, C. (2018).  Neural tangent kernel: Convergence and generalization in neural networks.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 8580–8589, Red Hook, NY, USA. Curran Associates Inc.
  * Scholkopf and Smola, (2001) Scholkopf, B. and Smola, A. J. (2001).  Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond.  MIT Press, Cambridge, MA, USA.
  * Schrijver, (1999) Schrijver, A. (1999).  Theory of linear and integer programming.  In Wiley-Interscience series in discrete mathematics and optimization.
  * Shalev-Shwartz and Ben-David, (2014) Shalev-Shwartz, S. and Ben-David, S. (2014).  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press.
  * Yao, (1986) Yao, A. C.-C. (1986).  How to generate and exchange secrets.  In 27th Annual Symposium on Foundations of Computer Science, pages 162–167. IEEE.