論文の概要: On the Dichotomy Between Privacy and Traceability in $\ell_p$ Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2502.17384v1
• Date: Mon, 24 Feb 2025 18:10:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:53:01.593751
• Title: On the Dichotomy Between Privacy and Traceability in $\ell_p$ Stochastic Convex Optimization
• Title（参考訳）: $\ell_p$確率凸最適化におけるプライバシーとトレーサビリティの分離について
• Authors: Sasha Voitovych, Mahdi Haghifam, Idan Attias, Gintare Karolina Dziugaite, Roi Livni, Daniel M. Roy,
• Abstract要約: 我々は,$ell_p$測地の下での凸最適化(SCO)における暗記の必要性について検討する。 我々の主な成果は、SCOにおけるトレーサビリティと過剰リスクの根本的なトレードオフを明らかにすることである。
• 参考スコア（独自算出の注目度）: 34.23960368886818
• License:
• Abstract: In this paper, we investigate the necessity of memorization in stochastic convex optimization (SCO) under $\ell_p$ geometries. Informally, we say a learning algorithm memorizes $m$ samples (or is $m$-traceable) if, by analyzing its output, it is possible to identify at least $m$ of its training samples. Our main results uncover a fundamental tradeoff between traceability and excess risk in SCO. For every $p\in [1,\infty)$, we establish the existence of a risk threshold below which any sample-efficient learner must memorize a \em{constant fraction} of its sample. For $p\in [1,2]$, this threshold coincides with best risk of differentially private (DP) algorithms, i.e., above this threshold, there are algorithms that do not memorize even a single sample. This establishes a sharp dichotomy between privacy and traceability for $p \in [1,2]$. For $p \in (2,\infty)$, this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route of proving these results, we introduce a complexity notion we term \em{trace value} of a problem, which unifies privacy lower bounds and traceability results, and prove a sparse variant of the fingerprinting lemma.
• Abstract（参考訳）: 本稿では,確率凸最適化(SCO)におけるメモリ化の必要性を$\ell_p$ジオメトリで検討する。 学習アルゴリズムは、その出力を分析することによって、少なくとも$m$のトレーニングサンプルを識別できる場合、$m$サンプル(または$m$-traceable)を記憶する。 我々の主な成果は、SCOにおけるトレーサビリティと過剰リスクの根本的なトレードオフを明らかにすることである。 すべての$p\in [1,\infty)$に対して、サンプル効率の学習者はサンプルの \em{constant fraction} を記憶しなければならないリスクしきい値の存在を確立する。 p\in [1,2]$の場合、この閾値は微分プライベート(DP)アルゴリズムの最良のリスクと一致する。 これにより、プライバシーとトレーサビリティの急激な二分法が$p \in [1,2]$で確立される。 p \in (2,\infty)$の場合、この閾値は代わりにDP学習の新たな下限を与える。 これらの結果を証明するために、プライバシーの低い境界値とトレーサビリティーを統一し、フィンガープリント補題のスパース変種を証明する、問題の「em{trace value}」という複雑さの概念を導入する。

関連論文リスト

• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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