Online Composite Optimization Between Stochastic and Adversarial Environments
Authors: Yibo Wang
Sijia Chen
Wei Jiang
Wenhao Yang
Yuanyu Wan
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Composite Optimization
Online Learning
Primary area: online_learning

Abstract: We study online composite optimization under the Stochastically Extended Adversarial (SEA) model. Specifically, each loss function consists of two parts: a fixed non-smooth and convex regularizer, and a time-varying function which can be chosen either stochastically, adversarially, or in a manner that interpolates between the two extremes. In this setting, we show that for smooth and convex time-varying functions, optimistic composite mirror descent (OptCMD) can obtain an $\mathcal{O}(\sqrt{\sigma_{1:T}^2} + \sqrt{\Sigma_{1:T}^2})$ regret bound, where $\sigma_{1:T}^2$ and $\Sigma_{1:T}^2$ denote the cumulative stochastic variance and the cumulative adversarial variation of time-varying functions, respectively. For smooth and strongly convex time-varying functions, we establish an $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2)\log(\sigma_{1:T}^2 + \Sigma_{1:T}^2))$ regret bound, where $\sigma_{\max}^2$ and $\Sigma_{\max}^2$ denote the maximal stochastic variance and the maximal adversarial variation, respectively. For smooth and exp-concave time-varying functions, we achieve an $\mathcal{O}(d \log (\sigma_{1:T}^2 + \Sigma_{1:T}^2))$ bound where $d$ denotes the dimensionality. Moreover, to deal with the unknown function type in practical problems, we propose a multi-level \textit{universal} algorithm that is able to achieve the desirable bounds for three types of time-varying functions simultaneously. It should be noticed that all our findings match existing bounds for the SEA model without the regularizer, which implies that there is \textit{no price} in regret bounds for the benefits gained from the regularizer.

Online Composite Optimization Between Stochastic and Adversarial Environments
Yibo Wang Sijia Chen' Wei Jiang', Wenhao Yang Yuanyu Wan Lijun Zhang 122
'National Key Laboratory for Novel Software Technology. Nanjing University, Nanjing, China
School of Artificial Intelligence, Nanjing University, Nanjing, China 'School of Software Technology, Zhejiang University, Ningbo, China (wangyb, chensj, jiangu, yangwh, zhanglj @1addaaaa.m.m.mmm nju. edu. cn, wanyy0zju. edu.
Abstract
We study online composite optimization under the Stochastically Extended Ad- versarial (SEA) model. Specifically, each loss function consists of two parts: a fixed non-smooth and convex regularizer, and time-varying function which can be chosen either stochastically, adversarially, or in a manner that interpolates be- tween the two extremes. In this setting, we show that for smooth and convex time-varying functions, optimistic composite mirror descent (OptCMD) can obtain an O(vorr /ETTT) regret bound, where oi.r and >7.7 denote the cumulative stochastic variance and the cumulative adversarial variation of time-varying func- tions, respectively, For smooth and strongly convex time-varying functions, we establish an O((o max + Emax) log(o E):r) regret bound, where o and E2 Emax denote the maximal stochastic variance and the maximal adversarial varia- tion, respectively. For smooth and exp-concave time-varying functions, we achieve an (d log (oF. + )) bound where d denotes the dimensionality. Moreover, deal with the unknown function type in practical problems, we propose a multi- level universal algorithm that is able to achieve the desirable bounds for three types of time-varying functions simultancously. It should be noticed that all our findings match existing bounds for the SEA model without the regularizer, which implies that there is no price in regret bounds for the benefits gained from the regularizer.
1
Introduction
Online composite optimization has drawn considerable attention in recent years (Duchi and Singer
2009 Ghadimi and Lan 2012 Lei and Zhou 2017, [Scroccaro et al., 2023]. Formally, it can be viewed as an iterative game between a learner and the environment. each round f, the learner makes a decision from convex set X' 1dd and then suffers loss de (xx)) in the form of
o (x) = f((x) + r(x).
where f((-) X' IR denotes the time-varying function that is chosen by the environment, and r()) X + I denotes the fixed non-smooth and convex regularizer, such as the L fn-norm for sparse
vectors and the trace norm for low-rank matrices [Langford al. 2009 Flammarion and Bach 2017
Zhang et al. 2019 Garber and Kaplan 2019]. In the literature, online composite optimization is generally divided into two categories: stochastic composite optimization [Lan] 2012 2016 Zhang
et al. 2017, Lei and Tang 2018 Lei et al. 2019 Kulunchakov and Mairal 2019 and adversarial
composite optimization Xiao| | Duchi et al. 2010, Mohri and Yangl 2016 Joulani et al. 2020
Yang et al. [2024c]. In the former one, fr(+) is assumed to be independent and identically distributed (i.i.d.) over time; in the latter one, fe(.) can chosen arbitrarily or even adversarially. However,
"Lijun Zhang is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the environment in real-world scenarios is seldom purely stochastic or adversarial. but rather falls somewhere in between [Amir al., 2020 Garber al. 2020 [Sherman et al. 2021 Zimmert and
Seeldnn 2021
Ito 2021 and our understanding for the more common intermediate scenarios remains
limited in online composite optimization.
Recently Sachs et al. [2022) introduce the Stochastically Extended Adversarial (SEA) model as an intermediate setting online optimization without regularizer, i.e., r(x) = 0. In the SEA model, loss functions are not restricted to fully i.i.d. or adversarial; instead, the environment selects them from any intermediate state between the two extreme settings. To reflect how stochastic or adversarial the environments are, they introduce the cumulative stochastic variance oi. and the cumulative adversarial variation Lirr as shown below:
o.r = Σ
1
and Eir = E
Σ
T
sup [VF((x - F V X
(2)
where of SuPxEX Ex.-D, V (x)
(x) denotes the variance of gradients and F.(x)
Bic-D [[](x] denotes the expected function for [e(.). For the SEA model, two classical algorithms
in optimistic online learning Rakhhlin and Sridharan [001) -
Besloo-Thh--egulaae
Leader (FTRL) [Sachs et al., 2022] and optimistic Online Mirror Descent (OMD) [Chen et al. 2023 have been proven ensuring sublinear regret bounds with respect to both of and i
In this paper, we extend the SEA model into online composite optimization, termed as composite SEA, to bridge the gap between stochastic and adversarial composite optimization. Specifically, in ① r() remains fixed over time and fc(-) is selected from a distribution D,, which is chosen by the environments either stochastically, adversarially, in manner that interpolates between the two extremes. The goal of composite SEA to minimize the expected regret in terms of (]:
E [Regrety] = E Σ T
[f((x)) + r(x:)] min xEX
Σ
(3)
which benchmarks the cumulative composite loss of the learner and that of the best fixed decision. To handle the composite setting, natural impulse is to treat fr(-) + +(-) as one function and directly apply existing methods for the SEA model, i.e., optimistic FTRL and optimistic OMD. However, such a straightforward application is unsuitable because (i) these methods heavily rely on the smoothness of loss functions, but due to the non- non-smooth component r(.), the summation function (be()) = fe(.)++())) +r(--) loses this crucial property; (ii) directly applying these methods ignores the presence of r(-) and thus fails to gain the benefits from the regularizer, e.g., the sparsity induced by the -noom.. Therefore, a natural question arises whether it is possible to deal with both the intermediate nature of environmentss and the composite structure of loss functions concurrently.
We affirmatively answer the above question by revisiting a variant of optimistic OMD Scroccaro al., 2023], named Optimistic Composite Mirror Descent (OpICMD). This method inherits the idea of optimistic online learning [Rakhlin and Sridharan 2013). i.e., exploiting estimates on upcoming loss functions for decision updates, and can disentangle f.)-) and r(.) during the optimization, thereby effectively leveraging distinct properties of each. However, OptCMD is originally designed for adversarial composite optimization, and a simple extension will lead to unsatisfactory bounds in composite SEA. In this paper, we reanalyze OptCMD and show that with suitable configurations, OpICMD attains O(Voi. + V O + > log(oī.7 + >):r)) and Old log(gg (o". Eir)) bounds for smooth and general convex, smooth and strongly convex, and smooth and exp- concave time-varying functions, respectively. Our findings generalize previous results stochastic and adversarial composite optimization, and can reduce to them by specializing of and E. Moreover, our results coincide with existing bounds for the SEA model [Sachs et al. 2022 Chen et al. 2023 which indicates that there is no price in regret bounds for the benefits from r(-).
One concern of OptCMD is the requirement of the function type in advance, which is often impractical in real-world problems and motivates us to design universal algorithm that is agnostic to the prior knowledge about loss functions. We note that recently, Yan et al. [2023] have introduced universal algorithm for the SEA model without regularizer, based on the meta-expert structure in online learning [van Erven and Koolen 2016 Mhammedi et al. 2019 Wang et al., 2019 Zhang et al. 2022) However, their method |Yan et al.) 2023 cannot naturally support the composite setting, as it highly depends on the smoothness of the (summation) loss functions, which does not necessarily hold the composite SEA model. In this paper, we propose novel universal algorithm for composite SEA,

---

based on the observations that (i) the regularizer remains fixed over time and is accessible to the meta-algorithm from the beginning round; (ii) the meta-algorithm is able obtain expert decisions for the current round before estimating their performance. With these two facts, we can utilize the information about r(.) to track experts, ensuring the meta-regret will not deviate from that of the best one. Specifically, inspired by Yan et al. [2023] we employ a two-layer Multi-scale Multiplicative- weight with Correction (MsMwC) [Chen et al. 2021] as the meta-algorithm. and choose OpICMD as the expert-algorithm. To effectively estimate the expert performance, we first collect decisions of each expert for the current round, and then explicitly integrate them and expert performance on r(-) into the losses and optimisms used in MsMwC. Theoretical analysis demonstrates that, with the proposed integration, our universal algorithm can achieve desirable bounds for three types of loss functions simultancously. We summarize contributions shown below.
We first introduce the composite SEA model, which serves as an intermediate setting between stochastic and adversarial composite optimization and can naturally adapt to two extreme settings; For the composite SEA model, we demonstrate that OptCMD can attain the regret bounds of +( O(
max + Emaxe) log(oi:> +X.)) and (d +(.r)) for smooth and general convex, smooth and strongly convex, and smooth and exp-concave time-varying functions, respectively. Owing to the versatility of oir and Ei.r, these bounds can recover previous results in stochastic and adversarial composite optimization;
Moreover, to handle the unknown function type, we propose a new universal algorithm in composite SEA and show that it can concurrently achieve desirable bounds for three kinds of functions; Finally, we discuss implications of our theoretical findings for two common intermediate examples with composite loss functions, and derive favorable bounds specific these practical scenarios.
2 Related work
In this section, we briefly review related work adversarial and stochastic composite optimization, the SEA model and universal online learning.
Adversarial composite optimization. In this setting, fe(-) is assumed to be chosen by the environ- ments arbitrarily or even adversarially, and the performance measured by regrer shown in brackets of 3 In the literature, the seminal work (Duchi and Singer 2009] proposes the FOBOS method with ((VT) and O log 7') regret bounds for general convex and X-strongly convex fc(-), re- spectively. Later, Xiao (2009) proposes the RDA method based on the primal-dual subgradient framework NNsterov 2009), and shows that RDA is able to generate sparser decisions than FOBOS
when rxx) = -||x|| for some > O. In the same time, another subsequent work (Duchi et al. 2010
introduces the COMID method under the mirror descent framework [Beck and Teboulle 2003 J. and
achieves the same bounds as FOBOS. Recently, for a-exp-concave (-). Yang et al. 2024cc establish
an ((d/aa) log T) regret bound by proposing the ProxONS method.
Besides, there exist other powerful methods (Yang et al.) 2014 Mohri and Yang 2016 Joulani et al., 20200, (Scooccaoo et al.] 2023) equipped with -eeeedddeeeeentt bounds. These bounds can safeguard the above results in the worst-case scenarios and become tighter when environments have special properties, such smoothness. Among them, the most related work is by Scroccaro et al. [2023], who develop OptCMD based on the optimistic online learning framework [Rakhlin and Sridharan 2013). The key idea is to make an estimate for the upcoming loss function, which ensures tighter bounds when the estimate is accurate and still maintains the worst-case bound otherwise. By utilizing the smoothness of f+()), OpICMD achieves ((VVT) and O() -loo Vr) regret bounds for general convex and X-strongly convex fc(), respectively, where V1 ΣT maxxex f(()
(x) ||2 denotes the gradient-variation and can be small when f.).) gradually changes.
Stochastic composite optimization. In this setting, fe(.) is assumed to be i.i.d. sampled from a fixed distribution 2. and the goal is to minimize the composite objective: minxex E [x)] + r(x). The performance is measured by excess risk, which compares the solution with the optimal one, i.e., EywD (xx)) + rxx)) min [Eg~d (x)] + r(x)).
In the literature, there are a substantial body of methods designed for the stochastic setting [Ghadimi] and Lan| 2012 2 Lan 2012 2016 Lei and Tang 2018 Lei et al.) 2019). and by utilizing the online-to- batch conversion technique [Cesa- Bisa-hia et al. 20044] existing methods for adversarial composite
optimization Xiao] 2009 Duchi et al. 2010
Yang et al. 2024c can also be extended to the stochastic
3

---

