Linear Convergence of the Derivative-Free Proximal Bundle Method on Convex Nonsmooth Functions, with Application to the Derivative-Free VU-Algorithm

Proximal bundle methods are a class of optimisation algorithms that leverage the proximal operator to address nonsmoothness in the objective function efficiently. This study focuses on a derivative-free (DFO) proximal bundle method and one of its applications called the DFO VU VU -algorithm. These algorithms incorporate approximate proximal points as subprocedures in order to optimise convex nonsmooth functions based on approximated subdifferential information. Interestingly, the classical VU VU -algorithm, which operates on true subgradient values, achieves superlinear convergence. At each iteration, the algorithm divides the whole space into two: the smooth U U -space and the nonsmooth V V -space. It takes a Newton-like step on the U U -space and a proximal-point step on the V V -space, enabling it to handle both smooth and nonsmooth parts effectively and converge faster. In this work, we reveal the worst possible convergence rate for the DFO VU VU -method by showing the linear convergence of the DFO proximal bundle method. This will be done by presenting a suitable framework and using the subdifferential-based error bound on the distance to critical points.