Summary of Projection-free Online Convex Optimization with Time-varying Constraints, by Dan Garber et al.
Projection-Free Online Convex Optimization with Time-Varying Constraints
by Dan Garber, Ben Kretzu
First submitted to arxiv on: 13 Feb 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Optimization and Control (math.OC); Machine Learning (stat.ML)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary A novel approach to online convex optimization is introduced, focusing on scenarios where actions must satisfy both fixed constraints and time-varying soft constraints. To address this challenge, projection-free algorithms are designed that access the fixed constraint set through a linear optimization oracle (LOO). The proposed algorithm ensures (T^{3/4}) regret with respect to losses and O(T^{7/8}) constraints violation, holding across any interval of the sequence. Additionally, a more efficient variant is presented that leverages first-order oracle access to soft constraints, achieving similar bounds in expectation. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Online convex optimization is used to solve problems where actions must follow certain rules. In this case, we’re looking at scenarios where these rules change over time and we need to make sure our actions are still okay. To do this, we’ve created algorithms that don’t require projecting the actions onto a fixed set of constraints. Instead, they use a “linear optimization oracle” (LOO) to check if the actions are valid. The algorithm works well, with an average regret (a measure of how good our predictions were) and constraint violation that gets better as we do more iterations. |
Keywords
* Artificial intelligence * Optimization
