The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Robust Stochastic Approximation Approach to Stochastic Programming
Abstract
In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the stochastic approximation (SA) and the sample average approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say, linear) structure of the considered problem, while the SA approach is a crude subgradient method, which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems and present (in our opinion highly encouraging) results of numerical experiments.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
McKay, M. D., Beckman, R. J., & Conover, W. J. (2000) · Technometrics · doi:10.2307/1271432 · Cited by 7,415
Bregman, L. M. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90040-7 · Cited by 2,618
The Sample Average Approximation Method for Stochastic Discrete Optimization
Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623499363220 · Cited by 1,983
Self-citationIntroduction to Stochastic Search and Optimization: Estimation, Simulation, and Control
Spall, J. C. (2003) · Wiley eBooks · doi:10.1002/0471722138 · Cited by 1,890
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
Acceleration of Stochastic Approximation by Averaging
Polyak, B. T., & Juditsky, A. B. (1992) · SIAM Journal on Control and Optimization · doi:10.1137/0330046 · Cited by 1,827 · cited 1×
“An important improvement of the SA method was developed by Polyak [18] and Polyak and Juditsky [19], where longer stepsizes were suggested with consequent averaging of the obtained iterates.”
MethodSelf-citationProblem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,329
The Existence of Probability Measures with Given Marginals
Strassen, V. (1965) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177700153 · Cited by 1,301
Weighted sums of certain dependent random variables
Azuma, K. (1967) · Tohoku Mathematical Journal · doi:10.2748/tmj/1178243286 · Cited by 1,084
Cited by
(2010) · Cited by 8,261
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., & Nocedal, J. (2018) · SIAM Review · doi:10.1137/16m1080173 · Cited by 3,128
(2015) · Cited by 2,857
Federated Optimization: Distributed Machine Learning for On-Device Intelligence
Konečný, J., McMahan, H. B., Ramage, D., & Richtárik, P. (2016) · arXiv · doi:10.48550/arxiv.1610.02527 · Cited by 1,563
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Niu, F., Recht, B., Re, C., & Wright, S. J. (2011) · arXiv · doi:10.48550/arxiv.1106.5730 · Cited by 1,211
Computational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044010 · Cited by 1,046
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
Ghadimi, S., & Lan, G. (2013) · SIAM Journal on Optimization · doi:10.1137/120880811 · Cited by 1,034
Self-citationMinimizing finite sums with the stochastic average gradient
Schmidt, M., Le Roux, N., & Bach, F. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1030-6 · Cited by 922
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
Karimi, H., Nutini, J., & Schmidt, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46128-1_50 · Cited by 824
Random Gradient-Free Minimization of Convex Functions
Nesterov, Y., & Spokoiny, V. (2017) · Foundations of Computational Mathematics · doi:10.1007/s10208-015-9296-2 · Cited by 822
A Survey of Optimization Methods From a Machine Learning Perspective
Sun, S., Cao, Z., Zhu, H., & Zhao, J. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2950779 · Cited by 789
From Predictive to Prescriptive Analytics
Bertsimas, D., & Kallus, N. (2020) · Management Science · doi:10.1287/mnsc.2018.3253 · Cited by 784
Smart “Predict, then Optimize”
Elmachtoub, A. N., & Grigas, P. (2022) · Management Science · doi:10.1287/mnsc.2020.3922 · Cited by 773
Personalized Cross-Silo Federated Learning on Non-IID Data
Huang, Y., Chu, L., Zhou, Z., Wang, L., Liu, J., Pei, J., & Zhang, Y. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i9.16960 · Cited by 723
Demystifying Parallel and Distributed Deep Learning: An In-depth Concurrency Analysis
Ben-Nun, T., & Hoefler, T. (2020) · ACM Computing Surveys · doi:10.1145/3320060 · Cited by 577
Optimal Distributed Online Prediction using Mini-Batches
Dekel, O., Gilad-Bachrach, R., Shamir, O., & Xiao, L. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.1367 · Cited by 512
Frameworks and Results in Distributionally Robust Optimization
Rahimian, H., & Mehrotra, S. (2022) · Open Journal of Mathematical Optimization · doi:10.5802/ojmo.15 · Cited by 506
Sayed, A. H., Tu, S.-Y., Chen, J., Zhao, X., & Towfic, Z. J. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2012.2231991 · Cited by 494
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Rakhlin, A., Shamir, O., & Sridharan, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.5647 · Cited by 492
Accelerated gradient methods for nonconvex nonlinear and stochastic programming
Ghadimi, S., & Lan, G. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0871-8 · Cited by 487
Self-citationA Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
Roux, N. L., Schmidt, M., & Bach, F. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.6258 · Cited by 481
A Stochastic Quasi-Newton Method for Large-Scale Optimization
Byrd, R. H., Hansen, S. L., Nocedal, J., & Singer, Y. (2016) · SIAM Journal on Optimization · doi:10.1137/140954362 · Cited by 459
Paradigm shift in urban energy systems through distributed generation: Methods and models
Manfren, M., Caputo, P., & Costa, G. (2011) · Applied Energy · doi:10.1016/j.apenergy.2010.10.018 · Cited by 437
Stochastic Gradient Hamiltonian Monte Carlo
Chen, T., Fox, E. B., & Guestrin, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4102 · Cited by 434
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Needell, D., Srebro, N., & Ward, R. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0864-7 · Cited by 432
An optimal method for stochastic composite optimization
Lan, G. (2012) · Mathematical Programming · doi:10.1007/s10107-010-0434-y · Cited by 427
Self-citationLian, X., Zhang, C., Zhang, H., Hsieh, C., Zhang, W., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09056 · Cited by 395
Decentralized Federated Averaging
Sun, T., Li, D., & Wang, B. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3196503 · Cited by 388
Minimax Optimal Procedures for Locally Private Estimation
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2018) · Journal of the American Statistical Association · doi:10.1080/01621459.2017.1389735 · Cited by 386
Mitigating Sybils in Federated Learning Poisoning
Fung, C., Yoon, C. J. M., & Beschastnikh, I. (2018) · arXiv · doi:10.48550/arxiv.1808.04866 · Cited by 385
Statistical guarantees for the EM algorithm: From population to sample-based analysis
Balakrishnan, S., Wainwright, M. J., & Yu, B. (2017) · The Annals of Statistics · doi:10.1214/16-aos1435 · Cited by 384
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
Lessard, L., Recht, B., & Packard, A. (2016) · SIAM Journal on Optimization · doi:10.1137/15m1009597 · Cited by 383
Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Bertsekas, D. P. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0006 · Cited by 381
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
Ghadimi, S., Lan, G., & Zhang, H. (2016) · Mathematical Programming · doi:10.1007/s10107-014-0846-1 · Cited by 376
Self-citationLi, L., Xu, W., Chen, T., Giannakis, G. B., & Ling, Q. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33011544 · Cited by 373
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Duchi, J. C., Jordan, M. I., Wainwright, M. J., & Wibisono, A. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2409256 · Cited by 370
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Sagawa, S., Koh, P. W., Hashimoto, T., & Liang, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08731 · Cited by 331
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
Lian, X., Huang, Y., Li, Y., & Liu, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.08272 · Cited by 324
AUC Maximization in the Era of Big Data and AI: A Survey
Yang, T., & Ying, Y. (2023) · ACM Computing Surveys · doi:10.1145/3554729 · Cited by 323
Train faster, generalize better: Stability of stochastic gradient descent
Hardt, M., Recht, B., & Singer, Y. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.01240 · Cited by 323
Parallel stochastic gradient algorithms for large-scale matrix completion
Recht, B., & Ré, C. (2013) · Mathematical Programming Computation · doi:10.1007/s12532-013-0053-8 · Cited by 300
Online Nonnegative Matrix Factorization With Robust Stochastic Approximation
Guan, N., Tao, D., Luo, Z., & Yuan, B. (2012) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2012.2197827 · Cited by 287
Communication-efficient algorithms for statistical optimization
Zhang, Y., Duchi, J. C., & Wainwright, M. J. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426691 · Cited by 283
Monte Carlo sampling-based methods for stochastic optimization
Homem-de-Mello, T., & Bayraksan, G. (2014) · Surveys in Operations Research and Management Science · doi:10.1016/j.sorms.2014.05.001 · Cited by 283
Recent Advances in Stochastic Gradient Descent in Deep Learning
Tian, Y., Zhang, Y., & Zhang, H. (2023) · Mathematics · doi:10.3390/math11030682 · Cited by 277
Structure and dynamics of information pathways in online media
Gomez Rodriguez, M., Leskovec, J., & Schölkopf, B. (2013) · Proceedings of the sixth ACM international conference on Web search and data mining · doi:10.1145/2433396.2433402 · Cited by 271
Ghadimi, S., & Lan, G. (2012) · SIAM Journal on Optimization · doi:10.1137/110848864 · Cited by 269
Self-citationBayesian inference with optimal maps
El Moselhy, T. A., & Marzouk, Y. M. (2012) · Journal of Computational Physics · doi:10.1016/j.jcp.2012.07.022 · Cited by 267
Distributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Position-Transitional Particle Swarm Optimization-Incorporated Latent Factor Analysis
Luo, X., Yuan, Y., Chen, S., Zeng, N., & Wang, Z. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3033324 · Cited by 264
Stochastic Model-Based Minimization of Weakly Convex Functions
Davis, D., & Drusvyatskiy, D. (2019) · SIAM Journal on Optimization · doi:10.1137/18m1178244 · Cited by 258
Linear convergence of first order methods for non-strongly convex optimization
Necoara, I., Nesterov, Y., & Glineur, F. (2019) · Mathematical Programming · doi:10.1007/s10107-018-1232-1 · Cited by 258
Qsparse-local-SGD: Distributed SGD with quantization, sparsification, and local computations
Basu, D., Data, D., Karakus, C., & Diggavi, S. N. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.2985917 · Cited by 256
“This is a standard assumption in [SSS07, NJLS09, RRWN11, HK14, RSS12, SCJ18, Sti19, YYZ18, KSJ19, AHJ + 18].”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
Konecny, J., Liu, J., Richtarik, P., & Takac, M. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2505682 · Cited by 254
Hybrid Deterministic-Stochastic Methods for Data Fitting
Friedlander, M. P., & Schmidt, M. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/110830629 · Cited by 254
Communication-efficient algorithms for statistical optimization
(2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2567769 · Cited by 195
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Cotter, A., Shamir, O., Srebro, N., & Sridharan, K. (2011) · arXiv · doi:10.48550/arxiv.1106.4574 · Cited by 173
On Analog Gradient Descent Learning Over Multiple Access Fading Channels
Sery, T., & Cohen, K. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2989580 · Cited by 172
Harrow, A. W., & Napp, J. C. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.140502 · Cited by 121
Distributed stochastic optimization and learning
Shamir, O., & Srebro, N. (2014) · 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2014.7028543 · Cited by 120
Information-theoretic analysis of stability and bias of learning algorithms
Raginsky, M., Rakhlin, A., Tsao, M., Wu, Y., & Xu, A. (2016) · 2016 IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2016.7606789 · Cited by 70
Jia, T., Wu, Y., Hou, C., & Li, Y. (2021) · 2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE) · doi:10.1109/issre52982.2021.00021 · Cited by 55
Large-scale methods for distributionally robust optimization
Levy, D., Carmon, Y., Duchi, J. C., & Sidford, A. (2020) · arXiv · doi:10.48550/arxiv.2010.05893 · Cited by 52
“…paper, we consider the setting in which (cid:96) is a Lipschitz convex loss, a prototype case for stochastic optimization and machine learning [75, 49], and we propose methods for solving the problem (1) with ∇ complexity independent of sample size N and dimension d , and with optimal (linear)…”
rTop-k: A Statistical Estimation Approach to Distributed SGD
Barnes, L. P., Inan, H. A., Isik, B., & Ozgur, A. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.3042094 · Cited by 44
Bandit Structured Prediction for Learning from Partial Feedback in Statistical Machine Translation
Sokolov, A., Riezler, S., & Urvoy, T. (2016) · arXiv · doi:10.48550/arxiv.1601.04468 · Cited by 14
Metadata
- Authors
- Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A.
- Venue
- SIAM Journal on Optimization
- Published
- 2009-01
- Volume
- 19
- Issue
- 4
- Pages
- 1574-1609
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1992208280
- Cited by
- 1,945
- References
- 26
- FWCI
- 53.85
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.