Universal Online Convex Optimization with $1$ Projection per Round

Authors: wenhao  yang
yibo  wang
peng  zhao
lijun  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 16:51:23

Abstract: To address the uncertainty in function types, recent progress in online convex optimization (OCO) has spurred the development of universal algorithms that simultaneously attain minimax rates for multiple types of convex functions. However, for a $T$-round online problem, state-of-the-art methods typically conduct $O(\log T)$ projections onto the domain in each round, a process potentially time-consuming with complicated feasible sets. In this paper, inspired by the black-box reduction of Cutkosky and Orabona [2018], we employ a surrogate loss defined over simpler domains to develop universal OCO algorithms that only require $1$ projection. Embracing the framework of prediction with expert advice, we maintain a set of experts for each type of functions and aggregate their predictions via a meta-algorithm. The crux of our approach lies in a uniquely designed expert-loss for strongly convex functions, stemming from an innovative decomposition of the regret into the meta-regret and the expert-regret. Our analysis sheds new light on the surrogate loss, facilitating a rigorous examination of the discrepancy between the regret of the original loss and that of the surrogate loss, and carefully controlling meta-regret under the strong convexity condition. With only $1$ projection per round, we establish optimal regret bounds for general convex, exponentially concave, and strongly convex functions simultaneously. Furthermore, we enhance the expert-loss to exploit the smoothness property, and demonstrate that our algorithm can attain small-loss regret for multiple types of convex and smooth functions.

Main paper: 
 introduction: 
 Online convex optimization (OCO) stands as a pivotal online learning framework for modeling many real-world problems [Hazan, 2016] . OCO is commonly formulated as a repeated game between the learner and the environment with the following protocol. In each round t ∈ [T ], the learner chooses a decision x t from a convex domain X ⊆ R d ; after submitting this decision, the learner suffers a loss f t (x t ), where f t : X → R is a convex function selected by the environment. The goal of the learner is to minimize the cumulative loss over T rounds, i.e., T t=1 f t (x t ), and the standard performance measure is the regret [Cesa- Bianchi and Lugosi, 2006] :EQUATIONwhich quantifies the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight.Table 1 : A summary of our universal algorithms and previous studies over T rounds d-dimensional functions, where L T denotes the small-loss quantity. Abbreviations: cvx → convex, exp-concave → exponentially concave, str-cvx → strongly convex, # PROJ → number of projections per round. Although there are plenty of algorithms to minimize the regret of convex functions, including general convex, exponentially concave (abbr. exp-concave) and strongly convex functions [Zinkevich, 2003 , Shalev-Shwartz et al., 2007 , Hazan et al., 2007] , most of them can only handle one specific function type, and need to estimate the moduli of strong convexity and exp-concavity. The demand for prior knowledge motivates the development of universal algorithms for OCO, which aim to attain minimax optimal regret guarantees for multiple types of convex functions simultaneously [Bartlett et al., 2008 , van Erven and Koolen, 2016 , Wang et al., 2019 , Mhammedi et al., 2019 , Zhang et al., 2022] . State-of-the-art methods typically adopt a two-layer structure following the prediction with expert advice (PEA) framework [Cesa-Bianchi and Lugosi, 2006] . Specifically, they maintain O(log T ) expert-algorithms with different configurations to handle the uncertainty of functions and deploy a meta-algorithm to track the best one. While this two-layer framework has demonstrated effectiveness in endowing algorithms with universality, it raises concerns regarding the computational efficiency. Since each expert-algorithm needs to execute one projection onto the feasible domain X per round, standard universal algorithms perform O(log T ) projections in each round, which can be time-consuming in practical scenarios particularly when projecting onto complicated domains.In the literature, there indeed exists an effort to reduce the number of projections required by universal algorithms tailored for exp-concave functions [Mhammedi et al., 2019] . This is achieved by applying the black-box reduction of Cutkosky and Orabona [2018] , which reduces an OCO problem on the original (but can be complicated) feasible domain to a more manageable one on a simpler domain, such as an Euclidean ball. Deploying an existing universal algorithm [van Erven and Koolen, 2016] on the reduced problem enables us to attain optimal regret for exp-concave functions, crucially, with only one single projection per round and no prior knowledge of exp-concavity required. However, this black-box approach cannot be extended to strongly convex functions (see Section 3.1 for technical discussions). Therefore, it is still unclear on how to reduce the number of projections of universal algorithms to 1, and at the same time ensure optimal regret for strongly convex functions (as well as general convex and exp-concave functions).In this paper, we affirmatively solve the above question by introducing an efficient universal OCO algorithm. Our solution employs the black-box reduction Cutkosky [2020] to cast the original problem on the constrained domain X to an alternative one in terms of the surrogate loss on a simpler domain Y ⊇ X . Specifically, we construct multiple experts updated in domain Y, each optimizing a expert-loss specialized for a distinct function type. Then, we combine their predictions by a metaalgorithm, and perform the only projection onto the feasible domain X . The meta-algorithm chooses the linearized surrogate loss to measure the performance of experts, and is required to yield a secondorder regret [Zhang et al., 2022] . The key novelty of our algorithm lies in the uniquely designed expert-loss for strongly convex functions, which is motivated by an innovative decomposition of the regret into the meta-regret and the expert-regret. To effectively deal with strongly convex functions, we explore the domain-converting surrogate loss in depth and illuminate its refined properties. Our new insights tighten the regret gap in terms of original loss and surrogate loss, and further exploit strong convexity to compensate the meta-regret, thus achieving the optimal regret for strongly convex functions. Section 3.2 provides a formal description of our key ideas. With only 1 projection per round, our algorithm attains O( √ T ), O( d α log T ), and O( 1 λ log T ) regret for general convex, α-exp-concave, and λ-strongly convex functions, respectively.We further establish small-loss regret for universal OCO with smooth functions. The small-loss quantity L T = min x∈X T t=1 f t (x) is defined as the cumulative loss of the best decision chosen from the domain X , which is at most O(T ) under standard OCO assumptions and meanwhile can be much smaller in benign environments. To achieve small-loss regret bounds, we design an enhanced expert-loss for smooth and strongly convex functions and integrate it into our two-layer framework, which finally leads to a universal OCO algorithm achieving O( √ L T ), O( d α log L T ), and O( 1 λ log L T ) small-loss regret for three types of convex functions, respectively. Notably, all those bounds are optimal and the algorithm only requires one projection per iteration. We summarize our results and compare with previous studies of universal algorithms in Table 1 .Organization. The rest of the paper is organized as follows. Section 2 presents the preliminaries and reviews several mostly related works. Section 3 illuminates the technical challenges and describes our key ideas. Section 4 provides the overall algorithms and regret analysis. We finally conclude the paper in Section 5. All the proofs and omitted details are deferred to appendices. 
