Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

Vitaly Feldman (), Cristóbal Guzmán () and Santosh Vempala ()
Additional contact information
Vitaly Feldman: Apple, Inc., Cupertino, California 95014
Cristóbal Guzmán: Institute for Mathematical and Computational Engineering, Facultad de Matemáticas & Escuela de Ingeniería, Pontificia Universidad Católica de Chile, Region Metropolitana, 3580000 Santiago, Chile
Santosh Vempala: ANID – Millennium Science Initiative Program – Millennium Nucleus Center for the Discovery of Structures in Complex Data, 7820244 Santiago, Chile; School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia 30332

Mathematics of Operations Research, 2021, vol. 46, issue 3, 912-945

Abstract: 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 R d . 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.

Keywords: Primary: 90C15; secondary: 68Q32; Primary: Programming/stochastic; stochastic; programming; convex; nonlinear; data; statistics (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1111 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:912-945

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().