Optimization Online


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

Haihao Lu (haihao***at***mit.edu)
Robert Freund (rfreund***at***mit.edu)
Yurii Nesterov (yurii.nesterov***at***uclouvain.be)

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(.) is not uniformly smooth -- for example in D-optimal design where f(x):=-ln det(HXH^T), or even the univariate setting with f(x) := -ln(x) + x^2. 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 of Bauschke, Bolte, and Teboulle.

Keywords: large-scale optimization, first-order methods, D-optimal design, computational complexity, primal gradient, dual averaging

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization

Citation: MIT Operations Research Center Working Paper MIT

Download: [PDF]

Entry Submitted: 10/19/2016
Entry Accepted: 10/19/2016
Entry Last Modified: 10/10/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society