Proximal bundle methods in depth: a unified analysis for inexact oracles

The last few years have seen the advent ofa new generation of bundle methods, capable to handle inexact oracles, polluted by “noise”. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence, keeping in mind that in the presence of inexactness convergence is to be understood in an approximate manner. The purpose of this paper is twofold. First, we state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establish each intermediate result. Our framework is comprehensive and generalizes in various ways a number of algorithms proposed in the literature, for which we show convergence without much effort. Second, based on the ingredients of our synthetic theory, we consider new bundle variants adapted to oracles for which high accuracy is possible, yet it is preferable not to make exact calculations often, because they are too time consuming.

Article

Download

View PDF