論文の概要: Approximate Replicability in Learning

• arxiv url: http://arxiv.org/abs/2510.20200v1
• Date: Thu, 23 Oct 2025 04:36:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:17.331483
• Title: Approximate Replicability in Learning
• Title（参考訳）: 学習における近似的再現性
• Authors: Max Hopkins, Russell Impagliazzo, Christopher Ye,
• Abstract要約: そこで本研究では,PAC学習における再現性の自然な緩和を3つ提案する。 一定の再現性パラメータに対して、サンプル最適PAC学習者を得る。
• 参考スコア（独自算出の注目度）: 5.613537675448949
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness). While a strong and interesting notion of stability, the cost of replicability can be prohibitive: there is no replicable algorithm, for instance, for tasks as simple as threshold learning (Bun et al. STOC '23). Given such strong impossibility results we ask: under what approximate notions of replicability is learning possible? In this work, we propose three natural relaxations of replicability in the context of PAC learning: (1) Pointwise: the learner must be consistent on any fixed input, but not across all inputs simultaneously, (2) Approximate: the learner must output hypotheses that classify most of the distribution consistently, (3) Semi: the algorithm is fully replicable, but may additionally use shared unlabeled samples. In all three cases, for constant replicability parameters, we obtain sample-optimal agnostic PAC learners: (1) and (2) are achievable for ``free" using $\Theta(d/\alpha^2)$ samples, while (3) requires $\Theta(d^2/\alpha^2)$ labeled samples.
• Abstract（参考訳）: Impagliazzo et al STOC '22)によって導入されたリプリケータビリティは、アルゴリズムが入力の再サンプリング(共有ランダム性へのアクセス)の下で安定であるべきだという考えである。 例えば、しきい値学習(Bun et al STOC '23)のような単純なタスクに対して、複製可能なアルゴリズムは存在しない。 複製可能性という近似的な概念が学べるのか? 本研究では,PAC学習の文脈における再現性に関する3つの自然な緩和法を提案する。(1) ポイント: 学習者は任意の固定された入力に対して一貫性を持たなければならないが,全ての入力に対して同時に一貫性を持たなければならないこと,(2) 近似: 学習者は,ほとんどの分布を一貫した分類を行う仮説を出力しなければならないこと,(3) 半: アルゴリズムは完全に複製可能であるが,共有されていないサンプルを使用することもできる。 いずれの場合も, 一定の再現性パラメータに対して, (1) と (2) は $\Theta(d/\alpha^2)$ サンプルを用いて ``free' に対して達成可能であり, (3) には $\Theta(d^2/\alpha^2)$ ラベル付きサンプルが必要である。

関連論文リスト

• The Role of Randomness in Stability [20.718747268949112]
  学習における安定性という2つの重要な概念,すなわち複製可能性と差分プライバシーのランダム性複雑性について検討する。 安定に対する弱強強化定理(英語版)を証明し、タスクのランダム性複雑性は最適な複製確率によって厳しく制御される。
  論文  参考訳（メタデータ） (2025-02-11T23:06:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Replicability and stability in learning [16.936594801109557]
  Impagliazzo氏、Lei氏、Pitassi氏、Sorrell氏(22)は先頃、マシンラーニングにおけるレプリカ性の研究を開始した。 我々は、任意のレプリカブルアルゴリズムを、任意の確率が 1 に近く同じ出力を生成するように拡張する方法を示す。 任意の確率で 1 に近い確率で達成できるように、リストの複製性を高めることができることを証明した。
  論文  参考訳（メタデータ） (2023-04-07T17:52:26Z)
• List and Certificate Complexities in Replicable Learning [0.7829352305480285]
  リストの複製性と証明書の複製性という2つの実現可能な複製性について考察する。 リストと証明書の複雑さに最適な学習問題のアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-04-05T06:05:27Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• On the Stability and Generalization of Triplet Learning [55.75784102837832]
  トリプルトラーニング(トリプルトラーニング)、すなわちトリプルトデータから学ぶことは、コンピュータビジョンタスクに大きな注目を集めている。 本稿では,安定解析を利用した三重項学習の一般化保証について検討する。
  論文  参考訳（メタデータ） (2023-02-20T07:32:50Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。 双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
  論文  参考訳（メタデータ） (2020-05-24T18:11:57Z)

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

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