Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization

Simple item page
dc.contributor.authorFeldman, Vitaly
dc.contributor.authorGuzman, Cristobal
dc.contributor.authorVempala, Santosh
dc.date.accessioned2024-01-10T13:10:23Z
dc.date.available2024-01-10T13:10:23Z
dc.date.issued2021
dc.description.abstractStochastic 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 Perception and other online algorithms for learning halfspaces.
dc.fechaingreso.objetodigital2024-05-16
dc.format.extent34 páginas
dc.fuente.origenWOS
dc.identifier.doi10.1287/moor.2020.1111
dc.identifier.eissn1526-5471
dc.identifier.issn0364-765X
dc.identifier.urihttps://doi.org/10.1287/moor.2020.1111
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/77849
dc.identifier.wosidWOS:000686221800005
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Guzman Paredes, Cristobal Andres; 0000-0002-1498-2055; 1041986
dc.issue.numero3
dc.language.isoen
dc.nota.accesocontenido parcial
dc.pagina.final945
dc.pagina.inicio912
dc.publisherINFORMS
dc.revistaMATHEMATICS OF OPERATIONS RESEARCH
dc.rightsacceso restringido
dc.subjectstochastic
dc.subjectprogramming
dc.subjectconvex
dc.subjectnonlinear
dc.subjectdata
dc.subjectstatistics
dc.subjectLOWER BOUNDS
dc.subjectORACLE COMPLEXITY
dc.subjectPERCEPTRON
dc.subjectNOISE
dc.subjectMODEL
dc.subject.ods03 Good Health and Well-being
dc.subject.odspa03 Salud y bienestar
dc.titleStatistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
dc.typeartículo
dc.volumen46
sipa.codpersvinculados1041986
sipa.indexWOS
sipa.trazabilidadCarga SIPA;09-01-2024
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
2024-05-16. Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.pdf
Size:
2.72 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas