# Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

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

## Key facts

- Cited by 108 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2016.

## Built on by (most cited first, 30 of 108)

- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [Mirror Descent Maximizes Generalized Margin and Can Be Implemented Efficiently](https://mlsanity.com/paper/2205.12808/) (2022)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [A general class of surrogate functions for stable and efficient reinforcement learning](https://mlsanity.com/paper/2108.05828/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [A connection between Tempering and Entropic Mirror Descent](https://mlsanity.com/paper/2310.11914/) (2023)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [A Unified Approach to Controlling Implicit Regularization via Mirror Descent](https://mlsanity.com/paper/2306.13853/) (2023)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [Fisher-Rao Gradient Flow: Geodesic Convexity and Functional Inequalities](https://mlsanity.com/paper/2407.15693/) (2024)
- [Entropy annealing for policy mirror descent in continuous time and space](https://mlsanity.com/paper/2405.20250/) (2024)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)

## Abstract (arXiv)

The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some Lipschitz constant L. However, in many settings the differentiable convex function f(·) is not uniformly smooth -- for example in D-optimal design where f(x):=-ln det(HXHT), or even the univariate setting with f(x) := -ln(x) + x2. Herein we develop a notion of "relative smoothness" and relative strong convexity that is determined relative to a user-specified "reference function" h(·) (that should be computationally tractable for algorithms), and we show that many differentiable convex functions are relatively smooth with respect to a correspondingly fairly-simple reference function h(·). We extend two standard algorithms -- the primal gradient scheme and the dual averaging scheme -- to our new setting, with associated computational guarantees. We apply our new approach to develop a new first-order method for the D-optimal design problem, with associated computational complexity analysis. Some of our results have a certain overlap with the recent work citebbt.