preliminaries and related works: 
 In this section, we first present preliminaries for OCO, and then review several most related works to our paper, including universal algorithms and projection-efficient algorithms.We introduce two typical assumptions of online convex optimization [Hazan, 2016] .Assumption 1 (bounded domain) The feasible domain X ⊆ R d contains the origin 0, and the diameter is bounded by D, i.e., ∥x -y∥ ≤ D holds for any x, y ∈ X .Assumption 2 (bounded gradient norms) The norm of the gradients of all online functions over the domain X is bounded by G, i.e., ∥∇f t (x)∥ ≤ G holds for all x ∈ X and t ∈ [T ].Throughout the paper we use ∥ • ∥ for ℓ 2 -norm in default. Owing to Assumption 1, we can always construct an Euclidean ball Y = {x | ∥x∥ ≤ D} containing the original feasible domain X .Next, we state definitions of strong convexity and exp-concavity [Hazan, 2016] , and introduce an important property of exp-concave functions [Hazan et al., 2007, Lemma 3] .Definition 1 (strongly convex functions) A function f : X → R is called λ-strongly convex, if the condition f (y) ≥ f (x) + ⟨∇f (x), y -x⟩ + λ 2 ∥y -x∥ 2 holds for all x, y ∈ X . Definition 2 (exponentially-concave functions) A function f : X → R is called α-exponentially- concave, if the function exp(-αf (•)) is concave over the feasible domain X .Lemma 1 For an α-exp-concave function f : X → R, if the feasible domain X has a diameter D and ∥∇f (x)∥ ≤ G holds for ∀x ∈ X , then we haveEQUATION)for all x, y ∈ X , where β = 1 2 min{ 1 4GD , α}.There are many efforts devoted to minimizing regret, including general convex, α-exp-concave, and λ-strongly convex functions. For general convex functions, online gradient descent (OGD) with step size [Zinkevich, 2003] . For α-exp-concave functions, online Newton step (ONS) is equipped with an O( d α log T ) regret [Hazan et al., 2007] . For λ-strongly convex functions, OGD with step size Shwartz et al., 2007] . These regret bounds are proved to be minimax optimal [Ordentlich and Cover, 1998, Abernethy et al., 2008] . Furthermore, tighter bounds are attainable when the loss functions enjoy additional properties, such as smoothness [Shalev-Shwartz, 2007 , Luo and Schapire, 2015 , Srebro et al., 2010 , Orabona et al., 2012 , Chiang et al., 2012 , Yang et al., 2014 , Mohri and Yang, 2016 , Zhang et al., 2019 , Zhao et al., 2020 , 2024 , Chen et al., 2024] and sparsity of gradients [Duchi et al., 2010 , Tieleman and Hinton, 2012 , Mukkamala and Hein, 2017 , Kingma and Ba, 2015 , Reddi et al., 2018 , Loshchilov and Hutter, 2019 , Wang et al., 2020a] . We discuss small-loss regret below.η t = O(1/ √ t), attains an O( √ T ) regretη t = O(1/[λt]), achieves an O( 1 λ log T ) regret [Shalev-For general convex and smooth functions, Srebro et al. [2010] prove that OGD with constant step size attains an O( √ L) regret bound, where L is the upper bound of L T . The limitation of their method is that it requires to know L beforehand. To address this limitation, Zhang et al. [2019] propose scale-free online gradient descent (SOGD), which is a special case of scale-free mirror descent algorithm [Orabona and Pál, 2018] , and establish an O( √ L T ) small-loss regret bound without the prior knowledge of L T . For α-exp-concave and smooth functions, ONS attains an O( d α log L T ) small-loss regret bound [Orabona et al., 2012] . For λ-strongly convex and smooth functions, a variant of OGD, namely S 2 OGD, is introduced to achieve an O( 1 λ log L T ) small-loss regret bound [Wang et al., 2020b] . Such bounds reduce to the minimax optimal bounds in the worst case, but could be much tighter when the comparator has a small loss, i.e., L T is small.Most existing online algorithms can only handle one type of convex function and need to know the moduli of strong convexity and exp-concavity beforehand. Universal online learning aims to remove such requirements of domain knowledge. The first universal OCO algorithm is adaptive online gradient descent (AOGD) [Bartlett et al., 2008] , which achieves O( √ T ) and O(log T ) regret bounds for general convex and strongly convex functions, respectively. However, the algorithm still needs to know the modulus of strong convexity and does not support exp-concave functions.An important milestone is the multiple eta gradient (MetaGrad) algorithm [van Erven and Koolen, 2016] , which adapt to general convex and exp-concave functions without knowing the modulus of expconcavity. MetaGrad constructs multiple expert-algorithms with various learning rates and combines their predictions by a meta-algorithm called Tilted Exponentially Weighted Average (TEWA). To avoid prior knowledge, each expert minimizes the expert-loss parameterized by a learning rate η,EQUATION)MetaGrad maintains O(log T ) experts to minimize (3), and attains O( √ T log log T ) and O( d α log T ) regret for general convex and α-exp-concave functions, respectively. To further support strongly convex functions, Wang et al. [2019] propose a new type of expert-losses defined asℓ sc t,η (x) = -η⟨∇f t (x t ), x t -x⟩ + η 2 G 2 ∥x t -x∥ 2 (4)where G is the gradient norm upper bound, and introduce an expert-loss for general convex functionsℓ cvx t,η (x) = -η⟨∇f t (x t ), x t -x⟩ + η 2 G 2 D 2 (5)where D is the upper bound of the diameter of X . Their algorithm, named as Maler, obtains O( √ T ), O( 1 λ log T ) and O( d α log T ) regret for general convex, λ-strongly convex functions, and α-exp-concave functions, respectively. Later, Wang et al. [2020b] extend Maler by replacing G 2 in (4) and ( 5) with ∥∇f t (x t )∥ 2 , thereby enabling their algorithm to deliver small-loss regret bounds. Under the smoothness condition, their algorithm achieves O(√ L T ), O( 1 λ log L T )and O( d α log L T ) regret for general convex, λ-strongly convex, and α-exp-concave functions, respectively.MetaGrad and its variants require the carefully designed expert-losses. Zhang et al. [2022] propose a different universal strategy that avoids the construction of losses. The basic idea is to let each expert handle original functions and deploy a meta-algorithm over linearized loss. Importantly, the meta-algorithm is required to yield a second-order regret [Gaillard et al., 2014] to exploit strong convexity and exp-concavity. By incorporating existing online algorithms as experts, their approach inherits the regret of any expert designed for strongly convex functions and exp-concave functions, and also obtains minimax optimal regret (and small-loss regret) for general convex functions.Although state-of-the-art universal algorithms can adapt to multiple function types, they create O(log T ) experts per round. As a result, they need to perform O(log T ) projections in each round, which can be time-consuming in practical scenarios with complicated domains. To address this limitation, we aim to develop projection-efficient algorithms for universal OCO.In the studies of parameter-free online learning, Cutkosky and Orabona [2018] propose a black-box reduction technique from constrained online learning to unconstrained online learning. To avoid regret degeneration, they design the domain-converting surrogate loss g t : Y → R defined as,EQUATIONwhere S X (y) = ∥y -Π X [y]∥ is the distance function to the feasible domain X . Then, we can employ an unconstrained online learning algorithm that minimizes (6) to obtain the prediction y t , and output its prediction on domain X , i.e., x t = Π X [y t ]. Cutkosky and Orabona [2018, Theorem 3] have proved that the above surrogate loss satisfies ∥∇ g t (y t )∥ ≤ ∥∇f t (x t )∥, andEQUATIONfor all t ∈ [T ] and any x ∈ X . Based on this fact, we know that the regret of the unconstrained problem directly serves as an upper bound for that of the original problem, hence reducing the original problem to an unconstrained surrogate problem and retaining the order of regret.Subsequently, Cutkosky [2020] introduces a new surrogate loss g t : Y → R defined as,EQUATIONwhere v t = yt-xt ∥yt-xt∥ is the unit vector of the projection direction. As depicted in the following lemma, this surrogate loss avoids the multiplicative constant 2 on the right-hand side of (7).Lemma 2 (Theorem 2 of Cutkosky [2020] ) The function defined in (8) is convex, and it satisfies ∥∇g t (y t )∥ ≤ ∥∇f t (x t )∥. Furthermore, for all t and all x ∈ X , we haveEQUATIONWhile the black-box reduction is proposed for the constrained-to-unconstrained conversion, it also facilitates the conversion to another constrained problem (i.e., Y ̸ = R d ). This enables us to transform OCO problem on a complicated domain into another on simpler domains such that the projection is much easier. Building on this idea, Mhammedi et al. [2019] introduce an efficient implementation of MetaGrad [van Erven and Koolen, 2016] , which only conducts 1 projection onto the original domain in each round, and keeps the order of regret bounds. However, as detailed in the following section, the black-box reduction does not adequately extend to strongly convex functions. We also mention that Zhao et al. [2022] recently employ the technique to non-stationary OCO with non-trivial modifications to develop efficient algorithms for minimizing dynamic regret and adaptive regret. However, they focus on the convex functions and do not involve the considerations of exp-concave and strongly convex functions as concerned in our paper.3 Technical challenge and our key ideasIn this section, we elaborate on the technical challenges and our key ideas. 
