HAL - INRIA :: [inria-00618152, version 3] Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

inria-00618152, version 3

Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

Mark Schmidt ( Author to contact preferably ) ^1, 2, Nicolas Le Roux () ^1, 2, Francis Bach () ^1, 2

NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems (2011)

Abstract: We consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the non-smooth term. We show that both the basic proximal-gradient method and the accelerated proximal-gradient method achieve the same convergence rate as in the error-free case, provided that the errors decrease at appropriate rates.Using these rates, we perform as well as or better than a carefully chosen fixed error level on a set of structured sparsity problems.

1: SIERRA (INRIA Paris - Rocquencourt)
INRIA : PARIS - ROCQUENCOURT – Ecole Normale Supérieure de Paris - ENS Paris – CNRS : UMR8548
2: Laboratoire d'informatique de l'école normale supérieure (LIENS)
CNRS : UMR8548 – Ecole Normale Supérieure de Paris - ENS Paris

inria-00618152, version 3
http://hal.inria.fr/inria-00618152
oai:hal.inria.fr:inria-00618152
From: Nicolas Le Roux <>
Submitted on: Thursday, 1 December 2011 16:03:15
Updated on: Tuesday, 20 December 2011 09:42:09

See detailed view

Associated documents

PDF :

arXiv: 1109.2415

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00618152"><analytic>
<author><persName><forename>Mark</forename><surname>Schmidt</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
</affiliation>
</author>
<author><persName><forename>Nicolas</forename><surname>Le Roux</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
</affiliation>
</author>
<author><persName><forename>Francis</forename><surname>Bach</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole Normale Supérieure de Paris - ENS Paris</orgName>
</affiliation>
</author>
<title type="main" level="a">Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization</title></analytic><monogr><meeting>NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems</meeting><imprint><pubPlace><settlement>Grenada</settlement><country>Spain</country></pubPlace><biblScope type="publicationDate">2011-12-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00618152</idno><idno type="HALFile">http://hal.inria.fr/inria-00618152/PDF/111201_arxiv_inexact_prox.pdf</idno></biblStruct>
</listBibl>
</listBibl>