Unconstrained Dynamic Regret via Sparse Coding

Summary

This paper studies adaptive online convex optimization, with focus on adapting to unbounded domain and arbitrary time-varying comparator sequence. Different from previous studies which mostly consider the path-length as the prior which appears in the dynamic regret bound, this paper aims to enlarge the range of priors. For a given dictionary of orthogonal feature vectors, it is shown that an $\tilde{O}(\sqrt{E\cdot \text{Sparsity}_H})$ regret bound can be achieved, which not only recovers previous results on path-length, but also allows more flexibility. This paper also strictly improves the result of JC22 by replacing comparator-dependent terms in the regret bound by strictly smaller ones.

Strengths

This paper makes solid contributions to adaptive online convex optimization. It extends the scope of comparator adaptivity from the traditional path-length, to other priors on the comparator via a novel sparse coding framework. The achieved bounds involve more refined dependence on the comparator, and are never worse than previous results. In particular, the special case of the wavelet dictionary improves the SotA result in JC22.

Weaknesses

The main weakness is the unclear presentation of technical results, which are hard to fully understand and interpret. Though the claimed results seem promising, I have to vote for rejection for now because I can't verify the correctness without a better understanding of the results. Here are some confusions I met. For the size 1 dictionary case, isn't the assumption too strong which seems to trivialize Lemma 2.1? In line 211, the comparator is assumed to lie in the span of a single vector $h_{1:T}$, which is just a scaling of the vector $h_{1:T}$. Since the dictionary is fixed and revealed to the player, the range of potential comparators seems very restricted (the degree of freedom is just one through $\hat{u}$). The same issue carries over to the main result Theorem 1, which assumes the signal $z^{(n)}$ lies in the span of a single vector. Even if the reconstruction error creates certain flexibility, to achieve vanishing regret one still needs to guarantee the comparator is very close to $\sum_{n=1}^N z^{(n)}$, which seems under-expressive: for a given dictionary, the overall degree of freedom is just $n$, while for arbitrary time-varying comparators the degree of freedom is $dT$. Two examples are presented right after the main theorem. The case of static regret is well understood. However, I feel the case of orthogonal dictionary requires more technical details, at least to readers unfamiliar with signal processing. For example, what exactly does the "orthogonal" means here? (which vector is orthogonal to which?) It would be great if you can provide an intuitive example here to show the power of your method over previous results. I'm also concerned with how to choose the dictionary. It seems a good choice of dictionary requires prior knowledge. It's not clear to me if one can adapt to a class of dictionaries.

Questions

Can you provide more technical details to address my questions discussed above? In particular, can you provide 1: an example of dictionary that recovers the traditional path-length case, and 2: an example of dictionary that corresponds to some other prior different from path-length? Can you provide details on using the Fourier dictionary to tackle periodic environments? It looks interesting to me because the naive idea of setting $H_t=(-1)^t I_d$ won't work.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

The presentation of technical results is not very clear.

Summary

The problem that this paper tries to tackle is the unconstrained online convex optimization with dynamic regret. Previous works usually assume that the comparator sequence is arbitrary and maybe time-varying with some fixed form of comparator measurement in the final dynamic regret bound. For this paper, it proposes a new way of the comparator measurement by first using a pre-defined subspace (by the users) to characterize the comparator sequence and then upper bound the dynamic regret in terms of the pre-defined subspace complexity as well as the reconstruction error between the subspace and the comparator sequence. It shows that for the almost static environment, the proposed algorithm + wavelet constructed subspace could have better regret than the existing works' in (maybe) the constant part.

Strengths

1) It provides the researchers a new perspective of measuring the comparator sequence when upper bounding the dynamic regret, which is interesting and useful in real applications. 2) The specific wavelet based subspace version could result in a regret better than the existing works' with (maybe) smaller constant part.

Weaknesses

1) The proposed algorithm framework only moves the dynamic regret from previous works in the constant value part. And in order to compare the actual improvement in terms of the constant part, the author/s need to provide the complete regret result comparison instead of an order O() based one. 2) The paper result depends heavily on the existing work [MK20], and the subspace based comparator sequence measurement is the only part that makes it interesting, although previous works like [HW15, ZLZ18] has already shown such an idea as pointed out by the author/s. 3) The author/s explained the motivation of tackling unconstrained dynamic setting rather than the constrained one. But for the finite range argument in the paper, more often than not, the finite range usually comes from the requirement of the model output and not just some heuristic estimation. I think it's better to also provide some examples to demonstrate the motivation of this paper.

Questions

1) The proposed algorithm requires the user to provide the subspace, which is very critical for the final dynamic regret result. If the user provided subspace is not good enough, does that mean the resulted algorithm will have bad performance? If so, how to guarantee the performance? 2) Since the proposed algorithm depends on the Algorithm 3 a lot, do you think it may make more sense to move Algorithm 3 from the Appendix to the main paper?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

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.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

