Agnostic Learning of K-Juntas over "small" distribution

Question

I have two questions related to agnostic learning, one specific and one more general, specifically when the distribution relative to which the learner must operate is given explicitly as part of the input.

The specific question is closely related to proper agnostic learning of k-Juntas, though the connection is fuzzy. Consider the following optimization problem.

Problem statement: You are given a set $S$ of $m$ binary strings in $\{0,1\}^n$, a boolean function $f: \{0,1\}^n \to \{0,1\}$, and a parameter $k$. Find a k-Junta $g:\{0,1\}^n \to \{0,1\}$ which agrees with $f$ on as many elements of $S$ as possible.

Question: What is the best (multiplicative or additive) approximation algorithm for this problem if you are allowed to query f on points in S, and are allowed to run in time polynomial in m, n, and k? What about if you are allowed to run in time polynomial in m,n and $2^k$?

I sense that the answer to this question may be known or follow directly from existing techniques. A literature search reveals several works on agnostic learning of k-Juntas relative to the uniform distribution, where additive approximation schemes are possible (see, e.g. here). Observe that the problem above differs from the settings considered in much of the literature in that the set of points S in the hypercube that we "care" about classifying correctly is explicitly given in the input. In essense, this can be thought of as learning with respect to a uniform distribution on a subset S of the hypercube, where the runtime of the learner may depend on the size of S and the learner is allowed to query $f$ on $S$. This interpretation raises a more general reference-request question.

Question: Is there literature on agnostic learning relative to "succinctly given" distributions? Anyone know of example papers? What are the keywords one should search for? Also, to what extent do upper/lower bound results on agnostic learning w.r.t the uniform distribution imply something for succinct-distribution variants of the same problem?

Answer 1

Uniform convergence bounds should imply that agnostic learning with respect to a succinct distribution specified by a finite set S is no easier than learning with respect to the uniform distribution, at least for large enough $S$. Specifically, for any class of functions $C$ with VC-dimension $d$, the canonical algorithm which takes a randomly sampled collection of $m$ points for $m = O(d/\epsilon^2)$ and finds the function $f \in C$ which minimizes error with respect to the sample, will be within an additive $\epsilon$ of the minimum error function over the entire target distribution. So if you have an algorithm for agnostically learning with respect to an explicitly represented set of points $S$, you can learn over the uniform distribution by just taking a sufficiently large sample of points $S$ and feeding $S$ to your algorithm for concise distributions. In fact, this holds for any distribution, not just the uniform distribution.

Now there are ${d \choose k}\cdot 2^{2^{k}}$ size $k$ juntas, and so they have VC-dimension at most $d \leq 2^k + k\log d \approx 2^k$. So for large enough $S$ (at least, larger than $2^k$), lower bounds for agnostically learning w.r.t. the uniform distribution (or any other distribution) should apply to the problem of learning w.r.t. a concise distribution.