The DOI matches its Crossref record; 72 of the 72 references it cites were found in a registry or an index.
Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Open accessAbstract
We survey incremental methods for minimizing a sum $\sum_{i=1}^mf_i(x)$ consisting of a large number of convex component functions $f_i$. Our methods consist of iterations applied to single components, and have proved very effective in practice. We introduce a unified algorithmic framework for a variety of such methods, some involving gradient and subgradient iterations, which are known, and some involving combinations of subgradient and proximal methods, which are new and offer greater flexibility in exploiting the special structure of $f_i$. We provide an analysis of the convergence and rate of convergence properties of these methods, including the advantages offered by randomization in the selection of components. We also survey applications in inference/machine learning, signal processing, and large-scale and distributed optimization.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
(2010) · Cited by 8,261
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Self-citationAn iterative thresholding algorithm for linear inverse problems with a sparsity constraint.
Daubechies, I., Defrise, M., & De Mol, C. (2004) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20042 · Cited by 4,958
WIDROW, B., & HOFF, M. E. (1960) · doi:10.21236/ad0241531 · Cited by 4,009
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719
Monotone Operators and the Proximal Point Algorithm
Rockafellar, R. T. (1976) · SIAM Journal on Control and Optimization · doi:10.1137/0314056 · Cited by 3,559
Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,524
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5086 · Cited by 3,515
Some methods of speeding up the convergence of iteration methods
Polyak, B. T. (1964) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(64)90137-5 · Cited by 3,069
Eckstein, J., & Bertsekas, D. P. (1992) · Mathematical Programming · doi:10.1007/bf01581204 · Cited by 2,791
Self-citationIntroductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Signal Recovery by Proximal Forward-Backward Splitting
Combettes, P. L., & Wajs, V. R. (2005) · Multiscale Modeling & Simulation · doi:10.1137/050626090 · Cited by 2,678
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
A dual algorithm for the solution of nonlinear variational problems via finite element approximation
Gabay, D., & Mercier, B. (1976) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(76)90003-1 · Cited by 2,514
Smooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
Convex Analysis and Optimization
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. (2003) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2,148
Self-citationA New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration
Bioucas-Dias, J. M., & Figueiredo, M. A. T. (2007) · IEEE Transactions on Image Processing · doi:10.1109/tip.2007.909319 · Cited by 2,064
Splitting Algorithms for the Sum of Two Nonlinear Operators
Lions, P. L., & Mercier, B. (1979) · SIAM Journal on Numerical Analysis · doi:10.1137/0716071 · Cited by 1,972
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Self-citationRobust Stochastic Approximation Approach to Stochastic Programming
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070704277 · Cited by 1,945
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
Analysis of recursive stochastic algorithms
Ljung, L. (1977) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1977.1101561 · Cited by 1,467
Neuro-Dynamic Programming: NDP
Bertsekas, D. P. (2001) · Encyclopedia of Optimization · doi:10.1007/0-306-48332-7_333 · Cited by 1,466
Self-citationStochastic Approximation Methods for Constrained and Unconstrained Systems
Kushner, H. J., & Clark, D. S. (1978) · Applied Mathematical Sciences · doi:10.1007/978-1-4684-9352-8 · Cited by 1,459
Facility location : applications and theory
Drezner, Z., & Hamacher, H. W. (2001) · Springer eBooks · Cited by 1,281
An EM algorithm for wavelet-based image restoration
Figueiredo, M. A. T., & Nowak, R. D. (2003) · IEEE Transactions on Image Processing · doi:10.1109/tip.2003.814255 · Cited by 1,219
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273598 · Cited by 973
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901
A method for unconstrained convex minimization problem with the rate of convergence o(1/k^2)
Nesterov, Y. E. (1983) · Medical Entomology and Zoology · Cited by 865
The method of projections for finding the common point of convex sets
Gubin, L. G., Polyak, B. T., & Raik, E. V. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90113-9 · Cited by 828
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814
Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems
(1983) · Studies in Mathematics and Its Applications · doi:10.1016/s0168-2024(08)x7003-1 · Cited by 760
Chambolle, A., De Vore, R. A., Lee, N.-Y., & Lucier, B. J. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.661182 · Cited by 751
Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
Passty, G. B. (1979) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(79)90234-8 · Cited by 609
Incremental Subgradient Methods for Nondifferentiable Optimization
Nedic, A., & Bertsekas, D. P. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499362111 · Cited by 589
Self-citation(2025) · Portfolio Optimization · doi:10.1017/9781009428095.021 · Cited by 553
Control Techniques for Complex Networks
Meyn, S. (2007) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804410 · Cited by 528
Quantized incremental algorithms for distributed optimization
Rabbat, M. G., & Nowak, R. D. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.843546 · Cited by 408
A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
Johansson, B., Rabi, M., & Johansson, M. (2010) · SIAM Journal on Optimization · doi:10.1137/08073038x · Cited by 336
Gradient-based algorithms with applications to signal-recovery problems
Beck, A., & Teboulle, M. (2009) · Convex Optimization in Signal Processing and Communications · doi:10.1017/cbo9780511804458.003 · Cited by 333
A New Class of Incremental Gradient Methods for Least Squares Problems
Bertsekas, D. P. (1997) · SIAM Journal on Optimization · doi:10.1137/s1052623495287022 · Cited by 312
Self-citationA Convergent Incremental Gradient Method with a Constant Step Size
Blatt, D., Hero, A. O., & Gauchman, H. (2007) · SIAM Journal on Optimization · doi:10.1137/040615961 · Cited by 306
Incremental proximal methods for large scale convex optimization
Bertsekas, D. P. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0472-0 · Cited by 303
Self-citationOptimization of Stochastic Models
Pflug, G. C. (1996) · Kluwer international series in engineering and computer science · doi:10.1007/978-1-4613-1449-3 · Cited by 259
Fast alternating linearization methods for minimizing the sum of two convex functions
Goldfarb, D., Ma, S., & Scheinberg, K. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0530-2 · Cited by 246
Incremental Stochastic Subgradient Algorithms for Convex Optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · SIAM Journal on Optimization · doi:10.1137/080726380 · Cited by 239
Distributed asynchronous computation of fixed points
Bertsekas, D. P. (1983) · Mathematical Programming · doi:10.1007/bf02591967 · Cited by 230
Self-citationOptimization of Stochastic Models: The Interface Between Simulation and Optimization
Orman, A. J., & Pflug, G. C. (1998) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2600016 · Cited by 214
Elad, M., Matalon, B., & Zibulevsky, M. (2007) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2007.02.002 · Cited by 201
Sparse reconstruction by separable approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2008) · 2008 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2008.4518374 · Cited by 189
Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
Kiwiel, K. C. (2004) · SIAM Journal on Optimization · doi:10.1137/s1052623400376366 · Cited by 182
An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
Tseng, P. (1998) · SIAM Journal on Optimization · doi:10.1137/s1052623495294797 · Cited by 160
Applications of the method of partial inverses to convex programming: Decomposition
Spingarn, J. E. (1985) · Mathematical Programming · doi:10.1007/bf01586091 · Cited by 151
Incremental Least Squares Methods and the Extended Kalman Filter
Bertsekas, D. P. (1996) · SIAM Journal on Optimization · doi:10.1137/s1052623494268522 · Cited by 150
Self-citationStochastic Programming Methods
Ermoliev, Y. M. (1976) · IIASA PURE (International Institute of Applied Systems Analysis) · Cited by 147
Distributed Asynchronous Incremental Subgradient Methods
Nedić, A., Bertsekas, D. P., & Borkar, V. S. (2001) · Studies in computational mathematics · doi:10.1016/s1570-579x(01)80023-9 · Cited by 146
Self-citationA Collaborative Training Algorithm for Distributed Learning
Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2012992 · Cited by 145
On the Convergence of the LMS Algorithm with Adaptive Learning Rate for Linear Feedforward Networks
Luo, Z.-Q. T. (1991) · Neural Computation · doi:10.1162/neco.1991.3.2.226 · Cited by 140
Fast Multiple-Splitting Algorithms for Convex Optimization
Goldfarb, D., & Ma, S. (2012) · SIAM Journal on Optimization · doi:10.1137/090780705 · Cited by 96
Error Stability Properties of Generalized Gradient-Type Algorithms
Solodov, M. V., & Завриев, С. К. (1998) · Journal of Optimization Theory and Applications · doi:10.1023/a:1022680114518 · Cited by 88
The effect of deterministic noise in subgradient methods
Nedić, A., & Bertsekas, D. P. (2009) · Mathematical Programming · doi:10.1007/s10107-008-0262-5 · Cited by 68
Self-citationLu, Z., Monteiro, R. D. C., & Yuan, M. (2010) · Mathematical Programming · doi:10.1007/s10107-010-0350-1 · Cited by 58
Convergent on-line algorithms for supervised learning in neural networks
Grippo, L. (2000) · IEEE Transactions on Neural Networks · doi:10.1109/72.883426 · Cited by 45
Davidon, W. C. (1976) · Journal of Optimization Theory and Applications · doi:10.1007/bf00935703 · Cited by 42
Gradient convergence in gradient methods
Bertsekas, D. P. (1997) · Cited by 40
Self-citationThe Incremental Gauss-Newton Algorithm with Adaptive Stepsize Rule
Moriyama, H., Yamashita, N., & Fukushima, M. (2003) · Computational Optimization and Applications · doi:10.1023/a:1025703629626 · Cited by 30
A fast iterative thresholding algorithm for wavelet-regularized deconvolution
Vonesch, C., & Unser, M. A. (2007) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.733532 · Cited by 28
Cited by
Practical Recommendations for Gradient-Based Training of Deep Architectures
Bengio, Y. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-35289-8_26 · Cited by 2,259
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
Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
Chen, J., & Sayed, A. H. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2198470 · Cited by 680
A Proximal Stochastic Gradient Method with Progressive Variance Reduction
Xiao, L., & Zhang, T. (2014) · SIAM Journal on Optimization · doi:10.1137/140961791 · Cited by 592
Further improvements to the ptychographical iterative engine
Maiden, A., Johnson, D., & Li, P. (2017) · Optica · doi:10.1364/optica.4.000736 · Cited by 452
Metadata
- Authors
- Bertsekas, D. P.
- Venue
- Optimization for Machine Learning
- Publisher
- The MIT Press
- Published
- 2011-09-30
- Pages
- 85-120
- OpenAlex
- W2134130436
- Cited by
- 381
- References
- 72
- FWCI
- 58.40
- Type
- book chapter
- Language
- en
- Open access
- green
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.