論文の概要: Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

• arxiv url: http://arxiv.org/abs/2105.05555v1
• Date: Wed, 12 May 2021 10:11:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-13 12:28:24.614093
• Title: Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
• Title（参考訳）: 固定構造ベイズネットワークのほぼ線形時間におけるロバスト学習
• Authors: Yu Cheng and Honghao Lin
• Abstract要約: 我々は、サンプルの$epsilon$-fractionが逆転して破損するベイズネットワークを学習する問題を研究する。 本稿では,この問題に対する線形時間アルゴリズムを,次元に依存しない誤差保証で提示する。
• 参考スコア（独自算出の注目度）: 13.617081331738056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning Bayesian networks where an $\epsilon$-fraction of the samples are adversarially corrupted. We focus on the fully-observable case where the underlying graph structure is known. In this work, we present the first nearly-linear time algorithm for this problem with a dimension-independent error guarantee. Previous robust algorithms with comparable error guarantees are slower by at least a factor of $(d/\epsilon)$, where $d$ is the number of variables in the Bayesian network and $\epsilon$ is the fraction of corrupted samples. Our algorithm and analysis are considerably simpler than those in previous work. We achieve this by establishing a direct connection between robust learning of Bayesian networks and robust mean estimation. As a subroutine in our algorithm, we develop a robust mean estimation algorithm whose runtime is nearly-linear in the number of nonzeros in the input samples, which may be of independent interest.
• Abstract（参考訳）: 我々は,サンプルの$\epsilon$-fractionが敵対的に破損するベイズネットワークを学習する問題について検討する。 基礎となるグラフ構造が知られている完全観測可能なケースに焦点を当てる。 本研究では,この問題に対して次元非依存な誤りを保証した最初の近似時間アルゴリズムを提案する。 比較エラー保証を持つ従来のロバストアルゴリズムは、少なくとも$(d/\epsilon)$という係数で遅く、ここで$d$はベイズネットワーク内の変数の数、$\epsilon$は破損したサンプルの分数である。 私たちのアルゴリズムと分析は、以前の研究よりもかなりシンプルです。 ベイズネットワークのロバストな学習とロバストな平均推定との直接的な関係を確立することでこれを実現できる。 提案アルゴリズムのサブルーチンとして,入力サンプルの非ゼロ数に対して,実行時間がほぼ直線であるロバスト平均推定アルゴリズムを開発した。

関連論文リスト

• Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
  我々は citekothari2018robust で導入された正準平方和プログラムを新たに解析する。 このプログラムは,すべての $varepsilon に対して[0,frac12)$ の誤差率を効率よく達成できることを示す。
  論文  参考訳（メタデータ） (2024-11-21T16:57:05Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• A Sparse Structure Learning Algorithm for Bayesian Network Identification from Discrete High-Dimensional Data [0.40611352512781856]
  本稿では,高次元離散データから疎構造ベイズネットワークを学習する問題に対処する。 本稿では,空間特性とDAG特性を同時に満足するスコア関数を提案する。 具体的には,アルゴリズムを高次元データで効率的に動作させるため,最適化アルゴリズムに分散低減法を用いる。
  論文  参考訳（メタデータ） (2021-08-21T12:21:01Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Active Structure Learning of Bayesian Networks in an Observational Setting [21.376800678915558]
  観測環境におけるベイズネットワークのアクティブ構造学習について検討した。 本稿では,高い確率で最適なスコアに対して$epsilon$-closeのスコアを持つ構造を求める,新しい能動学習アルゴリズムを提案する。 安定」と呼ばれる分布のクラスについて、$d$がネットワーク変数の数である$widetildeOmega(d3)$の係数までのサンプル複雑さの減少が得られることを示しています。
  論文  参考訳（メタデータ） (2021-03-25T12:50:14Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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