Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability

Thanks for your very careful review and pointing out two technical problems. We have provided a detailed proof for equation (13), and clarify that our Theorem 1 indeed requires the mixability of loss functions over $\mathbb{R}^d$. These issues will not affect the key contributions of our paper, but we acknowledge that they were not stated with sufficient precision. We will carefully revise the paper to address these imprecisions and ensure clarity.

Q1: the optimal solution of line 959.

A1: Thanks for the detailed inspection of our proof. Here, we provide a more thorough explanation of why equation (13) represents the optimal solution.

Proof. First, observe that $m_{sq}(P, y)$ is constant for a given value of $y$. Let us define $M_1 = m_{sq}(P, B)$ and $M_2 = m_{sq}(P, -B)$. The optimization problem in line 959 can then be reformulated as:

$~~~~~~~$ \arg\min_{z \in \mathbb{R}^d} \max\{(z - B)^2 - M_1, (z + B)^2 - M_2\}. $$

Define the functions $g_1(z) = (z - B)^2 - M_1$ and $g_2(z) = (z + B)^2 - M_2$. We have the follow close-form solution for the inner optimzation problem:

$~~~~~~~$ h(z) = \max\{g_1(z), g_2(z)\} = \begin{cases} g_1(z), & \text{if } z \leq z_*, \\ g_2(z), & \text{otherwise}, \end{cases} $$

where $z_* = \frac{M_2 - M_1}{4B}$. We now analyze three separate cases:

1. When $-B \leq z_* \leq B$:

   • For $z \in (-\infty, z_*]$, $h(z) = g_1(z)$, which is decreasing since $z_* \leq B$.
   • For $z \in [z_*, \infty)$, $h(z) = g_2(z)$, which is increasing since $z_* \geq -B$.

   Hence, the minimum of $h(z)$ is achieved at $z = z_*$.

2. When $z_* < -B$:

   • On $(-\infty, z_*]$, $h(z) = g_1(z)$ remains decreasing, and the minimum in this interval is at $z = z_*$.
   • On $(z_*, \infty)$, the minimum of $h(z)$ is at $z = -B$ since $h(-B) = g_2(-B) = -M_2$.

   Under the condition $z_* \leq -B$, one can verify that $h(-B) \leq h(z_*)$, so the overall minimum is attained at $z = -B$.

3. When $z_* > B$: By symmetry to the previous case, the minimum of $h(z)$ occurs at $z = B$ using the same reasoning.

By combining all three cases, we can show that the optimal solution is given in equation (13). We will clarify this reasoning in the revised version of the manuscript. $\blacksquare$

Q2: ".... it actually relies on stronger assumptions, ...Definition 2..., ...Theorem 1..." ($\mathcal{W}$ versus $\mathbb{R}^d$).

A2: Thanks for pointing out this issue. Theorem 1 indeed requires the mixability of loss functions over $\mathbb{R}^d$. We apologize for the confusion caused by the imprecise statements. We now describe the assumptions and decision domain more precisely.

• On assumption: Our assumption for Algorithm 1 is that the loss function is mixable over $\mathbb{R}^d$, which is necessary due to the use of a Gaussian prior in the algorithm. This assumption is satisfied by several commonly used curved loss functions in online learning, such as the squared loss and logistic regression loss, as discussed in Examples 1 and 2 and elaborated on in Section 4. Moreover, while the algorithm maintains a distribution over $\mathbb{R}^d$, we emphasize that for certain losses—such as the squared loss—the resulting final predictor $w$ can still lie within the domain $\mathcal{W}$, as shown in Section 4.1.
• On decision domain: In the generic algorithmic template, we allow the improper learning where the predictor $\mathbf{w}_t$ is outside the domain $\mathcal{W}$, while the comparator remains constrained within $\mathcal{W}$. Therefore, the proposed method may be improper depending on the loss function. For the squared loss, we obtain a proper learning algorithm, but for least-squares regression and logistic regression, the method should be considered improper, as discussed in Section 4.

To ensure that the assumptions and problem setting are clearly presented for the generic template, we will add a new subsection at the beginning of Section 3 to explicitly state the assumptions and capabilities of the learner. We will add the proofs for equation (13) in the paper.

Please consider updating the score if our responses and the additions in the revised version have adequately addressed your concerns. Thank you!

Thanks for your expert comments! We will address your main concerns regarding the literature comparisons. Without a doubt, Baby and Wang pioneered the line of dynamic regret for exp-concave/strongly convex functions. While we attempted to make a comparison, we unfortunately missed two relevant references, which will be included in the revised version. Moreover, we will add a paragraph discussing the limitations of fixed-share-type methods, which is attached at the end of this rebuttal.

