Parameter-free Algorithms for the Stochastically Extended Adversarial Model
Authors: Shuche Wang
Adarsh Barik
Peng Zhao
Vincent Y. F. Tan
Venue: NeurIPS 2025 poster ()
Keywords: Online Convex Optimization
Parameter-free Algorithm
Primary area: theory

Abstract: We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish a comparator-adaptive algorithm for the scenario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of $\tilde{O}\big(\Vert u\Vert_2^2 + \Vert u\Vert_2(\sqrt{\sigma^2_{1:T}} + \sqrt{\Sigma^2_{1:T}})\big)$, where $u$ is the comparator vector and $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$ represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this to the more general setting where both $D$ and $G$ are unknown, attaining the comparator- and Lipschitz-adaptive algorithm. Notably, the regret bound exhibits the same dependence on $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.

Parameter-free Algorithms for the Stochastically Extended Adversarial Model
Shuche Wang' Adarsh Barik²
Peng Zhao
Vincent F. Tan 1,566 T
Institute of Operations Research and Analytics, National University of Singapore
2 Department of Computer Science and Engineering, Indian Institute of Technology Delhi National Key Laboratory for Novel Software Technology, Nanjing University
School of Artificial Intelligence, Nanjing University
Department of Mathematics, National University of Singapore
Department of Electrical and Computer Engineering, National University of Singapore
shuche. wangou, nus edu, adarshbarik10iit ac.in, zhaop@lamda, wonida.njj..... nju. edu. en, vtandnus. edu. ag
Abstract
We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specifee parameters, such as the diameter of the domain and the Lipschitz constant of the loss functions G, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish comparator adaptive algorithm for the nario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of (1 + [|ul|a( Voi.r + VEi.r)), where u is the comparator vector and ofr and Dir represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this the more general setting where both D and G are unknown, attaining the comparator- and aipsciit algorithm. Notably, the regret bound exhibits the same dependence on oir and Ei.r, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.
Introduction
We focus on online convex optimization (OCO) [13, a broad framework for sequential decision- making. In each round t [T]. learner chooses point I; from convex set X' C Rdd The environment then discloses a convex function ft : X' + R, after which the learner incurs loss fxx)) and updates their decision. The standard way to show the performance is via the regret, the total loss relative to comparator X, defined Ri(")) ΣT f(( ET= Se(u).
For convex problems, the regret can be bounded by O(VT) 4. which is known be minimax optimal 5.. OCO encompasses two primary frameworks: adversarial OCO 4 b). which aims minimize regret against arbitrarily chosen loss functions, and stochastic OCO (SCO) [6] 77) which minimizes excess risk under i.idd losses. While both frameworks are well-studied, real- world scenarios typically fall between these theoretical extremes of purely adversarial or stochastic settings. The Stochastically Extended Adversarial (SEA) model proposed in [8] bridges the gap between traditional adversarial and stochastic frameworks in OCO. This hybrid approach serves as an intermediate formulation that captures aspects of both adversarial OCO and SCO settings.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison of the regret bounds of existing results and our proposed algorithms.
Algorithm
Free of D
Free of G Bound on Expected Regret [u)]
OFTIR, OMD
0 o δ Vo + /
X
1/
(Sachs et al. [8] Chen et al.
OONS
(Thearm
CA-OONS
/
1ull1 + || V o + EiTT
(Thearem 1
CLA-OONS
/ /
@1lulB((oir
v |ull + von U 11r
(Theorem 1.5
Optimal performance in OCO, SCO, and SEA models typically relies careful step-size tuning, which requires prior knowledge of problem parameters such as the diameter of the decision set and Lipsehitz constants. However, these parameters are often unknown in practice, motivating the development of parameter-fre algorithms that achieve comparable regret without requiring such oracle information. Specifically, parameter-free algorithms include (unknown diameter D) and Lipschitz-aduptive algorithms (unknown Lipschitz constant G). A related challenge arises when the decision set X' is unbounded, allowing adversaries induce arbitrarily large losses for linear functions. Traditional methods often circumvent this by assuming bounded domains, where sup,, || y112 S D. Consequently, developing OCO algorithms that remain effective under both unknown parameters and unbounded domains is significantly more challenging than in classical settings 9 10
algorithms
To address these challenges, we propose "parameter-free" algorithms for the SEA model, accom- modating potentially unbounded decision sets. Using the Optimistic Online Newton Step base algorithm, we systematically relax assumptions: first tackling the case of an unknown domain diameter D (potentially infinite) with known Lipschitz constant G, and then extending to the more complex scenario where both D and G are unknown. In the SEA model, at each time step t, the learner selects a distribution D, over functions and incurs loss fi (zt). where ft sampled from Dt- The expected gradient is denoted as (z( = E,,DD, (z)).
Main Contributions. Our main results and contributions are summarized as follows.
(1) We begin by introducing the Optimistic Online Newton Step (OONS)
foundational algorithm. The OONS algorithm is inspired by [IO]; however, we incorporate an adaptive step-size 7 rather than a fixed step-size throughout the learning process. When the parameters D and G are known, we demonstrate that OONS achieves expected regret bound of Ö(vo
v ) matching the state-of-the-art results terms of dependence on the cumulative stochastic variance oF. and the cumulative adversarial variation E7,7 g 12]. This establishes solid foundation for our subsequent extensions to parameter-free algorithms.
(2) We introduce the first parameter-free (comparator-adaptiv) algorithm for the SEA model that remains effective when the domain diameter D is unknown, provided the Lipschitz constant G is known. This is achieved through meta fratme-rawwookk wherein each base learner operates within distinct bounded domain, complemented by the Multi-scale Multiplicative-Weit
with Correc- tion (MsMwC) algorithm [10] for the meta-algorithm's weight updates. This construction yields an expected regret bound of Ö(I + || 12 oo. + / )), where the bound scales with the noom of the comparator without requiring prior knowledge of the domain diameter D.
(3) We further consider setting in which both the domain diameter D and the Lipschitz constant G are unknown. By devising appropriate update rules for the estimation of the domain diameter, we establish an expected regret bound Ö ([ VE . + || + Voi. + Bi.r) where Tirr captures the deviation of the stochastie gradients (excluding squared norms), and GI.r denotes the sum of the maximum expected gradients over the sequence.
A summary of our results and the best existing results are included in Table Due to space limitations,
we hide the Lipschitz constant G in the Ô(-) -notation in the regret bound of CLA-OONS algorithm.

---

1.1
Related Work
The SEA model [ is motivated by foundational insights from the gradual-variation online learning. The study of gradual variation can be traced back to the works of [13] and [14], and it has gained significant traction in recent years [15] 16
[8 19]. Notably, the SEA model has emerged as 18] 19]. Furthermore, this model serves as bridge between adversarial OCO and SCO. This intermediate framework is comprehensively
17
practical application of the gradual variation principle 16
understood in the context of expert prediction 220 21 and the bandit setting [2 23
Parameter-free online learning has emerged as a fundamental advancement in machine learning, offering solutions to the critical challenge of parameter tuning in practice. In the baseline scenario, when both the diameter parameter D) and the gradient bound G' are known, algorithms leveraging Follow the Regularized Leader or Mirror Descent principles achieve the minimax optimal regret bound of (T) I O(GDVT) (2). The field has subsequently progressed to address more practical scenarios where complete parameter knowledge is unavailable. Notably, in the Lipschitz-adaptive setting, it is still possible to attain the same optimal regret bound, differing only by constant factors [24] (25] Xie et al. [18] extended these principles to gradient- variation online learning.
In the aappaaratoo-adapttio setting, the online learning problem becomes substantially more challeng- ing due to the unknown comparator's magnitude, which could cause the al algorithm's predictions to significantly deviate from the optimal solution, leading to a large regret. For this challenging scenario,
a key result has been established as Ru) < O([uu|==GVT) 226 24 27 For scenarios where both parameters D and G are unknown, significant progress has been made recently. Cutkosky [25] developed an algorithm with Rr( s x + ||u|| (vl22GVT) while Mhammedi & Koolen (28
achieve (u) I { |ull2 maxigr (E, / max, I19=l12)). An alternative approach
by (29 presented the regret bound Rt(w)) S O (I|u| 1 GVV... More recent advances including M
achieve the regret (u) s Ó(G]|ul|2 + (VT under the condition that subgradients satisfy
l1a.l12 S G+ G L||xell2- Cutkosky & Mhammedi [30 further improve (G |u]l
Besides parameter-fre free algorithms for OCO. 31 and [32 studied the parameter-fiee stochastic gradient descent (SGD) algorithms. Khaled et al.
333 introduced the concept of "tuming-frre free"" SGD within polylogarithmic
algorithms, which achieve performance comparable to optimally factors, requiring only approximate estimates of the relevant problem parameters.
Although this series of works on parameter-free algorithms in OCO provides valuable insights, these approaches cannot be directly applied to attain the optimal regret bounds for the SEA model without prior knowledge of parameters. This limitation stems from the fact that the desired bounds for the SEA model should be expressed in terms of the variance-like quantities oi. and E rather than the time horizon T. While Sachs et al. [8] have attempted to address this issue by proposing an algorithm that adapts to an unknown strong convexity parameter, their step-size search range still depends on both D and G, thereby restricting its fully parameter-frr adaptivity.
2 Problem Setup and Preliminaries
In this section, formulate the problem setup of the Stochastically Extended Adversarial (SEA) model, present the existing results, and discuss the key challenges.
2.1 Problem Setup of the SEA Model
In iteration E [T), the learner selects a decision 2; from a convex feasible domain X' C Rd and nature chooses a distribution D, from set of distributions over functions. Then, the learner suffers a loss fxxx)), where ft random function sampled from the distribution D,. The distributions are allowed to vary over time, and by choosing them appropriately, the SEA model reduces to the adversarial OCO, SCO, or other intermediate settings. Additionally, for each t E [T']. the (conditional) expected function is defined as Fz) EG,DD, [f((x) and the expected gradient is defined as FF(x)) = EE,,D [ fc (z)]. We define G := suprex [VVF(() || to be the largest norm
of the expected gradient, and use the shorthand G1.T to denote the sum Σ 6..
3

---

Due to the randommess in the online decision making process, our goal in the SEA model is to bound the expected regrer with respect to the randomness the loss functions fo drawn from the distribution
Dj against any fixed comparator u E X, defined as [u)] & E f(())) - E capture the characteristics of the SEA model, we introduce the following quantities. For each E [T], define the (conditional) variance of the gradients and cumulative stochastic variance respectively as
ft (u))), To
of = sup E, E, (I..D.IIVVAA V+(()) (x) xEX
c.r =
Σ
of
which reflect the stochasticity of the online process. Additionally, we introduce the concepts of stochastic gradient deviation and cumulative gradient deviation to characterize the stochastic variation of gradients, without the squared norm. The stochastic gradient deviation is defined de
suPxex EF [IV [+)) - (x))ll) and the cumulative gradient deviation is defined as 01:77 =
E E oz]. The cumulative adversarial variation is defined
Σ = E
Σ sup EE
where Fo = O, reflecting the adversarial difficulty. This work aims to provide expected regret bounds that depend on problem-dependent quantities such as oi.,, Ei.r. and $1.7 instead of T.
Below, we present several assumptions. Note that results do not rely all of these assumptions; rather, specific assumptions are required for each result, which will be explicitly stated in the theorem.
Assumption 2.1 (Boundedness of gradient norms). The gradient norms of all loss functions are bounded by G, i.c., m max |/ (z)]l2 S G.
Assumption 2.2 (Boundedness of domain). The diameter of the convex set X' (the feasible domain) is bounded by D i.e., suPa,yex || - vll2 S D.
Assumption 2.3 (Smoothness). For all / E [T]. the expected function F, is L-smooth over X, i.e., [VFF(()) (v) S L||z - al1a for all 2, y X. Assumption 2.4 (Convexity). For all t [77, the expected function F; is convex on X'
Notations. Given a positive definite matrix A, the norm induced by A is ||>|| = vr Ar. AN denotes the (N 1) -iimensional simplex. Let v X be continuously differentiable and strictly convex function, the associated Bregman divergence is defined as (I, y) = xb(x) (vy)
(Vv(y), x - v). The notation (()) hides constants and Ö-) additionally hides polylog factors.
2.2 Existing Results for the SEA Model
Bounded domain and gradient norm. Sachs et al. X established a regret bound for the SEA model using both Optimistic Follow-The-
Bealoo-The-Regulaazzz------ Regularized-Leadee (OFTRL) and Optimistic Mirror Descent (OMD), given by [1)) O( O + v / achieved by setting the step-size as Y
Esgl min( ( ? 10emm D) (9g.- mm-lml) where = fx(z) and m, = =9--1- Similarly, Chen et al. 12 derived the same bound by Optimistic Online Mirror Descent (OMD) with the step-size ?/t
D²
V5-46a-B1_1 where V=-1= --1
m,,12 1 and 5 >
In of the above settings, the optimal step-size 7/e is dependent on the parameters D (the diameter of decision set X') and G (Lipschitz constant), there has been natural motivation to develop algorithms that achieve similar regret bounds without knowing such parameters a priori. We term such algorithms as "parameter-free" algorithms for the SEA model.
Parameter-free algorithm for the SEA model. Theorem 5 in (27 demonstrates that the parameter- free mirror descent algorithm can be extended to enjoy gradient-variaatio regret of Ry) <
Ö([[u||2y Σr_ (v,) (z))ll) In fact, this can directly yield an expected regret bound for the SEA model scaling with क.. : E Din EIND [sup, ([) (x:)))) i.e.,
(u)l 5 [lulla (Vöir + v2(.7)
(2)

---

Algorithm 1 Optimistic Online Newton Step (OONS)
Input: learning rate 7/: > 0, 21 O.
1: for L= 1 1.....,, T do
2: Receive optimistic prediction me and range hint 2t-
3: Update Iy = arg min (a, mi) ) + Dv (2, a{}} where vx(x) = 2/11111,, and A = 42
E 77 (V m,)(V. (V, mm,) + +4m 2
4: Receive Ot = V (xx)) and construct V. +==00 St + 3.2m (0x, 9t - ma) (ge- - m²).
5: Update T/41 arg mix V.) + Do, x(),
6: end for
Akin o.. oir defined in [12] also captures the stochastic nature of the SEA model. Furthermore, in the worst case, the bound in ( reduces to O([[u]|2v [T]]ulllvVT, matching the best available problem- independent bound. The outer expectation in the definition of oi. accounts for the randomness in the choice of the distribution Dj at each step. Refer to Appendix B.I for a self-contained proof of (2).
Key Challenge. However, we emphasize that our goal is to obtain regret bounds scaling with o.... as defined in [D. As pointed out in previous work on the SEA model [12 Remark 9], of is more favorable than .... First, from mathematical perspective, the latter is generally larger due to the convexity of the supremum operator. The difference between o and 7 can, fact, be arbitrarily large. The detailed comparison is provided in Appendix [ Second, from an algorithmic perspective, an algorithm with a regret bound involving कं. typically involves an implicit update, which operates on the original function and is significantly more costly than standard first-order methods (see Remark 10 in (22). Third, achieving regret bounds scaling with oi. typically requires leveraging the Regret Bounded by Variation in Utilities (RVU) property (34), which captures the regret to be bounded not only by the gradient variations but also an additional negative stability term. Formally, an algorithm satisfies the RVU property if its regret upper bound is in the form
of Df T (2= (x* - Iz, Ue) S a + Eنn ||u u - Σi | 1 x2-1 for some constants a, 1, > 0. This structure enables finer control over the regret by explicitly analyzing trajectory stability, establishing profound connections to game theory [3 35 and accelerations in smooth optimization [36]. Consequently, the key challenge lies in how to achieve this preferred of -scaling
without knowledge of D and G for unbounded domains.
3 Optimistic Online Newton Step (ONS) for the SEA Model
In this section, different from the Optimistic follow-the-reeee thheerrgularized--eeaeee (OFTRL) 8 and Opti- mistic mirror descent (OMD) [12, we first introduce the Optimistic Online Newton Step (OONS) algorithm as the base algorithm for the "parameter-free" algorithms to be introduced later. This algorithm is summarized in Algorithm
The ONS algorithm (6] is an iterative algorithm that adaptively updates a second-order (Hessian- based) model of the loss, allowing more efficient gradient-based updates and improved regret bounds. OONS also maintains two sequences { and {a T like OMD and OFTRL, which achieved by introducing the optimistic prediction m,, Chen et al. [10] also considered combining their Multi- scale Multiplicative-weii
with Correction (MsMwC) algorithm with this variant of the ONS algorithm. However, the step-size 7 is fixed in their algorithm and the MsMwC algorithm is applied to learn the optimal T). Different from it, in OONS, we consider adaptive step-sizes nh
Theorem 3.1. Suppose that l|g: mellz 2 < 2t, 2, is non nec-decreasing in t, 64n I for all E [T]. and 17, is non-increasing in t.. Then, OONS guarantees that
Ru( < O (al((Toer//a)) 1 =fl1u||B + D(2r =1) Eie me m22
2f E 1
Fz 113
where r is the rank of Et (gt mm))
Next, we verify that OONS also works for the case with known parameters D, G. and we can also
obtain similar regret bound [8] and [2]. The regret bound of OONS for the SEA model with
5

---

Algorithm 2 Comparator-adappix algorithm for the SEA model (CA-OONS)
Input: Lipschitz constant G.
I: for 1= , T do
2: Create N log T base-learners. Each base-learner [N] runs OONS with stepsize 1/.
3: Each base-learner provides z².
4: Run Algorithm to to obtain W; AN-
5: The final decision is It Σj= Wt.
6: end for
known parameters D and G is presented below. We specify the adaptive step-size for all E [T] as
7 =mmin min
64Dzr
--- I19. ma DV
Since G is known, we have 11 mell2 S at 2G, Vt [T]] and th. is defined in terms of or here.
Theorem 3.2. Under Assumptions 2.1 2.2 2.3 and 2.4 OONS with step-size Th given in (4).
Vi- and Ze 2G for all t E (T) ensures E (i)) = 0 0. V
Remark 3.3. Theorem 3.2 achieves the same (up to logarithmic terms) dependence o.r and Σ as in 8 and 12. The primary reason to use OONS as the base algorithm instead OMD 12 is
that the final regret bound for OMD typically depends DV D 11g mm l12. In scenarios when D is unknown or potentially infinite, like Section 4.2 this might lead to (T) regret bounds. By contrast, OONS leverages adaptive second-order information, which helps remove (or substantially reduce) explicit dependence on D. In (.) the only term relevant to is ( 21), which solely depends on the starting and ending points, 21 and 27.
4 Parameter-free Algorithms for the SEA Model
In this section, we develop parameter-free algorithms for the SEA model, building on OONS which we use the base algorithm. Moreover, we allow the decision X to be potentially unbounded throughout this section, i.e. D = oo in Assumption 2.2 In Section 4.1 we present a comparator- adaptive algorithm for the SEA model for unknown D but known G, and then, we develop the comparator- and Lipschitz- algorithm where both D and G are unknown in Section
4.1
Comparator-adaptin algorithm
We now propose the pappaarttorAdaaiivv Optimistic Online Newton Step (CA-OONS) algorithm for the unknown D (potentially infinite) but known G case by using meta-base algorithm framework. Recent works in [TO] and [ addressed the challenges associated with unbounded domains by devel- oping base-learner framework. Building on this philosophy, we propose CA (A-OONN((lloorimmm where we adopt the MsM algorithm [10] as the meta algorithm.
The algorithm uses N base-learners. For any base-learner i E [N], the regret can be decomposed as
T
RT(") = Si -MW f((a)) Σ fa(xt)) + Σ Sa(at) Ed(w)
1=1 1=1
t=1
Meta Regret
Regret
Let A, denote the base algorithm for the i-th base-learner. We denote R (u) = ET f((xt) Σi [u) as the base regret by taking A; as the base algorithm. Moreover, the final decision x, is a weighted-average of all the base-learners' decisions: It = Σj= We with we E AN. As such,
T
RT(u) S (R((1))
Σ
(1, wi - w:))
(5)

---

Algorithm 3 Meta Algorithm
Input: Additional expert set S defined in
Initialization: pi E As such that P1,e x By for all & E E.
1: for tort= ,,...,, T do
2: Construct h4 R. with h2 = (V
3: Each expert &s E S runs MsMwC with step-size Bbg and plays w/ E AN.
4: Receive w. for each & E S and compute H = (wt h2)-
5: Compute p: = arg pE (p, Hi) + (p,,p)))
6: Play Wi = -EKES uf E AN.
7: Receive & E R. Define I = (wt, (i) and by = 32,32 (T H
8: Compute pb+1 = arg pEAs (p, L + by) + Do(p.Pt).
9:
end for
Table 2: Three-layer hierarchy of CA-OONS
Layer
Algorithm
Loss
Optimism
Decision
Output
Top Meta
MsMwC
(Lf)
(HF)
Pt E As
We =
Σn kw w
Middle Meta
MsMwC
4 E RN
h4 E R.
(W)) E AN
Base
OONS
f((((())
(El)SEN E X2
x
where 4 E R.V. with e = (z)(( x²) and wi is a vector in AN whose j-th component is (wi) = if and 0 otherwise. Refer to Appendix D.2 for the proof of (5)
We first consider the base algorithm. Specifically, for each base-learner j E [N], impose constraint that it operates within X, = (x ||=||| < Dj and æ E }},, where D, = 2). Then, we define of = V fz (z!)) and m V (x Each base-learner j [N] runs OONS with step-size
m min {
1
64DD2rr' Djy V ll m
which depends on Dy instead of D in OONS. Hence, each base-learner j can update z via OONS N with step-size v/. Since the final decision is T, j=1 Wr,ar/ need to adopt a meta-algoriihh to learn the weight parameter W, AN.
As mentioned above, we introduce constraint that each base-learner j [N] operates within Dj- bounded domain. We can consider this as a "multi-scale" base-learner problem (37 9 10 where each
base-learner has a different loss range such that |e/1 < GD, since ! (x xz). ) We choose the Multi-scale Multiplicative-weigee
with Correction (10) as the meta- meta-algorithm to learn Wt, which is implemented based on the MsMwC [10] Details of MsMwC are presented in Appendix D. Specifical... we define new expert set
(asMwC)-Master algorithm (Algorithm 2 in
S= (k E Z 3j [1, 52,
For all & E S, the step-size of the MsMstcr algorithm is to 33 -2.2. Each expert A E S runs the MsMwC algorithm with w/ being uniform over 2(k), where Zz = {j E [N]: :]:GD. GD, < 2x-2). }. Moreover, each base MsMwC algorithm only works in the subset 2(k), i.c., w, E AN with ut. = 0 for all j & (k)). We can view CA-OONS (Algorithm as three-layer structure, where the meta-algorithm (Algorithm 3 itself consists of two layers, which we refer to as meta top and meta middle. Also, the base layer OONS algorithm. For clarity, we summarize the notations of the three-layer hierarchy for CA-OONS in Table 2
In the following, we provide the expected regret guarantee for CA-OONS.
7

---

Theorem 4.1. Let D be unknown (potentially infinite). Under Assumptions 2.7 OONS provides the following regret
2.3 and 2.4
CA-
[1u1 lolllittllllll + +
[w)
(8)
This regret guarantee is referred to as "comparator-adaas adaptive" because it depends directly on the norm of the comparator, ||u]]2, rather than explicitly relying on the diameter of the decision set, D. Notably, when considering the constrained decision set with a diameter D. our regret bound immediately
recovers the result [u]] = Õ(D² + D(voi. + VE(,T) established in [8
One limitation of our regret bound (8) is that when particularizing to adversarial OCO, it achieves only worst-case regret bound, which falls short of the best-known ([Ilu]] re- gret bound (24 27 28 However, in the following two remarks, we will justify the ||u]] deleedddddeeece in the gradient- variattin regret and emphasize the fundamental challenge of achieving adaptivity from the gradient-variate variation bound (for smooth functions) to the worst-case bound (for the non-smooth case) when the decision set of online learning is unconstrained.
an 0[[1u|13 + | 2
Remark 4.2 (Dependency on |wll²). Recent studies have established the connection between gradient- variation online learning and accelerated offiin optimization through advanced online-to-batel conversions 36 38). Specifically, let do = I| 2r.l22 denote the distance of an initial point zo to variation online algorithms using first-order information correspond to accelerated convergence rate of O (LdB/TT) via the stabilized online-to- regret bounds translate to an O(Go// /T) rate through the standard conversion [.. In this context, we hypothesize that the ||ul|2 term may be unavoidable in gradient- variiatoo regret for unconstrained online learning, paralleling how the di term also appears in the accelerated rate of unconstrained offline optimization. Remark 4.3 (Adaptivity between gradient-variation bound and worst-case bound). We argue that worst-case
the optimum I... For an L-smooth function, gradient-variation
batch conversion [39]. For a G-Lipschitz function, the problem-independed
achieving adaptivity between the gradient-variatie bound in unconstrained online learning may be as challenging as achieving universality in offline optimization over unconstrained domains, where the method must adapt to both smooth and Lipschitz functions. To the best of our knowledge, the best-known universal method for offline unconstrained optimization is by [4)). which combines UNIXGRAD [39 with the DoG step size [31]. Nonetheless, this method is complex and still relies on a predefined range of parameters, highlighting both the difficulty of the problem and the fact that remains only partially solved. Consequently, designing single unconstrained online learning algorithm that adaptively bridges the gradient-variation variaatio regret bound for smooth functions and the worst-case bound for Lipschitz functions is non-trivial, which could provide new insights into universal offline optimization methods. We leave this for future work. Remark 4.4 (On dependence on the time horizon). The use of T in CA-OONS (via N = [log T experts) is only for convenience and not fundamental. An anytime variant is obtained by the standard doubling trick: restart the algorithm at epochs of lengths 1, 2, .... and in epoch & set N₂ = logg 2/. This introduces at most an additional logarithmic factor already hidden in O(-) [41 Section 4.3], A restart-free alternative is a sleeping (awakening) expert grid of learning rates as in the multi-rate rate construction of [22, which activates only those experts whose scale becomes relevant.
bound and the moblem-indeppndde
4.2 Comparator- and Lipschitz-adaptive Algorithm
The algorithm in the previous subsection requires prior knowledge of the Lipschitz. constant G. Due to practical limitations such knowledge may not be available real applications. comparator- and Lipschitz-adaptive algorithm would instead adapt to an unknown Lipschitz constant G.
simple approach to handling the unknown gradient norms, proposed by (25), relies on a gradient- clipping reduction. The key idea is to design an algorithm A that achieves appropriate regret when given prescient "hints" h, 2 g| ll at the start of round t. Since such hints are impractical (as ge is not observed beforehand). we instead approximate them using a clipped gradient, inspired by [25]. We start with an initial guess B, on the range of max; [gg, mm where Sr- = (xx)). We define B, = maxogast llg. m,ll2 as the predicted error range up to iteration t. The truncated gradient
B then defined as g. m, + B. (gt m.). The truncated gradient satisfies l1 - mzll2 S B,-1,
allowing the learner to assume that the range of predicted error in iteration is known the start.
Next, we initialize the decision set diameter guess as D, = 1. For each iteration E [T]. we first play 2₁ and receive 9r Vf(().). To update D.. we consider the condition D, <
8

---

Algorithm 4 Comparator and Lipschitz-Adapivee (or CLA-OONS) for the SEA model
Input: Initial scale Bu- Initialize: D1 = 1.
1: fort t = 1..... T do
2: Run OONS in D--bounded domain and obtain 21. Play 2, and receive 9: V.f((z)).
3: Construct 9t m4 + B, (gt me), where B, = maNugast llg. - m2ll2-
B
4: if Dr
E== max [1, ga lo 22]
11-112
then
5: Update D2+1 = 2/ Ex= max m.max li [a] and reset Ar+1 as 9 and 4/41 = 0.
6: end if
7: Feed St to OOOS running in the D4+1 -ounddddded domain and get T4+1, where 2+1 = B2.
8: end for
this condition holds, we update D++1 using the doubling trick. This ensures that we need update De a maximum of . Ollog times. We divide the total I' iterations into disjoint subsets of M iterations, If the "doubling" occurs at the i-th iteration, we update ta t- and reset 2 1 0 and the matrix A441 in OONS as follows
V ESm [1, lise [
A4+1 11 I+
Σ nv - m.)(V. -ma)² + 470-1 s=1++1
Then, we feed Tt to OONS running in the -boudbounded domain Xe+1 = {xr ||~||2 S Do+1 J.3 and obtain 1++1. We summarize the ideas in Algorithm 4 and term it as Comparator and Lipschitz-Adaptive Optimistic Online Newton Step (or CLA-OONS OONS) algorithm.
Theorem 4.5. Let both D (potentially infinite) and G be unknown. Under Assumptions 2.7 (utt G is unknown).
2.3 and 2.4 the proposed FPF-OONS algorithm satisfies
(1) s (1ul)(
VER.T + G2 Iull2 + Gl| G2 GoVT (
where di.r captures the stochastic gradient deviation (without the squared norm) and GI4 denotes the sum of maximum expected gradients.
Remark 4.6 (Discussion and challenges). In Theorem 4.5 the regret includes ||ul|2 o Eir))
Ideally, aim to achieve dependence of (11uula consistent with [25 and (43. However, achieving this within the SEA framework presents significant challenges. As mentioned in Section? 2 obtaining regret bounds that scale with of. in the SEA framework is difficult. These challenges are compounded in the comparator and Lipschitz-adaptee adaptive setting. Below, we outline some of the main technical challenges associated with achieving the desired bound of Õ (/Iwlla(
V ))r)).
As stated in Section 2 the methods such as those proposed by 225 27 I1 cannot be applied to obtain the expected regret bound in terms of .;. The work 44 also looks promising; however, remains unclear to us whether the approach proposed in the paper can be directly extended to the SEA framework. Their results, presented in Theorems and of [4 are not srpsschitz-daaptii Specifically, they operate under the assumptions that ||gel|2 and |melll S
One could also use large number of base-learners achieve regret of ((1 E. 9 my 1 [ similar to [10]. However, this approach presents subtle yet significant challenge. Following
similar analysis 10 get the following decomposition: E, (gt, u) = E, (gt, x
E Exeee u/ u). By leveraging Theorem 23 in [10), we can write E, (g,, = - u) as E, 21
Σ. || 113) Observe that expressing the first term, E, 11gt - m, 12z in terms of σ1. and Σ1.r introduces additional terms involving Σ, || Ie-1ll (See Lemma in (12). The only way to address this term is through the negative term which becomes tricky. This challenge is reminiscent the problem encountered by [17]. Their solution, outlined in Equation (17) of [17] relies on the bounded domain assumption, which is not applicable in our setting. Consequently, this limitation prevents us from improving the | dependence in the leading term by using additional base-learners.
u) x [[(uu) /r E. 9 m
- ||a - 2.

---

The bound in Theorem 4.5 also includes additive term involving v which reflects the sum of the maximum expected gradients' norms over rounds, and arises because the domain is potentially unbounded. Note that this term does not have a ||u]] dependence. Hence, the comparator having large norm in an unbounded setting (potentially dependent on T) does not affect its growth. In the worst case, v O 1: O(vT), which underscores that this additive term does not have significant adverse effect on the regret as Vol. and V also scale as vT [8.
Conclusions and Future Work
This paper presents novel parameter-free algorithms for the SEA model, addressing critical challenges in online optimization where traditional approaches require prior knowledge of parameters such as the diameter of the domain D and the Lipschitz constant of the loss functions G. Our proposed algorithms: CA-OONS and CLA-OONS are designed to operate effectively even when D and G unknown, demonstrating their adaptability and practicality.
There are several avenues for future research. First, we would like to improve the regret's 's dependence on ||u||2 when both D and G unknown. Another promising direction is to reduce the number of gradient queries in CA-OONS from O (log T) to (1), thus enhancing its efficiency. An intriguing question in the comparator-adaptiv setting whether is possible design single, simple online algorithm that simultaneously achieves two types of bounds: O(1]u] + [|u]|2( oo / / and
([I As discussed in Remark 4.3 it remains an open challenge to construct an adaptive parameter-free online algorithm that can interpolate between these bounds. An additional open direction is to move beyond expected regret and derive high-probabbilty (or variance-sensitive) regret guarantees for the SEA model in the parameter-fre setting. Current SEA analyses, including [8 12). bound only E[RR (u)]; developing concentration results that retain the fine of and E dependence without incurring suboptimal logarithmic inflation appears non-trin non-trivial and left for future work.
Acknowledgments and Disclosure of Funding
This research is funded by the Singapore Ministry of Education Academic Research Fund Tier under grant number 4-8000423-00--00 and three Singapore Ministry of Education Academic Research Funds Tier 1 under grant numbers A-80001 11--889-0010 A-8000980-00 and A- 4-8002934-00-00.
10

---

References
[1] Nicolo Gesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[2] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-225, 2016.
[3] Francesco Orabona. A modern introduction to online learning. arXiv preprint ar:::: 111iv:1912..333 2019.
[4] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning, pages 928 188-936,600 2003.
[5] Jacob Abernethy, Peter L Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st annual conference on learning theory, pages 414-424, 2008
[6] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169 192, 2007.
[7] Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic con- straints. Advances in Neural Information Processing Systems, 30, 2017.
[8] Sarah Sachs, Hedi Hadiji, Tim van Erven, and Cristobal Guzman. Accelerated rates between stochastic and adversarial online convex optimization. arXiv preprint (3Xi:22333.03222,, 2023.
[9] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493-1529. PMLR, 2018.
[10] Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-1259. PMLR, 2021.
[11] Andrew Jacobsen and Ashok Cutkosky. Unconstrained online learning with unbounded losses. In International Conference on Machine Learning, pages 14590-1463 PMLR, 2023.
[12) Sijia Chen, Yu-Jie Zhang, Wei-Wei Tu, Peng Zhao, and Lijun Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25 (117))11-622 2024.
[13] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning, 80:165-188 2010.
[14] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2012.
[15] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, 33:12510-12520, 2020.
[16] Yu-Hu Yan, Peng Zhao, and Zui-Hua Zhou, Universal online learning with gradient variations: A multi-layer online ensemble approach. Advances in Neural Information Processing Systems, 36:37682-37715. 2023.
[17] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zui-Hua Zhou Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. Journal of Machine Learn- ing Research, 15(98):1-52. 2024.
[18] Yan-Feng Xie, Peng Zhao, and Zhi-Hua Zhou Gradient-variation online learning under generalized smoothness. Advances in Neural Information Processing Systems, 37:3885-37778 2024.
[19] Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. A simple and optimal approach for universal online learning with gradient variations. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.

---

[20] Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315-14325, 2020.
[21] Shinji Ito. On optimal robustness to adversarial corruption in online decision problems. Ad- vances in Neural Information Processing Systems, 34:7409-74200 -420, 2021.
[22] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 467-475. PMLR, 2019.
[23] Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and minimax-op copimaat- in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, pages 6142-6151. PMLR,
2021.
[24] Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016.
[25] Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory, pages 874-894. PMLR, 2019.
[26] Dylan Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances in Neural Information Processing Systems, 28, 2015.
[27] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Conference on Learning Theory, pages 4160-4211 PMLR, 2022.
[28] Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory, pages 2858-2887 PMLR, 2020.
[29] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
[30] Ashok Cutkosky and Zak Mhammedi. Fully unconstrained online learning. Advances in Neural Information Processing Systems, 37:10148-10201, 2024.
[31] Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning, pages 14465-14499, PMLR, 2023.
[32] Ahmed Khaled, Konstantin Mishchenko, and Chi Jin. Dowg unleashed: An efficient universal parameter-free gradient descent method. Advances in Neural Information Processing Systems, 36:6748-6777 6769, 2023.
[33] Ahmed Khaled and Chi Jin. Tuning-free stochastic optimization. International Conference on Machine Learning, pages 23622-2366) PMLR, 2024.
[34] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[35] Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time- varying zero-sum games. International Conference on Machine Learning, pages 26772- 26808. PMLR, 2022.
[36] Peng Zhao. Lecture Notes for Advanced Optimization, 2025. Lecture 9, Optimism for Acceler- ation.
[37] Sebastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. Online auctions and multi-scale online learning. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 497-514, 2017.
[38] Yuheng Zhao, Yu-Hu Yan, Kfir Yehuda Levy, and Peng Zhao. Gradient-variation online adap- tivity for accelerated optimization with hölder smoothness. In Advances Neural Information Processing Systems 38 (NeurIPS), page to appear, 2025.
12

---

[39] Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. UniXGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances neural information processing systems, 32, 2019.
[40] Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In The Thirty Seventh Annual Conference on Learning Theory, pages 3257-332 PMLR, 2024.
[41] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125))1--5, 2021.
[42] Zakaria Mhammedi, Wouter M Koolen, and Tim Van Erven. Lipschitz adaptivity with multiple learning rates online learning. In Conference on Learning Theory, pages 2490-2511. PMLR, 2019.
[43] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:/002.4900. 2010.
[44] Ashok Cutkosky. Combining online learning guarantees. In Conference on Learning Theory, pages 895-913, PMLR, 2019.
[45] Haipeng Luo, Alekh Agarwal, Nicolo Cesa-Bianchi, and John Langford. Efficient second order online learning by sketching. Advances in Neural Information Processing Systems, 29, 2016.
13

---

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 abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our regret bound are discussed Remarks 4.2, 4.3, and 4.5,
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 a separate "Limitations" section 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
14

---

The problem setting is clearly introduced in Section and all theoretical results are accompanied by proofs.
Justification:
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 in the statement of any theorems.
The proof' 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 a 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 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper is fully theoretical paper without experimental section.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 to 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 is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[NA]
Justification:
This paper is fully theoretical paper without an experimental section.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuia wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: [NA]
Justification: This paper is fully theoretical paper without an experimental section. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is fully theoretical paper without an experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It 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 enrors 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 error 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 in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is fully theoretical paper without experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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 https: htttss:/ /twprriss//eurip.ccco httparrpp....pppp.cc//ccccccaaaa
Answer: [Yes]
Justification:
The authors confirm with the NeurlPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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: The work is mainly theoretical, thus there is identifiable societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people 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.
there are negative socictal 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 a 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: The work is mainly theoretical.
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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper 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 is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppsiipteeeee whworeeswthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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:
The 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The 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.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standad components.
Please refer to our LLM policy hattps://neurips... 200ps//ee///0ooeeeeeee////////// for what should or should not be described.
20

---

A
Separation between oer and न.
Recall (Section
2 the two stochastic variance measures:
o sup ZER
V
of = sup ZEN
VV((() (V)()))VF((()) (
and their cumulative versions Incquality, but the gap can be arbitrarity large. The following simple 1-dimensional construction (with a growing number of disjoint regions) shows an order difference.
of - 07. Always of S o by Jensen
Proposition A.1 (Linear separation between न.. and og:)). Let X= = X C. R with disjoint ,n.. cells X, = ji - 1, for E {I,...,n] For each round E {L,..., .T} and each cell i E {1..... n). draw independently
Ca, ~ Bernoulli( ht) and $1, TxEee +f-,,+1] with Pr(St, = 1) = Pr(st., = -1)
and define the (stochastic) gradient field by
Vi((r)= 00, for all x E X;,
with arbitrary values on cell boundaries. Let Fg be the expected loss, defined up to an additive constant by F.(()) EVV fe(x)] (we fix the constant so that F, = 0). Consider the two grudient-noise proxies
of = sup Sunp -
of = sup Vie(x) - VF((1)]
=E
and their sums oi. = Σ of and न.. = =E== o.
Then, for every n. T 1,
of and o. = 1 (1- 1 111
n+0 1-11)
e
hence, for all large n,
T = 011 and न.. = 11-- (1- = O(T).
In particular, taking TTT)= T yields o. 1 while o.. 2 (1 c 1T, iee, linear (in T)
separation between the two quantities.
Proof. By construction and independence, for any x E X,,
(F((x) = [+]])(+)]] = E|a,, B[st,] = 1.2 - =0
so F; = 0 (up to an additive constant). Therefore
of = sup E [[V = sup E(c2,,82,) =up
F/e.d 1.
ZEX
Summing over i gives o.. T/n. For o7, note that s3,, = 1 and (z)( = ot for all x X1. Thus
o, = E. sup [+)) F. maxcr,) c1.1 Pr(vi, at o;;= 0)= -1)==111111))) (1)
Since (1 - 1)" < -1 for all n, we have o7 E [1 e 111. Summing over yields न..z
T(1 - (1 - () 2 (1- Finally, with n = T we obtain of. and प.. 2 (1 e e T., which proves the claimed linear separation.
Remark. This example shows that regret bounds expressed in terms of ... E, || ||a]
can be factor ((T') looser than bounds in terms of of E, sup, E[ll [ on the same instance.
21

---

B Omitted Details of Section 2
B.1 Proof of 2
Proof. From Theorem 5 in [27 we have
(y) S Ō |
[Vf((z)) V
||
2
sup Vf((z) - ZEX
From Lemma 8 in 12
also have
T
sup
(f)
v
E
T
S 2
Σ
sup xEX'
Vf((z) V
+4 +4
sup #E
VF((z) VF:-1
Taking expectations with Jensen's inequality and the definition of o.. and Dj.r, we obtain
B (u) s Ō [Iulla( o.. v (2(
C Omitted Details of Section 3
C.1
Auxiliary Lemmas
Lemma C.1 (Bregman Proximal Inequality). The Bregman Proximal update in the form of r++1 min (xx + (2, x,)} satisfies
(gt. #141 u) s (w, - (v T141) D2, Fx+11)
(10)
Proof. By the first-order optimality condition 24+1, for any u X, we have
(gr Vv((o++1 Vib(zx:), u rz+1)
On the RHS of TO expand each term by the definition of Bregman divergence
D& (u, ( (x(x,, (Vb(z441) Vv((x)) Z(41). Hence, the proof is finished by rearranging the terms.
Lemma C.2. Let Dt = arg minzex (z, m.) + (x, xf)} and 2/41 = arg min (0,, gt)
Dey (x,, x.)}. Then, it holds for any X
T
T
Σ
(x. u. u.9t) S Σ (Ct 2'411 m.) + D (u, - Dv. (u, 2(41)
Do,, D (21,
Proof. We have
(x) u. gc) (I1 2(41, me) +
(1 u,gi) + (xx 2'41190 ma). C.I twice, i.e., (a- U Dvlu,b) - Dv(u,a) Das(a, since
(11)
We apply Lemma
arg min (x, DD b). Then, we have
(Ne- 2141, m²) < Do, (4
Dv, (1(419 - Das, (2r,, x(); (x'44 u, 9t) Do. (u, x1)) Do. (2'(1), Do. (2/ z'41))
Substitute these two back to [11) and over T providing the desired result.
22

---

Lemma C.3. In OONS. we have 0 S (2t - (21-1 V. mm) - 2/|V, - -mell A, and Et=l
T Vt -m) S o
eln(Tmer//a (21)
47
Proof. We define
F.,, (I) (x, ma) + Do. (2, 2/):
Fv, (x. Ve) + Dor (x,
By OONS, we have
24 arg min Fm. (z),
2 arg min Fv, (2)). xe
xE
Since D = As and by the first-order optimality at 2'411, we have
(x) Fv. (x(+1) 2 2 |1:0e x' 11
Also, we can write Fo, Pr, (1/+11) as
Fv, (x+) - Fo, (1((+1) = (are 2'441 V.) + Drs (1t, x/)) Dar (3 at)-
Then,
2 Øt - x 101-2/442133 S (Iz J'(11 V. - -mm) + Fi. (2x) Fmm (2(422)
1
S (xz - V, -m),,
where the second inequality comes from arg min Fmn (x). Therefore, we have (iee r'41 V. ma) - 2 mell 1
Since 2'41 minimizes Fm, (x) and 2; minimizes Fv, (x), we have
0 < Fv, (xx) Fv, (2(42) = (at, x'411, v + Dv. (I,, x1) DWh, (2(41; 2l),, = (2t x'411, V. -m) + Fm (xt) - Fm, (2(41)
S (1x r/411 V. - -me)-
By the definition of V. 9t + 32m (Iz, 91 mm) m.), we have
V. mr|12 = 11 - m4 + 32322 (Fi,, - m.) me)ll2
19 my 12 + 32n, Dllgc mell2 5 |1 mell2-
(12)
Next, we define
A, = 42
++ Σ 7s8 7/( V. - -m,)(V ms))
s=1
Hence, Ar 2 As since
VV mell
44|g: mell 4z7 Also, we have
(V. m.)(V, m²)
Im (V, m.) (V. -m=) - (A, Ar-1)
1/t
7/b
Then,
T
V. mell3--1 <
V. me mell
Σ Lrace (V (V.-m.)) (V. (ma)
-ma) Ar
trace (A, Ar-
Th.
(In [Ā, - Inn A7,
1=1
In
1p
AA
23

---

For |Arl:
|Ar| S 1
+ Σ
(V. mv)(V. m.)
1=1
r
In |n|A <0(rln(1
11
V - mmml3)
+
42
1=1
427 T
I <O(rin(1 +
Σ m1)) 4zf t=1
$ 5O(rin(1 + m T)
29
where the rank of Ei=1 (V. (V, -m)
Therefore, we have
2/4 V. -m²) S 0 ( c
1p
Lemma C.4. Let 82, VI E [T) be non-negative. Then,
T
T Σ [=1
8t
$
St-
j=1
8j
Proof. Let S: Ej=1 8j. Then,
Sr
dx
dr = 2/ ST.
Sc-1
Lemma C.5 (Theorem 81 Lemma in 12
Under Assumptions 2.1 and 2.3 we have
Vf((z)) - v 62 +
[f(()) VF((E)11 + +4L2
| 21-1
C.2 Proof of Theorem 3.1
Proof. By Lemma C.1 we have
Σ c1 u, V.)
(1t 1/411 V. - -m) + Du,
Dar, x(41) Dar (211 Des, (2e,
T
T-1
(1t 1/411 V, - mm) + Dar, (u,
+
Σ
Denus (u, x/41)) Dar, (u, 2(+1)
1=1
T
Σ (22, + (x,,
24

---

Term Dæ, 2(): Since the initialization of z = and A = Ozfff), we have
Der (u, 2 [lul,, S (
1
Term
Eis Des ((+1) - Du (1, First, we have
A++1 - = =n:[V - -m) - (m)) + 4mo - =z)1.
Also,
1 (u x'(+) T (Ac-1 Ao)(u- x/(-)
D (u, (141) (u, 2/41)
(u - 1-444))) (ne(VV mc)(V -ma)² T + 41j ( =2) - x((+1)
2
171
(u r'441 V. - -ma)² + 20 (2 = - 1'41112.
2
Then, we have
Decn (u, (2,1)
Dro (u,(u,
T-1
M uu- r/411 V. - -m,)² + +0(
Dh (2tt1 - -)))),
T-1
1 64D2T
2 (m 1/411 V. mmm)² 00
Σ
D( - =z)/2T),
(since 1) S
[=1
1/1 (u 1 V, - vm-m,)² ((T 21));
Ve(u Ft. V. - -m,)² +
Melae - 2/411 V. - mi)² O 21)),
ne(u It, V. -m,)² +
nc( 1/41 V. m2) -
V. - mm)
+0 - 21));
T-1 no(u x2. V. -m,²² +
D2 - 1/411 V. mm)+ O(D(2r--2)))
(Using Equation 12
(r 1/m22/21 + D(2r -2)).
r rln
no(u Iz. V. -m,)² m
mpr
(Using Lemma C.3)
(TT((Tm2r/2) + D(2r 21)).
rln r
2n (u, V. - -ma)² 2m (1r, V. -m,)² o
8mkk St mz)² (1 St m,)² + O (l((Tmer/Z)) + D(2T - 21))
mr
(since 32m, (It, 9t - mi) 1 2
25

---

Term (21.2 + De (2 2/)):
Σ (1r, + Dar (1tr Σ
(110 x'llå, + +110/11 - -
t=
T+1
2| 2/113,,,
Σ
|| 2'llå,
4 T
T
||
- 24-1112
27
Σ
10g - x2-1 112
4
t=2
t=
where the last inequality comes from A, ł A-1 2 42
Since (xr) is convex in we have
Σ -
(z u, gt) + 16 m²)² 167, (u. 9t. m²)² - Σ
V Iz u).
Therefore, the final regret bound here is
T
Pir()= <
(oe gx)
<0
(0(Iln(TMT//// =111u112 + D(= =1) Σ
T
(u, gr mma²²
21
2
|
11
1/T
x=
C.3
Proof of Theorem 3.2
Proof. In this case, we have l1g. mell2 $ 2G, Vt [T]. Then, we set 21 = 2G, Vt E [T] and step-size Ni as
= min
for t [T].
64DzT
D D 119. m
By substituting 7) and z, into 3 we have
7-1
T
T'
Rr(u)= < Ō(D D
1gge m4 GB+G2D2 + Σ
Th (u, gt - -ma)2
G2 Σ
|x xz-1 12)
By Lemma C.4 we have
(u, 9t -mi) < 2D,
Σ 19. m
Then,
T
Ru < 30DD
Σ
11.r m
G21|22 xz-1
26

---

By Lemma
C.3
and the definition of 9r and my, we have
T
T
D
Σ
19
my
G²
x2-1
Tz
1=1
1=2
T
$ DG 2D
2D
V +2v2D
Vf(((e) - VF((1))
T
+ 2LD,
Σ
1 21- 21-111 - Σ
10 - 21-1
t=
D
T
& DG +
+ 2D
VF((( - VFC-I
G
T
+ +222D
Vf((())) -
Therefore, have
(p) s olyor, + 1Vx++V27 121))
C.4 Computational Complexity of OONS
The primary computational bottleneck in proposed OONS algorithm (Algorithm 1 is the management of the x d matrix A,, A naive implementation would involve storing this dense matrix and performing full matrix inversion each step, leading prohibitive costs in nigh-dimensional settings.
Storage: Storing the dense d matrix A, requires (d2) memory.
Computation: A naive matrix inversion A, would cost O(d)) per step, and the subsequent matrix-vector products would cost (dd))
In practice, this complexity can be significantly reduced. Since the matrix A is constructed by sum of outer products (A, c/ + Σ N,v.0, its inverse can be efficiently computed and updated at each step using the Aherman-Morrisee Woodbury formula. This reduces the update complexity from (dd) to ( per step.
However, (dd) complexity per step still be prohibitive in high-dimensional scenarios. To address this, existing research has explored several techniques:
Matrix Sketching:
This technique approximates the original d x matrix A, with much smaller "sketched" matrix, thereby significantly reducing both storage and computational requirements. For instance, Luo et al. [45] have successfully applied sketching to the Online Newton Step (ONS) algorithm, creating matrix-free updates that avoid direct manipulation of the digh-dimensional matrix.
Sparsity: If the gradient vectors sparse most iterations, specialized sparse data structures and algorithms can be utilized. This allows update computations to be performed much more efficiently, avoiding the full (dd)) cost of dense matrix-vector multiplications.
Integrating these high-dimensional adaptation techniques into our proposed algorithms for the SEA model and analyzing their theoretical guarantees is an interesting direction for future work.
27

---

Algorithm 5 Multi-scale Multiplicative-eeihh with Correction (MsMwC)
Input: w1= E AN.
1: for 1,,...,, T do
2: Receive the prediction h, E RR-.
3: Compute We arg weAy (w, he) + (s w(), where de(w) - ws In
4: Play wt, receive & and construct correction term 0r RR with des 323r (P) mmm)²
5: Compute w/41 arg min (w, 4 + ae) + Ds)
6: end for
D Omitted Details of Section 4.1
D.1 Multi-scale Multiplicative-weiiht with Correction (MsMwC)
We rephrase the MsMwC algorithm
10] as the following Algorithm 5
D.2 Proof of equation
5
The final decision is a weighted-average of base-learners' decisions: -E Wesee. Then,
(u) = Ri +
f(( Σ f((z))
= (A) +
f(( Σ Wey Σ f((x))
JEIN
T
< <Rp(()) +
Σ
W1.fe(1)) Σ fx(x))
1=1 JE(N]
T
= (n) + Σ [((2))(015- - 1 =
JE[M]
= (t) + Σ Σ
- - - 10 =
t= JE
< A + Σ Σ ( 10==0) =1]]
t=1 JENN
= Ri + Σ (le, we wt):
where 4, E R with ef = (V)(())) and w$ is vector in Ax whose j-th component is
(wi), = if = and 0 otherwise.
D.3 Auxiliary Lemma
Lemma D.1. (Theorem 6 in (IOI) Suppose for all E [T] and j [N]. 16/1 < GD, and h GD
where Eg = (x)),, s{) and le = (1)- x(). Define r = lu(
NTD, and the sei as D
ε E= 8 (Bk, Gk) wk S,
1
24 J
where Gk is the MsMwC algorithm with w/ being uniform over 2(k), S = fk Z 3j
GD, < 2 < GD,yTT and Z₁ = eie [N] GD3 < 2 We have the following regret
28

---

bound
T
(4, wy - w() S 0 (Dr, +
r; Σ ( -1))) n1)p)
1=1
Proof. The regret E (le, 14 w can also be decomposed
Σ (4, we - -w()=
L, wi
L, w2 w
T
les w
w!)
+
LL. - -ex)
where 6k. is the kthth standard basis vector and the second equality is from the definition of Lę-
For any E [N], there exists a k, such that S min
S 2nk, By
128GD,
ΣE (c) (1))
Lemma and Theorem 4 in 10 we have
T
T r.
(4, we - w (D,
D Ce
D.4 Proof of Theorem 411
Proof. We begin with considering the first and second cases that ||ul|e S D₁ and |lull D2 S 2/Ju||2.
Here, we define of fe(()) and mi = ( for all 1 E [T] and j E [N]. For the meta
regret, define l R with & (V)((=)), and h4 RN with hę (V (mt-1), Then, ( S GD and | < GD, for all / E [7] and j E [N]. By applying Lemma D.1 we have
T
Σ
(b, wi w() s (DD,
r, X (1))
t=1
1=1
By the definition of E and hi, we have
T
T
Σ c
m2
-
T
T
D
[V((zt)
V = DJ
Σ
11
m
Hence,
T
Σ
(1, w. - w S ( Dig
r, r lot
mfl33
(13)
Then, we investigate the expert regret part. Here, we set the step-size for the expert as
min (6AD,E DivE 1-1 loot m
(14)
29

---

By substituting the size specified in
14 to 30, we have
(u) - Ō(Di)
Σ llst
mil
+
g9
mill
G²
x
Dr
<0( DJ Diy
Σ
19 m
G2
11-1113
(15)
Therefore, by combining [13 and 15
we have
T G² Σ
Rr(u) = + D;
Σ
199 mm11
| - 21-111
2=
Then, by applying Lemma C.5
we have
D
Loi-mil13
G2
2/-111
D
GD, +
2D,
Σ
G
+2V2D, [f(())) (F(()
Since the expert runs OONS within the set X; = (x: ||=|| - D S X, we have
sup BAND, [+(x) - (x) S x
sup ,-, [1] V ft (+)(1))
sup (F) FF sup (x) (=)1(=)) s
dE
Hence,
D-L2 G + D. oo. + D, [
(u)) S Ō
(16)
Case 1: |/ul|2 I Dr. We take i = and substitute D; with Dj into 16. Hence, we have [[ S @VVoir /r.rr.
Case 2: In this case, let i be the smallest integer such that ||ull2 S D, = 2'. We have |ull2 S D2 s 2//u||2 since Di+1 = 2D; Then, we substitute D. with 2/|u||2 into the regret bound 16). Then,
[[R s (11u1)) [ulll( / ofr + /2r)))
Case 3: |/ul|2 > Dmnxx
Next, we consider the case when ||ul|2 > Dinax 2 Then, we have
r
((xx)) - Se(u)= S V - u)
22GT||ul[2.
We take N ['o, then T < ||u||2. Therefore,
f(a)) f(())) < 2G||u|B.
By combining these two cases above, the desirable regret bound is achieved.
30

---

E Omitted Details of Section 4.2
In this section, we also denote 9r = f((e))) and my = ( We first note that
119.112
max Dr <
SVT.
IST
max (1, maxisa [1
Thus, we need to update Dj at most Ologg T) times. Let M be the number of total updates in De. where M ()og We split the T iterations into M intervals I with m [M], where the last iteration of Im (denoted by fm) either equals to or Dt... +1 * D....
E.1
Proof of Theorem 4.5
Proof. We have
(r) Σ (( Σ Si(u)
(gts Jt u)
M
T
(ge: 1t - up)
(ge Uu - u),
Tem
where we define un = min(1, Dr Ju.
||ui|2
We first consider Tm as
Σ
Te Us}
Σ
(et, Te - ue) + Σ
(g.
Te, ue)
tEL.
tELm
Note that iteration within interval Im. i.e., t E Im the domain has bounded diameter D. When t Amx we take
1
T)e mint 64D,a
(-1 E
11.
m
where & is first index in Im. Also, denote the last index in Im as lms respectively. From the Line 5 or 8 in FPF-OONS we need to reset s',, = 0 and A, for all E In at iteration ( as follows
f-1 Σ nv - m.)( - -m.) + 4m
A. 42
8mth
Similar to the proof of Theorem 3.1
we have
Ue, V.)
bm
(or
2/411 V. -mm) Dar, (u,
Σ
Deriy (ut, ((41) Dapo (ut, F/-1)
1=
fm
(D ((11 + Der (It, 2()),
t=
where V. = 9: + 32m, (Ie. mi) (gt m.).
We first consider the term Eim fFt 2/411 V. mi). By Lemma C.3 we have 0 S (xr 2/-1; V. - m.) < 2/|V, m, 12 A-
31

---

Also, we have
BB-1 (ge ms) melle
l mell2 |lm +
B.
I 11g - 10mmm -mel2
By the definition of V. = 0z + 32m (Te: 9t m²) (ā: - m²) and l1ã. mella S 11g. -mall2, we have
VV - -mm1l2- = 1l m + 321H/ (ire; gt- m²) (+r m2))la
x 1 mell2 + 3217 Dil - melê
ll mell2 + 32m, D 2111 mella
3
3 11:: -mel2-
in
2
gg
mella S 2
For E Lms we also redefine
A. 42 I
Σ
17 V. -v.) -,))
8=11
Hence, A - Ag since
V mell3 S 4 mel13 S 427- Also, for t [ti + 1, m. we have
1
1 (A. A(-1)
(V. m.)(V, m.)
(n((V mm) -m =
= 17c
m
Then.
V mell A
V -me, 11 1
+
Ve my m
1
km
V me
+
IV mell2=
4
+
<1
+
| - -mel
(since Ve, - mm,13 5 422;
1=
Vv_ mel 1| +1
1=h-1
fm
(In Arl - In A 1)) + 1
t=f -1
A
In
1.
7tm.
Ar
For AAmml |:
Amm 1/ 142 1 + Σ
ne (V. m.)(V, -ma)
t=t1
<0(11n(11 + fm
In A
11t
V
mm.113)
42
1=11
422
<0(rin(1 +
Σ nn
4.7 t=
<0(rln(1 +
7/1 2t T)
2
2/1
32

---

Therefore, we have
fm
(o F(+1: Ve - -mm) s s0( (rln(TTn the 7e 2os
(
nm
Term Der, 2/,);
Din, (24, x(1,)= Ilull S 50 (l.111))
Term Di=h Dirsi (ue, x1(11) D Ve x'+1): By the definition of un min(1, D. Ju, we have |lu|la
llulle min[/|u|le, Dz}.
Then, we have
D Dosu (ue, 2641) - De (ux, l2(11)
t
fm
1
tm -1
T1
U1 r'441, V, - me) + 0
1/e 1/:|ut - 13 =²))
2
Im
11t [14 - 1/+1 V mi)² + +0
Dr - -2))
(since ||ul12 S (D21122
2
t
mm
11 ( (14 1/41, V. mi)² +0 bm-1
Di(2f411 -22)/2))
(since ne S 64D,
2
Mt (ut - 1/411 V. m+)² O(Di +
(since 21 21
2
+0 In (T me, 2tm 120))
(uc Tt mz)² Sm (2x, m0)
+ Dem =m
11.m
Term Eim (Der, (F1, + Dv, (x),
(De, + Di 21)) t=h
(1|2 2'11a,, + |11//1 - =ell2,)
t=
1 4m
Im +1
2
+ 2
Σ
|| 1//13,,
2
(=1++1
1=t++1
2
bm
|1 21-1 =
Σ
|| x1-11
4
1=
1=
where the last inequality comes from A, 2 A,- X 42, 7 when 1. E [11 + 1,4m)
Then, we have
Σ tE!.
[h, Ft -t0)
In (TTe, 3tm /20))
fm 1
fm
s so
+ 2/ 1111112 + 2 +
Σ
ne ne - -m,)2 2
zi.
| - 5z--
17t.
tmtt
f1#1
<ō(
Σ FELm
11 me 11 + 11111 = Dr + ||u1/
Σ ll m. 113
2
| - 112)
=6
f1+1
33

---

Furthermore, by l1 -mll2 - l19: - mell2, we have
Σ (9t Ir, - ux) S (D, + 11212)) Σ
1
Tel S (D: + (D++1lul)
+1ul12)
Σ
Br BB-1
B, 11
m2112
m
AC Tm
1El
s 2(D + ||u||2GG.
At the last iteration T, we have
l max (1, maxage [19]112]
Dr
l1gel2
l1g. Elallle + (|))l(
[z,)) +
Therefore, we have
M
(gt, un) u4)= =0(1111 11ge
m4 +
2f Σ 1x 2 11
LE|T
T || 2 11
s =011112,
19: + (E(T]
Σ
(since 21 Bo = 1)
Now, we bound Texu- We observe that uy is either or T
D u. When us + u, ||ul22 2 Dr >
1|
Once in u, it stays there. Let t" be the last round when de # u.
21 maxts. 1106112"
T
(gt - u) = Σ
(9t, - u) -
(gt, ue u) + 21|u||22G
1=1
t=1
- 2||u|12
119ella
21|u||22G
119.112
< 2||u||12G
+ 2/|u||2G
max 11
1=1
< 2 + 2||u||2G.
Therefore, we have
Ry(u) <0(1u1B
119. my 113 + GD +
+
Σ
| x
[c(2]
34

---

By Lemma C.3 we have
||u12
Σ
1190 mel3
2t
21-1112
G2 G2ll1 + 21lu112
[VF((1=-1) -
+2V2/|u|12
-T()))))-R(((;)) +2L1Iu1B
Σ
| Fz- 112
Ft T 12
s 12/ + 1/11/ + 2
+2/2/|u1 f((e)) VF((I:)1
Therefore, we can conclude that
(u) - (1ull2t for + VZir) + GP VVVT-- - BAT + G2I|ul12 + ||u|| + G
where o1.r captures the stochastic gradient deviation (without the squared norm) and 1.. denotes the sum of maximum expected gradients.
35


Reviews:
[{"review_id": "rQt28jxTNd", "reviewer": "Reviewer_ygmp", "summary": "This paper proposes the first parameter-free algorithm based on the optimistic online Newton step algorithm for the stochastically extended adversarial (SEA) model, which is a hybrid model of stochastic and adversarial frameworks for online convex optimization. The authors obtain the regret bound of the proposed algorithm for the scenario with unknown domain D but known Lipschitz constant of the loss function G, and the scenario with both G and D unknown.", "questions": "1. I understand this paper is a theoretical paper and acknowledge its theoretical contributions, but I wonder, is it possible to validate the efficiency of the algorithm by numerical experiments?\n2. Could the authors discuss the computational cost under the high-dimensional settings?\n3. I wonder what the order of the variance of the algorithm is or how the variance of the proposed algorithm compares with other non-parameter-free algorithms.", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The contributions are clear. \n2. The technical results are solid.\n3. The contributions are novel since there is no parameter-free algorithm for SEA. This paper fills this gap.\n\nWeaknesses\nThe dependence of the regret-bound on the norm of the comparator is not optimal. Since the authors have discussed this point in detail, I don't see this as a big concern.", "was_revised": true, "final_justification": "The paper makes solid contributions for the stochastically extended adversarial model. The authors have improved their paper by adding some discussions about the computational cost under the high-dimensional settings. Their justifications about not making numerical experiments and variance analysis are acceptable. \n\nHowever, since I am not very familiar with this area. I have set the confidence as 1.", "rebuttal": "We thank the reviewer for your positive review and suggestions. Below we respond to the comments in Questions (Q).\n\n---\n\n>**Q1. I understand this paper is a theoretical paper and acknowledge its theoretical contributions, but I wonder, is it possible to validate the efficiency of the algorithm by numerical experiments?**\n\nThanks for the comment. Since our contributions are primarily theoretical, we did not prioritize numerical experiments. This approach aligns with prior theoretical works in online convex optimization ( e.g., [Cutkosky (2019)], [Jacobsen & Cutkosky (2022)],  [Jacobsen & Cutkosky (2023)], [Sachs et al. (2023)] and [Chen et al. (2024)] ).\n\n>**Q2. Could the authors discuss the computational cost under the high-dimensional settings?**\n\nThe primary computational bottleneck in our proposed OONS algorithm (Algorithm 1) is the management of the $d \\times d$ matrix $A_t$. A naive implementation would involve storing this dense matrix and performing matrix inversion at each step, leading to prohibitive costs.\n\n- **Storage:** Storing the dense $d \\times d$ matrix $A_t$ requires $O(d^2)$ memory.\n- **Computation:** A naive matrix inversion $A_t^{-1}$ would cost $O(d^3)$ per step. The matrix-vector product would cost $O(d^2)$ per step.\n\nIn practice, the matrix $A_t$ is constructed by a sum of outer products, $A_t = cI + \\sum \\eta_s v_s v_s^T$. The matrix $A_t$ is constructed iteratively from the outer products of past gradients, and does not require direct computation or approximation of the Hessian matrix at any step. Its inverse can be efficiently computed and updated at each step using the Sherman-Morrison-Woodbury formula, reducing the complexity from $O(d^3)$ to $O(d^2)$. \n\nHowever, the high-dimensional settings should be tackled separately, like even for the stochastic/online optimization problem, high dimension is also an independent problem to work with. To address this, existing research has explored like:\n\n- **Matrix Sketching:** This technique approximates the original $d\\times d$  matrix $A_t$  with a much smaller \"sketched\" matrix, thereby significantly reducing storage and computational requirements. For instance, related work [Luo et al, (2016)] has achieved matrix-free updates by applying sketching to the Online Newton Step (ONS), avoiding direct manipulation of the high-dimensional matrix.\n- **Sparsity:** If the gradient vectors are sparse in most iterations, sparse data structures and algorithms can be utilized to perform the updates, thus avoiding the full $O(d^2)$ matrix-vector multiplications.\n\nIntegrating these high-dimensional adaptation techniques into our proposed algorithm for the SEA model and analyzing their theoretical guarantees is a very interesting research direction. **We will include the above complexity analysis as a subsection in the appendix of the final version. For the high-dimensional settings, we will mention this in the discussion and conclusion sections of our paper as a prospect for future work**.\n\n>**Q3. I wonder what the order of the variance of the algorithm is or how the variance of the proposed algorithm compares with other non-parameter-free algorithms.**\n\nThank you for this insightful question. If we understand your comment correctly, you are asking about the variance of the regret, and how it compares with non-parameter-free algorithms.\n\nTo the best of our knowledge, the analysis of regret variance for the SEA model is a largely unexplored area. The existing literature on this model, including the foundational non-parameter-free works in [Sachs et al. (2023)] and [Chen et al. (2024)], has primarily focused on deriving bounds for the **expected regret,** $\\mathbb{E}[R_T(u)]$. These seminal works established the key dependencies on the adversarial variation and stochastic variance in expectation. Therefore, a direct comparison of our algorithm's regret variance to that of existing non-parameter-free SEA algorithms is difficult.\n\nYou raise a very important point. Most current regret analyses provide guarantees on the expected regret, which is a deterministic quantity. The question of regret **variance** is deeply connected to the study of **high-probability regret bounds**. Deriving such high-probability bounds for the SEA model, particularly in the parameter-free setting, is a significant and non-trivial challenge. We believe this is an interesting direction for future research and will add a discussion of this point to our paper.\n\n---\n\n[Cutkosky (2019)] Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory, pages 874–894. PMLR, 2019.\n\n[Jacobsen & Cutkosky (2022)] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Conference on Learning Theory, pages 4160–4211. PMLR, 2022.\n\n[Jacobsen & Cutkosky (2023)]  Andrew Jacobsen and Ashok Cutkosky. Unconstrained online learning with unbounded losses. International Conference on Machine Learning. PMLR, 2023.\n\n[Sachs et al. (2023)] Sarah Sachs, et al. Accelerated rates between stochastic and adversarial online convex optimization. arXiv preprint arXiv:2303.03272 (2023).\n\n[Chen et al. (2024)] Sijia Chen, Yu-Jie Zhang, Wei-Wei Tu, Peng Zhao, and Lijun Zhang. Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 2024.\n\n[Luo et al. (2016)] Haipeng Luo, et al. Efficient second-order online learning by sketching. Advances in Neural Information Processing Systems 29, 2016."}, {"review_id": "ICY5aBVkS9", "reviewer": "Reviewer_hGBe", "summary": "The paper considers Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization, and focuses on designing parameter-free algorithms, which refers to algorithms that requires no prior information about the domain $D$ and the Lipschitz constant $G$. The authors first develop a Optimistic Online Newton Step (OONS) algorithm and establish a comparator-adaptive regret bound, and then generalize their algorithm to the parameter-free setting where $D$ and $G$ are unknown.", "questions": "1. See weakness.\n2. Is the main difference between the proposed OONS and the existing OOMD [1] in this paper just in the regularization, or are there other important differences between these two algorithms?\n3. Is there any lower bound for parameter-free SEA?\n\n\n\n[1] Chen, S., Zhang, Y. J., Tu, W. W., Zhao, P., & Zhang, L. (2024). Optimistic online mirror descent for bridging stochastic and adversarial online convex optimization. Journal of Machine Learning Research, 25(178), 1-62.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper is well written. The OONS algorithm is novel. The authors clearly demonstrate the advantages of OONS compared to existing optimism online mirror descent algorithms. The proof is clear and easy to follow.\n\n**Weaknesses**\n\n1. The biggest issue is that the parameter-free regret bound is not worst-case optimal. When D is unknown but G is known, the algorithm’s regret is larger by a factor of $||u||_2$ compared to the setting where both D and G are known. This makes the results of this paper insufficiently strong, especially considering that in the parameter-free online learning setting, existing algorithms [3] can achieve adaptive regret with worst-case optimality. \n2. Although the authors have eliminated the dependence on D and G, their algorithm is still not fully parameter-free, as it requires knowing the value of $T$ in advance. In previous parameter-free online learning algorithms [1][2], it was typically not necessary to know $T$ in advance. \n3. ONS is a second-order method, which can be computationally inefficient in practice.\n\n\n\n\n\n[1] Cutkosky, A. (2019, June). Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory (pp. 874-894). PMLR.\n\n[2] Cutkosky, A., & Orabona, F. (2018, July). Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory (pp. 1493-1529). PMLR.\n\n[3] Jacobsen, A., & Cutkosky, A. (2022, June). Parameter-free mirror descent. In Conference on Learning Theory (pp. 4160-4211). PMLR.", "was_revised": true, "final_justification": "Most of my concerns are resolved.", "rebuttal": "We thank the reviewer for your positive review and suggestions. Below we respond to the comments in Weakness (W) and Questions (Q).\n\n---\n\n>**W1. The parameter-free regret bound is not worst-case optimal.**\n\nThe main contribution of our work is to develop the first parameter-free algorithms for the SEA model. The key challenge here is not just to be free of parameters $D$ and $G$, but to achieve a regret bound that adapts to the problem's underlying statistical structure, as captured by the cumulative stochastic variance $\\sigma^2_{1:T}$  and cumulative adversarial variation $\\Sigma^2_{1:T}$. As we mention in Section 2.2, from Theorem 5 in [Jacobsen & Cutkosky (2022)] we can directly obtain the expected regret bound as equation (2) (but scaling with $\\tilde{\\sigma}\\_{1:T}^2$), where it does not contain the additional $||u||\\_2^2$. But $\\tilde{\\sigma}\\_{1:T}^2$ can be arbitrarily larger than $\\sigma^2\\_{1:T}$ in some cases.  In the **Key Challenge** part, we discuss the technical difficulty that lies in how to achieve this preferred $\\sigma\\_{1:T}^2$ scaling without knowledge of $D$ and $G$ for unbounded domains. Also, in Remark 4.2, we discuss that the dependency on $||u||_2^2$ may be unavoidable.\n\n>**W2. The algorithm is still not fully parameter-free, as it requires knowing the value of $T$ in advance. In previous parameter-free online learning algorithms [1][2], it was typically not necessary to know in advance.**\n\nIn the context of this paper and much of the related literature on Comparator- and Lipschitz-adaptive learning, the term \"parameter-free\" is primarily used to signify independence from the two most critical and often unknown parameters:\n\n- **The domain diameter** $D$**:** Can be infinite in unconstrained settings.\n- **The Lipschitz constant (or gradient bound)** $G$\n\nWhen we named the algorithm, we also used Comparator- and Lipschitz-adaptive. Our work successfully eliminates the need for prior knowledge of $D$ and $G$. \n\nAs presented in Section 4.1, our algorithm requires prior knowledge of the time horizon $T$ to set the number of experts, $N=\\lceil \\log T\\rceil$.  This limitation is not fundamental to our approach and can be addressed by applying a well-established technique **doubling trick**. This method is specifically designed to convert a fixed-horizon online algorithm into an **anytime** algorithm that does not need to know the total number of rounds in advance. \n\nThe procedure is as follows:\n\n1. The learning process is divided into epochs $k=1,2,3,\\dotsc$. Epoch $k$  runs for $2^{k-1}$ time steps (i.e., from $t=2^{k-1}$ to $t=2^k-1$ ).\n2. At the beginning of each epoch $k$, we restart our entire algorithm (including all base learners and the meta-algorithm).\n3. Within epoch $k$, we run our algorithm by treating the length of that epoch, $T_k=2^{k-1}$, as the \"known\" time horizon. This means the number of experts is set to $N_k=\\lceil \\log T_k\\rceil$.\n\nThis approach will introduce an additional logarithmic factor $\\log T$ into the final regret bound. Also, the algorithm needs **restart** in this approach.\n\nFurthermore, we can adopt a more sophisticated technique similar to the one used by [**Mhammedi et al. (2019) in Section 3.2]** of their work on Lipschitz-adaptive MetaGrad.  Specifically, instead of pre-defining a fixed number of experts based on $T$, they define an **infinite, discrete grid of potential learning rates** (our \"experts\"). At any given time, only a finite and adaptively chosen subset of these experts is \"awake\" and active. An expert \"wakes up\" only when the cumulative statistics of the problem (e.g., the observed gradient norms) suggest that its corresponding learning rate has become relevant. This is often referred to as a sleeping expert technique.\n\nIn summary, thank you for raising this point regarding the dependency on $T$. In line with the majority of the literature in this area, the primary theoretical focus of our work has been on the core challenges of achieving **comparator- and Lipschitz-adaptive learning** in the SEA model.  We will add a **Remark in Section 4.1** in the final version to explicitly state that our algorithm can be made \"anytime\" (i.e., independent of a known $T$) by applying a standard doubling trick or a more sophisticated sleeping expert approach. We will provide the details of the standard doubling trick as mentioned above in a new appendix. \n\n> **W3. ONS is a second-order method, which can be computationally inefficient in practice.**\n\nThank you for raising this point about computational efficiency.\n\n- **Clarification: ONS as a Pseudo Second-Order Method:** We clarify that while ONS leverages second-order *information* by adaptively building an inverse of a local Hessian approximation, it is technically a **first-order (Pseudo Second-Order) method** in terms of its oracle requirements. It only requires access to **gradients**, not the actual Hessian matrix. The main computational task is updating and using the matrix $A_t$, not querying a second-order oracle. To be precise, the matrix $A_t$ is constructed iteratively from the outer products of past gradients, and does not require direct computation or approximation of the Hessian matrix at any step.\n    \n- **Computational Cost of ONS:** The inverse calculation of the matrix $A_t$ is indeed the primary computational step. However, because $A_t = cI + \\sum \\eta_s v_s v_s^T$ is updated via a simple rank-1 update at each step, its inverse can be computed very efficiently using the **Sherman-Morrison-Woodbury formula**. This reduces the complexity from $O(d^3)$ to $O(d^2)$ per step, which is the same as OMD.\n\n- **Justification for Using ONS instead OMD:** Our choice of ONS was a necessary one to tackle **unconstrained domain** in the parameter-free setting. As we explicitly state in lines 201-205, the regret bound for OMD typically scales with $D$, the domain diameter. For instance, the bound often contains a term like $D\\sqrt{\\sum||g_t - m_t||^2}$. When $D$ is unknown and potentially infinite, this dependence becomes problematic and can lead to vacuous $O(T)$ regret bounds. The adaptive second-order information in ONS is precisely the mechanism that allows us to decouple the regret from the unknown domain size. In our analysis (see Theorem 3.1 and its proof), the dependence on $D$ is isolated to terms like $D(z_T - z_1)$.\n\n>**Q1. Is the main difference between the proposed OONS and the existing OOMD [1] in this paper just in the regularization, or are there other important differences between these two algorithms?**\n\nThe main difference lies in the regularizer used at each step. In OOMD, the regularizer like the squared Euclidean norm. Our work employs a time-varying regularizer. Specifically, it uses $\\frac{1}{2}||x||_{A_t}^2$, where the matrix $A_t$ is adaptively built from the observed gradients. This choice of regularizer is not arbitrary; it is the key enabler for achieving our parameter-free results, particularly comparator-adaptivity in unconstrained domains as we mentioned in the response to **W3**.\n\n>**Q2. Is there any lower bound for parameter-free SEA?**\n\nTo the best of our knowledge, a formal lower bound for the parameter-free Stochastically Extended Adversarial (SEA) model has not yet been established. Proving such a bound is a highly non-trivial task, as it requires simultaneously addressing the hardness inherent in both parameter-free learning and the SEA model itself.\n\nLet's break down the challenges:\n\n- **The Hardness of Parameter-Free Learning:** Even in the standard adversarial OCO setting, moving to a parameter-free framework introduces fundamental hardness, especially in the unbounded domain setting.\n- **The Hardness of the SEA Model:** The SEA model introduces its own layer of complexity. A lower bound for SEA (even with known parameters) must construct a sequence of functions that is difficult to learn. In [Sachs et al., (2023)], the lower bound of the stochastic part is established by showing the contradiction that any algorithm achieving a rate better than $\\Omega(D\\sigma\\sqrt{T})$ could be converted, via an online-to-batch conversion, into an offline stochastic optimization algorithm that violates the well-known $\\Omega(D\\sigma\\sqrt{T})$ lower bound for that setting. However, this proof relies on the assumption of a **known, bounded domain** with diameter $D$. It is not clear how this reduction-based argument could be extended to our **unconstrained (unbounded) and parameter-free setting**, where $D$ is unknown and potentially infinite.\n    \nWe have indeed contemplated this challenging question in our paper, and our thoughts on a related aspect are partially reflected in **Remark 4.2 (lines 262-264)** of our paper. In that remark, we hypothesize that:\n    \n> \"...the $||u||^2$ term may be unavoidable in gradient-variation regret for unconstrained online learning, paralleling how the $d_0^2$ term also appears in the accelerated rate of unconstrained offline optimization.\"\n    \nThis remark connects the $||u||^2$ dependence in our online regret bound to the unavoidable $d_0^2$ dependence in offline accelerated optimization methods. This parallel suggests that the dependence on the squared norm of the comparator might be a fundamental aspect of the problem's hardness in the unconstrained setting, rather than just an artifact of a specific algorithm or analysis. \n    \nHence,  we would like to say constructing a single lower bound for the **parameter-free SEA** setting would require weaving these two sources of hardness together into one difficult problem instance, which is a significant undertaking. Making progress on this undertaking requires first solving each of the two problems above.\n\n---\n\n[Mhammedi et al. (2019)] Lipschitz adaptivity with multiple learning rates in online learning. COLT, 2019.\n\n[Jacobsen & Cutkosky (2022)] Parameter-free mirror descent. COLT, 2022."}, {"review_id": "mDQsPODE3T", "reviewer": "Reviewer_nf4u", "summary": "This paper proposes a parameter-free stochastic online optimization algorithm based on optimistic online Newton step. The algorithm does not rely on problem parameters such as the Lipschitz constant and domain diameter. The regret bound of the algorithm is similar to existing algorithms that need the knoweldge of the problem parameters.", "questions": "1. As discussed in Weakness, The authors are suggested to give some examples, where the regret bound in [27] is much larger (in order sense) than the one in this paper.\n\n2. Justification of the technical challenge of stochastic OCO compared to deterministic OCO", "limitations": "Not applicable.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. Well written paper, which is easy to understand.\n2. Clear contribution: problem-paraemter-free algorithm with regret bound similar to those requiring problem parameters\n\nWeakness:\n1. A problem-parameter-free algorithm was developed in [27]. The authors tried to justify the difference of the proposed algorithm and the one in [27]. The main difference in terms of regret bound is that the one in [27] depends on $\\tilde{\\sigma}^2$ (expectation of supremum), which is generally larger than $\\sigma^2$ (supremum of expectation). Thought the former is obviously larger than the latter, I still doubt how much difference this will make. The authors are suggested to give some examples, where the regret bound in [27] is much larger (in order sense) than the one in this paper.\n\n2. In general, compared to deterministic OCO, what is the main technical challenge of the considered stochastic OCO? In determinic case, the loss functions are changing, while in the stochastic case, the distributions of the loss functions are changing. Except for a variance term for each loss function, what will be the main novelty and technical challenge of stochastic OCO compared to the deterministic one?", "was_revised": true, "final_justification": "The authors have responded to my comments. I would like to maintain my positive rating.", "rebuttal": "We thank the reviewer for your positive review and suggestions. Below we respond to the comments in Weakness (W).\n\n---\n\n>**W1. A problem-parameter-free algorithm was developed in [27]. The authors tried to justify the difference of the proposed algorithm and the one in [27]. The main difference in terms of regret bound is that the one in [27] depends on $\\tilde{\\sigma}^2$(expectation of supremum), which is generally larger than $\\sigma^2$ (supremum of expectation). Thought the former is obviously larger than the latter, I still doubt how much difference this will make. The authors are suggested to give some examples, where the regret bound in [27] is much larger (in order sense) than the one in this paper.**\n\nWe thank the reviewer for this suggestion, which helps to further highlight the strengths of the results in this paper. We show in the following example that the difference between $\\sigma^2_{1:T}$ and $\\tilde{\\sigma}^2_{1:T}$ can, in fact, be arbitrarily large. \n\nLet the decision space $X$ be the union of $n$ disjoint intervals, $X = \\bigcup_{i=1}^n X_i$, where for instance $X_i = [i-1, i)$. For each round $t \\in [T]$, we define the loss functions as follows:\n\n$f_t(x)=\\langle c_{t,i}s_{t,i}, x\\rangle, \\text{if}\\ x\\in X_i$, where $c_{t,i} \\in \\set{0, 1}$ for each  $i \\in [n]$ with $P(c_{t,i}=1) = 1/n$ and $P(c_{t,i}=0) = 1 - 1/n$ and $s_{t,i} \\in \\set{-1, 1}$ for each $i \\in [n]$ with $P(s_{t,i}=1) = P(s_{t,i}=-1) = 1/2$.  \n\nThen we have $\\nabla f_t(x)=c_{t,i}s_{t,i}, \\text{if}\\ x\\in X_i$ and $\\nabla F_t(x)=0$. \n\nHence,  $\\sigma_t^2 = \\sup_{x \\in X} \\mathbb{E}[||\\nabla f_t(x) - \\nabla F_t(x)||^2] = \\sup_{x \\in X} \\mathbb{E}[||\\nabla f_t(x)||^2]=1/n$ and $\\sigma_{1:T}^2=T/n$.\n\nOn the other hand, $\\tilde{\\sigma}\\_t^2 = \\mathbb{E}[\\sup_{x \\in X} ||\\nabla f_t(x) - \\nabla F_t(x)||^2] = \\mathbb{E}[\\sup_{x \\in X} ||\\nabla f_t(x)||^2]=\\sup_{i \\in [n]} (s_{t,i}c_{t,i})^2=\\sup_{i \\in [n]} c_{t,i}$,  where the last step holds because $s_{t,i}^2=1$ and $c_{t,i} \\in \\set{0,1}$ implies $c_{t,i}^2=c_{t,i}$.\n\nLet $Y_t = \\sup_{i \\in [n]} c_{t,i}$. The random variable $Y_t$ is 1 if at least one $c_{t,i}$ is 1, and 0 otherwise.\n\n$P(Y_t=0) = P(\\text{all } c_{t,i} = 0) = (1 - 1/n)^n$,\n\n$P(Y_t=1) = 1 - P(Y_t=0) = 1 - (1 - 1/ n)^n.$\n\n$\\tilde{\\sigma}_t^2 = \\mathbb{E}[Y_t] = 1 \\cdot P(Y_t=1) + 0 \\cdot P(Y_t=0) =  1 - \\left(1 - \\frac{1}{n}\\right)^n.$\n\nFor large $n$, we have\n$\\tilde{\\sigma}^2\\_{1:T} = \\sum_{t=1}^T \\tilde{\\sigma}\\_t^2 \\approx \\sum_{t=1}^T (1-1/e) = T \\cdot (1-1/e) = \\Theta(T).$\n\nIn this example, we can see when $n \\to \\infty$, $\\sigma^2_{1:T}\\to 0$ and $\\tilde{\\sigma}^2_{1:T} = \\Theta(T)$.\n\n**In the final version, we will add a footnote at the bottom of Page 4 to mention that “The difference between $\\sigma^2_{1:T}$ and $\\tilde{\\sigma}^2_{1:T}$ can, in fact, be arbitrarily large.” Also, we will add the details of the above example as a new Appendix subsection.**\n\n>**W2. In general, compared to deterministic OCO, what is the main technical challenge of the considered stochastic OCO? In determinic case, the loss functions are changing, while in the stochastic case, the distributions of the loss functions are changing. Except for a variance term for each loss function, what will be the main novelty and technical challenge of stochastic OCO compared to the deterministic one?**\n\nThanks for your comment. From a certain perspective, the stochastic online convex optimization (SCO) problem setting might appear easier than the adversarial (or deterministic) OCO problem. In the deterministic case, the sequence of loss functions can be chosen by an adversary to be worst-case at every step. In contrast, SCO assumes the loss functions are drawn i.i.d. from a fixed, underlying distribution, which provides a stable structure to the problem. According to [Sachs, et al. 2022], the SEA model provides a unifying framework that encompasses a range of important learning models. This not only includes the fully adversarial model and the stochastic i.i.d. model, but also extends to include the adversarially corrupted i.i.d. model and Random Order Models (ROM) as special cases.\n\nNonetheless, there is a rich and distinct body of research for SCO. The core technical challenge and novelty arise because **simply applying methods designed for the worst-case deterministic OCO setting to solve SCO problems can be suboptimal.** A generic deterministic algorithm is built to be robust against any possible sequence of losses and is therefore unable to exploit the statistical regularity inherent in the i.i.d. assumption of SCO. The innovation in SCO lies in designing algorithms that leverage this statistical structure to achieve much faster convergence rates for minimizing the *expected risk.*\n\nThis suboptimality is most evident under stronger assumptions like strong convexity:\n\n- **For strongly convex and non-smooth functions**, a standard online-to-batch conversion of a deterministic algorithm with $O(\\log T)$  regret would yield an $O(\\log T/T)$ rate. However, specialized SCO algorithms can achieve a faster $O(1/T)$ rate.\n- **For strongly convex and smooth functions:** Deterministic OCO methods cannot break the fundamental regret barriers imposed by the adversarial setting. In contrast, by exploiting both smoothness and strong convexity in the stochastic setting, it's possible to achieve **convergence rates** $e^{-T/\\kappa}$. A simple online-to-batch conversion of a deterministic algorithm cannot produce such an exponential convergence rate.\n\nOur paper's primary focus is on the general convex case. In this setting, the rates for SCO and deterministic OCO are both typically $O(1/\\sqrt{T})$, making the performance gap less pronounced than in the strongly convex case.  Our results for the SEA model, which bridges these two worlds, demonstrate how to achieve near-optimal rates that adapt to the problem's structure—from the purely stochastic to the fully adversarial—without needing to know this structure in advance. Crucially, we show that our parameter-free algorithm can be obtained without loss in performance for the general convex case."}, {"review_id": "NWA33tRjDn", "reviewer": "Reviewer_7Ufi", "summary": "This paper studies the stochastically extended adversarial (SEA) model in the online parameter-free setting where the domain (equivalently, the norm of the comparator) is unbounded and a uniform upper bound on the Lipschitz constants of the cost functions is not known a priori. The authors use the Optimistic Online Newton Step as the base algorithm and adapt it to the parameter-free setting by running multiple copies of base learners and combining their predictions using a multiplicative weight (MsMwC) algorithm. The authors adequately survey the related literature and put their contributions into an appropriate context.", "questions": "1.\tPlease make it clear in the problem statement (Section 2.1) whether the distribution $D_t$, from which the cost functions are sampled, is known to the learner before it selects the action $x_t$ for round t?\n2.\tAs a follow-up to the above question, if $D_t$ is unknown and is never “exploited” by the algorithm, then how does stochasticity help in this setting? \n3.\tIn the definition of cumulative adversarial variation (line 128), what randomness does the outer expectation refer to? The expected gradients seemed to be deterministic (c.f. Assumption 2.3). \n4.\tDo the results hold when the distributions $D_t$’s are chosen adaptively?\n5.\tNo lower bound is established for the regret bounds derived in this paper. Thu,s it is not clear whether the regret bounds are tight. \n6.\tTheorem 4.1 “improves” upon [27, Theorem 5] by moving the expectation outside of the sup over the worst-case conditional variance. However, it does so only at the expense of an extra $||u||^2$ term. The authors discuss this limitation in Remark 4.2, however this discussion is very vague and can be classified as a conjecture. Since this “improvement” is claimed as a major contribution of the paper, I would highly recommend the authors give formal proof for the matching lower bound.", "limitations": "The paper does not have any direct negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is well-written and easy to follow. On the flip side, as discussed in the comments below, it is not clear whether the bounds derived in this paper are tight. Please see the questions below.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I will keep my score.", "rebuttal": "We thank the reviewer for your positive review and suggestions. Below we respond to the comments in Question (Q).\n\n---\n\n>**Q1. Please make it clear in the problem statement (Section 2.1) whether the distribution $D_t$, from which the cost functions are sampled, is known to the learner before it selects the action for round t?**\n\nThe distribution $D_t$ is NOT known to the learner before it chooses its action $x_t$. To make it concrete, we provide the following example:\n\n- The learner's action $x$ represents the parameters of a model.\n- The distribution $D_t$ is the true (and unknown) distribution over data samples, e.g., feature-label pairs $z$.\n- The **expected loss** (or true risk) is the quantity we wish to minimize: $F_t(x)=\\mathbb{E}_{z\\sim D_t}[\\ell (x,z)]$, where $\\ell (x,z)$ is the loss of the model on $z$. The learner never gets to see $F_t(x)$ directly.\n- The **realized loss function**, which is what the learner actually observes at round $t$, is based on a single sample $z_t\\sim D_t$. That is, $f_t(x)=\\ell(x,z_t)$.\n\nIn this setting, the learner never directly accesses or knows the full distribution $D_t$. Its only information comes from observing the sequence of realized loss functions $f_1,f_2,\\cdots,f_T$, one after another.\n\n>**Q2. As a follow-up to the above question, if $D_t$ is unknown and is never “exploited” by the algorithm, then how does stochasticity help in this setting?**\n\nThe algorithm never knows or explicitly \"exploits\" the $D_t$. Let's revisit the concrete example from the response to Q1:\n\n- The learner's goal is to minimize the unknown **expected loss** $F_t(x)=\\mathbb{E}_{z\\sim D_t}[\\ell (x,z)]$\n- The information it actually observes at round is the **realized loss** $f_t(x)=\\ell(x,z_t)$\n\nIn our setting, we can observe information of $f_t(x_t)$ as well as its gradient, where the stochasticity helps in this setting.\n\n>**Q3. In the definition of cumulative adversarial variation (line 128), what randomness does the outer expectation refer to? The expected gradients seemed to be deterministic (c.f. Assumption 2.3).**\n\nThe outer expectation $\\mathbb{E}[·]$ in the definition of cumulative adversarial variation $\\Sigma_{1:T}$  refers to the **randomness in the environment's choice of the sequence of distributions** $D_1, D_2, ..., D_T$. \n\nOur framework is designed to handle the more general and challenging case of an adaptive adversary. Here, the environment's choice of the distribution $D_t$ at round $t$ can be a random variable that depends on the learner's past actions $(x_1,\\cdots,x_{t-1})$. Because the choice of $D_t$ is itself a random process, the resulting expected function $F_t(x)$ and its gradient $\\nabla F_t(x)$ are also random variables.\n\nWe will add a **Footnote** to mention that ‘’If the environment is oblivious,  $F_t(x)$ and $\\sigma_{t}^2$ become fixed (non‑random), hence the expectation operators in the definition of $\\sigma_{1:T}^2$ and $\\Sigma_{1:T}^2$ can be dropped.''\n\n>**Q4. Do the results hold when the distributions $D_t$’s are chosen adaptively?**\n\nAs we discussed in the response to Q3, our results hold even when the distributions $D_t$ are chosen adaptively by an adversary. The adversary is permitted to choose the distribution $D_t$ at round $t$ based on the entire history of the game up to that point, including all of the learner's past actions $x_1, ..., x_{t-1}$ and the past realized loss functions $f_1, ..., f_{t-1}$.\n\n>**Q5. No lower bound is established for the regret bounds derived in this paper. Thus, it is not clear whether the regret bounds are tight.**\n\nTo the best of our knowledge, a formal lower bound for the parameter-free Stochastically Extended Adversarial (SEA) model has not yet been established. Proving such a bound is a highly non-trivial task, as it requires simultaneously addressing the hardness inherent in both parameter-free learning and the SEA model itself.\n\nLet's break down the challenges:\n\n- **The Hardness of Parameter-Free Learning:** Even in the standard adversarial OCO setting, moving to a parameter-free framework introduces fundamental hardness, especially in the unbounded domain setting.\n- **The Hardness of the SEA Model:** The SEA model introduces its own layer of complexity. A lower bound for SEA (even with known parameters) must construct a sequence of functions that is difficult to learn. In [Sachs et al., (2023)], the lower bound of the stochastic part is established by showing the contradiction that any algorithm achieving a rate better than $\\Omega(D\\sigma\\sqrt{T})$ could be converted, via an online-to-batch conversion, into an offline stochastic optimization algorithm that violates the well-known $\\Omega(D\\sigma\\sqrt{T})$ lower bound for that setting. However, this proof relies on the assumption of a **known, bounded domain** with diameter $D$. It is not clear how this reduction-based argument could be extended to our **unconstrained (unbounded) and parameter-free setting**, where $D$ is unknown and potentially infinite.\n    \n    We have indeed contemplated this challenging question in our paper, and our thoughts on a related aspect are partially reflected in **Remark 4.2 (lines 262-264)** of our paper. In that remark, we hypothesize that:\n    \n> \"...the $||u||^2$ term may be unavoidable in gradient-variation regret for unconstrained online learning, paralleling how the $d_0^2$ term also appears in the accelerated rate of unconstrained offline optimization.\"\n    \nThis remark connects the $||u||^2$ dependence in our online regret bound to the unavoidable $d_0^2$ dependence in offline accelerated optimization methods. This parallel suggests that the dependence on the squared norm of the comparator might be a fundamental aspect of the problem's hardness in the unconstrained setting, rather than just an artifact of a specific algorithm or analysis. \n    \n\nHence,  we would like to say constructing a single lower bound for the **parameter-free SEA** setting would require weaving these two sources of hardness together into one difficult problem instance, which is a significant undertaking. Making progress on this undertaking requires first solving each of the two problems above.\n\n>**Q6. Theorem 4.1 “improves” upon [27, Theorem 5] by moving the expectation outside of the sup over the worst-case conditional variance. However, it does so only at the expense of an extra $||u||^2$ term. The authors discuss this limitation in Remark 4.2, however this discussion is very vague and can be classified as a conjecture. Since this “improvement” is claimed as a major contribution of the paper, I would highly recommend the authors give formal proof for the matching lower bound.**\n\nFrom Theorem 5 in [Jacobsen & Cutkosky (2022)], we can directly obtain the expected regret bound as equation (2) scaling with $\\tilde{\\sigma}\\_{1:T}^2$ (expectation of supremum). Throughout our paper, we are dedicated to deriving the bound in terms of $\\sigma\\_{1:T}^2$ (supremum of expectation). From Jensen's inequality, the expectation of the supremum is obviously larger than the supremum of the expectation. To make it concrete, we provide the following example to show that the difference between $\\sigma^2\\_{1:T}$ and $\\tilde{\\sigma}^2_{1:T}$ can be arbitrarily large. \n\nLet the decision space $X$ be the union of $n$ disjoint intervals, $X = \\bigcup_{i=1}^n X_i$, where for instance $X_i = [i-1, i)$. For each round $t \\in [T]$, we define the loss functions as follows:\n\n$f_t(x)=\\langle c_{t,i}s_{t,i}, x\\rangle, \\text{if}\\ x\\in X_i$, where $c_{t,i} \\in \\set{0, 1}$ for each  $i \\in [n]$ with $P(c_{t,i}=1) = 1/n$ and $P(c_{t,i}=0) = 1 - 1/n$ and $s_{t,i} \\in \\set{-1, 1}$ for each $i \\in [n]$ with $P(s_{t,i}=1) = P(s_{t,i}=-1) = 1/2$.  \n\nThen we have $\\nabla f_t(x)=c_{t,i}s_{t,i}, \\text{if}\\ x\\in X_i$ and $\\nabla F_t(x)=0$. \n\nHence,  $\\sigma_t^2 = \\sup_{x \\in X} \\mathbb{E}[||\\nabla f_t(x) - \\nabla F_t(x)||^2] = \\sup_{x \\in X} \\mathbb{E}[||\\nabla f_t(x)||^2]=1/n$ and $\\sigma_{1:T}^2=T/n$.\n\nOn the other hand, $\\tilde{\\sigma}\\_t^2 = \\mathbb{E}[\\sup_{x \\in X} ||\\nabla f_t(x) - \\nabla F_t(x)||^2] = \\mathbb{E}[\\sup_{x \\in X} ||\\nabla f_t(x)||^2]=\\sup_{i \\in [n]} (s_{t,i}c_{t,i})^2=\\sup_{i \\in [n]} c_{t,i}$,  where the last step holds because $s_{t,i}^2=1$ and $c_{t,i} \\in \\set{0,1}$ implies $c_{t,i}^2=c_{t,i}$.\n\nLet $Y_t = \\sup_{i \\in [n]} c_{t,i}$. The random variable $Y_t$ is 1 if at least one $c_{t,i}$ is 1, and 0 otherwise.\n\n$P(Y_t=0) = P(\\text{all } c_{t,i} = 0) = (1 - 1/n)^n$,\n\n$P(Y_t=1) = 1 - P(Y_t=0) = 1 - (1 - 1/ n)^n.$\n\n$\\tilde{\\sigma}_t^2 = \\mathbb{E}[Y_t] = 1 \\cdot P(Y_t=1) + 0 \\cdot P(Y_t=0) =  1 - \\left(1 - \\frac{1}{n}\\right)^n.$\n\nFor large $n$, we have\n$\\tilde{\\sigma}^2\\_{1:T} = \\sum_{t=1}^T \\tilde{\\sigma}\\_t^2 \\approx \\sum_{t=1}^T (1-1/e) = T \\cdot (1-1/e) = \\Theta(T).$\n\nIn this example, we can see when $n \\to \\infty$, $\\sigma^2_{1:T}\\to 0$ and $\\tilde{\\sigma}^2_{1:T} = \\Theta(T)$.  Also, the bound presented in equation (2) becomes tighter only when $||u||_2 > \\sqrt{T}$. However, in this regime, the entire bound scales as $O(T)$, which makes the regret bound even meaningless.\n\n---\n\n[Jacobsen & Cutkosky (2022)] Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. In Conference on Learning Theory, pages 4160–4211. PMLR, 2022."}]

Author rebuttal:

Meta-review: This work studies the challenge of adaptivity in the Stochastically Extended Adversarial (SEA) model, a model proposed to bridge between i.i.d. and fully adversarial settings in online learning. This work is the first to provide adaptive rates in this model, which I believe makes this model much more relevant and usable in practice. Reviewers noticed some limitations, but they are overall satisfied and enthusiastic about the merits of this paper. Hence, I strongly recommend acceptance.
Decision: Accept (poster)