An Ellipsoid Algorithm for Online Convex Optimization
Authors: Zakaria Mhammedi
Venue: NeurIPS 2025 poster ()
Keywords: Online Convex Optimization
Projection-Free
Ellipsoid Method
Separation Oracle
Primary area: optimization
TL;DR: A new projection-free algorithm for online convex optimization that relies on a separation oracle and does not require preconditioning of the feasible set.

Abstract: We study the problem of Online Convex Optimization (OCO) over a convex set $\mathcal{K} \subset \mathbb{R}^d$, accessed via a separation oracle. While classical projection-based algorithms such as projected Online Gradient Descent (OGD) achieve the optimal $O(\sqrt{T})$ regret, they require computing Euclidean projections onto $\mathcal{K}$ whenever an iterate falls outside the feasible set. These projections can be computationally expensive, especially for complex or high-dimensional sets. Projection-free algorithms address this by replacing projections with alternative oracle-based procedures, such as separation or linear optimization oracles. However, the regret bounds of existing separation-based methods scale poorly with the set's \emph{asphericity} $\kappa$, defined as the ratio between the radii of the smallest enclosing ball and the largest inscribed ball in $\mathcal{K}$; for ill-conditioned sets, $\kappa$ can be arbitrarily large.

We introduce a new separation-based algorithm for OCO that achieves a regret bound of $\tilde{O}(\sqrt{dT} + d^2)$, with only logarithmic dependence on $\kappa$. This removes a key limitation of prior work and eliminates the need for costly geometric pre-processing, such as transforming $\mathcal{K}$ into isotropic position. Our algorithm is based on a novel reduction to online optimization over a sequence of dynamically updated ellipsoids, inspired by the classical ellipsoid method for convex optimization. It requires only $\tilde{O}(1)$ separation oracle calls per round, on par with existing separation-based approaches. These advances make our method particularly well suited for online optimization over geometrically complex feasible sets.

