SelectFormer in Data Markets: Privacy-Preserving and Efficient Data Selection for Transformers with Multi-Party Computation
Authors: Xu Ouyang
Felix Xiaozhu Lin
Yangfeng Ji
Venue: ICLR 2025 Poster (2025)
Keywords: Secure Multiparty Computation
Machine Learning
Efficiency
Transformer model
Primary area: infrastructure, software libraries, hardware, systems, etc.
TL;DR: Secure and fast data selection & appraisal over MPC (Multi-Party Computation), for training NLP/CV Transformer models

Abstract: Critical to a free data market is $ \textit{private data selection}$, i.e. the model owner selects and then appraises training data from the data owner before both parties commit to a transaction. To keep the data and model private, this process shall evaluate the target model to be trained over Multi-Party Computation (MPC). While prior work suggests that evaluating Transformer-based models over MPC is prohibitively expensive, this paper makes it practical for the purpose of data selection. Our contributions are three: (1) a new pipeline for private data selection over MPC; (2) emulating high-dimensional nonlinear operators with low-dimension MLPs, which are trained on a small sample of the data of interest; (3) scheduling MPC in a parallel, multiphase fashion. We evaluate our method on diverse Transformer models and NLP/CV benchmarks. Compared to directly evaluating the target model over MPC, our method reduces the delay from thousands of hours to tens of hours, while only seeing around 0.20% accuracy degradation from training with the selected data.

Published as a conference paper at ICLR 2025
SELECTFORMER IN DATA MARKETS: PRIVACY- PRESERVING AND EFFICIENT DATA SELECTION FOR TRANSFORMERS WITH MULTI-PARTY COMPUTATION
Ouyang, Felix Xiaozhu Lin, Yangfeng Ji Department of Computer Science University of Virginia (ftpEnr, felixlin y
ABSTRACT
Critical free data market is private data selection, i.e. the model owner selects and then appraises training data from the data owner before both parties commit to transaction. To keep the data and model private, this process shall evaluate the target model to be trained over Multi-Party Computation (MPC). While prior work suggests that evaluating Transformer-basse models over MPC is prohibitively expensive, this paper makes it practical for the purpose of data selection. Our contributions are three: (1) new pipeline for private data selection over MPC; (2) emulating high dinensiinnni nonlinear operators with low-dimension MLPs, which are trained on small sample of the data of interest; (3) scheduling MPC in a parallel, multiphase fashion. We evaluate models and NLP/CV benchmarks. Compared to directly evaluating the target model over MPC, our method reduces the delay from thousands of hours to tens of hours, while only seeing around 0.20% accuracy degradation from training with the selected data.
method diverse Transformer
INTRODUCTION
Data selection appraisal In today's ML ecosystem, data and models are often owned by separate parties. Examples include mobile users versus app providers, and small businesses versus marketing firms. As model owners are interested in acquiring data train their models from data owners, data becomes a commodity to be valued and traded.
Selection preparation in the clear
Basic information of the model and data
Forward DOGS
MPC
Entropy
Remaining data Indices the clo
Nx
Figure Three stages of our data selection workflow in chronological order.
In a free data market, no purchase commitment should be required unless both parties reach an agreement, for which pre-purchase assessment is vital. contains two steps: select the most valuable data; (optionally) appraise the selected data. To model owners, pre-purchase selection is key to cost- effectiveness. Extensive work already showed that datasets are often redundant and noisy (Settles) 2012, Katharopoulos & Fleuret 2018 Mirzasoleiman et al.) 2020 Ouyang al. 2022 purchase budgets should be spent on data points that are most likely to maximize model accuracy. To data owners, selection allows them reveal less data in exchange for the same monetary reward, which

---

Published as a conference paper at ICLR 2025
retains their data ownership and reduces privacy exposure. The need for judicious data selection is further highlighted by that data candidates are often unlabeled (Hoi et al. 20066 |Smihh et al. 2018 and have skewed label distributions (Kaur et al. 2019). This paper targets this issue.
Challenge: private selection Data selection and appraisal should be private: they should not leak any data and model parameters; if purchase agreement is eventually reached, the model owner should learn no more beyond the data she is paying for. To select and appraise data, a common algorithm is to
model's forward passes over data candidates and select based on the outcome (see Section 2 for details), It can be made private by building atop Multi-Party Computation (MPC) (Goldreich al. 1987 Shamir 1979 Yao 1986): both parties (owners) jointly evaluate over the candidate data, learning only the indices of selected data and the quality measurement.
However, evaluating Transformer models MPC is expensive. A forward pass of BERT on a batch of 4 requires 3252 communication rounds and over 245 GB data exchanged, taking around 0.76 hours across commodity servers with GPUs. Most of the cost comes from executing nonlinear arithmetics such as softmax, which is pervasive in Transformers. Some efficient Transformers works can improve inference speed (Fu et al., [02T]] You et al.) 2022 Fu et al.] (022). But to support Transformer inference over MPC, recent work approximates nonlinearity with cheaper linear operations (Li et al., 2022; Dong et al.) 2023 Chen et al. 2021). For data selection, they are not only too slow (hundreds of GPU hours to select from tens of K data points) but also have poor results this paper will show.
Goal & techniques Our goal is to accelerate private data selection for transformer- e.g. BERT and ViT, while retaining the training performance. Our key insight is that the nonlinearity in Transformers can be fused and evaluated at low dimensions; fortunately, the resultant model evaluation outcomes will be acceptable for the purpose of data selection, which only depends on how the outcomes for individual data candidates compare to each other. We present a holistic selection pipeline with three key techniques.
models,
Nonlinearity emulated by multi-layer perceptron (MLPs). While existing MPC frameworks treat individual nonlinear operations in isolation (e.g. Newton-Raphson iterations for reciprocal), we fuse adjacent non-linear operators and emulate them altogether with a small MLP. The benefits are twofold. (1) MLPs significantly reduce MPC costs because they not only serve as approximators (converting nonlinear to linear operations) but also dimension reducers, e.g. substituting a 512- dimensional softmax with 2-dimensional MLP. This sets us apart from prior work that approximates single nonlinear operation (e.g. reciprocal) with an MI.P (Chen et al. 2022). which does not reduce dimensions and therefore executes much slower. (2) ML.s are data-driven. They are trained atop the distributions of the actual model activations, tailored to the datasets of interest. They only require small amount of training data, as few as several hundred on average in our experiment.
Multi-phase selection. For efficiency, the data/model owners jointly select data in multiple phases. While early phases evaluate cheap selection models to filter most of the data, later phases run more expensive selection models to select from the data that survived from earlier phases. This reduces the total selection delay without compromising accuracy.
Parallel MPC executions. To further reduce the selection delay, the data/model owners batch network latency-bound bound MPC operations and execute them in parallel to network bandwidth- MPC operations; they further overlap the MPC communication and computation across different batches. No prior MPC systems exploit such parallelism, to the best of our knowledge.
Workflow There are three stages in our proposed workflow: two in the clear and one over MPC. As shown in Figure 1] in the beginning, the model owner and the data owner exchange some basic information the clear. For instance, the total amount of data and the amount of data that the model owner plans to purchase. Next is the private multi-phase selection which is over MPC. Two parties secretly share encrypted proxy model parameters and data to do a forward pass and get the entropy value. We then rank them and select the top candidates based on their rank. The remaining data points' indices will be reused in the next phase. The comparison outcomes will be revealed and the data indices are in the clear. Data will not be transferred among phases. The final transaction is in the clear. After private data selection, the model owner pays for the data wants and the data owner sends out the data to seal the deal. More details in Section 4
2

---