In this paper, the authors examine the dynamic regret of Online Convex Optimization (OCO) within the context of unbounded comparator sequences. To address this issue, they introduce a novel framework of sparse dictionary coding for online optimization. Following this, the authors provide theoretical proof for the regret bounds applicable to different types of dictionary matrices - the general dictionary matrix, orthogonal dictionary matrix, and the Haar wavelet dictionary matrix. Of notable mention is the result pertaining to the Haar wavelet dictionary matrix, where the authors establish a regret bound that surpasses the current state-of-the-art.

Strengths

- Originality & Significance: The introduction of the sparse coding framework for Online Convex Optimization (OCO), complemented with the corresponding proof, is highly innovative. Furthermore, considering the dynamic regret of OCO in the unbounded domain is very crucial. The result that the authors obtained is related to the comparator average, first-order variability, and second-order variability, rather than the path length. This indicates that the authors have achieved smaller dynamic regret under more adaptive conditions, thereby enriching optimization theory within the community. - Quality & Clarity: The work is clear, well written, and technically sound.

Weaknesses

- Comparing the proposed method with the meta-expert optimistic online gradient descent method as described in [1] could be beneficial. Particularly in Examples 1 and 2, it appears that the meta-expert optimistic online gradient descent method can also achieve a regret of $\mathcal O(\sqrt T)$, considering the path-length is actually $\mathcal O(\sqrt T)$. This comparison might offer a broader perspective. - I'm concerned about the computational complexity of $\mathcal O(d\log T)$ for high-dimensional problems, especially when compared to the $\mathcal O(\log T)$ complexity of both the meta-expert OGD and the meta-expert optimistic OGD methods. If possible, an in-depth discussion on this issue would be helpful for readers. - Additionally, the main text seems to miss Algorithms 3-5. This omission may cause a minor confusion for readers during their first read. Rectifying this could help in enhancing the flow and clarity of the paper. Ref: [1] P Zhao et.al., Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization.

Questions

See above discussions.

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.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

This paper studies the universal dynamic regret minimization problem with the unconstraint decision domain. The authors proposed the sparsing coding framework, which converts the dynamic regret minimization problem in the time domain into a static regret minimization problem in the transfer domain. The comparator-adaptive static regret bound in the transfer domain implies a dynamic regret bound in the time domain. Specifically, by choosing the dictionary as the Haar wavelet base, this paper achieves improved dynamic regret bound with better dependence on the range of the comparator sequence. Several concrete examples are provided to illustrate the superiority of the proposed bound.

Strengths

+ This paper provides a novel framework to obtain universal dynamic regret bound via sparsing coding. The conversion from comparator-adaptive static regret bound to dynamic regret bound in the time domain is interesting to me. + This paper achieves improved universal dynamic regret bound with the new framework, which is strictly better than the existing results. Several examples are provided to illustrate the advantages of the proposed bound. + This paper is well-written and provides a sufficient discussion of the related literature.

Weaknesses

I do not find a major weakness in the paper, but there are still some minor comments: - about the general formulation (Eq. (5)): it would be nice to mention that the dynamic regret bound (Eq.(5)) is not universal dynamic regret bound in general as it only holds for the comparator $u_{1:T}\in\mbox{span}(h_{1:T})$. The universal dynamic regret bound can only be achieved with an appropriate choice of the dictionary. - about the examples: this paper has listed several examples with the specific choice of the comparator sequence to show the superiority of the proposed bound. However, since the main focus of this paper is the universal dynamic regret, it is unclear in which situation the listed comparator sequence is an appropriate benchmark that can minimize the right-hand side of Eq (2). I suggest the authors provide more concrete examples to illustrate the advantage of the proposed bound with certain specific loss functions.

Questions

- could you provide more concrete examples to illustrate the superiority of the proposed bound? (please refer to the second point of the weakness for more details) - is it possible to achieve the $\tilde{O}\left(\Vert \bar{u}\Vert\sqrt{T}+\sqrt{P\bar{S}}\right)$ bound without the knowledge of $T$. Could you highlight what is the main difference to obtain such a bound?

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

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

One of the main limitations of the paper is that the tightness of the proposed bound is still unclear. The authors discuss this issue at the end of the paper.

Reply to Authors

Thank you for your detailed reply. In my opinion, the general result seems less interesting than its special cases: to recover the general dynamic setting, the algorithm requires $dT$ feature vectors, which is unpractical. On the other hand, the Haar wavelet version does provide some solid improvements over previous results. Though this work has certain limitations currently, the signal-processing perspective is novel and promising, which may open a new avenue for future research. I have updated my score accordingly.