Optimal Computational Trade-Off of Inexact Proximal Methods

In this paper, we investigate the trade-off between convergence rate and computational cost when minimizing a composite functional with proximal-gradient methods, which are popular optimisation tools in machine learning. We consider the case when the proximity operator is computed via an iterative procedure, which provides an approximation of the exact proximity operator. In that case, we obtain algorithms with two nested loops. We show that the strategy that minimizes the computational cost to reach a solution with a desired accuracy in finite time is to set the number of inner iterations to a constant, which differs from the strategy indicated by a convergence rate analysis. In the process, we also present a new procedure called SIP (that is Speedy Inexact Proximal-gradient algorithm) that is both computationally efficient and easy to implement. Our numerical experiments confirm the theoretical findings and suggest that SIP can be a very competitive alternative to the standard procedure.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00704398
Author Machart, Pierre, Anthoine, Sandrine, Baldassarre, Luca
Maintainer CCSD
Last Updated October 30, 2026, 16:21 (UTC)
Created October 30, 2026, 16:21 (UTC)
Identifier hal-00704398
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'informatique Fondamentale de Marseille (LIF) ; Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
creator Machart, Pierre
date 2012-10-17T00:00:00
harvest_object_id 4889c92f-3010-491d-854b-d015e98670c2
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-01-27T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1210.5034
set_spec type:REPORT