Projection-Free Online Convex Optimization via Efficient Newton Iterations
Authors: Khashayar Gatmiry
Zakaria Mhammedi
Venue: NeurIPS 2023 poster (2023)
Keywords: Online Learning
Online convex optimization
projection-free
Newton method

Abstract: This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain $\mathcal{K} \subset \mathbb{R}^d$. Classical OCO algorithms (such as Online Gradient Descent) typically need to perform Euclidean projections onto the convex set $\mathcal{K}$ to ensure feasibility of their iterates. Alternative algorithms, such as those based on the Frank-Wolfe method, swap potentially-expensive Euclidean projections onto $\mathcal{K}$ for linear optimization over $\mathcal{K}$. However, such algorithms have a sub-optimal regret in OCO compared to projection-based algorithms. In this paper, we look at a third type of algorithms that output approximate Newton iterates using a self-concordant barrier for the set of interest. The use of a self-concordant barrier automatically ensures feasibility without the need of projections. However, the computation of the Newton iterates requires a matrix inverse, which can still be expensive. As our main contribution, we show how the stability of the Newton iterates can be leveraged to only compute the inverse Hessian a vanishing fractions of the rounds, leading to a new efficient projection-free OCO algorithm with a state-of-the-art regret bound.

Projection-Free Online Convex Optimization via Efficient Newton Iterations
Khashayar Gatmiry
Zakaria Mhammedi MIT mhammedi @mit edu
MIT gatmirydmit.cm
Abstract
This paper presents projection-free algorithms for Online Convex Optimiza- tion (OCO) over convex domain R Classical OCO algorithms (such as Online Gradient Descent) typically need perform Euclidean projections the convex set K. to ensure feasibility of their iterates. Alternative algorithms, such those based the Frank-Wolfe method, swap potentially-expensise Euclidean projections onto IC for linear optimization over K. However, such algorithms have a sub-optimal regret in OCO compared projection-basee based algorithms. In this paper, we look at a third type of algorithms that output approximate Newton iterates using self-concordant barrier for the set of interest. The use of self-concordant barrier automatically ensures feasibility without the need of projections. However, the computation of the Newton iterates requires a matrix inverse, which can still be expensive. As our main contribution, we show how the stability of the Newton iterates can leveraged to only compute the inverse Hessian a vanishing fractions of the rounds, leading to new efficient projection-free OCO algorithm with a state-of-ther regret bound.
1 Introduction
We consider the Online Convex Optimization (OCO) problem over a convex set IC c B2 in which learner (algorithm) plays game against adaptive adversary for T rounds. At each round i [T]. the learner picks w, K given knowledge the history Hi-1 {(e,, w., w,,)) Then, the adversary picks a convex loss function &, K. E with the knowledge of H4-1 and the iterate w,, and the learner suffers loss (w:) and proceeds to the next round. The goal of the learner to minimize the regret after I' rounds:
T Regr(w) (w:w) -(w))-((()))
against any comparator K. The aim of this paper is to design computationnall--efiiien (projection- free) algorithms for OCO that enjoy the optimal (up log-factor in T) Ö(VT) regret.
The OCO framework captures many optimization settings relevant machine learning applications. For example, OCO algorithms can be used in offline convex optimization as more computationally- and memory-efficient alternatives to interior-point and cutting plane methods whenever the dimension d is large [14] [6). OCO algorithms are also often used in stochastic convex optimization, where the standard O(VT) regret (achieved by, e.g. Online Gradient Descent) translates into the optimal O(1/VT) rate via the classical online-to-batch conversion technique 3 37 It has been shown that OCO algorithms can also achieve state-of-the-ane accelerated rates in both the offline and stochastic optimization settings despite being designed for the more general OCO framework 6 28). What is
This the optimal rate when further assumptions are made.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

