Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness
Authors: Chung-En Tsai
Ying-Ting Lin
Yen-Huan Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Online portfolio selection
small-loss bound
gradual-variation bound
second-order bound
optimistic FTRL with self-concordant regularizers
TL;DR: This work introduces the first small-loss and gradual-variation regret bounds for online portfolio selection, marking the first instances of data-dependent bounds for online convex optimization with non-Lipschitz, non-smooth losses.

Abstract: This work introduces the first small-loss and gradual-variation regret bounds for online portfolio selection, marking the first instances of data-dependent bounds for online convex optimization with non-Lipschitz, non-smooth losses. 
The algorithms we propose exhibit sublinear regret rates in the worst cases and achieve logarithmic regrets when the data is "easy," with per-round time almost linear in the number of investment alternatives. 
The regret bounds are derived using novel smoothness characterizations of the logarithmic loss, a local norm-based analysis of following the regularized leader (FTRL) with self-concordant regularizers, which are not necessarily barriers, and an implicit variant of optimistic FTRL with the log-barrier.

Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness
Chung-En Tsai
Department of Computer Science and Information Engineering National Taiwan University
CHUNGENTSAI @ NTU.EDU.TW
Ying-Ting Lin
Department of Computer Science and Information Engineering National Taiwan University R08922060 ETU.ED
Yen-Huan Li
Department of Computer Science and Information Engineering
Department of Mathematics
Center for Quantum Science and Engineering
National Taiwan University
YENHUAN. L CSIE.NTU.EDU.T
Abstract
This work introduces the first small-loss and gradual-variatien regret bounds for online portfolio selection, marking the first instances of data-dependent bounds for online convex optimization with non-Lipschitz, non-smooth losses. The algorithms propose exhibit sublinear regret rates in the worst cases and achieve logarithmic regrets when the data is "easy," with per-round time almost linear in the number of investment alternatives. The regret bounds are derived using novel smoothness characterizations of the logarithmic loss, local norm- norm-based analysis of following the regularized leader (FTRL) with celf-concordant regularizers, which not necessarily barriers, and an implicit variant of optimistic FTRL with the log-barrier.
Introduction
Designing an optimal algorithm for online portfolio selection (OPS), with respect to both regret and computational efficiency. has remained significant open problem in online convex optimization for over three d OPS models long-term investment as multi-round game between two strategic players the market and the INVESTOR- -eeesee avoiding the need for hard-to-verify verify probabilistic models for the market. In addition to its implications for robust long-term investment, OPS is also a generalization of probability forecasting and universal data compression [5].
The primary challenge OPS stems from the absence of Lipschitzness and smoothness the loss functions. Consequently, standard online convex optimization algorithms do not directly apply. For example, standard analyses of online mirror descent (OMD) and following the regularized leader (FTRL) bound the regret by the sum of the norms of the gradients (see, e.g., the lecture notes by
Readers are referred to recent papers, such as those by Luo et al. [22], van Erven et al. [35], Mhammedi and Rakhlin [24], Zimmert et al. [38], and Jézéquel et al. [17], for reviews on OPS.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Orabona [28] and Hazan [12]). In OPS, the loss functions are not Lipschitz, so these analyses do not yield a sub-linear regret rate. Without Lipschitzness, the self- bounding property of smooth functions enables the derivation of a "small-loss" regret bound for smooth loss functions [33]. However, the loss functions in OPS are not smooth either.
The optimal regret rate of OPS is known to be Ood T), where d and T denote the number of investment alternatives and number of rounds, respectively. This optimal rate is achieved by Universal Portfolio [9, 10]. Nevertheless, the current best implementation of Universal Portfolio requires O(dTT14) per-round time [20], too long for the algorithm to be practical. Subsequent OPS algorithms can be classified into two categories.
Algorithms in the first category exhibit near-optimal (d) per-round time and moderate OVVdT) regret rates. This category includes the barrier subgradient method [26], Soft- Bayes [30], and LB-OMD [34].
Algorithms in the second category exhibit much faster (ppoly(d) polylog(T)) regret rates with much longer ((poly(d) d) poly(T)) per-round time, which is. however, significantly shorter than the per-round time of Universal Portfolio. This category includes ADA- BARRONS [22], PAE+DONS [24], BISONS [38], and VB-FTRL
The aforementioned results are worst-case and do not reflect how "easy" the data is. For instance, the price relatives of the investment alternatives remain constant over rounds, then a small regret is expected. Data- Data-dependent regret bounds refer to regret bounds that maintain acceptable rates in the worst case and much better rates when the data is easy. In this work, we consider three types of data-dependent bounds.
A small-loss bound bounds the regret by the cumulative loss of the best action in hindsight.
A gradual-variatie variation bound bounds the regret by the gradual variation (6) of certain charac- teristics of the loss functions, such the gradients and price relatives.
A second-order bound bounds the regret by the variance or other second-order statistics of certain characteristics of the loss functions, such as the gradients and price relatives.
Few studies have explored data-dependent bounds for OPS. These studies rely on the so-called no-junk-bonds assumption [2], requiring that the price relatives of all investment alternatives are bounded from below by a positive constant across all rounds. Given this assumption, it is easily verified that the losses in OPS become Lipschitz and smooth. Consequently, the result of Orabona al. [29] implies small-loss regret bound; Chiang et al. [8] established gradual-variee variiaan bound in the price relatives; and Hazan and Kale [14] proved a second-order bound also in the price relatives. These bounds are logarithmic in the number of rounds T in the worst cases and can be constant when the data is easy.
The no-junk-bonde assumption may not always hold. Hazan and Kale [14] raised the question of whether it is possible to eliminate this assumption. this work, we take the initial step towards addressing the question. Specifically, we prove Theorem 1.1.
Theorem 1.1. In the absence of the no-junk-bonee bonds assumption. two algorithms exist that pos- sess a pradual-variation bound and small-loss bound, respectively. Both algorithms attain Old polylog(T))) regret rates in the best cases and Ó regret in the worst cases, with (dd) per-rounde time.
Theorem 1.1 represents the first data-dependent bounds for OPS that do not require the jn-junk-bonds assumption. To the best of our knowledge, this also marks the first data-dependent bounds for online convex optimization with non-Lipschitz non-smooth losses. In the worst cases, Theorem 1.1 ensures that both algorithms can compete with the OPS algorithms of the first category mentioned above. In the best cases, both algorithms achieve near-optimal regret with a near-optimal per-round time, surpassing the OPS algorithms of the second category in terms of the computational efficiency. Table in Appendix A presents detailed summary of existing OPS algorithms in terms of the worst-case regrets, best-case regrets, and per-round time.
We also derived second-order regret bound by aggregating variant of optimistic FTRL with different learning rates. The interpretation of the result is not immediately clear. Therefore, we detail the result in Appendix I.
2

---

