Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

By Vitaly Feldman, Crist'obal Guzm'an, Santosh Srinivas Vempala. 2015

96 citations recorded by the source corpus.

Stochastic convex optimization, by which the objective is the expectation of a random convex function, is an important and widely used method with numerous applications in machine learning, statistics, operations research, and other areas. We study the complexity of stochastic convex optimization given only statistical query (SQ) access to the objective function. We show that well-known and popular first-order iterative methods can be implemented using only statistical queries. For many cases of interest, we derive nearly matching upper and lower bounds on the estimation (sample) complexity, including linear optimization in the most general setting. We then present several consequences for machine learning, differential privacy, and proving concrete lower bounds on the power of convex optimization–based methods. The key ingredient of our work is SQ algorithms and lower bounds for estimating the mean vector of a distribution over vectors supported on a convex body in Rd. This natural problem has not been previously studied, and we show that our solutions can be used to get substantially improved SQ versions of Perceptron and other online algorithms for learning halfspaces.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

Citations in the corpus

Privacy Amplification by Iteration (2018, background): “The question of optimizing multiple loss functions was also studied in [21], [40].”
Private Stochastic Convex Optimization with Optimal Rates (2019, background): “It is well-known and easy to see that the effect of this additional approximation error on the standard convergence bounds is that excess empirical loss may grow by at most the error times the diameter of the domain (e.g. [NB10, FGV15]).”
Limits on Gradient Compression for Stochastic Optimization (2020, methodology): “Also, stochastic optimization over lp spaces using a biased first-order oracle which is constructed by using only statistical query access to the underlying data was considered in [10].”
Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, background): “SQ algorithms for a wide range of convex ERM problems were proposed by [13], implying good risk bounds for LDP. [9] established matching upper and lower bounds for convex risk minimization problems.”
A General Characterization of the Statistical Query Complexity (2016, methodology): “A weaker (exponential) separation of sign-rank and VC dimension using the class of parity functions was first obtained in Forster’s breakthrough result (Forster, 2002) (and, as pointed out in (Feldman et al., 2015), is also implied by known results on SQ complexity of learning parities and halfspace”
Lossless Compression of Efficient Private Local Randomizers (2021, background): “[FGV15] who show that the mean estimation problem can be solved by having each client answer a single counting query.”
Provable limitations of deep learning (2018, background): “, which are algorithms that access estimates of the expected value of some query function over the underlying data distribution (e.g., the rst moment statistics of inputs’ coordinates). In particular [FGV17] shows that gradient-based algorithms with approximate oracle access are realizable as statis”