more, it has recently been shown that even non non-convex (stochastic) optimization can be reduced to online linear optimization (a special case of OCO), where it then possible to recover the best-known convergence rates for the setting 77.
Given the prevalent use of OCO algorithms in machine learning applications, it is important to have computationally--ffcccen algorithms that scale well with the dimension d of the ambient space. However, most OCO algorithms fall short of being efficient because of the need of performing (Euclidean) projections onto IC (potentially at each iteration) to ensure that the iterates are feasible. These projections are often inefficient, especially in high-dimensione sets. Existing projection-free free OCO algorithms address this computational challenge by swapping eeentiaaly-expensivvv Euclidean projections for often much cheaper linear optimization or separation over the feasible set K. However, existing projection-fis free algorithms have sub-optimal regret guarantees in terms of their dependence T, or have potentially unbounded "condition numbers" for the feasible set multiplying their regret guarantee.
settings with complex feasible
Contributions. this paper, we address these computational and performance challenges by revisiting an existing (but somewhat overlooked) type of projection-free OCO algorithms. Unlike existing algorithms, our proposed method does not require linear optimization or separation over the feasible set K. Instead, the algorithm, Barrier- Barrier- Regularized Online Newton Step (BARONS) uses a self-concordant barrier & for the set X. to always output iterates that are guaranteed to be within K.; much like interior point methods for offline optimization. In particular, our algorithu outputs Newton iterates with respect to vareingy translated versions of Φ. The main novelty of our work is in devising new efficient way of computing the Newton iterates without having to evaluate the inverse of the Hessian of the barrier at every iteration, which can be computationally expensive in digensiienni settings. Our algorithm only needs to compute full inverse of the Hessian vanishing O(1/VT) fraction of the rounds. For the rest of the rounds, the computational cost is dominated by that of evaluating the gradient of the barrier 4, which can be much cheaper than evaluating the inverse of its Hessian in many cases.
For the special case of a polytope with m constraints, we show that there is choice of a barrier (e.g. the lee-Sidford barrier) that when used within our algorithm, reduces the per-round compu- tational cost to essentially Õ() linear-system-solyy cheaper than performing linear optimization over I., which other projection More importantly, our algorithm achieves a dimension-free Ö(VT) regret bound. This improves over the existing regret bounds of projection-free algorithms over polytopes. For example, among projection-free algorithms that achieve O(VT) regret, the algorithms by [28] 11 26), which require a separattio/mmemmershipp Oracle for K. have a multiplicative K R/r factor multiplying their regret bounds, where r. R 0 are such that B(r) S K s B(H). The constant k. known as the asphercity [12] can in principle be arbitrarily large. Even after applying a potentially expensive pre-processing step, which would typically involve putting the set K. into (near-) isotropic position g 38 K can still
of size m x d. We show that this is often
algorithms require.
be as large as d in the worst-case, and so the regret bounds achieved by the algorithms of (28
26
can be of order (dv/T); this is worse than ours by a d factor. Other projection-fiee free algorithms based on the Frank- Wolfe method, e.g. those in 10 35 19 also have multiplicative condition numbers that are even less benign that the asphercity K. In fact, the condition numbers in the regret bounds for polytopes appearing in, c.g. [1O, can in principle be arbitrarily large regardless of any pre- pre-processing.
Finally, another advantage of our algorithm is that it can guarantee a sublinear regret even for non- Lipschitz losses (i.e. where the norm of the sub-gradients may be unbounded). In particular, we show that the general guarantee of BARONS implies a Ō(VdT) dT)) regret bound for the portfolio selection problem [5] and a problem of linear prediction with log-loss (36), all while keeping the per-round computational cost under (dd), when T 2 d. The losses in both of these problems are neither bounded or Lispehitz.
Related works. In the past decade, many projection-free OCO algorithms have been developed to address the computational shortcoming of their projection-based counter parts [14 Most projection- -free algorithms are based on the Frank- Wolfe method and perform linear optimization (typically once per round) over IC instead of Euclidean projection. Under no additional assumptions
16
15
18 28 [T]
We credit the name BARONS to 27 who used reruaee-reullrizzed Newton steps for the portfolio selection problem.
2

---

other than convexity and lipschitzness of the losses, the best-known regret bound for such algorithms scales as O(T3/4) [1S]. While this bound is still sublinear in ' and has no dependence in the dimension d, it is sub-optimal compared to the O(vT) regret bound achievable with projection- the recent years, there have been improvements to this bound under additional assumptions such as when the functions are smooth and/or strongly convex [1] 18], or when the
based algorithms.
For the case where IC is a polytope, 10 presented a mmear-optimizztion-ban based algorithm that enjoys a O(pv d regret bound, where is conditioning number for the set I.. Unfortunately, j can be large for many sets of interests it essentially scales inversely with the minimum distance between the vertices of K. In this work, we achieve a dimension-free (VVT) regret bound without the j factor.
convex set IC is smooth and/or strongly convex [T 23 29 24].
More recently new type of projection-fiee algorithms have emerged which use member- ship/separation oracle calls instead of linear optimization [28 I 24 (6]. From a computational perspective, separation-base
and linear optimization-basee algorithms are not really comparable, since there are sets over which separation is cheaper than linear optimization, and vice-versa. On the regret side, separation- based algorithms have been show to achieve a ((v/T) regret bound, where is the asphercity of the set K. Separation-basee algorithms are simple, often easy to analyze, and achieve the optimal-in-T regret bound, unlike linear optimization- based algorithms. However, the multiplicative factor in their regret bounds means that a pre-conditioning step may be required to ensure it is appropriately bounded. This precondition step would involve putting the set into (near-)
isotropic position [Р]: an operation, that can cost (dd') arithmetic operations [38]: and even after
such pre-processing step, K can still be large as d in the worst-case. Our algorithm has the benefit of not requiring any pre-processing step.
A third type of algorithms avoid projections by outputting Newton iterates that are guaranteed to be feasible thanks to the use of a self-concordant barrier. The first such algorithm in the context of online learning was introduced by (2) They presented general recipe for using self-concordant barriers with Newton steps in online linear optimization. However, their approach falls short of being computationalll--ffiiie the barrier at every iteration. Inspired by the work of [2], [I used damped Newton steps with quadratic terms added to the barrier to design an efficient algorithm for the classical portfolio selection problem. Closer to our work is that of (30] who used a similar barrier for designing an algorithm for exp-concave optimization that can be viewed as a computationally--ffiiien version of the Online Newton Step [13]. Similar to our work, [30] also leverage the stability of the Newton iterates to avoid computing the inverse of the Hessian of the barrier at every step. However, their approach and analysis, which are tailored to the exp-concave setting do not necessarily lead to improved regret bounds in the general OCO setting we consider. In particular, their algorithm does not lead a O(VT) regret bound over polytopes.
as their algorithm needs to compute the inverse of the Hessian of
Finally, for our application to polytopes, we make use of recent tools and techniques developed for solving linear programs efficiently. In partieular, which can be computed efficiently and, when used to compute Newton iterates, leads to the state-of- the-art& Ō(Vā) iteration upper-bound for solving a linear program. For the OCO setting, we show that using the Lee-Sidford barrier within our algorithm leads to a Ö Ō(VT) regret bound, We also note that ideas similar to the ones we use to avoid computing the inverse of the Hessian of the barrier at every round were used to amortize computations in the context of solving linear programs (see
make use of the Lee-Sidford barrier [20, 21 22)
e.g. 39 40
Outline. In section 2 we present our notation and relevant definitions. In Section 3 algorithm and guarantees. In Section 4 we apply results to the case of polytope. All the proof are differed to the appendix.
we present our
2 Preliminaries
Throughout the paper, we let K. be a closed convex subset of 2d. We denote by || the Euclidean norm and by B(R) 2d the Euclidean ball of radius R > O. We let i denote the interior of K.
3

---

Our main algorithm, which can be viewed as "online" counter-pai to the Newton iterations [3]. uses a self-concordant barrier over the of interest to avoid the need of performing Euclidean projections onto IC. Next, we present the definition of a self-concordant barrier.
Self-concordant barriers. For the rest of this section, we let K. be convex compact set with non- empty interior int K. For twice [resp. thrice] differentiable function, we let v2 f(u) [resp. V [(u)] be the Hessian [resp. third derivative tensor] of u.
Definition 1 (Self-concordant function), A convex function f:int KC + IR is called self-concordant with constant M, 2 if is Os and satisfies
f(xx) + +00 for 24 + I OK; and for
* For all z & int K and u R I IV* [u)) uII s (
Definition 2 (Self-concordant barrier). For M v2 say that K:int TR is (M v) self- concordant barrier for K. if is a self-concordant function over with constant Mj and
Vw in,
sv.
Computational Oracles. We will assume that our algorithm has access to a self-coneordant function over the set IC through the following gradient and Hessian Oracles.
Definition 3 (Gradient Oracle). Given point w int K and tolerance > 0, the gradient Oracle Og ( returns e-upproximate vector V. of the gradient (D(w) in the dual local norm of the Hessian:
V - (-W)ll--- SE.
We denote by Cgrad( the computational cost of one call (g))
When clear from the context, will simply write cgrad and Ograd for Carad and Ograd ()). respectively.
Definition 4 (Hessian Oracle). Given point w int K. and tolerance >> 0, the Hessian Oracle Obess(4) returns a matrix H and its inverse H-1 which are 1 = E spectral approximations of the Hessian and inverse Hessian of t at w:
(1 (1- 11 & (1++)V
and (1-e) 11 (1+s)V-
We denote by (bees()) the computational cost of one call to (hess( ())
When clear from the context, we will simply write Chess and Ohess for Chess and Ohess (). respectively.
Additional notation. We use the notation f to mean f fs Cg for some universal constant C > 0. We also write f Ög to mean f s polylog(T', g. We let V = (V²)-1 and v- refer to the inverse of the Hessian and the inverse of the square root of the Hessian, respectively.
3 Algorithm and Regret Guarantees
In this section, we construct projection-free algorithm for Online Convex Optimization. The algorithm in question (Alg. [1) outputs approximate Newton iterates with respect to "potential functions" (Φ;) that take the following form:
(.(w) = +(w)
Σ 5m
gN5
where (gs dl,(w,,,) (w.)) are the sub- gradients of the losses (l.) at the iterates (w.) of Algorithm I and a senf-connordant function over K. Algorithm [ Juses the the approximate gradient and Hessian Oracles of & (see 2 to output iterates (wa) approximate Newton iterates in the following sense:
V [T), Wi+1 & w. - v 2 P++ (w.)
As by now somewhat standard in the analyses of online Newton iterates of the form T we will bound the regret of Algorithm by showing that:
I

---

The iterates (w) are close (in the norm induced by the Hessian (2)(ww)) to the FTRL iterates, which are given by
wi E argmin ((
wick
The regret of FTRL bounded by O(VT).
Our main contribution is an algorithm that outputs iterates (we) that satisfy the first bullet point (i.e. iterates that satisfy [[ while only calling a Hessian Oracle (which is potentially computationally expensive) O(I/VT) fraction of the rounds after I' rounds. As we show in Section 4 for the case where IC is a polytope with m E constraints, the algorithm achieves a Õ(VT) regret bound, where the per-iteration computational cost essentially reduces to linear-system-solve involving d x m matrix. Among existing OCO algorithms that achieve ((VT) regret bound, none achieve this computational complexity for general polytopes with m constraints (see Section 4 for more details).
3.1 Efficient Computation of the Newton Iterates with BARONS
The key feature of BARONS (Algorithm D is that is uses amortized computation of the Hessians. Namely, BARONS computes the inverse of the Hessian the barrier & only for a small fractions of the iterates (w²). Henceforth, we refer to the iterates where the algorithm computes the full inverse of the Hessian as landmark iterates; these are the iterates (uz) in Lines 13 and 16 of Algorithm I The idea behind this is that for a sufficiently curved barrier Φ the Newton iterates with respect to are stable enough that it suffices to compute the inverse of the Hessian of & at the closest landmark iterate. For example, this is what was done in 30 to design an efficient algorithm for exp-concave optimization.
Unlike the setting of 30), where it is possible add quadratic terms the barrier for additional stability, in our setting we cannot do that without sacrificing performance in terms of regret. Without the quadratic terms, the Newton iterates are not stable enough for our desired guarantee. Instead of adding regularization terms, BARONS takes Õ(1) Newton steps per round to get "closer" to the Newton iterate with the true Hessian matrix. This simple approach is key to the success of our approach.
In the next subsection, we give a generic guarantee for BARONS.
3.2 Generie Regret Guarantee of BARONS
In this subsection, we present general regret and computational guarantee for BARONS under minimal assumptions on the sequence of losses and without turning the "step size" fj. In the next subsection, we will instantiate the regret guarantee when additional assumptions on the sequence of losses are available. We now state the main guarantee of BARONS (the proof in Appendix C.I).
Theorem (Master theorem). Let & be a self-concordant function over K. with constant Mş 20000 a = 0.001, and Myevten (log eMa ). Further, let (wi) be the iterates of Algorithm / with input (n, E, a, Myeewon)) and suppose that the corresponding sub-gradients (gt) satisfy 1 24(w))) S b, for all t2 2 1. Then, the regret of Algorithm is bounded as:
and let b, E,,, > O and Muewton E N be such that S 10006MM'
((((w))- -4 (c s (w) E1
+ ++ Elell (w)))) +
> El
Igellv 20(10)))
Vw e int (3)
Furthermore, the computational cost of the algorithm is bounded by
of (Cgrad + +d)) TT log
Chees
chees,
(MoTe+ + Mo Σ 1-1
T
nlleell (lloe)l)--
eM4
Theorem 5 essentially shows that it is possible to achieve the same regret as FTRL, while only computing the inverse of the Hessian of 4 at most Õ (T) number of times.
Informally, the "curvature" of convex function is high when the rate of change of its gradients is high.
5

---

Algorithm BARONS:
Bagrier-Regularized Online Newton Step
Require:
Parameters e, O, and Mienton
Gradient/Hessian Oracles Og /Olese for self-concordant function + with constant Mo
w= E aargmin,.xx (w)-
1: Set W1 = '" H1 = Obess (onms(ww) (w"), and 0.
2: for l= 1...,,
3:
Play and observe Ir (w)(w:).
4:
Set 8, = 8t-1 + 19th-
5: Set w Wig.
// Perform intermediate Newton steps to decrease the Newton decrement
6:
for m ,,..., N.ueeton do
7:
Set V Og (w(+1)
8:
Set mm V-1 8t. V x (0
9:
Set w+1 w
Hr
E+1
10:
end for
11:
Set Wh+11 itt
// Check if the landmark needs updating
12:
if [1 well H. 11)(4M then
13:
Set u ut // Update landmark
14:
Het1 H, and H7,1 H.
15:
else
Set M W,+1- // landmark update
17:
Set H..1 Ohees (w++1) and compute H
end if
19:
end for
3.3 Regret Guarantee Under Local and Euclidean Norm Bounds on the Sub-Gradients
We now instantiate the guarantee in Theorem 5 with (Ms, -eff-cooooonn barrier & for the set IC, with respect to which the local norms of the sub-gradients are bounded; that is, when l9 vv- I b. We note that the regret bound in (36) has an additive ((w) which may be unbounded near the boundary of K. However, it is still possible to compete against comparators in int K by making additional assumptions assumptions in the sequel. For the next theorem, we will state the regret bound BARONS relative to comparators in the restricted set:
the range of the losses [ [2]. We discuss some of these
K. = (1- (cw"),
where @ denotes the Minkowski sum, w" aargmin (ww), and (0, a parameter.
With this, we now state a regret bound for BARONS when the aah--radieets of the losses have bounded local norms. The proof of the next theorem is in Appendix C.2
Theorem 6 (Local norm bound). Let T be (Ms. s)-seff-conooraant barrier for K. and let C (0, 1),b > Further, suppose that for all t [T], [0llv=24((w)) S b, where (we) are the iterates
of BARONS with input parameters (n,, a. Myevtoa) such that
vloge RT
T 0.001, and Miexttn == = =0(108 1
==
VV
(5)
EM4
For T 1 large enough such that 17 To00b 8 2000005 the regret of BARONS is bounded as
Regf
BAROES
BAROFS (w) by vI logc, Yw Kc,
(6)
where K, K. as in Further, the computational complexity of BARONS this case bounded by
0 ( +df) (T. log MM
Chess Ma To loge

---

Remark 1. The regret bound in Theorem 6 is stated with respect to comparators in the restricted K2 defined in (4). possible extend this guarantee to all comparators int K. under an additional assumption on the range of the losses. For example, for w" aargmin weK (ww), we have
lx
1
w0') ) (()
sup wrint tett([]]
then the regret guarantee in (6) can be extended to all comparators in int K. up to an additive O ((VT) term (see Lemma 7 in the appendix). In this case, the log term in the computational complexity need be replaced by log T. We note that the condition in 7 does not require uniform bound on the losses. Instead, only restrict the rate of growth of the losses (&(()) as approaches the boundary of K. As we show in the sequel 4.2g
7
is satisfied for some popular losses which are not Lipschitz.
We now instantiate the guarantee in Theorem | when the sub- gradients are bounded in Euclidean norm (instead of local norm); that is, assume that for all i [T], [Ige|] s G for some G 0. We note that this assumption implies (7). and we will be able to bound the regret against all comparators
in int K. alluded to in Remark [ The proof of the next theorem is in Appendix C.3
Theorem 7 (Euclidean norm bound). Let Vi be an (Mv,v) self-concordant barrier for K. and let (())= = V +
+ 28a |-|12. Further, let G, R > and suppose that K. = B R) and all t e [T), 1 s G, where e (wr) and (wi) are the iterates of BARONS with input parameters (1), Eq Cr (Beton)) such that
log T
V T
a 0.001, and Miytton i= θ log 1 EMy
11 =
(8)
RG
T
For T 1 large enough such that 17 '0000G
1
20000 the regret of BARONS is bounded
BARONS (w) & RG Tog Yw E int IC. Regr
(9)
Further, the computationnll complexity of BARONS in this case is bounded by
o (C (grad (V) + d²) T log vM
T
Chees Chees(V) MM TTuloggl
4 Application to Polytopes Using the Lee-Sidford Barrier
In this section, we assume that the set IC is polytope in Rdd specified by m linear constraints:
K= fw e IRd1
Vie [m], a. 1/))
(10)
and we construct efficient gradient and Hessian Oracles for self-concordant barrier for KC This will then allow us instantiate the guarantees of BARONS in Section 3 and provide explicit and state-of-the-arr bounds on the regret of BARONS.
We will assume without loss of generality that ||a,]l for all i [m], and let A = (aI...., am) R.mxd denote the constraint matrix of the set K.. For the rest of this section, it will be convenient to define the "slack" variables Sw,i a. - 66, for [m]. Here, Sw,i essentially represents the distance of w to the ith facet of the polytope K. Further, we let S., == diag(sw) be the diagonal matrix whose äth diagonal entry is Sw.i.
The barrier. To perform Online Convex Optimization over X., we pick the regularizer of BARONS to be the Lee-Sidford (LS) barrier L [22 with parameter > O, which is defined as
t (v²) min - degddeAA' S. A) + I+p tr tr(v)=1/p). DE
where V diag(w) (). One way to think of the LS barrier is as a weighted log-barrier. As we will discuss in the sequel, this choice will confer computational and performance (in terms of regret) advantages over the standard log-barrier.
7

---

Self-concordance of the LS barrier. p ((log(m)) self-concordant function with parameter Maia satisfying
According to [8 Theorem 30), the LS barrier with the choice
Ma = (log(m))))) (/6) Ö(1,
The other favorable property of this barrier is that its Newton decrement at any point IC is of order (Vvd); that is,
| (w) (w))-app = Ō(Va).
(11)
Therefore, g is a (((())(()) (eeoo(dddddll-ooooooee self-concoordan barrier. For the log-barriets the fight-hand side of 11 would be /m.
We consider the computational complexities of gradient and Hessian Oracles for qLs. By 22 we have that for > 0,
Cost of gradient and Hessian Oracles.
Cerad (1't) S Õ(Crvs log((/=)), and Chera s Ö(Crya log(1/=)),
where Caya is the computational cost of solving a linear system of the form A diag(v) = y, for vectors IRg. and y Rd we recall that A (0i...., dm)² is the constraint matrix for K. In the worst-case, such a linear system can be solved with cost bounded as
Caya S 00md ))
(12)
where w is the exponent of matrix multiplication, and is the number of constraints of K. However, as we show in the sequel, Cays can be much smaller in many practical applications.
With this, we immediately obtain the following corollary for the regret and run-time of BARONS under local norm and Euclidean norm bounds on the sub- too-gradients.
Corollary 1 (OCO over polytope with LS barrier). Let G,, R, > O, and suppose IC is given by (10) and that his is the corresponding LS barrier. Further, let (w:) be the iterates of BARONS, and Tet Ke be the restricted version of defined in (4. Then, the following holds:
Local uorm bound: If (fllee))=== $ b, for all t 2 1, and the parameters (1,, az Mnenton) of BARONS set as in Theorem 6 with t Th. and (Ma,v) (ō(1), (d)), then for T large enough (as specified in Theorem (). the regret of BARONS is bounded by
RegT
BARONS (w) by d'lloge
Vw E K..
(13)
Euclidean norm bound: If S B(R) and 119.1 s G. for all 2 1, and the parameters
(n,E, M,newoo of BARONS are set as in Theorem 7 Tith (-.)) = (.) + रमे 1 and
(Ma,u)= = (Ō(1), then for T large enough (as in Theorem 7 BARONS has regret bounded as
BARONS (w) RG Vwe int
(14)
In either case, the computational complexity is bounded by
Õ((c ((cay*+dd) +d) T Caya dvT).
(15)
where Ceys is the computational cost of solving a linear system of the form A diag(v) Ax y. for vectors e Rd and e Ted (recall that A is the constraint matrix for the polytope K.).
Using the barrber We note that since K. is a polytope, we could have used the standard log-barries
m
log
w
Σ
log(b/ w)
(16)
This barrier is (1, seeesecoo--onn and so instantiating Theorem with it would imply a Ö(bvmdT) regret bound in the case of local sub-grade sub-gradient norms bounded by b > 0. Using the LS barrier replaces the /m term in this bound by dd regardless of the number of constraints-sce

---

13). However, this comes at C computational cost, which can be as high as md in the worst-case (see I2 In the case of the log-barrier, this cost would be replaced by md (essentially because Cgrad s oo < (md)). Thus, when m is of the order of d, using the log-barrier may be more computationall-eficinn compared to using the LS barrier. In the next corollary, we bound the regret of BARONS when + $ bloR; this result an immediate consequence of Theorem 7
Corollary 2 (OCO over polytope with the log barrier). Let G, > O, and suppose K. given by (10) and that glog is the corresponding log-barrier. Further, let (wx) be the iterates of BARONS. If CCB(R and I[gel S G. for all 1 2 1, and the parameters (1), E, O2 Mgevren) of BARONS are set as in Theorem 7 with (c)) o golo (.) + 2nº2 I. and (Me (1,m), then for T large enough (as in Theorem BARONS has regret bounded as
Regt RegaAROKs
BARONS (w) RGV/
Vw e
(17)
The compulational complexity is bounded by
σ (mmd+ d). T (mm
(18)
4.1 Implications for Lipschitz Losses
We now discuss implications of Corollary algorithms for Lipschitz losses.
and compare the bound of BARONS to those of existing
Dimension-free regret bound. We note when the Euclidean norms of the sub- uub-gradients are bounded, BARONS achieves a dimension-free O(VT) regret bound. In contrast, the best dimension- free regret bound" achieved by existing projection-free free algorithms is of order 0(73/1) (see algorithms that achieve e.g. VT regret; for examples those presented in 128 II 26). are not dimension-free Their regret bounds are of order (KVT),, where phercity parameter can depend on the dimension d 288. and even after a pre-conditioning step (which would involve putting the set K. into near-isotropic position and can cost up 12dd²) (25), as large as d in the worst-case. Of course, to make a fair comparison with existing projection-free algorithms, we also need take computational complexity into account. This is what we do next.
We also note that existing scparation/memmbrrhiip--
R/r with r. R such that B(r) K. (R). The as-
be
Computational cost. The computational cost in 1.5 should be compared with that of existing projection-free algorithms. For linear optimization-based projection-free algorithms, the computa- tional cost after I' rounds is typically of order Cain .T, where Clin is the cost of performing linear op- timization over KC' which, for a polytope K,, reduces to solving linear program. Using -tate-of-the-art interior point methods for solving such linear program would cost Cain & Ö(Vd-Caya) see e.g. [22] Thus, linear optimization-be based projection -fren algorithms can have a cost that is a factor Vd worse than that of BARONS in the setting of Corollary [ On the other hand, separation//mmmbership- -based algorithms, the computational cost scales with O(C=pp TT) after T rounds, where Coop is the cost of performing separation for the set K. For a general polytope Rdd with m constraints, we have Ceep s O(md), which may be smaller than Çeys (the latter can be as large as mdd-1 in the worse case;see h.). Here, it may be more appropriate to compare against the computational guarantee of BARONS given in Corollary 2 by (18). we have that for T 2 d0-2 2m, the computational cost of BARONS in the setting of the corollary is dominated by (md + d T, which is comparable to that of existing separation-base algorithms.
4.2 Implications for Non-Lipschitz Losses
Another advantage BARONS has over projection-free and even projection-based, algorithms is that has regret bound that scales with a bound on the local norms of the gradients (3). We now showcase two online learning settings where this leads to non-trivial performance and computational improvements over existing OCO algorithms.
"The dependence in T he improved under additional structure such smoothness strong-convexity of the losses.
This only concerns algorithms that interior point method to implement linear optimization over K.

---

The portfolio selection problem is a classical online learning problem where the gradients of the losses can be unbounded. In this paragraph, we demonstrate how the guarantee of BARONS in Corollary [ leads to a non-trivial guarantee for this setting both in terms of regret and computational complexity. In the online portfolio setting, at each round I, a learner (algorithm) chooses a distribution W; Ag over fixed set of d portfolios. Then, the environment reveals a return vector T; E 1Rg0 and the learner suffers a loss
Online Portfolio Selection [5].
(())) == - log ii rt--
The goal of the learner is to minimize the regret Regr(w) (w) = Σi- (f=:(((w)) ((w)) after T 2 1 rounds. For this problem. it is known that a logarithmic regret is achievable, but the specialized algorithms that achieve this have computational complexity that scales with min dTT)
[5] 32 [7]. On the other hand, applying the generic Online Gradient Descent or the Online Newton Step to this problem leads to regret bounds that scale with the maximum norm of the gradient (which can be unbounded). Instantiating the guarantees of BARONS in Corollary | with O set to the standard log-barrier for the simplex /
in particular the bound in (33), to the online portfolio selection the norm of the observed gradients. Furthermore, we have Cays < (d)). and so by (15) the computational complexity is essentially OddT') after T rounds. Technically, the bound in (13 only against comparators in the restricted set IC.. However, by setting с = 1/T, it possible to extend this guarantee to all comparators in int K. as explained in Remark [ since the losses this case satisfy (6) (27 Lemma 10].
problem leads an Ö(VdT) regret bound, which does not depend
Linear prediction with the log-loss. Another classical online learning problem with unbounded gradients is that of linear prediction with the log-loss [36]. For this problem, each round the learner receives feature vector 24 E X' s Rd, outputs wa W Rd, then observes label yt + {-1,1) and suffers loss
((w.. 1yy 1} log(1 w. Ily 0} log(1 w..
In the settings, where (X' W) (A,, (1)) and (x,
(1), Az), we have that
(V(((w) (v-2)())))))))))))))))))))))))) S 01) for all w int W, where set to the corresponding log-barrier for W.
Thus, instantiating Corollary [ (in particular (3)) in this setting implies that BARONS achieves
regret bound of the form:
O(VaT),
(19)
and has computational complexity bounded by (dTT). as long as T d. Again, we emphasize that the bound in (19) does not depend on the norm of the gradients, which may be unbounded.
Finally, we note that there exist few specialized algorithms that provide sublinear regret bounds for non- lipschiititz losses. This includes, for example, the Soft-Bayes algorithm (34]. However, this algorithm is specialized to the log-loss with a particular dependence on the predictions, and is not clear, for example, what regret bound it would have in the linear prediction setting and other similar settings with non-Lipschitz losses.
"Technically, we need barrier for the set {w e Roo Eiqa--1 Wss 5 1): see e.g. 32
10

---

Acknowledgments and Disclosure of Funding
ZM acknowledges support from the ONR through awards N00014-20-1-2336 and N00014-20-1-3994
References
[1] Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang. Faster rates for convex-concave games. In Conference On Learning Theory, pages 1595-1625. PMIR, 2018.
[2] Jacob D Abemetth,, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. 2009.
[3] Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions Information Theory,
2004.
[4] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
[5] Thomas M Cover. Universal portfolios. Mathematical Finance, 1(1):1-29, 1991.
[6] Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In International Conference on Machine Learning, pages 1446-1454, PMLR. 2019.
[7] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non- smooth non-convex optimization through online-to-non-comyee conversion. arXiv preprint arXiv:2302.03775, 2023.
[8] Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing lewis weights to high precision. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2723-2742. SIAM, 2022.
[9] Abraham D Flaxman, Adam Tauman Kalai, and Brendan MeMahan. Online convex optimiza- tion in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
[10] Dan Garber and Elad Hazan. A linearly convergent variant the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, (6(3):1493-152 2016.
[11] Dan Garber and Ben Kretzu. New projection-free algorithms for online convex optimization with adaptive regret guarantees. In Conference on Learning Theory, pages 2326-2359. PMLR, 2022.
[12] IL Goffin. Affine and projective transformations in nondifferentiable optimization. Trends in Mathematical Optimization, pages 79-91, 1988.
[13] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learming, 69(2-3):169-199 2007.
[14] Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1843-18 1850, 2012.
[15] Elad Hazan and Edgar Minasyan. Faster projection-free free online learning. In Conference on Learning Theory, pages 1877-1893. PMLR, 2020.
[16] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional conference on machine learning, pages 427-435. PMLR, 2013.
[17] Rémi Jézéquel, Dmitrii M Ostrovskii, and Pierre Gaillard. Efficient and near-optimal online portfolio selection. arXiv preprint 13X 2022.
[18] Ben Kretzu and Dan Garber. Revisiting projection-free online learning: the strongly convex case. International Conference on Artificial Intelligence and Statistics, pages 3592-3600. PMLR, 2021.
11

---

[19] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimization variants. Advances in neural information processing systems, 28, 2015.
[20] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in (vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424 433. IEEE, 2014.
[21] Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 230-249. IEEE, 2015.
[22] Yin Tat Lee and Aaron Sidford. Solving linear programs with sqrt (rank) linear system solves. arXiv preprint arXiv: 191000033,, 2019.
[23] Kfir Levy and Andreas Krause. Projection free online learning over smooth sets. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1458-12 1466. PMLR, 2019.
[24] Ning Liu and Benjamin Grimmer. Gauges and accelerated optimization over smooth and/or strongly convex sets. arXiv preprint arXiv:2303.050:3 0,0037 2023.
[25] László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an o*(4) volume algorithm. Journal of Computer and System Sciences, 72(2):392-417, 2006.
[26] Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan, Projection-free adaptive regret with membership oracles. In International Conference on Algorithmic Learning Theory, pages 1055-1073. PMIR, 2023.
[27] Haipeng Luo, Chen Yu Wei, and Kai Zheng. Efficient online portfolio with logarithmic regret. Advances in neural information processing systems, 31, 2018.
[28] Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, pages 5314-5390. PMLR, 2022.
[29] Zakaria Mhammedi. Exploiting the curvature of feasible sets for faster projection-free online learning. arXiv preprint 2rXiv:2205.114700 2022.
[30] Zakaria Mhammedi and Khashayar Gatmiry. Quasi-newton steps for efficient online exp- concave optimization. arXiv preprint arXiv:2211.0135: 2022.
[31] Zakaria Mhammedi and Alexander Rakhlin. Damped online newton step for portfolio selection. In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178, pages 5561-5595. PMLR, 2022.
[32] Zakaria Mhammedi and Alexander Rakhlin. Damped online newton step for portfolio selection. In Conference on Learning Theory, pages 5561-5595, PMLR, 2022.
[33] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
[34] Laurent Orseau, Tor Lattimore, and Shane Legg. Soft-bayes: Prod for mixtures of experts with log-loss. In International Conference on Algorithmic Learning Theory, pages 372-399, PMLR, 2017.
[35] Fabian Pedregosa, Geoffrey Negiar, Armin Askari, and Martin Jaggi. Linearly convergent frank-wolfe with backtracking line-search. In International conference on artificial intelligence and statistics, pages 1-10. PMLR, 2020.
[36] Alexander Rakhlin and Karthik Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv preprint 1rXiv:1501.07344 2015.
[37] Shai Shalev-Shwartz al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[38] Tomasz Tkocz. Asymptotic convex geometry lecture notes. 2018.
12

---

[39] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2599-778 SIAM, 2020.
[40] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 775-788, 2020.
[41] Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency-regre pareto frontier for online learning of portfolios and quantum states. In Conference on Learning Theory, pages 182-226. PMLR, 2022.
13

---

A Self-concordance properties
Throughout, for twice-differentiable function f:int K R. we let (xxf) (vf(z))<=3)) denote the Newton decrement of f at E i..
Lemma Let f:int K R. be self-concordant function with constant M, 1. Further, let x e int K and xy argminneex f(x). Then, 1) whenever Mr, f) < f/M,, we have
satisfies x" int and - (t=Isly'(a)) I zz=zz(l>)s>) - (z,
and II) for any M 2 My the Newton step x" = = A(x*, .f MZ, f)2/(1 MX,,
Lemma 2. Let frint K be self-concordant function with constant M, and x int K. Then, for any such that r == - x/>> < M/M we have
(1 (1-M)r)&v'
v f(x) s (1- (1-
The following result from 33 Theorem 5.1.5] will be useful to show that the iterates of algorithms always in the feasible set.
Lemma 3. Let f: int K + IR be self-concordant function with constant Mj 2 and x e int K. Then, E = fw q e Rd [w 2/, 1 E int K. Furthermore, for all w E Eg, we have
[ 2
|| x w S My x
Finally, we will also make use the following result due to 31 Lemma 4. Let f:int K R. be self-concordant function with constant My 0. Then, for any I, we int such that r = || w|/>>((>) < M, we have
- v/ (1 Mrr) W x 2
B Technical Lemmas
Our analysis relies the crucial fact that the Newton decrement can be sufficiently decreased by taking a Newton step using only approximate gradients and Hessians. We state this fact next; the proof is in $D.I
Lemma (Decrease in the Newton decrement). Let & be self- colcooonncodnntt function over int K. with constant Ms O, and let y Rdd be such that Muy +) 1/(40M+). Further, let H e IR and V Rd be such that
19, -0(() SEC
(20)
40Mo
(1-a) < (1+a)
(21)
for a < 1/5. Then, for ÿ y
my H - V we have
X(7" ()) 9MM 2)5a Φ) X(y*, 4) s 20(1 +a)e (1+ 20 a)a) A ②).
Next, we show that as long as the Newton decrement is small enough at the current iterate W;-1, the "intermediate" Newton iterates ( (w"") remain close to the landmark point u this will be important for the proof of Theorem [5] The proof
D.2
Lemma 6 (Invariance under Newton iterations). Let db be self-concordant function over int K. with constant Ms > O. Let b 0, Miauton O(log EM I), a S 1/(1000M)). < 1/ (200000Ma). o = 0.001, and v & 1/)1000Mbb). Further, let (we, with uy ft. H,) be as in Algorithm with imput (1), E, Or, MBpouton). Suppose that at round 1 of Algorithm we have
XW Pr-1) a and | Wi- (00011)0((mm))) S 40M
(22)
14

---

For t > 1, if the sub-gradiens 9t-1 at round satisfies 1190-11v-20 1) S b, then
15 m-1
M( 21)
X(w, 11) 5005 40Ms
(23)
Furthermore, we have for all m [Mgoeton]:
v
2 (()((( (2 (w;"),
(24)
|mm u- H
(25)
10M4
15 m-11
|00 wi (( $
+ 240c,
(26)
49M
16
15
||u"" u4-1 H,- | - 4c-1l| s
+ 5000 + 2a. (27)
40M
16
where W arx (w) is the optimum solution of 2..
We note that we have not made an attempt to optimize over the constants in Lemma Lemma 7. Let & be (Mg, (elee-)))---ccooooreeee barrier for K. and let w" @argmin ((w).
Further, suppose that the losses satisfy:
Es ((1-7)
1 1 T w0w) ((w)
sup weint K,(][T]
(28)
VT
Then, for any w Kc there exists w E K2/r (where Kro is as in (4) such that
((((w)))(ww)) (l((w) ( O(VT).
(29)
Proof. Fix w IC and define = F (1- +) w KTŞT. Then, by (8) we have, for all e [T].
(ww.)) (w) s $4( (x) 1/3
(30)
Summing this over t= I,..., T leads to the desired result.
C Proofs of the Main Results
Next, present the proof of Theorem 5
C.1 Proof of Theorem
Proof. The proof consists of three parts: 1) First, we show that BARONS keeps the Newton decrements A(w,. 4.),t 2 1, small this is the main invariant of BARONS; II) Then, we bound the regret of BARONS using this invariant and the results of Lemma 6 III) Finally, we bound the runtime of BARONS.
Bounding the Newton decrements. We will show that the Newton decrements satisfy
X(w,, 2.) s a == min 11000M 1000s
(31)
s 2 1. will show 31 by induction over 2 1.
Base case. The base case follows by the facts that wi e argmin ((w), Φ = and that the Newton decrement zero at the minimizer.
Induction step. Suppose that (31) holds with s s= for some 1. We will show that it holds for
t. First, note that by the update rule of landmark (see Lines 12 and 17 of Alg. TT, we have that
|| Me-1l|He. S 41M
15

---

implies the following bound the where = -.- Thus, by the choice of in the theorem's 's statement, we have
u Wt-1 Wt-1llp20(um-))
(32)
40M
This, combined with the fact that (31) holds with t (the induction hypothesis) implies that the conditions of Lemma are satisfied. This in turn implies
X(wi. 2.) (0)
A(ui Manaaro D2) s
mavste
X(w) )1) + 500 S
50
15
Missstos
(b) 5000 S a,
16
Mp 16
where (a) follows by the fact that W/ wy W Niouoto
(by definition; see Algorithm and (b) follows by the choice of MNeeton in the theorem's 's statement. This shows that (31 holds for = t and concludes the induction.
Bounding the regret. To bound the regret of BARONS, we make use of the FTRL iterates (wi), which are given by wi e argmin welk (ww): By Lemma we have that for all t E [7].
1
15
ww i ()))(
||! uuueee wi (=)()))) 49
+240 O(e),
(33)
16
where the last inequality follows by the choice of Migetoo (log (1/(sM+))) in the theorem's statement. Using this and Hölder's inequality, we now bound the sum of linearized losses of the algorithm in terms of the sum of linearized losses with respect to {wī}:
Σ (we.ge) 9c) s Eiwi 9t) Σ 1w -
- wellva 11 (
(34)
[-1
Now, by (24) in Lemma 6 (which holds due to (32) and with = t as we showed in the prequel), we have 1 < v2b(w;), which implies that [|ge ([9elv-20(w)) $ 2 2 1 -0(w.)-
Combining this with 333 and (34). we get that
(wr gc) $ Ewi 96) + O())
Σ
1) E=
(35)
Now fix w é K. Subtracting ΣT (w, ge) from both sides of 33 regret of BARONS:
Regr
BARONS
(w) S (ww (Ww .9t))
(w, (wwggh) 9r) +(e)
Σ
11 (()))
1=1
[-1
t=1
T
4 (w)
+ n Σ 1g 12 - + O(E) Σ
11 v-20))))
where the last inequality follows by the regret bound of FTRL (see e.g. (30
Bounding the run-time. Note that BARONS updates the landmark points on the rounds where
llue - wella, 1/(41M4). Now, by (27) in Lemma (which holds due and 31 with s =t as we showed in the prequel), we have
|l+ wel wella. H.
lu+- -
|lue Wa
TT 11, - ||u, Wt
11
1
15
$ 22119:t11 1 (0 +
+ 500e + 2a
40Ms
16
< [ 11- +((e),
where the last incquality follows by the choice of Myeston in the theorem's statement. Hence, the quantity | - w.] H. increases each time by at most 2n| 20(w,1) O(z). Therefore, the number of times that the landmark u, changes is bounded by
Σ (2m (2nl9.ll ( + +(E))) 0
T
MoTe+ Mo Σ nl l [=]
o
1/(41M²)
16

---

Thus, the overall computational cost of recalculating the Hessians and their inverses at the landmark iterates bounded by
(MOTEe Mr
Cheas
Σ Enlleili (1llullv-20(m))) 1=1
where the multiplicative cost Chess reflects the fact that the instance of BARONS in the theorem's statement needs 1 a accurate approximations of the Hessians and their inverses (in the sense of Definition 4 at the landmark iterates. Moreover, BARONS needs to compute an e-approximate gradient of Φ at every point wt" for all ł E [T] and m E [Maeeton] Thus, the cost of computing the gradients is Caraa ' log EM, Finally, the matrix-vector product H, 1 (w) in BARONS costs (dd²) work, and overall the computational cost is
o O +B²) - 1
T Σ nlgg (== )) t=1
+ Chess
M M4
sMa
C.2 Proof Theorem
Proof. Note that without having any effect on the algorithm, we can add an arbitrary constant to the barrier C. Thus, without loss of generality, we assume $(w") 0, which implies ((w) 0, for all
K.
We define the restricted comparator class
Ë (w KC ((w) (ww") llogc).
By 33 Corollary 5.3.3] and the fact that & is an (Mg sewp:)-selfffooorree barrier for K,, we have that
Ke S.
(36)
and so it suffices to bound the regret against comparators in R. Fix w e K. Under the assumptions of the theorem, the preconditions of Theorem 5 are satisfied and have,
T (() - (2 s 2 i + +1
T 11 ( + t-
Σ
Σ 11 11.1l ( 1ll
v log c+ nbpTT + ETb, (since t e K and l|gell 20(())) $ b)
2by /T log b/
where in the last step we used the choices of and in (5). Combining this with (36) implies the desired regret bound. The bound on the computational complexity follows immediately from Theorem the fact that [. 4 20(w:; S b, and the choices of and in (5).
C.3 Proof of Theorem
Proof. Similar to the proof of Theorem and without loss of generality, assume that V is its minimum, i.e. V (ww) = 0. We define the restricted comparator class
ズ = (w K: (w) s ((w") ) n log
(37)
By 33
Corollary 5.3.3) and the fact that v is an (Mu v) v) --seeff-coomoodaa barrier for K., we have that
K2/r E K.
(38)
On the other hand, by Lemma 7 we have that
T - [(((w=))(((w))
I (((((:))-(()++000)
sup weint FC
sup Weint K.
Combining this with (38 implies that it suffices to bound the regret against comparators in K. Fix e K. Note that since & is equal to V plus quadratic, Φ is also self-concordant function with
17

---

constant M4 My [3]. Thus, under the assumptions of the theorem the preconditions of Theorem are satisfied and we have,
1 (()) E(e((w)) (()))
T
I
T
+
Σ 1-1
2-20 (wrs)
+ Σ
ge
(39)
A-1
1
Now, by the choice of Φ, we have that
(99e)v-20(w.)) $ R //V RGIVE.
Moreover, from the condition that K. = B(R), 37 and the fact that (2=)) = 0. we have for all
K:
((w) S v log T
2
Plugging this into 39 and using that w E K, we get
Σ [(((w)) - (((())(())))) = v log T
1 "
RºG TRG
+
T+E
21
Vi
= =2RG Tlog RGVT,
where in the last step we used the choices of 1) and in (8) Combining this with (38) implies the
desired regret bound. The bound on the computational complexity follows from the computational
complexity in Theorem 5 and the fact a gradient Oracle O ( [resp. Hessian Oracle Og (V)
for (.)) ((-) + 2 can be implemented with one call to Ograd (V) [resp. Ohees [)) plus arithmetic operations.
D Proofs of the Technical Lemmas
D.1 Proof of Lemma 5
Proof. Throughout, we let h is the Newton step based on the exact gradient v
v
Recall that i and y* from the lemma's statement satisfy
y = y h and H Bounding the Newton decrement at ÿØ First, we bound the Newton decrement at ÿ*. By definition, the square of the Newton decrement at ÿ y + is
A 4) = v + h) T v (y++h)++0 ())
Now for the vector defined below, we define the function F as
2 - h) h) and F(v) = v
(40)
The partial derivative of F' in direction h is given by
DF -h -h'v2
= -V
- 2z()))
(41)
Now, by 21 we have
a 11- /||
1-a
18

---

Thus, the first term on the right-hand side of (41 can be bounded as
"r
|006))=11111177
$ 1-a
1-a
a(1 + +a)
(1 (1-a)²
a(1 + a)
(1 a)) M(y, 4) |,||v~
Plugging this into (41 and using the definition in 440 we obtain
a(1 a)) (1 a1= X(y, +) |=|v=0(0-
[F(
(42)
Now, let (s) y sh and Fo yss) F(y(s)) With this, we have
(Fo
(""(())) (") (()()
(43)
On the other hand, by Lemma and our assumption on A 2) we have
()()) v)v - *|bbvv==())) I-a / $ 1-a a
A(u, D),
(44)
(45)
30M
Thus. by Lemma I we have
(1 - 1+Mllly(s) ) v & (1- (o)l))) -yllv=(()) (2
This, together with
45 also implies that
(1 (1 y(s) )
(L+Mall))))
After rearranging, this becomes
-3.4lly(()) v)( (V) v ( v/ -vlo))))))
Combining this with 44 and the fact that e 1 gives
4M 1 v (x)) v ()(s)) v² 4))
(46)
Finally, by Lemma and 46 obtain the following bound the right-hand side of
43
(Fo y) y) & 6MaA(y, +)1 1=l
Integrating this over s gives
V + = (F
(Fo (()o))())+ + (F S. -FF))))()(oFo))()))))
5 2 DF 6M, 4) [1| (
6M
< <v DF
1 X(y. ->>
(47)
where the last inequality follows by that Mw, 4) 1/(44))4))) (0MM), we have
44
Now. note that from 46 (with s = 1) and the assumption
9
19

---

This implies
10
10
> (v) S
|12|o= = X + h 2).
9
9
Plugging this into 47 and using
42 we get
20Ms
( 2 (2
2+ [F
My,, x) h)
3(1-a)
$ a(1+a) a) X(y: 1 == 3(1-a)
20M
Myy 8) X(y + 4)
a1~a)²
< 10a(1+ + a)
X(y: $)\(μ h, 20M
X1y, ))² h $)
a)1
3(1 a)
Now, from the definition z, we have
vo 2= M 1, b)
Thus, since a 1/4, we finally get
M(y + h, 1) s 99MaA(y, 4)² + (v,
This proves the first part of the claim, i.e.
(4))
Bounding the Newton decrement y² in terms of that of 5 = h. Note that
We bound the Newton decrement at y² y -
5" -ーーシ" H (v
On the other hand, from 64 and 45
we have
V/ (1+ 3M 3 (1) v)2 7 (1)
(48)
which implies that
"² 1/2 7 (1+
Therefore,
1 wツ-h""1aa00m
(VV(y) (77))
(VQ(1") - - -, 1/2
"'' " "-" - -g,)
(1+ - -1)0))))--000(0000000000000000
49
16
49
+++)) v, レルーー
16
Combining this with 48) and our assumption on V from 20 implies
l y 1o [ (1+a))Vv(y) 4,l4 20(w) s 55(1+a) a)s.
(49)
Thus, by Lemma I we have
((1 (1-5 ( -1)))))))))))))--))))))))))))))-
11-5(1aa)eMM) -1 F²
Since E < 1/(40M4)) we get
-20(1 - 20(1++))73((1)1
(50)
20

---

Now, by Lemma instantiated with x 8" and w = yy, we have
1y* 5" (v24(1)
(1- Mo 1y8 50 (v2(()))
$ <10(1+a);,
(51)
where in the last inequality used (49) and the fact that s 11/(40M)).
Using the triangle inequality, we can bound the Newton decrement at y/ as
Ayy 1) S ((72))))-((()))1133100100))00000 + +
$ 22 vb()"))
-
(by 50 and & 1/(40.M4)
s 20 a)s (1+ 21+)((++)))) X(i Φ);
where the last inequality follows by 50) and 51
This completes the proof.
D.2 Proof of Lemma 6
Proof. By definition of (wir in Algorithm 1 have wt Wt-1 and w. wy Misersn
We show
properties 25
(26 and 27 using induction over y = 1,.... Newton-
Base case. We start with the base case; m Note that from the assumption in 22 and definition of wi, we have
|lm u (1 $ 1/(40Mb).
(52)
Now, by definition the Oracle Obees and the fact that H;-1 Ohees (wt-1) (see Algorithm I with = 0.001, we have
(1-0.001) ( ((4-1))
Hi-1 & (1 (4.00))V4((4-1))
(53)
Combining this with 52 implies property (25 for the base case. Furthermore, since w! wt-1 (by definition), (7 follows trivially for the base case.
Now, using that (.(w) (w) ngl_1 have
X(w), 0.)² A(w+-1, 22)²
(v (w/-) + 79. 2 2
+ 19:-11) gc-1 TV (2 2 (w/-1))t-)
< 224 V 2 ( V + 2
21(u--1, 2 )² 2n 9--1
V
(54)
$ 22 + +2 2/² (25000M))
(55)
where the last inequality follows by 22 and the fact that |1gt11 20 $ b. This shows prop- erty 23 for the base case. Thus, by Lemmal we have, for w argmin (x(w).
w wi [(=)(w!)) ||l! - wi Il= S A(w,, (1 (ad ( S 49Mo
(56)
Now, combining (53) with the fact that ||u,-1 - wi (7 = ||4--1 - w - $ 11/(40Mg))
(see (22) and Lemma
we obtain
31
(32 (
H & (2 &
(31 H
(57)
32
Plugging 57 into (66).
we get
l
He-1 $ W
11/440Mp).
(58)
21

---

Now, by the triangle inequality
get 11--1 - wi 1l.t.. $ |1t-1 w let 1/ - w/ |1
$ <1/(00mM,,
(59)
where in the last inequality used 22 and (58). Combining
59 with (53) and Lemma
( H411 < (5/4)V²
(60)
Combining Equations (60 and implies property 22 for the base of Induction. Furthermore, note that from Lemma
50 A(w,, 11) s
1
| wi (w)(
49
49
which shows property 266 for the base case.
Induction step. Now, assume that properties 23 show that these properties holds for m 1. From the hypothesis of induction, we have
26 and hold for m 1. We will
wwy" u H H
12M
which combined with (53 and Lemma Timplies
0.84V (u:") < H1-1 $ (2
(61)
Thus, by Lemma 5 (instantiated with 1/5) and the fact that Mwu"", Φ.) 1/(40M²) (by the induction hypothesis), we get that for प, mm+1 = "," H (oa"")
X( (wm-l T.)) & DMMM((w; (w,". Φ.)² + +.,cA(w.." +.) s (7/8) (b)).
Again, by Lemma with c= 1/5, we have
X(w m+1 p.)) s 20(1 + c)E+ (1+20 c) b)
15
25c
X(w 21) 1/(50M+).
(62)
16
m-1 N(w! T.) + 500s. Combining
By the induction hypothesis, we also have that X(w;" T.) s (16) this with 622. we get
15 m
Mw 21 s
X(w;, 2,) 500s.
(63)
16
This shows that (33 holds with m replaced by
Next, we show that 25 holds with m replaced by m + 1. Combining (62) with Lemma I implies
| m- w/ (()) $ A(w?++1 .b.)(11 MeN(w;"*) m+1 +.)) s 1/(49M²).
This, together with (60 gives
1wm++1 W/ |H,i s 1/(32Moo).
(64)
Combining (59 with 64 gives:
1 m+1 u w1-1ll S
12M
which proves that 25 holds with replaced by m + 1.
Next, show that 26 holds with m replaced by m 1. By 633 and Lemma T
we have
50
15 m
[ m+1 - w/ (o)))(())))) s
\(w Tb.) 240c.
49
16
15
1
240
(65)
49M
16
20M
22

---

where in the last inequality we used (55) and the bound on E in the lemma's 's statement. This shows that (26) holds with m replaced by
Next, we show that 27 holds with m replaced by m + 1. By plugging (60) into 665 p. we get
1
15
|w wil Ii.1
300s.
(66)
40Ms
16
On the other hand, by (54 we have
X(wt, 1t) s / v- (w)- (1r -0 (w--1) V ///g-11 (V2((((=)))))))))(())((())())"")
>(ww p,-1) n199- v-20(w)-))
Plugging this into 56 and using (55)
we get
50
|w: wel (1o() $
(A Aw P1-1) ( (((1))))
49
50
s (a + 1 (---
(67)
49
where the last inequality follows by (22). Combining (67 with (6T)
(instantiated with m = 1),
|w/ w ll H... s 2( n 20(w)1))
(68)
Now, by 666
688 and the triangle inequality, we have
1
15
w w/ get1 H 22199-ills 20((--1)
+500s 20.
40MB
16
Via another triangle inequality, we get
1
15
[ witt1 He-1 |wa-1 -1--1 H1-1 $ 2nl 9r- 1001111000
40.
16
+500 + 2a.
This shows that 27 holds with replaced by 1. Finally, combining (60) with (6) implies
J v2 v (w)"),
which completes the proof.
E
Helper Lemmas
Lemma 8 (Bounding norm of the Newton step). Let K. and H e R.dxd be such that (1
c)) H < (yy) Then, for h == bHy), we have
[ S (+()))--000)
Proof. We can write
[bllve0()) =1
= =
1/2 -24
(x)).
(69)
For the middle matrix v² 1/2 "ー
1/2
we have that
v 2 1/2 "1""""
1/2 & 1-c 1
I+c
since (1-c)v20(1) 4 (1 F2 by assumption. Plugging this back into 69 we get
|1|lv20())
Lemma - A
are symmetric matrices and PSD, then xT Ay s | Blly B.
23


Reviews:
[{"review_id": "0fFsZPbwch", "reviewer": "Reviewer_WCK3", "summary": "This paper proposes a \"projection-free\" algorithm for online convex optimization. The proposed algorithm adopts a self-concordant barrier of the constraint set as the regularizer, automatically ensuring the feasibility of the actions. The proposed algorithm only requires computing the inverse of an approximate Hessian at some rounds, instead of all rounds, achieving a small overall complexity when, e.g., the constraint set is a polytope. \n\n---\n\nThe authors have addressed my questions. I keep the original rating.", "questions": "Please address the weaknesses.", "limitations": "This is a theory paper. The assumptions are explicitly stated. Other possible issues I have noticed have been pointed out in the weaknesses block.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The algorithm is new and the analysis is non-trivial. \n2. The algorithm achieves the currently best regret performance for online convex optimization on a polytope.", "weaknesses": "1. **Computation of approximate gradient and Hessian.** I wonder how reasonable the error tolerances in the definitions of the approximate gradient and Hessian are, regarding that the Hessian inverse can have arbitrarily small eigenvalues in general. Can the approximate gradient and Hessian easily computed in general? \n2. **Explanations about complexity claims.** The claim that the per-round complexity of the algorithm is cheaper than that of the linear optimization oracle and the complexity bound in Corollary 1 need some explanations. \n3. **Inconsistent names.** It is claimed that the Lewis-Weights barrier will be used in Section 1 and the title of Section 4, but Ln. 226 says the barrier is called the Lee-Sidford barrier. \n4. **Presentation of Algorithm 1.** In Ln. 12--14, $H_{t + 1}$ is not specified. \n5. **Typos.** \n    - Ln. 160: \"[zm:cite]\"\n    - Ln. 188: an -> and\n    - Ln. 189: turning -> tuning\n    - Ln. 190: \"additional assumptions on the sequence of losses.\": incomplete sentence. \n    - Ln. 199: if -> of\n    - Ln. 232: $\\tilde{O} (1)$ is not an appropriate use of the notation. \n    - Ln. 299: \"in the sense of (3) *and (3)*\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for you positive review and helpful suggestions.\n\n**\"I wonder how reasonable the error tolerances in the definitions of the approximate gradient and Hessian are…\"**\nTo get a sense of this, let’s look at the case of a polytope in $\\mathbb{R}^d$ with $m$ constraints. Here, we want to use the LS barrier (see Section 4) as it gives a regret bound that is independent of the number of constraints $m$ (this would not be the case with the standard log-barrier). When using the LS barrier, results in [Lee and Sidford 2019] imply that we have \n- $\\mathcal{C}^{\\texttt{grad}}_{\\varepsilon}\\leq \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\cdot \\log (\\varepsilon^{-1}))$, and\n- $\\mathcal{C}^{\\texttt{hess}}_{\\varepsilon} = \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\sqrt{d} \\cdot  \\log (\\varepsilon^{-1}))$, \n\nwhere $\\mathcal{C}^{\\texttt{sys}}$ is the computational cost of solving a linear system of the form $A^\\top \\text{diag}(v) A x = y$, for vectors $v\\in \\mathbb{R}^{d}_{\\geq 0}$ and $y\\in \\mathbb{R}^d$; here $A$ represents the constraint matrix of the polytope. So when using the LS barrier, the computational efficiency is directly related to how efficiently the linear system can be solved. In the worst-case, the linear-system solve cost is $O(m d^{\\omega -1})$, where $\\omega$ is the exponent of matrix multiplication, but in many practical cases, the cost is much smaller.\n\nWe note that if a linear optimization oracle (which is typically used by other projection-free algorithms) is implemented via an interior point method, then the state-of-the-art approach would require $\\sqrt{d}$ linear-system solves of the type described in the previous paragraph (see [Lee and Sidford 2019]). This means that our algorithm can be a factor $\\sqrt{d}$ faster than linear-optimization-based projection-free algorithms (because our algorithm only requires $\\widetilde{O}(1)$ such linear-system solves per round). We will add details on this in the revision (together with clarifications for the complexity in Corollary 1).\n\n**“The claim that the per-round complexity of the algorithm is cheaper than that of the linear optimization oracle”**\nPlease see previous paragraph (we will add details in the revision).\n\n**“Inconsistent names” + “resentation of Algorithm 1. In Ln. 12--14, $H_{t+1}$ is not specified.”**\nThese are typos that we will fix. Thank you for pointing them out.\n\n**References:**\n\nYin Tat Lee and Aaron Sidford. \"Solving linear programs with sqrt (rank) linear system solves.\" arXiv preprint arXiv:1910.08033 (2019)."}, {"review_id": "kLtamaTxrQ", "reviewer": "Reviewer_kmvY", "summary": "This paper proposes new projection-free algorithms for online convex optimization over a convex domaim $\\mathcal{K}$. \nSpecifically, this paper proposes efficient Newton iterations to obtain projection-free online convex optimization.", "questions": "no", "limitations": "no", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper proposes an efficient online Newton method which is computation efficient.", "weaknesses": "This paper seems only using existing method to the online Newton. Though the author claims that unlike the setting of [26], where it is possible to add quadratic terms to the barrier for additional stability, in our setting, we cannot do that wihout sacrificing performance in terms of reget, we could not find any theoretical hardness in this paper to overcome this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n**“This paper seems only using existing method to the online Newton.”**\nOur algorithm does apply novel techniques to achieve the desired regret guarantee in the general OCO setting. In fact, applying existing techniques such as those in [Mhammedi and Gatmiry 2023] fails for two reasons:\nThe first reason, as you already mentioned, is that we cannot add quadratic terms as in [Mhammedi and Gatmiry 2023] since this would lead to a suboptimal regret in the OCO setting. These terms confer stability to the iterates of their algorithm, and they are able to add them without sacrificing performance because they consider the online exp-concave optimization setting. One novelty of our algorithm is in the choice of regularizer, which ensures stability without any quadratic terms.\nStability aside, the other issue is that their algorithm performs Taylor expansions to approximate Hessian matrices, which are required to compute the Newton iterates. Note that these Taylor expansions are only computationally efficient when the feasible set is a Euclidean ball, and so this does not apply to our OCO setting with general convex sets. To overcome this issue, we replace Taylor expansions by multiple Newton steps per round (see Lines 6-9 of Algorithm 1), and we show (via a non-trivial analysis) that doing this essentially leads to the same guarantee as one would get using Taylor expansions. As far as we know, this approach of taking multiple Newton steps per round in novel.  \n\n\n**References:**\n\nZakaria Mhammedi and Khashayar Gatmiry. \"Quasi-newton steps for efficient online exp-concave optimization.\" In The Thirty Sixth Annual Conference on Learning Theory, pp. 4473-4503. PMLR, 2023.\n"}, {"review_id": "QjDc0jN29I", "reviewer": "Reviewer_eL2Y", "summary": "This paper introduces new projection-free algorithms for online convex optimization, which utilize Newton iterates with a self-concordant barrier for the target set. The authors establish a state-of-the-art regret bound for this algorithm.", "questions": "See above.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths And Weaknesses:\nThe paper presents a new approach for projection-free online convex optimization. The main advantage of the proposed algorithm is that it only requires computing a full inverse of the Hessian in a vanishing O(1/\\sqrt{T}) fraction of each round. Additionally, for the case of a polytope with m constraints, their method exhibits lower per-iteration computational cost compared to linear optimization. Furthermore, their method achieves a better regret bound than existing works in this specific scenario.\n\nHowever, I have some concerns that I would like the authors to address:\n\nIt would be beneficial to have a comparison of the gradient complexity between this method and other related works. Additionally, it would be valuable to provide further analysis of the computational complexity mentioned in line 208. Specifically, it would be helpful to clarify under which circumstances the gradient complexity dominates the Hessian complexity, and vice versa.\n\nRegarding the computation complexity mentioned in line 208, there is a coefficient M_{\\Phi}. In some cases, M_{\\Phi} can be significantly larger than d. For instance, when considering a polytope with m constraints, M_{\\Phi} is related to m, and m can be exponential in d.\n\nIn Theorem 6, the authors assume that the local norm of g_t is less than C for all w_t. This assumption is not trivial, as the Hessian of a self-concordant function is typically unbounded.", "weaknesses": "See above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\n**“It would be beneficial to have a comparison of the gradient complexity between this method and other related works.”** \nIn previous works, the gradient complexity refers to the number of gradient computations of the losses. Our algorithm only requires a single gradient computation of the loss at each step, which is on par with previous approaches. We suspect that you are referring to $\\mathcal{C}^{\\texttt{grad}}$. We answer this next.\n\n**“Additionally, it would be valuable to provide further analysis of the computational complexity mentioned in line 208. Specifically, it would be helpful to clarify under which circumstances the gradient complexity dominates the Hessian complexity, and vice versa.…”**\nThe Hessian cost $\\mathcal{C}^{\\texttt{hess}}$ will typically dominate the gradient cost $\\mathcal{C}^{\\texttt{grad}}$ for the barriers of essentially all common convex sets used in practice. To get a sense of this, let’s look at the case of a polytope in $\\mathbb{R}^d$ with $m$ constraints (these details will be added in the revision). When using a standard log-barrier $\\Phi$, we have $M_{\\Phi}=1$, $\\mathcal{C}^{\\texttt{grad}}\\leq O(md)$, and $\\mathcal{C}^{\\texttt{hess}} = O(m d^{\\omega -1})$ (these are the costs of computing the gradients and Hessians exactly), where $\\omega$ is the exponent of matrix multiplication. Now, if we use the LS barrier as in Section 4 (which confers benefits in terms of the regret), results in [Lee and Sidford 2019] imply that we have \n- $M_{\\Phi}=O(\\log(m)^{2/5})$;\n- $\\mathcal{C}^{\\texttt{grad}}_{\\varepsilon}\\leq \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\cdot \\log(\\varepsilon^{-1}))$; and \n- $\\mathcal{C}^{\\texttt{hess}}_{\\varepsilon} = \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\sqrt{d} \\cdot \\log(\\varepsilon^{-1}))$,\n\n where $\\mathcal{C}^{{\\texttt{sys}}}$ is the computational cost of solving a linear system of the form $A^\\top \\text{diag}(v) A x = y$, for vectors $v\\in \\mathbb{R}^{d}_{\\geq 0}$ and $y\\in \\mathbb{R}^d$; here $A$ represents the constraint matrix of the polytope. So for both the LS- and log-barrier, the cost of approximate Hessian evalution dominates that of (approximate) gradient evaluation. We will add details on this in the revision.\n\n**“Regarding the computation complexity mentioned in line 208, there is a coefficient M_{\\Phi}...”**\nAs we mentioned in the previous paragraph (see also display after Line 229), the constant $M_\\Phi$ for the LS barrier [resp. Log-barrier] is such that $M_{\\Phi}=O(\\log(m)^{2/5})$ [resp. $M_{\\Phi}=1$]. And so for the application to polytopes, $M_{\\Phi}$ is at most logarithmic in $m$ (and so at most polynomial in $d$ when $m$ is exponential in $d$). Note that $M_{\\Phi}$ is not to be confused with the parameter $\\nu$ of the self-concordant barrier (see Definition 2), which is the one that may scale polynomially in $m$ depending on the choice of the barrier. In fact, for the log-barrier, we have $\\nu =m$, and for the LS barrier we have $\\nu =d$; having $\\nu$ being independent of $m$ is precisely the appeal of using the LS barrier.  \n     \n**“In Theorem 6, the authors assume that the local norm of g_t is less than C for all w_t. This assumption is not trivial, as the Hessian of a self-concordant function is typically unbounded.”**\n\nNote that the assumption we make involves the inverse of the Hessian, i.e. we assume $\\Vert g_t\\rVert_{\\nabla^{-2}\\Phi(w_t)}$ is bounded. \n\nAnd so large Hessian eigenvalues only make things better here. In general, you should think of this assumption as being much weaker than the standard Lipschitzness assumption in OCO. In fact, there are many settings where the losses are non-lipshitz, i.e. where $\\Vert g_t\\rVert$ is unbounded, but the local norm $\\Vert g_t\\rVert_{\\nabla^{-2}\\Phi(w_t)}$ is. This includes, for example, the setting of linear regression with the log-loss (see e.g. Section 6 and Lemma 7 in [Rakhlin and Sridharan 2015]), and the classical portfolio selection setting (see e.g. [Luo et al. 2018]). There are other settings where the local gradient norms can be much smaller that their standard Euclidean counterparts; see [Abernethy et al. 2012] for a discussion.      \n\n\n\n**References:**\n\nJacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. \"Interior-point methods for full-information and bandit online learning.\" IEEE Transactions on Information Theory 58, no. 7 (2012): 4164-4175.\n\nAlexander Rakhlin, and Karthik Sridharan. \"Sequential probability assignment with binary alphabets and large classes of experts.\" arXiv preprint arXiv:1501.07340 (2015).\n\nHaipeng Luo, Chen-Yu Wei, and Kai Zheng. \"Efficient online portfolio with logarithmic regret.\" Advances in neural information processing systems 31 (2018).\n\nYin Tat Lee and Aaron Sidford. \"Solving linear programs with sqrt (rank) linear system solves.\" arXiv preprint arXiv:1910.08033 (2019).\n"}, {"review_id": "g6JNcbUrTj", "reviewer": "Reviewer_y1W5", "summary": "Building upon recent progress in projection-free OCO, this paper presents a new IPM-like algorithm attaining optimal regret with improved efficiency, which calculates Hessians only $O(\\sqrt{T})$ number of times. The algorithm assumes access to a self-concordant function by gradient oracles and Hessian oracles.", "questions": "Can you elaborate more on how to obtain Corollary 1?", "limitations": "There is an author's comment in line 160, which I suspect violates the double-blind rule. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper makes a solid contribution on more efficient projection-free OCO, which admits optimal regret and better efficiency at the same time. Moreover, it also opens a new avenue of using IPM-like methods for projection-free OCO, besides classic LOO-based methods and SO/MO-based approaches developed recently.", "weaknesses": "There is an author's comment in line 160, which I suspect violates the double-blind rule. Though the contents are interesting, I regret to reject the paper for this reason.\n\nI think the paper can benefit from a detailed comparison with the ONS algorithm in HAK07.\n\nThere are many typos, here are some that I caught:\n\nLine 12: expansive - expensive (it appears multiple places)\n\nLine 39: insure - ensure\n\nLine 129: interior - interior of\n\nLine 13 in the alg box: there should be another line of Set $H_{t+1}=H_t$?\n\n---Update--- \n\nAfter a discussion with the AC, the comment is considered as a typo and I changed the score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review.\n\n**“There is an author's comment in line 160, which I suspect violates the double-blind rule...”**\nUnfortunately, this was a typo that we only spotted shortly after the submission deadline.  \n\n**“I think the paper can benefit from a detailed comparison with the ONS algorithm in HAK07.”** \nWe note that the ONS algorithm in [Hazan et al. 2007] is an algorithm for online exp-concave optimization and is not intended for use in the OCO setting we consider in this paper; naively applying ONS to OCO would lead to suboptimal (even linear) regret. This is because ONS  uses certain quadratic terms (designed for the exp-concave setting) in the regularizer that can lead to a linear regret in the OCO setting. Furthermore, the ONS algorithm requires generalized projections at each iteration which is precisely what we are trying to avoid as these can be computationally costly; see discussion in [Garber and Kretzu 2023].\n\n**“There are many typos, here are some that I caught”**\nThe typos will be fixed in the revision. And you are correct, there should be $H_{t+1}=H_t$ on line 13 of the algo (we have already spotted this and fixed it).\n\n\n**“Can you elaborate more on how to obtain Corollary 1?”**\nWhen using the LS barrier, results in [Lee and Sidford 2019] imply that we have \n- $\\mathcal{C}^{\\texttt{grad}}_{\\varepsilon}\\leq \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\cdot \\log (\\varepsilon^{-1}))$; and \n- $\\mathcal{C}^{\\texttt{hess}}_{\\varepsilon} = \\widetilde{O}(\\mathcal{C}^{\\texttt{sys}} \\sqrt{d} \\cdot  \\log (\\varepsilon^{-1}))$, \n\nwhere $\\mathcal{C}^{{\\texttt{sys}}}$ is the computational cost of solving a linear system of the form $A^\\top \\text{diag}(v) A x = y$, for vectors $v\\in \\mathbb{R}^{d}_{\\geq 0}$ and $y\\in \\mathbb{R}^d$; here $A$ represents the constraint matrix of the polytope. In the worst-case, the linear-system solve cost is $O(m d^{\\omega -1})$ (i.e. $\\mathcal{C}^{{\\texttt{sys}}}\\leq O(m d^{\\omega -1})$), where $\\omega$ is the exponent of matrix multiplication. Plugging these bounds into the computational complexity in Theorem 6 should imply the claimed complexity in Corollary 1. We will add these details in the revision.\n\n**References:**\n\nElad Hazan, Amit Agarwal, and Satyen Kale. \"Logarithmic regret algorithms for online convex optimization.\" Machine Learning 69 (2007): 169-192.\n\nYin Tat Lee, and Aaron Sidford. \"Solving linear programs with sqrt (rank) linear system solves.\" arXiv preprint arXiv:1910.08033 (2019).\n\nDan Garber and Ben Kretzu. \"Projection-free Online Exp-concave Optimization.\" arXiv preprint arXiv:2302.04859 (2023).\n"}]

Author rebuttal:

Meta-review: There is an overall consensus among reviewers that this is an interesting submission that should be accepted, which is also my evaluation.
Decision: Accept (poster)