technical challenge: 
 As mentioned, Mhammedi et al. [2019] exploit the black-box reduction scheme of [Cutkosky and Orabona, 2018] to improve the projection efficiency of MetaGrad [van Erven and Koolen, 2016] . We summarize their algorithm in Algorithm 1. In the following, we will demonstrate its effectiveness for exp-concave functions and explain why it fails for strongly convex functions. Construct the surrogate loss g t (•) as ( 6) and send it to MetaGrad 7: end forThe above bound is measured by surrogate loss, thus requiring a further analysis that converts it back to that of the original function. Since β = 1 2 min 1 4GD , α , the function x -βx 2 is strictly increasing when x ∈ (-∞, 2GD]. Therefore, the property of surrogate loss g t (•) in ( 7) impliesEQUATION)Combining ( 10) with ( 11) and applying the AM-GM inequality, we obtainT t=1 ⟨∇f t (x t ), x t -x⟩ - β 2 T t=1 ⟨∇f t (x t ), x t -x⟩ 2 ≤ O d α log Tthus achieving the optimal regret based on Lemma 1.Failure in strongly convex functions. To handle strongly convex functions, a straightforward way is to use a universal algorithm that supports strongly convex functions, such as Maler [Wang et al., 2019] , as the black-box subroutine in Algorithm 1. However, for strongly convex functions, the above analysis cannot be applied, and we are unable to derive a tight regret bound. Specifically, according to the theoretical guarantee of Maler [Wang et al., 2019 , Theorem 1], we haveEQUATION)From the standard black-box analysis and the definition of strong convexity, we knowEQUATION)Substituting ( 12) into (13), we encounter an O(T t=1 ∥y t -x∥ 2 -λ 2 T t=1 ∥x t -x∥ 2) term, which is unmanageable since ∥y t -x∥ ≥ ∥x t -x∥. Here, O(•) further omits the ploy(log T ) factors.To address above challenges, we introduce novel ideas in both algorithm design and regret analysis.Algorithm design. Our algorithm is still in a two-layer structure. The main contribution lies in a uniquely designed expert-loss for strongly convex functions. For simplicity, we consider that the modulus of strong convexity λ is known for a moment, and defineEQUATION)where g t (•) is the surrogate loss defined in (8). Let us compare our designed expert-loss ( 14) with the one when applying existing universal algorithms in a black-box manner. Suppose Maler [Wang et al., 2019] is used, their expert-loss construction (4) indicates that the algorithm over domain Y essentially optimizes the expert-loss formulated as (up to constant factors).ℓ sc t (y) = ⟨∇g t (y t ), y⟩ + λ 2 ∥y -y t ∥ 2 (15)An important caveat is that our expert-loss ( 14) evaluates the performance of the expert (associated with strongly convex functions) based on the distance between its output y and the actual decision x t ∈ X , as opposed to the unprojected intermediate one y t ∈ Y in (15).In fact, this design of expert-loss ( 14) stems from a novel regret decomposition as explained below. First, by strong convexity of f t and the property of the domain-converting surrogate loss, we haveT t=1 f t (x t ) - T t=1 f t (x) (9) ≤ T t=1 ⟨∇g t (y t ), y t -x⟩ - λ 2 T t=1 ∥x t -x∥ 2 = T t=1 ⟨∇g t (y t ), y t -y i t ⟩ + T t=1 ⟨∇g t (y t ), y i t -x⟩ - λ 2 T t=1 ∥x t -x∥ 2 (16)where y i t denotes the decision of the i-th expert. The first term of the above bound is the meta-regret in terms of linearized surrogate loss. Then, we reformulate the remaining two terms as followsEQUATION)where the expert-loss in ( 14) naturally arises. Combining ( 16) with ( 17), we arrive atEQUATION)Theoretical analysis. For the expert-regret, since expert-loss ( 14) is λ-strongly convex and its gradients are bounded (see Lemma 6), we can use OGD to achieve an optimal O( 1 λ log T ) regret. Following Zhang et al. [2022] , we require the meta-algorithm to yield a second-order regret boundEQUATIONNotably, the upper bound of ( 19) and the negative term in ( 18) cannot be canceled due to the dismatch between y t -y i t and x t -y i t . To resolve this discrepancy, we demonstrate that the surrogate loss defined in (8) enjoys the following two important improved properties.Lemma 3 In addition to enjoying all the properties outlined in Lemma 2, the surrogate loss functionEQUATIONfor all t and all x ∈ X . Furthermore, we also haveEQUATIONRemark 1 We highlight the improvements of Lemma 3 over Lemma 2. First, we provide a tighter connection between the linearized original function and the surrogate loss in ( 20). Second, we analyze the difference between the actual decision x t and the intermediate decision y t , along the direction ∇g t (y t ) in ( 21). As shown later, both of them are crucial for controlling the meta-regret. ◁Utilizing (20) in Lemma 3, we refine the decomposition in ( 18) to establish a tighter bound 17),( 20)T t=1 f t (x t ) - T t=1 f t (x) (16),(≤ ER(T ) + T t=1 ⟨∇g t (y t ), y t -y i t ⟩ - λ 2 T t=1 ∥x t -y i t ∥ 2 -∆ T (22)where ER(T ) is the expert-regret, and∆ T = T t=1 1 {⟨∇ft(xt),vt⟩≥0} • ⟨∇f t (x t), y t -x t ⟩ ≥ 0 is the negative term introduced in the surrogate loss. Compared to (18), the new upper bound ( 22) enjoys an additional negative term -∆ T , which is essential to achieve a favorable regret bound in the analysis.To utilize the negative quadratic term -λ 2 T t=1 ∥x t -y i t ∥ 2 in ( 22) for compensating the second-order bound in (19), we need to convert y t to x t , a place where (21) comes into play. From ( 19) and ( 21), we prove that for any γ ∈ (0, G 2D ] it holds that (see Lemma 8 for details):EQUATIONSubstituting ( 23) into ( 22), the additional term ∆ T is automatically canceled out, and we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ ER(T ) + O G 2 2γ + γ 2G 2 T t=1 ⟨∇g t (y t ), x t -y i t ⟩ 2 - λ 2 T t=1 ∥x t -y i t ∥ 2 ≤ ER(T ) + O G 2 2γ + γ 2 - λ 2 T t=1 ∥x t -y i t ∥ 2 = O 1 λ log Twhere the final regret bound is because we set γ = min{ G 2D , λ}.Remark 2 Section 2.3 describes two kinds of surrogate loss, as specified in ( 6) and ( 8). Indeed, they both are suitable for parameter-free online learning [Cutkosky, 2020] and non-stationary online learning [Zhao et al., 2022] . However, it is essential to adopt the new surrogate loss in our purpose: as established in Lemma 3, both negative terms and the mild difference between x t and y t are exploited in our regret analysis. By contrast, the old surrogate loss (6) lacks these advanced properties. ◁ 
efficient algorithm for universal online convex optimization: 
 In this section, we present our efficient algorithms for universal OCO. To reduce the cost of projections, we deploy multiple experts on a ball Y = {x | ∥x∥ ≤ D} enclosing domain X . After combining their decisions, we project the solution in Y onto X , which is the only projection onto X per round.To handle unknown parameters of strong convexity and exp-concavity, we construct two finite sets, i.e., P sc and P exp , to approximate their values [Zhang et al., 2022] . Taking λ-strongly convex functions as an example, we assume the unknown modulus λ is bounded by λ ∈ [1/T, 1] 2 , and setP sc = {1/T, 2/T, • • • , 2 N /T }, where N = ⌈log 2 T ⌉.In this way, for any λ ∈ [1/T, 1], there exists a λ ∈ P sc such that λ ≤ λ ≤ 2 λ. Moreover, we design three types of expert-losses. For general convex functions, we construct the expert-loss asEQUATIONwhere g t (y) is defined in (8). Since ℓ cvx t (•) is convex, we use OGD as the expert-algorithm to minimize it. To handle exp-concave functions, we construct the expert-loss for each α ∈ P exp asEQUATION)where β = 1 2 min{ 1 4GD , α}. It is easy to verify that ℓ exp t, α (•) is β 4 -exp-concave, so we use ONS as the expert-algorithm. For strongly convex functions, we construct the expert-loss for each λ ∈ P sc asEQUATION)Since ℓ sc t, λ (•) is λ-strongly convex, we use OGD with step size η t = 1/[ λt] as the expert-algorithm. Finally, we deploy a meta-algorithm to track the best expert on the fly. Following Zhang et al.Algorithm 2 Efficient Algorithm for Universal OCO 1: Input: The modulus set P sc and P exp , the expert set A = ∅, the number of experts k = 0 2: k ← k + 1, create an expert E 1 by running OGD with loss (24) over Y 3: for all α ∈ P exp do 4:k ← k + 1, create an expert E k by running ONS with loss (25) and parameter α over Y 5: end for 6: for all λ ∈ P sc do 7:k ← k + 1, create an expert E k by running OGD with loss (26) and parameter λ over Y 8: end for 9: Add all the experts to the set: [2022], we use the linearized surrogate loss to measure the performance of the experts, and choose Adapt-ML-Prod [Gaillard et al., 2014] as the meta-algorithm to yield a second-order bound.A = {E 1 , E 2 , • • • , E k } 10: for t =Our efficient algorithm for universal OCO is summarized in Algorithm 2. From Steps 2 to 9, it creates a set of experts by running multiple online algorithms over the ball Y, each specialized for a distinct function type. Then, it maintains a set A consisting of all experts, and the i-th expert is denoted by E i . In the t-th round, it computes the weight p i t of each expert E i in Step 11 according to Adapt-ML-Prod. After receiving all the predictions from the experts in Step 12, it aggregates them based on their weights to attain y t in Step 13. Next, it conducts the only projection onto the original domain X to obtain the actual decision x t in Step 14. In Step 15, it evaluates the gradient ∇f t (x t ) to construct the expert-losses in ( 24), (25), and (26). In Step 16, it sends the corresponding expert-loss to each expert so that it can make predictions for the next round.Finally, we elucidate how our algorithm determines the weight of the i-th expert E i . We measure the performance of expert E i by the linearized surrogate loss, i.e., l i t = ⟨∇g t (y t ), y i t -y t ⟩. According to Lemma 2, we have |l i t | ≤ ∥∇g t (y t )∥∥y i t -y t ∥ ≤ 2GD. Since Adapt-ML-Prod requires the loss to fall within the range of [0, 1], we normalize l i t to construct the meta-loss asℓ i t = (⟨∇g t (y t ), y i t - y t ⟩)/(4GD) + 1 2 ∈ [0, 1].The loss of the meta-algorithm in the t-th round is ℓ t = |A| i=1 p i t ℓ i t , which is a constant 1 2 due to its construction and Step 13. For each expert E i , its weight is updated by:EQUATIONwhereη i t-1 = min 1 2 , (ln |A|)/(1 + t-1 s=1 (ℓ s -ℓ i s ) 2) . In the first round, we setw i 0 = 1/|A|.Remark 3 While the surrogate loss in (8) involves the projection operation, our proposed meta-loss and expert-losses only access g t (y) through ∇g t (y t ), which is given by Cutkosky [2020] ,∇g t (y t ) = ∇f t (x t ) -1 {⟨∇ft(xt),vt⟩<0} ⟨∇f t (x t ), v t ⟩ • v twhere v t = yt-xt ∥yt-xt∥ . According to its formulation, the gradient can be directly computed from x t and y t , which means no additional projections are needed. Therefore, in each round, our algorithm requires only 1 projection onto domain X . ◁Due to page limit, we provide the expert-algorithms, as well as all the proofs, in Appendix B. The theoretical guarantee of Algorithm 2 is given below.Theorem 1 Under Assumptions 1 and 2, Algorithm 2 attains O( √ T ), O( d α log T ) and O( 1 λ log T ) regret for general convex functions, α-exp-concave functions with α ∈ [1/T, 1], and λ-strongly convex functions with λ ∈ [1/T, 1], respectively. Remark 4 Similar to previous studies [Wang et al., 2019 , Zhang et al., 2022] , our universal algorithm also achieves the minimax optimal regret, but only requires 1 projection. ◁ 4.2 Efficient algorithm for small-loss universal regret Furthermore, we consider the small-loss regret for smooth and non-negative online functions. To this end, an additional assumption is required [Srebro et al., 2010] .Assumption 3 All the online functions are non-negative, and H-smooth over X .To exploit the smoothness, we enhance the expert-loss for strongly convex functions in (26) asEQUATION)Since ℓ sc t, λ (•) is strongly convex and smooth, we use S 2 OGD [Wang et al., 2020b] as the expertalgorithm. For general convex and exp-concave functions, we reuse ( 24) and ( 25) as the expert-losses, and employ ONS [Orabona et al., 2012] and SOGD [Zhang et al., 2019] as the expert-algorithms. The meta-algorithm remains unchanged. In this way, we obtain the following regret guarantee.Theorem 2 Under Assumptions 1, 2 and 3, the improved version of Algorithm 2 attains O(√ L T ), O( d α log L T ) and O( 1 λ log L T ) regret for general convex functions, α-exp-concave functions with α ∈ [1/T, 1],and λ-strongly convex functions with λ ∈ [1/T, 1], respectively, where the small-loss quantity L T = min x∈X T t=1 f t (x) is the cumulative loss of the best decision from the domain X .Remark 5 With only 1 projection in each round, our universal algorithm is able to deliver optimal small-loss regret bounds for multiple types of convex functions simultaneously. In contrast, Wang et al. [2020b] and Zhang et al. [2022] take O(log T ) projections to achieve the small-loss regret. ◁ 