Published as a conference paper at ICLR 2025
Results We test SelectFormer with four target models, seven NLP/CV benchmarks, and variety of purchase budgets
We show that with commodity GPUs and typical Internet, our pipeline select from 10K-100K data points within tens of hours, order of magnitude faster than prior work. Using unmodified MPC protocol and framework, we provide a strong privacy guarantee. Our selected data only results in just 0.20% lower accuracy compared directly evaluating the target model over MPC for selection, gold method which is however 204 x slower.
Contributions This work proposes novel application of MPC private data selection, and makes it practical on large Transformer models. It achieves so via three new techniques:
A data-driven MLP approximation that is uniquely tailored for data selection, instead of generic inference.
Multi-phase selection that progressively increases the selection models' capability and reduces the amount of data candidates.
Parallel MPC executions that hide the delays of computation and communication rounds behind that communication data exchange.
BACKGROUND
2.1 ASSUMPTIONS ON SYSTEMS
Two parties The model owner possesses pretrained Transformer model Mtarget and wants to finetune it. The data owner owns the dataset D for selection. The model owner plans to buy B datapoints (B~ (D)) from dataset which will used to finetune the target model Marget- The model owner has a private, small validation set, on which she wants to maximize the validation accuracy. The two parties agree on and that they will use MPC for selection.
Datapoints We follow common premise in prior work on data selection: (Coleman et al. 2019 Mahmood al. (022)), the dataset D is unlabeled and might have an imbalanced class distribution, which warrants careful selection before training. This premise is motivated by real-world situations where data labels are scarce and data owners often lack the motivation, expertise, and authority to label their data (Hoi et al. 2006 Smith et al. 2018)
Threat model Without alternation, we follow a semi-honest model widely used in prior security research (Knott et al. 2021 Dong et al.) 2003 Mohassel & Zhang (017): both parties faithfully follow the MPC protocol but nevertheless attempt to learn each other's private information (model weights and datapoints) through their interactions. Notably, do not deviate from protocols
implemented by well-known frameworks such as Crypten (Knott et al. 2021). As such, our privacy guarantee is as strong the underlying framework.
2.2 ALGORITHM FOUNDATIONS
(1) Maximum entropy selection Active learn- ing (AL) (Settles) 2012) selects from unlabeled data to maximize training performance. To ap- praise an example for training model M, AL runs forward pass of M over (or query x with M) and computes the prediction entropy: higher entropy implies lower model confidence, hence higher learning value of x. (2) Proxy mod- with Mtarget can be slow. To this end, prior work uses lightweight model Mp called "proxy" for selec- tion before training Mtarget with the selected data (Coleman et al., 2019). To select valu- able data, M, prediction should resemble that of Margeti hence M, is often created as miniature version of Mtarget: examples include
LayerNorm
MatMul
Comp (sec)
0.9
Comm rounds
136
118
11
Data
20.9
1.8 2.3 0.5
(GB)
els Querying all examples
Figure Transformers over MPC incurs high com- munication and computation overhead. Showing one forward pass of one layer (12 heads) over a batch of 5 (maximum allowable on our GPU). Hardware: Quadro RTX 4000. MPC framework: Crypten (Knott et al. 2021).
3

---

