# "Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent

arXiv: https://arxiv.org/abs/1710.04718 · HTML: https://mlsanity.com/paper/1710.04718/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2017.

## Built on by (most cited first, 15 of 15)

- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses](https://mlsanity.com/paper/2104.14562/) (2021)
- [Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements](https://mlsanity.com/paper/2107.08011/) (2021)
- [A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization](https://mlsanity.com/paper/2112.11928/) (2021)
- [Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity](https://mlsanity.com/paper/2401.13971/) (2024)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions](https://mlsanity.com/paper/2202.12843/) (2022)
- [Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity](https://mlsanity.com/paper/2305.14161/) (2023)
- [A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions](https://mlsanity.com/paper/2308.16362/) (2023)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)
- [GBM-based Bregman Proximal Algorithms for Constrained Learning](https://mlsanity.com/paper/2308.10767/) (2023)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)

## Abstract (arXiv)

The usual approach to developing and analyzing first-order methods for non-smooth (stochastic or deterministic) convex optimization assumes that the objective function is uniformly Lipschitz continuous with parameter Mf. However, in many settings the non-differentiable convex function f(·) is not uniformly Lipschitz continuous -- for example (i) the classical support vector machine (SVM) problem, (ii) the problem of minimizing the maximum of convex quadratic functions, and even (iii) the univariate setting with f(x) := max0, x + x2. Herein we develop a notion of "relative continuity" that is determined relative to a user-specified "reference function" h(·) (that should be computationally tractable for algorithms), and we show that many non-differentiable convex functions are relatively continuous with respect to a correspondingly fairly-simple reference function h(·). We also similarly develop a notion of "relative stochastic continuity" for the stochastic setting. We analysis two standard algorithms -- the (deterministic) mirror descent algorithm and the stochastic mirror descent algorithm -- for solving optimization problems in these two new settings, and we develop for the first time computational guarantees for instances where the objective function is not uniformly Lipschitz continuous. This paper is a companion paper for non-differentiable convex optimization to the recent paper by Lu, Freund, and Nesterov, which developed similar sorts of results for differentiable convex optimization.