Relatively Smooth Convex Optimization by First-Order Methods, and Applications
Haihao Lu, Robert M. Freund, Yurii E. Nesterov · SIAM Journal on Optimization · 2018
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 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 [H. H. Bauschke, J. Bolte, and M. Teboulle, Math. Oper. Res., 42 (2017), pp. 330--348].
Cited by 264 works. doi:10.1137/16m1099546
Authors
References
- Smooth minimization of non-smooth functions
- The Equivalence of Two Extremum Problems
- Primal-dual subgradient methods for convex problems
- Gradient methods for minimizing composite functions
- Optimal and Efficient Designs of Experiments
- On the complexity of approximating the maximal inscribed ellipsoid for a polytope
- Rounding of Polytopes in the Real Number Model of Computation
- A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications
- Computation of Minimum-Volume Covering Ellipsoids
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids