Learning Low Degree Hypergraphs
- URL: http://arxiv.org/abs/2202.09989v1
- Date: Mon, 21 Feb 2022 04:38:24 GMT
- Title: Learning Low Degree Hypergraphs
- Authors: Eric Balkanski, Oussama Hanguir, Shatian Wang
- Abstract summary: We study the problem of learning a hypergraph via edge detecting 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.
- Score: 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.
Related papers
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
Given a query $S subset U$, $|S|=2$, the oracle returns yes if the points are in the same cluster and no otherwise.
For adaptive algorithms with pair-wise queries, the number of required queries is known to be $Theta(nk)$.
Non-adaptive schemes require $Omega(n2)$ queries, which matches the trivial $O(n2)$ upper bound attained by querying every pair of points.
arXiv Detail & Related papers (2024-09-17T05:56:07Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
We present an algorithm that learns the edges of $G$ in at most $tildeO(d2m3/4)$ quantum queries.
In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $tildeO(sqrtm)$ quantum queries.
arXiv Detail & Related papers (2024-02-28T21:23:40Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$.
While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
arXiv Detail & Related papers (2021-04-29T14:50:03Z) - Quantum algorithms for graph problems with cut queries [17.149741568581096]
We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)2)$ many cut queries.
We also show that a quantum algorithm can learn a general graph with $O(sqrtm log(n)3/2)$ many cut queries.
arXiv Detail & Related papers (2020-07-16T12:21:01Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy.
For small enough $epsilon$, we show an improved algorithm with sample complexity.
arXiv Detail & Related papers (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
We study the problem of agnostic $Q$-learning with function approximation in deterministic systems.
We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
arXiv Detail & Related papers (2020-02-17T18:41:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.