Universal Online Convex Optimization with $1$ Projection per Round

Many thanks for the constructive reviews! We will revise our paper accordingly.

Q1: The main weakness is that the paper feels poorly factored.

A1: We apologize for the confusion caused by the numerous references to previous equations in this paper. Due to page limit, we attempted to include all the math equations of our key ideas in this paper, which made it difficult to follow in the printed version. We promise to polishing our writing and will follow your suggestion to factor the results into lemmas and propositions.

Q2: Do you think there could possibly be a more abstract way to formalize these universal algorithms?

A2: Yes, there do exist a general framework in the studies of universal online learning that allows expert-algorithms to process the original functions [Zhang et al., 2022]. We are pleased to briefly describe the basic idea of their method here. Following the two-layer structure, the regret can be decomposed to the meta-regret and the expert-regret, that is,

where $x_t$ and $u_t$ denote the output of the meta-algorithm and expert in the $t$-th round. To bound the expert-regret, we can directly use existing online algorithms as the expert-algorithms that achieve optimal regret bounds for different types of convex functions, e.g., $O(\sqrt{T})$ and $O(\log T)$. To control the meta-regret, their meta-algorithm employs the linearized loss, i.e., $l_t(x)=\langle \nabla f_t(x_t), x-x_t\rangle$, to measure the performance of each expert. Furthermore, they also require the meta-algorithm to yield a second-order bound in terms of $l_t(\cdot)$. In this way, the meta-regret is small for exp-concave functions and strongly convex functions, i.e., $O(\log\log T)$, and is also tolerable for convex functions, i.e., $O(\sqrt{T})$. By incorporating existing online algorithms as experts, their approach inherits the regret of any expert designed for strongly convex functions and exp-concave functions, and also obtains minimax optimal regret for convex functions. We feel that this framework is close to the "final" paper on universal guarantees that you mentioned.

We acknowledge that our work indeed follows this universal framework. However, to address new problems, we have to make essential modifications to this framework. In this paper, we focus on reducing the projection complexity of universal online learning, and have made innovative technical contributions based on this framework. These include specially designed expert-losses for expert-algorithms that handle strongly convex functions, and novel theoretical analysis that advances universal algorithms and the black-box reduction.

Many thanks for the constructive reviews! We will revise our paper accordingly.

Q1: Would simple doubling trick allow to tune prior knowledge of the parameters $G$ and $T$?

A1: In fact, the doubling trick enables our proposed algorithm to avoid the prior knowledge of $T$, at the cost of an additional $\log T$ in the regret bound. However, this trick is inadequate for removing the requirement of the prior knowledge of $G$, as the variability in function gradients is unknown. Therefore, designing lipschitz adaptive online learning algorithms is a highly challenging task and merits further exploration in the future.

Q2: Your algorithm still requires $O(1)$ projection steps on $\mathcal{X}$ and $O(\log T)$ projection steps on $\mathcal{Y}$.

A2: We would like to clarify that, in contrast to the expensive projection operations onto the complicated domain, projection operations on the surrogate domain $\mathcal{Y}$ are much cheaper and can be considered negligible. In this work, we construct a ball $\mathcal{Y}=\\{x | \Vert x\Vert\leq D \\}$ as the surrogate domain. For the OGD algorithm, the projection operation of the reduced algorithm on $\mathcal{Y}$ can be realized by a simple rescaling, i.e., $y_t = \hat{y}_t$ if $\Vert \hat{y}_t\Vert \leq D$; otherwise $y_t=\hat{y}_t \cdot \frac{D}{\Vert \hat{y}_t\Vert}$, where $\hat{y}_t$ denotes the unprojected decision and $y_t$ denotes the decision on the ball $\mathcal{Y}$. For the ONS algorithm, there exists an efficient implementation of ONS in the literature, where the time-consuming projection operation can be replaced by a more efficient singular value decomposition [Lemma 7, Mhammedi et al., 2019]. After combining all the experts' decisions by a meta-algorithm, we project the solution in $\mathcal{Y}$ onto $\mathcal{X}$, which is the only projection onto $\mathcal{X}$ per round.

Q3: Do you think that projection-free algorithms such as variants of Online Frank Wolfe could be used instead of OGD and ONS to remove all projections while still being adaptive to the smoothness?

A3: Thanks for your insightful comments! We can choose projection-free algorithms, such as variants of Online Frank Wolfe, as the expert-algorithms. However, given the current studies on projection-free algorithms (summarized in the table below), this approach may suffer a deterioration of the regret bound and can not handle certain cases.

More specifically, as is shown in the table, in the literature, there are no suitable projection-free algorithms for exp-concave functions, neither for strongly convex and smooth functions. Moreover, when functions are smooth, existing projection-free algorithms are unable to achieve problem-dependent bounds, such as the small-loss bounds in this work.

Finally, we would like to highlight that although using projection-free algorithms can remove all projections, they may not achieve greater efficiency based on the universal framework. Specifically, most projection-free algorithms, such as OFW and its variants, replace the original projection operation with a linear optimization step. Since the universal framework requires maintaining $O(\log T)$ expert-algorithms, this approach needs to perform $O(\log T)$ linear optimization steps per round, which can be time-consuming when $T$ is large.