Technical Contributions.
The proof of Theorem 1.1 relies on several key technical breakthroughs:
Theorem 3.2 provides a general regret bound for optimistic FTRL with self-concordant regularizers, which may not be barriers, and time-varying learning rates. The bound generalizes those of Rakhlin and Sridharan [31] and Zimmert et al. [38, Appendix HJ and is of independent interest.
Existing results small-loss and gradual-variation bounds assume the loss functions are smooth, an assumption that does not hold in OPS. In Section 4, we present Lemma 4.3 and Lemma 4.7, which serve local-nome counterparts to the Lipschitz gradient condition and the self-bounding property of convex smooth functions, respectively.
To apply Theorem 3.2, the gradient estimates and iterates in optimistic FTRL must be computed concurrently. Consequently, we introduce Algorithm 2, a variant of optimistic FTRL with the log-barrie and validate its definition and time complexity.
The gradual-variation and small-loss bounds in Theorem 1.1 are achieved by two novel algorithms, Algorithm and Algorithm 4, respectively. Both are instances of Algorithm 2.
.N] by [N]. The sets of non- negative and strictly positive numbers are denoted by E, and R respectively. The i-th entry of a vector e E Id denoted by v(i). The probability simplex in R.d the set of entry-wise non-negative vectors of unit nn-rr,, is denoted by Aa. We often omit the subscript for convenience. The closure and relative interior of a set X' is denoted by cl X' and ri X, respectively. The nn-norm denoted by Il-ll,, The all-ones vector is denoted by For any two vectors u and v in IR their entry-wise product and division are denoted by u O v and u Ø v, respectively. For time-indexed vectors djy..., at E Rd, we denote the sum di ... + a₂ by di:t.
Notations. For any natural number N, we denote the set (1....,Ny
2 Related Works
2.1 Log-Barrier for Online Portfolio Selection
All algorithms we propose are instances of optimistic FTRL with the log-barrier regularizer. The first use of the log-barrier in OPS can be traced back to the barrier subgradient method proposed by Nesterov [26]. Later, Luo et al. [22] employed a hybrid regularizer, which incorporated the log-barrier, in the development of ADA-BARROW
This marked the first OPS algorithm with regret rate polylogarithmic in and an acceptable per-round time complexity of (dd-5T). Van Erven et al. [35] conjectured that FTRL with the barrberierr (LB-FTRL) achieves the optimal regret. The conjecture was recently refuted by Zimmert et al. [38], who established regret lower bound for LB-FTRL. Jézéquel al. [17] combined the log-barrier and volumetric barrier to develop VB-FTRL, the first algorithm with near-optimal regret and an acceptable per-round time complexity of ((PT). These regret bounds are worst-case and do not directly imply our results.
2.2 FTRL with Self-Concordant Regularizer
Abernethy et al. [1] showed that when the regularizer is chosen as self-concordant barrier of the constraint set, the regret of FTRL is bounded by the sum of dual local norms of the gradients. Rakhlin and Sridharan [31] generalized this result for optimistic FTRL.
The requirement for the regularizer to be a barrier is restrictive. For instance, while the log-barrier is self-concordant, it is not barrier of the probability simplex. To address this issue, van Erven et al. [35], Mhammedi and Rakhlin [24], and Jézéquel et al. [17] introduced an affine transformation such that, after the transformation, the log-barrier becomes a self-concordant barrier of the constraint set. Nonetheless, this reparametrization complicates the proofs.
Theorem 3.2 in this paper shows that optimistic FTRL with self-concordant regularizer, without the barrier requirement, still satisfies a regret bound similar to that by Rakhlin and Sridharan [31]. The proof of Theorem 3.2 aligns with the analyses by Mohri and Yang [25], McMahan [23], and Joulani et al. [19] of FTRL with optimism and adaptivity, as well as the local-norm based analysis by Zimmert al. [38, Appendix H].
In comparison, Theorem 3.2 generalizes the analysis of Zimmert et al. [38, Appendix H] for optimistic algorithms and vare-narying learning rates; Theorem 3.2 differs from the analyses of Mohri and Yang
3

---

[25], McMahan [23], and Joulani et al. [19] in that they require the regularizer to be strongly convex, whereas the log- log-barrier is not.
2.3 Data-Dependent Bounds
The following is a summary of relevant literature on the three types data-dependent bounds. For a more comprehensive review, readers may refer to, e.g., the lecture notes of Orabona [28].
Small-loss bounds, also known as L bounds, were first derived by Desa-Bianchi al. [6] for online gradient descent for quadratic losses. Exploiting the self-bounding property, Srebro al. [33] proved a small-loss bound for convex smooth losses. Orabona et [29] proved logarithmic small-loss bound when the loss functions are not only smooth but also Lipschitz and exp-concave.
Chiang et al. [8] derived the first gradual-variation bound, bounding the regret by the variation of the gradients over the rounds. Rakhlin and Sridharan [31, 32] interpreted the algorithm proposed by Chiang et al. [8] as optimistic online mirror descent and also proposed optimistic FTRL with self-concordant barrier regularizers. Joulani et al. [18] established gradual- gradual-variation bound for optimistic FTRL.
Bisa--Binchi et al. [7] initiated the study of second-order regret bounds. Hazan and Kale [13] derived regret bound characterized by the empirical variance of loss vectors for online linear optimization. In the presence of the no-junk-bone assumption, Hazan and Kale [14] proved regret bound for OPS characterized by the empirical variance of price relatives.
Except for those for specific loss functions, these data-dependent bounds assume either smoothness or Lipschitzness of the loss functions. Nevertheless, both assumptions are violated in OPS.
Recently, Hu et al. [16] established small-loss and gradual-variatin variation bounds in the context of Rieman- nian online convex optimization. We are unaware of any Riemannian structure on the probability simplex that would render the loss functions in OPS geodesically convex and geodesically smooth. For instance, Appendix B shows that the loss functions in OPS are not geodesically convex on the Hessian manifold induced by the log-barrier.
3 Analysis of Optimistic FTRL with Self-Concordant Regularizers
This section presents Theorem 3.2, a general regret bound for optimistic FTRL with regularizers that self-concordant but not necessarily barriers. This regret bound forms the basis for the analyses in the remainder of the paper and, as detailed in Section 2.2, generalizes the results of Rakhlin and Sridharan [31] and Zimmert al. [38, Appendix H].
Consider the following online linear optimization problem involving two players, LEARNER and REALITY. Let X C Ra be closed convex set. At the 1-th round,
first, LEARNER announces E X;
then, REALITY announces a vector U/ E Rd:
finally, LEARNER suffers a loss given by (ve, 21)-
For any given time horizon N, the regret (T(x) defined as the difference between the cumulative loss of LEARNER and that yielded by the action x E X; that is,
T
(x) = Σ (v),
(v2,
x),
Vr E
The objective of LEARNER is achieve a small regret against all x E X. Algorithm I provides strategy for LEARNER, called optimistic FTRL.
We focus the case where the regularizer yp is self-concordant function.
Definition 3.1 (Self-concordant functions), closed convex function yp : IR. (-o0, oo] with an open domain dom is said to be M M-self--onccordan if it is three-times continuously differentiable on dom yp and
1D*((())(u, u]] S 2M (u, (ip(z)u) 3/2
Vr E dom p, E..

---

Algorithm Optimistic FTRL for Online Linear Optimization
Input: A sequence of learning rates {nt
R++.
1: é1 0.
2: #1 E arg min % "oo' s2(x).
3: for all E do
4: Announce and receive bt E IRd.
5: Choose an estimate Ut+1 for vt+1,
6: 2++1 f- arg minzex (Via, x) + (0) + ne nt'p(())
7: end for
Suppose that V is positive definite at point z. The associated local and dual local norms are given by ||e|| V(u, V2i(z)u) and ||ull,,, == (ve V (=)(()) respectively. Define w(t)
t - log + t).
Theorem 3.2. Let be an --seef-concorrlan function such that X contained the closure of dom y and min (p(x)= O. Suppose that V² is positive definite for all x & n dom ip and the sequence of learning rates {Nt is non- ton-increasing. Then, Algorithm satisfies
RT(x)) < ((x))
Σ t=1
(va 01 Ft Iet1)
12-1 w (M]la se+1 se+tllaa)
1
9T
If in addition, Th 11-1 Ge Iell
s 1/(2M) for all t e N, then Algorithm 1 satisfies
f(x) 7f
T
Rr(x) <
11e Bell
The proof of Theorem 3.2 is deferred to Appendix It worth noting that the crux of the proof lies in Lemma D.1; the remaining steps follow standard procedure.
4
"Smoothness" in Online Portfolio Selection
4.1 Online Portfolio Selection
Online Portfolio Selection (OPS) is multi-round game between players, say INVESTOR and MARKET. Suppose there are investment alternatives. A portfolio of INVESTOR is represented by vector in the probability simplex in Rd which indicates the distribution of INVESTOR's 's wealth among the d investment alternatives. The price relatives of the investment alternatives at the (-th round are listed vector a, R4.
The game has T' rounds. At the t-th round,
first, INVESTOR announces portfolio 2; A C Rdd
then, MARKET announces the price relatives 0; E TRQ
finally, INVESTOR suffers a loss given by fe(It), where the loss function fa is defined as
ft(x) = log (ae, 2).
The objective of INVESTOR is achieve small regret against all portfolios A, defined as²
T Rx(x)= f((x)) f(.)) Vx An
T
n dom fc-
In the context of OPS, the regret corresponds the logarithm of the ratio between the wealth growth rate of INVESTOR and that yielded by the constant rebalanced portfolio represented by E A. Assumption 1. The vector of price relatives a; is non-zero and satisfies ||a,]] ll = 1 for all N.
Becaase the vectors have entries, general, dom fo does not contain A.

---

The assumption on ||ae|lco does not restrict the problem's applicability. If the assumption does not hold, then we can consider another OPS game with a, replaced by â, az/||ael and develop algorithms and define the regret with respect to 0z. It is obvious that the regret values defined with de and 0 are the same.
The following observation, readily verified by direct calculation, will be useful in the proofs.
Lemma 4.1. The vector x (- f(())) lies & for all x E Eri Ari and E N.
4.2 Log-Barrier
Standard online convex optimization algorithms, such as those in the lecture notes by Orabona [28] and Hazan [12), assume that the loss functions are either Lipschitz or smooth.
Definition 4.2 (Lipschitzness and smoothness). A function is said to be Lipschitz with respect to norm II-II if
Iv(()) -0()) - Llyy ælI, for some > O. It is said be smooth with respect to the norm ||-11 if
vz, dom
[V - Vx(x)l,, S L'lly - xll. for some L' 0, where |I-1l, denotes the dual norm.
Vz, y E dom V
Given that (ax, x) can be arbitrarily close to zero on A n dom Sa in OPS, is well known that there does exist Lipschitz parameter L nor smoothness parameter L' for all loss functions fr- Therefore, standard online convex optimization algorithms do not directly apply.
We define the Nog-barrier as²
h(x) = -d log d log xi),
((x())...., x(d) E IR
It is easily checked that the local and dual local norms associated with the log-barrier are given by
|w|l_ == I| @ xrll: ||ulla,-
I|u @ xrl2--
In the remainder of the paper, we will only consider this pair of local and dual local norms.
Note that Lipschitzness implies boundedness of the gradient. The following observation motivates the use of the log-barrier in OPS, showing that the gradients OPS are bounded with respect the dual local norms defined by the log-barriet
Lemma 4.3. holds that [x))ll,,,. I 1 for all x and t N.
similar result was proved by van Erven al. [35, (2)]. We provide a proof of Lemma 4.3 in Section E for completeness.
The following fact will be useful.
Lemma 4.4 (Nesterov [27, Example 5.3.1 and Theorem 5.3.2]). The log-barrier h and loss functions ft in OPS are both 1-self-concortant.
4.3 "Smoothness" in OPS
Existing results on small-loss and gradual- variation bounds require the loss functions to be smooth. For example, Chiang al. [8] exploited the definition of smoothness (1) derive gradual-variation bounds; Srebro et al. [33] and Orabona et al. [29] used the "self-bounding property," consequence of smoothness, to derive small-loss bounds.
variation
Lemma 4.5 (Self-bounding property [33, Lemma 2.1]). Let f Rd + IR be an L-smooth convex function with dom f = Rdd Then, |/ f=))l < 2L(f(x) - min f(y)) for all x E Rdd.
While the loss functions in OPS are not smooth, provide two smoothness characterizations of the loss functions in OPS. The first is analogous to the definition of smoothness (1).
'The definition here slightly differs from those typically seen in the literature with an additional ld d term. The additional term helps us remove log d term in the regret bounds.

---

