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

Authors:
  • HLHaihao Lu
    Haihao Lu
  • RFRobert M. Freund
    Robert M. Freund
  • YNYurii Nesterov
    Yurii Nesterov

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...
Funding Information
  • Université Catholique de Louvain
  • Air Force Office of Scientific Research (FA9550-15-1-0276)

This publication has 18 references indexed in Scilit: