Improved algorithms for convex minimization in relative scale

Peter Richtárik

doi:10.1137/090747142

Improved algorithms for convex minimization in relative scale

Peter Richtárik^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

Abstract

In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter.

Original language	English (US)
Pages (from-to)	1141-1167
Number of pages	27
Journal	SIAM Journal on Optimization
Volume	21
Issue number	3
DOIs	https://doi.org/10.1137/090747142
State	Published - 2011
Externally published	Yes

Keywords

Convex optimization
Löwner-John ellipsoids
Nesterov's smoothing technique
Relative scale
Sublinearity

ASJC Scopus subject areas

Software
Theoretical Computer Science

Access to Document

10.1137/090747142

Cite this

@article{37bd17530a284dd4b072364a7d81b27a,

title = "Improved algorithms for convex minimization in relative scale",

abstract = "In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter.",

keywords = "Convex optimization, L{\"o}wner-John ellipsoids, Nesterov's smoothing technique, Relative scale, Sublinearity",

author = "Peter Richt{\'a}rik",

year = "2011",

doi = "10.1137/090747142",

language = "English (US)",

volume = "21",

pages = "1141--1167",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Improved algorithms for convex minimization in relative scale

AU - Richtárik, Peter

PY - 2011

Y1 - 2011

N2 - In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter.

AB - In this paper we propose two modifications to Nesterov's algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of the optimum, with k being the iteration counter.

KW - Convex optimization

KW - Löwner-John ellipsoids

KW - Nesterov's smoothing technique

KW - Relative scale

KW - Sublinearity

UR - http://www.scopus.com/inward/record.url?scp=80054748079&partnerID=8YFLogxK

U2 - 10.1137/090747142

DO - 10.1137/090747142

M3 - Article

AN - SCOPUS:80054748079

SN - 1052-6234

VL - 21

SP - 1141

EP - 1167

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 3

ER -

Improved algorithms for convex minimization in relative scale

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this