Locally Private Nonparametric Contextual Multi-armed Bandits

• URL: http://arxiv.org/abs/2503.08098v2
• Date: Tue, 25 Mar 2025 16:13:14 GMT
• Title: Locally Private Nonparametric Contextual Multi-armed Bandits
• Authors: Yuheng Ma, Feiyu Jiang, Zifeng Zhao, Hanfang Yang, Yi Yu,
• Abstract summary: We address the challenge of nonparametric contextual multi-armed bandits (MAB) under local differential privacy (LDP)<n>We develop a uniform-confidence-bound-type estimator, showing its minimax optimality supported by a matching minimax lower bound.
• Score: 10.579415536953132
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by privacy concerns in sequential decision-making on sensitive data, we address the challenge of nonparametric contextual multi-armed bandits (MAB) under local differential privacy (LDP). We develop a uniform-confidence-bound-type estimator, showing its minimax optimality supported by a matching minimax lower bound. We further consider the case where auxiliary datasets are available, subject also to (possibly heterogeneous) LDP constraints. Under the widely-used covariate shift framework, we propose a jump-start scheme to effectively utilize the auxiliary data, the minimax optimality of which is further established by a matching lower bound. Comprehensive experiments on both synthetic and real-world datasets validate our theoretical results and underscore the effectiveness of the proposed methods.

Related papers

• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD. We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Minimax Optimal Two-Sample Testing under Local Differential Privacy [3.3317825075368908]
  We explore the trade-off between privacy and statistical utility in private two-sample testing under local differential privacy (LDP) We introduce private permutation tests using practical privacy mechanisms such as Laplace, discrete Laplace, and Google's RAPPOR. We study continuous data via binning and study its uniform separation rates under LDP over H"older and Besov smoothness classes.
  arXiv  Detail & Related papers  (2024-11-13T22:44:25Z)
• Reward-Augmented Data Enhances Direct Preference Alignment of LLMs [63.32585910975191]
  We introduce reward-conditioned Large Language Models (LLMs) that learn from the entire spectrum of response quality within the dataset.<n>We propose an effective yet simple data relabeling method that conditions the preference pairs on quality scores to construct a reward-augmented dataset.
  arXiv  Detail & Related papers  (2024-10-10T16:01:51Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• Optimal Locally Private Nonparametric Classification with Public Data [2.631955426232593]
  We investigate the problem of public data assisted non-interactive Local Differentially Private (LDP) learning with a focus on non-parametric classification. Under the posterior drift assumption, we derive the mini-max optimal convergence rate with LDP constraint. We present a novel approach, the locally differentially private classification tree, which attains the mini-max optimal convergence rate.
  arXiv  Detail & Related papers  (2023-11-19T16:35:01Z)
• Theoretically Principled Federated Learning for Balancing Privacy and Utility [61.03993520243198]
  We propose a general learning framework for the protection mechanisms that protects privacy via distorting model parameters. It can achieve personalized utility-privacy trade-off for each model parameter, on each client, at each communication round in federated learning.
  arXiv  Detail & Related papers  (2023-05-24T13:44:02Z)
• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning [8.760651633031342]
  We propose a novel approach called the score attack, which provides a lower bound on the differential-privacy-constrained minimax risk of parameter estimation. It can optimally lower bound the minimax risk of estimating unknown model parameters, up to a logarithmic factor, while ensuring differential privacy for a range of statistical problems.
  arXiv  Detail & Related papers  (2023-03-13T14:26:27Z)
• FedLAP-DP: Federated Learning by Sharing Differentially Private Loss Approximations [53.268801169075836]
  We propose FedLAP-DP, a novel privacy-preserving approach for federated learning. A formal privacy analysis demonstrates that FedLAP-DP incurs the same privacy costs as typical gradient-sharing schemes. Our approach presents a faster convergence speed compared to typical gradient-sharing methods.
  arXiv  Detail & Related papers  (2023-02-02T12:56:46Z)
• Differentially Private Decentralized Optimization with Relay Communication [1.2695958417031445]
  We introduce a new measure: Privacy Leakage Frequency (PLF), which reveals the relationship between communication and privacy leakage of algorithms. A novel differentially private decentralized primal--dual algorithm named DP-RECAL is proposed to take advantage of operator splitting method and relay communication mechanism to experience less PLF.
  arXiv  Detail & Related papers  (2022-12-21T09:05:36Z)
• Mitigating Algorithmic Bias with Limited Annotations [65.060639928772]
  When sensitive attributes are not disclosed or available, it is needed to manually annotate a small part of the training data to mitigate bias. We propose Active Penalization Of Discrimination (APOD), an interactive framework to guide the limited annotations towards maximally eliminating the effect of algorithmic bias. APOD shows comparable performance to fully annotated bias mitigation, which demonstrates that APOD could benefit real-world applications when sensitive information is limited.
  arXiv  Detail & Related papers  (2022-07-20T16:31:19Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  We study episodic two-player zero-sum Markov games (MGs) in the offline setting. The goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori.
  arXiv  Detail & Related papers  (2022-02-15T15:39:30Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.