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

By Haihao Lu, Robert M. Freund, Yurii E. Nesterov. 2016

425 citations recorded by the source corpus.

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(\cdot)$ is not uniformly smooth---for example, in $D$-optimal design where $f(x):=-\ln \det(HXH^T)$ and $X:= \mbox{{\bf D}iag} (x)$, or even the univariate setting with $f(x) := -\ln(x) + x^2$. In this paper we develop a notion of “relative smoothness” and relative strong convexity that is determined relative to a user-specified “reference function” $h(\cdot)$ (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(\cdot)$. 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 a...

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “Assumption 3.1 The function ω ( ) satisﬁes Since ω ( x ) is convex by the triangle inequality, we de-ﬁne the dual distance Remark 3.2 Usually, extensions of smoothness of a function use Bregman divergences (see e.g. [Lu et al. 2018; Bauschke et al. 2017]).”
On Acceleration with Noise-Corrupted Gradients (2018, background): “Examples include problems in which f ( · ) has H ¨ older-continuous gradients, and even the problems with certain structured non-smooth objectives (Nesterov, 2005; Allen-Zhu & Orecchia, 2015; Lu et al., 2016).”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “Several applications of interest are not smooth but relatively smooth, e.g. , algorithmic game theory (Birnbaum et al., 2011); Poisson inverse problems (Bertero et al., 2009); and more (Lu et al., 2018).”
Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry (2019, background): “The above concept of relative quadratic curvature is inspired by the concepts of relative smoothness and relative continuity introduced in [2, 17, 18, 22].”
Variance Reduction for Matrix Games (2019, methodology): “Third, we adapt our framework to achieve linear convergence when φ and ψ are relatively strongly convex in the sense of [23].”