An Ellipsoid Algorithm for Online Convex Optimization
Zakaria Mhammedi" ittameddi@googlee com
Abstract
We study the problem of Online Convex Optimization (OCO) over convex set K c IR accessed via a separation oracle. While classical projection-basee algorithms such as projected Online Gradient Descent (OGD) achieve the optimal O ((VT) regret, they require computing Euclidean projections onto K. whenever an iterate falls outside the feasible set. These projections can computationally expensive, especially for complex high-dimensional sets. Projection-free algorithms address this by replacing projections with alternative oracle-based procedures, such as separation or linear optimization oracles. However, the regret bounds of existing separation-basee methods scale poorly with the set's asphericity k, defined as the ratio between the radii of the smallest enclosing ball and the largest inscribed ball in IC; for ill-conditioned sets, K can be arbitrarily large.
We introduce a new separation-base bound of ((vT++d)) with only logarithmic dependence on K. This removes a key limitation of prior work and eliminates the need for costly geometric pre-processing, such as transforming I. into isotropic position. Our algorithm is based on novel reduction to online optimization over sequence of dynamically updated ellipsoids, inspired by the classical ellipsoid method for convex optimization. It requires only ((1) separation oracle calls per round, on par with existing reparation-basee approaches. These advances make our method particularly well suited for online optimization over geometrically complex feasible sets.
algorithm for OCO that achieves regret
Introduction
Convex optimization plays central role in many areas of modern machine learning and related fields. While classical algorithms are designed for settings with a fixed objective function, recent work has increasingly considered the more general framework of Online Convex Optimization (OCO) [10] OCO models sequential decision-making problems where a possibly different convex function is revealed at each round, potentially chosen in an adversarial manner. This framework captures broad range of learning scenarios and provides a unified lens for analyzing them. Standard online-to-bated conversion techniques 3 |2 allow regret guarantees in OCO to translated into convergence rates for offline (fixed-objective) and stochastic convex optimization problems. In contrast, the analysis of traditional offline methods does not always extend to stochastic settings. Even stochastic non- convex optimization has benefited from the OCO framework: [5] showed that stochastic non-convex optimization can be reduced OCO, and that this reduction leads to the best-known convergence rates for finding stationary points. Given its broad applicability, designing computationally efficient OCO algorithms with strong regret guarantees remains an important direction of research.
In constrained optimization settings where the decision variable must lie in a feasible set K. the classical (projected) Online Gradient Descent (OGD) 2 requires Euclidean projection onto IC
"Google Reseach, NYC.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

whenever an iterate falls outside K. This step can be computationally expensive when K. has complex structure, and may limit the practicality of OGD. To address this, projection free algorithms have been proposed. These methods avoid explicit projections; for example, the Frank-Wolfe algorithm 7 uses linear optimization over K.. More recent approaches rely on membership or separation oracles to enforce constraints [18 8 17 [] In particular, separation oracles can often be more tractable to implement and use in settings where projections are costly.
The aforementioned projection-free algorithms are analyzed in the OCO framework, where at each round the algorithm selects a point w, from convex feasible set K. RR It then incurs loss fe( wi), where fi is a convex function that may be chosen adversarially. The goal is to ensure a small regret uuP Σ (J,, - (u)). While projected OGD achieves the optimal O(VT) regret, projection-free methods based on linear optimization oracles have not improved beyond O O(T5/1) 12 without additional structural assumptions on the OCO problem. Separation oracle-based methods proposed by [8] [ achieve the optimal T -'dependeecce with a ((v/T) regret bound, where k == R/r denotes the set's asphericity, defined as the ratio of the radii of the smallest enclosing and largest inseribed balls in K. However, the linear dependence on K. is not desirable, as K can be arbitrarily large for ill-conditioned sets. Although preprocessing I. into isotropic position ensure K d up Odd)) separation oracle calls 16 and does not fully resolve the issue: the dependence on k may reappear implicitly through changes in the Lipschitz constant of the loss functions after the isotropic reparametrization. A more recent method [99] improves this by achieving a regret bound of Ö(VdT'+ kd), making the k term independent of T. However, a residual dependence on the potentially large asphericity remains.
6
this transformation is computationally expensive
Contributions. This paper introduces new projection-free algorithm for OCO based on separation oracles. Our key contribution is an algorithm that achieves a regret bound with only logarithmic dependence on the feasible set's asphericity k. Specifically, it guarantees a regret of Ö Ö(vdT + d²) without requiring expensive geometric preprocessing of the set K. Thus, this approach more practical and robust to the feasible set's ill-conditioning compared to prior separation- baaed methods.
The algorithm preserves the oracle complexity of existing separation-base based approaches, requiring only Ö(1) separation oracle calls per round. The total computational cost per iteration is Ö(Csep d where Czep denotes the cost of a single separation oracle call and w is the matrix multiplication exponent. Our approach integrates ideas from the classical ellipsoid method with reduction online exp-concave optimization over a sequence of dynamically updated ellipsoids. A slight modification of the standard online-to-batch conversion yields convergence rate of / (e/T) for Stochastic Convex Optimization (SCO), where o² denotes the gradient variance, and rate of (dd (T) in the offline setting (a 0). A detailed comparison with prior results is presented in Table
Limitations. We do not provide regret lower bounds or experimental validation for our algorithm.
Table 1: Comparison of projection-free algorithms for OCO and Stochastic Convex Optimization
(SCO). x R/r is the asphericity of the feasible set K. d² is the variance in SCO.
Regret bound in OCO
Convergence rate SCO (a 2 0)
Number oracle calls per round
Runtime per round
Papers
Oracle type
O(T
0 Ti/s
Linear optimization
1
Clintee d
18
O(KVT)
0
Separation
0(1)-((1)
Csep d
19
Ō(VoT + rd)
δ 0 ad 8(0v $ +7)
Separation
Õ(1)
Cuep df
This paper Ö(VoT+&)
Separation
Õ(1)
Capp de
Related works. This work builds upon the recent line of research on separation oracle-based projection-free algorithms for OCO. The prior art established methods achieving (<</T) [18 17 and subsequently Ō D(VdT+xae +x) regret bounds 19.. A key limitation of these results is the dependence on the asphericity k. Our work directly addresses this limitation by providing an algorithm whose regret guarantee depends on only logarithmically.

---

Our algorithmic approach is inspired by the classical ellipsoid method [14, 23 2, which we adapt to the online optimization setting. While the classical method is designed for offline problems. our algorithm addresses the sequential nature of OCO by combining ellipsoid updates with reduction to online optimization over a sequence of changing ellipsoids that always contain the feasible set K. Our reduction shares conceptual links with the one presented in [9] but crucially, our method updates these ellipsoids adaptively to better "approximate" the shape of the feasible set, unlike prior approaches using fixed ball. This ability to adapt to the feasible set's s geometry on the fly is key feature distinguishing our method from previous separation- approaches.
2
Preliminaries
In Section 2.1] we formally introduce the OCO setup along with the notation used throughout the paper. [Section 2.2 presents key concepts we rely on such as Gauge distance and Gauge projections.
2.1 Setup and Notation
Let KC be a closed convex subset of the Euclidean space R. where we assume d 2 throughout P We consider the standard framework of OCO over XC, in which an algorithm generates a sequence of decisions (we)t21 within IC. On each round t E [T']. the algorithm selects a point w, K. and incurs a loss fi (w:), where ft : IC + R is convex loss function that may depend adversarially on past decisions. As standard in this setting. we assume access to subgradient gi é (wy) rather than the full loss function. The performance of the algorithm is measured by its regret after T rounds, defined as Regr == ΣTh fe(w:) unx Σi (u... Due to the convexity of each fú, the regret can be upper bounded by the so-called linearized regret: Σi wt) inf Σt= (g,, u). Hence, suffices to control the linearized regret to bound Regr.
Building on recent projection-fiee free methods, this work aims to develop an efficient OCO algorithm that achieves sublinear linearized regret with only logarithmic dependence on the asphericity K, while requiring a logarithmic number of separation oracle calls per round.
Definition 2.1 (Separation oracle). A Separation oracle Sepe. for set C is oracle that given é Rd returns (b, v) E {0,1} x B() (where B1) denotes the unit Euclidean ball in Rd), such that
* b= 0 and v 0, if u é C; and otherwise. b= and (v, u) (v, w). all K.
We denote by Caep (C) the computational cost of one call this oracle.
In addition the standard OCO setup, we impose two common assumptions. To present these assumptions, we let |. denote the Euclidean norm and use (B 7) c Rd to denote the ball of radius y > 0 centered at e E IRd. With this, the first assumption asserts that each loss function fe is G-Lipschitz with respect to II], for some constant G > O. The second assumption requires that the feasible set IC is bounded and lies between two Euclidean balls.
Assumption 2.1. There is some G > O, such that for all t 2 1, the function ft K. + IR is convex and for all KC and g E (w) we have Igll S G.
Assumption 2.2. The set C satisfies B(co,r) EK B(R) for some r, R O, and co E B(R).
Prior work 18 19 assumes the feasible set K. satisfies ((r) S K. B(R) for r. R O. This paper relaxes the condition B(r) S K. Requiring I. contain a positive-radius ball centered at the origin is restrictive for general convex sets; such a ball may only exist after translation, its radius r can be small even then, and computing an optimal translation can be computationally expensive. Our algorithm eliminates the need to compute this translation. dynamically adapting to the geometry of IC instead. We also note that both Assumption 2.2 and the assumptions in [18) 19 require K. to have non-empty interior. This is without loss of generality, as any set I. contained in a lower-dimensiona affine subspace can be reparametrized as full dile-siinlll set with non-empty interior.
Throughout, we let 6 R/r denote the asphercity of IC with r, R as in Assumption 2.2
In one dimension (d= = 1), computing Euclidean projections is straightforward, making projected gradient methods both efficient and optimal.
3

---

Algorithm I Gau H, 6): Approximate value and subgradient of the Gauge distance.
require: Separation oracle Sepe. input vector w E IR H Rdxd PSD, C Rd and 6 0. returns If ws & and c E C, then S = Sc-e(w c) and = e c).
1: Set (b, v) (w),
1/b=1 if eC; and 0, otherwise. // This corresponds to the case where w C.
2: 6 then
3: Set (5,8) ()== (0,
4:
return (S, s).
5: Set (b) (c)
1/b=1 if ceC; and 0, otherwise.
6:
if
then
7: Set (S, 8) (0, 3dv/ / Hn).
8:
return (5, 8).
9: Set a 0,
and (a+ 8)/2. 5 do
10:
while B - a 8d
11:
Set (b, v) + Sepc (1 w c) c).
=/b= if u(w-c) - ccE; and 0, otherwise.
12:
i v/-vvle v. (w (w- c) < 2d / v. Hu then break
Set - y if
and B - otherwise.
14:
Set J1 + (a /2/
15: Set S a=" and
B.v (w-c)
16:
return (S,
Additional notation. We denote by == {x Rd: (z. v) 1, Vy KC} the polar set of KC 1 We let Sdxd denote the d d positive-definite matrices and | vx Hæ for æ Rd and H Raxd For E Rdd H Soxd, define the ellipsoid {(c, H)) {u Rd (u-c)² H- 1). We O() hide poly-log factors parameters appearing in the expression.
2.2 Gauge Function, Distance, and Projection
We now introduce the concepts of the Gauge function, distance, and projection [8 19]. which central to algorithm and existing separation- baased methods. Throughout this section, these concepts are defined using a convex set C S Rd containing the origin. Here, C is used for definitional purposes only and does not necessarily correspond to the feasible set IC in OCO problem.
Definition 2.2. The Gauge function "i IRd of defined as (c( inf R2o e AC).
The Gauge function "i can be viewed as "pseudo" norm induced by the convex set C; it becomes true norm when is centrally symmetric (i.e., C = -C). With this, we define the Gauge distance.
Definition 2.3 (Gange distance). The Gauge distance function Se corresponding to the set is
Sc) = (o))) 11)
Rdd
When the set contains the origin in its interior. [88 showed that Se has the more distance-like expression (u) inf Vo (u- x), for all a é Rd. From this expression, we see that the Gauge distance generalizes the Euclidean distance, which obtained by replacing " [resp. C] with the Fuclidean norm IIl [resp. B(1)]. Observe that when E C, then Sc(u) O. Otherwise, Sc(u) 0.
Gauge projection. Similar to 18 19 algorithm relies Gauge projections to ensure fea- sible iterates. The Gauge projection operator 11 induced by C is the mapping: 115 (u) == argmin,se (c 2). for all u Rdd [8 showed that when O lies in the interior of C, the gauge projection admits the closed-form expression 11 (u) I+Se(u)' This makes the gauge projection particularly useful in our setting, as it can be approximated efficiently (by approximating the gauge distance Sc) using logarithmic number of separation oracle calls.
In this paper, we use Algorithm to approximate both the Gauge distance and its subgradients, which are required by our OCO algorithm. The algorithm, similar to 19 Algorithm 1]. uses calls to separation oracle for C and binary search approximate the distance function. In a nutshell, given input (C, H, c) such that C and w C. Algorithm returns pair (S, s). where S is

---

an approximation of the Gauge distance Sc-c(w-c)) and is an approximate subgradient of this function w c. Algorithm Iis slightly more general than [19 Algorithm in that it allows for + O and can handle & C. TTii feature is important because our projection-free algorithm will operate on a sequence of potentially uncentered ellipsoids. The next lemma is proven Appendix A
Lemma 2.1. Let 5' (0, w. C R2, C Rd convex, and e aegd be given such that C & E == {a) (x Hx - -c) S 1) and w é E. Consider call to Algorithh 1 with input C,H,H,,,,,, and let (S, 8) be its outpur. Then, either |H s|| 2d;
have for all u Rdd
C.E. C, Sc-c(w-or - c) s S & ( e) + 6, and Sc-c(u- c) 2 Sc-e(w c) (u - (w= & 6. Further, Algorithm makes at most 2 + ( 18) calls to the separation oracle Sepe-
As will see in Section 4.1 the case where |/ 2d in Lemma 2.1 corresponds to a situation where the set H (C c) is too "thin" in the direction H We will later use this test to dynamically update ellipsoids containing the feasible set, adapting them to its geometry.
3
Overview and Limitations of Previous Approaches
In this section, we briefly review existing ipparation-based approaches that our work builds on and highlight their main limitations that we address in this paper.
18 19 reduce OCO over IC to OCO over a ball B(R) 2 K. For this reduction, they rely on an inner OCO algorithm that produces iterates (u,) in BB (where Euclidean projections are cheap), from which feasible iterates (w,) are extracted using Gauge projections (also cheap when given a separation oracle for KC; see Section 2.2p. The feedback vector fed to the inner algorithm is given by
Jt 9: 1[ (9:. u²) < 0} (gt,, wt) 8t,
(1)
where 8, E OSx (w:) ). The subgradient 8, can be computed efficiently using the GaugeDist subrou- tine in Algorithm see Section 2.2 This choice of g. guarantees that
vt. 1, Vu e IC, (gt, Wt; 1) S (gt, u4 - u))
which represents key result in their reduction: see 19 Lemma 4.1]. The inequality in (2) is useful
because allows one to bound the instantaneous regret of their algorithm (left-hand side of (2) in
terms of that of the inner algorithm (right-hand side of (2). Thus, if the inner algorithm achieves low
regret over the ball B R), this guarantee essentially carries over to their final algorithm via (2)
The key issue with this approach is that standard OCO algorithms typically have regret bounds that scale with the maximum norm of the feedback vectors. Thus, if the inner algorithm one such algorithm, its regret will scale linearly with max, [7] ll@: Due to the presence of s in the definition of T. in (1) and because ||se]] can be as large as the asphericity = R/r (see [19] Lemma 4. JJ).), the resulting regret bound is of order OKk/T) (in our work, we aim for logarithmic dependence on si).
In follow-up work, 119 manages move the dependence on into lower-order term, achieving final regret bound of Õ(ViT + Rd) by using variant of ONS the inner algorithm. We now sketch why ONS was key to achieving this result; this is relevant as we also use ONS as the inner algorithm.
Advantage of ONS. The regret of ONS with learning rate 17 can be bounded by (see 19 Thm. 3.1))
Vue IC, where B == max ggcl- " Σ (g,, u)² + 0(1) dllo(B1)
2 [e[T]
17
tc[T]
On the other hand, as observed by 19 as long as S (max lg.. -)l)
Eq. (2) implies
7 (g). wr u) (g.. w. - up²) s Σ (g. u, - uu " (g. us - -u)² Vu K.
2
Combining this with (3) and rearranging terms implies that the regret Σ wi- u) is bounded by 2 ET-1(9 w; - u)² + 0(1) dlog(BT) for all u e K. Tuning 7 optimally in the interval between 0 and (maxeer)) Iuu - u. g.)l) -1 yields the regret bound
of G log (Bg( + max (u+ u. (.) dlog (log(B)) )B7)
tc[T]
5

---

for all u K. The key takeaways from (4) are two-fold: 1) Unlike the regret bound of [18] where the dependence on B is linear, the B term in ( which grows with the maximum norm of the vectors (s:), appears only inside logarithmic term; and II) although the scale of the vectors (&t) still affects the bound in ( outside logarithms through maxx<[T]] ((u, u. (.)l this quantity can significantly
smaller than St itself, as we will see the analysis.
19 show that (4) can be bounded from above by OV + kd). However, the xd term, while independent of T, can still be arbitrarily large for ill-conditioned sets, and we would like remove it.
Limitations of reparametrization. Although any set K can be put into isotropic position so that its asphericity и. is reduced to at most O(d) [ computing approximate isotropic transformation may require up to (dd)) calls to a separation oracle [[6] which can be computationally prohibitive many practical applications.
4 Algorithm and Guarantees
In Section 4. we present our algorithm and outline the core ideas behind its design and how they allow us overcome the limitations of previous approaches discussed in Sectionn 3 In Section 4.2 we formally state our algorithm guarantees.
Algorithm 2 Ellipsoid algorithm for online convex optimization.
require: Rounds T, feasible point C K. r, R, and G,
1: Set n. +- It + 1 B + ngG c1 + c, H1 + R2I, E1 + BI, (Auin dmaa) + 2ix r
40d2
2: for t= 1...., T
3: Set (Sr, 8:) + GaugeDist (u; H1, S). 11 St m Sk-o (ur (uc- 81 0SK-o, (ut cc).
if 1H7,1/2s sall 2d then
4:
5:
Play wi e and observe gt E (w))
6:
Set g. 0.
// Update the ellipsoid containing X.
7:
Update Gt-1 C. 2d+2
Hese
H.,
8:
Update Het1 + 1d--1
1d8-1
H 28--d-1
H.s.s H:
9:
else
10:
Play wi = -1 + ct and observe gr @f((w:). T+S,
// wi 11 (w: - Ci) + Cc
11:
Set D. = 9t - 1[( un - ct) < 0} (gi, w. ci)
Update Ct-1 C₁ and H41 He.
/* Do one ONS in Ex = {ul (u C(n) ( Hill (u c.n) s 1} given "loss vector" g: */
13:
Set Ex.1 + Ex.1 + 199h9
14:
Set Zetl ur Enhgg
// Approximate Usi1 + arg min,
uct (#t-1 - - EE-1 -w) with PoE Algorith 3
15:
Set u1+1 +
C41,, BR =-1 HGt1; Aminy Amax: E).
4.1
Algorithm Overview and Design Rationale
Our main algorithm AAloriihhm 2) effectively reduces OCO over the feasible set K. to OCO over sequence ellipsoids
ε, E,
12
each containing K. with centers (cx) dRd and positive definite matrices (H1, Sond Intuitively, with each update, the ellipsoid increasingly pulls in around the feasible set, yielding a progressively tighter approximation of K. and allowing to bypass the need for any expensive pre-processing of K. even when is ill-conditioned. The advantage of working with ellipsoids containing IC instead will that
of IC itself is that projections onto the former can be carried out more efficiently; the complexity of doing so is almost independent of the geometry A. The specifics of how the ellipsoids constructed and when updates occur will be explained in detail in the sequel.
Inner algorithm. Similar to prior works 19,, our reduction relies on an inner OCO algorithm whose iterate round lies within the ellipsoid &,. For clarity of exposition, directly instantiate

---

the inner algorithm with variant of ONS (see Line 13 and Line 15) that is adequate to achieve our desired regret bound. The version of ONS we use similar to the original algorithm proposed by [II] with the key difference is that we perform generalized projections over a sequence of varying sets, namely the ellipsoids (Ex), rather than projecting onto a fixed set; the generalized projection solves the problem uee ||ue ca for a convex set C. and a matrix H e $00
Efficient "projections." In Algorithm 2 we use the poE subroutine (described in Appendix C to efficiently perform generalized projections onto the ellipsoids (E,) (see Line 15]; this costs O(d²)) The iterates (u+) produced by ONS are then projected onto the set I. using Gauge projections (Line and Line 10), which we showed can be implemented using logarithmically many calls to a separation oracle for K. (see Sectionn 2.2). This yields sequence of iterates (w,) that are guaranteed to be in AC.
Feedback to inner algorithm. The feedback given to the inner ONS algorithm is a modified gradient vector F: (reminiscent of the choice of 9: in prior works displayed in (1) defined as
gt g: [[ u, - cx) < 0}- (gt, 20,- - cz) 8t,
where C₁ is the center of the ellipsoid at iteration t, and st is an approximate subgradient of the Gauge distance function Sk-c. u, 1 C. This subgradient computed efficiently (see Line 3) using the GaugeDist subroutine from Seection 2.2 Similar to (2) this choice of g: ensures that
(w, u. .:): S (u: (u:-u.gt. Ur),, 21 1, Vu K,
(6)
where gt E Of (r) is a subgradient of the loss function at the outer iterate wi, and ut, is the iterate of the inner ONS algorithm. This inequality is useful because it allows us relate the instantaneous regret of Algorithm to to that of the inner OÑS algorithm. Thus, as long as ONS, run over the sequence of ellipsoids containing K., guarantees low regret, we get low regret for Algorithm
As mentioned earlier, one advantage of working with ellipsoids that contain IC is that projections onto them can be performed more efficiently than projections onto I. itself. However, this alone does not
explain our use of a sequence of varying ellipsoids, rather than a fixed ball as in [18 19). The key reason is that varying ellipsoids allow to dynamically adapt to the geometry of K. and avoid any linear dependence in K in our final regret bound.
Mitigating x-dependence. As discussed in Section 3 prior methods incur a term due to either a large norm of 8, E 0Sx (w:)) (as in [88 or large inner product (u, u, g+Yl for some / and comparator u (as in [19). In the latter case, observe that ((u, u. Fe)l becomes large only if
(u, - u. st)] is large, due to the expression for g. in (1 (also the case for our choice of g. in (5)
As we will clarify shortly, a large value of (ut u. s;) indicates that IC is too "thin" in a certain direction. Our approach exploits this fact to adapt to the geometry of IC whenever such thin directions are detected. On the other hand, our analysis shows that these detections can happen at most (dd)) times, and outside of the "detection rounds". : the inner product (u, u. T. is independent of K, and the regret incurred by the inner ONS algorithm is well controlled.
Gervetry-driven ellipsoid updates. We now examine the condition that determines when the ellipsoid is updated in Algorithm 2] From Line Line 8 see that update is triggered only when [112." s 2d; in (9) below, we relate |H."'' st to the magnitude of (wu: - u, s:)l in the previous paragraph. Here, 8, is approximate subgradient of Sx-e, at u, c₁. The condition | |H,"' s, 2d can be interpreted as a test for whether IC is thin in some direction relative to the ellipsoid
& E(c,, H.) {u E Rd (u - c.) H, 1 (u s1)
We now clarify this claim. Suppose that 11,11221 > 2d. Since s, aSSk-ex (u, c.) (ignoring any approximations for now), it follows that 8, (KC (x)) Lemma G.5). Therefore, by the definition of the polar set (KC - we have
Vu IC, (u uu- 81) s 1.
Define the unit vector v. := -1,,12 / / 11,'' Then, by (7) (7) and the assumption that ||11,/22 sell > 2d, (u.
we have for all u E K. -c,, (H1 1/2 u, vz) a a.l
S |
S 2d Equivalently, we have
Vue e 1/ 1/2 (KC - -x),, (u, vz) 5 2d
1
(8)
7

---

which implies that the reparametrized set (K ct) is thin in the direction of v,. When this occurs, we work with a new ellipsoid E--1 that better aligns with the geometry K in that direction. Specifically, we set E1+1
(Ce--,-H++1) where C++1 and H(+1 are as in Line 7 and Line 8 of Algorithm respectively. We now motivate these choices for Ct+1 and H++1-
Suppose that || sell > 2d. and therefore (8)
holds. Then, by (8) and the fact that K. S & we 0, s 1 /2d). Thus, by Lemma (an adapted result from the
have (K {u E BB1) uuv,
analysis of the ellipsoid method; see, e.g., (2] Lem. 2.3]), we have:
=1--11 1,, ( cx) Eee1 = =E(- 2(-)11 H2+1), where He-1 == 4d--4 (La
2d 20-ad-1
It can be verified that Ct H, E 1 which implies that K. - E Lemma B. also implies that vol( s exp( ø2) vol ( that is, we not only maintain the invariant A. S E but we also ensure that the volume of the ellipsoid shrinks with each update, providing a tighter approximation of K. Since X s &g, for all t 2 1, the volumes (vo)(E,)) cannot shrink indefinitely, enabling us to bound the number of ellipsoid updates.
E(c+11 Hot)), with C++1 and H4+1 as in Line 7 and Line 8
Bounding the number of ellipsoid updates. Assumption 2.2 and that vol(Ex-1) S vo,) we can show that the number of updates is bounded by O(d log( Rfr)) (recall that B(co: r) E K BB (R)).. In other words, the condition on Line 4| be satisfied at most (nd log RR/r) times.
Regret on update rounds. In our analysis, whenever the ellipsoid is updated at round & (i.e., the condition |HH''ss/ st|l 2d on Line 4 is satisfied), the algorithm simply plays default vector e AC. The cumulative cost of playing e over these rounds is at most Odd log( R/r)), due to the bound on the number of updates; we are willing to absorb this overhead into the overall regret bound.
Regret on no-update rounds. Now, we argue that when the ellipsoid is not updated at round & (i.e., 1/2 when |H stll 2d), the inner product (u, u. remains bounded independently of for all u E IC, which ensures that the regret of the inner ONS algorithm on these rounds remains small.
1/2 sz < 2d (i.e., no ellipsoid update). In this case, by Hölder's 's inequality: Suppose that |H
1/2 (u: - u) |H, sell 2d, Vt [T][ E (u u. s,)1 $ H,," (u:
(9) where the last inequality follows from the assumption that | ||H s₁ S 2d and that both un and u lie in & Indeed, u, & because the inner ONS algorithm outputs iterates in &,, and & because our construction maintains the invariant K. S & The inequality in (9) implies that for all u e I, we have (u, u. G.)l s OGd) (by the definition of y. in (5) and Assumption 2.1 which, from (4) is what we need to ensure the regret bound of the inner ONS scales only logarithmically in k.
4.2 Algorithm Guarantees
We now formalize the claims made in Section 4.1 and present the regret guarantee of our algorithm. We start with the invariants that Algorrign 2 maintains. The proof of the lemma is in Appendix E.
Lemma 4.1. Let T 2 1, 1J >>>0 O, and e be given and suppose that Assumption 2.2 and Assump
Jion 2. hold with 0 < r S R and G O, respectively. Consider a call to Algoorihh 2 with input (T,c,r, R. G. Then, for any subgradients (gt), the variables in Algorithum 2 satisfy for all t [T]:
1. K.E& {u. R (u- -.) T H.! (u (u-c;)
ct) $ $1;;
2. If If H,s, 2d, then C, E K.;
3. vol(E) Se Nt RPd, where No -+1 11 V 87 11 2d);
4. N, Sel log(R (R/r);
5. mmin (H.) 2 and o (max S (1+2/d)) R2 K 162
Consistent with the claim made in Section 4. Item of the lemma establishes that the set K. is always contained within the ellipsoids (E.). Item 2 shows that c, XC whenever [1 8: S 2d, ensuring that when the ellipsoid is not updated, the center c, of the ellipsoid &, lies within K. This is crucial for the correctness of our reduction, and in particular for the validity of Item shows that the volume of the ellipsoid shrinks by a factor of E -1/(8d) whenever an update occurs. Item bounds the total number of such updates by O( d2 (R(r))).
8

---

The next lemma formalizes our reduction result in (6) showing that the instantaneous regret of Algorithm is bounded by the instantaneous regret of the inner ONS algorithm. The lemma also bounds key quantities discussed in inSSection 4.1 that appear in the ONS regret bound.
Lemma 4.2. Let T 2 2, 11 0, and e K. be given and suppose that Assumption 2.2 and Assumpp
rion 2. hold with 0 < r $ R and G > O, respectively. Consider a call to Algoritim 2 with inpur (T, R. n) Then, for any subgradients (gt), the variables in Algorithm 2 saatisyy for all tllt [T]:
1. @ G 4kd);
2. wt E EK;
3. For all E KC [uu - Ue M...:i>\ 0. 22G 4d):
4. For all u E KC, (gi. we u) [[ 8: His, s 2d} s (ge. uu u) + 3GR T
The proof of the lemma in Appendix E.I Item bounds the norm of the feedback vectors (g+ passed to the inner ONS algorithm. While the norm of T. can be as large as O(Gnd), this is acceptable because the regret bound for ONS only involves |gg. inside logarithmic terms (see (4)
and recall that B = max (7) g This is precisely why the choice of ONS as the inner algorithm
is essential to our approach. Item 2] guarantees the feasibility of the iterates of|Algorithm [tem 3
shows that the inner product [u, - u, 9:)l is at most O (RGd) for all e K. and crucially, this bound independent of K. This key to ensuring that the regret of the inner ONS algorithm does not depend к outside of logarithmic terms; see (4) Finally. [tem 4 a consequence of our specific choice of g: in (5) shows that, on rounds where no thin direction is detected, the instantancous regret of Algorthmm 2 bounded by that of the inner ONS algorithm (up to small additive term).
With these results in place, we now proceed to bound the regret of the inner ONS algorithm. The bound in the next lemma should be reminiscent of the ONS bound displayed in (3) (proof in Appendix D).
Lemma 4.3 (ONS Regret). Let T 2 2, y) O, and e K. be given and suppose that Assumption 2.2 and Assumption 2.I hold with 0 < S R and G > O, respectively. Consider a call to Algorithm 2 with input (T, R, G,T). Then, for any (g:), the vectors (gt, Un Ce, H1) in illloorittmm 2) satissy
T Vu Σ u u)
T
Ge, u u)² 2nn R² 240n G2 dlog(1 + T2 R2/13)
7
Σ
2
2n
and u. E = E(ce, H.), VI 2 1. Further, given Gt. computing Ue+1 costs most Oad (Tg())
The proof closely follows the original analysis of the ONS algorithm by M. despite the fact that we are working with a sequence of varying feasible sets (E,); what is important here is that we have K. S &,, for all / 2 1. One key difference from the analysis of [ is that we do not assume access to an exact oracle for generalized projection, which involves solving inf usc - ci for convex set C and matrix H E Sulad Instead, we use the PoE subroutine (Algorithm 3), which approximates this projection in Odd (Tg(T time (see Lemma C.I) using binary search when C E,, for 2 1. Note that this translates into a OCCspp + d')) per-round cost for our OCO algorithm Algorithm 2 We formalize this next and give the main regret guarantee for Algorithmm 2 (proof in Appendix E.2).
Theorem 4.1 (Main Regret). Let T 2 2 and e E KC be given and suppose that Assumption 2.2 and Assumption 2.1 hold with 0 < r S R and G O, respectively. Consider a call to Algorithh 2 with input (T, R, G. for n 10dGR. Then, for any (g:). the iterates (wi) of Algorithm 2 $satisfy
Σ (g. w:: - u) s Eg w. - u)² dllo(1 + Td R2 500d (ogg/((()))))()))) (10) E1
T
2 E1
27
for all u. K. Further, the per-round cost of the algorithm is at most O(C + (o))
Regret bound after tuning 1). By Assumption 2.1 and the fact that we E K. g (R),, we have A (10dGR)-1 in
that (gg wi- - u)) 2RG, for all t E [T]. Thus, setting 17 Theorem 4.1 gives a OdToo (kT) d² log((<T) regret bound for Algorithm 2 as desired.
Rates for stochastic optimization. By combining this regret bound with a standard online-to-bart conversion technique (c.g., [O0), we obtain convergence rate of Ö(/d/T++ dd/T) for stochastic convex optimization. However, due to the presence of the "second-order" term ΣT (g., w: u)² in (10) we can achieve an improved rate of Ö( /d/T + d²/T), which simplifies to ((P/T) when the gradient noise a is zero; see Theorem F.] for formal statement.
9

---

5 Discussion on Computational Efficiency
key consideration for our algorithm is its computational runtime, particularly in comparison to clas- sical projection-based methods and other projection- prrection-fre approaches. The per-iteration computational cost of our proposed algorithm is on the order of Ö(d + Csep), where w N 2.372 is the exponent of matrix multiplication, and this cost arises from solving d d linear system. The Csep term the cost of single call to the separation oracle.
While the dh term appears significant (larger than the de in 19 for instance), it is crucial to contextualize this cost. In many large-scale optimization settings, the separation cost Csep is the dominant computational bottleneck. A canonical example is optimization m linear constraints in I K = { IR" a, s b;, Vi [m]].
polytope defined by
In this common setup, call to the separation oracle reduces to membership testing, which requires computing m inner products. The separation cost is therefore Ceep = O(m)). The d' term in our complexity is dominated by this separation cost as soon as m d dl.37, In this regime, our per-iteration cost becomes Ö(md), which is cheaper than Euclidean projection as we discuss next.
5.1 Cost of Euclidean Projection in the Polytope Setting
We compare the projection cost of two standard methods in the canonical polytope setting.
Using an Interior-Point Method (IPM), the cost of single projection Ō(v (d mdf)) (see, e.g.. M here, /m is the number of IPM iterations, and d mat is the per-iteration cost, which stems from computing the Hessian of the logarithmic barrier (md") and inverting it (d*).
Another alternative for projection is to use a butting-plane method 22 The complexity of this approach is Ö(d- Czep d²) per projection. In the polytope setting, this becomes Ö(md² d²).
We see that the computational cost of both projection methods is significantly higher than method's per-iteration cost of Ö(md d²) when m 2 d.
While per-iteration cost important, a more holistic measure of efficiency is the overall runtime required to reach target e-average regret. We analyze this next.
5.2 Runtimes to Achieve an E-Average Regret
We compare our method's runtime for achieving an e-average regret against OGD with projections performed with either IPM or a cutting- cutting-plane method in the polytope setting.
Since OGD has a O ((VT) regret, the total runtime of OGD to achieve an g-average regret is bounded by O OCCroojee)) where Crroj is the cost of projection. Thus, instantiating the projection costs for the IPM and sutting-planes methods in (Secction 5.1 we get the runtimes:
Ō( (d + +md)) - (OGD+IPM), and Ömmd + . (OGD+Cuttine-laane
The comparable runtime for our proposed approach is Ö(md? dd+1))=a . Thus, our method's runtime is faster than OGD with the projection approaches we discussed, as long as m 2 d.
We note, however, that newer cutting-plan methods exist with an improved complexity, running [15.. Consequently, pairing OGD with these state-of-the-art methods would result in a runtime to achieve an e-average regret that comparable to our approach, potentially slightly better due to improved lower-order term (d instead of d=+1). However, these new methods are significantly more involved and often hide large constant factors in the Ō(-) notation, which may limit their practical applicability.
in Ö(md? dd) time per projection
Frank-Wolf (FW) Methods. Finally, we position our work relative to projection-free methods based on linear optimization, such Frank- Wolfe (FW). These methods are indeed very useful and practical, and their dimension-frn -fre guarantees are particularly appealing. We view these approaches as complementary to ours. Our algorithm can be more competitive in popular settings where, the absence of additional structure (like well-studied combinatorial structure), the linear optimization oracle required by FW becomes computationally expensive; some cases, comparable to a full projection such as in the canonical polytope discussed above.
10

---

Acknowledgments and Disclosure of Funding
We thank the reviewers for their constructive feedback on the presentation of our computational efficiency analysis.
References
[1] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[2] Sébastien Bubeck. Convex optimization: Algorithms and complexity, 2015.
[3] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[4] Ashok Cutkosky. Anytime online-to-batchh optimism and acceleration. In International Conference on Machine Learning, pages 1446-1454. PMLR, 2019.
[5] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-comvex conversion, 2023.
[6] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimiza- tion the bandit setting: gradient descent without a gradient. Proceedings of the sixteenth annual ACM-SIAM symposium Discrete algorithms, pages 385-394, 2005.
[7] Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly. 3(1-2):95-11) 1956.
[8] Dan Garber and Ben Kretzu. New projection-free algorithms for online convex optimization with adaptive regret guarantees. In Conference Learning Theory, pages 2326-2359, PMLR, 2022.
[9] Benjamin Grimmer. Radial duality part i: foundations. Mathematical Programming, 205(1):33- 68, 2024.
[10] Elad Hazan. Introduction online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
[11] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 699--1):169-192 2007.
[12] Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Coference International Conference Machine Learning, pages 1843-1850, 2012.
[13] Caan-Baptiste Hiriart-Urruty and Claude Lemaréchal. Fundanentas of convex analysis. Springer Science & Business Media, 2004.
[14] DB ludin and Arkadi S Nemirovskii. Evaluation of informational complexity of mathematical- programming programs. Matekon, 13(2):3-25, 1977.
[15] Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala. Efficient convex optimization with membership oracles, 2017.
[16] László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an (*(4) volume algorithm. Journal of Computer and System Sciences, 72(2):392-417, 2006. JCSS FOCS 2003 Special Issue.
[17] Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with membership oracles. In International Conference on Algorithmic Learning Theory, pages 1073. PMLR, 2023.
[18) Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, pages 5314-5390, PMLR, 2022.

---

[19] Zakaria Mhammedi. Online convex optimization with a separation oracle. arXiv preprint arXiv:2410.0247,, 2024.
[20] Marco Molinaro. Curvature of feasible sets offline and online optimization. arXiv preprint arXiv:2002.03213, 2020.
[21] Phan Phien. Some quantitative results on lipschitz inverse and implicit functions theorems. arXiv preprint arXiv: 1204,496, 2012.
[22] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning. 4(2):107-194, 2011.
[23] Naum Z Shor. Cut-off method with space extension in convex programming problems. Cyber- netics, 13(1):94-96, 1977.
[24] Pravin M Vaidya. A new algorithm for minimizing convex functions over convex sets. Mathe- matical programming, 73(3):211-31,, 1996.
[25] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In International Conference Machine Learning, pages 928 936, 2003.
12

---

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: All the claims made the abstract are formally stated Section 4 and proven in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: After the contribution paragraph in the introduction, we discuss the limitations our work; we not provide regret lower bounds or experimental validation for our algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best 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.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The paper contains the full set of assumptions and formal result statements. The proofs will be included the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is purely theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/ bublic/guides/CodeSuin www.ooooosoooosiiioo.oooooo.o for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.cc/publl. http:l/c/ggude//odeeeeeeeeee
wwrooddeSbmssssionooo ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA].
Justification: The paper does not include experiments.
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: The paper does not include experiments.
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, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr 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 reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
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 of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///bburrrssscccoooo//cttte
Answer: [Yes]
Justification: Reviewed code of 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 circumstances 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:
No societal impact; purely theoretical paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
16

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
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: No risks. Purely theoretical paper.
Guidelines:
The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No use of existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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 use in the package should be provided. For popular datasets, |ppper swi thcode. com/ cona/datsets 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 it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No release of new assests.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing involvement.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing or research on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy https////.ecrroo.cccoooooeeeesss for what should or should not be described.
19

---

Contents of Appendix
Computing the Gauge Distance (Proofs of Lemma 2.1)
21
Ellipsoid Updates
23
Generalized Projections onto Ellipsoids
25
D ONS Analysis (Proof of Lemma 4.3)
30
OCO Analysis
33
Algorithm Invariants (Proofs Lemma 4. and Lemma 4.2)
33
OCO Regret (Proofs of Theorem- 4.1)
37
Rates for Stochastic Convex Optimization
38
Helper Lemmas
40
20

---

a+3 2 3 (see Algorithm A Computing the Gauge Distance (Proofs of Lemma 2.1
For the proof of Lemma 2.1| need the next intermediate result showing that the output (S, of Algorithm is such that (u c) s for all u C and input vector
Lemma A.1. Let 8 10,1), w. TR,, C Rddt convex, and H RRdxd PSD be given, and consider call to Algorithm with input (c, H, ww,) 8). Then, the output (S, ofAorrithh 1 satisfies
VuEC, (u-c)' &s1 s..
(11)
Proof. We first establish ( [TD] If w E C, then the "if" condition on Line 2 evaluates to "truc", and
the algorithm returns the pair s) (0,0), 0), which clearly satisfies (11) Now, if e C, then the "if" condition on Line 6 evaluates to "true", and so the algorithm returns the pair (S,s)
(0, (0.3dv/vo) Hv). where is the unit-norm vector corresponding to the hyperplane separating from C. Thus, by definition a separating hyperplane, we have that for all É C, u S c' v, which implies (11 after using that s 3dv/Vv' He.
Now, suppose that w & C and c C. In this case, Algorithm returns (S, s). where s 3 3-wwecTTv
and is the vector returned by the last call Sepe (oPe(p(())) - c) + +c) before the algorithm returns; here, (9 and are as in Algorithm 1 We first verify that 3 (w - c) > so that s is well defined. Since is the vector returned by the last call to Sepc(u(w c) + c), have
VueC, C,
(u-c) u(w c) v.
(12)
Instantiating this with and using that μ a-8 3, get that
2
0 3(w c) v..
and so is well-defined in Rd. Dividing both sides of (12) by B (w c) and using that
(ww-c) we get
VuEC, (u-c)' s5 u(w s= (w c)'u
3 (w c)T S 1,
where the last inequality follows by the fact that =
Proof of Lemma 2.1 We consider cases.
Case where C. If c & C, then the "if" condition on Line 6jevaluates "true", and the algorithm returns the pair (S, s) (0, 3dv/Vo' Hv), where is the vector returned by the call to Sepc Line 5 In this case, clearly have that 1/2 >|| > 2d.
For the rest of this proof, we assume that c C.
Case where c, w é C. If w é C, then the "if" condition on Line 2 of Algorithm I evaluates to "true", and the algorithm returns the pair (S, (0, 0). Since w C, we have (C-c(w c) inf - c)} and so, have for all Rd.
Sc-o c) max(0, cc-c(u c) 1) 0 max(0, (w- - c).
This implies the desired claim.
Case where c C and w é C: approximate gauge value. For the rest of this proof, we assume that CeC and C, and let a, 8, μ., v, S, and be as in Algorithhm 1 when the algorithm returns.
If the condition on Line 12 of of Algorithm satisfied, then by definition of Algorithm have that
we
|| 2d.
Moving forward, we consider the alternative case where 1/2 s 2d, which, by contrapositive, implies that the condition on Line 12 is never satisfied during the call to Algorithm ] Thus, by design, when Algorithm returns, we have
B(w- c) c and 18 - al 5 &fft
21

---

Since (0-c(u) inf 0 w X c)),)), for all u é R
we have that
8 $ TC-c -) c)s 1
1
(13)
a
with the convention that 1/0 +00. By definition of in Algorithm
we also have that
8 8 w - c),
< H s|| || (12(ww (w-C))) -c)l, (Hölder's s inequality)
s 2d,
(14)
where the last inequality follows by the fact that || s 2d and the assumption that w e the lemma statement. Using (14) | - al s sd and the fact that e (0, 1) implies that > 0. Further,
(14) with |3 al 542 also imply that
<
5
8d
(see below)
(15)
3
4.2d2'
$ + 6, (by (14)
(16)
where (15) follows by the fact that since which clearly satisfies x s 2 3 s 2d and 5 (0, 1). Combining (16) with (13) and using that
1 s 1 2x, for all x S 1
2 we instantiate the latter with x
83d2
a- (see Algorithm 1b, we get
cC-C(w - c) SS+15 S c) 6
This together with the facts that Sc-r c) = maxx 0, 7C c - c) 1) and pc-cww--ae c) 2 (since w C and e C) implies that Sc-c(w - c)) s S Sc (--((w) w c) + 6, as desired.
Case where e C and w C: approximate gauge subgradient. Still in the same case as the previous paragraph, we now show that the second output of Algoriih iis an approximate subgradient of the gauge distance function at w.
By Lemma A.
we have
Vu Eu,CC (u-c) 8 v(w c) 1.
This implies that e (C c) c) (by definition of the polar set) and by Lemma G.5 we have
Yu E Rd.
s s'us s
sup mc(Ce)
x t'u (c)
(17)
On the other hand, combining (16) with (13)
we get
cc- (w c) - 5
8 (w c),
(18)
3
where the equality uses the expression of Combining (17) and (18) implies that
Vu IRd S" (u - w + c) TC- c) 85 (c-)(u),
which, in turn, implies (through the change of variable - u-
Vu e d (u- w) ( ( - c) á rc-c (u c).
Thus, subtracting from both sides and using that Sc-c (w c) cC- (w c) (since w C and e C), we get that
Vu 1
8 s"(u- w) + Sc-e - c) - d rC-c (u c) -
s max(0, 7c- 1C- e) - -1);
= Sc-c
22

---

Thus, we have shown that when |/ s 2d, the outputs (S,s) of Algorithm are such that S approximates the Gauge distance Sc-e(w- (w c) and is an approximate subgradient of Sc-e w as desired
Number of oracle calls. The number of oracle calls is bounded by the number of iterations of the "while" loop on Line 10 plus the two calls to Sepe before the while loop. Since Algorithm I implements bisection, the number of iterations in the while loop is at most log2( 8 total number of calls to the oracle most log, (8d (8d28-1) 2.
8d"
). Thus, the
B Ellipsoid Updates
In this section, we provide the intuition behind the ellipsoid update rule used in Algorithm 2 As discussed in Seccion 4.1, when the condition for updating the current ellipsoid & = {(,,, H4,) 2 K. is satisfied at round of Algorithm 2 (i.e.. when Line 4s satisfied), we have:
(19) We show that under this condition, an updated ellipsoid E,+1 can be constructed such that it still contains K. and its volume is reduced relative &,.
( ca) = (u B(1) u² 1/2d).
To achieve this, we consider the more abstract problem identifying the minimum volume ellipsoid that encloses the set (u E BB1) u e) for some unit-norm vector v; this is the same in but with (v,, 1/(2)) replaced by (v,E). The construction of this ellipsoid follows a similar approach to that found in the classical ellipsoid method (see. e.g., (2). A sketch of this construction, which mirrors the steps outlined in (2), is provided below.
Ellipsoid parameterization. Fix t > 0 and E (0,1), and define H ave b (La ve") ) for b O. We will start by solving the intermediate problem of finding parameters b e IR such that the ellipsoid ar = fx e [Rd| (æ + tv) H ( + tv) 1] contains the set given by
{u B() o s E).
We will derive expressions for and b as function of then tune & so that the corresponding ellipsoid has the smallest volume.
Choosing a and b. Observe that to satisfy the requirement that {u B(1) v' s &t,a, it suffices to choose parameters a, b e R such that the boundary 0E,,a,6 b of the ellipsoid &r,a,b contains -v (which in OB(1)) and the intersection set B(1) {u e Rd vJu = =]. This requirement translates to the following constraints:
and Solving 20) for a, b, we get
-U E dr,
V U, EU V1-V1--- 1-222x DE,
(20)
(t + =)² (1- 1)2
(1 t) and b 1 1-
(21)
Tuning for the smollest-volume ellipsoid. Now that we have derived expressions for and b as function of such that (u BB1) v u E) S Er,,,,, will tune to obtain the smallest-volume ellipsoid E,,,, Note that the volume of the ellipsoid E,, satisfies
vol(Er, vol(B(1)) Va
1
d-1
(22)
Vt
For s 1. and (a,b) as in (21) the parameter ł that minimizes the right-hand side of (22) is given by 2d
t= 2(d + 1)*
(23)
This leads H.. H
4d-4 1d2-1
[I (2d+1)(d-1) vov)
2d
and by Cherman-Morissom,
2d
2d
Ha,
la
vo
4rp
2d22 + d -
23

---

Further, by (22) it can be shown that with the choices of (a,b) and t as in (21) and (23) respectively, we have
vo1(Er,a,b) vol (B)(
< exp
(24)
8d
We formalize this result in Lemma B. Before presenting this lemma, we give a few comments.
The informal sketch presented above shows that when H, - c+) s {u e TB(1) 2 n'v, s 1/2d) (a condition satisfied whenever the ellipsoid update |lllorrithm is triggered), then
(K- c,) E (
2(d-1) :eeT))
where HEL1
4d"-1 4d'-4 (la
2d (
Further, it can be verified that c. + 11,12 E(c+r, 1) with Ct+1 and H as defined on Line 7 and Line Algorittt 2 Thus, K. Ec-1 & H++1) discussed in Section 4.1
Et,1
We also note that the choice necessary to show the volume decrease in (24) This puts limit the maximum value can take and contributes to the additive Ö(d) term in the final regret bound of Algorithm 2
scaling inversely with in the construction just described was
We now formalize the guarantee of our construction.
Lemma B.1. Let é &d be such that |ba| 1, and define
4d8-1 (Ia Ad=-1
2d vo and
2d
1 = uE Rd (u+ w) H (u+ 2(d-1) 0) $1
Then, we have
{u B(1) v-u
SE SE.
(25)
Furthermore, it holds that vol(E) s E vol(
Let H be as in the lemma statement. By Sherman-Morissan we have Proof. We first prove (55)
4d 4
2d
H
Ta+
() va
(26)
4d
(2d
Thus, for all u Rd, we have
4d
u
H-1
ut
4d
4
2(d+1)
2(d 1)
2d
1
=
u
La+
(2d 1) - vo
u
2(d+1 v
2(d
2d
d
1+
(u u))= + 4(d + 1)2
(2d + 1)(d 11)
2(d+ () ()
2d
d+1 u To
u (d+ 1)d 1)
(27)
We need to prove that the right-hand side is at most for all u e fx e B(1) vJ s 2d
Note that
for any such we have u v [-1, J. Therefore, we have that for all u é {x (BI) v x < 1
2d(u=v)
d 4dd ((d+1)2 1)2 ((++))((++ () d+1 (d+
1
uT
2du V
1+
(2d + ()
2d.a2
d
2d.
< sup 1+
(2d + ()
2(d+ ()2 (d 4(d+1)2
d+1 (d+ (d+1)(2d+ 1)
ze -1.2d
Now, note that the function
2d
d
2d d (d 1)dd++ 1)
x² (2d+ ()
4(d+ 1)2
2(d+ ()d ()
24

---

is convex, and so its maximum in the interval [-1, 1 must be attained at the endpoints -1 and Therefore, have that for all {x e BB vJx 2d):
2d
2d
2d(wFv) v)2
1
u'v
2du'
(2d+ + 1) 4(d+1)²
2(d+ 1) 1)
d+1 (2d 1) 1)
2dx²
d
x
2dæ
< max
+
4(d+ 1)2 2(d+ 1)d--11 +
(2d ()
d+1 (d+ ()d 1)
xe (1122
4d -1
4d -4
Combining this with (27) shows that (u+
2 xd.11 u) 1-1 (u+ 2(111 v) S for all e {or e BB())
J. 28 and so
{u B(1) v. u 1 3.
Volume decrease. It remains to prove that vol vEl(E) - vol()())) The volume of the ellipsoid given by
T 4/2
vol(E)
(28)
T(d/2 1)
Vdet(II-1))
where I' is the Gamma function. We now compute the determinant of H (26) we can write
- avv + b(I - vv=),,
where a 4(1+d)² (1+d)a and 1d--4 (d-1)(2d+1), Thus, for any x v, we have H 2 = bz. addition, 4d_-1
2d
we have H av because || 1. Therefore, a and are the only eigenvalues of H with having multiplicity d - 1, and det((--) (H-1) d-1b. Therefore, by (28)
d-1 1-d 2
vE) T(d/2+11 1) Va
4/2
1
d/2
1d
4/2
e n2 (29)
((d/2+1)
(d+1)
I(d/2+1)
(2d+1)
where the last incquality follows from the fact that
2
d
1d
SEn
S
vd 1,
(d-1)
(2dt+ 1)
and we are assuming that d 2 2 in this paper (see Section 2.1 vol(B(1)) / + 1) completes the proof.
Combining (29) with the fact that
C Generalized Projections onto Ellipsoids
In this section, we consider the generalized projection problem
U. E arg min( u - z) =) (u 10--2) 2),
(30)
uc8
for z Rd and Q e 50
gdxd in the special case where & is ellipsoid; that is:
E {I E R (x (x- s1)
for some H e gdxd and c Rdd By Lagrangian duality, the problem in (30) is equivalent to the max-min problem:
sup inf (z - u) (= - u) x c) (w--))
(31)
Asd ueld
25

---

Algorithm 3 PoE: Projection onto ellipsoid via binary search.
require: 2, ee RR" Q, H E dddd and parameters X_, A,, O. If
almost in the ellipsoid {cc, H), then return slightly 'scalled down' version of it (z c)/(1 + */
I: if (= H
(2-c) 1 then
2: return (= ()) +c.
/* Approximate u' arg men (2 (== (== u) via binary search */
3: Set + A. 3 and μ (a+ 3)
4: Set " = (HQ- (HQ uc).
5: Set D = (u,, -c) c)..
6: while D [1
7:
if' d then
8:
Set + and μ - (a + 82/2.
9:
else
10:
Set a μ and μ (a+ 8)/2.
11:
Set n (HQ" (HQ pc). Set D= = (u) - c) H (u) -c)
12:
13:
return /
For fixed À 0, the inner minimization problem has a closed-form solution:
u = SHQ A1) (HQ' 2 Ac).
By leveraging this structure, we show that the problem in (31) can be solved efficiently via binary search over the dual variable X. In this paper, we do this using Algorithm 3 This algorithm takes inputs c, Q. and H, and outputs approximate solution to the problem in (30) We now state the guarantee of the algorithm.
Lemma C.1 (Projection onto ellipsoid). Let R > 0, 6 > 0 be given. Let 2, BRR), and H (z c) 1 8 and m (H) S R². Further, define ((v) = (uER* Rd (u- c) H (u - 2 v.. u R. and consider a call Algorrih with amin (H) and X4 2
Q gdxd be such that (z -
input (2,C.Q.H,,,,,... 2). where s 8 Algorithm 3 returns 2i Idd such that:
40 (H) omin (HI) (Q) Then,
3u [0,6] u² arg min(u u Q (u- (e)
LAg The number of iterations in the while loop on Line 6 of Algorithu is at most O(log, (L22)) )), where
Tmax (H) maax (Q)2 R and B
Gwns (H)
aaiin (Q) A
L 4(B R)- mmin HH33. mmin (Q)
(H)
(Q)
Finally, each iteration of the while loop in Algorithu can be performed in O(d)) time, where w is the matrix multiplication exponent.
Remark C.1 (Computational cost of PoE). By Lemma C.I the number of iterations in the while- loop of Algorithm
bounded by log( Ld+)), We later show that for our application, we have poly f T). Note also that the cost per iteration of Algorithm 3 is bounded by the cost of solving linear system (which costs Odd)), and total cost of running Algorithm i bounded by Odd log LA.). It is possible to implement Algorithm 3 so that the total cost bounded by Odd log Ldd. d)) instead, where now the dominant term ((d ) independent of any logarithmic factor This can be done as follows:
LA=
8x
Bd
Lh+ EEven though Odd log zx_
) is technically better than O log LA+ + dd) asymptotically (since < 3). 3x_
the O(-) notation in the former typically hides large constants making the new implementation described in the remark more favorable in practice.
26

---

Compute Cholesky decompositions of Q and H (costs O(d))) that is, compute lower- triangular matrices Lo and Lи such that Q = و and H LHL
Compute SVD decomposition H 1.Q T. Ln (costs O(d)); that compute (A, U)
such that M UAU", UU I, and A
Compute inverses LØ and Q-1 (costs (dd))
With this, we have for any 1s 0:
(HQ + +HII z pc)= L Udag
U Li (HQ' pc).
Pd + we can compute (HQ-1- μTy- - + uc) (dd)
P1 +
Thus, given (IHH Lqg, T. N.A.:TTH,QQ,,AAUU (matrix-vector multiplication for any μ O. Thus, the total cost poE with this implementation is bounded by Odd log 5x_ + +d because the operations described in the bullet points (which cost O(d)) need to be performed only once.
Li=
The computational cost of Euclidean projection onto an arbitrary set can be much worse than that of PoE in Remark C.I For example, using state-of-ther -hertt-rrt ellipsoid methods to project point onto a set K. specified by a separation oracle can incur cost of up to O(d (IC) dd),, where Csep denotes the cost of single separation oracle call [15] Moreover, the Ō(-) notation often conceals large constants, which can render these methods impractical. Alternatively, a Fuclidean projection can be formulated as quadratic program and solved using interior point method. This approach requires a self-concordant barrier for the set K. whose gradients and Hessians are inexpensive to compute. However, even under favorable conditions, the associated cost typically remains higher than the costs detailed in Remark C.I
Proof of Lemma C.1
Let 2, c (BR)) and Q, H E Sdxd be given. For À 2 1, let define (u- (u
U E aargmini (u- === Q ()=)) ((u c) (u c) 1).
welkd
Setting the gradient of the objective to zero and solving for u, we obtain
ux (Q- (Q- 1H- c).
(32)
We now study how the "constraint" objective g(A) = (u) c) H H (w; c) varies as function of A. Taking the derivative of gives
du
)(A)= -c) H
(33)
yA
On the other hand, by the expression of u; in (32) we have
( c- (Q
du
(Q-
+Q XF -H (34)
d)
HK - zj
=
= =QQ-1+ (c- rA).
Plugging this into (33) we get that
=(())=221
H AHI ( -c) s0,
where the last inequality follows by the fact that the matrix H H-'(Q-1 -H is positive definite. Therefore, g()) is non-increasing in X, and
find X using binary search. To show that this can be done efficiently, it remains to identify reasonably small interval for the values of X*
Upper bound on X" Note that " = =Q-++ + x
(/00///>1)11(("///---111113399"1 T)-1)c
-==((-((''))--)")(==-))))
(35)
27

---

For X ma (
we have by the stability of the inverse operator Lemma G.1
Omin Omin(H) (H) minn min (Q)
4
muin (H) 1/2
(H)1/2
IIHQ / 1)= olop
|IQ
llop
(36)
31
3R
where we used that min H/ & R, by assumption. Using (35) and (36)
we get
((>) = (ui ( c),
c) (1 (HQ 1) H (1-(0())A+)))))) 1)= (z
[HQ />+ ((H | 1 cl?
$ 9 ||,,,
< 14/9x1,
where the last inequality uses that z, C B(R). Thus, for all 2 ma HH)R Since g() is non-increasing, and we know that g(X*) ) 1, we must have that
mmin oo (Q) we have g(A) $
X m0 (HR
1QH 11p lop
miin (H) 122 O (Q)
2
Lower bound on X". For the other direction, we have X /HQ- (XQ A1)
And so, by Lemma G.1 long À s 1Q0 1o have
I(QQ + XI) QQ lop $ 2 11pp-
(37)
Moving forward, we let E = AQH X(HQ-1 + AQ) and assume that X s X (recall that X |QH-~1 (2).2). With this and (35) we have that
g(A) = (ui c) / (wx
= (= (1-xQU") E -QU1- (2-
(38)
Now, let E" == -==== E, and note that by the triangle inequality and (37) we have
11'llop s >|QQ1111 lop + 1011QQ1111 2A|QH
Topp.
(39)
where the last inequality follows from the fact that À 11p/22 On the other hand, by (38)
(= -
= (= <z - (x= (x-))
(z
Thus, by (39) and the fact that C B(R), we have that
16R A Q lop
16R X 12
lo(A) (=- e) c)
min ())
miin (H)
24 A
x
IQH lops
(since À
mmin (H)
24R² X. max (Q)
S
Omin H
Therefore, if x S 8. 21R2 mmx)
Cmin(H)
we get that
lg(A) (z c))
(z= c) sd.
Thus, we must have
o min (11)
40 max (1) R
S2
24R2 o mmax ()
mmin ( (H) mmiu Q)
and so by the assumptions on X_ and X it holds that
0< A 5
Now that we have established that X is in between X_ and A we can use binary search to find X such that g(X*) s The number of iterations of the binary search will depend on the ratio X, / /X_,
the precision d, and the Lipschitz constant of g.
28

---

Lipschitz constant of Since u = (HQ ( xc) and cE B(R), we have that
| s + (10 1t)
(RIIHQ X
Omin (HQ-1 + +X)
$ B = R. max (1Q-1)+
min (HQ-1)
On the other hand, we have that
=(())=((u} = - -c)² H --- dui
dd
and from (34)
du (Q"
yA
"I) cz-c), ~T
Therefore, by the triangle inequality and the fact that 2, c IB R), we get
1o(( S 4(B+ + R)
|1Q R,
Min (H) min +1Q-++++00
s L = 4(B R)
max m 11QQ1)
miin (H) min (HQ-1)²² R.
Number of iterations binary search.
Given that
0< A_ - & X+,
g(A+) S 9((') 1, and
9 is non-increasing in À and L-Lipschitz
Algorithm finds a fu [A_, A+] such that
1 - 8 g(m)= (ui, ( (u,, -c)
(40)
after at most N O(1) logz 2 iterations of binary search on Line 6 Note that as as Algorithm finds such μr, returns u u (see Line and Line 13 of Algorithm 3
Optimality of u' Let μ = 1- (u- e)T (w c), where u the vector returned by the call to Algorithm 3] and note that we have just shown that [0, 6] (see (40).. Now, consider the problem in the lemma statement:
min (u (u= meE(v)
This problem can equivalently be written as:
min wf(w)sl-v fo(u1;
(41)
where fo(u)= = (u (u-z) tu x) and f(u) (u - c). By the definition of u", it can be verified that
voo + μ 4 00
Furthermore, we have /(u") s(n) = 1 - v (by (4 and the definition of v/). Therefore, the primal-dual pair (u", ,4) satisfies the KKT conditions for the convex problem in (41) and so we have
u E arg orgmin(u - = (u 2),
ue8(v)
as desired. This completes the proof of Lemma C.T
of
29

---

D ONS Analysis (Proof of Lemma 4.3
Proof. Let (H₃, Ct2 R2, We De, 9t, 17) be in Algorithm 2, First, note that for any t [T] such that / / H, > 2d, we have gt Fix [T] such that sj His S 2d. By Lemma 2.1 and Assumption 2.2 we have
C+41 E K B(R).
For the rest of this proof, we fix u E K. By definition of 1 in Algorithm we have
x u E
Multiplying both sides by
1/2 2++1- we get
E (2 u) 1 ur u) _x+1 Dt.
Taking the norm of both sides and squaring leads to
|| u/ E... = |1 li... + 9 1
-2(ue - ut g.).
(42)
Using that ||e, 10.3 =|2 1.. n u. ge)² (since 21+1 2i + ng.g! and rearranging
(42)
gives
(uu: θi)
71 (u: n.) U1 u u12
"
2
1
| - 2 1u +
(43)
We will apply Lemma C.1 (guarantee of PoE) to bound the term Ze+1 u a left-hand side of
(43)
Then, summing the resulting inequality over / 1, 1,...,, T will give us the desired result.
calls PoE with input (z, Q, H, A_, 24, 6) (Zt-1, (Z,-1,C4+,, BR H,+1, Amiu, Amax: E). where 18822 Amin 24x
Invoking the guarantee of PoE. Note that at iteration t, Algorithm 2
Amax 10d"x, and 3 n/2 (G is as in Assumption 2.10. To invoke Lemma C.I we need check that the conditions on A_ and X, are saushed. By Lemmaa 4.1 we have that
mmin (H++1) ) 2 n² and mmax (Hz=1) S K 16 R²
(44)
On the other hand, since Et+1 = 3I + 17 Et- T-I. and [@ell s G(1 + 4kd) (by Lemma 4.2
we have
min 2 and mmax (E++1) $ $ T) max re[t+1]
|g < Ty (1 4nd))
(45)
Therefore, since (Q, H) (BR H++1, we have min (H)²
minu 12+1)2
8 24R o max (Q)
24R o Laxloaax (3R2E,1) L-1
1 Tmin (Er+1)
E
(by (44)
24,R
r13
2 e. 24
(by
(45)
Amin
24k
Thus, the condition A_ in Lemma C.1 is satisfied. Now, show that the condition on X_ is satisfied. We have
max H))
40 max (H41)-R R
mina 1/2 Jmin (Q)
σ mui (11+2 1/2 Jmin (31221111
4n 16 R² o max (Eer))
(by (44)
Rr
< 27 1 Axd)
(by (45)
4x (.,1(1+T( + 4nd)²),
(since G
< 2 Amax X4.
Thus, the condition on X, is also satisfied. Therefore, we can apply Lemma C.I in this proof. In particular, Lemma C.T implies that
U E Es+l,
(46)
which we will use in the sequel.
30

---

Computational cost. cost of the PoE call on Line 15 of Algorithm 2 Thus, by Lemma C.I. this cost is at most Odd
The cost of computing the new iterate Uc+1 given is dominated by the
log( Amaaz L1 Amnin
)), where
Omax (H) max (Q)
Ouaa (H)
(Q) Amax
I == + R)
R;
B = R.
min H) 0 min (Q)
Ominl
maax (Q)
and (Q, H 138 He.1,e). Using (44) and (45) so the cost of computing Mc+1 given g: is at most (dd d Tog (TR/R))
we get that Amaux! L Amin
Spoly(T,R/1) and
Bounding the instantaneous ONS regret. the inner ONS algorithm within Algorithm 2
We now bound the instantaneous regret (u, u. u. of We consider cases based on the value of
Case where || C++1 H & (2+11 - c++1) THel (Zt+1 - Ct-1) s e, then PoE returns U++1 (Zt+1 Ct+1 ( +8) Ct-1 e Et-1. In this case, by the triangle inequality, have
1z++1 - -u// 21/1 = [111 + +e) (u4+1 - (++1) C++1 2 Eie
2 |4--1 u Eun -E |4++1 | C++1 Ees
2 |t-11 1211 E max (2x+1) 1/2 |luc+1 C++1li
Ut-1 u Ee+1
mmnx Ete1 1 1122 maxx (H(+)) 1/2 )
|ui.1 Ceel High
U6-1 u/ Em. -max (E++1 ) max (H++1) 1//, (by (46)..
Ue-1 ul Ee.s -K R (V3+ Vn 4nd)
(47)
where the last inequality follows by (44) and (45) Now, by
(46) we have u E141. On the other
hand, by Lemma 4.1 I. Ex+1 and El+1. Therefore,
U++1 Ue 1z2 S 2, and so
[1411 u/I Dun S maxx (E++1) 1/2 0 max H 1/2) -| n12)
< 2x 8 R. (v B+ (T + 4nd)),
(48)
where the last inequality follows by (45) and (44) Squaring (47) and using (48) get
[case: (Z++1 C++1) H | [z++1 C++1 s1+
(49)
|241 uul2..., |4411 ul|
E
Sex 16 R2 1/T² And)2)
Case where || C++1 1 H.1 > + Now, suppose that (z+11 - c41) T (2t-1 -(+1) >1+
In this case, by Lemma C.I there exists [0,e] such that
u arg min (x zz+1) Ex-1 - (x zc+1), wEE
(50)
where Eet1 in fxc IRd (a: - -++1) H (a (a-aa ( $ 1 11-v/ v) S Ett1- Fix such a v. By Lemma 2.1 have that K. Et+1, and Et.1. This in turn implies that
1 1 C.+1) + Cu-1 (++(
u, 1 2v
(u
where we used that 1. 1 for 1/2]. Thus, by (50) and Lemma G.2 we have
| ur $ Zz-1 Wr
31

---

On the other hand, by the expression of uy and the triangle inequality, we have that
F++1 - uu, 22,1100 E111 = *++1 1 2v
(u
c(+1) + Ct+1
Ee41
2v
$ #tel u Si
u Ct+ 11
+ 2v
$ - u Drel + 2E max (E(-1) 1/2 ||ue c+all, [0,=])
< E u E + 2E . max (Ex-1) 1/2 T (H+1) 1/2 |u cuallethh
< || E+ u Emm 22 . max (Ex-1) 1/2 Tmax (H())) )21² (since u El+1)
$ || u u +ee R
23 + VnIGG1+ VnIG((++nd))
(51)
where the last inequality follows by (45) and (44) Similarly, we have that
1
| urllEm1
Mx+1
(u C++1) C++1
1 2v
E11l
2y || Cct1ll
> U1+11 - -u|1x
1 2v
2 U1+11 u||xxm -2Ek R. (V23+ V1TTG(1 (TTG(1+4dd))
(52)
Thus, combining (51) and (52)
we get
U u D...
22k R.
1/23+////i (123+/ITG(1+4xx)) S 3 21/.
(53)
Taking the square in (53) and using (48) get
[case: (z1+1 C++1) ( (zt+1 1 c+-1) > [+
(54)
U++11
u1 2
24ch 16 R2 (28 (1+++T+k)+++)))) (xd))) s |z411 - u uu E...
Plugging
49
and (54)
into (43) yields
17
(u u. gt)
(uu u. u.
2
1 1 24 R² (23
u/l | ul.....
(55)
2
So far, we have considered rounds e [T] satisfying v $ H.s: s 2d. As remarked at the beginning of this proof, when V H,s, 2d, we have g. 0, and so (55) remains true since E,+1 E, and U++1 = Ut-
Bounding the ONS regret. We now bound the regret of ONS (not just the instantancous regret).
Summing
(55) over i [T] and telescoping the terms (I]u: u. (1,,, ) we get
[u u.g:)= !7 /
(u: u. (.))
T
ull
Σ
1. 24Tex R² (23 TT + 4nd))),
2
|-1
T
28RR2
Σ
g.
2
+ 24TEx 16 R². (2.3 GT + 4kd))))
(56)
On the other hand, by Lemma 11] and Lemma 4.2 we have that
dlog(n (1 4md) 2//3 1)
gg 1 S
7
32

---

Plugging this into (56) and using that 3 = n22 and E T3 we get
[1 u. g.
?
2 (uu u. 01)²
22RR² dlog(n 2xd))T/3+++
+ 24TEx R2. (23+ 4nd))),
2nj
s 2 n² dlog(1 + 9x 9x22
+ 240 R² 24 G2
2nj
This completes the proof.
E
OCO Analysis
E.1
Algorithm Invariants (Proofs of Lemma 4.1 and Lemma 4.2)
Proof Lemma 4.1, We will show the claim via induction over f I...., T. The base case holds trivially because H1 = R and K. s IB( E where the set inclusion follows by Assumption 2.2 Now, suppose that the claim holds for t [T - 1] and we show that it holds for + 1. Note that
(Ce+1. H(+1) (c,, H₂) only if His, > 2d. Suppose that V s H,s, 2d. By Lemma A.1 we have that
Vue KC, (u- Ci, 81) 1
Therefore, have
Vu K, (u-
c.).
H1!
1
V 8 H.8t
V H.s,
2d
11,²
This implies that for the unit-norm vector v1 H.o.
have that
H c.) _ {u Rd 1. u s )
(57)
And, by the induction hypothesis, we also have that H; 1/2 (K- - ci) s B(1.. Combining this with (57) implies that
1 cx) s (u BB1) viu
(58)
Now, by Lemma B.I we have that
{u E B(1) v. 2 E Rd
u 2(d 1) U1
H
2(d 1) Ui
s s1
(59)
where Hit1 = 102-1
4d-11 (Ia
20 v.us) Combining (59) with (58)
implies that
H- - ca) _
u u a 2(d +
1
11 Mー1 u +
2(d+ 1) 11 $ [s1
1
This means that
VueK, K. 12 H- 12 112
H.l
H H-
11
2(d+1) ve 12
2(d 1) Ut
and by using the definitions of He.1, Her1, Vr. and Ctol. we have
1
1112 v,
Hill C. 2(d+ 1)
H 112 v2)
Ct 2(d 1)
= (u - c+1) ) Hid (u C(+1).
(60)
Thus, (60) implies that K Em-1
33

---

Showing tem 2.
This item follows from
Lemma 2.1
Showing Item 3
If ( 8, His, s 2d, then (Ct-1, H4+1) = (c,, H,) Item 3 follows immediately
by the induction hypothesis. Now, assume that vs, H1,, 2d. In this case, have H+t1
4df-1 H1 12 I- 2d- o 0,00 1d-1
2d 11"² " H!!? Thus,
H H1 E {u IRd (u- H1, 11, c.1) Hir 11, cc+1) $1}
where
-1
2d
H 122 s H 1/2
1u. 4d
2dl2 d
8. H
and so by Lemma B.I we have that
vol
(22 E(+1)
Se s2,
(61)
vol(
On the other hand, we have
4/2
vo1(E(+1)
vol(E:.1)
I(d/2+1) +1 vol(E,)
where the last equality follows by the fact that vol(E.)
4/2 [(d//+1)
and det H 1/2)|
(H;")
/dde(HH)) because He is positive definite. Now, using that vol(B(1)) = = (d/22 1), we get that
vol vH,(H, (2+1) vol(E(+1)
vol(B(1)) vol(E,)
Combining this (61) wc get
vo1(E vol(E:)
S Se" 84
as desired. This proves Item
Showing Item 4 By Item and Assumption 2.2 we have that B(co,r) E K. E41. Therefore, ( 2 pd On the other hand, by Item we have vol(Er+1) $ e Rd, and so N, dd log( (R/r); otherwise, we would contradict vol (E++1) rd.
Nr
Showing Item 5, We now prove Item in the lemma statement. By Assumption 2.2 there exists Co é (RR) such that (c), K., and by Item we have (Bco,r) Ex-1. Thus, by Lemma G.3 we have
BB (CC.1, Er+1.
Let Zt+1 be the unit-norm eignevector corresponding the largest eigenvalue of Hz)- Since rz41 + Ce-1 e ((C++1,)) r) S Ext1, we have that
1 2 2 2T:1 Hi R
, | | llops
Omin (H++))
Rearranging implies that auin (H,1)) ) 2 x2 It remains to bound Fmax (max) By Lemma G.4 we have that
Tmax (Her)) [
Tmax (H.).
de
34

---

Thus, by the induction hypothesis, we have
2 m
No
max (H++1)
1+
R²²
d2
and so by ltem 4 have
8at log( R//))
2
1
R²
d2
e (6log(A(r) R²,
(see below)
(62)
16 n²,
where 622) follows from (1 + 2/)) & ex for all n 2 1 and [2| n.
Proof of Lemma 4.2
Fix L [T], and let St, 8t, the It. and wo be as in Algorithm 2
When the
condition in Line 4 of Algorithm is satisfied (i.e., when Vs, H4 > 2d), we simply have 9t and w; = c A, In which case all the items hold. For the rest of the proof, we assume that
V H,8 2d.
(63)
By Lemma 2.1 have that c₁ K.. Using this, the triangle inequality, Assumption 2.2 inequality, we have
and Hölder's
7 $ Iggell Kg:, we ct)l ||sr||,
G 2GR H 1/2 Ilap sss HiS,,
Vs H,
G 2GR
minn H₂) 1/2
$ SG( + 4kd),
where the last inequality follows from (63) and the fact that Gmin (Hi) 2 72 by Lemma 4.1 This shows Item 1
Proving Item 2 By definition of wi, have w,
Ws c. (recall that are in the case where 1+S.
V H1S S 2d). Therefore, by the homogeneity of the Gauge function (see Lemma G.5), have
-c-ci (u,- -c)
"K-o; (w: cz)
+ St
+ SK c, (Uh - Ct)
Ic-e (since Sx-e. (u: ct) max(()n -c) 1))
1 1+S
$1, where the last inequality follows from Sk-e, (u; c.) s S₁ by Lemma 2.1
(64)
Eq. (64) implies that
W; Ct K ct by definition of the Gauge function (see Definition 2.2), which is equivalent to
w; E K.
Proving Item 3 We now show Item 3
Fix E K. Using the expression of ğ. and the triangle
inequality, we have that
Ku un u. g.)l sKu u. (uu ue, st)l Kgr wi -c)c ct)l and since e, IC (Lemma 4.1) and w. e K. (B)) by Item 2 and Assumption 2.2, we have
12R++2RG ((u u4, st)l.
< + HH;" 1/2 (u (u)++))l / 8 H1s (by Hölder's inequality)
s 2RG + 2RG (I 1/2 ( ct)l H, 1/2 u.)l) / H.s:,
< 2RG + 4RG V8 (see below)
(65)
< 2RGG1+ +d)).
where (65) follows by the fact that K. s & (Lemma 4.1) and that u, e Ey; this is because u, the output of A which is constrained to output vector in & at round t.
35

---

Proving [tem 4
We now prove that
Vu E K,, (g,, u) s (gr. U, -u) 3GR
(66)
T
For this, define the surrogate loss function le:
tu Rd (e()) = (g. u) l( us ct) < <0} (gi. w, ci) Sk-c, (i)
Since the pair (St, 81) is the output of GaugeDist(u,, K, H4, e) with KT we have by Lemma 2.1]
Vu E R", Sx-ea (u ct) Sk-ai (u: ct) + (u - u,)² -u)- R
(67)
Now, since wR (u:-c)/(11 Si) ct (see Algorithm 2) and St 2 Sx-e. (ut - -c,) 2 (by
Lemma 2.1] we have that - (gt, ct) 0f (gt, we Ct) 2 O. And so, using (67) and the
definition of l, we get
Vuc R (vu)) (1))
(g: [[g:; Ut - c.) <0 (gt, wi - cc.) 8t, un u) Ngr: we ci) T
(ge, u, u) ((g, w: w.- ca)l T'
(by definition of g. in Algorithm
(g., U1 u) 2GR
(68)
where the last inequality uses that K. S (BR) (by Item and Assumption 2.2 e K. (by Lemma 4.1p, and llg.1 s G (Assumption 2.1).
remains to prove that (gt, w. u) s lo (u:) - l (u), , for all u e K. First, note that we have for all E K., Sk-e, (u- cx) max(0, 7k-o; (u cx) 1) 0 (by definition of the Gauge function), and so
2, u) (gr: u): V.
(69)
We will now compare (g:, w.) to le(u)) uz) by considering cases. Suppose that S, In this case, we have we uy and so (gt, we) (gt, uz) = & (w:). Now suppose that S; > 0 and (gt, Ue ce) 2 0. In this case, since w; T+S, Cr, have
(gt, wi) S+ (gi, u c.) ci).
(gi, u: c.) + (gi, ct) (gi, uz) (u())). [case where (ge, u, ct) 2 2]
(70)
Now suppose that S, > 0 and (gt, - c,) < O. Again, using that w, Mycc, + Cr, we have T+S,
(gt, w.) + (gt. wi c.) Sk-c, (2: - ct)
=(g:, u, ct) + Sx-ci uu - Ct)
+ (g:,ci).
1 1 S₁
and so since (gt, u ct) < and Sx-c, (wt ct) 2 St
Ki8zz (by Lemma 2.
$ (g), - ci) 1 1+ ml072 (g),c)),
1+
(gi,u,) u.) + +l(gi, ui -cell $1872'
$ (9),4) + |/ gell |
11- (m+- - -c)ll "1872''
(Hölder's inequality)
(m e E,) $ (g:, ux) + |/112222 gell x
GR
$ (g:, u.) + T
(71)
36

---

where the last inequality follows from the fact that Tmax (Hi) S k 16 R² (by Lemma 4.1 and Igil s G (Assumption 2.1p. Rearranging (71) we get
GR
(9c, wi)
uz) un) (gt, we cc) Sk-e (u -c) (=)== ((())) [case where (gi, u, ca) 0]
T
(72)
By combining (68)
69)
(70) and (72) we obtain
GR
2GR
Yu E K,
(g:; wr u)
s ((())) - -l((u) s (gr, ur - u)
T
T
which shows the inequality in (66)
E.2 OCO Regret (Proof's of Theorem 4.1)
Proof. Fix u K. By Lemma 4.2
the sequence of vectors (g:) satisfies (g.) c cB(G) with
G G- (1 4nd). Thus, by invoking Lemma 4.3 we gel
(un) E {x Red (x- c+1)
H (41)
(x cc-1
and
" [u -u.uu.g) u.gi)²) s 2n R² + +200 C d2d2 dlog(1 + TT?)
(u u. 91)
2
21)
24RGd+ dlog(1 + 9n. T72)
(73)
21j
where in the last step we used that 7 10dGR
We now prove that
(g. w. u)
2 2 w. u)²
5
Σ (g. u2 u)
2-220
(g. 20 un - u)²)
!
+ 10GR 16RGd log( (R/r),
which together with (73) would complete the proof. Using Lemma 4.1 we have
V [T),
lir, uu -u)l 2RG(1+ 4d).
(74)
Combining this with the facts that:
It s H,s, s 2d} (g., w. - u) (ā., u) 3GR x > x 2=² in non-decreasing for all x s 1 (we instantiate this with x = T[V lo His, s
T for all te [T] (by Lemma 4.2
2d) (gt, wi - u. and x (ge, ur - u) 3GK ); and
" S ToaGR
we get that for all te [T]
I( 8 H.s, s 2d)
((9r, w. - u) - -n/g,, w: 2))
(g., u. - u) 3GR
6nGR
9n R²
ng u, u)
(g., u: u)
T
T
(g., u, u) m/ u, u)² 10GR
T
where the last step follows by (74) and and n 10dGR
Summing this over t= 1,... T, we obtain
! "( ui uz²) + 10GR
ge, un - u)
2
2 T(V 88 His: $ 2d] ((0r w0 1 u) ? " w. - =2)²)
> Σ (gr, we u4 7 (g:, wi - u)²) 16d GRlog(///)))
(75)
37

---

where the last inequality follows by the fact that Σ/= 1f 8, His s 2d} < 8d (og((or)) (by
Lemma 4. IJ uy K B(R): and 9. é (B)), for [T). Rearranging (75) and combining
with (3) we get the desired result.
Computational cost. The per-round computational cost of Algorithm 2 is dominated by the calls of the GaugeDist (Algorithm T) and PoE (Algorithm 3) subroutines. As established in Lemma 2.1 the cost of single call to GaugeDist is at most sopp (K.) Iog( l/r(TR/r)) Similarly, Lemma 4.3 show that the cost of single call to PoE is bounded by O - Consequently, the total per-round of Algorithm is O((d' (C))( log(TT//r)).
Rates for Stochastic Convex Optimization
In this section, we use our regret bound from Theorem 4. to derive a state-of-the-an convergence rate for projection-fres freee stochastic convex optimization that only depends the asphercity of the set K. logarithmically. We start by stating our assumptions for the stochastic optimization setting.
Assumption F.1. There is a function f K. + R and parameters 2 and G > such that the loss vector gt that the algorithm receives round
is of the form gi 9: & where
For all t 2 1, 9: (w())) where w, is the output of the algorithm at round t;
. (Ex) c TRd are ii.dd noise vectors such that B[G.] 0 and [[[ o², for all t 1; and
For all t 1, |g s G.
The conditions in Assumption F.1 are standard in the stochastic convex optimization literature; see, e.g., [19]. Under Assumption F. parameter 77 to
we now state the guarantee of Algorithm when setting the input
1
dlog(1 + x2
1) min
(76)
10dRG
16R202T
where K. R/r and r, R. R.>00 are as in Assumption 2.2
Theorem F.I. Ler 2 2 and e IC be given and suppose that Assumptiin 2.2 and Assump tion 2.1 hold with 0 s and G O, respectively. Consider call to Algorithm with input (T,c,r, R, G, for n as in (76) Then, for k = R/r, we have
dlog(1 9dTT222)
+ 56d2GR(1 + log 9x2
B[f(@r)] - inf f(w)= 4Ro wek
T
T
where Wr T DY wi and (we) are the iterates of Algorithm 2
The computational cost is at most
O (T (C (KC) + d²) llog()))))
The proof of Theorem F.] is very similar to that of 19 Theorem 5.1]. Proof. Let u² e arg min fuu). Using Jensen's inequality, we get
E[f(@r))-f(u))
1 <
E
Σ (f(w:) f(u'(()) f(u'))
T
$ T
Σ (g,, wi u²)
(by convexity and g. e af(ww))
[=1
Σ (gt, wi 2
EE [E]]] by Assumption F.1
(77)
7
38

---

Now, by instantiating the bound in Theorem 4.1 with comparator u é K, we get:
T
Σ (g. w =u) "
9t. wi u2)²
2
dlog(1 + R2 + 50d 50d Go(loo(E))))())))
(78)
2n
Now, by Assumption F.1 (in partieular, the fact that 9: 9t Ev) together with the fact that (a + b)d $ 2a + 25 and Wi, u² B(R), we have
(g:, w. u²) u²)²² s 2(9 wi - u
SR* |E&/?
(79)
On the other hand, by definition of u² and the facts that w, wi, w2, E B(R), we have for all te [T]:
2GR (gt, we u²)
2 f(w)) - f(n'), (by convexity of f and Ør (f(w:))
2 0,
(80)
where the last inequality follows by the fact that e K. (Lemma 4.2) and that u² is the minimizer of within K. Note that (80) implies that for all t [T),
lgt. wi u² > (ge. - u²) 2GR
(81)
T
Picking up from (79) we get
Σ gt. w. 2²
$ 2 > (gt, WT u u²²²+ 8R² |5
Σ
t=1
1=1
T Σ
$ 4GR
(gt, Wt u')l R
15
(by the left-hand side inequality in (80)
1-1
S <4GR Σ gr, Wi u²) + SG R² + 8R²
Σ
1
(by (81)
E1
E=1
Plugging this into (78) and rearranging, we get
Σ (9,, wi - u - RG Σ (g.. wi - =4)
1-1
dogg( + 9d2 R²² 12)1) |c: 2
$ 42 R2 + Rn Σ
+ 50d log(H/r)).
2m
[=1
Taking the expectation on both sides and using that E[g = g. and E[| 1 s a², we get
AnR + 4nG² dlog(1 1 + 2 n2? 22211²)
GR(1
2n
E Σ (g, wi- u')
-2GR
Σ
(gr, w. (gr,w,,-"))
T Σ
(1 2GR))) .E
(gt, wi u²)
T (B[ (((()))))(())))))))
2
where the last inequality follows by the fact that 17 1GR and rearranging, get
and (77)
Now, dividing by T on both sides
2
B[f( f(u'((()))))) SnR² o2 R
dlog(1 + 9d R2
50d log R/r))
T
2n
T
GR
dlog(1 92PT2
10dGGR(1 log
8n 02
(82)
T
2n/
T
39

---

where the last inequality follows by 10dGR'
1 Note that the optimal tuning of in (2) is given by
dllo(1+ cPP(3)
"
16R
We now consider cases.
Case where 17" & T0dGR we get
First, note that this implies that 1j" And so, plugging this into (82)
dlog(1 9d²T2R²2)
GR
50d + log
[f(())))-((3)) AR
(83)
T
Case where 17" TOdGR expression of 17", we have
In this case, we have 17 TOdGR Now, using that 1)" ToaGR and the
5dG
dlog(1 (1 kx2)
(84)
Plugging 17 TOdGR into (82) and using (84) get
(case 17" ToaGR
E (TT) 1 f(u")
GR. +
dlog(1 + (2T
50d + log
s SnRR' 0²
T
2
T
d dlog(1 1 + R22T2R22
GR
5d GRlogl + xx2
2Ro
T
T
T
50d + log
(85)
T
where the last inequality follows by (84)
Thus, combining (83) and 85))
get
dlog(1 kx2
56d G log 1 + xx²)
B[s(@r)] f(u'((())))))) 4R
T
This proves the desired convergence rate.
G
Helper Lemmas
Lemma G.1 ((1)). Let A, E Rdxd be such that A is invertible and r ||A-1 < 1. Then,
I(A+E) A | [1][A-")
Lemma G.2. Let C be a convex set and let H 3dxd and Rd be given. Further, let arg min Iu H. Then,
VuEC, |2- ul H 2 1u" ul
Proof. See, e.g.,
Lemma G.3. Let r O, Co, e Rdd, and H e gdxd be given, and define E = {u Rdd (u c) H e) $ 1). IfBBB (fo((o.)) E then (e,, E
Proof. Let x (cco. r) and suppose that X E. Since is centrally around (i.e.. -(u-c) + cc for all u e E), we have -(B(co, r) c) + c E. Since B(r) -B(r), this implies that
X = B(-co + 2c, r) EE
40

---

Now, since & is convex, we have that
1
1 x E 2
x
(86)
2
Fix 2 e B(r). We have that Co 2c e X and + co X and so by (86) we have 2 c E &, which establishes that r) & and completes the proof.
Lemma G.4. Let e Rdxd be a positive semi-definite matrix, and let v e Id {0} be given. Define
4d2
2d
Hov' H
He =
H
4d
2d d- 00 Ho
Then, we have mmax (Ha) s + 2/d²) m ()).
Proof of Lemma G.4
Since
H
2d
Hoo
= H, we have that
2d-+d-1
HH
4d2 1
2
H, 3
H s
1 d²
H
4d2 - 4
where the last inequality follows from the fact that Adf-1
f for d 2 2 and that H is positive
1d2-4
semi-definite. This implies that mmax (H+)= (1 2/d²) F (H).
We need the following properties of the Gauge function (sce e.g. [20] for proof).
Lemma G.5. Let IRd {0) and
R. Further, let be closed convex such that B(r) SC B(R)) Then, the following properties hold:
a. re ( (w) oe (w) supwecs x² w and (c = C.
b. oc(aw) ade (w) and @oc(w doc (w) arg max w). for all O.
c. r|w/|| s (w)) R. wll. || R 7he (w) s /w//rr and B(1/R) c B(1/r).
41


Reviews:
[{"review_id": "FNs1CTmZoy", "reviewer": "Reviewer_h8Ps", "summary": "This paper proposes a novel separation-based algorithm for online convex optimization (OCO) to improve the sample complexities in terms of the shape-dependency of the action set. The separation-based algorithms in prior works were proposed to mitigate the computation complexities due to the projection steps of the gradient-based methods, however, they suffer from having regrets that scale polynomially with respect to the asphericity of the action set. The algorithm proposed in this work achieves a regret bound that only depends polylogarithmically on the asphericity, albeit having a worse dimension dependence.", "questions": "1. As elaborated in the weakness section, we recommend the authors to revise the manuscript to correct typos in problem formulation and clarify the dependencies of all parameters when comparing regrets in related works. \n\n2. The authors presents a natural extension to stochastic optimization on page 9, however, it is not clear what is the oracle model considered here. We recommend the authors to clarify the oracle model, as well as providing a brief overview of the best know results in different settings (e.g., zeroth order, first order, or having access to both). \n\n3. The asphericity of the action set is often not a fundamental constraint in the sense that a hyperelliposid action set could have large asphericity, but it is trivial to achieve the optimal O(\\sqrt{T}) regret by operating in a linearly transformed space where the action set is a hyperball while constraint parameters G and R remain the same. Could the authors provide an example where the dependency of asphericity can not be resolved by extending [16][7] through this approach.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \nOCO is a central problem in online learning and improvements in its regret bounds under computational constraints are impactful. The algorithm proposed in this work achieves improved performances compared to best known separation-based algorithms when the shape of the action set is highly skewed. The proposed algorithm was explained in details, with clear update condition and intuitions, and their performance is analyzed and adequately compared to prior works.  \n\nWeaknesses: \n1. While the regret performance achieved by the proposed algorithm is order-wise larger than the sample-optimal gradient-based algorithms, they can also be order-wise larger compared to separation-based algorithms in prior works in certain regimes, e.g. when dimension d is large, due to the additional d factors in the stated upper bounds.\n2. The assumptions and prior results can be better clarified. For instance, there is a typo in the second bullet point of definition 2.1 which makes the inequality being always invalid and the meaning of the separation oracle totally unclear. It would also be helpful to clarify what are the dependency of R and G for the regrets achieved in prior works to ensure the comparison is approprate.", "was_revised": true, "final_justification": "While the authors promised to revise the manuscript to correct the typos, the paper could benefit from examples where high asphericity gives a fundamental lower limit on the required sample complexities. The reviewer believes that a simple ellipsoid action set wouldn't serve as such a hard instance, since it can be resolved with the linear-transformation-based approach. The authors wanted to defend this example as a hard instance, but it appears that there is a mismatch in their comparison between the outer radius of the two action sets. \n\nOverall, the topic of the paper is interesting, but perhaps similar to the point raised by AC it would be beneficial if this result could be accompanied by some converse arguments (even informal ones) to demonstrate why the proposed rates can not be easily improved.  Therefore, my score is unchanged. However, the topic investigated in this work is interesting enough, so I won't have a strong opinion against its acceptance.", "rebuttal": "Thank you for taking the time to review our work and provide your feedback.\n\n**While the regret performance achieved by the proposed algorithm is order-wise larger than the sample-optimal gradient-based algorithms, they can also be order-wise larger compared to separation-based algorithms in prior works in certain regimes, e.g. when dimension d is large, due to the additional d factors in the stated upper bounds.**\n\nThere are regimes where our regret bound is worse than that of previous separation-based algorithms, such as when $\\kappa$ is already small. For this reason, our approach can be seen as complementary to existing methods.\n\nAs a side note, it is possible to design an algorithm that achieves a regret matching the best of the bounds obtained by our method and those in [16] and [17]. One such approach would aggregate the outputs of the individual algorithms using exponential weights; see, for example, reference [1] below.\n\n **As elaborated in the weakness section, we recommend the authors to revise the manuscript to correct typos in problem formulation and clarify the dependencies of all parameters when comparing regrets in related works.**\n\nWe will correct the typo in the definition of the separation oracle. All the regret bounds—both ours and those we cite—depend linearly on the product RG, which is why we omitted it. This is generally the case for OCO algorithms, as their outputs are typically equivariant to the input scales R and G. The exception is algorithms that adapt to R and G, which is beyond the scope of this paper.\n\n**The authors presents a natural extension to stochastic optimization on page 9, however, it is not clear what is the oracle model considered here. We recommend the authors to clarify the oracle model, as well as providing a brief overview of the best know results in different settings (e.g., zeroth order, first order, or having access to both).**\n\nWe consider the standard stochastic optimization setting with access to a first-order stochastic gradient oracle. Some details specific to the stochastic setting were moved to Appendix F due to space constraints. We will restore more of this material to the main text thanks to the additional page that is allowed for the camera ready.\n\n**The asphericity of the action set is often not a fundamental constraint in the sense that a hyperelliposid action set could have large asphericity, but it is trivial to achieve the optimal O(\\sqrt{T}) regret by operating in a linearly transformed space where the action set is a hyperball while constraint parameters G and R remain the same. Could the authors provide an example where the dependency of asphericity can not be resolved by extending [16][7] through this approach.**\n\nThis is not always true, and here is why. Let $W \\in \\mathbb{R}^{d \\times d}$ be a positive-definite matrix, and let $\\mathcal{E} = \\\\{x \\in \\mathbb{R}^d \\mid x^\\top W^{-1} x \\leq 1\\\\}$ be an ellipsoid. Assume that $\\lambda_{\\min}(W) \\geq 1$, so that $\\mathcal{E} \\subseteq \\mathbb{B}(1)$. Suppose we are in the OCO setting, where $\\mathcal{E}$ is the feasible set and the losses $f_t$ are $G$-Lipschitz over $\\mathcal{E}$; that is, $\\\\|\\nabla f_t(x)\\\\| \\leq G$ for all $x \\in \\mathcal{E}$.\n\nNow, if we apply a reparametrization to work on the Euclidean ball instead, the reparametrized losses we work with are $\\tilde{f}_t: \\mathbb{B}(1) \\rightarrow \\mathbb{R}$ given by $\\tilde{f}_t(y) = f_t(W^{1/2} y)$. By the chain rule, the gradients of $\\tilde{f}_t$ satisfy $\\nabla \\tilde{f}_t(y) = W^{1/2} \\nabla f_t(W^{1/2} y)$ (assuming $f_t$ is differentiable for simplicity). Therefore, the Lipschitz constant of $\\tilde{f}_t$ in the reparametrized problem can be as large as $\\sqrt{\\lambda{\\max}(W)} G$, which can be arbitrarily larger than $G$ for ill-conditioned $\\mathcal{E}$. Here, $\\sqrt{\\lambda{\\max}(W)}$ is a measure of the asphericity of $\\mathcal{E}$.\n\nSince the regret bound scales linearly with the Lipschitz constant of the losses (see the answer to the first question), working with the reparametrized losses in this way can introduce a dependence on the asphericity in the regret bound. This issue with reparametrization holds more broadly (beyond the ellipsoid setting), as we discuss in the paragraph titled “Limitations of reparametrization” on Line 194.\n\n[1] Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. In Advances in Neural Information Processing Systems, pages 6020–6030, 2017."}, {"review_id": "HjPUGhb1Ur", "reviewer": "Reviewer_No35", "summary": "The paper proposes a novel projection-free algorithm for Online Convex Optimization (OCO) that relies solely on a separation oracle.  Prior projection-free methods based on separation oracles suffer from poor dependence on the asphericity $\\kappa$ of the feasible set. This work introduces an ellipsoid-based reduction combined with an ONS-type inner algorithm, achieving a regret of $\\tilde{\\mathcal{O}}(\\sqrt{dT}+d^2)$ with only logarithmic dependence on $\\kappa$, while preserving per-iteration oracle complexity. It significantly improves over previous methods in settings with ill-conditioned feasible sets.", "questions": "Please see above.", "limitations": "Please see above.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n* Improved Regret Bound: Achieves better dependence on asphericity $\\kappa$, improving practicality for ill-conditioned problems.\n\n* Methodical Analysis: The paper provides detailed and rigorous proofs, including algorithmic design, update rules, and complexity.\n\n* Conceptual Clarity: The use of Gauge projections and separation oracles is clearly explained and builds logically on prior work.\n\n## Weaknesses\n* Computational Overhead of Ellipsoid Updates: These updates involve operations with per-round complexity of $\\mathcal{O}(d^\\omega)$, where $\\omega$ is the matrix multiplication exponent. Any estimation for $\\omega$? Would it influence the overall computational complexity? \n\n* Lack of Empirical Validation: The paper focuses entirely on theoretical contributions and does not include any empirical results. While the regret guarantees are strong, it is unclear how the algorithm performs in practice. Empirical validation—such as experiments on standard OCO benchmarks or simulations comparing runtime and regret with other projection-free methods—would significantly strengthen the paper.\n\n * Minor issue: It seems that you forgot to mention the full name of ONS.", "was_revised": true, "final_justification": "I think this is a good paper and I would like to keep my score.", "rebuttal": "Thank you for your comments and for reviewing our paper.\n\n**Computational Overhead of Ellipsoid Updates: These updates involve operations with per-round complexity of $\\mathcal{O}(d^\\omega)$, where $\\omega$ is the matrix multiplication exponent. Any estimation for $\\omega$? Would it influence the overall computational complexity?**\n\nThe $d^\\omega$ term in our computational cost arises from the cost of inverting a matrix (or solving a $d \\times d$ linear system). This operation is required by the PoE subroutine to project onto the ellipsoid. The exponent $\\omega$ is currently estimated to be less than $2.371552$. However, even if we take $\\omega = 3$, the cost $d^\\omega$—that is, the cost of solving a linear $d \\times d$ system—remains much smaller than the cost of Euclidean projection for many feasible sets of interest\n\n**Lack of Empirical Validation: The paper focuses entirely on theoretical contributions and does not include any empirical results. While the regret guarantees are strong, it is unclear how the algorithm performs in practice. Empirical validation—such as experiments on standard OCO benchmarks or simulations comparing runtime and regret with other projection-free methods—would significantly strengthen the paper.**\n\nWe have acknowledged the lack of experiments in the limitations paragraph. Nevertheless, we believe the theoretical results we provide stand on their own.\n\n**Minor issue: It seems that you forgot to mention the full name of ONS.**\nWe will address this. Thank you for pointing this out."}, {"review_id": "XVa4PpGNft", "reviewer": "Reviewer_xFnF", "summary": "This paper proposes a projection-free method for OCO that accesses the feasible set through calls to a separation oracle. Their method has the advantage that the regret only depends on the asphericity $\\kappa = R/r$ in the logarithm.", "questions": "1. What is the term $\\omega$ in the computation cost term $d^{\\omega}$? \n2. How does the computation cost of the method compare with the following: (a) euclidean projection in every round, (b) putting the set in isotropic position once, (c) existing projection-free methods.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The approach has the clear advantage that the dependence on the asphericity in the regret is only in the logarithmic. This has not been achieved by existing methods.\n2. The paper clearly states how its analysis methods differ from the related work [17]. In particular, the use of ellipsoids rather than balls for the projection is a clear innovation.\n3. In general, the paper is well written.\n\nWeaknesses:\n1. The paper builds closely on [17], with fairly-minor improvements in guarantees.\n2. The computation cost per iteration depends on the term $d^{\\omega}$. It appears that this could result in significantly higher computation cost than existing methods. As such, the regret-per-computation of this method might not be better than existing methods even if the regret is lower for a given $T$. Furthermore, it is unclear if the computation cost is less than even projection-based methods (e.g. OGD, RFTL).\n4. Table 1 (which compares the guarantees with existing work) is somewhat confusing in that it shows the number of oracle calls per a round, but doesn't compare the computation cost. This is important given that the motivation for projection-free OCO is to reduce the computation cost of classical methods.", "was_revised": true, "final_justification": "I appreciate the author's efforts in the extensive discussion. This discussion answered the clarifying question that I had. \n\nI am maintaining my current score. I believe that this score is appropriate because the paper has (what I see to be) moderate methodological contribution in using an ellipsoid instead of a ball in the algorithm [17] and developing an associated analysis. At the same time, it is less clear how significant the performance guarantees (e.g. regret, computation cost) are as it seems that existing methods can provide better guarantees in many regimes.", "rebuttal": "We appreciate your careful review and the time you spent on our submission.\n\n**The paper builds closely on [17], with fairly-minor improvements in guarantees.**\n\nThe regret bound in [17] scales linearly with the asphericity, which can be arbitrarily large. In contrast, our bound moves this dependence inside a logarithmic factor, which we view as a significant improvement over the guarantee in [17].\n\n**The computation cost per iteration depends on the term . It appears that this could result in significantly higher computation cost than existing methods. As such, the regret-per-computation of this method might not be better than existing methods even if the regret is lower for a given . Furthermore, it is unclear if the computation cost is less than even projection-based methods (e.g. OGD, RFTL).**\n\nThe $d^\\omega$ term in our computational cost comes from inverting a matrix (or solving a $d \\times d$ linear system), which is required by the PoE subroutine for projecting onto the ellipsoid. Here, $\\omega$ is the matrix multiplication exponent, currently estimated to be less than $2.371552$. The per-round cost of our algorithm is on the order of $d^\\omega + C_{\\text{separation}}$, where $C_{\\text{separation}}$ is the cost of performing separation. This can be slightly higher than the per-round cost of the algorithm in [17], which is $d^2 + C_{\\text{separation}}$. However, in typical optimization settings, the separation cost $C_{\\text{separation}}$ dominates $d^\\omega$ (the cost of solving a $d\\times d$ linear system), in which case the overall computational cost of our method would be comparable to that of [17].\n\nAs for the comparison to Euclidean projection: if we could reduce the cost of Euclidean projection onto an arbitrary set to that of solving a linear system, it would represent a major breakthrough. In general, the cost of Euclidean projection can be much higher than the cost of solving a $d \\times d$ linear system (i.e., $d^\\omega$). In fact, given access to a separation oracle for $\\mathcal{K}$, the cost of Euclidean projection onto $\\mathcal{K}$ using state-of-the-art cutting plane methods is on the order of $\\tilde{O}(d^3 + d \\cdot C_{\\text{separation}})$, which is clearly worse than $d^\\omega + C_{\\text{separation}}$. Moreover, the complexity of cutting plane methods often hides large multiplicative constants in the $\\tilde{O}$ notation.\n\n**Table 1 (which compares the guarantees with existing work) is somewhat confusing in that it shows the number of oracle calls per a round, but doesn't compare the computation cost. This is important given that the motivation for projection-free OCO is to reduce the computation cost of classical methods.**\n\nAs mentioned earlier, the separation cost typically dominates the $d^\\omega$ term, which is why the table focuses on the separation oracle complexity. We will add the other computational costs to the table for completeness.\n\n**What is the term $\\omega$ in the computation cost term $d^\\omega$?**\n\n$\\omega$ is the matrix multiplication exponent and is currently estimated to be less than $2.371552$. In our case, we use $d^\\omega$ as an upper bound on the cost of solving a $d \\times d$ linear system.\n\n**How does the computation cost of the method compare with the following: (a) euclidean projection in every round, (b) putting the set in isotropic position once, (c) existing projection-free methods.**\n\n*Cost of Euclidean projection*: $\\tilde{O}(d^3+d\\cdot C_{\\mathrm{separation}})$ (see Lee et al., 2017 reference below). This cost is achieved using state-of-the-art cutting plane methods. We note that the $\\tilde{O}$ notation can hide large constants, which often makes such methods practical only for small- to medium-sized problems. Alternatively, one could use an interior point method for Euclidean projection, but this requires a self-concordant barrier for the feasible set, which is not always available. Even when such a barrier exists, the typical cost remains greater than $d^3$.\n\n*Putting the set in isotropic position*: $\\tilde{O}(d^4) \\cdot C_{\\text{separation}}$ (see [14]). This can be prohibitive, even if performed only once. Moreover, placing the set in isotropic position does not necessarily eliminate the dependence on asphericity in the regret bound; see the paragraph titled “Limitations of reparametrization” on Line 194 and the response to Reviewer h8Ps.\n\n*Per-round cost of existing projection-free methods*: $\\tilde{O}(d + C_{\\text{separation}})$ for [16], and $\\tilde{O}(d^2 + C_{\\mathrm{separation}})$ for [17]. The dependence on $\\kappa$ is linear in the regret bounds of both [16] and [17]; in [16], for example, $\\kappa$ multiplies $\\sqrt{T}$. Since the cost of separation typically dominates the cost of solving a $d \\times d$ linear system (i.e., $d^\\omega$), the overall complexity of our method can be considered comparable to that of [17], or slightly higher.\n\n*Per round cost of our approach*:  $\\tilde{O}(d^\\omega + C_{\\text{separation}})$; see answer to the second comment above for a comparison with [17].\n\nLee, Y. T., Sidford, A., & Vempala, S. S. (2018, July). Efficient convex optimization with membership oracles. In Conference On Learning Theory (pp. 1292-1294). PMLR."}, {"review_id": "0RrcH8yr75", "reviewer": "Reviewer_Urz6", "summary": "The paper considers the problem of developing efficient projection-free algorithms for online convex optimization (OCO). More formally, at each time $t$, the learner (an online algorithm) chooses $w_{t} \\in \\mathcal{K}$ for some convex set $\\mathcal{K}$, the adversary chooses a convex loss function $f_{t}$ and reveals a subgradient $g_{t} \\in \\partial f_{t}(w_{t})$, and the learner incurs loss $f_{t}(w_{t})$. The goal of the learner is to minimize the regret $\\sum_{t = 1} ^ {T} f_{t}(w_{t}) - \\inf_{w \\in \\mathcal{K}} \\sum_{t = 1} ^ {T} f_{t}(w)$. The optimal regret for the problem is $\\Theta(\\sqrt{T})$ achieved via the projected-OGD algorithm. However, OGD requires projections to $\\mathcal{K}$ (whenever the iterate falls outside $\\mathcal{K}$), which can be prohibitively expensive. Projection-free methods aim to alleviate this issue by assuming access to linear optimization/separation-based oracles. The current paper expands the line of work on separation-based oracles for OCO and proposes an algorithm that achieves a regret bound $\\tilde{\\mathcal{O}}(\\sqrt{Td} + d ^ {2})$, thereby improving the polynomial dependence on $\\kappa$ ($\\mathcal{K}$'s asphericity parameter; defined as the ratio of the smallest circumscribed ball and the largest inscribed ball) in the $\\mathcal{O}(\\kappa \\sqrt{T})$ and $\\mathcal{O}(\\sqrt{Td} + \\kappa d)$ regret bounds that appeared in the prior works. The key novelty in the paper is the usage of the ellipsoid method and a reduction to online convex optimization over a sequence of dynamically changing ellipsoids that always contain $\\mathcal{K}$ and progressively well approximate $\\mathcal{K}$.", "questions": "(1) In Definition 2.1, I believe the correct condition for Item II should be $\\langle v, u \\rangle > \\langle v, w \\rangle$ for all $w \\in \\mathcal{K}$, isn't it?\n\n(2) For the most-relevant prior work [17], what is the computation cost per round? Do they also incur a $\\mathcal{O}(d ^ {\\omega})$ cost per round? My guess is not, but it would be great if the authors could clarify.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper considers a fundamental limitation in existing projection-free separation oracle-based methods. Notably, they suffer from a polynomial dependence on $\\kappa$, which can be arbitrarily large for ill-conditioned sets. The paper completely manages to resolve the polynomial dependence (only a logarithmic dependence on $\\kappa$ remains) via a novel method. Remarkably, the proposed algorithm requires the same number of calls ($\\tilde{\\mathcal{O}}(1)$) to the separation oracle as the existing methods. The paper explains the limitations of existing methods that achieved the $\\mathcal{O}(\\kappa \\sqrt{T})$ and $\\mathcal{O}(\\sqrt{Td} + \\kappa d)$ bounds very clearly. The proposed algorithm is built upon these limitations, and Sections 3 and 4 are very well written. The algorithm, although technical, can be understood via the main ideas presented in Sections 3 and 4.1.\n\nWeaknesses: The authors acknowledge in the limitations that the paper does not have experiments to support the theoretical claim. However, I do not consider it a major weakness of the paper. The proposed algorithm has a solid theory and lack of experimental evidence is very minor.\n\nOverall, my assessment of the paper is towards acceptance.", "was_revised": true, "final_justification": "I did not have any concerns and continue to vote for acceptance.", "rebuttal": "We are grateful for your time and for your thoughtful evaluation of our work.\n\n**In Definition 2.1, I believe the correct condition for Item II should be $\\langle v, u \\rangle > \\langle v, w \\rangle$ for all $w \\in \\mathcal{K}$, isn't it?**\n\nWe will fix this typo.\n\n**For the most-relevant prior work [17], what is the computation cost per round? Do they also incur a  cost per round? My guess is not, but it would be great if the authors could clarify**\n\nThe per-round cost of [17] is $\\tilde{O}(d^2 + C_{\\text{separation}})$, which can be slightly lower than our cost of $\\tilde{O}(d^\\omega + C_{\\text{separation}})$, where $C_{\\text{separation}}$ is the cost of performing separation. However, since the cost of performing separation typically dominates the cost of solving a $d \\times d$ linear system (which we upper bound by $d^\\omega$ in our analysis), the overall complexity of our method can be considered comparable to that of [17], or slightly higher."}]

Author rebuttal:

Meta-review: Overall the opinion of the authors about this paper is positive. We had long discussions with the authors and I went over the paper myself. It is agreed that the paper makes an interesting contribution to the field of projection-free OCO, which received significant interest in recent years. 
I urge the authors to fulfill their promise that if the paper is accepted the discussions regarding previous projection methods and the limitations of this work would be better clarified: When comparing to previous work it is highly important to also include the runtime (and even memory requirement) and the dependence of regret bound on the dimension, e.g., when comparing with Hazan & Kale 2012 and other works. It may also be interesting to discuss the comparison to projection-based methods in terms of the overall time to reach epsilon average regret. This is so important, since this method (which improves upon a recent similar result), while is still so-called "projeciton-free" is becoming more and more computationally demanding in terms of runtime (beyond oracle implementation) and memory and has regret bound which scales with the dimension.
Decision: Accept (poster)