The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
Online Learning and Online Convex Optimization
Abstract
Online learning is a well established learning paradigm which has both theoretical and practical appeals. The goal of online learning is to make a sequence of accurate predictions given knowledge of the correct answer to previous prediction tasks and possibly additional available information. Online learning has been studied in several research fields including game theory, information theory, and machine learning. It also became of great interest to practitioners due the recent emergence of large scale applications such as online advertisement placement and online web ranking. Online Learning and Online Convex Optimization is a modern overview of online learning. Its aim is to provide the reader with a sense of some of the interesting ideas and in particular to underscore the centrality of convexity in deriving efficient online learning algorithms. It connects and relates new results on online convex optimization to classic results on online classification, thus providing a fresh modern perspective on some classic algorithms. It is not intended to be comprehensive but rather to give a high-level, rigorous, yet easy to follow survey of the topic.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
Cristianini, N., & Shawe-Taylor, J. (2000) · doi:10.1017/cbo9780511801389 · Cited by 13,855
The perceptron: A probabilistic model for information storage and organization in the brain.
Rosenblatt, F. (1958) · Psychological Review · doi:10.1037/h0042519 · Cited by 12,280
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,718
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162
(2002) · doi:10.1137/s0097539701398375 · Cited by 2,275
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
The Weighted Majority Algorithm
Littlestone, N., & Warmuth, M. K. (1994) · Information and Computation · doi:10.1006/inco.1994.1009 · Cited by 1,975
Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control
Spall, J. C. (2003) · Wiley eBooks · doi:10.1002/0471722138 · Cited by 1,890
(2003) · Cited by 1,733
Convex Analysis in General Vector Spaces
Zalinescu, C. (2002) · WORLD SCIENTIFIC eBooks · doi:10.1142/5021 · Cited by 1,518
Large margin classification using the perceptron algorithm
Freund, Y., & Schapire, R. E. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279985 · Cited by 1,071
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
Convex Analysis and Nonlinear Optimization
Borwein, J. M., & Lewis, A. S. (2006) · CMS books in mathematics · doi:10.1007/978-0-387-31256-9 · Cited by 780
Efficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
Vovk, V. G. (1990) · Conference on Learning Theory · doi:10.5555/92571.92672 · Cited by 551
The Relaxation Method for Linear Inequalities
Agmon, S. (1954) · Canadian Journal of Mathematics · doi:10.4153/cjm-1954-037-2 · Cited by 549
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 quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
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
Online Learning: Theory, Algorithms, and Applications
Shalev‐Shwartz, S. (2007) · Cited by 418
Self-citationRelative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions
Azoury, K. S., & Warmuth, M. K. (2001) · Machine Learning · doi:10.1023/a:1010896012157 · Cited by 298
Additive versus exponentiated gradient updates for linear prediction
Kivinen, J., & Warmuth, M. K. (1995) · Proceedings of the twenty-seventh annual ACM symposium on Theory of computing - STOC '95 · doi:10.1145/225058.225121 · Cited by 223
Competing in the dark: An efficient algorithm for bandit linear optimization
Abernethy, J., Hazan, E., & Rakhlin, A. (2008) · Cited by 193
Mistake bounds and logarithmic linear-threshold learning algorithms
Littlestone, N. (1990) · Cited by 183
A primal-dual perspective of online learning algorithms
Shalev-Shwartz, S., & Singer, Y. (2007) · Machine Learning · doi:10.1007/s10994-007-5014-x · Cited by 168
Self-citationOn-Line Algorithms in Machine Learning
Blum, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0029575 · Cited by 162
The Price of Bandit Information for Online Optimization
Dani, V., Kakade, S. M., & Hayes, T. P. (2007) · ScholarlyCommons (University of Pennsylvania) · Cited by 161
Regularization Techniques for Learning with MatricesPreprint
Kakade, S. M., Shalev‐Shwartz, S., & Tewari, A. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.0610 · Cited by 157
Self-citationThe Robustness of the p-Norm Algorithms
Gentile, C. (2003) · Machine Learning · doi:10.1023/a:1026319107706 · Cited by 145
Relative Loss Bounds for Multidimensional Regression Problems
Kivinen, J., & Warmuth, M. K. (2001) · Machine Learning · doi:10.1023/a:1017938623079 · Cited by 135
From on-line to batch learning
Littlestone, N. (1989) · Conference on Learning Theory · doi:10.5555/93335.93365 · Cited by 121
General Convergence Results for Linear Discriminant Updates
Grove, A. J., Littlestone, N., & Schuurmans, D. (2001) · Machine Learning · doi:10.1023/a:1010844028087 · Cited by 118
Ben-David, S., Pál, D., & Shalev‐Shwartz, S. (2009) · Conference on Learning Theory · Cited by 116
Self-citationBEHAVIOR OF SEQUENTIAL PREDICTORS OF BINARY SEQUENCES.
Cover, T. M. (1966) · Cited by 108
Auer, P. L., & Warmuth, M. K. (1998) · Machine Learning · doi:10.1023/a:1007472513967 · Cited by 105
Regret bounds for prediction problems
Gordon, G. J. (1999) · doi:10.1145/307400.307410 · Cited by 105
Optimal Strategies and Minimax Lower Bounds for Online Convex Games
Abernethy, J., Bartlett, P. L., Rakhlin, A., & Tewari, A. (2008) · Cited by 99
Online Learning: Random Averages, Combinatorial Parameters, and Learnability
Rakhlin, A., Sridharan, K., & Tewari, A. (2010) · ScholarlyCommons (University of Pennsylvania) · Cited by 75
Helmbold, D. P., & Warmuth, M. K. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1044 · Cited by 74
Improved Risk Tail Bounds for On-Line Algorithms
Cesa‐Bianchi, N., & Gentile, C. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.911292 · Cited by 51
The robustness of the p -norm algorithms
Gentile, C., & Littlestone, N. (1999) · Conference on Learning Theory · doi:10.1145/307400.307405 · Cited by 46
Data Dependent Concentration Bounds for Sequential Prediction Algorithms
Zhang, T. (2005) · Lecture notes in computer science · doi:10.1007/11503415_12 · Cited by 39
Optimal Stragies and Minimax Lower Bounds for Online Convex Games.
Abernethy, J., Bartlett, P. L., Rakhlin, A., & Tewari, A. (2008) · Conference on Learning Theory · Cited by 24
Cited by
(2015) · Cited by 2,857
A Continual Learning Survey: Defying Forgetting in Classification Tasks
Delange, M., Aljundi, R., Masana, M., Parisot, S., Jia, X., Leonardis, A., Slabaugh, G., & Tuytelaars, T. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3057446 · Cited by 1,647
A continual learning survey: Defying forgetting in classification tasks
De Lange, M., Aljundi, R., Masana, M., Parisot, S., Jia, X., Leonardis, A., Slabaugh, G., & Tuytelaars, T. (2019) · arXiv · doi:10.48550/arxiv.1909.08383 · Cited by 1,647
Big data deep learning: Challenges and perspectives
Chen, X.-W., & Lin, X. (2014) · IEEE Access · doi:10.1109/access.2014.2325029 · Cited by 1,255
A survey on deep learning for big data
Zhang, Q., Yang, L. T., Chen, Z., & Li, P. (2018) · Information Fusion · doi:10.1016/j.inffus.2017.10.006 · Cited by 1,226
Metadata
- Authors
- Shalev-Shwartz, S.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2011
- OpenAlex
- W2077723394
- Cited by
- 1,095
- References
- 47
- FWCI
- 10.57
- Type
- book
- 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.