論文の概要: Private List Learnability vs. Online List Learnability

• arxiv url: http://arxiv.org/abs/2506.12856v1
• Date: Sun, 15 Jun 2025 14:10:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.004566
• Title: Private List Learnability vs. Online List Learnability
• Title（参考訳）: Private List Learnability vs. Online List Learnability
• Authors: Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari,
• Abstract要約: この研究は、PACリスト学習の文脈において、差分プライバシー(DP)とオンライン学習の関連について考察する。 有限$k$-モノトーン次元は、有限$k$-リトルストーン次元とともにDP$k$-list学習可能性の別の必要条件であることを示す。
• 参考スコア（独自算出の注目度）: 26.86418374191696
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning. In this setting, a $k$-list learner outputs a list of $k$ potential predictions for an instance $x$ and incurs a loss if the true label of $x$ is not included in the list. A basic result in the multiclass PAC framework with a finite number of labels states that private learnability is equivalent to online learnability [Alon, Livni, Malliaris, and Moran (2019); Bun, Livni, and Moran (2020); Jung, Kim, and Tewari (2020)]. Perhaps surprisingly, we show that this equivalence does not hold in the context of list learning. Specifically, we prove that, unlike in the multiclass setting, a finite $k$-Littlestone dimensio--a variant of the classical Littlestone dimension that characterizes online $k$-list learnability--is not a sufficient condition for DP $k$-list learnability. However, similar to the multiclass case, we prove that it remains a necessary condition. To demonstrate where the equivalence breaks down, we provide an example showing that the class of monotone functions with $k+1$ labels over $\mathbb{N}$ is online $k$-list learnable, but not DP $k$-list learnable. This leads us to introduce a new combinatorial dimension, the \emph{$k$-monotone dimension}, which serves as a generalization of the threshold dimension. Unlike the multiclass setting, where the Littlestone and threshold dimensions are finite together, for $k>1$, the $k$-Littlestone and $k$-monotone dimensions do not exhibit this relationship. We prove that a finite $k$-monotone dimension is another necessary condition for DP $k$-list learnability, alongside finite $k$-Littlestone dimension. Whether the finiteness of both dimensions implies private $k$-list learnability remains an open question.
• Abstract（参考訳）: この研究は、PACリスト学習の文脈において、差分プライバシー(DP)とオンライン学習の関連について考察する。 この設定では、$k$-listの学習者は、インスタンス$x$に対して$k$の潜在的な予測のリストを出力し、リストに$x$の本当のラベルが含まれない場合に損失を発生させる。 有限個のラベルを持つ多クラスPACフレームワークの基本的な結果は、プライベート学習可能性はオンライン学習可能性(Alon, Livni, Malliaris, and Moran (2019), Bun, Livni, and Moran (2020), Jung, Kim, and Tewari (2020)]と等価であることを示している。 おそらく驚くべきことに、この等価性はリスト学習の文脈では成り立たない。 特に、マルチクラス設定とは異なり、有限$k$-Littlestone dimensioは、オンライン$k$-listの学習可能性を示す古典的なLittlestone次元の変種であり、DP$k$-listの学習性には十分でないことを証明している。 しかし、マルチクラスの場合と同様に、必要条件のままであることを示す。 等価性がどこにあるかを示すために、$\mathbb{N}$ 上の $k+1$ ラベルを持つ単調関数のクラスがオンライン $k$-list 学習可能であるが DP $k$-list 学習可能でないことを示す例を示す。 これにより、しきい値次元の一般化に役立つ新しい組合せ次元 \emph{$k$-monotone dimension} を導入することができる。 リトルストーン次元としきい値次元が有限であるマルチクラス設定とは異なり、$k>1$の場合、$k$-リトルストーン次元と$k$-モノトン次元は、この関係を示さない。 有限$k$-モノトン次元は、有限$k$-リトルストーン次元と共にDP$k$-リストの可読性にとって別の必要条件であることを示す。 両方の次元の有限性がプライベート$k$-listの可読性を意味するかどうかは未解決の問題である。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
  この研究は、差分プライベート(DP)とオンライン学習との関係について研究を続けている。 一般分類タスクにおいては,DP学習性はオンライン学習性を意味することを示す。
  論文  参考訳（メタデータ） (2024-07-10T15:43:30Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Simple online learning with consistent oracle [55.43220407902113]
  オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
  論文  参考訳（メタデータ） (2023-08-15T21:50:40Z)
• Self-Directed Linear Classification [50.659479930171585]
  オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。 そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
  論文  参考訳（メタデータ） (2023-08-06T15:38:44Z)
• A Characterization of List Learnability [15.368858716555888]
  我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
  論文  参考訳（メタデータ） (2022-11-07T21:28:05Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)

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

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