The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Open accessAbstract
We consider derivative-free algorithms for stochastic and nonstochastic convex optimization problems that use only function values rather than gradients. Focusing on nonasymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for d-dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most √d in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and nonsmooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple (m ≥ 2) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.
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
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2005) · doi:10.1002/047174882x · Cited by 13,791
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Self-citationSmooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
Asymptotically efficient adaptive allocation rules
Lai, T. L., & Robbins, H. (1985) · Advances in Applied Mathematics · doi:10.1016/0196-8858(85)90002-8 · Cited by 2,406
Convex Analysis and Minimization Algorithms I
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02796-7 · Cited by 2,378
Some aspects of the sequential design of experiments
Robbins, H. (1952) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1952-09620-8 · Cited by 2,184
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
Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control
Spall, J. C. (2003) · Wiley eBooks · doi:10.1002/0471722138 · Cited by 1,890
Introduction to Derivative-Free Optimization
Conn, A. R., Scheinberg, K., & Vicente, L. N. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718768 · Cited by 1,840
Stochastic Approximation and Recursive Algorithms and Applications
(2003) · Stochastic Modelling and Applied Probability · doi:10.1007/b97441 · Cited by 1,838
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000001 · Cited by 1,820
Self-citation(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
(2003) · Cited by 1,733
The Concentration of Measure Phenomenon
Ledoux, M. (2005) · Mathematical Surveys and Monographs · doi:10.1090/surv/089 · Cited by 1,700
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
Problem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,329
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S., & Cesa-Bianchi, N. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000024 · Cited by 1,295
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A., & Teboulle, M. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00231-6 · Cited by 1,060
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
INTRODUCTION TO STOCHASTIC SEARCH AND OPTIMIZATION: ESTIMATION, SIMULATION, AND CONTROL
Nowak, W. (2012) · Medical Entomology and Zoology · Cited by 1,033
Exponentiated Gradient versus Gradient Descent for Linear Predictors
Kivinen, J., & Warmuth, M. K. (1997) · Information and Computation · doi:10.1006/inco.1996.2612 · Cited by 864
Problem Complexity and Method Efficiency in Optimization
Darzentas, J., Nemirovsky, A., & Yudin, D. B. (1984) · Journal of the Operational Research Society · doi:10.2307/2581380 · Cited by 650
Dual Averaging Method for Regularized Stochastic Learning and Online Optimization
Xiao, L. (2009) · Cited by 574
Information-theoretic determination of minimax rates of convergence
Yang, Y., & Barron, A. (1999) · The Annals of Statistics · doi:10.1214/aos/1017939142 · Cited by 555
Online convex optimization in the bandit setting: gradient descent without a gradient
Flaxman, A. D., Kalai, A. T., & McMahan, H. B. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408007 · Cited by 546
Learning structured prediction models: a large margin approach
Taskar, B., Chatalbashev, V., Koller, D., & Guestrin, C. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102464 · Cited by 444
On the Generalization Ability of On-Line Learning Algorithms
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.833339 · Cited by 426
Minimax policies for adversarial and stochastic bandits
Audibert, J.-Y., Est, U. P., & Bubeck, S. (2009) · HAL · Cited by 346
Yu, B. (1997) · Festschrift for Lucien Le Cam · doi:10.1007/978-1-4612-1880-7_29 · Cited by 309
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.
Agarwal, A., Dekel, O., & Xiao, L. (2010) · Cited by 261
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization
Xiaolin (2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1953017 · Cited by 233
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
Agarwal, A., Bartlett, P. L., Ravikumar, P., & Wainwright, M. J. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2182178 · Cited by 225
Self-citationRandomized smoothing for stochastic optimizationPreprint
Duchi, J. C., & Wainwright, M. J. (2016) · Cited by 188
Self-citationStochastic Convex Optimization with Bandit Feedback
Agarwal, A., Foster, D. P., Hsu, D., Kakade, S. M., & Rakhlin, A. (2013) · SIAM Journal on Optimization · doi:10.1137/110850827 · Cited by 162
The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography
Ben‐Tal, A., Margalit, T., & Nemirovski, A. S. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499354564 · Cited by 157
The Robustness of the p-Norm Algorithms
Gentile, C. (2003) · Machine Learning · doi:10.1023/a:1026319107706 · Cited by 145
On the Fundamental Limits of Adaptive Sensing
Ery Arias-castro, A., Candès, E. J., & Davenport, M. A. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2215837 · Cited by 126
Query Complexity of Derivative-Free OptimizationPreprint
Jamieson, K., Nowak, R. D., & Recht, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.2434 · Cited by 103
Random gradient-free minimization of convex functionsPreprint
Nesterov, Y. E. (2011) · RePEc: Research Papers in Economics · Cited by 89
On the Complexity of Bandit and Derivative-Free Stochastic Convex OptimizationPreprint
Shamir, O. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.2388 · Cited by 86
Cited by
Evolution Strategies as a Scalable Alternative to Reinforcement Learning
Salimans, T., Ho, J., Chen, X., Sidor, S., & Sutskever, I. (2017) · arXiv · doi:10.48550/arxiv.1703.03864 · Cited by 1,027
“Derivative free optimization methods have also been analyzed in the convex setting Duchi et al. [2015], Nesterov [2012].”
MethodSquare 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
HopSkipJumpAttack: A Query-Efficient Decision-Based Attack
Chen, J., Jordan, M. I., & Wainwright, M. J. (2020) · 2020 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40000.2020.00045 · Cited by 718
Self-citationCommunication-efficient edge ai: algorithms and systems
Shi, Y., Yang, K., Jiang, T., Zhang, J., & Letaief, K. B. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3007787 · Cited by 488
Derivative-free optimization methods
Larson, J., Menickelly, M., & Wild, S. M. (2019) · Acta Numerica · doi:10.1017/s0962492919000060 · Cited by 381
Metadata
- Authors
- Duchi, J. C., Jordan, M. I., Wainwright, M. J., & Wibisono, A.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2015-05
- Volume
- 61
- Issue
- 5
- Pages
- 2788-2806
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2171830216
- Cited by
- 370
- References
- 40
- FWCI
- 16.58
- 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.