The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Stochastic Model-Based Minimization of Weakly Convex Functions
Open accessAbstract
We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate $O(k^{-1/4})$. As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss--Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set.
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
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921
Optimization of conditional value-at-risk
Rockafellar, R. T., & Uryasev, S. (2000) · The Journal of Risk · doi:10.21314/jor.2000.038 · Cited by 6,725
Robust 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
Proximité et dualité dans un espace hilbertien
Moreau, J. J. (1965) · Bulletin de la Société mathématique de France · doi:10.24033/bsmf.1625 · Cited by 1,462
Gradient methods for minimizing composite functions
Nesterov, Y. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0629-5 · Cited by 1,298
Total variation blind deconvolution
Chan, T. F., & Wong, C.-K. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.661187 · Cited by 1,201
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
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
Tosic, I., & Frossard, P. (2011) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.939537 · Cited by 897
Rank-Sparsity Incoherence for Matrix Decomposition
Chandrasekaran, V., Sanghavi, S., Parrilo, P. A., & Willsky, A. S. (2011) · SIAM Journal on Optimization · doi:10.1137/090761793 · Cited by 686
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Chen, Y., & Candès, E. J. (2017) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21638 · Cited by 477
Understanding Blind Deconvolution Algorithms
Levin, A., Weiss, Y., Durand, F., & Freeman, W. T. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.148 · Cited by 425
First-order methods of smooth convex optimization with inexact oracle
Devolder, O., Glineur, F., & Nesterov, Y. (2014) · Mathematical Programming · doi:10.1007/s10107-013-0677-5 · Cited by 422
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
AN OLD‐NEW CONCEPT OF CONVEX RISK MEASURES: THE OPTIMIZED CERTAINTY EQUIVALENT
Ben‐Tal, A., & Teboulle, M. (2007) · Mathematical Finance · doi:10.1111/j.1467-9965.2007.00311.x · Cited by 353
Prox-regular functions in variational analysis
Poliquin, R. A., & Rockafellar, R. T. (1996) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-96-01544-9 · Cited by 333
Angular synchronization by eigenvectors and semidefinite programming
Singer, A. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.02.001 · Cited by 329
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
Drusvyatskiy, D., & Lewis, A. S. (2018) · Mathematics of Operations Research · doi:10.1287/moor.2017.0889 · Cited by 267
Self-citationUniversal gradient methods for convex optimization problems
Nesterov, Y. (2015) · Mathematical Programming · doi:10.1007/s10107-014-0790-0 · Cited by 266
Self-calibration and biconvex compressive sensing
Ling, S., & Strohmer, T. (2015) · Inverse Problems · doi:10.1088/0266-5611/31/11/115002 · Cited by 229
Phase Retrieval: Stability and Recovery GuaranteesPreprint
(n.d.) · Cited by 207
Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
Chen, Y., Chi, Y., & Goldsmith, A. J. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2429594 · Cited by 205
A Geometric Analysis of Phase Retrieval
Sun, J., Qu, Q., & Wright, J. (2018) · Foundations of Computational Mathematics · doi:10.1007/s10208-017-9365-9 · Cited by 189
Asymptotic and finite-sample properties of estimators based on stochastic gradients
Toulis, P., & Airoldi, E. M. (2017) · The Annals of Statistics · doi:10.1214/16-aos1506 · Cited by 187
Efficiency of minimizing compositions of convex functions and smooth maps
Drusvyatskiy, D., & Paquette, C. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1311-3 · Cited by 179
Self-citationWang, M., Fang, E. X., & Liu, H. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1017-3 · Cited by 178
Expected Utility, Penalty Functions, and Duality in Stochastic Nonlinear Programming
Ben-Tal, A., & Teboulle, M. (1986) · Management Science · doi:10.1287/mnsc.32.11.1445 · Cited by 170
A proximal method for composite minimization
Lewis, A. S., & Wright, S. J. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0943-9 · Cited by 167
Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient Recovery
Abbe, E. A., Bandeira, A. S., Bracher, A., & Singer, A. (2014) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2014.2368716 · Cited by 137
Stochastic Methods for Composite and Weakly Convex Optimization Problems
Duchi, J. C., & Ruan, F. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1135086 · Cited by 127
Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization
Xu, Y., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/140983938 · Cited by 125
Descent methods for composite nondifferentiable optimization problems
Burke, J. V. (1985) · Mathematical Programming · doi:10.1007/bf01584377 · Cited by 119
Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
Duchi, J. C., & Ruan, F. (2018) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iay015 · Cited by 117
Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functionsPreprint
Davis, D., & Drusvyatskiy, D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.02988 · Cited by 106
Self-citationThe nonsmooth landscape of phase retrieval
Davis, D., Drusvyatskiy, D., & Paquette, C. (2019) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/drz031 · Cited by 80
Self-citationThe proximal point method revisitedPreprint
Drusvyatskiy, D. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1712.06038 · Cited by 63
Self-citationOn Proximal Subgradient Splitting Method for Minimizing the sum of two Nonsmooth Convex Functions
Bello-Cruz, Y. (2016) · Set-Valued and Variational Analysis · doi:10.1007/s11228-016-0376-5 · Cited by 34
Stochastic Methods for Composite Optimization ProblemsPreprint
Duchi, J. C., & Ruan, F. (2017) · arXiv (Cornell University) · Cited by 21
Cited by
Square Attack: A Query-Efficient Black-Box Adversarial Attack via Random Search
Andriushchenko, M., Croce, F., Flammarion, N., & Hein, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-58592-1_29 · Cited by 800
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
Data-Driven Aerospace Engineering: Reframing the Industry with Machine Learning
Brunton, S. L., Nathan Kutz, J., Manohar, K., Aravkin, A. Y., Morgansen, K., Klemisch, J., Goebel, N., Buttrick, J., Poskin, J., Blom-Schieber, A. W., et al. (2021) · AIAA Journal · doi:10.2514/1.j060131 · Cited by 270
Metadata
- Authors
- Davis, D., & Drusvyatskiy, D.
- Venue
- SIAM Journal on Optimization
- Published
- 2019-01
- Volume
- 29
- Issue
- 1
- Pages
- 207-239
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2790417304
- Cited by
- 258
- References
- 40
- FWCI
- 15.43
- Type
- journal article
- 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.