Q1: "requires to know the form of losses beforehand"

A1: Thank you for pointing this out. Yes, constructing the mixability mapping requires focusing on specific loss forms. While this may be a limitation of mixability-based methods, the form of loss is often predetermined in many applications. Examples include online nonparametric regression, online classification, and LQR control, as the reviewer noted. We will clarify this in the next revision

Q2: "current work assumes gradient Lipschitnzess for the losses"

A2: Thank you for the comments. In Theorem 1, we state that $\beta$-smoothness is required to achieve the improved bound. We believe this is a mild assumption, as many curved losses, like those in Section 4, are smooth. That said, removing the smoothness assumption, as done by Baby and Wang et al. (2022), remains a quite interesting question. We will clarify this comparison in the next revision.

Q3: "Results of Baby and Wang 2021, 2022 can also work with sleeping experts style experts."

A3: Currently, achieving $O(\log T)$ time complexity for the fixed-share method is challenging due to the need to add a small portion of the prior distribution $N_0$ at each iteration. We will clarify the time-complexity comparison in the revision.

Q4: two missing references and comparisons

• unaware about the following important references...
• Table 2: comparison regarding run-times as well as the inclusion of prior works.

A4: We will definitely include these two papers and update the table to include the time complexity of the compared methods.

$\dagger$ Indicates that the time complexity can be improved to $O(\log T)$ using more refined geometric covering techniques.

Q5: losses that are mixable but not exp-concave in a compact domain?

A5: To our knowledge, common mixable losses, like squared loss, logistic loss are also exp-concave with generally larger coefficients. A key difference is that the mixability coefficient $\eta_{\mathtt{mix}}$ typically does not depend on the diameter of the decision domain $\mathcal{W}$, whereas the exp-concavity coefficient $\eta_{\mathtt{exp}}$ often does. For example, the logistic loss is 1-mixable over $\mathbb{R}^d$ but only $e^{-D}$-exp-concave within a bounded domain $\mathcal{W}$ of diameter $D$. Consequently, mixability-based results may extend to unconstrained comparators, while exp-concavity-based methods generally require bounded domains.

[Revision: Section 4.4] Limitation and Future Work: Although our method achieves improved dynamic regret without relying on KKT-based analysis, there remain several directions for improvement. First, regarding time complexity: our method matches the $O(t)$ complexity of Baby and Wang et al. (2021, 2022) for the squared loss. However, prior work can further reduces this to $O(\log T)$ by using the sleeping expert algorithm with a geometric cover, incurring additional multiplicative logarithmic factors in regret. Incorporating this idea into the fixed-share update is a promising direction. Second, while common curved losses like squared loss and logistic regression are smooth, the analysis by Baby and Wang et al. (2022) does not require smoothness. Removing the smoothness assumption in mixability-based analysis remains an interesting theoretical challenge. Finally, to construct the mixable prediction $z_{\mathtt{mix}}$, mixability-based methods require the loss function to have a specific form, unlike the approach by Baby and Wang et al. Although this condition holds in many applications—such as online nonparametric regression, online logistic regression, and LQR control—it is worth exploring whether we can aggregate distributions efficiently using exp-concavity instead of mixability.

We will add these discussions and include a fair comparison to Baby and Wang's line of work. Please consider updating the score if our responses and the additions have adequately addressed your concerns. Thank you!

We thank the reviewer for appreciating the novelty of our methods and for the constructive suggestions. In the revision, we will include a more detailed comparison with Baby and Wang (2021) in the introduction, highlighting the issue of proper learning and the underlying assumptions. Below, we address the questions regarding the differences in proof techniques.

Q1: The manuscript would benefit from a more detailed comparison of the proof techniques to further legitimize your claims.

A1: Thank you for the helpful comments. Compared with Baby and Wang (2021) and subsequent literature, our work adopts a completely different analytic framework to achieve an improved dynamic regret bound. This distinction is evident in both the algorithmic design and the theoretical analysis.

• From the perspective of algorithmic design, the main challenge is how to adapt to non-stationary environments without prior knowledge of $V_T$. Baby and Wang (2021) and the subsequent work address this by employing a strongly adaptive algorithm to ensure adaptivity. In contrast, our method leverages the idea of fixed-share updates over a continuous space. This fundamental difference in algorithmic approach leads to a completely different proof technique in the analysis.