conclusion and future work: 
 In this paper, we propose a projection-efficient universal algorithm that achieves minimax optimal regret for three types of convex functions with only 1 projection per round. Furthermore, we enhance our algorithm to exploit the smoothness property and demonstrate that it attains small-loss regret for convex and smooth functions. To demonstrate the effectiveness of our proposed method, we also conduct empirical experiments, and the results are presented in Appendix E.There are several directions for future research. First, one potentially unfavorable characteristic of our work is the requirements of domain and gradient boundedness. Motivated by the recent developments in parameter-free online learning for unbounded domains and gradients [Orabona, 2014 , Orabona and Pál, 2016 , Cutkosky and Boahen, 2016 , 2017 , Foster et al., 2017 , Luo et al., 2022 , Jacobsen and Cutkosky, 2022 , 2023] , we will investigate whether our algorithms can further avoid these prior knowledge in the future. Second, in addition to the small-loss bound, another important type of problem-dependent guarantee is the gradient-variation regret bound [Zhao et al., 2020 [Zhao et al., , 2024]] , which has been actively studied recently due to its profound relationship to games and stochastic optimization. In the literature, recent studies [Yan et al., 2023 , 2024 , Xie et al., 2024 , Wang et al., 2024a] achieve almost-optimal gradient-variation regret in universal online learning, but also suffer high projection complexity. Therefore, it remains challenging and important to develop a projection-efficient universal algorithm with optimal gradient-variation regret guarantees. Third, to deal with changing environments, adaptive regret has been proposed to minimize the regret over every interval in various setting of online learning [Hazan and Seshadhri, 2007 , Daniely et al., 2015 , Wan et al., 2021a , Wang et al., 2024b] . Existing universal algorithms [Zhang et al., 2021 , Yang et al., 2024] typically conduct O(log 2 T ) projections per round. In the future, we will investigate whether whether we can reduce the projection complexity of universal algorithms for adaptive regret. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work is mainly theoretical. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We cite the creators of the dataset used in our experiments properly. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: This work does not release new assets. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we provide the detailed procedures of the expert-algorithms in our efficient algorithm.We use OGD [Zinkevich, 2003] to minimize ℓ cvx t (•) in ( 24). The procedure of the expert-algorithm for general convex functions is summarized in Algorithm 3.Algorithm 3 Expert E i : OGD for Convex Functions 1: Let y i 1 be any point in Y 2: for t = 1 to T do 3: Submit y i t to the meta-algorithm 4:Updatey i t+1 = y i t - 1 √ t ∇g t (y t ) 5:Conduct a projection onto Y Thus, we use ONS to minimize ℓ exp t, α (•). Different from OGD, the projection of ONS onto Y cannot be achieved through a simple rescaling like Step 5 in Algorithm 3. Here, we employ an efficient implementation of ONS [Mhammedi et al., 2019] that enhances the efficiency of its projection onto Y. The procedure is summarized in Algorithm 4.y i t+1 = y i t+1 , if ∥ y i t+1 ∥ ≤ D, y i t+1 • D ∥ y i t+1 ∥ ,Algorithm 4 Expert E i : ONS for Exp-concave (and Smooth) Functions1: Let y i 1 be any point in Y and Σ 1 = 1 β 2 D 2 I d 2: for t = 1 to T do 3:Submit y i t to the meta-algorithm 4:UpdateΣ t+1 = Σ t + ∇ℓ exp t, α (y i t )∇ℓ exp t, α (y i t ) ⊤ , y i t+1 = y i t - 1 β Σ -1 t+1 ∇ℓ exp t, α (y i t )where∇ℓ exp t, α (y i t ) = ∇g t (y t ) + β∇g t (y t )∇g t (y t ) ⊤ (y i t -y t ) 5:Conduct a projection onto Y in (29) 6: end for Lemma 5 Let Λ t+1 := diag((λ k t ) k∈ [d] ) and Q t+1 are the matrices of eigenvalues and eigenvectors of (Σ t+1 -1 β 2 D 2 I d ), respectively. Then, the projection onto the ball Y in Step 5 can be formulated asEQUATIONwherex i t+1 is the unique solution of ρ(x) := d k=1 ⟨e k ,Qt+1Σt+1 y i t+1 ⟩ 2 (x+λ k t ) 2 = D 2 .We establish the following lemma for function ℓ sc t (•) in ( 14). Lemma 6 Under Assumptions 1 and 2, the loss function ℓ sc t (•) in ( 14) is λ-strongly convex, and 26) shares the same formulation as ℓ sc t (•), ℓ sc t, λ (•) also benefits from the aforementioned properties, with the distinction being the substitution of λ for λ. Therefore, we use a variant of OGD [Shalev-Shwartz et al., 2007] to minimize ℓ sc t, λ (•). The procedure is summarized in Algorithm 5.∥∇ℓ sc t (y)∥ 2 ≤ (G + 2D) 2 . Since ℓ sc t, λ (•) in (Algorithm 5 Expert E i : OGD for Strongly Convex Functions 1: Let y i 1 be any point in Y 2: for t = 1 to T do 3: Submit y i t to the meta-algorithm 4:Updatey i t+1 = y i t - 1 λt ∇ℓ sc t, λ (y i t )where∇ℓ sc t, λ (y i t ) = ∇g t (y t ) + λ(y i t -x t ) 5:Conduct a projection onto Yy i t+1 = y i t+1 , if ∥ y i t+1 ∥ ≤ D, y i t+1 • D ∥ y it+1 ∥ , otherwise . 6: end for A.4 Scale-free online gradient descent for convex and smooth functionsTo exploit smoothness, we use scale-free online gradient descent (SOGD) [Zhang et al., 2019] to minimize ℓ cvx t (•) in ( 24). The procedure is summarized in Algorithm 6.Algorithm 6 Expert E i : Scale-free OGD for Convex and Smooth Functions 1: Let y i 1 be any point in Y 2: for t = 1 to T do 3: Submit y i t to the meta-algorithm 4:Updatey i t+1 = y i t -η t ∇g t (y t ) where η t = α δ + t s=1 ∥∇g s (y s )∥ 2 , α, δ > 0 5:Conduct a projection onto Yy i t+1 = y i t+1 , if ∥ y i t+1 ∥ ≤ D, y i t+1 • D ∥ y it+1 ∥ , otherwise . 6: end for A.5 Smooth and strongly convex online gradient descent Recall that to exploit smoothness, we enhance the expert-loss for strongly convex functions as followsℓ sc t, λ (y) = ⟨∇g t (y t ), y -y t ⟩ + λ 2G 2 ∥∇g t (y t )∥ 2 ∥y -x t ∥ 2 .The above expert-loss enjoys the following property.Lemma 7 Under Assumptions 1 and 2, ℓ sc t, λ (•) in (28) is λ G 2 ∥∇g t (y t )∥ 2 -strongly convex, and∥ ℓ sc t, λ (y)∥ 2 ≤ 1 + 2D G 2 ∥∇g t (y t )∥ 2 .Due to the modulus of strong convexity is not fixed, we choose Smooth and Strongly Convex OGD (S 2 OGD) as the expert-algorithm [Wang et al., 2020b] to minimize ℓ sc t, λ (•). The procedure is summarized in Algorithm 7. (y i s )∥ 2 , α, δ > 0 5:Conduct a projection onto Yy i t+1 = y i t+1 , if ∥ y i t+1 ∥ ≤ D, y i t+1 • D ∥ y i t+1 ∥ , otherwise . 6: end forIn this section, we provide the proofs of the theorems presented in the main paper (Theorem 1 and Theorem 2), as well as proofs of two important lemmas (Lemma 3 and Lemma 8).We present the exact bounds of the theoretical guarantee provided in Theorem 1. When functions are general convex, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + 2ΓGD ln |A| + 2D 2 + G 2 √ T - G 2 2 = O( √ T )where |A| = 1 + 2⌈log 2 T ⌉ andEQUATIONWhen functions are α-exp-concave, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 β ln |A| + 5 8 β + 2 √ 2GD d log T = O d α log T .When functions are λ-strongly convex, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 G 2 min{ G D , λ} ln |A| + (G + D) 2 λ log T = O 1 λ log T .We introduce the following decomposition for general convex functions, EQUATIONEQUATIONFirst, we start with the expert-regret. Since we are employing OGD to minimize ℓ cvx t (•), using standard OGD analysis [Zinkevich, 2003, Theorem 1 ] can obtain the following upper boundEQUATIONfor any expert y i t ∈ Y and any x ∈ X . Next, we move to bound the meta-regret. According to (48), we haveEQUATIONfor all expert E i ∈ A, where Γ is defined in (30) and the last set is due toEQUATIONFinally, substituting (32) and ( 33) into (31), we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + 2ΓGD ln |A| + 2D 2 + G 2 √ T - G 2 2 .For α-exp-concave functions, there exits α * ∈ P exp that α * ≤ α ≤ 2 α * , where α * is the modulus of the i-th expert E i . This inequality also indicatesβ * ≤ β ≤ 2 β * , β * = 1 2 min{ 1 4GD , α * }. (35) Since x -β * 2 x 2 is strictly increasing where β * = 1 2 min{ 1 4GD , α * } when x ∈ (-∞, 2GD], (9) implies that ⟨∇f t (x t ), x t -x⟩ - β * 2 ⟨∇f t (x t ), x t -x⟩ 2 ≤ ⟨∇g t (y t ), y t -x⟩ - β * 2 ⟨∇g t (y t ), y t -x⟩ 2 . (36)Then, we introduce the following decomposition for α-exp-concave functions,EQUATION)For the expert-regret, we can use the analysis of ONS [Hazan et al., 2007, Theorem 2 ] to obtainT t=1 ℓ exp t, α * (y i t ) - T t=1 ℓ exp t, α * (x) ≤ 5 4 β * + 2 √ 2GD d log T (38)for any expert y i t ∈ Y and any x ∈ X , where β * is defined in (35). Next, we move to bound the meta-regret. According to (48), we haveEQUATIONfor all expert E i ∈ A, where Γ is defined in (30) and the last step is due to 38) and ( 39) into (37), we have√ ab ≤ a 2 + b 2 . Substituting (T t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 2 β * ln |A| + 5 4 β * + 2 √ 2GD d log T.Finally, we use (35) to simplify the above bound.For λ-strongly convex functions, there exits λ * ∈ P sc that λ * ≤ λ ≤ 2 λ * , where λ * is the modulus of the i-th expert E i . Then, we introduce the following decomposition for λ-strongly convex functionsEQUATIONwhere∆ T = T t=1 1 {⟨∇ft(xt),vt⟩≥0} • ⟨∇f t (x t ), y t -x t ⟩.To bound the meta-regret, we derive the following theoretical guarantee.Lemma 8 Under Assumptions 1 and 2, the meta-regret of Algorithm 2 satisfiesT t=1 ⟨∇g t (y t ), y t -y i t ⟩ ≤ 8ΓGD + Γ ln |A| 16G 2 D 2 + T t=1 ⟨∇g t (y t ), y t -y i t ⟩ 2 ≤4ΓGD 2 + 1 ln |A| + Γ 2 G 2 2γ ln |A| + γ 2G 2 T t=1 ⟨∇g t (y t ), x t -y i t ⟩ 2 + ∆ T for any γ ∈ (0, G 2D ], where ∆ T = T t=1 1 {⟨∇ft(xt),vt⟩≥0} • ⟨∇f t (x t ), y t -x t ⟩ and Γ is in (30). Remark 6 As mentioned in Section 3.2, Lemma 8 is pivotal in delivering optimal regret for strongly convex functions. Specifically, when the meta-algorithm enjoys a second-order bound in terms of the surrogate loss in (8), we can then convert the intermediate decision y t in the meta-regret bound to the actual one x t , at the cost of adding an addition positive term, as presented in the analysis in (23). ◁ Combining Lemma 8 with (40) , we haveEQUATIONwhere ER(T ) = T t=1 (ℓ sc t, λ * (y i t ) -ℓ sc t, λ * (x)) and the last step is because we set γ = min{ G 2D , λ * }. Next, we bound the expert-regret [Shalev-Shwartz et al., 2011, Lemma 1 ]EQUATION)for any expert y i t ∈ Y and any x ∈ X . Substituting ( 42) into (41), we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 G 2 2γ ln |A| + (G + D) 2 2 λ * log T.Finally, we use λ * ≤ λ ≤ 2 λ * to simplify the above bound.According to (8), the (sub-)gradients of g t (•) can be formulated as Moreover, we derive the following equationEQUATION) (i) When ⟨∇f t (x t ), v t ⟩ ≥ 0.EQUATIONFinally, combining ( 44) and ( 46) obtains ( 20), further combining ( 45) and ( 47) yields (21).By the regret guarantee of Adapt-ML-Prod [Gaillard et al., 2014, Corollary 4] , we haveT t=1 ℓ t -ℓ i t ≤ 2Γ + Γ ln |A| 1 + T t=1 ℓ t -ℓ i t 2for all expert E i ∈ A, where Γ = 3 ln |A| + ln(1 + |A| 2e (1 + ln(T + 1))) = O(log log T ). By the definition of ℓ t and ℓ i t , we haveEQUATION)for any γ > 0, where the last step uses AM-GM inequality.Next, we handle the term ⟨∇g t (y t ), y t -y i t ⟩ 2 . We will consider two cases separately. (i) When ⟨∇f t (x t ), v t ⟩ ≥ 0 , we haveEQUATION)As the function q(x) = x -γ 2G 2 x 2 is strictly increasing when x ∈ (-∞, G 2 γ ], (49) implies that ⟨∇f t (x t ), x t -y i t ⟩ - γ 2G 2 ⟨∇f t (x t ), x t -y i t ⟩ 2 ≤ ⟨∇f t (x t ), y t -y i t ⟩ - γ 2G 2 ⟨∇f t (x t ), y t -y i t ⟩ 2 .for any γ ∈ (0, G 2D ]. By rearranging terms, we obtain γ 2G 2 ⟨∇g t (y t ), y t -EQUATIONEQUATION)Combining ( 50) and ( 51), we have γ 2G 2 ⟨∇g t (y t ), y t - 52) into ( 48), we finish the proof.y i t ⟩ 2 ≤ 1 {⟨∇ft(xt),vt⟩≥0} ⟨∇f t (x t ), y t -x t ⟩ + γ 2G 2 ⟨∇g t (y t ), x t -y i t ⟩ 2 (52) for any γ ∈ (0, G 2D ]. Substituting (The analysis is similar to Theorem 1. Also, we present the exact bounds of the theoretical guarantee provided in Theorem 2. When functions are general convex, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + √ 2D 2 δ + 4H 2ΓD ln |A| + √ 2(D + 2G) 2 + 2 √ H 2ΓD ln |A| + √ 2(D + 2G) L T + 4ΓGD 2 + 1 ln |A| + √ 2D 2 δ = O( L T ).where |A| = 1 + 2⌈log 2 T ⌉, Γ is defined in (30), and L T = min x∈X T t=1 f t (x). When functions are α-exp-concave, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 2β ln |A| + 2d β log β 2 D 2 H d T t=1 f t (x t ) + 1 + 2 β ≤ Γ + 2d β log 2β 2 D 2 H d T t=1 f t (x) + 2β 2 D 2 H d Γ + 2D 2 H log(2D 2 H) + 2 = O d α log L T where Γ = 4ΓGD 2 + 1 √ ln |A| + Γ 2 2β ln |A| + 2 β .When functions are λ-strongly convex, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤ Γ + (G + 2D) 2 2λ log 8Hλ (G + 2D) 2 T t=1 f t (x) + 8Hλ (G + 2D) 2 Γ + 2H log(2H) + 2 = O 1 λ log L T where Γ = 4ΓGD 2 + 1 √ ln |A| + Γ 2 G 2 2γ ln |A| + 1.We start with the meta-expert regret decomposition as presented in (31),EQUATION)For the meta-regret, we reuse (33) to obtainT t=1 ⟨∇g t (y t ), y t -y i t ⟩ ≤ 4ΓGD 2 + 1 ln |A| + Γ ln |A| T t=1 ∥∇g t (y t )∥ 2 ∥y t -y i t ∥ 2 ≤ 4ΓGD 2 + 1 ln |A| + 2ΓD ln |A| T t=1 ∥∇g t (y t )∥ 2 ,(54) for all expert E i ∈ A, where Γ is defined in (30). For the expert-regret, we can use the analysis of SOGD [Zhang et al., 2019, Theorem 2 ] to obtainT t=1 ℓ cvx t (y i t ) - T t=1 ℓ cvx t (x) ≤ √ 2D 2 δ + 1 + 2G D 2 T t=1 ∥∇g t (y t )∥ 2 .for any expert y i t ∈ Y and any x ∈ X . From the above formulation, we haveEQUATION)Substituting ( 54) and ( 55) into (53), we haveT t=1 f t (x t ) - T t=1 f t (x) (34) ≤ 4ΓGD 2 + 1 ln |A| + √ 2D 2 δ + 2ΓD ln |A| + √ 2(D + 2G) T t=1 ∥∇f t (x t )∥ 2 .Next, we introduce the self-bounding property of smooth functions.Lemma 9 (Lemma 3.1 of Srebro et al. [2010] ) For an H-smooth and nonnegative function, we have ∥∇f (x)∥ ≤ 4Hf (x).Thus, when functions are smooth, we haveT t=1 f t (x t ) - T t=1 f t (x) (34) ≤ 4ΓGD 2 + 1 ln |A| + √ 2D 2 δ + 2ΓD ln |A| + √ 2(D + 2G) 4H T t=1 f t (x t ).To simplify the above inequality, we use the following lemma.Lemma 10 (Lemma 19 of Shalev-Shwartz [2007] ) Let x, b, c ∈ R + . Then, we havex -c ≤ b √ x ⇒ x -c ≤ b 2 + b √ c.By utilizing Lemma 10, we finish the proof.The analysis is also similar to Theorem 1. We start with (37)EQUATION)For the meta-regret, we also use (39) to bound. For the expert-regret, we can use the analysis of ONS under the smoothness condition [Orabona et al., 2012 , Theorem 1] to getT t=1 ℓ exp t, α (y i t ) - T t=1 ℓ exp t, α (x) ≤ 2d β * log β * 2 D 2 16d T t=1 ∥∇ℓ exp t, α (y i t )∥ 2 + 1 + 2 β * .for any expert y i t ∈ Y and any x ∈ X . Next, we provide an upper bound for∥∇ℓ exp t, α (y i t )∥ 2 ∥∇ℓ exp t, α (y i t )∥ 2 = ⟨∇g t (y t ) + β * ∇g t (y t )∇g t (y t ) ⊤ (y -y t ), ∇g t (y t ) + β * ∇g t (y t )∇g t (y t ) ⊤ (y -y t )⟩ = ∥∇g t (y t )∥ 2 + 2 β * ⟨∇g t (y t ), y -y t ⟩∥∇g t (y t )∥ 2 + β * 2 ∥∇g t (y t )∥ 4 ∥y -y t ∥ 2 ≤ 1 + 2 β * 2 GD 2 ∥∇g t (y t )∥ 2 ≤ 4∥∇g t (y t )∥ 2 .Thus, we haveEQUATIONSubstituting ( 39) and ( 57) into (56), we haveEQUATIONwhere the last step is due to Lemma 9. Finally, we use the following lemma to simplify the bound.Lemma 11 (Corollary 5 of Orabona et al. [2012] ) Let a, b, c, d, x > 0 satisfy x-d ≤ a ln(bx+c).Then, we have x -d ≤ a ln(2(ab ln 2ab e + db + c)).Recall that we construct the expert-loss for strongly convex functions as followsℓ sc t, λ (y) = ⟨∇g t (y t ), y -y t ⟩ + λ * 2G 2 ∥∇g t (y t )∥ 2 ∥y -x t ∥ 2 .Then, we introduce a new decomposition for λ-strongly convex functionsT t=1 f t (x t ) - T t=1 f t (x) ≤ T t=1 ⟨∇f t (x t ), x t -x⟩ - λ 2 T t=1 ∥x t -x∥ 2 ≤ T t=1 ⟨∇f t (x t ), x t -x⟩ - λ * 2 T t=1 ∥x t -x∥ 2 ≤ T t=1 ⟨∇f t (x t ), x t -x⟩ - λ * 2G 2 T t=1 ∥∇g t (y t )∥ 2 ∥x t -x∥ 2 (20) ≤ T t=1 ⟨∇g t (y t ), y t -x⟩ -∆ T - λ * 2G 2 T t=1 ∥∇g t (y t )∥ 2 ∥x t -x∥ 2 (28) = T t=1 ⟨∇g t (y t ), y t -y i t ⟩ meta-regret + T t=1 ℓ sc t, λ * (y i t ) -ℓ sc t, λ * (x) expert-regret - λ * 2G 2 T t=1 ∥∇g t (y t )∥ 2 ∥x t -y i t ∥ 2 -∆ T (59) where ∆ T = T t=1 1 {⟨∇ft(xt),vt⟩≥0} • ⟨∇f t (x t ), y t -x t ⟩.To bound the meta-regret, we still incorporate with Lemma 8 to getT t=1 f t (x t ) - T t=1 f t (x) ≤ 4ΓGD 2 + 1 ln |A| + Γ 2 G 2 2γ ln |A| + T t=1 ℓ sc t, λ * (y i t ) -ℓ sc t, λ * (x) .For the expert-regret, we derive a variant of theoretical guarantee of S 2 OGD.Lemma 12 Under Assumptions 1 and 2, for any expert y i t ∈ Y and any x ∈ X , we haveT t=1 ℓ sc t, λ * (y i t ) - T t=1 ℓ sc t, λ * (x) ≤ 1 + (G + 2D) 2 2 λ * log λ * (G + 2D) 2 T t=1 ∥∇g t (y t )∥ 2 + 1Combining the above bounds, we haveT t=1 f t (x t ) - T t=1 f t (x) ≤4ΓGD 2 + 1 ln |A| + Γ 2 G 2 2γ ln |A| + 1 + (G + 2D) 2 2 λ * log 4H λ * (G + 2D) 2 T t=1 f t (x) + 1 .Finally, we simplify the above bound by utilizing Lemma 11.According to the definition of ℓ exp t, α (•) in (25), we have ∇ℓ exp t, α (y) = ∇g t (y t ) + β∇g t (y t )∇g t (y t ) ⊤ (y -y t ). Thus, for all y ∈ Y, it holds thatEQUATIONwhere ∇ 2 ℓ exp t, α (y) denotes the Hessian matrix of ℓ exp t, α (y) and the last inequality is due to a, and the definition of β. Therefore, ℓ exp t, α (•) is β 4 -exp-concave [Hazan, 2016, Lemma 4.1] . Next, we provide the upper bound of the gradient of ℓ exp t, α (•) as follows∥∇ℓ exp t, α (y)∥ 2 (34) ≤ (G + 2 βG 2 D) 2 ≤ 25 16 G 2 ≤ 2G 2 .This ends the proof.According to the definition of ℓ sc t (•) in ( 14), it holds for any x, y ∈ X thatℓ sc t (x) ≥ ℓ sc t (y) + ⟨∇ℓ sc t (y), x -y⟩ + λ 2 ∥x -y∥ 2 .By Definition 1, it can be seen that ℓ sc t (•) is λ-strongly convex. Next, we provide the upper bound of the gradient of ℓ sc t (•) as follows∥∇ℓ sc t (y)∥ 2 ≤ ∥∇g t (y t ) + λ(y -x t )∥ 2 (34) ≤ (G + 2λD) 2 ≤ (G + 2D) 2where the last step is due to our assumption that λ ∈ [1/T, 1].Similar to analysis of Lemma 6, for any x, y ∈ X , we haveℓ sc t, λ (x) ≥ ℓ sc t, λ (y) + ⟨∇ℓ sc t, λ (y), x -y⟩ + λ 2G 2 ∥∇g t (y t )∥ 2 ∥x -y∥ 2 By Definition 1, it is established that ℓ sc t, λ (•) is λ G 2 ∥∇g t (y t )∥ 2 -strongly convex.Next, we upper bound the gradient of ℓ sc t, λ (•) as follows∥ℓ sc t, λ (y)∥ 2 ≤ ∇g t (y t ) + λ G 2 ∥∇g t (y t )∥ 2 (y -x t ), ∇g t (y t ) + λ G 2 ∥∇g t (y t )∥ 2 (y -x t ) = ∥∇g t (y t )∥ 2 + 2 λ G 2 ∥∇g t (y t )∥ 2 ⟨∇g t (y t ), y -x t ⟩ + λ 2 G 4 ∥∇g t (y t )∥ 4 ∥y -x t ∥ 2 (34) ≤ 1 + 2 λD G 2 ∥∇g t (y t )∥ 2 ≤ 1 + 2D G 2 ∥∇g t (y t )∥ 2where the last step is due to our assumption that λ ∈ [1/T, 1].The analysis is similar to Wang et al. [2020b] . Let y i t+1 = y i t -1 ηt ∇ℓ sc t, α (y i t ). According to the definition of (28), we haveℓ sc t,k (y i t ) -ℓ sc t,k (x) ≤ ⟨∇ℓ sc t,k (y i t ), y i t -x⟩ - λ 2G 2 ∥∇g t (y t )∥ 2 ∥y i t -x∥ 2 = η t ⟨y i t -y i t+1 , y i t -x⟩ - λ 2G 2 ∥∇g t (y t )∥ 2 ∥y i t -x∥ 2 .For the first term, it can be verified that⟨y i t -y i t+1 , y i t -x⟩ = ∥y i t -x∥ 2 + ⟨x -y i t+1 , y i t -x⟩ = ∥y i t -x∥ 2 -∥ y i t+1 -x∥ 2 -⟨y i t -y i t+1 , y i t+1 -x⟩ = ∥y i t -x∥ 2 -∥ y i t+1 -x∥ 2 + ∥ y i t+1 -y i t ∥ 2 + ⟨ y i t+1 -y i t , y i t -x⟩ which implies that ⟨y i t -y i t+1 , y i t -x⟩ = 1 2 ∥y i t -x∥ 2 -∥ y i t+1 -x∥ 2 + ∥ y i t+1 -y i t ∥ 2 .Thus,ℓ sc t,k (y i t ) -ℓ sc t,k (w) ≤ η t 2 ∥y i t -x∥ 2 -∥ y i t+1 -x∥ 2 + 1 2η t ∥∇ℓ sc t, α (y i t )∥ 2 - λ 2G 2 ∥∇g t (y t )∥ 2 ∥y i t -x∥ 2 .Summing the above bound up over t = 1 to T , we attainT t=1 ℓ sc t, α (y i t ) - T t=1 ℓ sc t, α (x) ≤ η 1 2 ∥y i 1 -x∥ 2 + T t=1 η t -η t-1 - λ G 2 ∥∇g t (y t )∥ 2 ∥y i t -x∥ 2 2 + T t=1 1 2η t ∥∇ℓ sc t, α (y i t )∥ 2 ≤1 + T t=1 1 2η t ∥∇ℓ sc t, λ (y i t )∥ 2 ≤ 1 + (G + 2D) 2 2 λ T t=1 ∥∇g t (y t )∥ 2 (G + 2D) 2 / λ + t i=1 ∥∇g i (y i )∥ 2 .where the last two inequalities is due toη t = (1 + 2D/G) 2 + λ G 2 t i=1 ∥∇g i (y i )∥ 2which is specifically set for new expert-loss. Further, we will use the following lemma to bound the last term.Lemma 13 (Lemma 11 of Hazan et al. [2007] ) Let l 1 ,• • • ,l T and δ be non-negative real numbers. Then, we haveT t=1 l 2 t t i=1 l 2 i +δ ≤ log 1 δ T t=1 l 2 t + 1 .This completes the proof of Lemma 12.The analysis is similar to Mhammedi et al. [2019, Lemma 9] . When ∥ y i t+1 ∥ ≥ D, then we need to solve the following quadratic problem:y i t+1 = arg min y∈Y ( y i t+1 -y) ⊤ Σ t+1 ( y i t+1 -y).We use the Lagrangian multiplier to solve the above problemL(y, µ) = ( y i t+1 -y) ⊤ Σ t+1 ( y i t+1 -y) + µ(y ⊤ y -D 2 ).We set ∂L ∂y = 0 to attain Σ t+1 (y -y i t+1 ) + µy = 0, which impliesy = (µI d + Σ t+1 ) -1 Σ t+1 y i t+1 = Q ⊤ t+1 (xI + Λ t+1 ) -1 Q t+1 Σ t+1 y i t+1 where x = µ + 1/( β 2 D 2 ). Due to y ⊤ y = D 2 , x is the solution of the following problem ρ(x) := d k=1 ⟨e k , Q t+1 Σ t+1 y i t+1 ⟩ 2 (x + λ k t ) 2 = D 2 .In this section, we explain that bounded moduli are generally acceptable in practical scenarios, which is also stated in previous study [Zhang et al., 2022] . Taking λ-strongly convex functions as an example, we assume that λ ∈ [1/T, 1], since other cases that λ < 1/T and λ > 1 can be disregarded. (i) If λ < 1/T , the regret bound for strongly convex functions becomes Ω(T ), which cannot benefit from strong convexity. Therefore, we should treat these functions as general convex functions. (ii) If λ > 1, λ-strongly convex functions are also 1-strongly convex according to Definition 1. Thus, we can treat these functions as 1-strongly convex functions. In this section, we conduct empirical experiments to validate the effectiveness of our proposed methods, and present the details of experiments.We conduct experiments on the ijcnn1 dataset from LIBSVM Data [Chang and Lin, 2011, Prokhorov, 2001] , where the dimension of features is d = 22. We consider the following online classification problem. In each round t ∈ [T ], the online learner chooses a decision x t ∈ X . After submitting the decision, the online learner receives a batch of data samples {(xEQUATIONt )} m i=1 which are sampled from the dataset, where x (i) t is the feature vector of the i-th sample, and y (i) t is the corresponding label. The learner can evaluate the model by the online convex loss f t (x t ) and update the decision for the next round. In our study, we set T = 2000, the domain diameter as D = 20, and the gradient norm upper bound as G = √ 22. Following the general setup of Zhao et al. [2022] , we set the feasible domain to be an ellipsoidX = {x ∈ R d | x ⊤ Ex ≤ λ min (E) • (D/2) 2 }, where E is a certain diagonal matrix and λ min (E) denotes its minimum eigenvalue. We remark that the cost of one projection onto X is generally expensive since it requires solving a convex programming.In the following, we consider three types of online convex functions to simulate the unknown environment and demonstrate the universality of our method. First, for exp-concave functions, the online learner suffers a logistic loss:f t (x t ) = 1 m m i=1 log 1 + exp(-y (i) t x ⊤ t x (i) t ). Second, for strongly convex functions, we choose the regularized hinge loss:f t (x t ) = 1 m m i=1 max 0, 1 -y (i) t x ⊤ t x (i) t + λ 2 ∥x t ∥ 2 .Third, for general convex functions, the online learner suffers the absolute loss:f t (x t ) = 1 m m i=1 x ⊤ t x (i) t -y (i)t . Based on the above experimental settings, we conduct the empirical studies of our method, as well as other universal algorithms in the literature.Algorithms We compare the performance of our proposed method for minimax universal regret with existing universal algorithms, including MetaGrad [van Erven and Koolen, 2016] , Maler [Wang et al., 2019] , efficient implementation of MetaGrad [Mhammedi et al., 2019] , and USC [Zhang et al., 2022] . All the baselines share the same experimental setting as our method.Table 2 : A summary of state-of-the-art projection-free algorithms for different types of convex functions.Condition on Loss Regret Bound OFW [Hazan and Kale, 2012] convex O(T 3/4 ) OSPF [Hazan and Minasyan, 2020] convex and smooth O(T 2/3 ) SC-OFW [Wan and Zhang, 2021] strongly convex O(T 2/3 ) AFP-ONS [Garber and Kretzu, 2023] exp-concave and smooth O(T 2/3 )We repeat the experiments for five times and record the results in Figure 1 . We conduct the experiments on a machine with a single CPU (Apple M1 pro) and 16GB memory. We record both regret and running time (in seconds) for all methods. As shown in Figure 1 , the running time of our method is comparable to that of EffMetaGrad, yet it achieves better results for strongly convex functions. Compared to other algorithms which conduct O(log T ) projections, i.e., USC, Maler, and MetaGrad, the running time of our projection-efficient method is 5 to 20 times faster, and it also attains nearly optimal regret for three types of convex functions. In conclusion, the empirical results demonstrate the effectiveness of our method in achieving optimal regret guarantee and also significant enhancement in computational efficiency.In the literature, there exists a class of projection-free algorithms [Hazan and Kale, 2012 , Hazan and Minasyan, 2020 , Wan and Zhang, 2021 , Wan et al., 2021b , 2022 , Wang et al., 2023 , Garber and Kretzu, 2023] . Therefore, it is natural to ask whether projection-free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS to remove all projections while still being adaptive to the smoothness. Here, we provide some targeted discussions on this matter.In fact, we can choose projection-free algorithms as the expert-algorithms. However, given the current studies on projection-free algorithms, this approach will lead to a deterioration of the regret bound and can not handle certain cases. As is shown in Table 2 , in the literature, there are no suitable projection-free algorithms for exp-concave functions, neither for strongly convex and smooth functions. Moreover, when functions are smooth, existing projection-free algorithms are unable to achieve problem-dependent bounds, such as the small-loss bounds in this work.Finally, we would like to highlight that although using projection-free algorithms can remove all projections, they may not achieve greater efficiency based on the universal framework. Specifically, most projection-free algorithms, such as OFW and its variants, replace the original projection operation with a linear optimization step. Since the universal framework requires maintaining O(log T ) expert-algorithms, this approach needs to perform O(log T ) linear optimization steps per round, which can be time-consuming when T is large.Answer Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).One can verify the degenerated situations where the unknown modulus falls outside the range, which will not be a concern. Formal justifications are provided in Appendix D. 


