論文の概要: Derandomizing Multi-Distribution Learning

• arxiv url: http://arxiv.org/abs/2409.17567v1
• Date: Thu, 26 Sep 2024 06:28:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-28 22:56:36.399772
• Title: Derandomizing Multi-Distribution Learning
• Title（参考訳）: Derandomizing Multi-Distribution Learning
• Authors: Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy
• Abstract要約: マルチディストリビューション学習では、複数のデータ分散でうまく動作する単一の予測子を学習する。 近年の研究では、オラクル効率のアルゴリズムにより、ほぼ最適サンプルの複雑さが達成されている。 これらのアルゴリズムは、複数の分布に対する決定論的予測子を生成するためにデランドマイズできるのだろうか?
• 参考スコア（独自算出の注目度）: 28.514129340758938
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recent research on multi-distribution learning, focusing on binary loss and finite VC dimension classes, has shown near-optimal sample complexity that is achieved with oracle efficient algorithms. That is, these algorithms are computationally efficient given an efficient ERM for the class. Unlike in classical PAC learning, where the optimal sample complexity is achieved with deterministic predictors, current multi-distribution learning algorithms output randomized predictors. This raises the question: can these algorithms be derandomized to produce a deterministic predictor for multiple distributions? Through a reduction to discrepancy minimization, we show that derandomizing multi-distribution learning is computationally hard, even when ERM is computationally efficient. On the positive side, we identify a structural condition enabling an efficient black-box reduction, converting existing randomized multi-distribution predictors into deterministic ones.
• Abstract（参考訳）: マルチディストリビューションまたは協調学習は、トレーニング中の各サンプルを使用して、複数のデータ分布でうまく動作する単一の予測子を学習する。 近年,二分損失と有限VC次元クラスに着目した多分散学習の研究が,オラクル効率のよいアルゴリズムで達成された準最適サンプルの複雑さを示している。 すなわち、これらのアルゴリズムは、クラスに対して効率的なEMMを考えると、計算的に効率的である。 古典的なPAC学習では、決定論的予測器によって最適なサンプル複雑性が達成されるのとは異なり、現在のマルチディストリビューション学習アルゴリズムはランダム化された予測器を出力する。 これらのアルゴリズムは、複数の分布に対する決定論的予測子を生成するためにデランドマイズできるのだろうか? 離散化を最小化することにより,EMM が計算効率が高い場合でも,マルチディストリビューション学習のデランドマイズが困難であることを示す。 正の面では、効率的なブラックボックス削減を可能にする構造条件を特定し、既存のランダム化マルチディストリビューション予測器を決定論的に変換する。

関連論文リスト

• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
  論文  参考訳（メタデータ） (2025-01-15T04:09:21Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。 近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。 本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T13:44:49Z)
• Collaborative Learning with Different Labeling Functions [7.228285747845779]
  我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。 データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-16T04:32:22Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Quantifying Inherent Randomness in Machine Learning Algorithms [7.591218883378448]
  本稿では,モデル学習におけるランダム性,およびデータセットのトレーニングおよびテストサブセットへの分割におけるランダム性の影響を実験的に検討する。 我々は、ランダムフォレスト(RF)、グラディエントブースティングマシン(GBM)、フィードフォワードニューラルネットワーク(FFNN)の予測性能の変動の大きさを定量化し、比較する。
  論文  参考訳（メタデータ） (2022-06-24T15:49:52Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Expectation propagation on the diluted Bayesian classifier [0.0]
  本稿では,二項分類の文脈におけるスパース特徴選択の問題に対処する統計力学にインスパイアされた戦略を導入する。 予測伝搬(EP)として知られる計算スキームは、分類規則を学習する連続重みの知覚を訓練するために用いられる。 EPは、変数選択特性、推定精度、計算複雑性の点で頑健で競争力のあるアルゴリズムである。
  論文  参考訳（メタデータ） (2020-09-20T23:59:44Z)
• Differentially Private ADMM for Convex Distributed Learning: Improved Accuracy via Multi-Step Approximation [10.742065340992525]
  Alternating Direction Method of Multipliers (ADMM) は分散学習において一般的な計算方法である。 トレーニングデータが機密性のある場合には、交換されたイテレートが深刻なプライバシー上の懸念を引き起こす。 本稿では,様々な凸学習問題に対する精度の向上を図った分散ADMMを提案する。
  論文  参考訳（メタデータ） (2020-05-16T07:17:31Z)

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

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