Relatively Smooth Convex Optimization by First-Order Methods, and Applications
Authors:
- Haihao LuHLHaihao Lu
- Robert M. FreundRFRobert M. Freund
- Yurii NesterovYNYurii Nesterov
Top Cited Papers
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 28 (1) , 333-354
Abstract
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...
Keywords
All Related Versions
Funding Information
- Université Catholique de Louvain
- Air Force Office of Scientific Research (FA9550-15-1-0276)
This publication has 18 references indexed in Scilit:
- A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and ApplicationsMathematics of Operations Research, 2017
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoidsOptimization Methods and Software, 2008
- On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient ProjectionSIAM Journal on Optimization, 2008
- Location adjustment for the minimum volume ellipsoid estimatorStatistics and Computing, 2002
- The Volumetric Barrier for Semidefinite ProgrammingMathematics of Operations Research, 2000
- Large step volumetric potential reduction algorithms for linear programmingAnnals of Operations Research, 1996
- Rounding of Polytopes in the Real Number Model of ComputationMathematics of Operations Research, 1996
- On the complexity of approximating the maximal inscribed ellipsoid for a polytopeMathematical Programming, 1993
- Optimal and Efficient Designs of ExperimentsThe Annals of Mathematical Statistics, 1969
- The Equivalence of Two Extremum ProblemsCanadian Journal of Mathematics, 1960