論文の概要: Computationally Efficient Replicable Learning of Parities

• arxiv url: http://arxiv.org/abs/2602.09499v1
• Date: Tue, 10 Feb 2026 07:53:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-11 20:17:43.434256
• Title: Computationally Efficient Replicable Learning of Parities
• Title（参考訳）: 計算効率の良い親の再現性学習
• Authors: Moshe Noivirt, Jessica Sorrell, Eliad Tsfadia,
• Abstract要約: 第一の貢献は、任意の分布上のパリティの実学習のための計算効率の良い初のレプリカブルアルゴリズムである。 私たちのメインビルディングブロックは、ベクトルの集合が与えられた場合、そのほとんどをカバーする線形スパンの部分空間を出力する、新しく、効率的で、複製可能なアルゴリズムです。
• 参考スコア（独自算出の注目度）: 9.218538486245059
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational relationship between replicability (Impagliazzo et al. [STOC `22], Ghazi et al. [NeurIPS `21]) and other stability notions. Specifically, we focus on replicable PAC learning and its connections to differential privacy (Dwork et al. [TCC 2006]) and to the statistical query (SQ) model (Kearns [JACM `98]). Statistically, it was known that differentially private learning and replicable learning are equivalent and strictly more powerful than SQ-learning. Yet, computationally, all previously known efficient (i.e., polynomial-time) replicable learning algorithms were confined to SQ-learnable tasks or restricted distributions, in contrast to differentially private learning. Our main contribution is the first computationally efficient replicable algorithm for realizable learning of parities over arbitrary distributions, a task that is known to be hard in the SQ-model, but possible under differential privacy. This result provides the first evidence that efficient replicable learning over general distributions strictly extends efficient SQ-learning, and is closer in power to efficient differentially private learning, despite computational separations between replicability and privacy. Our main building block is a new, efficient, and replicable algorithm that, given a set of vectors, outputs a subspace of their linear span that covers most of them.
• Abstract（参考訳）: 複製可能性 (Impagliazzo et al [STOC `22], Ghazi et al [NeurIPS `21]) と他の安定性概念の計算的関係について検討する。 具体的には、複製可能なPAC学習とその差分プライバシー(Dwork et al [TCC 2006])と統計クエリ(SQ)モデル(Kearns [JACM `98])に焦点をあてる。 統計的には、微分プライベートラーニングとレプリカブルラーニングはSQラーニングと同等で、より強力であることが知られている。 しかし、計算学的には、以前に知られていた全ての効率(多項式時間)のレプリカブル学習アルゴリズムは、微分プライベート学習とは対照的に、SQ学習可能なタスクや制限された分布に限られていた。 我々の主な貢献は、任意の分布に対してパリティを再現できる最初の計算効率の良いレプリカブルアルゴリズムであり、これはSQモデルでは難しいことが知られているが、微分プライバシー下では可能である。 この結果は、一般的な分布に対する効率的なレプリカブル学習が、効率のよいSQ-ラーニングを厳密に拡張し、複製性とプライバシの計算的分離にもかかわらず、効率的な微分プライベートラーニングに近づきつつあるという最初の証拠となる。 私たちのメインビルディングブロックは、ベクトルの集合が与えられた場合、そのほとんどをカバーする線形スパンの部分空間を出力する、新しく、効率的で、複製可能なアルゴリズムです。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
  インフルエンサーベースのアンラーニングは、個別のトレーニングサンプルがモデルパラメータに与える影響を再トレーニングせずに推定する顕著なアプローチとして現れてきた。 本稿では,暗記(増分学習)と忘れ(未学習)の理論的関連性を確立する。 本稿では、インフルエンス近似アンラーニングアルゴリズムを導入し、インクリメンタルな視点から効率的なマシンアンラーニングを行う。
  論文  参考訳（メタデータ） (2025-07-31T05:34:27Z)
• On the Computational Landscape of Replicable Learning [40.274579987732416]
  本稿では,Impagliazzo,Lei,Pitassi,Sorrellによって導入された安定性の概念である,アルゴリズム的複製性の計算的側面について考察する。 複製可能性と他の学習可能性の概念との強い統計的つながりを築き上げた最近の研究に動機づけられた我々は、複製可能性とこれらの学習パラダイムの間の計算的つながりをよりよく理解することを目指している。
  論文  参考訳（メタデータ） (2024-05-24T14:30:40Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  本稿では,反復学習アルゴリズムにおける一般化とプライバシ保護の関係を2つのステップで検討する。 我々は、$(varepsilon, delta)$-differential privacyは、マルチデータベース学習アルゴリズムに縛られる平均的な一般化を意味することを証明している。 次に,ほとんどの学習アルゴリズムが共有する反復的な性質が,プライバシーの保護とさらなる一般化にどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2020-07-18T09:12:03Z)

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

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