論文の概要: On the Computational Landscape of Replicable Learning

• arxiv url: http://arxiv.org/abs/2405.15599v1
• Date: Fri, 24 May 2024 14:30:40 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 13:40:24.441801
• Title: On the Computational Landscape of Replicable Learning
• Title（参考訳）: Replicable Learningの計算ランドスケープについて
• Authors: Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, Felix Zhou,
• Abstract要約: 本稿では,Impagliazzo,Lei,Pitassi,Sorrellによって導入された安定性の概念である,アルゴリズム的複製性の計算的側面について考察する。 複製可能性と他の学習可能性の概念との強い統計的つながりを築き上げた最近の研究に動機づけられた我々は、複製可能性とこれらの学習パラダイムの間の計算的つながりをよりよく理解することを目指している。
• 参考スコア（独自算出の注目度）: 40.274579987732416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022]. Motivated by a recent line of work that established strong statistical connections between replicability and other notions of learnability such as online learning, private learning, and SQ learning, we aim to understand better the computational connections between replicability and these learning paradigms. Our first result shows that there is a concept class that is efficiently replicably PAC learnable, but, under standard cryptographic assumptions, no efficient online learner exists for this class. Subsequently, we design an efficient replicable learner for PAC learning parities when the marginal distribution is far from uniform, making progress on a question posed by Impagliazzo et al. [2022]. To obtain this result, we design a replicable lifting framework inspired by Blanc, Lange, Malik, and Tan [2023] that transforms in a black-box manner efficient replicable PAC learners under the uniform marginal distribution over the Boolean hypercube to replicable PAC learners under any marginal distribution, with sample and time complexity that depends on a certain measure of the complexity of the distribution. Finally, we show that any pure DP learner can be transformed to a replicable one in time polynomial in the accuracy, confidence parameters and exponential in the representation dimension of the underlying hypothesis class.
• Abstract（参考訳）: 我々は,Impagliazzo, Lei, Pitassi, Sorrell [2022] によって導入された安定性の概念であるアルゴリズムの複製性の計算的側面を研究する。 複製可能性とオンライン学習,私的学習,SQ学習などの学習可能性の概念との間に強い統計的関係を築き上げた最近の一連の研究によって,我々は,複製可能性とこれらの学習パラダイムとの計算的関係をよりよく理解することを目指している。 最初の結果は、PACを効率的に複製可能な概念クラスが存在することを示しているが、標準的な暗号的仮定の下では、このクラスには効率的なオンライン学習者が存在しないことを示している。 次に,Phigliazzoらによる質問に対して,限界分布が一様ではない場合に,PAC学習パリティのための効率的なレプリカブル学習器を設計する。 この結果を得るために,Branc,Lange,Malik,Tan[2023]にインスパイアされたレプリカブルリフトフレームワークを設計した。これは,Branc,Lange,Malik,Tan[2023]をベースとした,ブラックボックス方式の効率的なレプリカブルPAC学習者に対して,Booleanハイパーキューブ上の一様辺縁分布の下でのレプリカブルPAC学習者に対して,その分布の複雑性の一定の尺度に依存するサンプルと時間複雑性を用いて変換する。 最後に、任意の純粋DP学習者は、精度、信頼性パラメータ、指数関数を基礎となる仮説クラスの表現次元において複製可能な多項式に変換することができることを示す。

関連論文リスト

• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Replicability in High Dimensional Statistics [18.543059748500358]
  本稿では,いくつかの基本的高次元統計課題に対する再現性の計算的および統計的コストについて検討する。 我々の主な貢献は、最適なレプリカブルアルゴリズムと高次元等尺波の計算的および統計的等価性を確立することである。
  論文  参考訳（メタデータ） (2024-06-04T00:06:42Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [56.192740509339565]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• Replicable Reinforcement Learning [15.857503103543308]
  本稿では、並列値反復のための証明可能なレプリカブルアルゴリズムと、エピソード設定における証明可能なR-maxのレプリカブルバージョンを提供する。 これらは制御問題に対する最初の公式なレプリカ化結果であり、バッチ学習設定とは異なるレプリケーションの課題を提示している。
  論文  参考訳（メタデータ） (2023-05-24T16:05:15Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。 我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
  論文  参考訳（メタデータ） (2023-04-27T09:39:30Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learning [92.18524491615548]
  対照的な自己指導型学習は、(深層)強化学習(RL)の実践にうまく統合されている 我々は,低ランク遷移を伴うマルコフ決定過程(MDP)とマルコフゲーム(MG)のクラスにおいて,コントラスト学習によってRLをどのように強化できるかを検討する。 オンライン環境下では,MDPやMGのオンラインRLアルゴリズムと対照的な損失を生かした,新しい高信頼境界(UCB)型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-29T17:29:08Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Network Classifiers Based on Social Learning [71.86764107527812]
  空間と時間に対して独立に訓練された分類器を結合する新しい手法を提案する。 提案したアーキテクチャは、ラベルのないデータで時間とともに予測性能を改善することができる。 この戦略は高い確率で一貫した学習をもたらすことが示され、未訓練の分類器に対して頑健な構造が得られる。
  論文  参考訳（メタデータ） (2020-10-23T11:18:20Z)

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

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