![[2402.08621] A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2402.08621] A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization
Summary
This paper presents a unified framework for analyzing meta-algorithms in online convex optimization, addressing various feedback types and regret notions.
Why It Matters
Understanding online convex optimization is crucial for developing efficient algorithms in machine learning. This framework simplifies existing proofs and introduces new results, enhancing algorithm design across different settings, which is vital for researchers and practitioners in the field.
Key Takeaways
- Introduces a framework for analyzing meta-algorithms in online convex optimization.
- Covers various feedback types and regret notions, enhancing algorithm adaptability.
- Simplifies existing results in the literature with new proof techniques.
- Demonstrates the transformation of algorithms from full-information to semi-bandit feedback.
- Provides insights into converting first-order algorithms to zeroth-order with comparable bounds.
Computer Science > Machine Learning arXiv:2402.08621 (cs) [Submitted on 13 Feb 2024 (v1), last revised 20 Feb 2026 (this version, v4)] Title:A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization Authors:Mohammad Pedramfar, Vaneet Aggarwal View a PDF of the paper titled A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization, by Mohammad Pedramfar and 1 other authors View PDF HTML (experimental) Abstract:In this paper, we analyze the problem of online convex optimization in different settings, including different feedback types (full-information/semi-bandit/bandit/etc) in either stochastic or non-stochastic setting and different notions of regret (static adversarial regret/dynamic regret/adaptive regret). This is done through a framework which allows us to systematically propose and analyze meta-algorithms for the various settings described above. We show that any algorithm for online linear optimization with deterministic gradient feedback against fully adaptive adversaries is an algorithm for online convex optimization. We also show that any such algorithm that requires full-information feedback may be transformed to an algorithm with semi-bandit feedback with comparable regret bound. We further show that algorithms that are designed for fully adaptive adversaries using deterministic semi-bandit feedback can obtain similar bounds using only stochastic semi-bandit feedback when facing oblivious adversaries. We use this to d...