A General Characterization of the Statistical Query Complexity

By Vitaly Feldman. 2016

65 citations recorded by the source corpus.

Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution $D$ instead of i.i.d.~ samples from $D$. Given a query function $\phi:X \rightarrow [-1,1]$, the oracle returns an estimate of ${\bf E}_{ x\sim D}[\phi(x)]$ within some tolerance $\tau_\phi$ that roughly corresponds to the number of samples. In this work we demonstrate that the complexity of solving general problems over distributions using SQ algorithms can be captured by a relatively simple notion of statistical dimension that we introduce. SQ algorithms capture a broad spectrum of algorithmic approaches used in theory and practice, most notably, convex optimization techniques. Hence our statistical dimension allows to investigate the power of a variety of algorithmic approaches by analyzing a single linear-algebraic parameter. Such characterizations were investigated over the past 20 years in learning theory but prior characterizations are restricted to the much simpler setting of classification problems relative to a fixed distribution on the domain (Blum et al., 1994; Bshouty and Feldman, 2002; Yang, 2001; Simon, 2007; Feldman, 2012; Szorenyi, 2009). Our characterization is also the first to precisely characterize the necessary tolerance of queries. We give applications of our techniques to two open problems in learning theory and to algorithms that are subject to memory and communication constraints.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “7 We observe that the unifying treatment based on chi-square distance is reminiscent of the lower bounds for learning under statistical queries (SQ) derived in [24], [25], [47].”
Adversarial examples from computational constraints (2018, background): “Moreover, there are very few problems in any domain with exponential SQ hardness for which polynomial time algorithms are known; in fact, the only such problems involve solving systems of linear equations over finite fields (Feldman, 2017).”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “A recent line of work [FGR + 13, FGV15, FPV15, Fel16a] developed a framework of SQ algorithms for search problems over distributions, which encompasses the linear regression problem studied here.”
Dealing with Range Anxiety in Mean Estimation via Statistical Queries (2016, methodology): “However, it is unknown how to obtain lower bounds against this stronger oracle using existing analysis techniques ( e.g. [FGRVX12; FPV13; Fel16]).”