Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions

Nima Eshraghi, Ben Liang

Abstract

The performance of online convex optimization algorithms in a dynamic environment is often expressed in terms of the dynamic regret, which measures the decision maker's performance against a sequence of time-varying comparators. In the analysis of the dynamic regret, prior works often assume Lipschitz continuity or uniform smoothness of the cost functions. However, there are many important cost functions in practice that do not satisfy these conditions. In such cases, prior analyses are not applicable and fail to guarantee the optimization performance. In this letter, we show that it is possible to bound the dynamic regret, even when neither Lipschitz continuity nor uniform smoothness is present. We adopt the notion of relative smoothness with respect to some user-defined regularization function, which is a much milder requirement on the cost functions. We first show that under relative smoothness, the dynamic regret has an upper bound based on the path length and functional variation. We then show that with an additional condition of relatively strong convexity, the dynamic regret can be bounded by the path length and gradient variation. These regret bounds provide performance guarantees to a wide variety of online optimization problems that arise in different application domains. Finally, we present numerical experiments that demonstrate the advantage of adopting a regularization function under which the cost functions are relatively smooth.

Introduction

In Online Convex Optimization (OCO), a decision-maker iteratively chooses points to minimize a cumulative cost that evolves over time. Success in these environments is measured by dynamic regret, which compares the algorithm's performance against a sequence of optimal points that can shift at every time step.

Historically, establishing low dynamic regret has relied on the assumptions of Lipschitz continuity or uniform smoothness. However, many critical real-world models—such as those used in Poisson inverse problems or D-optimal design—violate these constraints because their gradients can become unbounded near the boundaries of the search space. This research addresses this gap by providing performance guarantees for these "difficult" functions using the concept of relative smoothness.

Methodology: Relative Smoothness and OMD

The authors utilize Relative Smoothness to circumvent the limitations of standard Euclidean-based smoothness. Instead of measuring gradient changes against standard distance, they measure them relative to a user-specified regularization function $r(\cdot)$.

The primary algorithm analyzed is Online Mirror Descent (OMD), a generalization of gradient descent that employs a "Bregman divergence" derived from the regularization function. This approach ensures that new decisions remain close to previous ones in a geometry that matches the cost function's structure.

To quantify environmental evolution, the authors define three regularity measures:

  1. Path Length ($C_T$): The total movement of the optimal comparator sequence.
  2. Functional Variation ($V_T$): The cumulative change in the cost functions over time.
  3. Gradient Variation ($G_T$): The cumulative change in the gradients of the cost functions.

Theoretical Regret Bounds

The paper establishes two primary theoretical results that extend OMD's utility:

  • Theorem 1: For relatively smooth functions, the dynamic regret is bounded by the path length and functional variation: $O(1 + C_T + V_T)$. Notably, this removes the $\sqrt{T}$ dependency common in previous literature, implying that regret remains low if the environment is relatively stable.
  • Theorem 2 & Corollary 3: If the functions also exhibit relatively strong convexity, the bound is further tightened to $O(1 + C_T + \min(V_T, G_T))$.

Numerical Experiments

The theoretical framework was validated through numerical simulations of two classic optimization problems: the D-optimal Design Problem (used in experimental statistics) and the Poisson Linear Inverse Problem (common in signal processing).

Cumulative cost comparison for the D-optimal design problem over 20 rounds.

In both scenarios, the choice of regularization function proved critical. By selecting the Burg function as the regularizer, the cost functions became relatively smooth, allowing OMD to significantly outperform standard approaches using KL-divergence or $\ell_1$-squared regularization.

Cumulative cost comparison for the Poisson linear inverse problem over 80 rounds.

As shown in the figures, the Burg-based OMD (red solid line) maintains a substantially lower cumulative cost compared to traditional methods, demonstrating the practical power of matching the regularization geometry to the problem's inherent structure.

Conclusion

This work demonstrates that relative smoothness is a powerful tool for analyzing online optimization in dynamic environments. By relaxing traditional smoothness requirements, the authors provide a path to apply OMD to complex problems previously considered too difficult for standard analysis. Future work may explore adaptive step-size mechanisms where the smoothness parameter $\beta$ is unknown, as well as extensions to decentralized optimization settings.

Summary updated

Abstract

The performance of online convex optimization algorithms in a dynamic environment is often expressed in terms of the dynamic regret, which measures the decision maker's performance against a sequence of time-varying comparators. In the analysis of the dynamic regret, prior works often assume Lipschitz continuity or uniform smoothness of the cost functions. However, there are many important cost functions in practice that do not satisfy these conditions. In such cases, prior analyses are not applicable and fail to guarantee the optimization performance. In this letter, we show that it is possible to bound the dynamic regret, even when neither Lipschitz continuity nor uniform smoothness is present. We adopt the notion of relative smoothness with respect to some user-defined regularization function, which is a much milder requirement on the cost functions. We first show that under relative smoothness, the dynamic regret has an upper bound based on the path length and functional variation. We then show that with an additional condition of relatively strong convexity, the dynamic regret can be bounded by the path length and gradient variation. These regret bounds provide performance guarantees to a wide variety of online optimization problems that arise in different application domains. Finally, we present numerical experiments that demonstrate the advantage of adopting a regularization function under which the cost functions are relatively smooth.
BibTeX
@article{eshraghi2022dynamic,
  author = {Nima Eshraghi and Ben Liang},
  title = {{Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions}},
  journal = {IEEE Control. Syst. Lett},
  year = {2022},
  doi = {10.1109/lcsys.2022.3155067},
}
Figure