Ke Yang

In this paper, we study the problem of using statistical

query (SQ) to learn highly correlated boolean functions, namely, a

class of functions where any

pair agree on significantly more than a fraction 1/2 of the inputs.

We give a limit on how well ...
more >>>

Ke Yang

We prove two lower bounds on the Statistical Query (SQ) learning

model. The first lower bound is on weak-learning. We prove that for a

concept class of SQ-dimension $d$, a running time of

$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is

defined to be the maximum number ...
more >>>

Avrim Blum, Ke Yang

We introduce a ``Statistical Query Sampling'' model, in which

the goal of an algorithm is to produce an element in a hidden set

$S\subseteq\bit^n$ with reasonable probability. The algorithm

gains information about $S$ through oracle calls (statistical

queries), where the algorithm submits a query function $g(\cdot)$

and receives ...
more >>>

Jacob Steinhardt, Gregory Valiant, Stefan Wager

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>