論文の概要: Differentially Private Worst-group Risk Minimization

• arxiv url: http://arxiv.org/abs/2402.19437v1
• Date: Thu, 29 Feb 2024 18:38:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-01 13:26:40.278515
• Title: Differentially Private Worst-group Risk Minimization
• Title（参考訳）: 個人別リスク最小化
• Authors: Xinyu Zhou, Raef Bassily
• Abstract要約: 本稿では,超過最悪の集団集団リスクを$tildeO(fracpsqrtdKepsilon + sqrtfracpK)$とするアルゴリズムを提案する。 我々の速度は、各分布がK/p$の固定サイズのデータセットによって観測されるときにほぼ最適である。
• 参考スコア（独自算出の注目度）: 17.81078463701913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate a systematic study of worst-group risk minimization under $(\epsilon, \delta)$-differential privacy (DP). The goal is to privately find a model that approximately minimizes the maximal risk across $p$ sub-populations (groups) with different distributions, where each group distribution is accessed via a sample oracle. We first present a new algorithm that achieves excess worst-group population risk of $\tilde{O}(\frac{p\sqrt{d}}{K\epsilon} + \sqrt{\frac{p}{K}})$, where $K$ is the total number of samples drawn from all groups and $d$ is the problem dimension. Our rate is nearly optimal when each distribution is observed via a fixed-size dataset of size $K/p$. Our result is based on a new stability-based analysis for the generalization error. In particular, we show that $\Delta$-uniform argument stability implies $\tilde{O}(\Delta + \frac{1}{\sqrt{n}})$ generalization error w.r.t. the worst-group risk, where $n$ is the number of samples drawn from each sample oracle. Next, we propose an algorithmic framework for worst-group population risk minimization using any DP online convex optimization algorithm as a subroutine. Hence, we give another excess risk bound of $\tilde{O}\left( \sqrt{\frac{d^{1/2}}{\epsilon K}} +\sqrt{\frac{p}{K\epsilon^2}} \right)$. Assuming the typical setting of $\epsilon=\Theta(1)$, this bound is more favorable than our first bound in a certain range of $p$ as a function of $K$ and $d$. Finally, we study differentially private worst-group empirical risk minimization in the offline setting, where each group distribution is observed by a fixed-size dataset. We present a new algorithm with nearly optimal excess risk of $\tilde{O}(\frac{p\sqrt{d}}{K\epsilon})$.
• Abstract（参考訳）: 我々は,最低グループリスク最小化の体系的研究を,$(\epsilon, \delta)$-differential privacy (DP)の下で開始する。 目的は、異なる分布を持つ$p$サブポピュレーション (groups) にまたがる最大リスクをほぼ最小化するモデルをプライベートに見つけることであり、各群分布はサンプルのオラクルを通してアクセスされる。 まず,すべての群から抽出されたサンプルの総数として$K$,$d$が問題次元である場合,$\tilde{O}(\frac{p\sqrt{d}}{K\epsilon} + \sqrt {\frac{p}{K}})$という超過最悪の集団集団リスクを実現するアルゴリズムを提案する。 我々の速度は、各分布がK/p$の固定サイズのデータセットによって観測されるときにほぼ最適である。 この結果は、一般化誤差に対する新しい安定性に基づく解析に基づいている。 特に、$\delta$-uniform の引数安定性は$\tilde{o}(\delta + \frac{1}{\sqrt{n}})$ 一般化エラー w.r.t を暗示している。 次に,DPオンライン凸最適化アルゴリズムをサブルーチンとして用いた,最悪の集団リスク最小化のためのアルゴリズムフレームワークを提案する。 したがって、別の余剰リスクは$\tilde{O}\left( \sqrt {\frac{d^{1/2}}{\epsilon K}} +\sqrt {\frac{p}{K\epsilon^2}} \right)$である。 典型的な$\epsilon=\theta(1)$ の設定を仮定すると、このバウンドは、k$ と $d$ の関数として、ある範囲の$p$ の最初のバウンドよりも有利である。 最後に、各グループ分布を固定サイズデータセットで観測するオフライン環境での個人的最悪のグループ経験的リスク最小化について検討する。 我々は,$\tilde{o}(\frac{p\sqrt{d}}{k\epsilon})$の最適超過リスクを持つ新しいアルゴリズムを提案する。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。