CLASP: Online learning algorithms for Convex Losses And Squared Penalties

Addressing Constrained Online Convex Optimization (COCO), we introduce CLASP (Convex Losses And Squared Penalties), a framework that minimizes cumulative loss together with squared constraint violations. We propose two variants of CLASP, CLASP-I and CLASP-F, allowing for a joint or separate handling of the static decision set and the time-varying constraints, a decoupling flexibility that affords simpler implementations when projections onto the static decision set are easy. Our theoretical analysis departs from prior work by fully leveraging the variety of \emph{cutter operators}, and contraction properties such as the strongly quasi-nonexpansiveness, a proof strategy not previously applied in this setting. For convex losses, both CLASP algorithms achieve regret $O\left(T^{\max\\{\beta,1-\beta\\}}\right)$ and cumulative squared penalty $O\left(T^{\\{1-\beta\\}}\right)$ for any $\beta \in (0,1)$. Most importantly, for strongly convex problems, we provide the first logarithmic guarantees on both regret and cumulative squared penalty: In the strongly convex case, both CLASP algorithms guarantee that the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.

Many systems must keep adapting as they operate: for example, a drone may adjust its motion as the wind changes, or a power grid controller may respond to shifting demand. In such settings, making effective decisions is not enough. Large violations of safety or operational limits can be far more harmful than small ones. We introduce CLASP, a method for online learning that balances performance with a penalty that increases quickly when a constraint is exceeded by a large amount. This focuses learning on preventing severe breaches, rather than pricing every additional unit of violation equally. CLASP comes in two forms: one projects updated decisions back toward the currently allowed region, while the other uses a simpler correction step. We prove that, for an important family of learning problems, both the cost of adapting online and the accumulated severity of violations grow only very slowly as decisions continue. Experiments on online prediction and classification tasks support this balance between performance and limiting severe breaches. CLASP may help build more reliable adaptive systems in robotics, energy, and other changing environments.