Decision: The paper considers the problem of handling various function classes like convex, exp-concave and strongly convex via 1 algorithm. This sub-area called universal algorithms has been studied significantly in literature. The typical solutions are running log T experts at different learning rates. The default such solution requires log T projections,1 for each expert. This was resolved by Mhammedi et al who gave an algorithm with 1 projection. That algorithm gets the right rate for convex and exp concave but misses the right rate for strongly convex suffering an additional d factor. This is the rate that this paper improves. They do so by changing the problem to the domain of a sphere via a construction by Cutkosky and Orabona. 

The paper is pretty well written and as the reviewers point out it lays out the results and the techniques pretty well. Overall the paper makes somewhat of a niche theoretical improvement in my opinion (shared by other reviewers), which is not very surprising. However since the reviewers have given a high score to the paper I am recommending acceptance.

Reviews: review: paper_summary: paper_summary: This paper studies universal OCO algorithms with fewer projections. Previous work either use $O(\log T)$ projections per round, or have a sub-optimal dependence on $d$ for strongly-convex loss. This work designs a new surrogate loss to achieve tight regret for Lipschitz convex/exp-concave/strongly-convex losses simultaneously, with only 1 projection per round.
strength_weakness: strength_weakness: The contribution seems somewhat incremental to me. The only improvement is a $d$ factor for strongly-convex loss. Such result is nice to know but I'm not sure how significant such it is. In addition, the technical novelty isn't significant either.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This paper addresses the challenge of online convex optimization with unknown smoothness properties of the loss functions, which can be convex, strongly convex, or exp-concave. The authors propose an algorithm that achieves regret bounds of order $\sqrt{T}$, $\log T$, and $d \log T$ respectively, while requiring only a single projection step per round on the original domain $\mathcal{X}$. Such projections can indeed be computationally expensive. Additionally, the authors present regret bounds with improvment for small losses.