• On the theoretical side, the core challenge in Baby and Wang (2021) lies in proving improved dynamic regret for a strongly adaptive algorithm. This requires using KKT conditions to characterize an offline optimal sequence and demonstrating that a strongly adaptive algorithm can track this sequence with low cost. In contrast, our analysis is based on the concept of mixability. By carefully designing the comparator distribution $Q_t$, we are able to directly establish the optimal improved dynamic regret bound.

We will clarify these points in the revision at the introduction level.

We thank the reviewer for very helpful comments. The main concerns are about i) presentation and ii) technical questions on the construction of mixability prediction for general functions. We first provide a concise answer and will expand the details later.

• [On Presentation] Our paper indeed requires much improvement, and we will enhance the presentation according to your constructive suggestions. Specifically, we will: include a subsection for problem formulation, reorganize the presentation of algorithms, and expand on the implementation of key conditions, etc. These changes aim to ensure the paper is easier to read.
• [On mixability prediction] For several common functions of interests (like square loss for regression, logistic loss for classification), the mixability prediction can be explicitly and efficiently constructed. For other ones, there may not have a close-form and one can obtain a feasible prediction by solving min-max optimization problems.

Q1: one paper presentation and assumptions

• "paper should have a (sub)section devoted to problem formulation"
• "...do you need W to be bounded? Do you need $f_t$ to have some smoothness properties?"

A1: In the original submission, we stated the assumptions within the theorem statements. For Theorem 1, it requires the loss functions to be $\eta$-mixable and $\beta$-smooth, along with the boundedness of the comparator domain. One potential confusion is that we allow improper predictions, that is, the predictor $\mathbf{w}_t$ can be unconstrained or take a nonlinear form—such as equations (14) or (15), which are used for least squares and logistic regression.

Thanks for your comments, we will revise the paper to consolidate all assumptions and the problem setting into a separate subsection at the beginning of Section 3 for improved clarify.

Q2: about algorithm presentation

"first introduced Algo1, which gives no explanation on implementation issues, and only discusses how to implement it after two sections"

A2: The goal of Section 3.1 is to present a generic algorithmic template along with conditions that guarantee improved dynamic regret. However, we agree that deferring the discussion of specific implementations may make the algorithm less accessible. In light of this, we plan to add the following remark in Section 3.1 to provide earlier insight into the implementation:

[Revision at Section 3.1]: Remark 1: Condition (4) is equivalent to the mixability condition defined in Definition 2, which ensures that for any function that is mixable over $\mathbb{R}^d$, a predictor satisfying condition (4) always exists. In the context of online prediction with a loss function of the form $f_t(\mathbf{w}_t) = \ell(\mathbf{w}_t^\top\mathbf{x}_t, y_t)$, where $(\mathbf{x}_t, y_t)$ is the feature-label pair, Vovk (1999, Equations 11 and 12) and Cesa-Bianchi and Lugosi (2006, Proposition 3.3) provide a general optimization framework for constructing such predictors (which may be improper). Moreover, for the squared loss and logistic loss, closed-form constructions of the predictor are available; these are discussed further in Section 4.

Q3: about the condition (4)

• ... it is still challenging to see how the algorithm can be implemented for general cost functions, especially the condition (4)...

• the computation complexity of the proposed method, especially when the cost functions are in general form.

A3: As mentioned in the response to Q2, for the online prediction problem where $f_t(\mathbf{w}) = \ell(\mathbf{w}^\top\mathbf{x}_t, y_t)$, Vovk (1999, Equations 11 and 12) and Cesa-Bianchi and Lugosi (2006, Proposition 3.3) provide a general min-max optimization framework for constructing predictions when $\ell$ is a mixable loss function. However, the optimal solution to this optimization problem depends on the specific structure of the loss function.

Q4: "...there is no simulation provided..."

A4: Dynamic regret of curved functions is a very challenging and fundamental theoretical problem in non-stationary online learning, and our primary focus has been on the theoretical aspect. Nonetheless, we are happy to include additional experiments in the revised version to further support our method.

Q5: the paper should also review the dynamic regret analysis for OCO with strongly convex costs

A5: Thanks for bringing this paper to our attention. It studies dynamic regret with switching costs, which is an interesting and complementary direction to our work. We will incorporate a discussion of this paper in the next version.

Although the current presentation indeed has certain unclear issues, we believe the core (technical) contributions are interesting and valuable to the community. We will ensure a substantial revision to improve the clarity. Please consider updating the score if these responses have properly resolved your concerns. Thanks!