論文の概要: Learning Low Degree Hypergraphs
- arxiv url: http://arxiv.org/abs/2202.09989v1
- Date: Mon, 21 Feb 2022 04:38:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 12:21:37.776858
- Title: Learning Low Degree Hypergraphs
- Title（参考訳）: 低次ハイパーグラフの学習
- Authors: Eric Balkanski, Oussama Hanguir, Shatian Wang
- Abstract要約: エッジ検出クエリによるハイパーグラフ学習の問題について検討する。
本稿では,エッジサイズが指数関数的に大きくなるクエリの複雑さに悩まされることなく,学習可能なハイパーグラフの族を特定することを目的とする。
- 参考スコア（独自算出の注目度）: 12.515216618616206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of learning a hypergraph via edge detecting queries. In
this problem, a learner queries subsets of vertices of a hidden hypergraph and
observes whether these subsets contain an edge or not. In general, learning a
hypergraph with $m$ edges of maximum size $d$ requires $\Omega((2m/d)^{d/2})$
queries. In this paper, we aim to identify families of hypergraphs that can be
learned without suffering from a query complexity that grows exponentially in
the size of the edges.
We show that hypermatchings and low-degree near-uniform hypergraphs with $n$
vertices are learnable with poly$(n)$ queries. For learning hypermatchings
(hypergraphs of maximum degree $ 1$), we give an $O(\log^3 n)$-round algorithm
with $O(n \log^5 n)$ queries. We complement this upper bound by showing that
there are no algorithms with poly$(n)$ queries that learn hypermatchings in
$o(\log \log n)$ adaptive rounds. For hypergraphs with maximum degree $\Delta$
and edge size ratio $\rho$, we give a non-adaptive algorithm with $O((2n)^{\rho
\Delta+1}\log^2 n)$ queries. To the best of our knowledge, these are the first
algorithms with poly$(n, m)$ query complexity for learning non-trivial families
of hypergraphs that have a super-constant number of edges of super-constant
size.
- Abstract（参考訳）: エッジ検出クエリによるハイパーグラフ学習の問題について検討する。
この問題において、学習者は、隠れたハイパーグラフの頂点のサブセットをクエリし、これらのサブセットがエッジを含むか否かを観察する。
一般に、最大サイズ$d$のエッジを持つハイパーグラフを学ぶには、$\Omega((2m/d)^{d/2})$クエリが必要である。
本稿では,エッジサイズで指数関数的に増加するクエリ複雑性に苦しむことなく学習可能なハイパーグラフの族を特定することを目的とする。
n$頂点を持つ超マッチングと低次近一様ハイパーグラフはpoly$で学習可能であることを示す。
(n)$クエリ。
ハイパーマッチング(最大次数1$のハイパーグラフ)を学ぶには、$o(\log^3)を与える。
n)$o(n \log^5 によるラウンドアルゴリズム
n)$クエリ。
この上限を補うために、poly$のアルゴリズムが存在しないことを示す。
(n)$o(\log \log)でハイパーマッチングを学ぶクエリ
n) 適応ラウンド$アダプティブラウンド。
最大次数$\Delta$とエッジサイズ比$\rho$のハイパーグラフに対して、$O((2n)^{\rho \Delta+1}\log^2の非適応アルゴリズムを与える。
n)$クエリ。
我々の知る限りでは、これらはpoly$(n,)を用いた最初のアルゴリズムである。
m)超定数サイズのエッジ数を持つ非自明なハイパーグラフの族を学習するためのクエリ複雑性。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - 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) - 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) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。
また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
論文 参考訳（メタデータ） (2020-07-16T12:21:01Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10: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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。