Most algorithms that achieve similar adaptive regret upper bounds rely on meta-algorithms that combine experts (running ONS or OGD with surrogate losses), inspired by the MetaGrad algorithm. Typically, these algorithms necessitate $\log(T)$ projection steps per round (one per expert), which can be computationally burdensome. Mhammedi et al. (2019) reduced this projection cost to $O(1)$ but at the expense of a $d \log T$ regret for strongly convex losses. To overcome this, the authors introduce new surrogate losses based on a black-box reduction technique by Cutkosky et al. (2018), which simplifies the constrained optimization problem on $\mathcal{X}$ to another domain, such as the Euclidean ball, where projections are easier.
strength_weakness: strength_weakness: - The theoretical improvements may appear incremental, appealing to a niche audience interested. The improvement being only in the specific case of strongly convex $\log T$ regret with $O(1)$ projection steps. The primary high-level ideas in the algorithm and analysis are based on prior work.
- The paper still relies on a meta-aggregation procedure, which, although theoretically effective, is not particularly elegant and maintains a per-round complexity of order $O(\log T)$. Achieving $O(1)$ complexity per round seems however highly challenging.
- The convex rate is actually $O(\sqrt{T \log\log T})$, not $O(\sqrt{T})$ as stated in the results.
questions: questions: - The algorithm requires prior knowledge of the parameters $G$ and $T$, would simple doubling trick allow to tune these?
- Your algorithm still requires O(1) projection steps on $\mathcal{X}$ and O(log T) projection steps on $\mathcal{Y}$. Do you think that projection free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS (up to deteriorating slightly the rate) to remove all projections (or at least the O(log T) on $\mathcal{Y}$) while still being adaptive to the smoothness?
limitations: limitations: The authors have addressed the limitations.
paper_summary: paper_summary: This paper introduces methods for constrained OCO
which automatically achieve the optimal rate without knowing
in advance whether the losses are convex, strongly convex,
exp-concave, or smooth, while using only 1 projection per round.
This is notable because the standard approach proceeds by combining
several expert algorithms with a meta algorithm; in constrained settings
these expert algorithms require implementing a potentially expensive
projection. This work avoids projecting each of the expert algorithm
iterates leveraging the constrained-to-unconstrained reduction of Cutkosky 2020.
strength_weakness: strength_weakness: The main weakness is that the paper feels poorly factored. There is
a very large number of back references to previous equations, and the paper would be
very hard to read in print. To actually follow the math, it's almost necessary to
read the paper with a pdf viewer which can display pop-up previews when hovering over links.
I think this would be remedied by better factoring the results into lemmas and propositions.

