2020/01/21 by Darina Dvinskikh, Dvinskikh, Darina · 1 citation
Computer Science · Engineering · Mathematics · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2001.07697
openalex publication_date 2020/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the machine learning and optimization community, there are two main\napproaches for the convex risk minimization problem, namely, the Stochastic\nApproximation (SA) and the Sample Average Approximation (SAA). In terms of\noracle complexity (required number of stochastic gradient evaluations), both\napproaches are considered equivalent on average (up to a logarithmic factor).\nThe total complexity depends on the specific problem, however, starting from\nwork citenemirovski2009robust it was generally accepted that the SA is\nbetter than the SAA. % Nevertheless, in case of large-scale problems SA may run\nout of memory as storing all data on one machine and organizing online access\nto it can be impossible without communications with other machines. SAA in\ncontradistinction to SA allows parallel/distributed calculations. We show that\nfor the Wasserstein barycenter problem this superiority can be inverted. We\nprovide a detailed comparison by stating the complexity bounds for the SA and\nthe SAA implementations calculating barycenters defined with respect to optimal\ntransport distances and entropy-regularized optimal transport distances. As a\nbyproduct, we also construct confidence intervals for the barycenter defined\nwith respect to entropy-regularized optimal transport distances in the\n\ℓ2-norm. The preliminary results are derived for a general convex\noptimization problem given by the expectation in order to have other\napplications besides the Wasserstein barycenter problem.\n