Fugu-MT 論文翻訳(概要): Learning stochastic decision trees

論文の概要: Learning stochastic decision trees

arxiv url: http://arxiv.org/abs/2105.03594v1
Date: Sat, 8 May 2021 04:54:12 GMT
ステータス: 処理完了
システム内更新日: 2021-05-11 15:09:40.841702
Title: Learning stochastic decision trees
Title（参考訳）: 確率的決定木を学ぶ
Authors: Guy Blanc and Jane Lange and Li-Yang Tan
Abstract要約: 対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
参考スコア（独自算出の注目度）: 19.304587350775385
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give a quasipolynomial-time algorithm for learning stochastic decision trees that is optimally resilient to adversarial noise. Given an $\eta$-corrupted set of uniform random samples labeled by a size-$s$ stochastic decision tree, our algorithm runs in time $n^{O(\log(s/\varepsilon)/\varepsilon^2)}$ and returns a hypothesis with error within an additive $2\eta + \varepsilon$ of the Bayes optimal. An additive $2\eta$ is the information-theoretic minimum. Previously no non-trivial algorithm with a guarantee of $O(\eta) + \varepsilon$ was known, even for weaker noise models. Our algorithm is furthermore proper, returning a hypothesis that is itself a decision tree; previously no such algorithm was known even in the noiseless setting.
Abstract（参考訳）: 対向雑音に最適な確率的決定木を学習するための準多項式時間アルゴリズムを提案する。サイズ-s$ 確率的決定木でラベル付けされた一様ランダムなサンプルの$\eta$ が与えられると、アルゴリズムは時間$n^{o(\log(s/\varepsilon)/\varepsilon^2)} で実行され、ベイズの最適値の2\eta + \varepsilon$ 内の誤差を持つ仮説を返す。追加の$2\eta$は情報理論の最小値である。以前は、より弱いノイズモデルであっても、$O(\eta) + \varepsilon$を保証する非自明なアルゴリズムは知られていない。我々のアルゴリズムはさらに適切であり、それ自体が決定木である仮説を返す。

関連論文リスト

Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文参考訳（メタデータ） (2024-02-24T06:36:08Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文参考訳（メタデータ） (2023-05-08T08:49:01Z)
Agnostic proper learning of monotone functions: beyond the black-box correction barrier [6.47243430672461]
2tildeO(sqrtn/varepsilon)$ 未知関数 $f:pm 1n rightarrow pm 1$ の一様ランダムな例を与えられたとき、我々のアルゴリズムは仮説 $g:pm 1n rightarrow pm 1$ を出力する。また,2tildeO(sqrt)の実行時間を用いて,未知関数$f$からモノトンへの距離を加算誤差$varepsilon$まで推定するアルゴリズムも提供する。
論文参考訳（メタデータ） (2023-04-05T18:52:10Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文参考訳（メタデータ） (2022-11-14T13:09:12Z)
Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文参考訳（メタデータ） (2022-10-12T16:25:48Z)
Testing and reconstruction via decision trees [19.304587350775385]
決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。 mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
論文参考訳（メタデータ） (2020-12-16T04:18:00Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文参考訳（メタデータ） (2020-03-03T18:46:34Z)

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