Lemma 4.6. Let f(x) = - log (a. for some E RQ. Under Assumption I on the vector
I Vf(x)) (y o 1/())ll2 I 4mmm { vlle. || v1ly} y
where @ denotes the entrywise product and |1-112 and Il-lly are the local-norms defined by the log- burrier (3).
The second smoothness characterization is analogous the self-bounding property (Lemma 4.5). For any x E ri and v E RRd, define
2 2 =/=1>011)
(v)
E
where r(i) and vii) denote the i-th entries of x and v, respectively.
Lemma 4.7. Let [(x) = - log (a, x) for some a E I24. Then, under Assumption I on the vector it holds that
[V) an (VS(z)) S <4f(x), Vx Erii,
where the notation e denotes the all-ones vector and Ill,, denotes the dual local norm defined by the log-bard log-barrier (3).
Remark 4.8. The value (v) is indeed chosen to minimize ||0 + oell over all E R.
The proof's of Lemma 4.6 and Lemma 4.7 are deferred to Appendix E.
5 LB-FTRL with Mulippicative-Cradien Optimism
Define 9: = V (xzz) By the convexity of the loss functions, OPS can be reduced to an online linear optimization problem described in Section 3 with 1 = It and X' being the probability simplex A. Set the regularizer regret guarantee in Theorem 3.2 to valid, it remains to ensure that ğr, the estimate gt, is selected to satisfy 77-1 11 gel , < 1/2 for all t. However, Tt, which defines the dual local norm, depends on 9t in Algorithm 1, selecting such Ii is non-trivial.
the fog-barrier (2) in Optimistic FTRL (Algorithm 1). By Lemma 4.4, for
To address this issue, we introduce Algorithm 2. This algorithm simultancously computes the next iterate 1++1 and the gradient estimate Ôi+1 by solving system of nonlinear equations (5). As we estimate It-1 ① gt++1 instead of st+1, we call the algorithm LB-FTRL with Multipicatiie-Grrann Gradieent Optimism. Here, LB indicates that the algorithm adopts the log- log-barrier as the regularizer.
Algorithm 2 LB-FTRL with aaaliplicative-GGadienn Optimism for OPS Input: A sequence of learning rates {n- } C R++.
1: M(x) == log Σd= log (t))
2: Φ1 0.
3: & arg min Too h(x).
4: for all it N do
5: Announce and receive di.
6: 9: ;= Vf(()..
7: Choose an estimate P++1 E Rd for F141 9t+1.
8: Compute I++1 and - such that
114 0t+1 Pt+1,
(5)
[141 arg min (g),.z) x) + (0)41, + m + h((x).
9: end for
By the definitions the dual local norm (3) and pt (5), we write
llg: - gr Il... = ||,, 3 ge x, 3 gellz = ||,, @ 9: Pelly

---

It suffices to choose Pt such that 7/-1 x @ prll2 I 1/2. Indeed, Algorithm and Algorithm 4 correspond choosing Pt 2t-1 g: -
and Pt 0, respectively. Algorithm 5 in Appendix I
corresponds to choosing p: (1/1o= Σー 7 1 + gr.
Theorem 5.1 guarantees that 2a and Ør well-defined and can be efficiently computed. Its proof and the computational details can be found in Appendix F.I.
Theorem 5.1. If n:P++1 E [-1,00] 0j* then the system of nonlinear equations (5) has solution. The solution can be computed in O(d) time.
Algorithm 2 corresponds to Algorithm with 2/2 = gt. 0; = p: 2 It. and poxx) = h(x). Corollary 5.2 then follows from Theorem 3.2. Its proof can be found in Appendix F.2.
Corollary 5.2. Assume that the sequence {mc} is non-increasing and pt E (-00, 0f* for allll e E. Under Assumption 1, Algorithm 2 satisfies
dlogg
T
RT(x) S
+
Σ t=1
(gt Pt 2 It, r++1)
w(1 xet1 + 2,
Tpr
In addition, for any sequence of vectors {ur such that Th mh- 11( + us) xt prllz S 1/2 and (4, 21 - I2+1) = 0 for all E N, Algorithm satisfies
dlogg T
(x) S
Σ 7- + O 0 x +
Remark 5.3. The vectors un are deliberately introduced derive a small-loss bound for OPS.
Data-Dependent Bounds for OPS
6.1 Gradual-Variation Bound
We define the gradual variation
T V/= Σ Vf
T
max [f((z) mEA
Vfi-1
(6)
where II- denotes the dual local norm associated with the log-barrier. The definition is local-norm analog the existing one [8, 18], defined Ei= m fe() fx- for fixed norm ||. Regarding Lemma 4.3, our definition appears to be a natural extension.
In this sub-section, introduce Algorithm 3, LB-FTRL with Last- Mest--Muulllcciieeiieeee and Theorem 6.1, which provides the first gradual- variation bound for OPS. Algorithm 3 is an instance of Algorithm 2 with P1 0 and p. xz-- @ 9t-1 for 2. Note that the learning rates specified in Theorem 6.1 do not require the knowledge of Vy in advance and can be computed on the fly.
Optimism,
The proof of Theorem 6.1 can be found in Appendix G.
Theorem 6.1. Let Tju 17 1/(16/2) and m /d/2d12d+2+ V,, for t 2 Then, Algo- rithm 3 satisfies
RT(œ) < (log T + 8) /V)//V//+ 512 + log T 128v2d, VT
By the definition of the dual local norm (3) and Lemma 4.1,
VT
| C Vi((ae1)) x1-1 o Vi 2(T 1).
As result, the worst-case regret of Algorithm 3 is O @(vdd dT log T), comparable to the regret bounds of the barrier subgradient method [26), Soft-Bayes [30], and LB-OMD [34] up to logarithmic factors. the other hand, if the price relatives remain constant over rounds, then Vr 0 and Ry Oddlog

---

Algorithm 3 LB-FTRL with Last- Last-Multphiiativ--rradee Optimism for OPS
Input: sequence of learning rates {n. C R.+..
l(x)) -d E log)(1).
2: pl +.
3: 21 &- arrg minggi 10 h(x).
4: for all t t N do
5: Announce 2t and receive ar.
6: - (f(())).
7: Pt-1 t 24 ④ gr.
8: Compute rt+1 and 0t-1 such that
F4p1 0t+1 pt+1,
[141 arg min
(g 2) + (0++1, + th h(x)).
9: end for
Time Complexity. The vectors 9: and Pt-1, 1, as well as the the quantity V,, can be computed using ((d) arithmetic operations. By Theorem 5.1, the iterate r++1 can be computed (d) arithmetic operations. Therefore, the per-round time of Algorithm 3 is O(d).
6.2 Small-Loss Bound
In this sub-section, introduce Algorithm 4, Adaptive LB-FTRL, and Theorem 6.2, the first small- loss bound for OPS. The algorithm is an instance of Algorithm 2 with pt = Then, 91+1 = 0 and It-1 is directly given by Line of Algorithm 4. Note that Theorem 5.1 still applies.
Algorithm Adaptive LB B-FTRL for OPS
M(x) dlog Σ Di= logæ(1) (i).
2: #1 -- arg min 1lo h(x).
3: for all E N do
4: Announce Dy and receive az.
5: 9i + f((
6: a: 5- az, (9t) (see the definition (4)).
dd
7: T) V4d+1+E; tar
8: Ft+1 +- arg min (oL x) + 1(x)).
9:
end for
The proof of Theorem 6.2 is provided in Appendix H.
Theorem 6.2. Let L1 minzed ΣT= fz()). Then, under Assumption 1, Algorithm 4 satisfies
(x(x)= < 2(log 2)v AdL; + 4d2 + d(log T + 2)2.
Under Assumption 1,
||l|| d
L min
log (a,, x/)
log
Σ logd 7 log d.
Assuming d, the worst-case regret bound O log d log also comparable to the regret bounds of the barrier subgradient method [26], Soft-Bayes [30], and LB-OMD [34] up to logarithmic factors. On the other hand, suppose that there exists an i* E [d] such that (i") = for all E [T]. That is, the -" investment alternative always outperforms all the other investment alternatives. Then, L = 0 and Ry = Od T).
Assumption 1 does not restrict the applicability of Theorem 6.2, as mentioned earlier. If the as- sumption does not hold, Theorem 6.2 is applied with respect to the normalized price relatives ā, ae///aalll laelloo In this case, Li is defined with respect to {ā.).

---

Time Complexity. Since 119: + a | @e - ax 1|2. it is obvious that computing a Tr and 91:t can be done ( arithmetic operations. By Theorem 5.1, the iterate 2++1 can be computed in (d) arithmetic operations. Hence, the per-round time of Algorithm 4 is O(d).
7 Concluding Remarks
We have presented Theorem 6.1 and Theorem 6.2, the first gradual-variation and small-loss bounds for OPS that do not require the no-junk-bondh assumption, respectively. The algorithms exhibit sublinear regrets in the worst cases and achieve logarithmic regrets in the best cases, with per-round time almost linear in the dimension. They mark the first data-dependent bounds for non-Lipschizz non-smooth losses.
potential direction for future research to extend our analyses for a broader class of online convex optimization problems. In particular, it remains unclear how to extend the two smoothness characterizations (Lemma 4.6 and Lemma 4.7) for other loss functions.
Orabona et al. [29] showed that achieving a regret rate of O + log L is possible under the no-junk-bonds assumption, where Li- denotes the cumulative loss of the best constant rebalanced portfolio. This naturally raises the question: can similar regret rate be attained without relying on the no-junk-bonde assumption? If so, then the regret rate will be constant in T the best cases and logarithmic in I' in the worst cases. However, considering existing results in probability forecasting with the logarithmic loss [5, Chapter 9]-a special case of OPS without the no-junk-bome cssumption-such data-dependent regret rate seems improbable. Notably, classical rate-optimal algorithms for probability forecasting with the logarithmic loss, such as Shtarkov's s minimax-optimal algorithm, the Laplace mixture, and the Krichevsky- Trofimmo mixture, all achieve logarithmic regret rates for all possible data sequences [5, Chapter 9].
Zhao et al. [37] showed that for Lipschitz and smooth losses, an algorithm with a gradual-variation bound automatically achieves a small-loss bound. Generalizing their argument for non -ipschiht non-smooth losses is a natural direction to consider.
Acknowledgments and Disclosure of Funding
The authors are supported by the Young Scholar Fellowship (Einstein Program) of the National Science and Technology Council of Taiwan under grant number NSTC 112-2636-E-002-003, by the 2030 Science and Technology Council of Taiwan under grant number NSTC 12-2628-EE-002001--MM and by the research project "Pioneering Research in Forefront Quantum Computing, Learning and Engineering" of National Taiwan University under grant number NTU-CC-1121893406.
Young Scholars Program (Excellent Young Scholars) of the National
References
[1] Jacob D Abemnethy, Elad Hazan, and Alexander Rakhlin. Interior-Poin Methods for Full- Information and Bandit Online Learning. IEEE Trans. Inf. Theory, 58(7):4864 4175, 2012.
[2] Amit Agarwal, Elad Hazan, Satyen Kale, and Robert E. Schapire. Algorithms for Portfolio Management Based on the Newton Method. In Proc. 23rd Int. Conf. Machine Learning, pages 9-, 2006.
[3] Heinz H. Bauschke, Jérôme Bolte, and Mare Teboulle, A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res., 42(2): 330-348, 2017.
[4] Nicolas Boumal. An introduction to optimization on smooth manifolds. Cambridge University Press, 2023.
[5] Nicoló Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[6] Nicoló Cesa-Bianchi, Philip M. Long, and Manfred K. Warmuth. Worst-Case Quadratic Loss Bounds for Prediction Using Linear Functions and Gradient Descent. IEEE Trans, Neural Netw. 7(3):604-66 619, 1996.
10

---

[7] Nicoló Cesa-Bianche Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-orde bounds for prediction with expert advice. Mach. Learn., 66:321-352, 2007.
[8] Chao-Kai Chiang, Tianbao Yang. Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online Optimization with Gradual Variations. In Proc. 25th Annu. Conf. Learning Theory, volume 23, pages 1.1-6.20, 2012.
[9] Thomas M Cover. Universal portfolios. Math. Financ., 1991.
[10] Thomas M. Cover and Erick Ordentlich. Universal portfolios with side information. IEEE
Trans. Inf. Theory, 42(2):348-36
1996.
[11] H. Gzyl and F. Nielsen. Geometry of the probability simplex and its connection to the maximum entropy method. Appl. Math., Stat. Inf., 16(1):25-35, 2020.
[12] Elad Hazan. Introduction Online Convex Optimization. The MIT Press, 2022.
[13] Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Mach. Learn., 80: 168-88888 2010.
[14] Elad Hazan and Satyen Kale. An Online Portfolio Selection Algorithm with Regret Logarithmic Price Variation. Math. Financ., 25(2):288-310, 2015.
[15] David Helmbold, Robert F. Schapire, Yoran Singer, and Manfred K. Warmuth. On-Line Portfolio Selection Using Multiplicative Updates. Math. Financ., 8(4):325-347, 1998.
[16] Zihao Hu, Guanghui Wang, and Jacob Abernethy. Minimizing Dynamic Regret on Geodesic Metric Spaces. arXiv preprint arXiv:2302.08665 2023.
[17] Rémi Jézéquel, Dmitrii M. Ostrovskii, and Pierre Gaillard. Efficient and Near-Optimal Online Portfolio Selection. arXiv preprint arXiv:2209. /3932, 2022.
[18] Pooria Joulani, András György, and Csaba Szepesvári. A Modular Analysis of Adaptive (Non-) Convex Optimization: Optimism, Composite Objectives, and Variational Bounds. In Proc. 28th Int. Conf. Algorithmic Learning Theory, volume 76, pages 681-720, 2017.
[19] Pooria Joulani, András György, and Csaba Szepesvári. modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, variance reduction, and variational bounds. Theor. Comput. Sci., 808:108-138, 2020. Special Issue on Algorithmic Learning Theory.
[20] A. Kalai and S. Vempala. Efficient Algorithms for Universal Portfolios. In Proc. 41st Annu. Symposium on Foundations of Computer Science, pages 486-491, 2000.
[21] Haihao Lu, Robert M. Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim., 28(1):333 354, 2018.
[22] Haipeng Luo, Chen- Yu Wei, and Kai Zheng. Efficient Online Portfolio with Logarithmic Regret. In Adv. Neural Information Processing Systems, volume 31, 2018.
[23] H. Brendan McMahan. A survey of Algorithms and Analysis for Adaptive Online Learning. J. Mach. Learn. Res., 18(90):1-50, 2017.
[24] Zakaria Mhammedi and Alexander Rakhlin. Damped Online Newton Step for Portfolio Selec- tion. In Proc. 35th Annu. Conf. Learning Theory, 2022.
[25] Mchryar Mohri and Scott Yang. Accelerating Online Convex Optimization via Adaptive Prediction. In Proc. 19th Int. Conf. Artificial Intelligence and Statistics, volume 51, pages 848-854 448-856,10 2016.
[26] Yurii Nesterov. Barrier subgradient method. Math. Program., Ser. B, 127:31-56, 2011.
[27] Yurii Nesterov. Lectures on Convex Optimization. Springer, second edition, 2018.
[28] Francesco Orabona. A Modern Introduction to Online Learning. arXiv preprint
1rXiv:1912.13213, 2022.
2022.

---

[29] Francesco Orabona, Nicoló Desa-Bianchi, and Claudio Gentile. Beyond Logarithmic Bounds in Online Learning. In Proc. 15th Int. Conf. Artificial Intelligence and Statistics, volume 22, pages 823-831, 2012.
[30] Laurent Orseau, Tor Lattimore, and Shane Legg. Soft-Bayes: Prod for Mixtures of Experts with Log-Loss. In Proc. 28th Int. Conf. Algorithmic Learning Theory, volume 76, pages 372-399, 2017.
[31] Alexander Rakhlin and Karthik Sridharan. Online Learning with Predictable Sequences. In Proc. 26th Annu. Conf. Learning Theory, pages 993-1019, PMLR, 2013.
[32] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Adv. Neural Information Processing Systems 26, 2013.
[33] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, Low Noise and Fast Rates. In Adv. Neural Information Processing Systems, volume 23, 2010.
[34] Chung-Eu En Tsai, Hao- Mao-Chung Cheng, and Yen-Huan Li. Online Celf-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States. In Proc. 34th Ins. Conf. Algorithmic Learning Theory, 2023.
[35] Tim van Erven, Dirk Van der Hoeven, Wojeiech Kotlowski, and Wouter M. Koolen. Open Problem: Fast and Optimal Online Portfolio Selection. In Proc. 33rd Amnu. Conf. Learning Theory, volume 125, pages 3864-3869, 2020.
[36] V. Vovk. Game of Prediction with Expert Advice. J. Comput. Syst. Sci., 56(2): 1998.
[37] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non- stationarity: Problem-dene deppeem-de dynamic regret for online convex optimization. arXiv preprint arXiv:2112.14366. 2021.
[38] Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the Seficiency-eegee Pareto Frontier for Online Learning of Portfolios and Quantum States. In Proc. 35th Annu. Conf. Learning Theory, 2022.
12

---

Readers are A A Summary of OPS Algorithms
Table 1: A summary of existing algorithms for online portfolio selection without the no-junk-bont bonds
assumption. Assume T >>
Regret (Ö)
Algorithms
Per-round time (Ö)
Best-case
Worst-case
Universal Portfolio [9, 20]
d dlog T
d'
EG [15, 34]
d' //332/33
d
BSM [26], Soft-Bayes [30], LB-OMD [34]
VaT
ADA-BARRONS [22]
d log
d.TT
LB-FTRL without linearized losses [35]
dlog 2+1
d'T
PAE+DONS [24]
d 1og'" T
d3
BISONS [38]
d Boog" 2 T
d3
VB-FTRL [17]
dlog'T
dT
This work (Algorithm 3)
dlog T
vdT
d
This work (Algorithm 4)
dlog' T
VdT
B Loss Functions in OPS are not Geodesically Convex
Let h(x) -d Σ log be the log-barrier. Let (M.g) be the Hessian mani- fold induced by the lar-barrier, where M riA and is the Riemannian metric defined by (u, v) = (u, (²h(r))).
Lemma B.1 (Gzyl and Nielsen [11, Theorem 3.1]). Lera, riA. The geodesic 7 :0,11] riA connecting is given by
((i)"
(1) = Σ/=1 x(j) -
e [d].
where (i) denotes the i-th entry of the vector (t) e A.
The proposition below shows that the loss functions in OPS not geodesically convex on (M, 9) in general.
Proposition B.2. Let a (2, 1) E R R The function (xx log (a, x) not geodesically convex on (M,g).
Proof. It suffices to show that o y [0.1] - R is not convex function [4, Definition 11.3]. Let I = (1/2,1/2) and y = (1/(1 + e), e/(1 + e)). By Lemma B.I, the geodesic connecting x, is (t) (1/(1 e²), /11 e²)). We write
Det (f (t) (2 12+)))((1+t) < O, Vt
log 2
2
showing that f o ryin not convex. The proposition follows.
C Properties of Self-Concordant Functions
This section reviews properties of self-concordant functions relevant to our proofs. referred to the book by Nesterov [27] for complete treatment.
13

---

Throughout this section, let be self-concordant function (Definition 3.1) and II- be the associated local norm, i.e., ||u||_ V(u, (ap(z) Vu R2 x E dom sp
Self-concordant functions are neither smooth nor strongly convex in general. The following theorem indicates that nevertheless, they are locally smooth and strongly convex.
Theorem C.1 (Nesterov [27, Theorem 5.1.7)). For any y dom p such that r = lly - -x11a <
1 1/M,
(1 - (r) S p - (1- Mr)² V2p(z).
Define (t)) = -- log( 1 + t). Let w. be its Fenchel conjugate, i.c. (t = - - loog( - t).
Theorem C.2 (Nesterov [27, Theorem 5.1.8 and 5.1.9)). For any v, y dom & with r 11 - 2 2.
y²
(Vy(y) Vp((x) x) 1 1 Mr
((0) 2 2(x) + (Vp(z), - x) + M2 (Mrr.
Ifr < 1/M, then
,2
(Vy(1) - Vv(x), x) s 1 Mr p S ( + (V x) + M2 (Mrr)
(8)
The following proposition bounds the growth of w and w..
Proposition C.3 (Nesterov [27, Lemma 5.1.5)). For any t 2 0.
t²
1²
2(1 +t) S sw(1)= s 2+t
For any t E [0, 1),
t² < (1) <
z²
2-t t
2(1
is easily checked that both the loss functions in OPS and the log-barrier are not only self-concordant but also self- coff-concordant barriers.
Definition C.4. 1-self-concorllan function up is said to a u-self-concorlurt barrier if
(Vipx)), w/2 < (u, (Zz(z))), Vx E dom yp, u E Rdd.
Lemma C.5 (Nesterov [27, (5.4.3)). The log- bog-barrier (2) a d-self-concordant barrier.
D Proof of Theorem 3.2 (Regret Analysis of Optimistic FTRL With Self-Concordant Regularizers)
D.1 Proof of Theorem 3.2
The proof of the following stability lemma is deferred to the next subsection.
Lemma D.1. Define (z) (er., x) + m) pxx)). Let {np be non-increasing sequence of
strictly positive numbers such that 77-1 || Dt 6z &ell.... I 1/(2M). Then, Algorithm satisfies
F((x1) F141(2441) + (ve, 21) S (vr 02, 21 x++1)
TT-M w (M [2411 xz sell..))
1/- M W2 1 Mll - 0, m...
7/- |/1e Ex 22.
14

---

Define (x) = (z) + (0), Since 0r+1 has no effect on the regret, we set 0r+1 = 0. By the
strong FTRL lemma [28, Lemma 7.1].
RT(x)= Σ (1)) - (v),
2bT+1, + p(Ø)
p(x)
+ (((((x)) ((41(2441) + x1))
min
11T
ZEX
7/0
+ Pr+i(eTT1) - (x+
((x)
(x) - (et1(10+1) + (1),
1f
((x) E (1e1) + (v1,
The penultimate line above follows from the assumption that m p(x)) 0 and that TT+1 minimizes Fr on X; the last line above follows from telescopic sum and ú1 0r+1 0. The theorem then follows from Lemma D.I.
D.2 Proof of Lemma D.1
Since is M-self-conccoraat, the function 7t-1F; is M-self-concordaat. By Theorem C.2, - (x(+1) - F((t)
1
2 (m V. 2441 - x2) M ( xet1ll2.))
= =m + 12), zx) Th (6,, - 21) + M2 21t1lla.).
Since ,, minimizes (x) + (6r, .)) on X, the optimality condition implies
(x)) + 0z, T++1 xz) 0.
Then, we obtain
(t-1F((z41)) - 1-1 2 - (6e, R441 - xx) +
WM - -zellz.).
M
Next, by the non non-inonennt mon-iccreasin of {m:}, (p((+1)) 2 O, and the last inequality,
F((x)) F141(01+1) 22)
(-1 1
1 (1_1)
= F((x)) - FI(4111 + (v), (ve, 2(41) +
p(((41)
17-1
me
< F((xe) - F.(x++1) + (vr, - r(+1)
I (vr - 82 F - 2(41) M WM - x x1llag).
This proves the first inequality in the lemma. By Hölder's inequality,
P.(x,) - Fe+ (x++1 + (ve, S Ilv. Gellz,, 1 - Re41lla;
m M2 (M 2z41 llay))
By the Fenchel-Yound inequality, [12 Ze+ ll.,)) + w-(n- Dellz,.)) 2 11 12 Zz Wella,ller 6o Bellogge (10)
Combining (9) and (10) yields
Fz, Fe-1 (x(41) + (v,, xz) Th- M2 (M 1|u: eellz..))
which proves the second inequality. The third inequality in the lemma then follows from the assumption that 7-11// Gellz..> I 1/(2M) and Proposition C.3.
15

---

E Proofs in Section 4 (Smoothness Characterizations)
E.1 Proof of Lemma 4.3
We write
| (()(a())(()22 S 1. (Ei (()())
E.2 Proof of Lemma 4.6
Define == || -vll-- Consider the following two cases.
ii Suppose that r 2 1/2. By Lemma 4.1,
1
|| @ V/(xx) - y o
S
41|x =vl..
2
iii Suppose that r < 1/2. We write
z(1)
1 =1)) 2
,² = ||= y
1
4i E [d]
y(1)
showing that
s(1)
< 1 -
S 11+1, Wie
y(1)
Then [10, Lemma 1].
(a, v) (a,x)
a())(() (i))((()
S max ali)v(i) E at))
max yi)
1
5
[c(d] x(1)
similarly,
(a, v)
1
2
1 r (a, x))
We obtain
-2r
1+r
x01) (a, v) y(1) (a, x))
1-r r 1
2r
S
<
1-r
1 r
1+r
Since r 1/2,
x(1) (a, v) (1- vii (a, x))
2 (T-r)
2r
4
S max
(1 r- < 16r
1
Therefore,
((())((1)
a())v(i) 2
I 2 Vf(x) y 3 [
(a,
(a.3)
(a, v) )
2 (1- x11) (a. v\
2
vi1 (a,x)
(a(iv((i)
16
(a,
16
showing that || o (f(x) y ff < 4/12 - رll
Combining the two cases, we obtain (())) y 3 V/(w)l1, S 44 - yll,- Since x and y are
symmetric, we also have || @ (f(z) ( | I 4
-/1.. This completes the proof.
16

---

E.3 Proof of Lemma 4.7
We will use the notion of relative smoothness.
Definition E.1 (Bauschke et al. [3], Lu et al. [21]. A function f is said to be L-smooth relative to function if the function Lh f is convex.
Lemma E.2 (Bauschke al. [3, Lemma 7)). Let f(x) log (a, for some non-zero R4.. Then, f is 1-smooth relative to the logarithmic barrier h.
Fix E ri A. By Lemma E.2, the function h is convex and hence
h()) f(x) + (Vh(x) Vf(x), v) S h(2 v) f(x + v). E where riA- - x = {u - x/u E ri By Lemma 4.4, Theorem C.2, and Proposition C.3, ||u||2 S 1/2,
h(z +) -(>)) - (Vh(z), S w. (1v1l))))) 1|ll.
Combining the two inequalities above yields
(-Vʃ(z), - |||| S (z) - f(x + u)) Since [xr v) minyea (vy 0 (Assumption and (e, v) O. write
(-V ac, v) |011 f(x). Va R. v E A x such that ||v|| S 1/2.
The left-hand side is continuous in v, so the condition that v E rii - x can be relaxed to v E A = u x/uu A). We get
(-V ac, v) ||lll s f(x), Ya TRERUEE such that ||l|| $1/2. (11)
We show that choosing
-c ( ax
(12)
for any e E (0, 1/2] ensures that
x and ||0|le 1/2.
First, we check whether ||u|],, - 1/2. We write
||~l__ = c| - (
= c/V f + az (Vf()))el
< c/V (x)
c
< 1/2,
where the last line follows from Remark 4.8 and Lemma 4.3. Then, we check whether v E A x or, equivalently, whether v + A. By the definition of az (V)(x)) (4), each entry of is given by
(ef(() E, (()))))(((()))
U/ = -10()
Vi [d],
where vạf(x) is the j-th entry of fz(). Obviously,
v.f(z) E,
Σ v()
co)
0,
so E, x(1 + vi) = 1. It remains to check whether x01) + v(i) 2 0 for all i E [d]. Notice that Vf(x) entrywise negative. Then,
xx1) + xc() = x(1) ccr(i) Vif(2) - Σ,
E, x1)
2 x + ccr)) E, ,,<())²
E, x(1
17

---

To show that the lower bound is non- non-negative, we write
-x(1)² ,
x(i)² a(((i)((i
Σ, (a)
x(1)
- E, x(1)²
max maxx(j)
seld]
z(1) max z(1)x(j)
Σ x xk))²
if j. then max,
x() mn xbb7
1 1; otherwise,
x x1))a((i)
S max x(1),{(j)
+ x S 1
max
J
Σx xkk)²
3&
2
Therefore,
x1i) + u 2 (1-c)=(1) 2 1 50(1) 20, Weldd
Plug the chosen (12) into the inequality (11). We write
f(x) 2 sup cllV/((x) + a2 a, (Vf(z))ell 05e51/2
f()) + +a,(V
= sup (c- ( + a2 (V(())))
0Se51/2
4 (+(+) + (
This completes the proof.
F Proof in Section 5 (LB-FTRL with Multipliaatie--rrddeen Optimism)
F.1 Proof of Theorem 5.1
We first check existence of a solution. For convenience, omit the subscripts in po+1 and 17; and write for 91st-
Proposition F.1. Assume that up E [-1,0] Define
d
X E arg min (A), ((A) = A Σ (1-rp(i)) (A + ni())).
(13)
XEdom
Then, X exists and is unique. The pair (I++I 2(+1), defined by
x++1(1) (1) + nn)))) It+1(1) = p(1) x ng(
1 (pi)
(14)
solves the system of nonlinear equations (5).
We will use the following observation [27, Theorem 5.1.1].
Lemma F2, The function xp is 1-self-concordamt.
Proof of Proposition F.I. By Lemma F.2 and the fact that dom e does not contain any line, the
minimizer X* exists and is unique [27, Theorem 5.1.13]; sine np E [-1, 0jd and X E dom do we have Ft-1 (i) 0; moreover,
mp(i) 0.
((x+)= 1 Σ x + ng((i)
Then,
Σ
re (1) = -1-=))(()))---------000-)))>)))-
18

---

showing that T++1 E A.
Then, check whether (1z+1, 1)+1) satisfies the equalities (5). It is obvious that 21+1 1 g++1 By the method of Lagrange multiplier, if there exists À E R such that
ng(i) + (1)
1 Iz+1 (1)
+ O,
Σ 2ml
(1) = Ie+ (1) 2 0,
then 21+1 E arg m (g.z) (0c+1, 2) 77 -1-7)/((a))) h(x). Is easily checked that the above conditions are satisfied with À = X and (14). The proposition follows.
We now analyze the time complexity. Nesterov [26, Section 7] [27. Appendix A.2] proved that when p 0, Newton's method for solving (13) reaches the region of quadratic convergence of the intermediate Newton's method [27, Section 5.2.1] ] after Ollog d) iterations. A generalization for possibly non-zero p provided in Proposition F.3 below. The proof essentially follows the approach of Nesterov [27, Appendix A.2]. is worth noting that while the function i is self-concordant, directly applying existing results self-concordas minimization by Newton's 's method [27, Section 5.2.1] I] does not yield the desired Oloo d) iteration complexity bound.
Starting with an initial iterate An IR Newton's method for the optimization problem (13) iterates as
A+11 A 1kk-8((Ae (aa)//000)))) V {0} UN.
(15)
Proposition F.3. Assume that up E [[1,, 1,00 0). Define i E arg (ag g(i)). Then, Newton's
method with the initial iterate
Ao = 1 1=-ng((")
enters the region of quadratic convergence of the intermediate Newton's 's method (27, Section 5 after Ollog d) iterations.
Firstly, we will establish Lemma F.4 and Lemma F.5. These provide characterizations of a/ and X that are necessary for the proof of Proposition F.3.
Lemma F4. The following hold.
(i) wf is strictly increasing and strictly concave function.
(ii) ('(x*)= 0.
(iii) Ao S X*
Proof of Lemma F.4. The first item follows by direct calculation:
w² (A) Σ 1- mpl1)
d
2 21 - rp)())
(>+ng()))² O, ("(A)
< 0.
(A ni()))
The second item has been verified in the proof of Proposition F.1. As for the third item, we write
1 - mp(1)
1 - -ipp mp(i") 5 +
('O)))
<
Ao + ng(i)
Ao + (it)))
The third item then follows from & (>o) ((*)) and the first item.
Lemma F.S. Let { be the sequence of iterates of Newton's 's method (15). For any / 2 0, ().) S and de S X*.
Proof of Lemma F.5. Recall that dom vi (-g(i*), o0). We proceed by induction. Obviously, An E dom v. By Lemma F.4, the lemma holds for L. 0. Assume that the lemma holds for some non-negative integer t. By the iteration rule of Newton's method (15) and the assumption that (),) < 0.
A+11 = d₁ ('()))
2 A
((A)))
19

---

which ensures that Ae+1 E dom sb. By Lemma F.4 (i) and the iteration rule of Newton's 's method (15),
we have
(Ac)
(A++1) S (Ax) + o (A:) A,) = (a,) (ve)
0.
(2+)
By Lemma F.4 (i) and Lemma F.4 (i), A4+1 I X The lemma follows.
Proof of Proposition F3. Define the Newton decrement as
(Ae))
ó(A) = 2 (A)/ (A)
By Lemma F.2, the region of quadratic convergence is [27, Theorem 5.2.2]
{A dom 6()) < 1/2).
Define T == [[9 + 7og d)/4] By Lemma F.5, (A,) S for all t 2 0. (A,) 0 for some 0 <<L 1 < T, then Newton's 's method reaches Q within T steps and the proposition follows. Now, let us assume that vd((,) < 0 for all 0 S 1 S T. By the concavity of up! (Lemma F.4 (i)),
(Ar)
( S (Ax) + (A)) - (Ae) + ("(D-1) 1 (Ax-1).
Divide both sides by v (1t-1). By Lemma F.5 and the AM-GM inequality,
(Ae))
+ (2())) 2 V (e (>oo)
(((11)
Then, for all 1 t
Ie' Ie'( (Ae) S (Ac
This implics that for all 0 +1
((()) (A01 1
(1
which further implies that
8(2,)² (A))))"))))) (v)"(A))3
1 (W(N))
16
(x))():))3
It remains to estimate & (Do)) (No), and ("()). Given up E [] and Ao + ng(i) 2 1. through direct calculation.
1 - mpp()
[Ao()
- <
Σ (1
mp(1)) - 1 < 2d,
No + (1)
1=1
1=1
(²(o)) Σ
1 - mp(i)
Σ 2
2d.
(No + (i))
1=1
i=1
Since
mp(i)
v'())) -1 Σ
Ae + (1) 5 0,
by the Cauchy-Schwarc inequality,
Σ xi [n
1-mp(t)
((())) = Σ 1 -i)
2 2d
(>e + ng())²
Σ b==1! (i)(
ΣL (1 mp(i))
(1p()))
Therefore, for 0 T+,
(2d)
6(2,)²
16
In particular, 8(Ar+1) < 1/2, i.c., Ar+1 Q. This concludes the proof.
20

---

Proposition F.3 suggests that after Ollog d) iterations of Newton's 'soo's method, we can switch to the intermediate Newton's method which exhibits quadratic convergence [27. Theorem 5.2.2]. Each iteration of both Newton's s method and the intermediate Newton's method takes ( time. Therefore, takes (d log d) time to approximate X Given X*, both 2+41 and 9++1 can be computed in (dd) time, according to their respective definitions in Equation (14). Therefore, the overall time complexity of computing Et+1 and g is (dd.
F.2 Proof of Corollary 5.2
By the definition of local norms (3), we write
l1 Dt + uell 2., = (I + uz) 4 te
2 x4 3 2 = [[ + [)) 2 24 - -Pell2-
By Lemma 4,4 and Theorem 3.2, if 1 + uz) 3 oe Poll2 2 S 1/2, then Algorithm 2 satisfies
h(x)
RT(x) -
Mh (g: + u²) O - -Pell
For any x E A, define x' = =1= - 1/T)a e/ddT). Then,
M(')) S - log d Σ
log dt
dlogT, A
and hence [22, Lemma 10]
d log T
T
RT(x)= S Re(x') + 2
M- 1- ue) 2 xt pell +
4/
G Proof of Theorem 6.1 (Gradual-Variation Bound)
G.1 Proof Theorem 6.1
We will use the following lemma, whose proof is postponed to the end of the section.
Lemma G.1. Let {ae) be the iterates of Algorithm for all
1 The 6' m- 9e Iellay S 1 6'
(1-0V)
1
Th- S S Th- and ll l1 S 1, 6V7)
(16)
then |1141 21 la. < 1.
We start with checking the conditions in Lemma G.I.
It is obvious that m7, S 1/(16v22 < 1/6.
By the definition of the dual local norm (3), the definition of ÿt. and Lemma 4.3,
l le.l.... 1l xzll2 ||g @ 2,1112 |19.-1 ilm, S 1,
Vt 2.
Then, by the triangle inequality and Lemma 4.3,
1
Mh rellza, < 16v2 llee + l1ōellan..)
<
8/2
6
21

---

It is obvious that the sequence {m is non non- -inceresa.. By the triangle inequality, Lemma 4.3 and the fact that Va Va+b S Va + votor for non-negative numbers and b, we write
n
V
Th-
V512d + V/
/512d + Vi-1
512dd +2+ Vi-1 +2
/512d + + Vi-1
512d +24 V1-1 + V2
V2
=1 V512d +2 +2+ V + V2
1 1
16Vd
2 6vd
Then, Lemma G.1 implies that
ri = | - Della, $ 1.
By Proposition C.3,
ri
w(|k2 - F4+1 )
4
By Corollary 5.2,
dloog T
Ry S
+
(gt - Pt 2 21, - -x+11
41p-1 7?
+ 2.
TT
Fort 2 2, by Hölder's inequality and the definition of the dual local norm (3),
(ge Pt It lt+1) S ||g. Pe Ø xellzn.
||,e ④ 9: pell2
||, @ gr It-1 2 91 1112
By the triangle inequality.
[ ④ - It-1 ④ 1t-1
| ② 9: Iz-1 (1 || @ V((( xz-1 gt-1 112
We bound the two terms separately. By the AM-GM inequality and Lemma 4.6, the first term is bounded by
I 2 gr Iz-1 Vi(aa-))ll 4m:11 C gr x1-1 Vi((a-)) 16
< 64 1 + 16m- 12.
By the AM-GM inequality, the second term is bounded by
| o Vf(((=1)) - zz-1 O 19-1111re = [Vf((x:-1) - Gt- Jt
< 4m, V((20-)) - - 1
r?
167-11
Combine all inequalities above. We obtain
(g. Pt It. Ft Fe+1)
2
417-1
(17)
< 4m V - 9t-1 1
11-11 + 64
64mp-172-
r
8T:
22

---

Fort = 1, by a similar argument,
1 2 si
1
1
(9,,21 n2)
r
-
4770
+
r1)
1
=
2nj0
(18)
4170
47j
2
47o
470
87j
By combining (17) and (18) and noticing that T/2 1// S 1/512,
T
1 2
O Bz, It
xe+1)
4rp-
T-1
1
s 21j0" +
4Mp [I 99--1
-9t- 11-111
641
re
81/-1
t=2
t=1
20o0 +
Amp VVV -9-
2=
By Corollary 5.2.
d logg T
Rr
2njo"
4m-1 V[(((=)))
V 2.
T/
Plug in the choice of learning rates into the regret bound. We obtain [28, Lemma 4.13]
T
Vf((z-1) - ( 12 x.-.. +3
Rr S V
V 5122 + 2 V/-1
S Vdlog + VV((((-11 v Pe-1.* +3
5112d + Vi
t=2
I Vdlog T( (V +12d 22) + 4vd 1/¹ Vrr
ds
V512d +3
< (log 7 V dV 5126 / 2d log T + 2 128v 2d.
G.2 Proof of Lemma G.1
Define
Vs E arg min (9I.t, x)) + h(x),
ze arg min (01.1 + h(x). DEA
ZEA
97-1
71
By the triangle inequality.
|| 1ll, Il,, S ||,, Well., 11ye 24 2ella, + || re+ilbe
(19)
Define d1 = || ye Yellz,- d2 = live - 21 Ily. and d3 = || I 1l Suppose that d, 5 1/5
for all 1 i < which we will verify later. By Theorem C.I,
1
(1 d, 22)()) & v2h(ge) -
(1 (1- d1) (2h(2r),
(1 dz) 2)) & &2h(E)=
5 (1-d2) d2)
(2h(yt)
(20)
1
(1 dz) 2 S v*h(2)) S (1 dz)²
(2h(2441).
We obtain
d2
da
18 zellz, 5
|| Z241 1b, < (1 di)(1 d2) dg)
I-dj" di
Then, the inequality (19) becomes
d2
d3
|| re-ille, 5 dl + 1- dj (1- (1-d))(1- -1)
23

---

It is easily checked that the maximum of the right- hand side is attained at d1 = d2 ds = 1/5 and the maximum value equals 269/320. This proves the lemma.
Now, we prove that d: - 1/5 for all 1 S siss. 3.
(Upper bound of d1.) By the optimality conditions of xy and yt.
19-191 + Vh(ye), 21 y0) 2 0
(/ 191:t-1 + 7 + Vh(xz), ye - xz) 2 0.
Sum up the two inequalities. We get
Th- (g: St, It we) 2 (Vh(az) Vh(u)), xx y1)
By Hölder's inequality, Lemma 4.4, and Theorem C.2, we obtain
df
Te- n - &ell.,,. d1 2 + d1
Then, by the assumption (16), we write
Th- 19 Dr Gellz,.- di <
< 1/5.
7/- 11 Del
Dellze,
2. (Upper bound of d2.) By the optimality conditions of yo and 24.
(g1:t + Vh(zz), Vt+ - 20) 2 0
(g 1 Vh(y)), ve)
1--1
Sum up the two inequalities. We get
(2 1/2 7 (---1) (Vh(y)), Ve 21) 2 (Vh(y)) Vh(2z), 2t)
1
By Definition C.4, Lemma C.5, and Theorem C.2,
(2) nt TT-1
d3
Vodz 2
17: 1 + d2
Then, by the assumption (16), we write
(1 Th / vd
d2 <
S 5 1 11-1111/1111 1//
3. (Upper bound of dz.) By the optimality conditions of and 2z41,
(Nh91a + n1++1 + Vh(x++1), r(+1) 2 0
(nigi. + Vh(z,) le41 21) 20.
Sum up the two inequalities. We get
T7 (0.+1, 2 - r+41) 2 (Vh(z)) - Vh(Io+1), 2: - x(+1).
By Hölder's inequality, the assumption (16), and Theorem C.2, we obtain
dz
1hd33 2 nell@++
d3 >
1 da
Then, by the assumption (16), we write
d3 <
< 1/5.
24

---

H Proof of Theorem 6.2 (Small-Loss Bound)
Recall that or minimizes
|| aell xi,*
over all E IR (Remark 4.8). We write
11ge + agel S 11:: S 1,
which, with the observation that S 1/2 for all / E N, implies that 111s + axellz, S 1/2. Then, since the all-ones vector e is orthogonal to the set A A, by Corollary 5.2 with = 0 and
ut = are, we get
dlog T RT S
M- + are) @ xxl12 + 2
4T
d log T
Σ M-llle + agell +
VT
Plug in the explicit expressions of the learning rates We write [28, Lemma 4.13]
dlog T
lige + ageller
RT S
+
Vd
+2
1/T
4d + 1 E 11 + aaeel
11ge + arell
dlogT
<
+ vd
+2
T/T
v
Et= 119, aaeel2...
Eis llactarlll
ds
< Vdllog
4d 1+
11 + arelle + Vd
+
4 +
T
< (log +22
19: + anel + 4d + d
T
< (log T + 2)
19: + anel + 4d + d.
Finally, by Lemma 4.7,
Rr (log + 2 4d Σ f(xx)) - 4d d.
The theorem then follows from Lemma 4.23 of Orabona [28].
I A Second-Order Regret Bound
In this section, we introduce AA + LB-FTRL with Multiplicaaiie--rraaanea Optimism (Algorithm that achieves second-order regret bound. This bound is characterized by the variance- like quantity
Qr
min PERa
I C V(((2))
=ll -
For comparison, existing second-order bounds characterized by the quantity
VT
min RERd
[V((())) - =0123
25

---

T times the empirical variance of the gradients (see, e.g., Section 7.12.1 in the lecture note of Orabona (28]). Given that every p E F can be expressed as p Iy ( v for t = p 2t, and by the definition of the dual local norm (3), we obtain
T
QT = min
VV((zz))
oER
1=1
showing that QT is local-norm analogue of VT.
The flexibility introduced by optimizing Qr over is easy. In particular, Theorem 1.2 in Section I.3 shows that when Qr I 1, then Algorithm 6 achieves a fast O(d log T) regret rate. However, while Qr looks reasonable Vr. the empirical variance interpretation for Vr does not extend to Qr. Interpreting QT seeking "more natural" variant of Qr left as a future research topic.
Rd allows for a fast regret rate when the data
mathematical extension of
1.1 The Gradient Estimation Problem
To obtain a better regret bound by using Corollary 5.2, one has to design a good strategy of choosing Pt. In Section 6.1, have used Pr It-1 -t-1- this section, consider different approach.
Consider the following online learning problem, which we call the Gradient Estimation Problem. It is multi-round game between LEARNER and REALITY. In the t-th round, LEARNER chooses a vector Pt E R then, REALITY announces a convex loss function {p) = M/- 1 @ 9t - p p1l: finally, LEARNER suffers loss (p.)..
1.2 LB-FTRL with Verage-Muttipicatie-Crrdiiii Optimism
In the gradient estimation problem, the loss functions are strongly-convex, A natural strategy of choosing Pt is then following the leader (FTL). In the (-th round, FTL suggests choosing
Pr
7--1 O 9r E arg min
(p).
70:-22 r=1
pER
This strategy leads Algorithm 5. Theorem 1.1 provides regret bound for Algorithm 5.
Algorithm 5 LB-FTRL with Nvernge-MulliplcctiveeGrrrrrerr Optimism
Input: A sequence of learning rates (M.220 C T4++.
1: h(x) -oo Σ log x())
2: 21 <- arg min 170 hxx).
3: for all t E N do
4: Announce 2t and receive at.
5: Jt = (x+)).
6: Pt-1 (1/10n-1) 1T- @ gr.
7: Solve I++1 and ge+1 satisfying
x441 O 0t+1 Pt+1,
[441 arg min (g1.,z) + (0141, + m h(()).
8: end for
Theorem I.1. Assume that the sequence of learning rates {nr} is non-increasing and 11((22)). Then, Algorithm 5 achieves
dlogg T
Rr
+
+2 min
Σ
Vf((z)) -pl
70:-11
PER
nh = 7 1/(222) constant, then
dlogT
RT <
+ 2n( T' +
2 nQT.
26

---

Proof. Since Pt is a convex combination of 2, @ 9r. by Lemma 4.1, Pr E -A. We restrict the action of the gradient estimation problem be -A. By the regret bound of FTL for strongly convex losses [28, Corollary 7.24].
T
T
T
(2/2T 11)
I Σ
Σ ((P)) t=1
min
(p))
2
270xe-1
70:1-1
t=1
1=1
t=1
Then, by Corollary 5.2,
dlogg T RT
dlog T
+ +
Σ (pp)) I
+ +2+
Σ
min
Σ
k(p).
T/T
1
70:-11
pe
The first bound in the theorem follows from
Σ
h(p)=
min PER
Σ
The second bound in the theorem follows from the inequality Σi 1/2((tn) S <logg + 1).
Time Complexity. Suppose that a constant learning rate is used. Then, both Jr and pt+1 can be computed in (d) arithmetic operations. By Theorem 5.1, T+41 can be computed in ((d) time. Hence, the per-round time Algorithm is ((d).
1.3 AA LB-FTRL with Average-MultplicattteCrrddddd Optimism
The constant learning rate that minimizes the regret bound in Theorem I.1 77 OlodlogT/CC However, the value of Qr is not unknown to INVESTOR initially.
In this section, propose Algorithm 6, which satisfies second-order regret bound without the need for knowing Qr in advance. Algorithm 6 uses multiple instances of Algorithm 5, which we call experts, with different learning rates. The outputs of the experts aggregated by the Aggregating Algorithm (AA) due to Vovk [36].
Algorithm 6 AA + LB-FTRL with Avenge-MaltiplicaiieeGrini Optimism
Input: The time horizon T.
1: K = + [log, T".
2: for all k [K] do
3:
wi 1.
4:
q 2
5: (N)) +
Vd T
2./2log T 55
6: Initialize Algorithm 5 with the constant learning rate (+) as the k-th expert As.
7: Obtain _i from Ak.
(k)
8: end for
9: #1 >K THT Σ wi (K) (K)
10: for all 1. [T] do
11: Observe 0t..
12: for all & E [K] do
(k)
/ (k)
(ar, (()))
13:
Wi+1
(k) 14: Feed a, into As and obtain 2 2:411
15: end for
16: Output F++1
Σk
(k) (8) w 21
Ek=i wess
end for
The regret bound of Algorithm 6 stated in Theorem 1.2, which follows from the regret of AA and Theorem I.I.
27

---

Theorem 1.2. Algorithm with inpur T E N satisfies
RT < (1+ (2) v2 dQT log'T 2v 2/ log T + L log T log(log2 T + 2) +3, ifq 2 v2 1 log T + 22 T + log(log, T + + 4,
2d T +
iQr 1.
v/2
Remark 1.3, Since Qr S 2T, the regret bound in Theorem 1.2 is O O log T) in the worst case.
Proof. = [log, 7 is the number of experts in Algorithm Let R be the regret k-th expert Ag. Since the loss functions fx(x) - llg (ae, x) are 1-mixable, by the regret bound of AA [36],
Rr S min RG + log K, ke[R]
where Ri and (k) denote the regret of Algorithm and the regret of the k-th expert, respectively.
The quantity (k) in Algorithm 6 is used as an estimate of Qr. Notice that Qr S 27 S g(K) Qr 2 I, then there exists k* [K] such that q -1) < Qr S q(k"), By Theorem I.I and some direct calculations.
R <11 V2+ log + 2v T +
log T + 3.
V2
If Qr < 1, then by Theorem I.1,
(x) s 22V2dlog T 2d
1
log T +
V2
The theorem follows by combining the inequalities above.
Time Complexity. In each round, Algorithm 6 requires implementing O(log log copies of Algorithm 5. By Theorem 5.1, the per-round time is Oddlog log T).
28


Reviews:
[{"review_id": "llVuuaPU57", "reviewer": "Reviewer_mCNh", "summary": "This paper studies how to achieve adaptive regret bound, including gradient-variation bound and small-loss bound, for the online portfolio management problem, without the classical no-junk bund assumption. The authors successfully achieve this goal by observing a new kind of smoothness for the function -log wx. ", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The finding of a kind of smoothness of -log<wx> is the major contribution of the paper. I think this is a novel and significant observation, and lead to multiple new conclusions. Specially, for the small-loss bound, one can easily show a upper bound related to root{sum of gradients at x_t} by using a step size inversely proportional to root{sum of norm of gradients}. However, to get a small loss, bound, the next step is to assume smoothness to create a relationship between root{sum of gradients at x_t} and root{sum of function values at x_t} (using the classical Lemma 2.1 of [29]). In this paper, the authors show that, in the OPS problem, for the loss -log<wx>, we do not need smooth to construct this relationship. The key observation, to me, is Lemma 4.7, which shows a similar result to Lemma 2.1 of [29] with a “surrogate gradient”. In this way, the paper achieves the first small-loss bound for non-smooth functions, which is novel and interesting. For the gradient-variation bound, similar arguments also hold. \n\nNote that, with this observation, one can directly combine it with existing adaptive methods to achieve adaptive bounds. However, it does not mean the proposed methods are less novel. \n\nThis paper is generally well-written and easy to follow. The key finding, section 4.3, is easy to understand.\n", "weaknesses": "For exp-concave functions with bounded gradients (e.g., with no-junk bund assumption),  algorithms such as variant of ONS () can get a O(log L^*) bound, while the algorithm in this paper yields a O(root{L^*} + log T) bound, which is sub-optimal. It would be great if the authors can consider how to get a best-of-both-world bound, which enjoys O(root{L^*} + log T) for non-smooth functions, and O(log L^*) for smooth functions. \n\nTo obtain he optimal gradient-variation bound, the proposed algorithms need to know V_T in advance. In the appendix, the authors propose an algorithm that can learn the step size adaptively. However, it somewhat lost the good property of the gradient-variation bound when V_T is small. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for correctly pointing out our main contribution and emphasizing the novelty in the proposed methods. \n1. **On achieving optimal small-loss bounds for both smooth and non-smooth functions simultaneously:** This is an interesting direction. Such generalization requires non-trivial work and seems to be not directly related to the topic of this paper. We will consider this as a future research direction. \n2. **On the gradual variation bound:** \n   - Our algorithm for the gradual variation bound does not need $V_T$ (see Theorem 6.1) and there is no need for learning the learning rate. It is Algorithm 5, which is for the second-order bound, that needs learning the learning rate. As stated in the paper, we have not found a good interpretation of the second-order bound and hence provide the second-order result only in the appendix. \n   - We do not get the statement on losing the good property when $V_T$ is small. We would appreciate it if you could elaborate. "}, {"review_id": "951xwCMUdw", "reviewer": "Reviewer_DgZU", "summary": "The paper studies follow the regularized leader algorithm (FTRL) on the online portfolio selection problem without the assumption of no junk bonds. This makes the resulting loss function non-Lipschitz and non-smooth and makes analyzing the regularized follow the leader algorithm hard to analyze. The paper proposes using a self-concordant regularizer for the FTRL algorithm and proves regret bounds for the algorithm for a generic online convex optimization problem. They then use the result to propose two novel algorithms that have small-loss and gradual-variation regret bounds, respectively, for the online portfolio selection problem, which to the best of the author’s knowledge are the first regret bounds for non-Lipschitz and non-smooth losses.", "questions": "Questions\n1. Is it possible to state Theorem 3.2 for a generic loss that satisfies some set of specific conditions? This might streamline sections 3 and 4 by highlighting the necessary conditions ahead of time. Additionally, it might reduce the repetition in redefining the problem since fundamentally the only thing that changed was the loss function. \n2. Is there intuition how the newly proposed algorithms get around the non-Lipschitz loss? My intuition is that it depends on choosing the learning rate properly so that when the Lipschitz constant is large, the correct learning rate mitigates it. Is the intuition correct? This seems to imply the learning rate should change depending on where the location of the data point for FTL type algorithms. ", "limitations": "The paper is generally more theory-oriented and authors imply it is unclear how the analysis can be generalized to other settings, thus adequately addressing the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper seems significant as it provides a new result towards bounding regret for non-Lipschitz and non-smooth losses. The main contribution seems to originate from being able to prove that FTRL with a self-concordant regularizer without the barrier requirement obtains a regret bound similar to the setting with the barrier requirement. They then show how to apply the result to the online portfolio selection problem which is a canonical online convex optimization problem. The paper provides clear background for the problem to help motivate the goal and significance of the result.", "weaknesses": "The paper lacks clarity in how exactly Theorem 3.2 is applied to the online portfolio selection problem. Specifically, it is unclear what conditions are needed to apply Theorem 3.2 as Algorithm 1 is applied to a very specific online convex optimization problem. I believe Section 4 tries to highlight these conditions via Lemma 4.4, 4.5, 4.6, and 4.7, but without looking at the appendix, it is unclear where the conditions factor into proving the regret bounds. \n\nMoreover, in Section 5 where Theorem 3.2 is applied to the online portfolio selection problem, it is very unclear why the implicit optimistic LB-FTRL Algorithm 2 solves it. The first challenge in understanding how Algorithm 2 maps the OPS problem to Algorithm 1 is in the limited explanation in the mapping. From my reading, it seems that the only explanation in the main body is in the second sentence of the first paragraph in Section 5, “By the convexity of the loss functions, OPS can be reduced to an online linear optimization problem described in Section 3 with $v_t = g_t$ and $\\mathcal{X}$ being the probability simplex $\\Delta$.” Writing the optimization problem explicitly would be more clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments. \n1. **On stating Theorem 3.2 for generic losses:** Yes, it is possible to state Theorem 3.2, which is currently stated for online linear optimization, for generic convex losses. Denote the loss function in the $t$-th round by $f_t$. The only modification required is to replace the loss vectors $v_t$ in Algorithm 1 with the gradients $\\nabla f_t ( x_t )$. This follows from the fact that $f_t ( x_t ) - f_t ( x ) \\leq \\langle \\nabla f_t ( x_t ), x_t \\rangle - \\langle \\nabla f_t ( x_t ), x \\rangle$ by the convexity of $f_t$, showing that it suffices to solve the online linear optimization problem with $v_t = \\nabla f_t ( x_t )$. \"Linearizing\" the losses is a standard approach. See, e.g., Section 2.4 of Shalev-Shwartz (2012) and Section 2.3 of Orabona (2023). \n\n    We chose to state Theorem 3.2 in the current way to follow the style of Shalev-Shwartz (2012) and Orabona (2023), whereas Hazan (2022) does not explicitly mention linearization and hides that in the proofs. Please let us know if you think it necessary to restate Theorem 3.2 for general loss functions. The modification is easy to do. \n2. **Intuition on how the non-Lipschitzness issue is solved:** Indeed, as we focus on deriving data-dependent bounds, the issue we face is lack of smoothness rather than lack of Lipschitzness. The lack-of-smoothness issue is addressed by Lemma 4.6 and Lemma 4.7, which provide local-norm analogies of the definition of smoothness and the self-bounding property, respectively. \n\n    Based on our results, one can also obtain a worst-case $\\tilde{O} ( \\sqrt{ dT } )$ regret bound for online portfolio selection by FTRL with the log-barrier, with a constant learning rate, and without optimisim (a very simple special case of Algorithm 2). The regret bound then follows from Corollary 5.2 and Lemma 4.3. The non-Lipschitzness issue is solved by Lemma 4.3, showing that the gradients are bounded in dual local norms. \n\nReferences: \n- S. Shalev-Shwartz, Online Learning and Online Convex Optimization, 2012. \n- E. Hazan, Introduction to Online Convex Optimization, 2022. \n- F. Orabona. A Modern Introduction to Online Learning. 2023. "}, {"review_id": "4IN8rOWK7n", "reviewer": "Reviewer_cmFV", "summary": "The paper presents beyond-the-worst-case regret bounds for Online Portfolio Selection (OPS). In general online learning, beyond-the-worst-case bounds are established using structural assumptions on the loss functions, such as Lipschitzness and smoothness, but the loss functions in OPS are neither Lipschitz nor smooth, which is the main technical difficulty the paper addresses. To this end, local norm analogues of Lipschitzness and smoothness are established for OPS, and a generic optimistic FTRL algorithm with the log-barrier regularizer is proposed. Specializations of this algorithm achieve a gradient-variation-dependent bound and a $L^*$ bound, which are the first without the additional no junk bond assumption. In the worst case, these bounds match a type of classical regret-computation tradeoff. In better cases, these bounds are logarithmic in $T$, which is a substantial acceleration. ", "questions": "- Could the authors comment a bit more on the novelty of the smoothness characterizations (Lemma 4.6 and 4.7)? \n\n- I'm also generally wondering about the regret computation tradeoff in OPS. Are there lower bounds? ", "limitations": "The limitations are adequately addressed. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Online portfolio selection is an iconic problem in online learning, with plenty of recent progresses in its worst case characterization. The paper introduces classical types of data dependent bounds to this problem, which has a very clear and natural motivation. \n\n- The challenge of non-Lipschitzness and non-smoothness is technically nontrivial. The solution relies on establishing local counterparts of these properties, which is interesting, and could be of broader applicability. \n\n- The specific data-dependent bounds are novel without the additional no junk bond assumption. \n\n- Related works are discussed in depth, which gives the new contributions a nice context. ", "weaknesses": "Overall this is a good paper, and there isn't any major criticism I'd like to make. On less important issues, \n\n- The technical presentation of the paper could be improved. Currently there are quite a few of typos and unclear notations. For example, there's Algorithm 1 in the main paper, and an algorithm 1 in the appendix. $\\omega$ in Theorem 3.2 is not defined in the main paper. The notation $x(i)$ is used in line 201 but defined in line 227, ...\n\n- I think compared to data-dependent bounds in general online learning, the benefit of data-dependent bounds in OPS is a little less clear, particularly due to the existence of a computationally inefficient logarithmic regret algorithm. I would appreciate more discussions on computation, since the paper essentially considers a particular regret computation tradeoff. Is $\\tilde O(d)$ runtime and $\\tilde O (\\sqrt{dT})$ regret pareto-optimal for OPS in some sense? A numerical example would also be helpful, as it will make the computational savings over universal portfolio (and line 33 to 36) more clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. \n1. **Novelty of the Smoothness Characterizations:**\n    We are not aware of any similar results in the literature. The closest is perhaps the well-known local smoothness property of self-concordant functions. \n2. **Optimal regret-efficiency tradeoff:**\n    To the best of our knowledge, there is not a characterization of the optimal tradeoff between regret and computational efficiency for online portfolio selection. Zimmert et al. (2022) consider the currently best tradeoff for *existing* algorithms. \n3. **Typos:** Thanks for the careful review. We will correct the typos. \n4. **Benefit of data-dependent bounds:** This work is motivated by the high computational complexities of existing logarithmic-regret algorithms. Given that the optimal tradeoff between regret and efficiency remains unclear, we seek the opportunity to attain the optimal regret rate with moderate computational complexity. The results in this paper show there are indeed algorithms that automatically exploit such opportunities. If you agree with this argument, we will make this clearer in the revision. \n\nReference: \n- J. Zimmert et al., Pushing the efficiency-regret Pareto frontier for online learning of portfolios and quantum states, 2022. "}, {"review_id": "5fKVYw5hH2", "reviewer": "Reviewer_q9Qg", "summary": "This work studies online portfolio selection (OPS) problem and establishes regret bounds that is square-root dependent on some data-dependent quantities, namely, the cumulative loss of the best action or the variation of the gradients respectively, without lipschitzness or smoothness assumption. Although previous studies obtain regret bounds with logarithmic dependence on the same data-dependent factors, they require the lipschitzness assumptions, which this work circumvents by investigating the problem carefully and proposing alternative local-norm lemmas as substitutes for lipschitzness and smoothness conditions. Furthermore, this work designs a novel optimistic FTRL algorithm with a self-concordant function to cooperate with the local-norm techniques and validates that the prediction can be resolved in $\\tilde{O}(d)$ time pre round.", "questions": "See comments above.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper leverages the inherent structure of the problem and derives the first data-dependent regret bounds without lipschitzness or smoothness assumptions for the OPS setting.\n2.\tThe proposed optimistic FTRL algorithm is novel and interesting, which facilitates the application of local-norm techniques with optimism for this problem.\n3.\tThis paper is clearly written and presented well.\n\n", "weaknesses": "The OPS problem is fundamentally challenging, and I am glad to witness advancements in this field even if the results have not yet reached an optimal level. Below are some questions that emerged when I am reviewing the paper, and I would be appreciated if the authors can provide some feedback.\n\n1.\tOrdinarily, one might anticipate that data-dependent bounds would demonstrate a marked advantage over minimax optimal results in the best-case scenarios, such as when $V_T = 0$ or $L_T^\\star = 0$. But, by Theorem 6.1, when $ V_T = 0$, the algorithm can only assure $O(d\\log T)$ regret bound, just matching the minimax optimal bound. By Theorem 6.2, $L_T^\\star = 0$ will imply an even less optimal bound than the minimax result. However, these results do attain Pareto frontier optimality when balancing the optimality and efficiency under the best cases. I advise the authors to elaborate further on the motivation and highlight the efficiency of the proposed algorithms to make the contributions clearer.\n2.\tAs the authors noted in line 242, the term \"implicit\" might potentially mislead readers since it is commonly associated with another class of algorithms [Kulis and Bartlett, 2010]. It may be beneficial to consider a different nomenclature for the algorithm. \n3.\tI’m interested in the relationship between two data-dependent bounds. Indeed, some earlier study (see Zhao et al., 2021, Theorem 6) posits that a gradual variation dynamic regret can imply a small-loss dynamic regret in the analysis, for general convex, non-negative, and smooth functions. This result is also true for static regret. A natural question that arises from this is whether it's feasible for one algorithm to concurrently secure guarantees for both the gradual-variation bound and small-loss bound.\n\nReferences:\n\nBrian Kulis and Peter L. Bartlett. Implicit Online Learning. ICML 2010.\nPeng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization. ArXiv:2112.14368, 2021.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating the online portfolio selection problem and our work. \n1. **Benefit of data-dependent bounds:** This work is motivated by the high computational complexities of existing logarithmic-regret algorithms. Given that the optimal tradeoff between regret and efficiency remains unclear, we seek the opportunity to attain the optimal regret rate with moderate computational complexity. The results in this paper show there are indeed algorithms that automatically exploit such opportunities. If you agree with this argument, we will make this clearer in the revision.\n2. **Another name for Algorithm 2:** We agree with the comment. We will rename Algorithm 2 as “LB-FTRL with Multiplicative-Gradient Optimism”. The name is motivated by the fact that, unlike standard optimistic algorithms, we predict $x_t \\odot g_t$ instead of the gradient $g_t$ in each round.\n3. **Possibility of a small-loss gradual-variation bound:** Thanks for pointing out the reference. We had also noticed this work. \n    - Yes, we can construct an algorithm that satisfies a unified small-loss gradual-variation bound. It suffices to aggregate the outputs of Algorithm 3 and Algorithm 4 by Vovk's aggregating algorithm. Since the losses are mixable and there are only two experts, the regret of the resulting algorithm is bounded by $\\min \\lbrace R_{3, T}, R_{4, T} \\rbrace + \\log 2$, where $R_{i, T}$ denotes the regret of Algorithm $i$. \n    - The reference by Zhao et al. (2021) that you pointed out provides a more efficient approach for standard smooth losses. Unfortunately, the techniques therein do not directly apply to our case, because our \"self-bounding property\" (Lemma 4.7) includes an additional $\\alpha^\\star (x) e$ term. We will mention generalizing Zhao et al. (2021) as a future research direction. \n\nReference: \n- P. Zhao et al., Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization, 2021. "}, {"review_id": "Chi5Z62OT7", "reviewer": "Reviewer_Xwzr", "summary": "The paper considers the online portfolio selection problem. In this problem, one must allocate funds between d possible investment choices, with the goal of maximizing the total amount. In each round, the \"success\" of each choice is revealed, in the form of a ratio between new and old price, called price relative; these price relatives are adversarially chosen. The goal is to have low regret, in terms of the logarithm of total wealth, against any constant, fractional allocation of funds between the investment choices. \n\nIn general, where the number of rounds is T, existing work for this problem exhibits either polynomial running time in T and poly-logarithmic regret in T, or running time independent of T and regret polynomial in T (specifically, square root). \n \nThe paper considers a different approach, providing data-dependent bounds for the problem.\nThe paper presents three bounds w.r.t. the input: small-loss bound, w.r.t. the total loss of the optimal allocation; gradual-variation bound, w.r.t. the volatility of the gradients of the loss functions; and a second-order bound, w.r.t. some second-order statistics of the loss function. The first two appear in the body of the paper.\n\nThe paper presents an algorithm based on optimistic FTRL w.r.t. a log-barrier regularizer; the optimism refers to using an estimate for the upcoming loss function in choosing the allocation for the next time step. To my understanding, the algorithmic contribution of the paper is in the method for choosing the loss estimate. \n\nComments:\nLine 33: Maybe \"lower\" instead of \"faster\"\nLine 283: In the displayed equation, should be a_t instead of a\n", "questions": "Regarding Assumption 1, the paper correctly states that this could be ensured by normalizing the price-relatives vector, without affecting regret. However, this does affect the total loss of the adversary, which comes into play in the small-loss bound in Theorem 6.2. If I understand correctly, the assumption is thus nontrivial to make, which weakens Theorem 6.2. Is this the case? ", "limitations": "yes", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The online portfolio selection is an interesting problem, and obtaining data-dependent bounds for this problem seems natural. \nIn that sense, the paper does a comprehensive job and provides bounds w.r.t. three parameters. ", "weaknesses": "I have a concern regarding the small-loss bound, addressed in the questions for rebuttal. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful review. \n1. **Typos:** We will correct them. Thank you. \n2. **Concern on the small-loss bound:** If the price relatives are not upper-bounded by 1, then the cumulative loss in the small loss bound is defined with respect to the normalized price relatives. Hence, the assumption that the price relatives are upper-bounded by 1 does not weaken the regret bound. Thank you for pointing out this potential confusion. We did not notice that because of the notations, the remark following Assumption 1 is not sufficient. We will clarify this after Theorem 6.2 in the revision."}]

Author rebuttal:

Meta-review: This paper provides new results for the classic online portfolio selection problem. Specifically, the main result is a data-dependent regret bound is better than known bounds when the data are "easy", while having O(sqrt{dT}) regret in the worst case, with O(d) running time per iteration. Crucially, the algorithm doesn't need to assume bounded gradients (also known as the "no-junk-bonds" assumption). Technically, the paper introduces new analysis of optimistic FTRL with self-concordant functions, which are not necessarily barriers. While the worst case regret is quite suboptimal, all known methods which have O(d) running time per iteration have the same regret bound.

Overall, the reviewers appreciated the contributions of this paper, so I am happy to recommend acceptance. Please take the reviewer comments into account while preparing the final version. Specifically, it would be nice if the authors can include a statement for more general losses in their paper. This may help others to build on this work and highlight the techniques developed in the paper.
Decision: Accept (poster)