Data Value Estimation on Private Gradients

Zijian Zhou, Xinyi Xu, Daniela Rus, Bryan Kian Hsiang Low · 2024

Read Data Value Estimation on Private Gradients by Zijian Zhou, Xinyi Xu, Daniela Rus, Bryan Kian Hsiang Low (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17008.txt.

Introduction

Zijian Zhou, Xinyi Xu, Daniela Rus, and Bryan Low ask whether data can be valued under differential privacy in a paper from 2024. Privacy noise is usually sprinkled on training gradients as random static. Data valuation scores each training point's worth for pricing and federated learning. The two practices collide badly.

With random noise, the error of a value estimate grows in step with the compute budget. More work yields guesses no better than chance, a paradox. The fix is correlated noise, shaped across steps on purpose. Careful correlation provably cancels the runaway error growth. Privacy and fair payment for data can then coexist. The result matters for any marketplace built on private gradients.

Catalog record

CREATORZijian Zhou, Xinyi Xu, Daniela Rus, Bryan Kian Hsiang Low
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17008

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Data Value Estimation on Private Gradients Zijian Zhou, Xinyi Xu, Daniela Rus, Bryan Kian Hsiang Low Abstract For gradient-based machine learning (ML) methods commonly adopted in practice such as stochastic gradient descent, the de facto differential privacy (DP) technique is perturbing the gradients with random Gaussian noise. Data valuation attributes the ML performance to the training data and is widely used in privacy-aware applications that require enforcing DP such as data pricing, collaborative ML, and federated learning (FL). Can existing data valuation methods still be used when DP is enforced via gradient perturbations? We show that the answer is no with the default approach of injecting i.i.d. random noise to the gradients because the estimation uncertainty of the data value estimation paradoxically linearly scales with more estimation budget, producing estimates almost like random guesses. To address this issue, we propose to instead inject carefully correlated noise to provably remove the linear scaling of estimation uncertainty w.r.t. the budget. We also empirically demonstrate that our method gives better data value estimates on various ML tasks and is applicable to use cases including dataset valuation and FL. 1 Introduction With growing data privacy regulations ( Bukaty, 2019 ; Council of European Union, 2014 ) and machine learning (ML) model attacks ( Shokri et al., 2017 ) , privacy has become a primary concern in many scenarios such as collaborative ML ( Sim et al., 2020 ; Xu et al., 2021 ) and federated learning (FL) ( McMahan et al., 2017 ; Yang et al., 2019 ) . Differential privacy (DP) ( Dwork & Roth, 2014 ) is commonly adopted as the de facto framework to provide privacy protection for training data with theoretical guarantees. In deep learning, DP is typically achieved by perturbing the gradients w.r.t. the model’s loss on the training data ( Abadi et al., 2016 ) . Data valuation ( Ghorbani & Zou, 2019 ) has received increased interest from providing attribution for parties in collaborative ML ( Sim et al., 2022 ) and identifying data quality for data curation ( Ghorbani & Zou, 2019 ) and data marketplace ( Agarwal et al., 2019 ) . Data values are often estimated with sampling-based methods such as Monte Carlo ( Castro et al., 2009 ) on user statistics, e.g. gradients of user data ( Ghorbani & Zou, 2019 ) . However, the sensitive nature of the user statistics requires privacy during data valuation to protect the data of participants in collaboration ( Sim et al., 2023 ) or to facilitate interaction between data buyers and sellers in a marketplace ( Chen et al., 2023 ) . Specifically, enforcing DP on the data is desirable in these scenarios for two reasons: 1) DP enjoys the post-processing immunity ( Dwork & Roth, 2014 ) , allowing further access to data without risking privacy leakage; 2) DP offers a natural trade-off between privacy protection and data quality: Data contributors can determine at their discretion the level of information protection at the expense of degraded data quality. While some previous works considered DP in data valuation ( Sim et al., 2023 ; Wang et al., 2023 ; Watson et al., 2022 ) , they either focused on a limited class of ML models or required a trusted central server, both of which are difficult to satisfy in real-world scenarios ( Sim et al., 2022 ) . A natural question arises: Can we circumvent these two challenges in data valuation while enforcing DP? One might think of perturbing gradients on user data before using them for updating a gradient-trained parametric model to overcome the challenges. Unfortunately, we demonstrate that the naive approach of adding i.i.d. Gaussian noise ( Dwork & Roth, 2014 ) to user gradients leads to practically useless data value estimates: The perturbation on the gradients erodes the information they carry, leading to a lowered data value and increased data value estimation uncertainty because the noise introduced by such perturbation accumulates with repeated evaluations (i.e., sampling methods methods ( Castro et al., 2009 ; Maleki et al., 2014 ) ). While a lowered (mean of) data value estimate is intuitive and expected as a result of information loss ( Dwork et al., 2015 ; Kairouz et al., 2015 ) , increased estimation uncertainty can render existing data valuation methods useless because the magnitude of the noise scales with the evaluation budget for a fixed DP guarantee. As an illustration, the 3 rd figure of Fig. 2 shows that as the number of evaluations k increases, removing data with high data value estimates produces a curve closer to that with random removal, implying that more evaluation samples, paradoxically, have worsened the quality of data value estimates. We theoretically account for this counter-intuitive phenomenon by showing that perturbation introduced by DP can cause the estimation uncertainty of data value estimates, measured in terms of the variance brought by the perturbation, to scale linearly in the number of evaluations . Fortunately, through our developed theoretical analysis, we derive an insight that leads to a method for controlling the estimation uncertainty. We focus the analysis on the family of semivalues widely adopted as data valuation metrics such as data Shapley ( Ghorbani & Zou, 2019 ) , Beta Shapley ( Kwon & Zou, 2022 ) , and data Banzhaf ( Wang & Jia, 2023 ) . We revisit the paradigm of data valuation in the context of gradient-based DP ML and thus design a technique that perturbs the gradients with correlated noise in repeated evaluations to mitigate the above issue. Contrary to the linear scaling of estimation uncertainty of the data value estimates with the evaluation budget in the naive approach, our proposed method is shown to control the estimation uncertainty to a constant . Additionally, we empirically demonstrate that, on various ML tasks, our proposed method produces (i) greater model degradation from removing high-value data; and (ii) higher AUC scores in identifying label-corrupted data. In comparison, the naive approach performs similarly to random selection. We also apply our approach to other scenarios including dataset valuation ( Wu et al., 2022 ) and FL ( McMahan et al., 2017 ) . Our specific contributions are summarized as follows: \bullet We formalize a notion of estimation uncertainty ( Eq. 3 ) to specifically target the uncertainty due to DP. We then theoretically identify that under the naive approach of injecting i.i.d. noise for DP, the estimation uncertainty grows in \Omega(k) with the evaluation budget k ( Proposition 5.1 ), resulting in low-quality data value estimates. \bullet As mitigation, we propose a simple yet effective approach (in Algorithm 1 ) via injecting correlated noise to control the estimation uncertainty to \mathcal{O}(1) ( Proposition 5.4 ) as opposed to \Omega(k) . \bullet We empirically demonstrate the implications of the escalating estimation uncertainty shown by the near-random performance on the data removal task ( Section 6.1 ) and noisy label detection task ( Section 6.2 ). Our approach outperforms the baseline approach on these tasks ( Section 6.2 ) and on noisy label detection task in dataset valuation and FL ( Section 6.3 ). 2 Related Work Prior works ( Sim et al., 2023 ; Wang et al., 2023 ; Watson

Read the complete text