Published as a conference paper at ICLR 2025
ResNet-18 18 proxy for ResNet-50 (Coleman et al. 2019). We use simplified Transformers as proxy models with fewer layers and attention heads.
2.3 TRANSFORMERS, MPC, AND OVERHEAD ANALYSIS
Transformers
We focus on transformer- based models (Vaswani et al. 2017). Each layer of these models features a Multihead Attention paired with FeedForward. Both are succeeded by layer normalization and residual connection. Within the Multihead Attention, operations proceed sequentially from QK V linear operation to the attention mechanism, and finally an attention output.
MPC setting: 2PC We assume the most common MPC setting: secret sharing under two-party computation (2PC) (Yang et al., 2019). The model owner randomly decomposes into two shares, I and 22 (such that + I22 = 2),, retains 21, and convey 22 to the data owner. Analogously, the data owner fragments y into 1/1 and y/2 and transfers 1/2 to the model owner. These shares individually disclose no information about the original numbers, x and Reconstruction of a number is possible when both parties exchange their shares and sum them up.
To compute x+ y, each party add their shares of z and y, yielding 21 I1 +1 y1 and 22 z2 1/- Both parties can retrieve 2 by adding 21 and 22. For multiplication, The parties can offline generate a random triple called Beaver triples (Beaver 1992), a, b, and e (such that ab c). The elements of this triple are then partitioned and disseminated amongst the parties, akin to x and y. The model owner calculates E #1 -. d1 y/ bi while the data owner computes 62 I22 022 62 1/2 b2. The parties jointly reconstruct e and 6. Subsequently, the model owner computes p1 = Ci + + 5zz +ed and the data owner calculates P2 C2 + E/2 + dxr2, enabling the retrieval of p = ay. Throughout this procedure, all intermediate computations, including é1, Eg, 81 and 82 maintain the confidentiality of æ, y and p. precluding any information leakage.
Major overheads comes from that MPC lacks native support for nonlinear operations, such as softmax, logarithmic, and exponential, which are pervasive in Transformers. response, MPC frameworks provide corresponding linear approximations. Unfortunately, the overhead is still high. Figure shows the cost of the operations for one transformer block. As shown in the table, the cost of nonlinear arithmetic dominates. Notably, softmax contributes 81.9% communication data and 142 communication rounds. The overheads become prohibitive for data selection, which needs to evaluate Transformers on tens of thousands of data points over MPC. We show this in Section 5
3 RELATED WORKS
Data selection and appraisal Our work builds the idea of using miniature version (proxy) of the target model as the selector (Coleman et al. 2019). Yet, proxies alone are still too expensive for MPC as we will show in Section Xu et al. (2022) investigates data appraisal over MPC. Contrasting to us, they assume labeled data (a strong assumption in practice), which allows them to appraise data via forward influence functions. Unlike us focusing on Transformer models, they only demonstrated logistic regression tasks. Mindermann et al. (2022) introduces RHO loss that quantifies by how much data candidates would reduce the loss on small holdout set the model were to train the candidates. They then select data based on RHO loss. Their methods inspire our bootstrap dataset. However, they rely on labeled data, whereas we focus on a more challenging setting selecting unlabeled data.
MPC inference of neural networks Existing research has developed discretized DNN training with a customized two-party protocol (Agrawal et al. 2019) and MPC-friendly approximations to speed up CNN. Chou et al. (2018) develop an optimization framework that minimizes the approximation error of order two polynomial to ReLU, MMshra et al. (2020) alleviates this problem by using a set of heuristics along with Neural Architecture Search (NAS). Mohassel & Zhang (2017) proposes costly approximation of softmax by replacing exponential with ReLU functions on high-dimension inputs.
MPCFORMER (Li et al. 2022) and PUMA (Dong et al. 2023 directly address efficient Transformer inference over MPC. MPCFORMERIS implemented based on Crypten (Knott et al. (02[) framework and its key idea is that approximate nonlinear operations in the student model and then distill it;
4

---

Published as a conference paper at ICLR 2025
PUMA proposes approximations for faster secure inference in three-party setting. Bolt (Pang et al., 2024) proposes a new Transformer inference framework. Compared to us, they miss the key opportunities of reducing nonlinearity dimensions and using learned approximators (MLPs). Furthermore, MPCFORMER'S 's model distillation approach is ill-suited to data selection, where labeled data for distillation is lacking. As Section will show, they perform poorly in data selection.
METHOD
4.1 HIGH-LEVEL WORKFLOW
Prior to the selection, the two parties exchange meta-information in the clear: the purchase budget B, the secure computation framework, the target model architecture type, pre-processing methods, and the metadata about the S, which includes the number of data points.
Pre-selection bootstrap:
The model owner purchases bootstrap data Sboot which constitutes a small fraction of the purchase budget B. The data owner randomly samples Shoot from S: the purchase requires selection and incurs no MPC overhead. The model owner will use Shoot generate proxy models MI..N, as will be described below.
For efficiency, the selection process is progressive sieve: earlier phases run smaller selector models for quickly filtering a majority of redundancy, whereas later phases run larger selector models for slower, more precise selection. Concretely, both parties jointly execute N selection phases over MPC. A phase i downselects dataset S to the set S; with selectivity a, |
Multipass selection
In phase i, the model owner queries the dataset S with a proxy model M, The query is executed as forward pass of M, on St-1 on MPC. The forward pass computes the prediction entropy values, which encrypted. Next, both parties jointly find the indices of |S; highest entropy values: execute the QuickSelect algorithm with ((():11)) pairwise comparisons between entropy values; the comparison is over MPC, each taking 8 communication rounds and transferring 432 bytes. A comparison does not reveal its inputs (entropy values) but only the binary outcome. Finally, the indices of data points with the highest prediction entropy constitute the input for the next phase.
Target model
Proxy models
Candidate Data So
Finetune Spoot
Proxy model
M1
Finetune
Marget
Mg
Spott
Bottom
M2
training
Proxy model
Initialize
S2
MLPs
Ex vivo traning
Target Medel Training
DAFS
Figure 3: Our high-level workflow. Left: proxy model generation. Right: multi-phase selection. M, the base model for the proxy models M M,.NN More details in subsecttion 4.2
N phases result in the final dataset Sy. The model owner may offer to buy Sx or request an appraisal of Sy before buying. For appraisal, both parties jointly compute an average entropy over Sy and reveal the average entropy. If the average entropy is sensitive, both parties can jointly compute if the (encrypted) average exceeds pre-defined threshold and only reveals the one-bit outcome.
Privacy guarantees The following information is kept private: dataset S; parameters of Mearget and Mr the prediction outcome and entropy. The following is revealed: the rank of prediction entropy; the architecture (operations) of M the number of data points and budget.
5

---

Published as a conference paper at ICLR 2025
DistiBERT
ViT-small
SST2
ONLI
QQP
AGNEWS
YELP
SST2
QNLI
QQP
AGNEWS
YELP
Cifar10
Cifar100
Cifar10
Cifar100
Ours
82.34
71.46
71.53
88.49
60.18
84.59
73.68
72.73
89.04
61.33
96.46
69.11
96.61
68.42
Random
79.08
70.34
66.18
86.43
58.09
79.58
73.56
68.84
$7.85
59.16
94,69
43,99
95.63
63,21
(vs. Ours)
-1.12
-5.35
-5.01
-1.19
-0.98
Oraele
71.51
89.19
59.93
86.06
73.08
89.74
60.8
96.87
96.94
(Vs. Ours)
-000
40.02
40.02
0.70
-0.25
1.47
0.94
0.35
0.70
-0.53
0.41
-0.71
0.33
-0.57
Table 1: Ours are consistently higher than Random across all models and benchmarks and are close Oracle (gold accuracy).
4.2 GENERATING PROXY MODELS IN DETAIL
proxy model M, characterized by 4i, w;, d, LA transformer layers with A, attention heads each (width), in which the nonlinear modules are substituted by MLPs with hidden dimension de and the GeLU functions are substituted by ReLU functions. FFN is also removed from proxy models. As shown in Figure 3 the model owner generates proxy models My..N N follows:
Extract sub-model M, from Mtarget. Mg comprises bottom layers from Mtarget where max((...x), with all the weights copied over. Mg serves as the backhone for M
=
* Finetune Mg on the bootstrap data Sboot- This serves two purposes: (1) collecting sample input/out- put of M2 nonlinear modules, which will be used to train the MLPs that substitute these nonlinear modules; (2) roughly adapting M, to sample from the dataset S. Initialize ML..N by pruning the width and depth of Mg-
Ex vivo MI.P training. For each transformer block a proxy model, randomly initialize three ML.ss Train them separately on the input/output of nonlinear modules collected from the previous step. More training data following the same distribution as the input/output will be randomly generated as data augmentations. See subssectin 4.3 for details.
In vivo MLP training. Substitute the nonlinear modules in M, with the MLPs trained in the previous step. Further finetune the resultant model M, on Spoot end-to-end. This co-tunes MLPs (the approximate portion of M,) and the remaining exact portion.
The model owner schedules the selection by setting {< 1, w. d2 >>i=1.N for N phases. As described above, the principle of schedule is progressive: increasingly higher 1/w d for later phases. Given budget B, SelectFormer determines the schedule via offline grid search. See Section 5
Mg
Entropy
Softmax
Trah
Bound communication rounds
(Pees Gael MLL
4-08/16
Linear
Linear
Train MLP
Add & LayerNorm
Extract 0p)
Bound by communication bandwidth
Train MLP
SoltMax
Extract
Multi-Head Attention
Multi-Head Attention
Enneedingg
Embendings
Mg.
transformer block with MLPs, for phase
original nonlinesr modules
Figure 4: Training MLPs for substituting the non- non-liny in Transformer models
4.3 APPROXIMATION MLPs FOR NON-LINEAL OPERATIONS
Our theoretical foundation Hornik et al. 1989): MLPs are able to approximate any function at any desired degree of accuracy, as long as the function is continuous on closed and bounded subset of R" A transformer's 's nonlincar modules satisfy this condition (Goodfellow et al. 2016). We use standard MLPs, each comprising ReLU layer sandwiched between two linear layers. Of proxy model, MLPs substitute the following nonlinear modules as shown in Figure 4)
Softmax in the attention module. At each transformer layer, a substitute MLP maps along the last dimension of the input and has the same input/output shape as the original softmax operation.

---

Published as a conference paper at ICLR 2025
5ST2
QNU
QQP
Accuracy
85%
80%
75%
00%
95%
70%
65%
55%
85%
45%
75%
20%
40%
0%
20%
40%
0%
20%
40%
0%
20%
40%
0%
20%
40%
Budget
Ours
Random -...
Oracle
--d-
Figure 5: Across a variety of budgets, Ours consistently outperforms Random and are comparable with Oracle (gold accuracy). Target model: DistilBERT.
LayerNorm the attention module. At each transformer layer, a substitute MLP emulates the reciprocal operation in LayerNorm. Of the LayerNorm, its learnable weights and bias in the affine functions are loaded from the original LayerNorm layers Mn. Its numerator is computed directly on MPC because the total number is constant and it needs just cheap summation and multiplication.
Softmax over logits and the subsequent entropy computation. At the top the model, substitute MLP emulates the two modules combined. The MLP input shape is the same as that of softmax. The output will be the entropy itself.
proxy model of layer / comprises 21 + MLPs in total: they have the identical hidden dimension albeit different weights. Different proxy models may have MLPs of different hidden dimensions, set as part of the schedule as described above.
Training MLPs MLPs need to be trained on the sample input/output of the nonlinear modules being substituted. While we can use such input/output observed in finetuning My over bootstrap data (Sboot), the data amount inadequate: randomly sampled Sboot must be small (3521 datapoints average in our experiments) in order to save the budget for private selection.
We address the problem with the empirical observation that inputs nonlinear module largely follow a parametric Gaussian distribution (Chen et al. 2022). As such, from the actually observed inputs, the model owner estimates the Gaussian distribution parameters (14, o) and uses such parameters to synthesize training inputs and outputs.
For given nonlinear module in Mg. an instance of (j, o) estimated and one dataset (5.12 million data points) is synthesized once, which is used to train the MLPs that substitute this particular nonlinear module in all proxy models MI..N. There are three synthesized datasets: Sem. Sin and S.c. This is shown in Figure 4 Note that MI..N with MLPs inserted will be further finetuned as described above. The MLP training very cheap compared with the selection over MPC, which can be measured in minutes.
4.4 10 SCHEDULING
Our proxy models perform sequence of matrix multiplication and ReLU. Operating high- dimensional inputs are bound by the network bandwidth; after being projected into lower dimensions, the operations succeeding the activation functions bound by network latency. To this end, (1) SelectFormer stacks and coalesces the latency-bound modules from multiple batches, reducing the number of communication rounds and improving the computation throughput. (2) Furthermore. SelectFormer exploits computation and communication parallelism across batches, executing module whenever its needed resources become available. For instance, while data exchange is occurring for one batch, computations for the subsequent batches can be performed concurrently. Such no-execution is only limited by data dependencies and the available memory of party hold operation inputs.
EVALUATION
5.1 EXPERIMENT SETUP
Models & datasets For NLP, choose target models BERT (12 layers) and DistilBERT (6 layers), with 12 attention heads and a hidden dimension of 768. For vision, we chose the target model ViT, with the same architecture BERT. We chose benchmarks with at least tens of thousands
7

---

Published as a conference paper at ICLR 2025
Emulated w/ MLP?
DiSiBERT Accuracy
BERT Accuracy
Outs
71.63
57.75et
84.3351,30
72.31=1.21
BR.
57
10,48-1. 27 (Q.12))
71 75 (40.22)
(-1 AN)
15, 14.1810:46
(40.81)
74, 74.15 Sel Ma)
N9.15 wo.55o.u [+1.18]
N
KL.8300 78 (.097))
71. 71.58M0.44 (10.0
49 (40.5) 551
85.055d 25 (40.50 581
72, 72.9646. 04 (40.45)
80.0000000 47 [40.71]
Nohpprox
52,02
70.4211.0 (3)2))
54,7911
70:1010 (0)00)
Table 2: Using MLPs emulate Transformer nonlinearity results in minor accuracy degradation
Oracle
Phose
Ours
DistiBERT
BERT
VIT-small
VIT-base
Delay/hrs
100
202
320
10
4972
Qk0
ADRENS
RRF
074R100
Figure 6: Our method reduces the end-to-end delays by two orders of magnitude. As in Section phase selection selects data using a proxy model with a hidden dimension of 16.
of data points which warrant selection. Following prior work (Xu al. 2022) to construct the training set with imbalanced labels, we remove some data points from the original benchmarks. Our imbalanced NLP benchmarks include binary classification from GLUE (Wang et al. (0118): SST2 (42K), QNLI (58K), and QQP (1 (149K); and multilabel classification (Zhang et 2015): AG news (40K) and Yelp review full (188K). Our vision benchmarks are two multilabel benchmarks CAFAR-10 (10K) and CIFAR- 100 (6K). Note that we do not change the test set.
We implement our scheme based on Crypten (Knott et al. 2021). a popular MPC framework. We run data/model owners separate GPUs (Nvidia Quadro RTX 4000) with Intel(R) Xeon(R) Silver 4210 CPU: we control the network bandwidth (100 MB/sec) and latency (100 ms) between them to emulate wide-area network condition. We report: (1) the test accuracy of the target model, after being trained with the selected data; (2) the delay of the data selection process over MPC.
These results are derived using two-phase data selection unless specified otherwise. In the first phase, for NLP tasks, we employ a proxy model with a single layer and a dimensionality of 2, while for CV tasks, a proxy model with three layers and the same dimensionality is utilized. In the second phase, proxy model with three layers and a dimensionality of 16 is applied for these two tasks.
Baselines We evaluate method against the following baselines.
1. Random selects data randomly from the data owner. It incurs zero MPC overhead.
2. Oracle queries data using the target model. Under our framework (Section 2). we consider that it leads to gold test accuracy. Yet, it incurs prohibitive MPC overhead as will be shown.
3. MPCFORMER (Li et al. 2022) is a closely related project that minimizes the cost of evaluating transformers over MPC. We implement this baseline to adopt MPCFORMER 's key optimizations for evaluating proxy models: linear operators for approximating nonlinearity and model distillation for recovering accuracy. For a fair comparison, MPCFORMER uses the same proxy model architecture as ours, and initializes the proxy models in the same way; runs distillation on the same amount of bootstrap data. Note that we cannot directly compare to PUMA (Dong et al. 2023), which is designed under compute parties.
Bolt (Pang et al. 2024)'s MPC framework contains linear approximations for nonlinear operations.
5.2 END-TO-END RESULTS
Selection delays Our method significantly reduces the delays. Compared to Oracle, our method's delay is lower by two orders of magnitude as shown in Figuue For instance, to select 20% from 42K data points (SST2 benchmark, DistilBERT model), our experiment takes around 20 hours whereas Oracle would take 3740 hours.
Selection efficacy Our method effectively selects training data that best boosts the test accuracy. Table zooms in on typical purchase budget (20%). Compared to Random, our test accuracy
8

---

Published as a conference paper at ICLR 2025
Legend
BERT
Vil-smal
X37
10000
5000
1000
Grode
Delay/hre
PM
5S12
S532
CHIAI-33
CHAMI-31
Figure 7: Delay reduction by our techniques. The results also show that using proxy models alone (variant "P" in the figure.) is not enough.
consistently higher across all NLP and CV benchmarks. The benefit is particularly pronounced on challenging tasks such as CIFAR-100 on which our accuracy is higher by 25.1 12% on ViT-small/base. Compared to Oracle, our test accuracy is comparable: only 0.08% - 0.58% lower for DistilIERT and BERT, and even 0. 13% and 0.15% higher for ViT-base and ViT-small.
Across different purchase budgets of 25%, 30%, and 40,, our method also leads to strong accuracy. Compared to Random, accuracy is 2.23% higher average, and up to 5.14%. Compared to Oracle, our average accuracy is only 0.91% lower on average, and as low as 0.01 %. See the Appendix for detailed results.
From a different angle to view our efficacy: to reach a given accuracy, our method demands a much lower budget. As shown in Figure 5] be on par with our test accuracy on budget of 20%, Random would need budget of 70% (BERT on QNLI), budget of 90% (DistilBERT on SST2), and budget of 100% (DistilBERT on YELP and BERT on YELP/SST2).
5.3 COMPARISON WITH MPCFORMER AND BOLT
As shown in Table 3 our method simultaneously delivers much higher test accuracy (by 23% 36%) and much shorter (by 7 xx) selection delays. The reasons are twofold. (1) MPCFORMER'S longer delays come from that it approximates individual nonlinear operators with linear coun- terparts; it does not reduce model dimension as we do. (2) MPCFORMER'S lower accuracy comes from that its proxy models come from the dis- tillation of the target model, process requiring ample, representative training data. This is at odds with data selection: Sboot is the only data available for distillation; it has a small size and skewed labels. The skewness propagates from Shoot to proxy models, to selected data, and to the target model. As a result, the trained target model is biased towards predicting the majority class in the training set. This results in poor accuracy if the test and train sets have different majority classes, sometimes even worse than random guess (e.g. QQP in Table 3). See Subsectionn 7.2 for the comparison with Bolt.
[M)
007
807
00F
5052
11.22
156
P1300
Table 3: Compared to MPCFORMER, our method results in much higher test accuracy and much lower delays. On GLUE benchmarks which were also evaluated and reported by MPCFORMER. Target model: BERT. Proxy model: 1 transformer layer with head + transformer layers with 12 heads.
5.4 ABLATION STUDY
Crypten incurs minor accuracy loss We validate that our choice of the Crypten framework (Knott al. (02T), which executes ML on a finite ring, introduces minor accuracy loss. On SST2 with the default budget (5% for Sboot; 20% total), private selection fully executed on Crypten results in test accuracy of 83.37%, which is even slightly (0.5% higher than executing on PyTorch.
MLP for non-linearity (1) Delay. Our use of MLP reduces the selection delay by two orders of magnitude, e.g. from 3740 hours to around 20 hours for DistilBERT on SST2. This is shown in Figure by the difference between P and PM. (2) Accuracy. The use of MLP incurs minor degradation in the test accuracy. The results are shown in Table 2 by the difference between Ours to NoApprox. On SST2, ours is 0.78% higher with DistilBERT and only 0.46% lower with BERT. On AGNEWS. ours are just 1.24% lower with DistilBERT and 0.93% lower with BERT. On QQP, it's 1.21% and 0.05% higher respectively. Among the three MI.Ps, softmax in the attention module shows higher

---

Published as a conference paper at ICLR 2025
Totl Phs
MLP dims
proxy layers
DistilBERT Accuracy
BERT Accuracy
Selectivitty
DistiBT
BERT
SST2
QQP
SST2
QQP
16
100%"~+20%%
82.91
71.28
83,49
64.48
2
2
191
1-93
200%
82.00 (-0.91)
71.62 (40.34)
(+1.7)
73.07 (+8.59)
2-98-16
19141
1-33-3
100%0-550%%
83.37 (+0.46)
(+1.6))
84.52 (+1.03)
73.48 (+9.00)
*: indlude bootstrap data
Table 4: Our multi-phase selection improves accuracy in general. Three example schedules (with 1, 2, and 3 total phases, respectively) and their test accuracies are shown.
impact on accuracy than the other two. As shown in Table and across all the datasets, by the difference between Ours to NoArmSM.. Using softmax approximation MLP is just 0.75% lower with DistilBERT and 0.99% lower with BERT on average; by the difference between Ours to NoAmmLN our approximations of LayerNorm only decreases the performance by 0.76% with DistilIBERT and 0. 166 higher with BERT on average. This is justified by the higher cost that our AttentionSM reduces data communication by 42x, while AttentionLN only reduces 8.25
Efficacy of multi-phase selection (MPS) We compare MPS to single-phase selection (SPS), in which the proxy model is the same the one used in the last phase of MPS; it has all other optimizations. (1) MPS reduces delays significantly. Compared to SPS, the two-phase selection reduces the total delay by 33%-61% % across all the benchmarks, Because MPS runs much smaller proxy model in phase to filter most datapoints. The advantage is more pronounced for large models such as BERT, where the efficiency gap between the proxy models in phase is even larger. (2) MPS improves accuracy moderately. We focus on two representative benchmarks SST2 and QQP (binary and multi- classification). The results are in (Table 4 Going from one phase to two/three phases results in tangible accuracy gain (around 1%); notably BERT sees accuracy gain as high as 1.72% (SST2) and 8.59% (QQP). We attribute the gain to MPS being more selective for the finally selected datapoints, which have been sieved through multiple proxy models, small and big.
Sizes of proxy models Multi-layer proxy models increase the selection delay while may improve the test accuracy. Our experiments show that: for small target models on challenging benchmarks (e.g. ViT-small on CIFAR-100), the test accuracy from a three-layer proxy outperforms a one-layer proxy significantly (by 17.33%); other benchmarks, 1 layers only result in minor increase in the test accuracy. On CIFAR-100, a three-layer ViT-base proxy model is 11 11.32% higher than a one-layer with 66.6% lower efficiency. Their accuracies are 0.26% higher than Oracle's average, but with 4x higher efficiency. is worth trading some extent of efficiency for much higher accuracy by a multi-layer proxy model, especially on difficult datasets like CIFAR-100.
MLP hidden dimensions To decide di, we conduct a grid search to find the best values, which included in our selection schedules shown in Table 4 We mainly do this grid search on SST2, validate the hyperparameters on QQP before applying the same settings to other datasets. A higher dimension like 16 has good accuracy on different datasets while not incurring much more latency. Multi-phase selection can reduce lots of latency, hence, we pick hidden dimension combinations that can bring more accuracy gain. For the Phase, we choose (2, 16) which has the highest accuracy on larger datasets and target models, such as BERT on QQP. For the 3 Phase, we choose (2, 8, 16). It has the highest accuracy with DisitilBERT on SST2, with BERT on QQP, and suboptimal accuracy on other experiments.
10 scheduling This optimization reduces the end-to-end selection delays by 1.3-1.4x, as shown in Figure 7 the difference between Ours and PMT. The reduction comes from overlapping the MPC computation and the communication rounds. their communication latency is hidden. The reduction depends on hardware: device computation bandwidth and the network latencies.
CONCLUDING REMARKS
This paper addresses the private selection of imbalanced, unlabelled data. We propose data selection on MPC, preserving privacy while evaluating data. Overcoming computational challenges, we introduce a data-aware MLP approximation for non-linear modules, tailored to different datasets for reduced latency. Our multi-phase selection mechanism enhances proxy models' efficiency across diverse benchmarks.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
The authors were supported in part by NSF awards #2128725, #1919197, and #2106893; as well as NSF awards #2124538 and #2007492. The authors thank the anonymous reviewers for their insightful feedback.
REFERENCES
Nitin Agrawal, Ali Shahin Shamsabadi, Matt J Kusner, and Adrià Gascón. Quotient: two-party secure neural network training and prediction. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 1231-1247, 2019.
Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum (ed.), Advances Cryptology CRYPTO '91, pp. 420 432, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. ISBN 978-3-540-46766-33
Tianlong Chen, Zhenyu Zhang, Xu Ouyang, Zechun Liu, Zhiqiang Shen, and Zhangyang Wang. "nnn bn = P": Training binary neural networks without batch normalization. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR) Workshops, pp- 4629, June 2021.
Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao, Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei. THE-X: prreecy-prss transformer inference with homomorphic encryption. In Findings of the Association for Computational Linguistics: ACL 2022, pp. 3510-3520, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 101118811//222 findiigsss acl.277. URL wtt.tttpss//// htt.://t.....aaaaa.ooooorrr///e.
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung. Albert Haque, and Li Fei-Fei. Faster cryptonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint arXiv:1811.09953, 2018.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Sclection via proxy: Efficient data selection for deep learning. arXiv preprint a9X6: /829, 2019.
Ye Dong, Wen-jie Lu, Yancheng Zheng, Haoqi Wu, Derun Zhao, Jin Tan, Zhicong Huang, Cheng Hong, Tao Wei, and Wenguang Cheng. Puma: Secure inference of llama-7b in five minutes. arXiv preprint 27Xiv:2307.125333 2023.
Yonggan Fu, Qixuan Yu, Yang Zhang, Shang Wu, Xu Ouyang, David Cox, and Yingyan Lin. Drawing robust scratch tickets: Subnetworks with inborn robustness are found within randomly initialized networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 13059-13072. Curran sociates, Inc., 2021.
paper/
Pawp:/77752222--p...pp.pp. Paper.pd.
Yonggan Fu, Qixuan Yu, Meng Li, Xu Ouyang, Vikas Chandra, and Yingyan Lin. Contrastive quant: quantization makes stronger contrastive learning. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pp. 205-210, 2022.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87. pp. 218-229. New York. NY. USA, 1987. Association for Computing Machinery. ISBN 0897912217. doi: 10.1145/28395.24422 UTL//ttas////..oc000111////88883
Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Leurning. MIT Press, 2016. http:
Steven C. H. Hoi, Rong Jin, Jianke Zhu, and Michael R. Lyu. Batch mode active learning and its application to medical image classification. In Proceedings of the 23rd International Conference Machine Learning, ICML '06, pp. 417-424, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 14.1 143844. 1 143897.
URL https

---

Published as a conference paper at ICLR 2025
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 2(5):599-33)) -6669996666-0 1989.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525-2534. PMLR, 2018.
Harsurinder Kaur, Husanbir Singh Pannu, and Avleen Kaur Malhi. A systematic review imbalanced data challenges in machine learning: Applications and solutions. ACM Computing Surveys (CSUR), 52(4):1-33) 1-11113666260 2019.
Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-pany computation meets machine learning. Advances in Neural Information Processing Systems, 34:4961 4973, 2021.
Dacheng Li, Rulin Shao, Hongyi Wang, Han Guo, Eric P Xing, and Hao Zhang. Mpcformer: fast, performant and private transformer inference with mpc. arXiv preprint arXiv:221 2022.
Rafid Mahmood, James Lucas, Jose M. Alvarez, Sanja Fidler, and Marc Law. Opti- mizing data collection for machine learning. In S. Koyejo, S. Mohamed, A. Agar- wal, D. Belgrave, Cho, and A. Oh (eds.), Advances Neural Information Pro- cessing Systems, volume 35, pp.
Curran Associates, Inc., 2022. URL
http:://ppeeeenn...rrrrrrcppeepp c 4444ccc2e64000003222255665611--4
Sören Mindermann, Jan M Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Prioritized training on points that are learnable, worth learning, and not yet learnt. International Conference on Machine Learning, pp. 15630-15649, PMLR, 2022.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pp. 6950-6960.
PMLR, 2020.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Sym- posium (USENIX Security 20), pp. 2505 2522. USENIX Association, August 2020. ISBN 978- 1-939133-17-5. URL http:://wwwauuuaaaaer/cc/e/eeeee presentation/ mi shra.
Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-prestt sewaccypreserving machine learning. In 2017 IEEE symposium on security and privacy (SP), pp. 19-38. IEEE, 2017.
Xu Ouyang. Shahina Mohd Azam Ansari, Felix Xiaozhu Lin, and Yangfeng Ji. Efficient nlp model finetuning via multistage data filtering. arXiv preprint arXiv:2207. 220.222207.4386,, 2022.
Qi Pang, Jinhao Zhu, Helen Möllering, Wenting Zheng, and Thomas Schneider. Bolt: Privacy- preserving, accurate and efficient inference for transformers. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 4753 4771. IEEE, 2024.
Burr Settles. Active Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2012.
Adi Shamir. How to share secret. Communications of the ACM, 22(11):612-613 1979.
Justin S. Smith, Ben Nebgen, Nicholas Lubbers, Olexandr Isayev, and Adrian E. Roitberg. Less is more: Sampling chemical space with active learning. The Journal of Chemical Physics, 148 (24):241733, 05 2018. ISSN 0021-9606. doi: 10.1063/1.5023802. URL/https://do.oo
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762 2017. URL
12

