We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A -junta function is a function which depends on only coordinates of the input. For relatively small w.r.t. the input size , learning -junta fu…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
10 results for “juntas”
Paper proves L2 regression can learn k-juntas without distributional assumptions.
problem Learning k-juntas using L2 regression without distributional restrictions.
method L2 polynomial regression and minimum mean square estimation (MMSE).
result Agnostic PAC learning of k-juntas using L2 polynomial regression.
In recent years, there are many attempts to understand popular heuristics. An example of such a heuristic algorithm is the ID3 algorithm for learning decision trees. This algorithm is commonly used in practice, but there are very few theoretical works studying its behavior. In this paper, we analyze the ID3 algorithm, …
Two statistical tasks are shown to have equivalent sample complexity.
problem Determining if a function depends on only a few variables and identifying those variables.
method Proved statistical equivalence of feature selection and junta testing through sample complexity analysis.
result Brute-force algorithm is sample-optimal for both tasks with optimal sample size.
Decision tree learning heuristics fail even in smoothed analysis for complex targets.
problem Greedy decision tree learning heuristics fail for complex target functions in the smoothed analysis model.
method Construct counterexamples and analyze the behavior of heuristics in the smoothed setting and agnostic setting.
result Greedy decision tree learning heuristics can build trees of exponential depth before achieving high accuracy for certain complex target functions.
Randomly biased data makes complex models as easy to learn as simple ones.
problem Learning complex models like multi-index and sparse Boolean functions.
method Introducing a small random shift in the first moment of the data distribution.
result Randomly biased data makes Gaussian single index models and sparse Boolean functions as easy to learn as linear functions.
Noise stability improves understanding of Transformer models.
problem Lack of robustness metrics for real-valued domains and junta-like input dependence in modern LLMs.
method Proposed noise stability as a new metric and developed a practical regularization method.
result Noise stability regularization method accelerates training by 35-75%.
New sparsification theorem for Gaussian processes reduces dimensionality.
problem Dimension-independent sparsification of Gaussian process suprema.
method Dimension-independent sparsification of Gaussian process suprema.
result Sparsifier size is independent of and .
The paper establishes lower bounds for learning polynomial functions on hypercube.
problem Establishing lower bounds for learning polynomial functions on the discrete hypercube.
method Using packing numbers and Fourier analysis, the paper proves lower bounds on the number of queries needed for learning.
result Proves sharp lower bounds on the number of queries required for learning polynomial functions.
Algorithm learns polynomials in Gaussian inputs with reduced sample complexity.
problem Learning polynomials of few relevant dimensions in high-dimensional data.
method Filtered PCA for warm start, geodesic SGD for accuracy.
result Sample complexity roughly , runtime .