Revisiting Projection-Free Online Learning with Time-Varying Constraints

Yibo Wang, Yuanyu Wan, Lijun Zhang · 2025

Read Revisiting Projection-Free Online Learning with Time-Varying Constraints by Yibo Wang, Yuanyu Wan, Lijun Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16046.txt.

Introduction

Wang, Wan, and Zhang improve learning systems that must decide step by step while respecting limits that shift over time. Think of a controller that must stay inside a feasible region and keep long-run promises. Projecting each decision back into the region can be too expensive, so projection-free methods are prized. The authors build a surrogate loss that folds goal and constraints together, using a Lyapunov-style construction, then run a parameter-free Frank-Wolfe method on it.

Their bounds on regret and total constraint violation beat the previous best for general losses, and tighten further for strongly curved losses. The ideas also extend to the harder setting where the learner sees only its own action's loss. Tests on real data back the theory. For engineers running systems under changing rules, the paper offers guarantees that the method will neither wander nor break its promises too often.

Catalog record

CREATORYibo Wang, Yuanyu Wan, Lijun Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16046

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Revisiting Projection-Free Online Learning with Time-Varying Constraints Yibo Wang, Yuanyu Wan, Lijun Zhang Abstract We investigate constrained online convex optimization, in which decisions must belong to a fixed and typically complicated domain, and are required to approximately satisfy additional time-varying constraints over the long term. In this setting, the commonly used projection operations are often computationally expensive or even intractable. To avoid the time-consuming operation, several projection-free methods have been proposed with an 𝒪 ⁡ ( T 3 / 4 ​ log ⁡ T ) \mathcal{O}(T^{3/4}\sqrt{\log T}) regret bound and an 𝒪 ⁡ ( T 7 / 8 ) \mathcal{O}(T^{7/8}) cumulative constraint violation (CCV) bound for general convex losses. In this paper, we improve this result and further establish novel regret and CCV bounds when loss functions are strongly convex. The primary idea is to first construct a composite surrogate loss, involving the original loss and constraint functions, by utilizing the Lyapunov-based technique. Then, we propose a parameter-free variant of the classical projection-free method, namely online Frank-Wolfe (OFW), and run this new extension over the online-generated surrogate loss. Theoretically, for general convex losses, we achieve an 𝒪 ⁡ ( T 3 / 4 ) \mathcal{O}(T^{3/4}) regret bound and an 𝒪 ⁡ ( T 3 / 4 ​ log ⁡ T ) \mathcal{O}(T^{3/4}\log T) CCV bound, both of which are order-wise tighter than existing results. For strongly convex losses, we establish new guarantees of an 𝒪 ⁡ ( T 2 / 3 ) \mathcal{O}(T^{2/3}) regret bound and an 𝒪 ⁡ ( T 5 / 6 ) \mathcal{O}(T^{5/6}) CCV bound. Moreover, we also extend our methods to a more challenging setting with bandit feedback, obtaining similar theoretical findings. Empirically, experiments on real-world datasets have demonstrated the effectiveness of our methods. 1 National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China 2 School of Artificial Intelligence, Nanjing University, Nanjing 210023, China 3 School of Software Technology, Zhejiang University, Ningbo 315048, China {wangyb, zhanglj}@lamda.nju.edu.cn, [email protected] Introduction Online convex optimization (OCO) has become a popular paradigm for modeling online decision-making problems ( Shalev-Shwartz 2012 ; Hazan 2016 ; Orabona 2019 ) , such as online portfolio optimization ( Agarwal et al. 2006 ) and online advertisement system ( McMahan et al. 2013 ) . Formally, OCO can be viewed as a structured iterative game between a learner and an adversary. Specifically, at each round t , the learner first chooses a decision \mathbf{x}_{t} from a convex and fixed domain \mathcal{K}\subseteq\mathbb{R}^{d} . Then, the adversary reveals a convex loss function f_{t}(\cdot):\mathcal{K}\mapsto\mathbb{R} , and the learner suffers the cost f_{t}(\mathbf{x}_{t}) . The goal of the learner is to minimize the regret: \mathrm{Regret}_{T}=\sum\nolimits_{t=1}^{T}f_{t}(\mathbf{x}_{t})-\min_{\mathbf{x}\in\mathcal{K}}\sum\nolimits_{t=1}^{T}f_{t}(\mathbf{x}), (1) defined as the difference between the cumulative loss of the learner and that of the best fixed decision. In the literature, there have been abundant theoretical appeals for OCO, such as the \mathcal{O}(\sqrt{T}) regret bound for general convex losses ( Zinkevich 2003 ) and the \mathcal{O}(\log T) regret bound for strongly convex losses ( Hazan, Agarwal, and Kale 2007 ) . In practice, besides the hard and fixed domain \mathcal{K} , the decisions made by the learner are typically governed by a series of soft and time-varying constraints, which may be violated in several rounds but should be satisfied on average over the long term. For example, in wireless communication systems, operators manage varying transmission power consumption to ensure the reception of messages ( Mannor, Tsitsiklis, and Yu 2009 ) ; in online advertisement systems, advertisers employ dynamic budgets to maximize the click-through-rates for their advertisements ( Liakopoulos et al. 2019 ) . These practical applications thus motivate the development of constrained online convex optimization (COCO) ( Mahdavi, Jin, and Yang 2012 ; Neely and Yu 2017 ) . In the framework of COCO, the time-varying constraints are typically captured by the inequality g_{t}(\mathbf{x})\leq 0 where g_{t}(\cdot):\mathcal{K}\mapsto\mathbb{R} is a convex function revealed by the adversary at the end of each round t . Consequently, in addition to minimizing ( 1 ), the learner also aims to ensure the cumulative constraint violation (CCV): Q_{T}=\sum\nolimits_{t=1}^{T}g_{t}^{+}(\mathbf{x}_{t}) (2) to be sublinear with respect to the time horizon T , where g_{t}^{+}(\mathbf{x})\triangleq\mathrm{max}\{0,g_{t}(\mathbf{x})\} . To optimize ( 1 ) and ( 2 ) concurrently, various efforts have been made recently ( Cao and Liu 2019 ; Yu and Neely 2020 ; Yi et al. 2021 ; Guo et al. 2022 ; Yi et al. 2023 ; Sinha and Vaze 2024 ) , and established plentiful guarantees, including the regret and CCV bounds of \mathcal{O}(\sqrt{T}) for general convex losses ( Yu, Neely, and Wei 2017 ) . The key operation in these COCO methods is the projection that pulls an infeasible decision back into the hard constraint \mathcal{K} . In many practical scenarios, the domain \mathcal{K} is typically high-dimensional and complex, rendering projections onto \mathcal{K} computationally expensive or even intractable, which significantly limits the applicability of these methods. To address this issue, several studies ( Lee, Ho-Nguyen, and Lee 2023 ; Garber and Kretzu 2024 ) propose projection-free methods for COCO, which replace the time-consuming projection with the more efficient linear optimization operation. One prominent example is online semidefinite optimization, where the hard constraint is a positive semidefinite cone with the bounded trace. In this case, the linear optimization has been proven at least an order of magnitude faster than projection ( Hazan and Kale 2012 ) . Unfortunately, existing projection-free methods can only guarantee the \mathcal{O}(T^{3/4}\sqrt{\log T}) regret bound and the \mathcal{O}(T^{7/8}) CCV bound for general convex losses ( Garber and Kretzu 2024 ) . In this paper, we improve the above bounds and introduce new theoretical guarantees for strongly convex losses. The key idea is to first construct a composite surrogate loss that consists of the original loss f_{t}(\cdot) and the time-varying constraint g_{t}(\cdot) , based on a carefully designed Lyapunov function. Rigorous analysis reveals that both ( 1 ) and ( 2 ) are simultaneously controlled by the regret in terms of the surrogate losses, so that we can directly apply classical projection-free methods, e.g., online Frank-Wolfe (OFW) ( Hazan and Kale 2012 ) , over the surrogate losses to minimize the two metrics. Notably, since the surrogate loss is generated in an online manner, essential prior knowledge for OFW (e.g., the gradient norm bound) is unavailable beforehand. Therefore, we need to employ the methods that are agnostic to the prior parameters about the surrogate loss. To this end, we propose the first parameter-free variant of OFW for general convex losses based on the doubling trick technique ( Cesa-Bianchi et al. 1997 ) . By running the parameter-free variant over the composite surrogate losses, we establish an \mathcal{O}(T^{3/4}) regret bound and an \mathcal{O}(T^{3/4}\log T) CCV bound for the general convex loss. Both of our results are better than the state-of-the-art bounds achieved by Garber and Kretzu (2024) . Additionally, we further investigate the strongly convex loss and achieve an \mathcal{O}(T^{2/3}) regret bound and an \mathcal{O}(T^{5/6}) CCV bound, by constructing the surrogate loss based on a different Lyapunov function and running the strongly convex variant of OFW ( Wan and Zhang 2021 ) . Furthermore, to handle the more challenging bandit setting, we combine our proposed methods with the classical one-point estimator ( Flaxman, Kalai, and

Read the complete text