---

Published as a conference paper at ICLR 2025
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint 1043::8804007611, 2018.
Xinlei Xu, Awni Hannun, and Laurens Van Der Maaten. Data appraisal without data sharing. In International Conference on Artificial Intelligence and Statistics, pp. 11422-11433 1433.. PMLR, 2022.
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. CoRR, abs/1902.04885, 2019. URRphhttt:///axxiv.oom
Andrew Chi- Chi-Chih Yao. How generate and exchange secrets. In 27th annual sympostum foundations of computer science (Sfcs 1986), pp. 162-167. IEEE, 1986.
Haoran You, Baopu Li, Zhanyi Sun, Xu Ouyang, and Yingyan Lin. Supertickets: Drawing task- agnostic lottery tickets from supernets via jointly architecture searching and parameter pruning. In European Conference on Computer Vision, pp. 674-690. Springer, 2022.
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In NIPS, 2015.
APPENDIX
7.1 MLP APPROXIMATION TIED TO DATA SELECTION
Inspired by the outstanding performance of our MLP approximations for nonlinear modules, one question was raised: the good performance of MLP approximations because its inference capabilliy? Our further experiments show that MLP approximation is tied data selection, instead of general model inference.
Following Li et al. 2022), replace three nonlinear modules in BERT-base model with approximations: Attention Softmax, Attention LayerNorm, and Feedforward Network Layernorm. There 3*12 36 MLPs in the BERT model. In the experiments, two LayerNorm approximations are always data-aware, while there are both data-aware and fixed approximations of Softmax because of varying attention masks. The BERT with MLP approximation will be fine-tuned on the benehmark before inference.
Three versions of attention softmax approximations achieve no better than random guess perfor- mances: (1) Using fixed MLP for attention softmax and changing the mask value to -3 instead of a very negative value for simpler distribution. Our BERT with approximation achieves only 52.92% accuracy. (2) Using data-aware attention softmax approximation, which zeros out masked values on MLP outputs, has 49.08% accuracy. we normalize the remaining values to [0, 1]. the accuracy remains 49.08%. To better understand the influence of each nonlinear approximation, we did an ablation study that keeps just one kind of MLPs (12 of them) in BERT. However, none them achieve better than 50.92% accuracies. We further notice that adding just one attention softmax MLP to the model has no impact on the inference accuracy. But adding one layernorm MLP will degrade the accuracy by 0.85% on average. These results show that having just one MLP will hurt the inference performance a lot; having 12 or even 36 MIPs will degrade model performance drastically. (3) Removing the attention mask to make MLP data-aware. always has 50.92% accuracies, no matter with all three approximations or just one approximation.
The poor inference performance and good data selection performance show that the MLP approxima- tion is specifically suitable for data selection while impractical for model inference directly.
7.2 COMPARISON WITH BOLT
We compare with Bolt (Pang et al. 2024)'s 's polynomial softmax approximation by replacing MLPs in our 2-phase proxy models while keeping other nonlinear layers intact. This approach ensures the highest softmax accuracy but the largest delay. Bolt achieves an accuracy of 69.04% + 11.86%, ours achieves 84.59% + 0.95%, and MPCFORMER achieves 50.92%. With proxy models trained on Sboots Bolt outperforms MPCFORMER. However, our method surpasses Bolt by 15.55% in accuracy and had lower standard deviation, demonstrating better robustness against the biased Spoot Notably, if full
13