scenarios. Specifically, Lan 2012 first establishes an ((1/vT) excess risk bound for general
convex objective, and then Lan 2016) improves the rate (1/T)) for strongly convex objective. By utilizing the online-to-ban to-hhtch conversion, both RDA [Xiao] 2009] and COMID [Duchi et al. 2010] achieve (II/VT) and (log T/(T)) excess risks for general convex and A-strongly convex objective, respectively. When f()) is a-exp-coneave, ProxONS Yang et al. 2024c ensures an Old (T/ogg))(()))))))))))))))))()))) excess bound.
SEA model. The SEA model is originally introduced by |aahhs al. [022 an intermediate setting in online optimization without regularizer. Moreover, they also propose two versatile quantities o..T and Ei.r to reflect the stochastic and adversarial aspect of the environments, respectively. Theoretically, for the SEA model, Sachs et al. [2022] prove that optimistic FTRL enjoys the bounds of O(v oivoi. + vEirr) and O "<>-'(0> max +
E log 7) for smooth and general convex, and
smooth and X-strongly convex loss functions, respectively. Later, Chen al. [023] demonstrate that optimistic OMD is able to attain the same bound for general convex losses and an improved
max + (o
D log(o + E () bound for the strongly convex losses. Moreover, they also
FT establish new ((d//o) o)) lor + ():)) bound for smooth and a-exp-concave functions.
Universal online learning. The universal online learning is proposed handle the uncertainty of the loss function types, when applying online algorithms to practical optimization problems. The center universal algorithms the powerful meta-expert structure [van Erven and Koolen 2016
Mhammedi et al. 2019 van Erven et al. 2021 which is also widely in many other fields of
2018 2020 2021 Cutkosky 2020 Wan et al. 2021 2022b Wang et al. 2024 Wan et al. 2024a The key ıdea of meta-expert
online learning Daniely et al. 2015 un al. 2017a b Zhang al.
structure to maintain multiple experts to process different types of loss functions and then, deploy
meta-algorithm to combine the decisions from experts (Wang et al. 2019 2020 van Erven et al.)
2021 Zhang et al. 2022 Yang et al., 20224]b) b). In the literature, the most related work is Yan et al. [2033] J. who propose a novel universal algorithm with a two-layer MSMWC [Chen et al.) 2021 as the meta-algorithm. By maintaining multiple instances of optimistic OMD, their method can adapt to the SEA model and deliver the same bounds those in Chen et al. (2023), Recently, Yan et al. [0244] further improve this method by employing a simpler meta-algorithm while achieving optimal
regret bounds for three types of functions. However, it should be noticed that these methods (Yan)
ct al. 2023 2024) heavily relies on the smoothness of the summation function (T). and thus cannot handle the composite structure in loss functions well, as previously discussed.
3 Preliminaries
In this section, we introduce some preliminaries, including standard assumptions and a brief review of OptCMD [Seroccaro et al. 2023).
3.1 Assumptions
We first list the common assumptions in prior studies Duchi et al. 2010 Chen et al. 2023 2024 Assumption 1. The convex decision set X belongs to an Euclidean ball with the diameter D. Assumption 2. At each round t, the random function f((-) is G-Lipschitz over X, i.e.
Vx,y E X, (f((x) fe(y)) s Gl|x (iix-yliy yll2-
Assumption 3. The regularized function r(-) is convex and bounded over X, i.e.
Vx,y X, r(y) 2 r(x) + -v(()) (y (x-x) x) and Vx E X, 0 0 r(x) S C. Assumption 4. At each round I, the expected function F.(-) is H-smooth over X, i.e.
Vx,y E X, [[VF((x) - F Il < H[x -yl2- Assumption 5. At each round t, the expected function F.(.) is convex over X, iee.
Vx,y E X, F(ly) 2 Fx(x) + V (y x)..
Assumption 6. At each round t, the expected functionn F-()) is X-strongly convex over X, iee
yx,y X, F(ly) > F((x) + VF(()) (y -x) x) + (A/2) y12.

---

Algorithm Optimistic Composite Mirror Descent (OpICMD)
Initialization: Let X1 X1 be arbitrary point in X.
for 1 to T do
2: Submit Xt, and the environment chooses a distribution D;
3: Suffer the composite loss fx(x,) + r(x)). where ft(-) is sampled from Dr
4: Update Xt+1 and x according to and (5). respectively
5: end for
Assumption 7. All the variance of the gradients and the adversarial variations are bounded, i.e.,
Vt E [T], of S duax and sup
[[ - VFi-1(x))B < Σ max
XEX
Assumption At each round the time-varying function fe(-) a-exp-coneave over X, i.e. vx E R, (xp(-af((x)) is concave.
3.2
Optimistic composite mirror descent
OptCMD is an algorithmic realization of the powerful optimistic online learning [Rakhlin and Sridharan 2013 in online composite optimization. Specifically, in each round f, the learner submits decision x, and suffers loss fr + r(x,). Then, the leamner receives optimism M,+1 that serves as an optimistic prediction for the gradient of subsequent function fe+1()). After that, the
learner performs the following update steps:
X argmin {(VS((x)),x) +x(x)= 1 (x, xx)}
(4)
XEX
X argmin { (M + (xx) + R1 (x, xt+1))}
(5)
XEX
where BR. yx) (x - with time-iarying function R,, of which the specific form depends on the type of fe(-) and will be illuminated later. Note that in 4 and (5). r(-) remains non-linearilzed, which allows the decisions {xx)(=1 to possess properties externally conferred by r(-), such as the sparsity.
(V) (VR())
denotes the Bregman divergence associated
Remark. Scroccaro et al.
2023
specialize the estimate M++1 = ( where fe+1(.)
denotes the function prediction of f++1()) and generally set as fe(-) in practice. We hightlight that this specification is unsuitable for the composite SEA model and inadvertently introduces dependency issue during the analysis. More detailed discussions can be found Sections 4.1 and 4.2
OptCMD for composite SEA
In this section, we provide our results for general convex, strongly convex and exp-concave cases in the composite SEA model. Due to space limitations, all the proofs are deferred to Appendix
4.1 General convex case
Initially, we consider the case where the regualizer r(-) is convex and non-smooth, and the expected functions F-(-) are general convex and smooth. We choose the following configuration for this case.
Rx(x) = 1 | min
D
D
VI+V 8 J. and M = V ft (xx).
(6)
217:
where V - (x.)
V - (x.-1)l and 8 >> O denotes the hyperparameter. With the configuration in we establish the following regret bound for the general convex case.
Theorem 1. Under Assumptions
2
3
and Algorithm 7 ensures
E Regrety] = O (Vot.r + D2
with the configuration in 6 where 8 = 6v2HD.
5

---

Remark. For the fully adversarial environments where E VT and o = O, our bound degenerates to O( (TV matching the previous result of Scroccaro et al. [2023]. For the fully stochastic environments where 2 21.r 0 and oं. o with the stochastic variance o², our result becomes (VVT) regret bound and further delivers an O(1/VT) excess risk bound by the online-to-bated conversion (Cesa-Bianchi Bianchi et al.) 2004], which coincides with the results of Lan (2012). Furthermore, our finding also aligns with existing bounds for the SEA model without r(-) [Sachs et al. 2022. Chen et al. 2023]. In other words, our method pays price in regret bounds for handling the additional regularizer.
Beyond the configuration in (6) we also employ those adopted by SSroccarro et al. [023]:
1
1
Rx(x)=
x 2
VAH² + D and M++1 (x
27je
where Du = 0 and 1 we obtain the following bound.
Σ (x,( (8)-1(8))13 By setting the configuration in 7
Theorem 2. Under Assumptions
1 3 and
with configuration in Annorishmeensures
(Vor o + Fi.r
E Regret O
where नं. with o? =
[V)( (F((x) 112.
Remark. This bound is less favorable than that in Theorem as it scales with new quantity ot.. which also measures the stochasticity in composite SEA but is larger than oir because of the fact that E,,-D, [suPxex |V fx() - V (x 2 supxex ES,-D, fx() Fx) where the inequality is due the convexity of supremum operator. This discrepancy arises from the inappropriate choice of Mc+1 V (& where & is generated based on fx,, shown in (4), which implies that & has already incorporated partial information about fe()), leading to dependence issue in analysis. To remove the dependency, we apply the supremum operator on & over X' (c.f. Lemma 4 but inevitably establish a reliance on 0i. in the final bound.
4.2 Strongly convex case
In this part, we focus on the case where the regualizer r(-) non-smooth and convex, and the expected functions F-(-) are smooth and X-strongly convex. We set OpICMD with the configurations:
2
Rx(x)
|x
1x
n7.
8 Xt" and M,+1 Vf((())).
(8)
where 5 > 0 denotes the hyperparameter. The theoretical guarantee for this case is shown below.
Theorem 3. Under Assumptions
3 and 7 Algorithm enatttheemseeseess
[Regrety] O
{o Iaxx + Σ E log (oî. + )
with the configuration in g where 6 2
Remark. Similar Theorem this bound reduces Oo--1log Vrr) matching that of Scroccaro
et al. (0023] when environments become fully adversarial, and derives the same Olog (7TX")) excess risk bound as that of Duchi and Singer [2009) and Xiao| [2009] when environments become fully stochastic. Moreover, this bound also recovers that of Chen et al. [2033 for the SEA model.
Additionally, we further equip OptCMD with the original configuration of Scroccaro al. 2023
Rx(x) 2ttt
| Th
4H² (A/2G3) and M fe((++1))
and obtain the following theorem.
Theorem 4. Under Assumptions
and 6
with the configuration in Algorithm ensures 2 log (ō + Ei.r)
E Regret,
Remark, This bound suffers two limitations. Firstly, it depends on the unfavorable oi.r. which is due to the improper estimation M,11 @9.. Secondly, scales with (GG)) due to the choice of n in (9) which is not tighter than O max + "2 ) in Theorem

---

Algorithm 2 A Universal Strategy for Composite SEA
Initialization: Moop with ry" (Co 2 and of (n with 1y Mi = 21/ and Pi 1/N, and experts
for each & [K] M
K.
1: for = 1 to T do
2: Receive x from expert E and update q, and p according to 11
3: Compute x = -, Pt x and submit x, = Ex q, x
4: Suffer the loss f((x)) ) + rxx,) and observe the gradient g: = fx()
5: Update at+1 and p according to (12)
6: Send the gradient gr and the regularizer r(-) to experts
7: end for
4.3 Exp-concave case
We further investigate the exp-concave case where the regualizer r(-) is non-smooth and convex, and the individual functions f+(.) are smooth and a-exp-concave.
Remark. In this case, require the exponential concavity the individual function fz(-) instead of the expected one F.).). This is due to the technical demand in analysis, and similar assumptions also adopted by Chen et [023) and Yang al. (2024c).
In this case, we set OpICMD with the following configuration:
1 (x(x) = - [Ix112 H. = 5T 57
3G
Σ t-1
I+
2 ==1 hs and M+1 = Vx((),),
(10)
2
where > O denotes the hyperparameter, denotes the d-dimension identity matrix, he ((((x)) and B = (1/2) min at. The regret for this case is stated below.
Theorem 5. Under Assumptions
3 and Algorithm Tensures
d log (o + 2xr)
E Regretyy] O
with the configuration in 10 where = 1.
Remark. For the fully adversarial setting, this bound degenerates to ((d/aa) log Vr), which is the first gobblem-dependen bound for exp-concave tame-narying functions in online composite optimization, and tighter than ((d/a) log I') by Yang et al. (024c) in benign environments. For the fully stochastic setting, result reduces to ((d/a: a:) log 7") regret bound and further implies the same excess risk of Od (a)T) as that of Yang et al. [2024c) through the online-to- to-hatch
conversion. Furthermore, it also matches existing results for the SEA model [Chen et al. 2023
5 The universal strategy
Although we have established favorable theoretical results in the composite SEA model, achieving these guarantees requires prior knowledge of the function type to set appropriate configurations, e.g., (6) for the general convex case. This requirement is often impractical in real-world scenarios and motivates us to design a universal strategy. the previous study Yan et al. [2023), based on the meta-expert framework [van Erven and Koolen 2016 Wang et al. 2020 et al.) 2022), they propose multi-layer universal algorithm, which can adapt to the SEA model without regularizer by choosing optimistic OMD [Chen al., 2023 the expert-algorithm. Unfortunately, their method (Ynn et al. 2023) requires the smoothness of the (summation) loss functions, which does not necessarily hold for ( that it cannot be directly applied to the composite SEA model. In this paper, we propose a novel universal algorithm for composite SEA. For the expert-algorithm, we choose OptCMD due its ability in handling three cases in composite SEA. For the meta-algorithm, we design a new method that is able to effectively manage the non-smooth component r(-) in (I and thus track experts according to their performances in the composite SEA model.
Our method based on two key observations. Firstly, r(-) in ① is fixed over time and available to the algorithm from the beginning round. Secondly, the meta-algorithm can access expert
7

---

decisions for the current round before the performance estimation. Therefore, the information about r(-) can be introduced into the expert tracking process, securing that the regret of meta aagor-al will not deviate from that of the best expert. Specifically, inspired by Yan et al. [003]] we employ a two-layer meta-algorithm, with each layer running an MsMwC algorithm [Chen et al. 202T] that maintains two weight sequences (qr. 9. E A )tETT) and group of losses L, (4: . and
optimisms m, = (m.. m. ) to measure the performance of N experts. To handle the composite loss, we explicitly incorporate r(.) into both I, and m, The incorporation serves two purposes: (i) it endows 4, with a composite structure, facilitating the estimation of expert performance on composite losses; (ii) it utilizes the cancellation between L and m, to eliminate the non-smooth component in loss functions, i.e., r()), so that the meta-algorithm is able to leverage the smoothness of f.(-). In the following, we describe our universal algorithm, which is also summarized in Algorithm 2
Meta- Meta-algorithm. Overall, our algorithm comprises two components: two-layer meta-algorithm and a set of experts, together forming a three-layer structure. Specifically, on the top layer, we run one MsMwC named Mup. which maintains the weights q E A assigned to K (log T) MsMwCs, named Mmid- On the middle layer, each M (k E (K) maintains the weights p AN assigned to N = Olog T) experts. At the round I, we receive the decision x from each expert E and update the weights qe and P according to:
k.i
q: = argmin qEA*
{ (m., q) + 1 (q. q:)) P = argmin {(m] P) + +B* (p.
(11)
DEAN
where (q) En(o In/")//** and v2((p) = Es''' lnp')/1//t denote the negative entropy functions, and m. and m, denote the optimism used by M and Mop. respectively. Then, we compute the weighted average decision x = E; pf x and submit x, Ex g/xx"- Next, we suffer the loss [((x)) + r(xx) and observe the gradient g: = V.((x.). We update 9++1 and pf+1 by
4o+1 = argmiin { [14 + as, q) + B (q. q()} ,p/1 argmin (7, + + p) + B 3 p/)), (12) q
PEA#
where 4, = (G.....
denote losses used by Mop and M respec- tively, and a, E R and by E EN denote the correction terms. At last, we send the gradient g, and the regularizer r(-) to each expert. Now, we specify the loss and optimism in (1] and (12). For Mup. we choose
16) and & = 1 1k.N)
1 = (B: x²) + +(xx)) + 71 l| - x m (m, Pē) + r r(xx) + 71 x| x (13) k.d
where m = (m, ..... m ) with m. R, = =Be,,,)) (gi-1 1, x - x ). For M we choose
E-' (g:, x ( r(xx 72 1 my ki
m. k. r r(x () rallx x x-2112 (14)
In the above, 71. 72 denote hyperparameters. and 7 ||x - x 112 and 72 || x 112 are injected for cancellation during the analysis (Yan et al. 2023). It should be noticed that we explicitly introduce r(-) in (3) and (14). This is because experts are running over the composite losses and their performance assessment should similarly reflect the composite structure, ensuring an accurate measure for expert tracking. Moreover, the optimism m, with r(-) helps eliminate the non- non-smooth component in 4 and thereby enables the meta- aeta-alggri to effectively utilize the smoothness of time-varying functions. To make it clearer, we take the general convex case as an example.
First, the expected regret can be decomposed into the meta-regret and the expert-regret, as below:
E [Regrety]
= E
(xx( + r(x:)]
min XEX
[f(()) + rxx]]]
T
x k'' + r(xx) rxxt )
(g x H 10 - xx)) +r(x (0) r(x')
< E
gi. Xt=
+
mmeta-rogret
:xexerr-regret
where x denotes the decision made by the best expert E For the expert-regret, we can directly apply the result in Theorem [ Therefore, the key is how to bound the meta-regret. By the
fact that r(x.)= < Ex EggEr (x+)) and r(x)) < E.P. 2 (xxtt.))) the meta-regret is bounded by
meta-regret S Σ 4.) - 15 + Σ" T
T
r-1 (0b ,1% 14 xr + +0(1,, (15)
8

---

where the first and second terms denote the regrets for tracking experts of Mop and M mid- respectively, While these two terms involve the losses 1 and 1 that incorporate the regularizer, they can be simultancously controlled by favorable bound of O (4 x mi k" , ))), which not only eliminates r(.) by the cancellation between 1 "t" and m but also suffices to achieve the desirable bound of O O + V for general convex case and (1) for other two cases. More details can be found in Appendix
B.6 B.6
Experts. Each expert is an instance of OptCMD that equips with certain configuration, i.c., (6) (8) or 10). To estimate the unknown curvature À and a, we utilize the discretization strategy by ZZhan et al. 2022], constructing the candidate sets as
P Petr = Pexp 21/T, /T)
where N [log2 T'. Based on the two sets, we create following three types of experts:
Strongly convex experts, each which is configured with (8) and a candidate A Pstri
Exp-concave experts, each of which is configured with (00) and candidate a E Peupi
General convex expert, which is configured with (6).
As demonstrated by Zhang et al. 2022], these experts are sufficient to identify the best one that runs for the true function type with the most accurate curvature. For instance, in the strongly convex case, there must exist an expert E' equipped with X E Pstr that satisfies X' < X S 2X'. Moreover, instead of directly minimizing the original loss function ( each expert runs over new composite surrogate loss to avoid high-computational gradient query costs. Specifically, we choose (f(x) (gr, x) +r(xx,
(x) = (g:, x) rxx) X xxl1 /21///2 and [,,x((x) (g. x) + r(x)+ + B (gr: x x,) /2 for general convex, strongly convex, and exp-concave experts, respectively. These surrogate losses not only inherit the composite structure and properties of fx),, e.g., the strongly convexity, but they also require only one gradient query for g: = V (x,, in each round. The theoretical guarantees of our universal algorithm are presented below.
Theorem 6. Under Assumptions 7 2 and with proper hyperparameterss Algorithm 2 ensures
the bounds of O( Vooo + -EE.rr (.r)). Ol max m log(o]:r++), +igg)) and Od i. E Eir)))
for general convex, strongly convex, and exp-concave lime-varying functions, respectively.
Remark. Theorem 6 indicates that Algorithm 2 can attain comparable regret bounds those of OpCCMD for the three cases, without knowing the function type and curvature in advance.
6 Implications
In the following, we discuss implications of our results for two common intermediate examples.
Composite adversarially corrupted stochastic data. We first focus on the composite adversarially corrupted stochastic model, of which a special case without regularizer has been widely investigated
in learning with expert advice [Amir et al. 2020), bandits Zimmert and Seldin 2021 Ito 2021), and
online optimization [Sachs et al. 2022 Chen et al.) 2023). Specifically, each loss function consists
of three terms: (-(-) hu(-) + (x(+) r()), where hx(-) denotes the loss of i.i.d. data from fixed distribution 2 with the variance o, and cr(-) denotes an adversarial perturbation measured by parameter Cr > satisfying Everry maxxex| (x) I Cr. and r(-) denotes the regularizer. In this model, the stochasticity and adversariality come from h+(-) and c-(.), respectively. Therefore, oer and Σi can be formulated as
नं. = o2T, Ei. =
Σ
sup Vcxx xEX
ve-1(x))13 S 4GC
(16)
t=1
With the above specification, our theoretical results can naturally be extended to this scenarios, delivering the following corollary.
Corollary 1. With the specification (66) in the scenarios of composite adversarially corrupted stochastic data, we can obtain an OlavT + /CT) bound for the general convex case by Theorem 2T
an Ollog(o2T Cr)) bound for the strongly convex case by Theorem 3 and an Od bound for the exp-concave case by Theorem 5

---

Adversarial online learning with limited resources. We then consider the another common scenar- ios where loss functions arrive in batches and the available computing resources are insufficient to process them all [Bottou and Cun 2003 [Benzúár et al. 2018 Li et al. 2024 Zhou 2024 Specifi- cally, in each round 1, we receive a group of functions F ()) [K[K]] with the size K,, each of which is selected by the environments adversarially. We denote by F.(.) K, EEE ft(,, i)) the average function. Due to limited computing resources, we can only sample a subset of functions for gradient estimation, and generate sparse decisions for efficient storage and inference. For this reason, our goal is to minimize (-) h₂(+) + r(-), where h-(.) B, Eie(B.] fi(t.i) denotes the approximation of F((-) by i..d. sampling B, E [Kg] functions f((.,)) i) from the group Fe, and r(-) = ||- 1 denotes the f fn-nomm regularizer. In this scenarios, it can be verified that
i:r
sup B finte xEX
Br >
B.
S 4G
T Σ Br
(17)
and E.T- = =E supxex [F((x) - (x)11 Applying the above specification into our theorems delivers the following corollary.
in the scenarios of composite adversarially corrupted stochastic data, we can obtain an O EiEm Br + v bound for the general convex case
Corollary 2. With the specification
by Theorem 7 an (ree(( B," + -)xr)) bound for the strongly convex case by Theorem and an (d log Exetr B, + ))):r) bound for the exp-concave case by Theorem 5
7 Conclusion and future work
In this paper, we investigate the intermediate setting between stochastic and adversarial composite optimization, named composite SEA, and demonstrate that OpICMD is able to attain the regret bounds of O(vofr + ) ( > - log(of.7 + )))) and O Od + )) for the general convex, strongly convex and exp-concave cases, respectively. To deal with the unknown function type in real-world problems, we further propose novel universal algorithm in online composite optimization, and show that our universal algorithm is able to achieve the desirable bounds the three cases, simultaneously. Due to the versatility of of.r and Ei.r. all our theoretical findings can recover previous results in fully stochastic and adversarial composite optimization. Finally, we explore several practical intermediate scenarios to demonstrate the implications of our results. Additionally, we also conduct empirical studies in Appendix A to verify our theoretical results.
There are many valuable directions for future research. First, our methods still rely on the domain and gradient bounded assumptions. We notice that there have been several methods designed for unbounded cases OOabonaa 2014, Orabona and Pál 2016 Cutkosky and Orabonal 2018 Jacobsen and Cutkosky 2022], but all of them focus on the setting without the reguralizer. Consequently. developing online algorithms with the unbounded domain and gradient for composite SEA remains an interesting research direction. Second, in the composite SEA model, we implicitly assume that the feedback (i.e., the loss function value and the gradient) is immediately revealed after making the decision, which, however, is not necessarily satisfied in practice [Joulani et al. 2013 Quanrud and Khashabi 2015 Wan et al. 2222a c [0024b]. Therefore, it also interesting to explore the composite SEA model with the delayed feedback. Thirdly, our proposed universal algorithm currently exhibits three-layer structure, which presents several challenges in both analysis and practical implementation. Therefore, designing simpler two-layer universal algorithm in composite SEA is another potential research direction in the future, which may require the advanced techniques in Yan et al. 20244.
Acknowledgments and Disclosure of Funding
The authors would thank Yu-Hu Yan for helpful discussions, and the anonymous reviewers for their constructive suggestions. This work was partially supported by National Science and Technology Major Project (2022ZD01 14801), and NSFC (U23A20382, 62306275.
10

---

References
Amir, Attias, T. Koren, Livni, and Y. Mansour. Prediction with corrupted expert advice. In Advances in Neural Information Processing Systems 33, pages 14315-14325, 2020.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3163):677177,, may 2003.
A. A. Benczúr, L. Kocsis, and R. Pálovics. Online machine learning in big data streams. ArXiv e-prints, 1XXv:1802.00872 2018.
L. Bottou and Y. L. Cun. Large scale online learning. In Advances in Neural Information Processing Systems 16, pages 217-224, 2003.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 5009)2000-20577, 2004.
C.-C. Chang and C.-J. Lin, Libsvm: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(27):1-27, 2011.
L. Chen, H. Luo, and C.-Y. Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Proceedings of the 34th Conference on Learning Theory, pages 1216-1259, 2021.
Chen, W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. In Proceedings of the 40th International Conference on Machine Learning, pages 5002-5035, 2023.
Chen, Y.-J Zhang, W.-W. Tu, P. Zhao, and L. Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25 126, 2024.
C.-K. Chiang, T. Yang, C.-J. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and Zhu. Online optimization with gradual variations. In Proceedings of the 25th Conference on Learning Theory, pages 6. 6.2.0, 2012.
A. Cutkosky. farameter-free, dynamic, and strongly-adaptive online learning. Proceedings of the 37th International Conference on Machine Learning, pages 2250-2259, 2020.
A. Cutkosky and F. Orabona. Black-box reductions for parameter- pareeeter-free free online learning in banach spaces. Proceedings of the 3 Conference on Learning Theory, pages 1493-1529, 2018.
A. Daniely, A. Gonen, and Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pages 1405-1411, 2015.
J. Duchi and Y. Singer. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research, 10:2899-299 2934, 2009.
J. C. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. In Proceedings of the 23rd Annual Conference on Learning Theory, pages 14-26, 2010.
N. Flammarion and E. Bach. Stochastic composite least-squares regression with convergence rate (1/n)). In Proceedings of the 30th Conference Learning Theory, pages 831-875, 2017.
D. Garber and A. Kaplan. Fast stochastic algorithms for low-rank and nonsmooth matrix problems. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 286-294. 2019.
D. Garber, G. Korcia, and K. Levy. Online convex optimization in the random order model. In Proceedings of the 37th International Conference on Machine Learning, pages 3387-3396, 2020.
Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework. SIAM Journal on Optimization, 22 (4):1469-1492, 2012.
F. Hazan, Agarwal, and Kale. Logarithmic regret algorithms for online convex optimization. Foundations and Trends in Machine Learning, 1992):169-199 2007.

---

E. Hazan, T. Koren, and K. Y. Levy. Logistic regression: Tight bounds for stochastic and online optimization. In Proceedings of the 27th Conference on Learning Theory, pages 197-209. 2014.
Ito. On optimal robustness adversarial corruption in online decision problems. Advances in Neural Information Processing Systems 34, pages 7409-7420, 2021.
A. Jacobsen and A. Cutkosky. Parameter-free mirror descent. In Proceedings of the 35th Conference on Learning Theory, pages 4160-4211, 2022.
Joulani, A. György, and C. Szepesvári. Online learning under delayed feedback. In Proceedings of the 30th International Conference Machine Learning, pages 1453-1461, 2013.
P. Joulani, A. György, and C. Szepesvári. A modular analysis of adaptive (non-)conver, optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theoretical Computer Science, 808: 108:108-130 138, 2020.
K.-S. Jun, F. Orabona, R. Willett, and S. Wright. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 943-951, 2017a.
K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Online learning for changing environments using coin betting. Electronic Journal of Statistics, 11(2):522255100, 2017b.
A. Kulunchakov and J. Mairal. A generic acceleration framework for stochastic composite op- timization. Advances in Neural Information Processing Systems 32, pages 12556-12567, 2019.
G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133: 365-397, 2012.
G. Lan. Gradient sliding for composite optimization. Mathematical Programming. 159:201-22 2016.
J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient. Journal of Machine Learning Research, 10:777-801, 2009.
Y. Lei and K. Tang. Stochastic composite mirror descent: Optimal bounds with high probabilities. In Advances in Neural Information Processing Systems 31, pages 1519-1529, 2018.
Y. Lei and D.-X. Zhou. Analysis of online composite mirror descent algorithm. Neural Computation, 29(3):825 860, 2017.
Y. Lei, P. Yang, K. Tang, and D.-X. Zhou. Optimal stochastic and online learning with individual iterates. In Advances in Neural Information Processing Systems 32, pages 5415-5422 2019.
L. Li, T. Zhang, 7. Bu, S. Wang, H. He, Fu, Y. Wu, J. Bian, Y. Chen, and Y. Bengio. Map: Low-compute model merging with amortized pareto fronts via quadratic approximation. ArXiv e-prints, arXiv:2406.07529, 2024.
Z. Mhammedi, W. M. Koolen, and T. van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Proceedings of the 32nd Conference on Learning Theory, pages 2490-2511, 2019.
M. Mohri and S. Yang. Accelerating online convex optimization via adaptive prediction. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 848-88 886,, 2016.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programming, 120(1):261-283, 2009.
F. Orabona. Simultaneous model selection and optimization through parameter-free stochastic learning. Advances in Neural Information Processing Systems 27, pages 1116-1124, 2014.
Orabona and D. Pál. Coin betting and parameter-free online learning. In Advances in Neural Information Processing Systems 29, pages 577-585, 2016.
12

---

R. Pogodin and T. Lattimore. On first-order bounds, variance and gap-dependent bounds for adversar- ial bandits. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence, pages 894-904, 2019.
K. Quanrud and D. Khashabi. Online learning with adversarial delays. In Advances in Neural Information Processing Systems 28, pages 1270-1278, 2015.
A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference on Learning Theory, pages 993-1019, 2013.
S. Sachs, H. Hadiji. T. van Erven, and C. Guzmán. Between stochastic and adversarial online convex optimization: Improved regret bounds via smoothness. In Advances Neural Information Processing Systems 35, pages 691-702, 2022.
P. Z. Scroccaro, A. S. Kolarijani, and P. M. Esfahani. Adaptive composite online optimization: Predictions in static and dynamic environments. IEEE Transactions on Automatic Control, 68(5): 2906-29211 2023.
U. Sherman, T. Koren, and Y. Mansour. Optimal rates for random order online optimization. In Advances in Neural Information Processing Systems 34, pages 2097-2108, 2021.
van Erven and W. M. Koolen. Metagrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29, pages 3666-3674, 2016.
T. van Erven, W. M. Koolen, and D. van der Hoeven. Metagrad: rates in online learning. Journal of Machine Learning Research, 22(161):1 2021.
adaptation using multiple learning
Y. Wan, B. Xue, and L. Zhang. Projection-Fe online learning in dynamic environments. In Proceedings of the 35th AAAI Conference on Artificial Intelligence Advances, pages 10067-10075, 2021.
Y. Wan, W.-W. Tu, and L. Zhang. Online frank-wolfe with arbitrary delays. In Advances Neural Information Processing Systems 35, pages 19703-19715, 2022a.
Y. Wan, W.-W. Tu, and I.. Zhang. Strongly adaptive online learning over partial intervals. Science China Information Sciences, 65(10):20200,, 2022b.
Y. Wan, Y. Wang, C. Yao, W.-W. Tu, and Zhang. Projection- online learning with arbitrary delays. ArXiv e-prints, arXiv:2204.0499 044944 2022c.
Y. Wan, C. Yao, M. Song, and L. Zhang. Non-stationary online convex optimization with arbitrary delays. In Proceedings of the 41st International Conference on Machine Learning, pages 49991- 50011, 2024a.
Y. Wan, C. Yao, M. Song, and I. Zhang. Improved regret for bandit convex optimization with delayed feedback. Advances in Neural Information Processing Systems 37, 2024b.
G. Wang, S. Lu, and L. Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence, pages 259-668,77 2019.
G. Wang. S. Lu, Y. Hu, and Zhang. Adapting to smoothness: A more universal algorithm for online convex optimization. In Proceedings of the 34th AAAI Conference Artificial Intelligence, pages 6162-6169, 2020.
Y. Wang, W. Yang, W. Jiang, S. Lu, Wang, H. Tang, Y. Wan, and L. Zhang. Sta-inaaionary projection-free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pages 15671-15679 2024.
L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. In Advances in Neural Information Processing Systems 22, pages 21 2116-2124, 2009.
Y.H. Yan, P. Zhao, and Z.-H. Zhou. Universal online learning with gradual variations: A multi-layer online ensemble approach. Advances Neural Information Processing Systems 36, pages 37682-37715, 2023.
13

---

Y.HH. Yan, P. Zhao, and Z.-H. Zhou. A simple and optimal approach for universal online learning with gradient variations. In Advances in Neural Information Processing Systems 37, 2024.
Yang, M. Mahdavi, R. Jin, and Zhu. Regret bounded by gradual variation for online convex optimization. Machine Learning, 95:183-2233 2014.
W. Yang. W. Jiang, Y. Wang, P. Yang, Y. Hu, and L. Zhang. Small-loss adaptive regret for online convex optimization. In Proceedings of the 41st International Conference on Machine Learning, pages 56156-56199 2024a.
W. Yang, Wang, P. Zhao, and L. Zhang. Universal online convex optimization with projection per round. In Advances in Neural Information Processing Systems 37, 2024b.
X. Yang, P. Tian, X. Cheng, Y. Wan, and M. Song. Regularized online exponentially concave optimization. Neurocomputing, 195:127789, 2024c.
Zhang, S. Lu, and Z.-H. Zhou, Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, pages 1323-1333 2018.
L. Zhang, T. Yang, R. Jin, and Z.-H. Zhou. Relative error bound analysis for nuclear norm regularized matrix completion. Journal of Machine Learning Research, 20(97): 19997):-22,, 2019.
L. Zhang, S. Lu, and T. Yang. Minimizing dynamic regret and adaptive regret simultancously. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 309-319, 2020.
I.. Zhang, G. Wang, W.-W. Tu, W. Jiang, and Z.-H. Zhou, Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex funetions. In Advances Neural Information Processing Systems 34, pages 24968 24980, 2021.
L. Zhang, G. Wang. J. Yi, and T. Yang. A simple yet universal strategy for online convex optimization. In Proceedings of the 39th International Conference on Machine Learning, pages 26605-26623, 2022.
W. Zhang, Zhang, Jin, R. Jin, D. Cai, X. Li, R. Liang, and X. He. Sparse learning with stochastic composite optimization. IEEE Transactions on Puttern Analysis and Machine Intelligence, 39(6): 1223-1236, 2017.
Z.-H. Zhou. Learnability with time- smarinh computational resource concemn. National Science Review, I1(10):wwae204, 2024.
J. Zimmert and Y. Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning, pages 928 928-936, 2003.
14

