Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE

• URL: http://arxiv.org/abs/2203.16100v1
• Date: Wed, 30 Mar 2022 07:11:01 GMT
• Title: Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE
• Abstract summary: We provide an end-to-end Renyi DP based-framework for differentially private top-$k$ selection. We show that our construction improves the privacy-utility trade-offs compared to the previous top-$k$ selection algorithms.
• Score: 19.344510696808282
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide an end-to-end Renyi DP based-framework for differentially private top-$k$ selection. Unlike previous approaches, which require a data-independent choice on $k$, we propose to privately release a data-dependent choice of $k$ such that the gap between $k$-th and the $(k+1)$st "quality" is large. This is achieved by a novel application of the Report-Noisy-Max. Not only does this eliminate one hyperparameter, the adaptive choice of $k$ also certifies the stability of the top-$k$ indices in the unordered set so we can release them using a variant of propose-test-release (PTR) without adding noise. We show that our construction improves the privacy-utility trade-offs compared to the previous top-$k$ selection algorithms theoretically and empirically. Additionally, we apply our algorithm to "Private Aggregation of Teacher Ensembles (PATE)" in multi-label classification tasks with a large number of labels and show that it leads to significant performance gains.

Related papers

• Selective Ensemble Based on Preference-Directed Multi-Objective Bandits [90.75513823660775]
  We formalize a sequential decision problem under partially specified linear preferences.<n>We then propose a preference-directed upper confidence bound (PrefUCB) algorithm.<n> Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate our method.
  arXiv  Detail & Related papers  (2026-06-20T07:52:46Z)
• Optimal Rates for Differentially Private Hypothesis Testing with E-values [38.69101315030117]
  Given two distributions $mathbbP$ and $mathbbQ$, what is the maximum achievable e-power when testing $Xsim mathbbPn$ against $XsimmathbbQn$ with e-values that satisfy $varepsilon$-differential privacy?<n>We characterize the optimal rate for this problem and provide an algorithm which matches it exactly.<n>In the sequential setting, when observations arrive one-by-one and the analyst chooses when to halt, we give matching upper and lower bounds on the stopping times of
  arXiv  Detail & Related papers  (2026-05-27T18:00:13Z)
• One-Stage Top-$k$ Learning-to-Defer: Score-Based Surrogates with Theoretical Guarantees [3.6787328174619254]
  We introduce the first one-stage Top-$k$ Learning-to-Defer framework.<n>We learn a shared score-based model that selects the $k$ most cost-effective entities-labels or experts-per input.<n>Experiments on CIFAR-10 and SVHN confirm that our one-stage Top-$k$ method strictly outperforms Top-1 deferral.
  arXiv  Detail & Related papers  (2025-05-15T10:41:16Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants. There is no differentially private distributed method for training, non-feedback problems. We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms. We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Differentially Private Best-Arm Identification [14.916947598339988]
  Best Arm Identification (BAI) problems are progressively used for data-sensitive applications. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence in both the local and central models.
  arXiv  Detail & Related papers  (2024-06-10T16:02:48Z)
• Privacy Profiles for Private Selection [21.162924003105484]
  We work out an easy-to-use recipe that bounds privacy profiles of ReportNoisyMax and PrivateTuning using the privacy profiles of the base algorithms they corral. Our approach improves over all regimes of interest and leads to substantial benefits in end-to-end private learning experiments.
  arXiv  Detail & Related papers  (2024-02-09T08:31:46Z)
• Variance Alignment Score: A Simple But Tough-to-Beat Data Selection Method for Multimodal Contrastive Learning [17.40655778450583]
  We propose a principled metric named Variance Alignment Score (VAS), which has the form $langle Sigma_texttest, Sigma_irangle$. We show that applying VAS and CLIP scores together can outperform baselines by a margin of $1.3%$ on 38 evaluation sets for noisy dataset DataComp and $2.5%$ on VTAB for high-quality dataset CC12M.
  arXiv  Detail & Related papers  (2024-02-03T06:29:04Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Optimal Unbiased Randomizers for Regression with Label Differential Privacy [61.63619647307816]
  We propose a new family of label randomizers for training regression models under the constraint of label differential privacy (DP) We demonstrate that these randomizers achieve state-of-the-art privacy-utility trade-offs on several datasets.
  arXiv  Detail & Related papers  (2023-12-09T19:58:34Z)
• On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence [16.295693624977563]
  We study the problem of Best Arm Identification with fixed confidence under $epsilon$-global Differential Privacy. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget. We propose AdaP-TT, an $epsilon$-global DP variant of the Top Two algorithm.
  arXiv  Detail & Related papers  (2023-09-05T13:07:25Z)
• Ranking Inferences Based on the Top Choice of Multiway Comparisons [2.468314282946207]
  This paper considers ranking inference of $n$ items based on the observed data on the top choice among $M$ randomly selected items at each trial. It is a useful modification of the Plackett-Luce model for $M$-way ranking with only the top choice observed and is an extension of the celebrated Bradley-Terry-Luce model that corresponds to $M=2$.
  arXiv  Detail & Related papers  (2022-11-22T02:34:52Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• PATE-AAE: Incorporating Adversarial Autoencoder into Private Aggregation of Teacher Ensembles for Spoken Command Classification [53.764020085834645]
  We propose an adversarial autoencoder (AAE) to replace generative adversarial network (GAN) in the private aggregation of teacher ensembles (PATE) AAE architecture allows us to obtain good synthetic speechnative upon a discriminative training of latent vectors. PATE-AAE improves the average classification accuracy by +$2.11%$ and +$6.60%$, respectively, when compared with alternative privacy-preserving solutions.
  arXiv  Detail & Related papers  (2021-04-02T23:10:57Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)

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.