References:

[1] Hazan and Kale. Projection-free Online Learning. ICML, 2012.

[2] Hazan and Minasyan. Faster Projection-free Online Learning. COLT, 2020.

[3] Wan et al. Projection-free Online Learning over Strongly Convex Sets. AAAI, 2021.

[4] Garber and Kretzu. Projection-free Online Exp-concave Optimization. COLT, 2023.

Many thanks for the constructive reviews. We will revise our paper accordingly.

Q1: The significance of our result.

A1: We emphasize that the $d$-dependence is significant in online learning studies. We provide the following elaborations and will also revise the paper to highlight this significance more clearly.

• For online convex optimization, knowing the minimax optimality regarding $d$ and $T$ is a fundamental question to investigate. It is well-known that for convex/exp-concave/strongly convex functions, the minimax rate is $O(\sqrt{T})$ , $O(d\log T)$ and $O(\log T)$. Therefore, in universal online learning, achieving the regret bounds that match these minimax rates is also of great significance. As explicitly mentioned by the authors of MetaGrad, van Erven et al., the extra factor $d$ in the regret bound for strongly convex functions is a "real limitation". Our results have successfully achieved minimax optimality in terms of $d$ and $T$ through non-trivial technical ingredients.
• Numerous studies in online learning are dedicated to improving regret bounds by reducing dependence on the $d$. For example, prior work on private OCO achieved an $\tilde{O}(\sqrt{dT}/\epsilon+\sqrt{T})$ regret bound [2], where $\tilde{O}(\cdot)$ hides polylog factors in $T$. In a subsequent study, this result is improved to $\tilde{O}(d^{1/4}\sqrt{T}/\sqrt{\epsilon}+\sqrt{T})$ [3], which is a significant advancement. Other examples include improving $d$-dependence for multi-armed bandits, bandit convex optimization, etc.

Therefore, we believe that the result in this paper is significant.

Reference:

[1] van Erven et al. MetaGrad: Adaptation using Multiple Learning Rates in Online Learning. JMLR, 2021.

[2] Jain et al. Differentially Private Online Learning. COLT, 2012.

[3] Kairouz et al. Practical and Private (Deep) Learning Without Sampling or Shuffling. ICML, 2021.

Q2: The significance of our technical novelty.

A2: We would like to take this chance to emphasize our technical novelty.

• Challenge: This work focuses on universal algorithms with $1$ projection per round. Prior work applied the black-box reduction to existing universal algorithm, i.e., MetaGrad, which achieves optimal regret for exp-concave and convex functions with $1$ projection per round. The basic idea is to cast the original problem on the constrained domain $\mathcal{X}$ to an alternative one of the surrogate loss on a simpler domain $\mathcal{Y}$. To handle strongly convex functions, a straightforward way is to use a universal algorithm that supports strongly convex functions, e.g., Maler, as the black-box subroutine. However, this black-box approach fails in deriving a tight regret bound for strongly convex functions, because we are unable to bound this term,

where $y_t\in\mathcal{Y}$ is the fake decision on the surrogate domain, and $x_t\in\mathcal{X}$ is the true decision on the feasible domain. The above term is unmanageable since $\Vert y_t-x\Vert\geq\Vert x_t-x\Vert$. To the best of our knowledge, this technical challenge is entirely new for both universal algorithms and the black-box reduction, with no prior work to draw upon.

• Analysis: In this work, we address the above challenge in two steps. First, we introduce a novel meta-expert decomposition and, motivated by this, we specifically design a novel expert-loss. This expert-loss offers the advantage of bounding the meta-regret by the following term,

Second, to bound the above difference, we dig into the properties of the surrogate loss of the black-box reduction. The technical novelty of our theoretical analysis is that the second-order bound in terms of the decision on the surrogate domain (fake decision) can be converted into the one of the decision on the feasible domain (true decision), at the cost of adding an addition positive term $\Delta_T$ (See Lemma 7 for details), that is

where $\Delta_T$ is defined in our paper. Furthermore, compared to previous work on black-box reduction, we also prove a tighter connection between the original function and the surrogate loss (See Lemma 3 for details), which introduces a negative term $-\Delta_T$ that can automatically offset the cost arising from the aforementioned conversion. By combining these two bounds, we are able to control the meta-regret under the strong convexity condition, thus ensuring that it does not affect the algorithm's optimality. Therefore, we believe that the technical novelty in our theoretical analysis is valuable for both universal algorithms and the black-box reduction.

• Applications: Two-layer algorithms are widely adopted in modern online learning, including universal online learning studied in our paper and also non-stationary online learning. Therefore, our developed techniques can be also useful for non-stationary online learning, especially regarding strongly convex/exp-concave functions. For example, Baby et al. [2022] propose a two-layer algorithm with optimal dynamic regret for strongly convex functions, which also suffers from $O(\log T)$ projection complexity. By applying our technique to a strongly adaptive algorithm with a second-order bound, it is hopeful to reduce the number of projections of their method to $1$ per round.

Overall, we believe that the technical novelty of our work is significant. Thanks for your comments, and we will revise the paper to further highlight the technical novelty.

References:

[4] Baby and Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. AISTATS, 2022.