# Is your function low-dimensional?

arXiv: https://arxiv.org/abs/1806.10057 · HTML: https://mlsanity.com/paper/1806.10057/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2018.

## Built on by (most cited first, 3 of 3)

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)

## Abstract (arXiv)

We study the problem of testing if a function depends on a small number of linear directions of its input data. We call a function f a linear k-junta if it is completely determined by some k-dimensional subspace of the input space. In this paper, we study the problem of testing whether a given n variable function f : ℝn → 0,1, is a linear k-junta or ε-far from all linear k-juntas, where the closeness is measured with respect to the Gaussian measure on ℝn. Linear k-juntas are a common generalization of two fundamental classes from Boolean function analysis (both of which have been studied in property testing) 1. k- juntas which are functions on the Boolean cube which depend on at most k of the variables and 2. intersection of k halfspaces, a fundamental geometric concept class. We show that the class of linear k-juntas is not testable, but adding a surface area constraint makes it testable: we give a mathsfpoly(k · s/ε)-query non-adaptive tester for linear k-juntas with surface area at most s. We show that the polynomial dependence on s is necessary. Moreover, we show that if the function is a linear k-junta with surface area at most s, we give a (s · k)O(k)-query non-adaptive algorithm to learn the function up to a rotation of the basis. In particular, this implies that we can test the class of intersections of k halfspaces in ℝn with query complexity independent of n.