Sharper Bounds for Proximal Gradient Algorithms with Errors
This work addresses the problem of ensuring reliable optimization in practical settings with computational inaccuracies, such as reduced-precision hardware, but it is incremental as it builds on existing error analysis frameworks.
The paper analyzes the convergence of proximal gradient algorithms when gradient and proximal computations are inaccurate, deriving new deterministic and probabilistic bounds that are applied to simulated MPC and synthetic LASSO optimization problems on reduced-precision machines. It shows that probabilistic bounds are more robust for verification and accurate for guarantees, and demonstrates how acceleration amplifies computational errors.
We analyse the convergence of the proximal gradient algorithm for convex composite problems in the presence of gradient and proximal computational inaccuracies. We derive new tighter deterministic and probabilistic bounds that we use to verify a simulated (MPC) and a synthetic (LASSO) optimization problems solved on a reduced-precision machine in combination with an inaccurate proximal operator. We also show how the probabilistic bounds are more robust for algorithm verification and more accurate for application performance guarantees. Under some statistical assumptions, we also prove that some cumulative error terms follow a martingale property. And conforming to observations, e.g., in \cite{schmidt2011convergence}, we also show how the acceleration of the algorithm amplifies the gradient and proximal computational errors.