CLASP: An online learning algorithm for Convex Losses And Squared Penalties
This work provides improved theoretical guarantees for online learning with constraints, which is incremental but addresses a specific bottleneck in optimization algorithms.
The paper tackles constrained online convex optimization by introducing CLASP, an algorithm that minimizes cumulative loss and squared constraint violations, achieving logarithmic regret and penalty bounds for strongly convex problems.
We study Constrained Online Convex Optimization (COCO), where a learner chooses actions iteratively, observes both unanticipated convex loss and convex constraint, and accumulates loss while incurring penalties for constraint violations. We introduce CLASP (Convex Losses And Squared Penalties), an algorithm that minimizes cumulative loss together with squared constraint violations. Our analysis departs from prior work by fully leveraging the firm non-expansiveness of convex projectors, a proof strategy not previously applied in this setting. For convex losses, CLASP achieves regret $O\left(T^{\max\{β,1-β\}}\right)$ and cumulative squared penalty $O\left(T^{1-β}\right)$ for any $β\in (0,1)$. Most importantly, for strongly convex problems, CLASP provides the first logarithmic guarantees on both regret and cumulative squared penalty. In the strongly convex case, the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.