Adaptive bound optimization for online convex optimization
Open accessAbstract
We introduce a new online convex optimization algorithm that adaptively chooses its regularization function based on the loss functions observed so far. This is in contrast to previous algorithms that use a fixed regularization function such as L2-squared, and modify it only via a single time-dependent parameter. Our algorithm's regret bounds are worst-case optimal, and for certain realistic classes of loss functions they are much better than existing bounds. These bounds are problem-dependent, which means they can exploit the structure of the actual problem instance. Critically, however, our algorithm does not need to know this structure in advance. Rather, we prove competitive guarantees that show the algorithm provides a bound within a constant factor of the best possible bound (of a certain functional form) in hindsight.
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Shuffling models can enable differentially private protocols with far smaller error than the local model, while relying on weaker trust assumptions than the central model.
“This can enable differentially private protocols with far smaller error than what is possible in the local model, while relying on weaker trust assumptions than in the central model, e.g., [120, 178, 45, 201, 204, 200, 202, 203, 110].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [120]
The Introduction (p. 1) discusses adaptive regret bounds, and Related work (p. 16) discusses online convex optimization. Searches for shuffling, differential privacy, local and central models, and trust assumptions found no passage addressing the claimed error or trust comparison. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
No citation lists for this paper
No citation lists for this paper yet — checked again daily.
References 19 · Cited by 227
Research works printed but not linked: 16
- Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In COLT , 2008.
- Peter Auer and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. In COLT , 2000.
- Peter L. Bartlett, Elad Hazan, and Alexander Rakhlin. Adaptive online gradient descent. In NIPS , 2008.
- L´ eon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In NIPS , volume 20, 2008.
- Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006.
- Koby Crammer, Alex Kulesza, and Mark Drezde. Adaptive regularization of weight vectors. In NIPS , 2009.
- Chuong B. Do, Quoc V. Le, and Chuan-Sheng Foo. Proximal regularization for online and batch learning. In ICML , 2009.
- Mark Drezde, Koby Crammer, and Fernando Pereira. Confidence-weighted linear classification. In ICML , 2008.
- John Duchi and Yoram Singer. Efficient learning using forward-backward splitting. In NIPS , 2009.
- Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and Systems Sciences , 71(3), 2005. ISSN 0022-0000.
- Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. In ICML , 2007.
- Matthew Streeter and H. Brendan McMahan. Less regret via online conditioning. http://arxiv.org/abs/1002.4862, 2010. · arXiv
- Lin Xiao. Dual averaging method for regularized stochastic learning and online optimization. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, NIPS , 2009.
- Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In ICML , 2004.
- Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML , 2003.
- Martin Zinkevich. Theoretical guarantees for algorithms in multi-agent settings . PhD thesis, Pittsburgh, PA, USA, 2004.
- Authors
- McMahan, H. B., & Streeter, M.
- Affiliations
- Google (United States) (US)
- ORCID
- McMahan, H. Brendan
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2010
- Pages
- 244-256
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1002.4908
- OpenAlex
- W1518461880
- Cited by
- 227
- References
- 19
- Citations by year
- 2026: 1 · 2025: 5 · 2024: 5 · 2023: 8 · 2022: 18 · 2021: 33 · 2020: 31 · 2019: 35 · 2018: 8 · 2017: 12 · 2016: 20 · 2015: 8 · 2014: 15 · 2013: 13 · 2012: 7
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- online convex optimization, adaptive regularization, regret bounds, adaptive algorithms
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