As noted, the approach is a fairly straight-forward modification of the results from
Cutkosky \& Orabona (2018) and  Cutkosky (2020), and essentially boils down to
not dropping negative terms in the analysis, and then exposing matching terms
in the regret decomposition. I think this is fine overall; these considerations
are missing from the literature, and this is a fitting
place for them to enter the literature.
questions: questions: Do you think there could possibly be a more abstract way to formalize these universal algorithms? The strange thing about these universal algorithms is that a whole new algorithm seemingly needs to be devised every time one wants to incorporate a new kind of loss (e.g. meta-grad -> mahler to handle strongly convex losses). The ideal result would more generally be a reduction which just passes the losses to each of the experts, maybe with some additional side-information, and lets them construct whatever surrogate loss they want with it. In this way there might just be one "final" paper on universal guarantees.
limitations: limitations: Yes, the paper points out in the conclusion that the bounded domain / gradient assumption is
a significant limitation that they hope to address in future work.

Comments: comment: Dear Reviewer aw3E,

Thank you very much for your kind reply! We will further improve our paper. 

Best regards, 

Authors
Thank you for your response. This addresses some of the points I raised. I have no further questions and will await the discussion with the other reviewers.
Thank you for your detailed response! 

Given that optimal dependence on $d,T$ is already known for each sub-case, the $d$ dependence improvement is on how we aggregate them to build universal algorithms. In my opinion, such $d$ dependence improvement is not as significant because the study of universal algorithms mostly remains on theory level so far: how useful universal algorithms are practically is in question, there seems much fewer scenarios that crucially require universal algorithms than those of each sub-case.

As a result, I will maintain my score.
Dear Reviewer VeB9,

Many thanks for your kind reply! We will further enhance our paper according to your constructive reviews. 

Best regards,

Authors
Great! Thanks for the detailed explanation of Zhang 2022, this does indeed seem to be the kind of result I was hoping for

I believe the authors will be able to factor the results and polish the writing between now and the camera-ready. I think these are important results and the approach is quite nice, so I've raised my score to a 7.