---

A Experiments
In this section, we conduct empirical studies validate theoretical results.
Setup. In this paper, we show that OptCMD with suitable configurations is able to achieve series of favorable theoretical guarantees for the composite SEA model. Moreover, for the practical scenarios where the prior knowledge of loss functions is unavailable, we propose novel universal strategy, called USC-SEA, which can still achieve the desired regret bounds for three cases in the composite SEA simultaneously. To verify our theoretical findings, we conduct experiments on the mushroom datasets from the LIBSVM repository [Chang and Lim 2011]. J. and consider the following online classification problem. Let T denote the number of the total rounds. At each round E [T], the learner receives sampled data (x,, Ut) E IRd {-1, 1] with d = 112. Then, the learner plays the decision w, from the ball X with the diameter D = 20, and suffers composite loss
Φe We(w;; Xx, Vt) fi(We; Mr) + Ar(w:),
where we set the hyper-parameter À = 0.001. The dataset used in the experiments is considered to be sampled from unknown distribution, possessing the inherent stochastic property. To simulate the stochastically extended adversarial environments, we perturb the dataset by randomly flipping the labels of 10% data the adversarial corruptions.
consider the following three types of loss functions.
For the general convex case, we choose the smooth and convex cross-entropy function as the time-varying function:
fe (W(w; Mc) = - log (x. wx) - (1- y1) log (1 a (x, wi))
where a-) denotes the sigmoid function, and utilize the f--norm regularizer r(w:) = ||w,ll1- Therefore, the composite function takes the form of:
d(wi; X1, 31) = -y log (x] w.) - (1 - ye) log (1 - a (x] wt)) + A/wwell
For the strongly convex case, we employ the cross-entropy functions with the nn-n regularizer as the time-varying function:
Se Wr Xt, (t. = - log (x] w:) (1 y/ log (1 (x] w.)) + 8|| w.
which is 26-strongly convex, and still leverage the & -norm regularizer. Hence, the composite loss function is in the form of:
@ Wr; Xt, y/) y/ log (x. w.) (1 yı) log (1 (x]wwx) w.)) ol A/|wa|la a = 0.001.
where we set the For the exp-concave case, we utilize the logistic function as the time-varying function:
fe(w; 31) log (1 exp (-yow,"xx xx)x
which is exp-concave and smooth [Hazan et al. 2014), and still employ the -n-rorm regularizer. The composite loss function is shown below:
6Wr; Xx: Mt) log (1 + exp (-y:w, x:)) + A/| A/[welli.
Contenders. For the general convex and strongly convex cases, we compare our methods with OGD Zinkevich 2003). COMID (Duchi al. 2010] and Optimistic-MMD [Chen et al.) 2023 For the exp-concave case, we choose ONS Hazan et al. 2007], ProXONS (Yang et al., 2024c and Optimistic-OMeir according to their theoretical suggestions. For instance, in the general convex case, the learning rate is V._1 ) -1/2 1/2 in OptimisticOOMD 1
[Chen al.) [023] as the contenders. All parameters of each method are set
set as 7 et 1/2 in OGD, and = cT-1/ 1/2 COMID, T7 D(c
where denotes the
selected from {10-
10*).
Results. All experiments are repeated ten times, and we report the instantaneous loss, the cumulative loss and the average loss against the number of rounds in Figure [ for the general convex case, Figure 2 for the strongly convex case and Figure for the exp-coneave case. From the experimental results, it is evident that adversarial corruptions cause considerable fluctuations in the instantaneous losses across different methods. Moreover, we also observe that, the three cases of composite SEA, both OpICMD and USC-SEA suffer lower losses compared to baseline methods, demonstrating better performance. This phenomenon can be attributed to their ability to adapt to the composite SEA environment, and their explicit support for handling the non-smooth component r(.).
15

---

1800
Instartanenns Lass
Cunndiaivve Los
0.9
1200
Avange
0.7
0.5
0.3
0
3
5
2
5
Rounds
163
Rounds
Rounds
(a) Instantancous Loss
(b) Cumulative Loss
(c) Average Loss
OCD
COMID
Optimisti-OMMD
OpICMD
USC-SEA
Figure 1: Experimental results for the general convex case.
2800
3.0
Indentanents Le8s
Curxiladvvv ToveeTsss oss
2100
2.4
1.8
1400-
Avergee
1.2
0.6
3
5
3
5
2
5
Rounds
Rounds
Rounds
(a) Instantaneous Loss
(b) Cumulative Loss
(c) Average Loss
OGD
COMID
OplimistieOMMD
OpCСMD
USC-SEA
Figure 2: Experimental results for the strongly convex case.
1600
Indontinnnus Les
Cunuueeivve Lo8S
0.8
1200
800
Awarge
0.6
400
0.4
0.2
3
2
3
4
5
2
5
Rounds
Rounds
Rounds
(a) Instantaneous Loss
Cumulative Loss
Average Loss
ONS
ProxONS
OptimisticOMDD
OPICMD
USC-SEA
Figure Experimental results for the exp-coneave case.
B Theoretical analysis
B.1 Proof of Theorem 1
First, since the expected function Fr(.) is convex in each round t, we could decompose the instanta- neous regret as below:
+ ((x)) rxx"]] -x(x))] (18)
E (x,) - -ft
[f( + -
< (x)( X -
16

---

The inequality is due the convexity of F.(-) and the last equality is due to the interchangeability of differentiation and integration by Leibniz integral rule. In the following, we shed the light on the right side of (T8).
Then, introduce the following lemma for OpICMI.
Lemma 1. Assume Re(-) is an r--strongly convex function with respect to the norm || and denote by II ||e the dual norm. According to the updating rule 4 and D for all x E X, we have
(Vf((x),x - x) + r(xi) r(x) 5 - -1,, - fxx + [B (x, 82)2 BR (x, x(1))
- R (x)+1. Xi) + BR. (x,, x,)].
(19)
In the general convex setting, we choose 7/2 = minkD/ and || 11 - 1|2.
v
and || ||. /nell 12- Therefore, the corresponding Bregman divergence becomes BR,((x,) y)
2m ||x yl with respect the n7- - strongly convex function R,(x)
1
2 | Now, make 2m.
use of Lemma ! with Mr = V ft (x)-1), and obtain
(V xx
-xxxxxxxx x') + r r(x:) r(x*) S mllVf((xx)) f
1
+
[1|x 8. 11 - ||x - x 2np
{ [18011
xxl13 + ||x: xx112))
21
Summing the above inequality over 1,... T, we have
Vi((x)), X, xx") r(xx) r(x')=
m (xx,)x) V (x
tern (a)
(20)
T
T
{||x*
&1112 - 1|x 8++112)
{1bs411 - xel12 + ||x; - xx
2m
2T
(b)
tern
Now, we have decomposed the upper bound into three terms and will analyze them separately. To bound the term (a), we introduce the following lemma.
Lemma 2. (Pugodin and Lattimore 2019 Lemma 4.8] Let I,. lT be non-negative real numbers
with the B). Then, we have
T
Σ
S 4 1+ Σ
B,
1+
where for simplicity we define 0/ 100
By utilizing Lemma 2 and the fact that 17: < D/ LDD/I+VV-L the term (a) can be upper bounded as
follows:
term (a) S [V)(( (
+ 4DG2.
(21)
VI+ V--
For the term (b), simple calculation delivers
1
1
term (b)
Xx
x
12
xx
-xell2
l|xx
x
11
27/1
11
21TT
(22)
D
D
T
1
D2
D.
V
Vr
D8
2m11
2
1/1
20Tr
2
2
1=2
17

---

For the term (c), we utilize the fact that - D/ō, and thus obtain
T+1
T
term (c)
2
[
x;-1
12 +
|x
- 8211
2 1=2
2 1=1
(23)
6
8
[11
xx-1112
||x - xc112 2
xx
x,-1
2D
4D
The last step is due the domain bounded assumption, i.e., Assumption we obtain that
Combining
21
22
and
23
3D -xx)) -xxx) VI+ VT
D8
8
Xt
X 11 4DG².
2
4D
tm
2
(24)
To bound the term Vr, we exploiting the following lemma. Lemma 3. Under Assumption and we have
Vr <C +8
[e(x))) VF((x.112
(25)
T
T
+ 4
[+i(x--1) - V (x 411
1
Plugging
25 into 24 obtains
(xx)))) + xx
GDD
D6
T
+ 4DGG2 + 2 + 6HH,
X2 X, x,
X2
x,
4D
1=2
+ 12D
Σ
[V)(x,)) (x 6D,
( - -
1=1
Then, we apply the AM-GM inequality, i.e., 6HD Ete lixt x1
5
36
5 WD
2 |x: x111 and obtain
D5
36
(xx,)))) Vr(xx) -x) 2 GD) + 4DG + +
1=1
T
T
+ +12
[ VE 6D,
VF - VF (X-1
By setting 8 = 62HHD, we have
T [V V
Σ (xx))x)) + Vr(xx), -x) 50,+ 12D
+ 6D
VF((x,-) - -
18

---

where C1 = 2(D + GD) + 4DG² + 6V2HD2 Next, according to the definition of cir and 1:T.
the expected regret can upper bound as follows:
T
E Regrety] SB
[Vx((x))) + V
5C + 12D 2 + -
-0
(Voir++
B.2
Proof of Theorem 2
First, according to 18 we have
E [[]((x)) + (x.)) - [s((') + r < [ - -x']] xx)]++++xxx rx(").
(26)
Till 1/12. Hence, the function Rx(x) 2mh ||x| is 7/e -strongly convex and the Bregman divergence becomes B (x. Then, applying Lemmal] [|]
In this setting, we still choose || بهب
|l- 1l2. and ||
_ |x y
2np.
we obtain
1
(Vfi(x)). X x*) + rxx,) - r(x*) Snel| (xx))l
+ - 1|x - 22e12
21).
1
|x -
x
12
||
xel13
||x; Sell2
277.
217
27p
Following the configuration in Scroccaro al. 2023 D,)-1/2 where D. Σ [v.) Theorem 2.5], we have
set Mr Vfi
(xe) and Tr- (4H²
V
(xt)
11..
According
[Scroccaro al. 2023
T
- r(x') & 5
4H2 Dr. V
2
To bound the term Dr, we introduce the following lemma.
Lemma 4, Under Assumption we have
T
T Σ
Dr s G +
sup xEX
- VF(
sup [V, - ( xex
By applying Lemma
obtain
Vi(x))) Xx x: xx) ((x)) - rx(x")
3 DD) [VAH++ G2
T
<
5 2
Σ
sup V V+L( -
(27)
1=1
xEX
+2,
sup [V) VF-1
xEX
1=1
Substituting
27 into (66) and taking the expectation on both sides finishes the proof.
B.3 Proof of Theorem 3
In the beginning, state the parameter configuration under the strongly convex setting (i.e., Fi(.) is
strongly convex and r(-) is general convex). The learning rate set as 7)+ 3+AZ
2 and the norm is
chosen ||- T l|2. with the dual norm |l. /nrell - ||2. Therefore, the function becomes
(x) 1 |x and the corresponding Bregman divergence becomes (x, - | yl
19

---

Then, we make use of the strong convexity of F.).), and decompose the instantaneous regret as below:
B (x)e + r(x))] [f(((') + r(x')
}]] E [xx( + (xx)] - [Fi(x*) +xx")]]
X
<B
[ -x' + rxx)) r(x')
2 211x²* -x,1 2
(28)
E
(V((())), xx) r(xx) - r(x') -|x X1 112
Similar the analysis in Theorem Lemma we have
we then focus on the the right side of (8)). By utilizing
(x.()), -x) +r(x) -r(x") r(x*)
x 11
x
Vf((x))
V
t=1
term (a)
1
T
1
{|1x² - -2 - 1|x* x
||x"
-x
{[|x[+1 - Xx 112 + ||x: xx
217
217
tarn
Next, we analyze the above three terms separately. For the term (a), we substitute v) S X
and obtain
T 2 X term (a) S Σ [i(e))
(x--
(29)
For the term (b), we exploit one result of Lemma in (52) i.e.
||x, Sct1ll2 I mel V fx(xs) V (x1-1)
(30)
with ||- =
1
lle and
||
||~ Tell ll2. By utilizing 330
we can upper bound the term (b) as
vh
following:
D
1
T
term
(b)
||x - ,,
x
X₁
271
217;
21/-1
2
D2>
[||x*
8++1
11 - 21|x** xx
4
(31)
D2X
D2A
Xx
[xx())) Ve--
D2A
Xm
y²
m (xxx)
パーー (x 12 S 4
+ term (a).
4
For the term (c), we make use of the non-increasing property of mn and m S 2/6, and obtain
T
term (c) 2
||:,
xx-1112 +
|| xx
21)=-1
27h-1
1=2
(32)
|x]
xx-1113
x1-1133
4n-1 1
1=2
1=2
Putting 29
31 and 32 together, we obtain
A T
fi(x)) - x3) r(x)) r(x*)
Σ
xx -xel1
2
t=1
(33)
D2A
T
T
[i(x))) (x
||x
x,-
4
M
20

---

Now, we make use of byproduct 55 from Lemma i.c.
[x,) V
4 - VF 4 x, x,-1
+
(x)
and thus
33 becomes
T
VV((())) x4 - -x)) - r(xx)
Σ
xx - x
2 1=1
T
16
(20)
+ suu [V((x)) vF--1(x)12)
(34)
Xt
X
1=1
16H
8
D22
||x
x 11
|
x1-1 -x,-xx-111
X
8
To bound the first two terms, we introduce the following lemma.
Lemma 5. (Yan et al. 2023 Lemma 9] For a sequence of {ot and b, where ae, b > for any
E [T], denoting by amax
maxaa and A & [b TE 0e), we have
T
a
Qmax
+ (1+InA) +
bt
6²
Let = -20-- + suPxex (x)
V (x) Amax
20 max + 52 mmx b = A and A
[A(20). + -1.1 Then, applying Lemma 5
we obtain
20 2)
2 + sup [ (177(x)-VFF-11) (x)-
(1+ + 1(207 + Ei:r))
X2
xEX
(35)
Let 0r we obtain
||x X1 x1-1/12 0max = =D2, and A = a DAE
|x,- x
Applying Lemma
5
Σ X1
x
x1
D2
1 1n(1 + Σ
[x
x
11:)
1
X
X
(36)
D2
1
S
X
1 1
Xt Xt_ 11
+
x
where the last step is due to In(1 + < for any x 2 0.
Substituting
(5) and 36 into
34
have
E
Σ xx
rx("')
Σ
I|x xx
t=1
<0
+ Σ
max In + {iir)) + [16H22
8 8
Σ t=2
xx
x, 0(1)
Setting& 8 = 12 finishes the proof.
B.4 Proof of Theorem 4
Similar to 28 Theorem 3 the instantaneous regret upper bounded by
[[f (x:) + rxx:) )] [f((x*) + rxxx)]] = E (Vi((x)), x1 - xx) + rxx:) - r(x")
1|x xx
21

---

According to [Scroccaro et al. 2023, Theorem 2.9], OptCMD with the configuration in
ensures
Vf((x)), x +r(x,) - r(x") 211xx² - -x,11
(37)
52HD²
G
4G
log (1+ (T)
H
For the term log (1+ aHC
Dr), we apply Lemma 4 and obtain
log
1+ 4HG
DT)
S log
1+
4H1
T
T V VF) + -
log
1
Σ
sup
sup VFi(() - V F
8HC²
t=1
xEX
t=1 xex
Taking expectation over both sides of the above inequality delivers
E log (
4HG² Dr)
A
DT
log (1 (1+ 4H
X
log 1
8HG2 (30 + 25
Plug the above result into
(37 finishes the proof.
B.5 Proof of Theorem 5
For the exp-concave setting (i.e., (.()) is exp-concave and r(.) is general convex), parameter configuration is follow Chiang al. (2012). To be precise, we define H, 51 + G 2 Σ h,
where h, = (x,,)) fx, The norm set as || || ll and || ||+ = || |.-, and
the function becomes Rx(x) } [xx. With this (x),, the corresponding Bregman divergence
becomes 8t (x, +l|xx y yli...
First, we introduce a common property of exp-concave function, as shown below.
Lemma HTaaan et al.
2007
Lemma 3] Under Assumption and if f(-) exp-concave over X,
we have
f(y) 2 f(x) + (VF(x) 2 (
for y E and min 1 a).
Then, according to the exponential concavity of fe(-) shown in Lemma 6 we can decompose the instantaneous regret as below:
E [xf( + rxx))] (xf((x)) + r[x")]
<
V [ xx) + rxx, r(x') x -
Recall that we denote h, Vf (V x,)²
Hence, the last term in 38 be rewrite as
Ix" 11.....
Now, we focus on the right side
38
By utilizing Lemma I we have
T f
(xi(x))
- x
r(x)) r(x*)
x xel1
[)((x) V/o-
1=1
tern (a)
[||x*
Re 1el1
1|x
8e+1 1441112 11
=1|x**
Xx
||
[|| xx + ||x X, 11:h]
tern
tern (c)
The term (a) can be upper bounded as shown in the following lemma.
22

---

Lemma 7. Let d be the dimension. Then, we have
term (a) S Sd In
3 T
1
[x)(
(x
(38)
B
86
For the term (b), we exploit the fact that H4+1
Hr = h and obtain
1
term (b)
2
||x
&111i1, - 1|x* x1+11125T+1
1 T
{ 1|x - 82+111 1133.111 -11x"= - Sc+1 1i., - -11xx* xollh. }
+
2
1=1
1 ||x
8111.11 - -1ix* -ST+111 + + Σ {11x* Sett 11. -2|xx* -xelbx.)
88
2
1=1
8 G2 D2 +
{11x - xx+1 Il. Σ
T
2||x* xxll2.
(39)
2
To proceed the proof, we introduce the following lemma.
Lemma 8. CChiang et al.
2012 Proposition 1] For any y, R and any PSD H E NNN, we
have lly + 2 - H
2 1
Applying Lemma on (39 obtains:
T
term (b) -
+
2
D2
12|x* -xelh, + + - *2+111?, - -2|[x* x xellhh }
2
4
4
1=1
2 +
8 8
6
D² +
8
Σ
||x:
211111?
(1
B
G2
D² + ||x - *
2
2
4
1=1
T
6 D2
2 +
(x,)
V -
(40)
where the penultimate step is due to H, 2 G hr. and the last step is due to
||x - &l I1,, S V (x.,) - V ff (
(41)
which could be obtained from Lemma with || || = || |l. and || ||= = || -1 For the term (c), we have
T+1
1 Σ ||x X1 11.2..
term (c) |
x 11
+ 2
1=2
(42)
T
{1|
x 1|xe - xx11]] 2
Xxt x111
t=2
where the first inequality is due to H, 2 H 2 81, ||+++] - X
-x
2 0 and ||x: - -x113, 2 0.
Combining (38)
(40) and (2)) obtains
T
9 T
(x(())) X x²) + r(x:)= r(x")
Σ
Ixx xx xtllh.
24d
3
T
8 T
<
D2 +
ln
1
V (( - v (x--
Xx - X x
2 4
3
85
23

---

Next, we leverage Lemma and arrive at
8
fx()))
xx") + rxxx) r(xx)
|x
x:llh.
2 1=1
6
3
8
16d
3
G2
D
Xx
X1-
In
1
6² +
-F)
2
4 1=2
18
T
BH²
T
+
[V(((((11) VFL-1(X(-1)]
X1 - -X x1-1
26
(=2
1=2
0
8
T
16d
B
T
+
G²
D²
[x
x1-1112 -x
+
In
1
G² + 8
Vf((()) - -
2
4 1=
86
1=1
T
16d
3H²
+
[F(((-))) - V (
+
In
1
|| - -
28
2=2
1=2
(43)
where the last step is due to the inequality
In(1 + u + v) & In(1 + u) + In(1 + u), Vu, v 2 0.
(44)
To simplify 43). we make of the following lemma.
Lemma 9. CChnn et al. 2023 Lemma 7] Let A 2 0. 2 0, 0. 0 and > O, we have
ab +1
1 cA aan
From Lemma
9
we have
16d In
3112
6 T
16d
x x,
+1
1
|x, x, 1 113
S
In +22dH²+1),
(45)
26
3
where we set 8 in the last step. Combining
(43 and (45) we have
T
T
V (x,,) + vr(x)), x²)
xx
Xx
ll
1
16d
16d
3
T
<
+ G2
D² +
In (32dH1 + 1) +
In
1+
G2
+
8
2
B
B
8
t=1
T
+
[F((x-)))
- 1
1=2
Taking the expectation over both sides delivers
8
E
(x())))
Vr(x.) xx")
2 Σ ||x - X2 11
3
16d In (32d/1² 1)
16d
B 02
3
62
D
In
1+
Boi.
2
B
3
8
2
where the last step is due to the Jensen's 's inequality. Finally, we complete the proof by substitute the above result into 38
B.6 Proof of Theorem 6
In this part, we analyze three types of functions separately.
24

---

B.6.1 For convex functions
First, since the expected function Fi(+) is convex in each round t, the instantaneous dynamic regret could be upper bounded as below:
E + + ( (VF, - + [[V xx) r(x;) r(x")]
+r(x,)) -F:: [x*( + }]]
Then, we decompose the regret into meta-regret and expert-regret:
T
E [eggetty] SE
Σ xxx( - + - r(x*)
T
T
=E
(f,()))) x + rxx)) - -(xx
+E
((Vs(()),, x/ - x²) + r(x, r(xx))
xx)++
meta-rogret
expert-regret
Expert-regret analysis.
According to the above decomposition, we define the surrogate loss functions (x) (V), x) + r(x) for the i-th expert. According 24 we can bound the expert-regret by
3D
expert-regret <E
V 1 VT
X
ki 2
4DG²
2
2
4D
3D
(1 + G)
+ 4D2 + 12D
oor
+
6D
Σ
T
6
+ 10HD
[x: x1
x
x-11
4D
where the last step is due to Lemma 3
Meta-regret analysis. We first consider the instantaneous meta-regret:
(V - x + rxx)) r(x
=VVf((x;; Xx - x
+ rxx:) - r(x{) + (V x x () + r(x)))
r(xxx1)
K
N
<Vf((x)), Xt x + Σ
L rx(t) r rxxx + (V)((x)),
Ps
kid
r(x 1o.b -
K
K
kyl
ki
of ||
x + x
Pt
m
k=1
1=1
72
Σ
P1
||x
b
x
bi
11
+ 72
x
x
= (q. - ek,4)) 4e) +
1x) - e 1
7/ Σ
||* - x
x - x
1=
N
7/
Pt
kii
xx
k.j
11
+
72
A.i xx-1
12
(46)
where the second step is due to Jensen's inequality, i.e., r(x,) r(Ek xx*+) s EK dx(()) and r(x,)) r
Xx k.d)
Pt kit rxxx and the third step due to the definition [4 For brevity, we denote gr (...... ,gk), l & (G...., ,14).
< EN
of th and do in 13 and
25

---

p. _ (gt" ::. at. ) and 1it - (1: 1.. ). By the above results, we have
T
Vf((x)), - x + r(xx) -r(x,")
Σ 1=1
(q:
ex,4) (p: -0%--e.11)
(1 - 71
||x
12
71
Σ
x
xf_11
(47)
t=
k=1
I 12
T
72
xx
Then, introduce the following lemma, which is similar to Yan al. 2023 different composite losses and optimisms in (13) and (14).
Lemma 3] but with
Lemma 10. Let lú, ml be defined in (13 and f... k. m, be defined in
14 Then, have
T
Σ (g ex. Le) + (pi ei, e..1,)
In 3(Con/))2
N
+ +3n
ml
k.d
1=1
Co
Co
l|q:
91-111
1-
16
1=2
t=
Note that
ki k.d)
m. = Σ
(VVi((x)), - -x+t) - (xx-- X1-1 -xai))
1=1
[x((x)) - Vi--1
x +2
hid 12 (x X1 xfd Xx-1 + x
T
T
<DD 4G2
Σ x x x, 102
||x,
k.t x
where the second and third steps are due to the fact that (a + b)2 2a² + +12 for any a, RR Taking the expectation on the both sides, we obtain
2
E
k. m
<2D + +2))
+ 4G
Σ
X x; x1-1
t
4G2
|x
ki
x-11
where the inequality is due to Lemma and Lemma 3 delivers
3
Therefore, Therefore,combinnng the above results with (47) Lemma 10
T
meta-regret
= E
(V
-x-xx x + r((x)) r(x(..)
In
+ 2566 22 + >. +
64 Co
212 + G
Co
64 71
Σ 1x:
T
x1-1
1/th
t=2
64G2
Co
T
Co
T
G2
+
72
Σ
|
l|g
q.-1 11
|p
p
Co
16 t=2
Co
1=1
t=2
K
||
ki
71
72
P1
To bound the first two terms, exploit the following lemma.
26

---

Lemma 11. Yan er al.
2023
Lemma 7] For the step size pool H. = {m.-". nnk with 7
1 20o 2
"T 2C0T if Co
X 27
there exists 1f E H satisfying
Y
+ + S 20 (n + X1XXX))
1/
Therefore, we have
N
+ +256n k D2((20):) + E1:T) 3(Con/)32
1
22
<2Coln(2N) + + (20 + E1
(20 + EiTT)
CB
<2Coln(2N) + 64D In
D C/
(20 + +
(V
v 12iTT)
Hence, by requiring Co 2 1, the meta-regret bounded as:
meta-regret
T Σ
<ō Voiir + -
+ +0(1) +64
2D + G²
64 71
| x
1=2
T
Co
Co
+ (64G² - 72))
Σ
|
kii
11
1 11-111
1p. p 11
x-1
2
16 t=2
[=1
t=2
T
71 Σ
Σ
x
Σ
kid
||x
x1111
72
Pt
Combining the expert-regret and meta-regret, get
E Regretty]
V p. +
Σ2
0(1)
(128D + 64G 10DH -m)
Σ
| x,
1=2
8
Co
+ 64G² - 4D
x
q:
llpt pi
T
<ō
(Voi.n + v /
+
+0(1) + (201 - 2m)
Σ
k
x x
1=2
+ 22 - 2D2
Co
Σ
q: 11? +
64G2 - -22
T
x
Rii
x
2
4D
1=2
where C 128D 24G 10DH and the last step is due the following lemma.
Lemma 12. Lerx, =K xt Then, we have
K
- - X, x1
||
x x +D= l|g. -q-1ll?
(48)
k=1
By setting Co 2 C, 2 8D 71 2 C and i 82 256G D + +4 we finish the proof.
27

---

B.6.2
For strongly convex functions
According to 28
we could decompose the regret as below:
T
E Reggett
T
EE
(x(())), X x") r(x,) - r(xx)
xx
X
1=1
fx()) X x*) + rxx1) -x(xt) -x(xx))))) X
SB
xx
x2112
2
1=1
X
(Vi( x4 -
((x)) - -(x
X
x
2
meta-regret
X
X T
+ E
(VI((x)),
+ +()) -
Σ
|x
x11
2
2
expert-regret
where the first step due to the fact that there exists an X H. satisfying X S 21'.
Expert-regret analysis.
We define the surrogate loss functions [x) = (V fx(,), x) + +xx)= +
1 ΣI_ xx - xel1 for the i-th expert. According to Theorem we can bound the expert-regret by
2
expert-regret
T
0 π (onax + - In (oi. + {(TT)
+ 16D2 (AP + +1)²
|x -
x1
1=2
5 (88D2 8D2 (H² +1
kid
2
1
20G
1
AD2
+ 4
+
+ x2
8
x
4
Meta-regret analysis. Similar to (46). the instantaneous meta- regret can be bounded by
X'
V (V(((x)), X1 x, ( + r(xi) r(x(tt)
|xx
x
2
K
S (g: eb 41) + (p: (4 Σ
x|x
x1 +
+ 1x11x - x
(49)
k=1
N
1/
Pi
||x
ki
bi 112 + 7/2 x
1|x
bis
11
|x
kid
xx11
2
1=1
For the first two terms, we exploit Lemma 10 and obtain
T
(q: - ex. 40) + (p:- ei, 1t)
In
N
+ 327
jo - m
ked 2
1
3(Corke22
1=1
(50)
Co
T
Co Σ
T
11q. 11
lpp
11.
2
16
t=2
t=2
Note that
MM
T
k.t k.i)
k.1)2
Σ(
- (Vff((x)))
- (V ( 1x) -xxx))- k.d
x²
2
m
1=1
([(( x x/:1)² 2
(x X,-1 x 2
+2
(51)
T Σ
(V[i(x)) X x )x 2G2 D2 < 4G2
kij 1
+ D2
Xt
x
28

---

where the first step is due to the fact that (a - b)² s
2a² + 26 for any a. E R. Substituting (50)
and ST
into (49 obtains
meta-regret
N
+
12
11
Σ
T
X
Co T 2
1--1ll
q
3(Cont))2
2
2=
Co
T
K
|pf
1i- -71
71
-
11
71
16
2=2
k=1
72
Pt
1|x
Ri
x 112 + 7/2
|x
Ri
x
G2
ln
N
+
12287
11
Σ
T
X
k
2
Co
T
9:-111
9:
1
2
2
1=1
t=
Co
T
2D
|p
p/-1
|
x x
71
16
1=
1=1
(27) 72)
Pt
[|
ki xt-1
11
+2221 >2|1x
x
64n G²
where the last step is due to Lemma 12 and C. 2 1. To bound the first term in the above result, we employ the following lemma.
Lemma 13. Yan et al. 2023
Lemma 8] For the step size pool H = =m....
. with 7) = 20
2
1/- 2C.T. Co TT where nf is the optimal step size, there exists 1/"h E H satisfying
1
Y
4Y
In
20 In (4Y
In
7
n
1f
(n²)²
Applying the above lemma with '7¹
2 delivers
256
512G²
2048NG2
Co
T Σ
meta-regret S2Co In (4NC)) +
11:
Q2-118 1
X
X²
2
1=2
K
Co
2D2m n
lpt
P--11
.1
le
|x
x
16
t=2
k=1
AD
(2%1 72)
Pt
x
ki
72
x
x
4
Then, we combine the expert-regret and meta-regret:
100 ( 10 (
E Reegrety
+ E In (oîr + 21.7)
T
+ 2D2 (H² +1 1)
+ 7/2
Σ
x
ki
+
2D
Co 2
Σ
l1q. 9: q.-1
1=2
Co
T
K
+
2D2m 12
Σ
|pt
p p + (2C2 - -m)
Σ
tt |x
x
16
1=2
k=1
N
+ (2%1 72)
Pt
||x
x
k.
+
t=1
where C2 16D2 (H² + 1)² Setting Co 2 AD2C2, Co 2 32D 8 GHT + +1) + 872. 71 2 202 and 72 2 71 completes the proof.
29

---

B.6.3
For exp-concave functions
According to 38).
we could decompose the regret as below:
8 T
E
R
E
- -x)) - rx(x))
Σ
VV(((x)). -xi)²
1=1
8
<B
(x() x²) +r(x) -x(x))
V (x(()))x x² xxxxxxxx>xxx)) -x,)²
2
t=
8r
2
ge: X x x + (xx:) (x
bib gi x
X
mataarregret
8 T
+ E
gr X x²) + +((xx") r(x") + +
Σ
gl
X
X1
g+. x
2
experi-regret
where g: fx(i)),, 9 1 mint JGD )²}, and the first step is due to the fact that there exists an a² H satisfying a² I a < 2
Expert-regret analysis. We define the surrogate loss functions 1x) = (ge. x) + r(x) +
g¹ [g. x xz)² for the i-th expert. According to Theorem 5 we can bound the expert-regret by
expert-regret
d
24d
C3
In
(oî.r
In
1
+
x2
x1-1
a
t=2
+
24d
In
1
3G
T
||x;
X
bib
112
6
|
Rif
Aib x,-1
112
+
8
G2
D2
B
2
4
d
24dCa
T
12dd*
8)
T Σ
00
In
+E9TT)
+
|x]
X
x4-1 112
x
x
8
4
1=2
3
G2) D2,
+ 2 + 4
where C3 = 8H2 + H4
Meta-regret analysis. Similar to 44)) the instantaneous meta-regret can be bounded by
(V(((x)), x. - x + rxx:) -(xx
R..)
(V]((x)). x -x,)
S (q: Ck, + pt c, 1,1
i Σ
dh l|x
x
112 + 71
x2_111
N
8 V)(((x)),
7/2
x
+ 12
x xx)
2
i=1
For the first two terms, we exploit Lemma 10 and obtain
Σ (q. ex, (pi e,, 16) - < 1/th
1 In
3(CorAa22
N
+327
#
m
kit
Co
T
Co T
1qg - 1
lp
p 1
16
1=2
30

---

Note that
4
my
k. 2
= -E
(VF((x))) - xx/) (x-)
T
V[(((x),, - x 2
+ (f--1(((-1)) - -x,-1 }
T
2
1=1
T V((())),x - x +2G2
Therefore, the meta-regret is bounded by
meta-regret
N
3
T
Xx -x-x,- x + 256G 12
In
+
1281/
17
3(ComT)2
2
Co
T
Co
T
K
91 - 90-1111 11?
Σ
lpt pp-illl 112 - m Σ
oe 11 - x + 11 - -x--112
2
16
tm
tm
k=1
N
72
Pt
Ri ki
||x]
x
Ris
112
+
7/2 xx
112
i=1
Applying Lemma 13 with 17"
8 delivers
256
Co T
512
2048N
meta-regret 22C In (4NC3) +
G
1q:
q:-1
B
8
2
t=2
Co
T
K
+ 20
lp
p
11?
71
k
x
b
16
2=2
k=1
(271 72)
Pt
ki
121
R
x
Then, we combine the expert-regret and meta-regret:
d In (oî. + 2ir)
48dDC's
Co T Σ
E [Regrety] 5
+
|1q: 4
8
1=2
+ 2DD29
Co
Ipp p
48dC's
Σ
oe x|
x
- 71
16
8
N
14dCa
8
+ (2 - 72)
Σ
||x
112 +
+ 7/
||x
x2111++
5
4
1=1
where C3 = 8H2 + 22 + 8G'
Setting Co 2 96dDCa/0 Co 2 32D 5 >
/6d(G4 + 4C3),, 71 2 48dC2/6 and 72 2% completes the proof.
31

---

C Supporting lemmas
C.1 Proof of Lemma [
First, we introduce two lemmas that will be used in the following proof.
Lemma 14. |Scroccaro el al. function and 1) > O. Define
2023 Lemma 3. 3.1] Let X be a convex set, sp()) X - be a convex
u = arg min (T) + v)]. XEd
Then, for any z E X, we have
r(g(u), u- 2) S B (2.v) (z.
-B -B () -B uBB (u.
where g(u) E @u(u)).
Lemma 15. (Scroccaro et al.
2023 Lemma 3.2] Let X be convex set, R X - be an a-strongly
convex function with respect to the norm || . Define
U1 arg min x.eX
((11xx)) + (x1) +B (x1,v)}
arg min { (W2, +r (x2) +B (x2, v)}
Then, we have
| - u2 S a ||w w2ll.-
Then, by exploiting the convexity of r()), we have
[x(()),, - x) + r(xx() - r(x) = (V)e(x)),, X - x) + rxxx) - r r(((+1)) + +((+++1) - -x(x)
fx())) - x)) + (Vr(x)), X1 xx+1) + (Vr X++1 -x)
(V)((x)) - M,, x(+1) + (M& + Vr(x,), X x (V)((x() + vr((++1); 81+1 x)
tern (a)
torm (b)
torm (c)
To upper bound the term (a), exploit Lemma 15 and obtain
term (a) <
Me|l- 8 a -1 - Mell
(52)
Next, we apply Lemma with the update
4 and (5), and obtain
term (b) B (K++1, xx) BR (K++1, Xx) BR. (xe, x1)
(53)
term (c) < Re (x, x;) BR (x, 81+1) - RR (8++1: xx)
(54)
Combining
52
53 and 54 finishes the proof.
C.2 Proof of Lemma
First, we consider the case f 1. Under the Assumption 2 obtain
(x;) - fo(x)) = | (x1 )l < G2
In the case 2 2, according the inequality ||a + b 2 | + 2/ have
(xxx)) (
<2 fx())) - V.F( ( -v
<xx,))( - - VF.
+ +4[[FF((xx - -V(-)----
Under the Assumption 4 the above result becomes
[xxx) Vx
f(x,) VFF 4H x
(55)
+ (X(xx-) - 1 - v
32

---

Combining both cases, we reach at
[VV)((x)) - Vfi-1(x--11B SG²
- -
+ + - x V - V
Summing up both sides of the above inequality over 1 1,... T obtains
VT GC +4 4
[V)()))) VX. - -1--
1=2
4H1
||x: -x +
(x) (
t=2
T
T
2 +8 8
[xx) VZ +4 +4
[+((x--1) (
T
+ 2H²
[xx x1-1
t=2
which completes the proof.
C.3
Proof of Lemma 4
Similar to the analysis in Lemma 3 we first consider the case t = 1.
= (V ( Vo(()))1
G?.
Then, for the case 2 2, we have
(lV 1 1 -
sup [V(( (x)
xEX
sup (xx xEX
V
sup 2 (x) v
xeX
S sup 2|| (x(x) ()
+ sup
2 (x)
v + sup sup 2 (
xEX
xEX
xEX
Summing up both sides of the above inequality over t 1, T completes the proof.
C.4 Proof of Lemma 7
The analysis is based on Lemma 19 in Chiang al. [2012). Recall the definition H, 1 0
D hp with h, = (fx Then, we can proof that
3 Σ h 8T
H. 81 +
(h, hy-1).
(56)
2
The first step is due to Assumption according to the fact that
2 and the last step is due to ((((())) the all-O vector. Next,
_ ( T + 1 2 Vf
hr + 2
h
2
(x,, + V (x)
(x)=) 10.
we have
hy + hp 2 V
(57)
Substituting
57 into (56 delivers
H. m 81
(V - (x--(( -//m(()))))
(58)
33

---

For brevity, we denote K, = 51= Er=1 (Vf+(x,) (+(x))))
- - vx--
From 58
obtain that H 3 K which implies
[Vx( - V
f((()) -
t=1
(59)
T
(V)((x)) - VI-
B
Then, introduce the following lemma:
Lemma 16. (Hazan et al. 2007 Lemma 11] Let u1
... ur E Rdd be any sequence vectors and
c > O be a positive real number. Denote V₁ = cI + > iiml
i.u. then we have
T
T
Σ
Vi Un S dlog
1+
u 1
1=1
By setting = å and u, / (Vf((x))
vfc (x we have
Σ p V (v)(x))) -Vit))- (x-r((
S dlog 1+ B
Σ
[Vvx())))
1 )1B
86
K,"
(60)
We complete the proof by combining (59 and
660
C.5 Proof of Lemma 10
Our proof starts from the following lemma for single-layer MsMwC.
Lemma 17.
Yan et al.
2023 Lemma 2 If max M1 [mi]]
S 1, then MsMwC enjoys
T
T
T
N
(.)
Σ
8
n pt (4: mi)²
11
t=1
1=1
1=1
1=1
+ 167
m,)
min kE[K]
Pr P-
4
(=1
t=2
can be verified that under Assumption in (13) and (14) are bounded
1
and
all our composite losses and optimisms defined
1 S GD GD+C+
Im S GD GD+C+
- < GD CD+C+ |m k. < GD+C+
and we can rescale them to [-1, 1] with only constant multiplicative factors in the constant hyperpa- rameter " and 722 Therefore, applying Lemma 17 with the first layer(i.e., with 1 as the surrogate losses), we have
T
T
K
Σ (1. q.)
Σ 1k
d (1t
mtt )²
77
17
k=1
A=1
(61)
T
T
+16 k
Σ
(1p - m
R/)
min kE[K]
q: 1
4
1=1
t=2
For the first two terms, the initialization gt (17
E (n and npt 1/((22h) imply
1 in
Ek_(1
K
xp=
1 3(Cont)3
In
S np In
+ 4Cb. (62)
np
k xp
(2
>
E
k
k=1
34

---

For the last term, due to n² = 1/(C)2*) S 2/Co. we have
1
Co
min
Σ
| q: 1111
9.
9--111
(63)
kE(K] 417
1=2
2
Substitute
(62
and
63
into 61
delivers
T
T Σ
q.)
In
3(Conph + 161/
(1
m
Co
91
q q:11 1 (64)
t=1
t=1
t=2
Then, we apply Lemma
17
again with if and m
T
Σ
Σ
nph.
1
In
k,
mpti
8
ΣΣ
n
R. k.d Pt
(1+ - mp k::0) 2
P1
1=
(65)
T
+ +16n R,s
m,
k.d 2
min iE(N]
1
Σ 1|pt p 11
4nth.
With the initialization ph
1/N and r/th
2n/²;
obtain
N
N
S ColIn +1)
P1
21/
Therefore, (65)
becomes
T
T N
Σ
L pi
In N +
167
&
Σ
Σ
Pt
kit
mmtd) 2
2n/²
t=1 i=1
(66)
T
Co T
+ 32n
Σ
-m
k.d)
Σ lllt -1
16
1=1
t=2
Combining (64) and (66), we obtain
T
qg ex. li) + (p: -e,
(=1
In
1
+ 3207
#
Σ
T
[ m, m.)))
Co
Σ lpp
p
112
C.
|1
9--1 11
17th
3(Conk))
16
1=1
1=2
1=2
161 *
(1 mt)
Σ
Pt #
(1
m
Hir 2
(67)
According to
13) and
14 the last term is bounded by
Ris (15 mt)² Σ Pt Ri (1+ m
N
= -(VVi((x)), xx²) - (mi pt))
(mitpp)) ))² -e
Pt
bib (1 - m k..0) 2
(68)
i=1
N
= (1)
m pf
Σ
Pt ki
k.d - (17-5- -
< 0
where 1.
((V
V (xx), x ) and the last step is due to Cauchy-Schware
inequality. Combining 67 and 688 completes the proof.
35

---

C.6 Proof of Lemma 12
k
K
k
||xe x
=
Σ
k
(-1
-
Σ
(xt
x + Σ
x x
(gf
s
1=1
2
k=1
k=1
K
K
2
Σ
(x}
x
+2
Σ
x (a z
k=1
k=1
K
4
x
x
1
-:- l1:
k=1
where the second step is due to (a
+ b)² S 2a + 262 and the last step is due to the triangle inequality.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions have been clearly claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations have been discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
37

---

Justification: All the assumptions are listed in Section 3.1 and the complete proof' are provided Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided detailed descriptions for experiments in Section A that are sufficient to reproduce the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
38

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: While the code is not included in the submission, the complete detailed descriptions of the experiments are provided in Section A
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://mips.cc.
aublic//uuddes/Coeeetuliiss www.siiyynnooyiiiioooooooooiiiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ tttips.cc/ubblic//e
wtteeee//ooSSSeeeseseeeee ssisssssiiipyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided detailed descriptions for experiments in Section A that are sufficient to reproduce the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experiments are repeated ten times with different random seeds, and the mean and standard deviation are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments are conducted on machine equipped with the Intel Xeon E5-2620 CPU and 32G memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Ye]]
Justification: The authors have diligently adhered the NeurIPS Code of Ethics in all aspects of this research.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mainly theoretical and there is no societal impact of this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
40

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is mainly theoretical and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper is mainly theoretical and does not use existing assets.
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
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.
41

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's 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 paper 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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
42

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
43


Reviews:
[{"review_id": "GFRPeulSlW", "reviewer": "Reviewer_ZP8k", "summary": "The authors study the online composite optimization under the Stochastically Extended Adversarial (SEA) model proposed by Sachs et al., 2022. They show that optimistic composite mirror descent (OptCMD), a variant of OMD by [Scroccaro et al., 2023], can achieve regret guarantees that match existing bounds for the SEA model without the regularizer. The bounds are derived for various classes of convex losses including convex functions, exp-concave functions, and strongly convex functions. Furthermore, the authors also propose a universal algorithm that achieves optimal bounds without requiring prior information of the function class.", "questions": "Please see the above.", "limitations": "Please see the above.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and ideas are presented clearly. The authors extend the existing algorithm OMD by [Scroccaro et al., 2023] to the composite loss setting. The main novelty lies in the careful selection of the algorithm's parameters that lead to a good regret bound. I have not gone through the technical details very carefully but the results look interesting and extend the known results from noncomposite to composite loss setting.", "weaknesses": "While the results look nice, my main concern lies in evaluating the novelty of the paper. I would be interested in knowing the challenges faced by the authors to extend the existing analysis of OMD by [Scroccaro et al., 2023] to the composite setting. Especially, what technical challenges does the new setting throw beyond a different selection of algorithm's parameters? Do these challenges require the authors to come up with any technical innovation in their proofs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Many thanks for the constructive reviews!**\n\n---\n**Q1**: What technical challenges does the new setting throw beyond a different selection of algorithm's parameters? Do these challenges require the authors to come up with any technical innovation in their proofs?\n\n**A1**: Thanks for the insightful question! We would like to emphasize that since we focus on the expected regret minimization in composite SEA, simply adjusting the algorithm's parameters is insufficient to achieve the desired bounds. In other words, it is also necessary to delve deeper into the analysis and make the corresponding modifications at intermediate steps to carefully deal with the expectation operation. To illustrate this clearly, we take the general convex case as an example.\n- **A straightforward attempt.** One can configure OptCMD with the parameters in $(6)$, obtain the regret bound of $\\mathrm{Regret}\\_T = O(\\sqrt{V_T})$ by the analysis of Scroccaro et al. [2023], and subsequently apply the expectation operation, i.e., $\\mathbb{E}[\\mathrm{Regret}\\_T] = O(\\mathbb{E}[\\sqrt{V_T}])$ to deliver the expected bound under the composite SEA model. However, it can be verified that such a straightforward approach can only deliver a much looser bound compared to ours;\n- **The underlying reason and our solution.** The underlying reason lies in that the above attempt only takes the expectation after the holistic analysis, neglecting the impact of expectation on intermediate results. To address this issue, we reorganize and dig into the analysis of OptCMD. At the intermediate steps, we isolate the quantities related to $\\sigma_{1:T}^2$ and $\\Sigma_{1:T}^2$ (see Lines $505$-$508$), and carefully manage the effect of expectations on them, ultimately achieving the desired bounds. Similar strategies are also applied in the strongly convex and exp-concave cases.\n\nAdditionally, we also face the following challenges:\n\n- **Analysis for the exp-concave case.** In the original study for OptCMD [Scroccaro et al., 2023], the analysis is limited to the general convex and strongly convex cases. In our paper, we extend the investigation to the *new* exp-concave case, and provide an in-depth analysis for OptCMD with the *new* configurations $(10)$. It should be noticed that our theoretical result for the exp-concave case is versatile. On the one hand, it can reduce to the existing results of $O(d \\log T/(\\alpha T))$ in the fully stochastic environments; on the other hand, it can deliver a tighter regret bound of $O((d/\\alpha) \\log V_T)$ than existing results in the purely adversarial environments. Detailed discussions can be found in Lines $245$-$250$;\n- **Design and analysis for the universal strategy.** As we have elaborated in Lines $289$-$290$, the primary challenge is to develop a meta-algorithm capable of tracking experts according to their performance on composite losses, while maintaining the overall regret bound. To address this issue, we propose our universal algorithm, which is based on the two observations: *the time-invariance of $r(\\cdot)$* and *the accessibility of expert decisions for the current round*. Consequently, we carefully design our universal algorithm with the two distinctiveness: (i) using the expert decisions for the current round to update the weights; (ii) choosing the multi-level MsMwC as the meta-algorithm and employing the composite surrogate loss and optimism in $(13)$ and $(14)$ to track the expert performance. In analysis, we reveal that although the additional regularization term $r(\\cdot)$ is included in the surrogate losses, it can be safely controlled through meticulous analysis, thereby eliminating its impact on the meta-regret. The corresponding analysis can be found in Lines $614$-$617$ for the general convex case, Lines $635$-$643$ for the strongly convex case and Lines $655$-$658$ for the exp-concave case.\n\nIt should be emphasized that although some techniques employed in our work may not be entirely novel, introducing them to the composite SEA model and modifying them to deliver favorable results remain highly non-trivial.\n\n---\nWe greatly appreciate your constructive review and helpful feedback, and we will offer more detailed descriptions of the technical challenges and innovations in the revised version. We hope that our responses can address your concerns, and we are also happy to provide further clarifications during the reviewer-author discussions if necessary.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JoYWBfDTt4", "reviewer": "Reviewer_qCfX", "summary": "This paper investigates online composite optimization within the SEA model. Specifically, it demonstrates that by appropriately adjusting the predictor and step size of the algorithm known as OptCMD, similar regret bounds to those in online optimization within the SEA model can be achieved for general convex functions, strongly convex functions, and exp-concave functions. Additionally, the paper proposes extending the universal algorithm for online optimization by Yan et al. [2023] to online composite optimization.", "questions": "- If the regularizer $r(\\cdot)$ is time-dependent, can the same regret upper bound be achieved with the current analysis? Or are there parts of the analysis that would require non-trivial adjustments?", "limitations": "The limitations of this study are discussed in the conclusion.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studies a problem setting considered important for practical applications.\n- By making simple adjustments to existing methods, the desired theoretical results are obtained.\n- The comparison with existing research is detailed, especially with Scroccaro et al. [2023].\n- Overall, it is well-written and easy to follow.", "weaknesses": "- The techniques proposed in this paper do not offer significant novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Many thanks for the constructive reviews!**\n\n---\n**Q1**: The techniques proposed in this paper do not offer significant novelty.\n\n**A1**: We acknowledge that our research is partially inspired by existing studies, and some techniques employed may not be entirely novel. However, we would like to emphasize that introducing these techniques into the composite SEA model and modifying them to achieve favorable results remain highly non-trivial. Additionally, there also exist unique challenges in our investigated problem (see A1 to Reviewer ZP8k), which necessitate novel technical innovations to address them.\n\nIn the following, we summarize our technical novelties.\n- **An in-depth analysis.** In the composite SEA, a straightforward approach is to simply adjust the parameters of OptCMD according to $(6)$, deliver the intermediate result by the original analysis in Scroccaro et al. [2023], and then take the expectations. However, this approach can only ensure much looser bounds compared to ours (see *A straightforward attempt* in A1 to Reviewer ZP8k). To address this issue, we reorganize and dig into the analysis of OptCMD. At the intermediate steps, we isolate the quantities related to $\\sigma_{1:T}^2$ and $\\Sigma_{1:T}^2$ (see Lines $505$-$508$ for the general convex case), and carefully manage the effect of expectations on them, ultimately achieving a series of favorable theoretical guarantees;\n- **A novel investigation.** Compared to the original study for OptCMD [Scroccaro et al., 2023], we further explore the exp-concave case, and provide an in-depth analysis for OptCMD with the *new* configurations $(10)$. It should be noticed that our result for the exp-concave case is versatile. On the one hand, it can reduce to the existing bound of $O(d \\log T/(\\alpha T))$ in the fully stochastic environments; on the other hand, it can deliver a tighter regret bound of $O((d/\\alpha) \\log V_T)$ than existing results in the purely adversarial environments. Detailed discussions can be found in Lines $245$-$250$;\n- **A crafted universal strategy.** Our universal algorithm is based on the two observations: *the time-invariance of $r(x)$* and *the accessibility of expert decisions for the current round*. These observations provide the foundation for utilizing information from $r(x)$ to track the expert performance. Based on them, we carefully design our universal algorithm with the two distinctiveness: (i) using the expert decisions for the current round to update weights; (ii) choosing the multi-level MsMwC with the composite surrogate loss and optimism in $(13)$ and $(14)$ as the meta-algorithm. With rigorous analysis, we demonstrate that our universal algorithm is able to deliver the desired regret bounds for three kinds of functions simultaneously, without prior knowledge of the function type. To the best of our knowledge, this is the *first* universal algorithm that can explicitly support composite loss functions.\n---\n**Q2**: If the regularizer $r(\\cdot)$ is time-dependent, can the same regret upper bound be achieved with the current analysis? Or are there parts of the analysis that would require non-trivial adjustments?\n\n**A2**: Thanks for the insightful question! We notice that in the purely adversary setting, there exist several efforts investigating the composite loss with the time-dependent regularizer [Scroccaro et al., 2023, Hou et al., 2023]. However, under the more general composite SEA model, analyzing the time-dependent regularizer is quite involved, and necessitates a more in-depth exploration. To be precise, we present the following updating rules of OptCMD for  the time-dependent $r_t(x)$:\n\\begin{align}\n\\hat{x}\\_{t+1}=&\\arg\\min\\_{x\\in\\mathcal{X}}[\\left<\\nabla f_t(x\\_t),x\\right>+r_t(x)+\\mathcal{B}^{\\mathcal{R}\\_t}(x,\\hat{x}\\_t)]\\\\\\\\x\\_{t+1}=&\\arg\\min\\_{x\\in\\mathcal{X}}[\\left<M_{t+1},x\\right>+P_{t+1}(x)+\\mathcal{B}^{\\mathcal{R}\\_{t+1}}(x,\\hat{x}\\_{t+1})]\n\\end{align}\nwhere $M_{t+1}$ and $P_{t+1}(x)$ denotes the estimations for $\\nabla f_{t+1}(\\mathbf{x}\\_{t+1})$ and $r_{t+1}(x)$ in the next round, respectively. Then, we consider the following two scenarios:\n\n- **The known $r_t(x)$ setting**, in which $r_t(x)$ is determined and known to the learner in advance. In this setting, it is natural to choose $P_{t+1}(x) = r_{t+1}(x)$ at the round $t$. In this way, there is no estimation error on $r_t(x)$, so that we can achieve the same theoretical guarantees as those in our paper;\n- **The unknown $r_t(x)$ setting**, in which $r_t(x)$ is selected by the environments either stochastically, adversarially, or in a manner that interpolates between the two extremes, and is only revealed after the learner submits the decision $x\\_t$. In this setting, we can only choose $P_{t+1}(x) = r_{t}(x)$ at the round $t$, and hence, an estimation error on $r_t(x)$, such as $F_T=\\sum_{t=1}^T\\sup_{x\\in\\mathcal{X}}|r_{t}(x)-r_{t-1}(x)|$, is inevitably introduced into the final regret bound. Therefore, to capture the variation of $r_t(x)$ in the composite SEA model, it is necessary to incorporate quantities in terms of $r_t(x)$ that capture the adversarial and stochastic aspects of the environments, which will require additional analysis. Furthermore, it should be noticed that $r_t(x)$ is assumed to be non-smooth, and thus, existing analytical techniques on $f_t(x)$ cannot be directly applied to $r_t(x)$, which also demands extra efforts.\n\nWe are deeply grateful to the reviewer for raising the insightful question. We believe that investigating the time-dependent $r_t(x)$ will further advance the understanding of composite SEA, and we plan to explore it in our future research.\n\n\n**Reference.**\n\n[1] R. Hou et al. Dynamic regret for online composite optimization. ArXiv, 2023.\n\n---\nWe hope that our responses can address your concerns, and we are also happy to provide further clarifications during the reviewer-author discussions if necessary.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MjwZLR2TeY", "reviewer": "Reviewer_tdoW", "summary": "This paper investigates online composite optimization in the regime between stochastic and adversarial environments, establishing theoretical guarantees for three types of time-varying loss functions: smooth and general convex, smooth and strongly convex, and smooth and exp-concave. These bounds not only extend previous results in online composite optimization but also recover those in the special setting without the regularizer. Furthermore, the paper introduces a universal algorithm for online composite optimization that is agnostic to the type of functions and attains optimal bounds for all three cases simultaneously.", "questions": "- The proposed algorithms in this paper are based on optimistic OMD. Is it possible to achieve similar conclusions using optimistic FTRL?\n- When the function $f_t(\\cdot)$ is non-smooth, can we still apply the proposed algorithms?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-organized, with a clear presentation of the background, motivations, and methods. The proofs are also easy to follow.\n- The investigation of the intermediate setting between fully stochastic and adversarial environments is an important topic in the community. This paper enriches this line of work, especially in online composite optimization. The regret bounds relate to both stochastic and adversarial aspects of the environments (i.e., $\\sigma_{1:T}^2$ and $\\Sigma_{1:T}^2$), allowing adaptation to different environments automatically.\n- The authors provide intermediate examples and explain the implications of their bounds in these cases, further highlighting the significance of their findings.", "weaknesses": "- Although the theoretical results are substantial, the paper lacks experimental validation. It would be more compelling if the authors conducted experiments to validate their theoretical results.\n- This paper appears to be an extension of [Sachs et al., 2022; Chen et al., 2023]. The authors should highlight their technical contributions more clearly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Many thanks for the constructive reviews!**\n\n---\n**Q1**: Although the theoretical results are substantial, the paper lacks experimental validation.\n\n**A1**: Thanks for the helpful suggestion! We have conducted empirical studies to verify our theoretical findings. Detailed descriptions can be found in the **General Response**.\n\n---\n**Q2**: The authors should highlight their technical contributions more clearly.\n\n**A2**: Thanks for the valuable suggestion! We have summarized our technical contributions in A1 to Reviewer qCfX. Additionally, we would like to emphasize that although some employed techniques are not entirely new, introducing them to the composite SEA model and modifying them to deliver favorable results remain highly non-trivial.\n\n---\n**Q3**: Is it possible to achieve similar conclusions using optimistic FTRL?\n\n**A3**: Thanks for the insightful question! We believe that **in the static regret minimization, it is possible to achieve similar theoretical guarantees using optimistic FTRL under the composite SEA model**. The reason lies in that optimistic online learning methods, including optimistic OMD and optimistic FTRL, can yield gradient variation bounds, from which we are able to capture the stochastic and adversarial aspects of the environments with careful analysis. In the literature, optimistic FTRL-based methods, such as CAO-FTRL [Mohri and Yang, 2016], have been shown ensuring the gradient variation bounds in general convex and strongly convex cases of online composite optimization. In the exp-concave case, although no optimistic FTRL-based method currently secures the gradient variation bound, we believe achieving such a guarantee is feasible. Therefore, with *an in-depth technical analysis* on optimistic FTRL-based methods, it is possible to achieve similar theoretical results as those presented in our paper for composite SEA.\n\nHowever, we would like to emphasize that **in the dynamic regret minimization, our OMD-based methods offer more advantages compared to FTRL-based methods**. As stated in A3 to Reviewer wJwu, our methods can adapt to non-stationary environments and minimize the more general dynamic regret, whereas FTRL-based methods, to the best of our knowledge, have not been proven to ensure the similar theoretical results in online composite optimization. Moreover, we note that in the standard online optimization without the regularizer,  Jacobsen and Cutkosky [2022] have shown that parameter-free variants of FTRL-based methods cannot deliver a dynamic regret bound better than $O(P_T \\sqrt{T})$ where $P_T$ reflects the non-stationarity of the environments. This finding partially reveals the limitation of FTRL-based methods in the dynamic regret minimization.\n\n---\n**Q4**: When the function $f_t(\\cdot)$ is non-smooth, can we still apply the proposed algorithms?\n\n**A4**: Below, we discuss the importance of the smoothness in our methods, and the potential modifications  for handling the non-smooth $f_t(x)$.\n\n- **Importance of smoothness.** In our analysis, the importance of the smoothness on $f_t(x)$ lies in decoupling the stochastic and adversarial aspects of the environments from the performance of algorithms. To be more precise, the smoothness is employed to extract $\\sigma_{ 1:T }^2$ and $\\Sigma_{1:T}^2$, each of which capture the stochastic and adversarial difficulties in the composite SEA model respectively, from the difference between $\\nabla f_t(x_t)$ and $M_t$. By choosing the  optimism $M_{t} = \\nabla f_{t-1}(x_{t-1})$, such an extraction introduces only an additional stability term, i.e., $\\sum_{t=2}^T || x_t  -  x_{t-1} ||_2^2$, which is typically controllable and can be retracted with careful analysis;\n\n- **Modification to non-smoothness.** To handle the non-smooth $f_t(x)$, a classical approach is to apply the implicit update  [Campolongo and Orabona, 2020, Chen and Orabona, 2023], which  replaces the linear approximation of $f_t(x)$ in the update rules with the original function  $f_t(x)$ itself. Following the idea of the implicit update, one possible attempt  is to modify the update rules of OptCMD in the following ways:\n\\begin{align}\n\\hat{x}\\_{t+1}=&\\arg\\min\\_{x\\in\\mathcal{X}}[\\left<\\nabla f_t(x\\_t),x\\right>+r(x)+\\mathcal{B}^{\\mathcal{R}\\_t}(x,\\hat{x}\\_t)]\\\\\\\\x\\_{t+1}=&\\arg\\min\\_{x\\in\\mathcal{X}}[f_t(x)+r(x)+\\mathcal{B}^{\\mathcal{R}\\_{t+1}}(x,\\hat{x}\\_{t+1})]\n\\end{align}\nwhere $\\langle M_{t+1},x\\rangle$ is replaced with $f_t(x)$. As mentioned above, the smoothness of $f_t(x)$ is crucial for revealing the adversarial and stochastic aspects of the environments. Therefore, in the non-smooth setting, the primary challenge lies in designing an analysis strategy that can still capture the two aspects of the environments without using the smoothness. This seems highly non-trivial, and we plan to investigate it in future work.\n\n**Reference**.\n\n[1] A. Jacobsen and A. Cutkosky. Parameter-free mirror descent. COLT, 2022.\n\n[2] N. Campolongo and F. Orabona. Temporal variability in implicit online learning. NeurIPS, 2020.\n\n[3] K. Chen and F. Orabona. Generalized implicit follow-the-regularized-leader. ICML, 2023.\n\n---\nWe hope that our responses can address your concerns, and we are also happy to provide further clarifications during the reviewer-author discussions if necessary.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aWd76yBT7w", "reviewer": "Reviewer_wJwu", "summary": "This paper studies the problem of online composite optimization under the Stochastically Extended Adversarial (SEA) model, where the environments select loss functions in a manner that interpolates between fully stochastic and fully adversarial scenarios. Specifically, the authors establish regret bounds for three kinds of loss functions and introduce a multi-level universal algorithm that can achieve these bounds simultaneously, without prior knowledge of the loss functions. These theoretical guarantees are interesting as they can not only recover previous findings for online composite optimization in both fully stochastic and adversarial environments but also lead to new results, including the first problem-dependent bound for exp-concave cases in the full adversarial setting.", "questions": "For questions please refer to the weaknesses section.\n\nsome suggestions:\n\n1. I recommend relocating the Implications Section to follow the Universal Strategy Section. Such reorganization will enhance the logical flow and ensure the continuity of the narrative.\n\n2. Currently, this paper primarily focuses on static regret minimization. I am curious whether we can establish the more general dynamic regret bounds in the investigated setting. I believe that theoretical insights into dynamic regret would also be significant for the field.", "limitations": "The authors discuss some limitations & future works in the Conclusion. And there is not potential negative societal impact, since this paper is purely theoretical.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The presentation is excellent, and the proof is readily comprehensible.\n\n2. The investigated problem of online composite optimization between stochastic and adversarial environments is significant, as it not only bridges two previously separate fields in online composite optimization but also extends the special case without the regularizer.\n\n3. The theoretical results are comprehensive and generalize previous findings in two extreme settings. Moreover, the authors clearly discuss the inadequacies of directly applying the existing work by Scroccaro et al. [2023] in the intermediate setting.", "weaknesses": "My only concern is that this article appears to be purely theoretical at present and lacks empirical validation. I believe that some experimental studies could further strengthen the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Many thanks for the constructive reviews!**\n\n---\n**Q1**: I believe that some experimental studies could further strengthen the theoretical results.\n\n**A1**: Thanks for the helpful suggestion! We have conducted empirical studies to verify our theoretical findings. Detailed descriptions can be found in the **General Response**.\n\n---\n**Q2**: I recommend relocating the Implications section to follow the Universal strategy section.\n\n**A2**: We truly appreciate your advice, and will relocate the Implications section in the revised version to make it more logically fluent.\n\n---\n**Q3**: I am curious about whether we can establish the more general dynamic regret bounds in the investigated setting.\n\n**A3**: Thanks for the insightful question! Compared to the static regret minimization, minimizing the dynamic regret is more challenging since it needs to build a universal guarantee over any comparators. In the composite SEA, we have also attempted to optimize the dynamic regret. Theoretically, we can achieve a provable dynamic regret bound of $O((\\sqrt{\\sigma_{1:T}^2} + \\sqrt{ \\Sigma_{1:T}^2})(P_T+1))$, where $P_T$ denotes the path-length of the comparator sequence, and a tighter $O(P_T + (\\sqrt{\\sigma_{1:T}^2} + \\sqrt{ \\Sigma_{1:T}^2})\\sqrt{P_T+1})$ dynamic regret bound based on the meta-expert framework. Both two results can also reduce to the purely adversarial and stochastic setting in online composite optimization with the specifications on $\\sigma_{1:T}^2$ and $\\Sigma_{1:T}^2$. We believe the two results can further broaden the field of composite SEA, and will add them in the extension version.\n\n---\nWe hope that our responses can address your concerns, and we are also happy to provide further clarifications during the reviewer-author discussions if necessary.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their constructive comments and appreciations of our work. Since both Reviewers tdoW and wJwu  suggest conducting experiments to validate our theoretical results, we present the following general response regarding the empirical studies.

---
**Setup.** In our paper, we show that OptCMD with suitable configurations is able to achieve a series of favorable theoretical guarantees in composite SEA. Moreover, for the practical scenarios where the prior knowledge of loss functions is unavailable, we propose a novel universal strategy, called USC-SEA, which can achieve the desired regret bounds for three cases in composite SEA simultaneously. To verify our theoretical findings, we conduct experiments on the mushroom datasets from the LIBSVM repository [Chang and Lin, 2011], and consider the following online classification problem. At each round $t \in [T]$, the learner receives a data $(\mathbf{x}_t, y_t) \in \mathbb{R}^d \times$ {$-1, 1$} with $d = 112$. Then, the learner plays the decision $\mathbf{w}_t$ from the ball $\mathcal{X}$ with the diameter $D=20$, and suffers a composite loss
$$\phi_t(\mathbf{w}_t; \mathbf{x}_t, y_t) = f_t(\mathbf{w}_t; \mathbf{x}_t, y_t) + \lambda r(\mathbf{w}_t),$$
where we set the hyper-parameter $\lambda = 0.001$. The dataset used in the experiments is considered to be sampled from an unknown distribution, possessing the inherent stochastic property. To simulate the stochastically extended adversarial environments, we perturb the dataset by randomly flipping the labels of $10$% data as the adversarial corruptions. Then, we sequentially pass each data to the learner.

We consider the following three types of loss functions. 
- For the general convex case, we choose the smooth and convex cross-entropy function as the time-varying function: $$f_t(\mathbf{w}_t; \mathbf{x}_t, y_t) = -y_t \log \sigma (\mathbf{x}\_{t}^\top \mathbf{w}_t) - (1-y_t) \log (1-\sigma(\mathbf{x}\_{t}^\top \mathbf{w}_t)),$$
where $\sigma(\cdot)$ denotes the sigmoid function, and utilize the $\ell_1$-norm regularizer $r(\mathbf{w}_t) = ||\mathbf{w}_t||_1$. Therefore, the composite function takes the form of:$$
\phi(\mathbf{w}_t; \mathbf{x}_t, y_t) = -y_t \log \sigma(\mathbf{x}\_{t}^\top \mathbf{w}\_t) - (1-y_t) \log (1-\sigma(\mathbf{x}\_{t}^\top \mathbf{w}_t)) + \lambda ||\mathbf{w}_t||_1;$$
- For the strongly convex case, we employ the cross-entropy functions with the $\ell_2$-norm regularizer as the time-varying function: $$f_t(\mathbf{w}_t; \mathbf{x}_t, y_t) = -y_t \log \sigma (\mathbf{x}\_{t}^\top \mathbf{w}_t) - (1-y_t) \log (1-\sigma(\mathbf{x}\_{t}^\top \mathbf{w}_t))+\delta||\mathbf{w}_t||_2^2,$$which is $2\delta$-strongly convex, and still leverage the $\ell_1$-norm regularizer. Hence, the composite loss function is in the form of:$$
\phi(\mathbf{w}_t; \mathbf{x}_t, y_t) = -y_t \log \sigma(\mathbf{x}\_{t}^\top \mathbf{w}\_t) - (1-y_t) \log (1-\sigma(\mathbf{x}\_{t}^\top \mathbf{w}_t))+\delta||\mathbf{w}_t||_2^2+\lambda||\mathbf{w}_t||_1;$$
- For the exp-concave case, we utilize the logistic function as the time-varying function:$$f_t(\mathbf{w}_t; \mathbf{x}_t, y_t) = \log (1 + \exp (-y_t \mathbf{w}_t^\top \mathbf{x}_t)),$$which is exp-concave and smooth [Hazan et al., 2014], and still employ the $\ell_1$-norm regularizer. The composite loss function is shown below:$$\phi(\mathbf{w}_t; \mathbf{x}_t, y_t) = \log (1 + \exp (-y_t \mathbf{w}_t^\top \mathbf{x}_t)) + \lambda ||\mathbf{w}_t||_1.$$
      
---
**Contenders.** For the general convex and strongly convex cases, we compare our methods with OGD [Zinkevich, 2003], COMID [Duchi et al., 2010] and Optimistic-OMD [Chen et al., 2023]. For the exp-concave case, we choose ONS [Hazan et al., 2007], ProxONS [Yang et al., 2023] and Optimistic-OMD [Chen et al., 2023] as the contenders. All parameters of each method are set according to their theoretical suggestions. For instance, in the general convex case, the learning rate is set as $\eta = ct^{-1/2}$ in OGD, and $\eta = cT^{-1/2}$ in COMID, $\eta_t = D (c + \bar{V}_{t-1})^{-1/2}$ in Optimistic-OMD  where $c$ denotes the hyper-parameter  selected   from {$10^{-3},10^{-2},\cdots,10^{4}$}.

---
**Results.** All experiments are repeated ten times, and we report the instantaneous loss, the cumulative loss and the average loss against the number of rounds in Figure 1 for the general convex case, Figure 2 for the strongly convex case and Figure 3 for the exp-concave case. From the experimental results, it is evident that adversarial corruptions cause considerable fluctuations in the instantaneous loss across different methods. Moreover, we observe that in the three cases of composite SEA, OptCMD incurs lower losses compared to baseline methods, and our universal method, USC-SEA, achieves similar performance to OptCMD without the prior knowledge of loss functions. This phenomenon can be attributed to their ability to adapt to the composite SEA environment, and their explicit support for handling the non-smooth component $r(\cdot)$.

**Reference.**

[1] C.-C. Chang and C.-J. Lin. Libsvm: A library for support vector machines. ACM TIST, 2011.

[2] E. Hazan et al. Logistic regression: Tight bounds for stochastic and online optimization. COLT, 2014.

[3] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML, 2003.

[4] E. Hazan et al. Logarithmic regret algorithms for online convex optimization. FTML, 2007.

Meta-review: This paper provides algorithms for the "stochastically extended adversary" setting in online optimization with composite losses. Happily, the resulting regret bounds are the intuitive result: the same as the non-composite case with the composite term not appearing in the bound.

Overall reviewers are very positive about this work, so it is recommended for acceptance.
Decision: Accept (poster)