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

Ben Liang, Nima Eshraghi, Ben Liang 0001

TL;DR

This paper extends the theoretical guarantees of Online Mirror Descent (OMD) to a much broader class of "relatively smooth" functions, moving beyond the restrictive standard assumptions of Lipschitz continuity or uniform smoothness. The authors prove that OMD can achieve tight dynamic regret bounds—essentially guaranteeing performance even when the environment and the optimal solution are constantly shifting—making it applicable to complex real-world problems like image reconstruction and experimental design.

What Problem Does This Paper Address?

In Online Convex Optimization (OCO), a decision-maker must choose a sequence of points to minimize a cumulative cost that changes over time. To measure success, researchers use dynamic regret, which compares the algorithm's performance against a sequence of optimal points that can change at every step.

Traditionally, proving that an algorithm has "low" dynamic regret requires the cost functions to be Lipschitz continuous (they don't change too abruptly) or uniformly smooth (their gradients don't change too fast). However, many important mathematical models—such as those used in Poisson inverse problems or D-optimal design—violate these assumptions. Their gradients can blow up near the boundaries of the search space. This paper addresses the gap: how do we provide performance guarantees for these "difficult" functions in a dynamic environment?

Methods

The authors leverage the concept of Relative Smoothness. Instead of measuring the smoothness of a cost function against a standard Euclidean distance, they measure it relative to a user-specified regularization function $r(\cdot)$.

The core algorithm analyzed is Online Mirror Descent (OMD). OMD is a generalization of gradient descent that uses a "Bregman divergence" (derived from the regularization function) to keep new decisions close to previous ones.

The authors derive new upper bounds for dynamic regret using three "regularity measures" that describe how the environment evolves:

  1. Path Length ($C_T$): How much the optimal comparator sequence moves.
  2. Functional Variation ($V_T$): How much the cost functions themselves change over time.
  3. Gradient Variation ($G_T$): How much the gradients of the cost functions change.

Datasets

As a theoretical "letter," the paper does not use standard large-scale datasets like ImageNet. Instead, it validates the theory using numerical simulations of two classic optimization problems:

  • D-optimal Design Problem: Used in statistics to create optimal experimental protocols.
  • Poisson Linear Inverse Problem: A staple in image science and signal processing.

In both cases, the authors show that choosing a specific regularization function (the Burg function) makes these problems "relatively smooth," allowing the algorithm to perform significantly better than standard approaches.

Key Insights and Ideas

  • Milder Requirements: Relative smoothness is a much more flexible assumption than traditional smoothness. It allows the cost function to behave "badly" by standard measures, provided the regularization function $r(\cdot)$ behaves similarly.
  • Breaking the $\sqrt{T}$ Barrier: For relatively smooth functions, the authors found a dynamic regret bound of $O(1 + C_T + V_T)$. This is notable because it removes the $\sqrt{T}$ dependency found in many previous works, suggesting that if the environment is stable ($C_T$ and $V_T$ are small), the regret stays very low regardless of the total time $T$.
  • The Power of Choice: The "aha moment" is that the performance of OMD is highly dependent on the choice of the regularization function. By matching the regularization function to the structure of the cost function (to achieve relative smoothness), you can "tame" functions that were previously thought to be too difficult for standard online analysis.

Key Results

  • Theorem 1: Proves that for relatively smooth functions, the dynamic regret is bounded by the path length and functional variation: $O(1 + C_T + V_T)$.
  • Theorem 2 & Corollary 3: Shows that if the functions are also relatively strongly convex, the bound can be tightened further to $O(1 + C_T + \min(V_T, G_T))$.
  • Numerical Superiority: In simulations, OMD using the Burg regularization function (tailored for relative smoothness) resulted in substantially lower accumulated costs compared to standard choices like the KL-divergence or $\ell_1$-squared regularization.

Limitations and Future Work

  • Fixed Step Size: The current analysis assumes a fixed step size $\eta$ based on the smoothness parameter $\beta$. In many real-world scenarios, $\beta$ might not be known in advance, suggesting a need for adaptive step-size versions of this theory.
  • Parameter Knowledge: The tighter bounds in Theorem 2 require knowledge of the strong convexity parameter $\lambda$.
  • Future Directions: The authors suggest that these results could be extended to more complex settings, such as decentralized online optimization or problems with time-varying constraints.

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{liang2022dynamic,
  author = {Ben Liang and 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},
}

Loading related content...

Figure