---

Published as a conference paper at ICLR 2025
approximations (e.g., reciprocal and layer normalization) applied, Bolt's accuracy is expected to decrease further, reducing its effectiveness compared to our methods.
7.3 ADDITIONAL EXPERIMENTS RESULTS
DOP
AGNSWS
Mone
DisstIBRRT
DEAT
54.0
12.0
63
00.4.
4.4
1
622
52.1
Paases
200
Datay Dhsury
Figure 8: Multi-phase selection achieves better trade-off between accuracy and delay in data selection. 2-phase proxy model: layer with attention head and a dimension of 2, layers with 12 attention heads and dimension of 16; 1-phase proxy model: layers with 12 attention heads and dimension of 16.
DistilBERT
BERT
SST2
QQP
S5T2
QOP
2
71.90
84.52
64.06
8
82.11
73.43
86.58
64.20
16
82.91
71.28
83.49
64.48
Average
83.57
71.67
84.63
63.97
(2,
84.85
72.79
69.30
(2, 16)
82,00
71.62
85.21
73.07
(4, 16)
82.57
72.19
83.49
72.56
Average
82.48
71.49
83.86
71.93
[2, 2)
71.67
(2,
85.55
71.31
[2, 16)
82:11
72.35
84.75
73.08
3
[2, 8)
82.57
70.79
85.21
72.77
12, 16)
83.37
72.90
84.52
73.48
161
71.75
Average
71.71
84.90
73.47
Table 5: Multi-phase selection is able to significantly reduce runtime and maintain comparable accuracy. On QQP, three-phase selection achieves 9.5% higher accuracy than using phase. Main results: 16. (2,16), 12,8,66).
musteen
Ouass
Selennianvl
Randore
Our
Selectorrel
Fandom
Dum
Sdedviiui
Hardon
Ours
Schcteohul
Randor
Omn
bebotworul
Fandom
25%
52.75331
83.071101
77.000880
71000150
72.70::00
73:18:229
(6.6741.3
580003.50
10.3540.11
87.37:0.44
053810.13
00.0300:0
58.420..0
47%
533001.06
13.0011.2
80
73.001132
72:93::266
20.001.19
73.401133
7357:361
08.7000.5
59 72.0
10.7240.35
07.0100
03.010.37
61.150014
59.1240-10
Table 6: Our methods robust against the increase in purchase budget. We have consistently better accuracy than Random by a large margin and achieve comparable performance with Oracle, up to 40% budget. Ours: 2-phase selection. layer with attention head and dimension of 2 in phase 1, 3 layers with 12 attention heads and a dimension 16 in phase 2.
14

---

Published as a conference paper at ICLR 2025
DiSiBERT
BERT
AGNEWS
AGNEWS
40%
80.219:10.88 81
70.92%:0.119 19
69.76840.54
07.815:00.66
59.13%:1049 49
80 80.997611.74 74
73:155:0.99 99
71,0781085
9885560.35
50%
79.79% 22
70 70.34%%00
71.07%49.27
88 48.48%20.44
58.59%40 23
80.859680.73
72.98%41.58
71.99%11 20
88. 98.92%%0.335
19.849:30.33
82.399610999
70%
80. 539553611.00 68
71 6386660.555 58
89.00%--0.20 47
59,74%60.33 32
82. 10.44
74.02%41.5 35
72 72.47%+0.66 65
88 73% 87
60. 46.46.0.33
81.06%c4..99 94
71,40ke0.79
40
50%
82,509613 00
39%36.666
73.79%11.00 08
00.45%600.88 35.5
59.96%110.5
50
82.73%61.40
40
74.3755:1.3
73.22911 05
21%60..3
60,28%40.26
100%
33.60%-+0.92
73.20%
73.85%640.94
29.57%s-0.2
60.36X+0.11
62.78%+1.91
74.83%e1.84
73.668440.62
89 N0..8NK60.55
50. 30.
Table 7: Accuracies randomly selecting more data to train the target model. Compared with our selection accuracies in the main body, Random needs much more data. 100% YELP and 90% QQP data is necessary for our 20% selection with DistilBERT; 100% YELP and SST2, 80% QQP and AGNEWS necessary match our 20% budget performance of BERT.
Dedtlaot
666T
ViFunal
5872
GRU
907
ADMINS
TE.P
5572
DCP
ACREWS
Y117
Cler0
Oledte
02m
8334:100
3146:1106
31523877
0011810:3
04.3033
75.08:10
SEAGI025
681111
9512:2.17
73.011.05
20.44:1.44
06.18:3544
66-3300:2
56,0000.0
73.90:335
892024
10.00040
94200037
21:3::300
2311:1.88
46591012
9646-674
Durg
-200
-000
600
70
0.5
+1.47
40.35
0.21
w0.30
.30
Table Ours are consistently higher than Random across all models and benchmarks and are close to Oracle (gold accuracy). Compared with Table 1 standard deviations of 5 runs are added.
15


Reviews:
[{"review_id": "w4DBlotOBM", "reviewer": "Reviewer_p75F", "summary": "This paper proposes SelectFormer, a method for privately selecting data for transformer finetuning using MPC. The setting is that a data holder is trying to sell data to a user, who wants to finetune a transformer on only a subset of the holder’s data. However, the data holder doesn’t want to expose all fo their data, and the data user doesn’t want to expose their model weights to the data holder. The main idea is to iteratively learn a sequence of models, each of which is used to privately rank points in the dataset in terms of their informativeness (entropy of the output distribution of the target model). These models replace nonlinear operations like softmax with an MLP with ReLU activation, where the MLP is trained by collecting input-output pairs from the intermediate model. The authors show that their method significantly reduces the time to select a good training dataset relative to prior private baselines, without sacrificing much in terms of quality (i.e. it selects data points that lead to a good downstream model).", "questions": "1) Can you share a plot of accuracy vs. delay for baselines and the variants of your method, including the variant with 1 phase and a dimension 2 MLP? \n\n2) Why is replacing one nonlinearity with a different nonlinearity useful for MPC? \n\n3) Can/should you compare to BOLT in the evaluation?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "-\tThe problem formulation is interesting and new\n-\tThe algorithm appears to cleverly use the available information\n-\tThe empirical performance and experiments are promising\n\nOverall, I think the paper is proposing an interesting new idea (both formulation and algorithm), and hence I gave it a positive score. However, I think the level of polish and writing is rather low, and I think the paper would need a significant clean-up prior to publication.", "weaknesses": "-\tThe paper is not polished or easy to read/understand\n-\tIt’s not clear if the paper compares against relevant baselines\n-\tImprecise threat model and privacy guarantees. The threat model does not clearly specify *who* should not learn *what data* \n-\tHow does the MPC handle nonlinearities in the MLP? \n-\tThe level of formalism in the paper is very low \n\nIn your privacy guarantees, please specify *who* learns or does not learn what information. For instance, if the data holder knows the architecture of the model(s) and they know the ranked entropy of their samples, why can’t they train the model locally on the most informative samples to approximate the private model? This leakage was not explored in the paper, to my knowledge. \n\nThe paper’s evaluation considers time-accuracy tradeoffs. However, these are mostly provided implicitly in tables that do not clearly show the tradeoff. It may be helpful to show a plot with selection time on one axis and accuracy on the other, and then see different baselines, including variants of your method. Specifically, based on the results in the Appendix, I think the 1-phase variant with a dimension 2 MLP may do well enough relative to the other hyperparameter settings, especially if you consider its lower delay. But it’s hard to judge from the tables provided. Can you produce this plot and compare it to the suggested hyperparameter settings? \n\nA lot of notation seemed to be undefined or imprecisely defined. This made the paper difficult to read. For instance, in Sec. 4.1, “with a selectivity αi = Si/Si−1” if S_i is a dataset, do you mean the ratio of the *cardinalities* of S_i and S_{i-1}? In Sec 2.1 and 2.2 -- What is the difference between M_t and M_target? Why do you want to query all the samples in D on M_t instead of M_target? I thought M_t was the finetuned model, which is unknown until you finetune with the selected data? The notation $\\hat M_i$ was not defined, and the proxy model was previously defined as $M_p$. And what is $M_g$ in Figure 2? It is not defined until later in the paper, in Section 4.2. But the definition doesn’t match Figure 2 (is it the bottom K or L layers?) What is the difference between $W_i$ and $w_i$? \n\nIn the same vein, the paper does not seem to formally write out the MPC algorithm or prove any guarantees. \n\nThe paper is missing several relevant references, including one potentially important baseline for comparison: \n-\tPang et al, “Bolt: Privacy-Preserving, accurate, and efficient inference for transformers” (S&P 2024)\n\nTable 1 is hard to read. Please enlarge. Also what metric is it providing? Please make the table and caption self-contained. This is true also of the tables in the appendix, many of which don't specify what metric they are listing.\n\n\nMinor comments:\n-\tIntro: “As shown in ??,”\n-\tThe section “Workflow” is very difficult to follow—it’s not clear what you mean by ranking samples by entropy, for instance\n-\tThe model owner has a private, small validation set, on which she wants to maximize the test accuracy.  Do you mean validation accuracy?\n-\t“offline generate a random triple called Beaver triple Beaver (1992)” wrong type of citation typo\n\n* I am not an expert in MPC and may be missing relevant literature and requirements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ieCWguHSx3", "reviewer": "Reviewer_jQt4", "summary": "The paper considers the private data selection problem, i.e. the problem of a model trainer selecting data to purchase from a data owner without revealing the purchased data to the model trainer. The authors focus on the active learning framework, which targets examples which have the largest prediction entropy, i.e. which the model can learn more from, and does not require labelled examples. Ideally multi-party computation can be used to have the model trainer and data owner compute the examples' entropies (or, if entropies are themselves sensitive, a relative ordering of the examples' entropies) without revealing any other information about the examples themselves. For transformers, MPC is infeasible because transformers use high-dimensional, non-linear operations. Past work got around this issue by approximating the non-linear operations using linear operations. However, using MPC to compute these approximations remains expensive and the approximation comes at a cost in accuracy.\n\nThe authors instead propose a number of techniques to make MPC evaluation of transformers more efficient. First, they fuse multiple non-linear steps. Next, they use multi-layer perceptrons (MLPs) to approximate the fused steps and reduce their dimension (as opposed to past work, which use MLPs to reduce a single non-linear step without dimension reduction). Third, they employ a multi-phase selection protocol, where initially a small model is used to filter the initial dataset $S$ into $S_1$, and in each successive step a larger model is used to filter $S_i$ into $S_{i+1}$ until the final dataset is acquired. To find the MLP approximation and also construct the smaller models, the model trainer purchases a small arbitrary bootstrap dataset up front, and uses the inputs/outputs of the large model on this dataset to train the MLP to approximate layers of the large model. The number of layers and width of the layers, as well as the dimension of the MLPs, can be reduced to construct a smaller model.\n\nThe authors perform an empirical comparison of their data selection protocol to (1) picking data at random (2) an oracle which chooses the highest-entropy examples without MPC, and (3) MPCFormer. At varying dataset sizes, the authors' result is competitive with baseline (2) in terms of accuracy and achieves a ~200x speedup in runtime over (2), and has large accuracy improvements over (1) and (3), on a variety of empirical tasks.", "questions": "Is there a way to make the grid search practical? We probably do not have the luxury of trying MPC with a data vendor multiple times with different parameters in practice. Maybe we can do a grid search to see what parameters perform the best on a non-private test dataset, and then use these values in all actual interactions with data owners?\n\nCan you include a 'baseline' for Figure 1? i.e., show how long the corresponding operations take without using MPC and the memory requirement for each (communication rounds could be omitted, of course).", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies a problem that has been of interest in past work. It proposes a method that is both very efficient and achieves high utility in the empirical studies. The authors can operate in a more general setting (where examples are unlabelled) than past work. It is clear from the presentation what techniques the authors' method uses to improve upon the past work, and the techniques are made understandable at a high-level even to someone who is not an expert in the area. Furthermore, techniques such as using MLPs for dimension-reduction and fusing multiple operations are themselves sufficiently different from past work and a possibly interesting contribution independent of the problem of data selection.", "weaknesses": "The MLP dimensions, proxy layers, and selectivity per round are chosen via grid search, which might limit the practicality of the method. It would be nice to have either \"standard\" guidance for choosing these parameters or a justification for grid search being practical. See Questions below.\n\nThe paper also needs some editing, there are some major typography errors, though I expect this is easy to handle in a revision. For example: \n* Line 82, citation to ??\n* Line 398 - \"under 3 compute parties\" appears twice\n* Line 498, $d_i$ is not formatted properly", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YynuMsa8Yw", "reviewer": "Reviewer_8FFm", "summary": "The paper focuses on private data selection for transformers over MPC. The authors consider a two-party setting, where a model owner wishes to purchase data points from a data owner. The model owner needs this data to fine-tune a target model. To find the most relevant data points without revealing the rest of the dataset, the two parties engage in a multiparty computation. \n\nComputational and communication overhead is a key challenge in making MPC practical for data selection. In an ideal world, the model owner could evaluate its target model on data points with MPC. However, this is not practical for large transformer models, which contain nonlinearities (such as layer norm or softmax) that are prohibitively expensive to compute with MPC. Thus, an alternative approach is to use a cheaper proxy model to approximate the target model efficiently while still selecting useful datapoints. \n\nThis paper proposes a new way of building such proxy models, by replacing costly nonlinearities by more MPC-efficient, trainable, multilayer perceptrons. The authors also introduce a multiphase selection approach where datapoints are selected progressively, thereby using previously selected datapoints to improve the selection of future datapoints. Delay can also be optimized by overlapping computation and communication. \n\nThe paper is evaluated on vision and NLP tasks, and shows significant improvements in both delay and accuracy compared to prior work.", "questions": "- Have you considered alternatives to MPCFormer, such as THE-X (that you cite, Chen et al 2022) or other modern 2PC inference papers for transformers, especially if they use data-independent nonlinearity approximations? Or are there reasons why such baselines don't apply or are already outperformed by MPCFormer in a data selection setting where distillation data is scarce?\n- If I understand correctly, computing ReLUs is still a bottleneck in MPC. This might be why FFNs take most of the computation time in Fig 1. Yet, your method introduces even more ReLUs by adding MLPs. Have you considered other learnable approximations as an alternative to MLPs, such as polynomials with learnable coefficients, which could be more MPC-friendly? Why should we expect MLP approximation to be the best way to obtain MPC-friendly proxy models?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Main strengths:\n- SelectFormer shows strong improvements in delay and accuracy over baselines, which include two naive baselines (Oracle and Random) and one recent MPC inference paper (MPCFormer). \n- Multiphase selection is a nice technique. The key idea is that we can significantly reduce delay by selecting the first datapoints with coarse model proxies, and progressively use more accurate and slower proxies (trained on a now larger collection of purchased datapoints) to better select the following datapoints. It turns out that this technique also improves accuracy a bit.\n- Another useful contribution is MLP approximation of nonlinearities, where the MLPs are trained by generating a large synthetic dataset using metrics coming from the small number of datapoints already purchased.\n- The paper's evaluation is broad and strong, across both vision and NLP tasks. I appreciated the numerous experiments and very granular ablation studies, such as Fig 4 and Fig 6.\n\n\nOther strengths:\n* It is useful to compare the accuracy drop from different MLP approximations.\n- Handling imbalanced and unlabeled data is important.\n- Using computation/communication parallelism sounds intuitive, but it might not be done by other works, so it is valuable to evaluate it. This parallelism offers a nice gain in performance.", "weaknesses": "Main weaknesses:\n- I don't know the literature extensively, but I wonder if MPCFormer is really the strongest baseline against which we should evaluate SelectFormer (the other baselines, Oracle and Random, are useful to set the delay/accuracy range but are not real alternatives to SelectFormer). Indeed, as the authors note, \"MPCFORMER’s model distillation approach is ill-suited to data selection\", and I wonder if this is the reason behind MPCFormer's particularly poor accuracy (Table 3). The paper mentions THE-X (Chen et al, 2022), which could be a stronger baseline. Another potentially relevant paper is Bolt, published at S&P 24: https://eprint.iacr.org/2023/1893. I don't know these works in detail, but they might be more amenable to data selection than MPCFormer if they do not rely on data distillation or data-dependent approximations. In short, I am worried that MPCFormer might be a strawman against which SelectFormer shines too easily.\n- Another concern is that the techniques proposed in this paper seem to only apply to a quite specific application, namely MPC data selection. Hence, depending on how widespread MPC data selection is, SelectFormer could have a pretty limited impact. Indeed, the authors note that their \"MLP approximation is specifically suitable for data selection while impractical for model inference directly\", which might limit the applicability of SelectFormer to other problems.  \n- Finally, I am not an expert in MPC systems, but I am a bit skeptical of the blanket claim that \"No prior MPC systems exploit such parallelism\". I remember a similar idea being mentioned by Meta in a research whitepaper (https://research.facebook.com/publications/private-computation-framework-2-0/), and a cursory web search returned a preprint showing how \"it is possible to carefully orchestrate the computation and communication steps to overlap\" in ML MPC training and inference (https://arxiv.org/pdf/2209.13643). The paper might still be making valuable contributions in MPC parallelism, but highlighting such contributions might benefit from a more detailed comparison to prior work. \n\nMinor comments:\n* typo: \"Note that we cannot directly compare to PUMA Dong et al. (2023), which is designed under 3 compute parties. and three computing parties.\"\n* I can't find the data showing that MPS reduces total delay by 33% to 61%. Is this from the difference between PM and PMT in Figure 6? Maybe this would be easier to break down if there was a delay column in Table 4?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gkG5Ih92Ks", "reviewer": "Reviewer_hi43", "summary": "This paper presents an efficient approach to private data selection, leveraging multi-party computing (MPC) for data appraisal in complex models such as transformers and ViT. The authors propose using a proxy model that approximates the complex model by emulating non-linear modules with MLP for data appraisal. While experimental results demonstrate improved efficiency compared to random selection and MPCFormer, the paper would benefit from clearer algorithmic descriptions and more comprehensive experimental analysis.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper addresses the important and challenging problem of efficient private data selection.\n2. The proposed hierarchical algorithm demonstrates thoughtful consideration of multiple components, including multi-phase selection and dimension optimization, to enhance efficiency.", "weaknesses": "1. The pipeline of the algorithm is not clear. In multi phase selection, why do you need to query the candidate data? Whether or not to select this subset of data depends on the test data performance. It seems that when you train the MLP, except for the selected data, you also generate an Gaussian distribution for the layer, but how to use this distribution to supervise fine-tuning is not clear. In sum, I hope there will be an algorithm pipeline to clearly show each steps and which parameters are hyper-parameters.\n2. The results in Table 2 is surprising. Does it mean that MLP is enough and we can drop all non-linear layer since some of your results show that all emulations with MLP outperform no emulations. \n3. The gap between MLP and non-linear module is simply shown by the final accuracy of your task, which may contain much randomness. Could you explain the gap in embedding layer? Like how much embedding difference for different layer emulation.\n4. The experimental results are not clear. E.g., in Table 3, did you test the model under the same communication and computation budget? In Figure 5, what does 1 phase mean? How many phased do you use in the \"ours\"? Why not compare your delay with the baseline MPCFormer?\n5. Lack of analysis. As your work focus on improving the efficiency and keeping performance, it is important to specifically analyze the computation and communication costs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)