Universal Online Convex Optimization with $1$ Projection per Round

Summary

This paper introduces methods for constrained OCO which automatically achieve the optimal rate without knowing in advance whether the losses are convex, strongly convex, exp-concave, or smooth, while using only 1 projection per round. This is notable because the standard approach proceeds by combining several expert algorithms with a meta algorithm; in constrained settings these expert algorithms require implementing a potentially expensive projection. This work avoids projecting each of the expert algorithm iterates leveraging the constrained-to-unconstrained reduction of Cutkosky 2020.

Strengths

The paper addresses a clear and real problem that has been left unaddressed by the majority of literature on this topic. The approach is a pretty straight-forward modification of existing reductions, but uses them in a new and unexpected way.

Weaknesses

The main weakness is that the paper feels poorly factored. There is a very large number of back references to previous equations, and the paper would be very hard to read in print. To actually follow the math, it's almost necessary to read the paper with a pdf viewer which can display pop-up previews when hovering over links. I think this would be remedied by better factoring the results into lemmas and propositions. As noted, the approach is a fairly straight-forward modification of the results from Cutkosky \& Orabona (2018) and Cutkosky (2020), and essentially boils down to not dropping negative terms in the analysis, and then exposing matching terms in the regret decomposition. I think this is fine overall; these considerations are missing from the literature, and this is a fitting place for them to enter the literature.

Questions

Do you think there could possibly be a more abstract way to formalize these universal algorithms? The strange thing about these universal algorithms is that a whole new algorithm seemingly needs to be devised every time one wants to incorporate a new kind of loss (e.g. meta-grad -> mahler to handle strongly convex losses). The ideal result would more generally be a reduction which just passes the losses to each of the experts, maybe with some additional side-information, and lets them construct whatever surrogate loss they want with it. In this way there might just be one "final" paper on universal guarantees.

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes, the paper points out in the conclusion that the bounded domain / gradient assumption is a significant limitation that they hope to address in future work.

Summary

This paper addresses the challenge of online convex optimization with unknown smoothness properties of the loss functions, which can be convex, strongly convex, or exp-concave. The authors propose an algorithm that achieves regret bounds of order $\sqrt{T}$, $\log T$, and $d \log T$ respectively, while requiring only a single projection step per round on the original domain $\mathcal{X}$. Such projections can indeed be computationally expensive. Additionally, the authors present regret bounds with improvment for small losses. Most algorithms that achieve similar adaptive regret upper bounds rely on meta-algorithms that combine experts (running ONS or OGD with surrogate losses), inspired by the MetaGrad algorithm. Typically, these algorithms necessitate $\log(T)$ projection steps per round (one per expert), which can be computationally burdensome. Mhammedi et al. (2019) reduced this projection cost to $O(1)$ but at the expense of a $d \log T$ regret for strongly convex losses. To overcome this, the authors introduce new surrogate losses based on a black-box reduction technique by Cutkosky et al. (2018), which simplifies the constrained optimization problem on $\mathcal{X}$ to another domain, such as the Euclidean ball, where projections are easier.

Strengths

- The paper is well-written and offers valuable insights into the use of surrogate losses to adapt to strong convexity or exp-concavity. It may serve as a comprehensive entry point into the extensive literature on universal OCO algorithms. - Despite combining various existing techniques, the results are non-trivial and required solving technical challenges, especially for the strongly convex case. The authors introduce novel negative terms in the analysis to achieve their results. - Experiments included in the appendix demonstrate that the computational improvements can be significant.

Weaknesses

- The theoretical improvements may appear incremental, appealing to a niche audience interested. The improvement being only in the specific case of strongly convex $\log T$ regret with $O(1)$ projection steps. The primary high-level ideas in the algorithm and analysis are based on prior work. - The paper still relies on a meta-aggregation procedure, which, although theoretically effective, is not particularly elegant and maintains a per-round complexity of order $O(\log T)$. Achieving $O(1)$ complexity per round seems however highly challenging. - The convex rate is actually $O(\sqrt{T \log\log T})$, not $O(\sqrt{T})$ as stated in the results.

Questions

- The algorithm requires prior knowledge of the parameters $G$ and $T$, would simple doubling trick allow to tune these? - Your algorithm still requires O(1) projection steps on $\mathcal{X}$ and O(log T) projection steps on $\mathcal{Y}$. Do you think that projection free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS (up to deteriorating slightly the rate) to remove all projections (or at least the O(log T) on $\mathcal{Y}$) while still being adaptive to the smoothness?

Rating

6

Confidence

5

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors have addressed the limitations.

Summary

This paper studies universal OCO algorithms with fewer projections. Previous work either use $O(\log T)$ projections per round, or have a sub-optimal dependence on $d$ for strongly-convex loss. This work designs a new surrogate loss to achieve tight regret for Lipschitz convex/exp-concave/strongly-convex losses simultaneously, with only 1 projection per round.

Strengths

The technical contributions are solid: this paper makes a strict improvement over previous results. The paper is very well-written, clearly introducing the challenges and the main ideas. Details of the analysis and algorithm are nicely explained.

Weaknesses

The contribution seems somewhat incremental to me. The only improvement is a $d$ factor for strongly-convex loss. Such result is nice to know but I'm not sure how significant such it is. In addition, the technical novelty isn't significant either.

Questions

See weaknesses.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

See weaknesses.