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.
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.
Note 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.
This paper is generally well-written and easy to follow. The key finding, section 4.3, is easy to understand.
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.
To 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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.