Relatively Smooth Convex Optimization by First-Order Methods, and Applications
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 exam...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120867 https://orcid.org/0000-0002-5217-1894 https://orcid.org/0000-0002-1733-5363 |
| _version_ | 1826197510398410752 |
|---|---|
| author | Nesterov, Yurii Lu, Haihao Freund, Robert Michael |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Nesterov, Yurii Lu, Haihao Freund, Robert Michael |
| author_sort | Nesterov, Yurii |
| collection | MIT |
| description | 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(HXHT) and X := Diag(x), or even the univariate setting with f(x) := -ln(x)+x2. 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(?) (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 [H. H. Bauschke, J. Bolte, and M. Teboulle, Math. Oper. Res., 42 (2017), pp. 330-348]. |
| first_indexed | 2024-09-23T10:48:47Z |
| format | Article |
| id | mit-1721.1/120867 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:48:47Z |
| publishDate | 2019 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1208672022-09-27T15:12:05Z Relatively Smooth Convex Optimization by First-Order Methods, and Applications Nesterov, Yurii Lu, Haihao Freund, Robert Michael Massachusetts Institute of Technology. Department of Mathematics Sloan School of Management Lu, Haihao Freund, Robert Michael 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(HXHT) and X := Diag(x), or even the univariate setting with f(x) := -ln(x)+x2. 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(?) (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 [H. H. Bauschke, J. Bolte, and M. Teboulle, Math. Oper. Res., 42 (2017), pp. 330-348]. 2019-03-11T18:29:55Z 2019-03-11T18:29:55Z 2018-02 2016-10 2019-02-13T16:21:10Z Article http://purl.org/eprint/type/JournalArticle 1052-6234 1095-7189 http://hdl.handle.net/1721.1/120867 Lu, Haihao et al. “Relatively Smooth Convex Optimization by First-Order Methods, and Applications.” SIAM Journal on Optimization 28, no. 1 (January 2018): 333–354 © SIAM https://orcid.org/0000-0002-5217-1894 https://orcid.org/0000-0002-1733-5363 http://dx.doi.org/10.1137/16M1099546 SIAM Journal on Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Nesterov, Yurii Lu, Haihao Freund, Robert Michael Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title | Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title_full | Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title_fullStr | Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title_full_unstemmed | Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title_short | Relatively Smooth Convex Optimization by First-Order Methods, and Applications |
| title_sort | relatively smooth convex optimization by first order methods and applications |
| url | http://hdl.handle.net/1721.1/120867 https://orcid.org/0000-0002-5217-1894 https://orcid.org/0000-0002-1733-5363 |
| work_keys_str_mv | AT nesterovyurii relativelysmoothconvexoptimizationbyfirstordermethodsandapplications AT luhaihao relativelysmoothconvexoptimizationbyfirstordermethodsandapplications AT freundrobertmichael relativelysmoothconvexoptimizationbyfirstordermethodsandapplications |