Online Learning for Adversaries with Memory: Price of Past Mistakes
The framework of online learning with memory naturally captures learning problems with temporal effects, and was previously studied for the experts setting. In this work we extend the notion of learning with memory to the general Online Convex Optimization (OCO) framework, and present two algorithms that attain low regret. The first algorithm applies to Lipschitz continuous loss functions, obtaining optimal regret bounds for both convex and strongly convex losses. The second algorithm attains the optimal regret bounds and applies more broadly to convex losses without requiring Lipschitz continuity, yet is more complicated to implement. We complement the theoretical results with two applications: statistical arbitrage in finance, and multi-step ahead prediction in statistics.
The paper extends the notion of online learning with adversarial memory to the OCO framework. The authors propose two efficient algorithms: first one applies to (strongly) convex and Lipschitz functions while the second applies to convex functions, without requiring Lipschitz property. The authors complement their results with experiments.Originality- I will not question this aspect of the paper. The authors mostly adapt existing theory in online learning but do it in a clever way, which, if correct (I will come to this later) is worthy of acceptance. Significance- I believe the idea will be interesting to the online learning community. Clarity- I have some minor issues regarding the clarity of the paper. I will list them so that (hopefully) the authors find it easier to read. 1. A concrete example of a function which calculates loss based on last $m$ moves of learner would have been helpful in the introduction.The authors simply say "However, in coding, compression, portfolio selection and more, the adversary is not completely memoryless". While I am sure I can find examples in the references, the introduction should be more enticing and the paper self-containing. 2. Line 156- It is mentioned that f_t is convex if $\tilde{f}(x)= f(x,x,...,x)$ is convex. Considering $f_t$ is a multivariate function, should it not be that $f_t$ being convex naturally mean that it is jointly convex in all $m$ arguments? Otherwise, why claim $f_t$ to be convex? 3. Theorem 3.1- The regret is for Lipschitz continuous function with constant L (line 176). However, L does not even appear in the regret equation. Looking at the proof, it seems L has somehow been absorbed in \lambda and \sigma. This is very confusing to someone reading the main paper.And in line 705, why is the Lipschitz constant $\sqrt(\lambda) \sigma$? 4. Though I understand the more involved work is for (non)-Lipschitz functions, Algorithm 1. and its' proof is extremely simple when regularizer is $\ell_2$ norm (basically OGD). In fact, in OGD, two consecutive iterates $x_{t+1}$ and $x_t$ are close as long as the gradient is controlled (it is when the function is Lipschitz). Maybe the analysis of Alg.1 can be moved to the supplement with more discussion about Alg 2. in the main paper. 5. Why are \hat{g}_t exp-concave with \eta/4G^2 (line 893)? I understand its exp-concave but why with factor \eta/4G^2?Quality- My major concern is with the proof of one lemma. I am enlisting my concern here: 1. Lemma D.3- The crucial part of Alg.2 is the bound on the number of switches (As formally stated in Lemma D.4).So effectively, the proof goes through the following line of argument: Alg.5 is modified in Alg.6, which changes the way $x_{t+1}$ is sampled. Through a series of arguments, it comes to the inequality in Lemma D.2. Then Theorem 4.1 follows by using a bound on number of switches.My concern is with Lemma D.3. First of all, both Alg.2 and Alg.6 are being applied to exp-concave function $\hat{g}_t$ (Change the function $\ell_t$ to $\hat{g}_t$ in Alg.6). I dont think it is correct to claim Alg.2 is being applied to function $g_t$. The loss is being calculated in terms of $g_t$ but the update is based on $\hat{g}_t$, since $\hat{g}_t$ is exp-concave. So the only difference between Alg.2 and Alg.6 is how the sequence $x_t$ is being generated. Crucially, in Alg.6, $x_t$ is being sampled from $p_t(x)$. In Alg.2 (using the same exp-concave functions), $x_t$ is being generated from $p_t(x)$ w.p.1- (w_t(x_{t-1})/w_{t-1}(x_{t-1})) and $x_t=x_{t-1}$with complementary probability. Since $p_t$ is same density function in Alg.2 and Alg.6, how can the two sequences comefrom same distribution? I find that very much counter-intuitive, and this lies in the heart of analysis of Alg.2. Moreover, when i tried to go through the proof of Lemma D.3, i got stuck at the first line. Why is Line 947 true?Overall, I am not sure about the veracity of the claim. I am of course not claiming it is wrong but I think its crucial to verify the proof. I would request other reviewers/ PC members to check the proof of Lemma D.3 at least.Update: After discussion, I have understood the proof of Lemma D.3. I have updated by rating. Assuming that the results have not appeared anywhere before, the paper should be accepted