Fugu-MT 論文翻訳(概要): Open Problem: Properly learning decision trees in polynomial time?

論文の概要: Open Problem: Properly learning decision trees in polynomial time?

arxiv url: http://arxiv.org/abs/2206.14431v1
Date: Wed, 29 Jun 2022 07:07:44 GMT
ステータス: 処理完了
システム内更新日: 2022-06-30 20:05:06.306691
Title: Open Problem: Properly learning decision trees in polynomial time?
Title（参考訳）: オープン問題:多項式時間で決定木を適切に学習する?
Authors: Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Abstract要約: 著者らは最近、一様分布の下で決定木を適切に学習するために、$nO(loglog n)$ time member queryを行った。この問題に対する以前の最速のアルゴリズムは、$nO(log n)$ timeで実行された。
参考スコア（独自算出の注目度）: 21.751077835678952
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The authors recently gave an $n^{O(\log\log n)}$ time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previous fastest algorithm for this problem ran in $n^{O(\log n)}$ time, a consequence of Ehrenfeucht and Haussler (1989)'s classic algorithm for the distribution-free setting. In this article we highlight the natural open problem of obtaining a polynomial-time algorithm, discuss possible avenues towards obtaining it, and state intermediate milestones that we believe are of independent interest.
Abstract（参考訳）: 著者らは最近、一様分布の下で決定木を適切に学習するための$n^{O(\log\log n)}$タイムメンバシップクエリアルゴリズムを作成した(Blanc et al., 2021)。この問題の以前の最速アルゴリズムは$n^{o(\log n)} で実行され、ehrenfeucht と haussler (1989) による分散フリー設定の古典的なアルゴリズムの結果である。本稿では、多項式時間アルゴリズムの自然開問題、それを得るための可能な道のり、そして我々が興味を持っていると信じている中間的マイルストーンを述べる。

関連論文リスト

Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
論文参考訳（メタデータ） (2024-09-19T21:40:57Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。目標は最小限のコストで予測を行うことだ。最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文参考訳（メタデータ） (2023-03-03T04:39:53Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
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)
Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文参考訳（メタデータ） (2021-09-14T11:12:32Z)
Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文参考訳（メタデータ） (2021-09-01T22:12:47Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)
Learning stochastic decision trees [19.304587350775385]
対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
論文参考訳（メタデータ） (2021-05-08T04:54:12Z)
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文参考訳（メタデータ） (2020-10-04T22:19:06Z)

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