Revisiting Projection-Free Online Learning with Time-Varying Constraints

Yibo Wang, Yuanyu Wan, Lijun Zhang

Abstract

This paper addresses the computational challenges of Constrained Online Convex Optimization (COCO) with time-varying constraints. By integrating a Lyapunov-based surrogate loss with a parameter-free Frank-Wolfe approach, the authors propose algorithms that eliminate the need for expensive projection steps. The proposed methods achieve tighter theoretical bounds for general convex functions and provide the first guarantees for strongly convex losses in this setting. Empirical results on real-world datasets demonstrate superior performance in both full-information and bandit feedback scenarios.

Introduction

In Online Convex Optimization (OCO), a learner makes a sequence of decisions to minimize a cumulative loss. However, real-world applications—such as power management in wireless networks or budget allocation in ad auctions—often involve "soft" constraints that change over time, a framework known as Constrained OCO (COCO).

The standard approach to handling these constraints involves "projections," which pull an infeasible decision back into the valid region. Unfortunately, projections are computationally expensive and often intractable in high-dimensional spaces. While projection-free methods like the Frank-Wolfe algorithm exist, previous iterations for time-varying constraints suffered from loose theoretical guarantees. This research aims to bridge that gap, providing faster, more reliable algorithms that bypass heavy-duty computation.

Methodology

The authors introduce a suite of algorithms, primarily OFW-TVC (Online Frank-Wolfe with Time-Varying Constraints) and its variants, built upon two core innovations:

  1. Lyapunov-based Surrogate Loss: Rather than treating the loss function and constraints independently, the authors combine them into a single "surrogate" loss. Utilizing a Lyapunov drift-plus-penalty framework, the algorithm balances the immediate cost of the loss against the long-term penalty of violating constraints.
  2. Parameter-Free Online Frank-Wolfe (OFW): Standard OFW algorithms typically require prior knowledge of the "gradient norm bound," a value rarely known in advance. The authors implement a "doubling trick" that allows the algorithm to estimate this bound dynamically, making the system truly parameter-free and robust for practical engineering applications.

The framework is extended across three distinct scenarios: general convex losses (using an exponential Lyapunov function), strongly convex losses (using a quadratic Lyapunov function to exploit curvature), and bandit feedback (where only the loss value is observed, requiring a one-point gradient estimator).

Empirical Evaluation

The proposed methods were evaluated using an online matrix completion task on two real-world datasets: MovieLens (100k) for the full-information setting and Film Trust for the bandit feedback setting. In these experiments, the learner predicts user ratings while adhering to time-varying linear constraints.

Performance comparison of OFW-TVC and SCOFW-TVC against baselines in the full-information setting (MovieLens).

As shown in the full-information results, the proposed OFW-TVC and SCOFW-TVC algorithms consistently outperform existing baselines like OPDP and LPM, maintaining lower cumulative cost loss and significantly lower cumulative constraint violations (CCV).

Performance comparison of BFW-TVC and SCBFW-TVC against baselines in the bandit feedback setting (Film Trust).

In the more challenging bandit feedback setting, the BFW-TVC and SCBFW-TVC variants similarly demonstrate superior stability and efficiency compared to the LBPM baseline.

Key Results and Insights

The paper establishes new state-of-the-art theoretical bounds:

  • General Convex: Achieved $O(T^{3/4})$ regret and $O(T^{3/4} \log T)$ cumulative constraint violation (CCV), an order-wise improvement over previous $O(T^{7/8})$ CCV results.
  • Strongly Convex: Established the first guarantees for this setting in projection-free COCO, reaching $O(T^{2/3})$ regret and $O(T^{5/6})$ CCV.
  • Simplicity and Agnosticism: Unlike complex state-of-the-art methods requiring multiple linear optimizations, this approach requires only one per round. Furthermore, the parameter-free nature (via the doubling trick) simplifies deployment by removing the need for exhaustive hyperparameter tuning.

Conclusion

By revisiting projection-free online learning through the lens of Lyapunov optimization, this work provides a more efficient and theoretically sound path for solving constrained online problems. While the authors noted a trade-off in the strongly convex case—where improved regret bounds led to slightly looser constraint violation bounds—the overall framework represents a significant advancement. Future research will focus on identifying more powerful Lyapunov functions to simultaneously optimize both metrics for strongly convex losses.

Summary updated

BibTeX
@inproceedings{wang2025revisiting,
  author = {Yibo Wang and Yuanyu Wan and Lijun Zhang},
  title = {{Revisiting Projection-Free Online Learning with Time-Varying Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=RU2XpQsIA9},
}
Figure