Fixed-Point Automatic Differentiation of Forward--Backward Splitting Algorithms for Partly Smooth Functions
This work addresses sensitivity analysis and parameter learning in non-smooth optimization, offering incremental improvements in efficiency for domain-specific problems.
The paper tackles the problem of differentiating the solution mapping of optimization problems involving sums of smooth and partly smooth functions, showing that automatic differentiation of proximal splitting algorithms converges to the derivative, with a variant called Fixed-Point Automatic Differentiation reducing memory overhead and providing faster convergence. Numerical results on Lasso, Group Lasso, and image denoising problems demonstrate convergence rates and practical applications in learning regularization terms.
A large class of non-smooth practical optimization problems can be written as minimization of a sum of smooth and partly smooth functions. We examine such structured problems which also depend on a parameter vector and study the problem of differentiating its solution mapping with respect to the parameter which has far reaching applications in sensitivity analysis and parameter learning problems. Under partial smoothness and other mild assumptions, we apply Implicit (ID) and Automatic Differentiation (AD) to the fixed-point iterations of proximal splitting algorithms. We show that AD of the sequence generated by these algorithms converges (linearly under further assumptions) to the derivative of the solution mapping. For a variant of automatic differentiation, which we call Fixed-Point Automatic Differentiation (FPAD), we remedy the memory overhead problem of the Reverse Mode AD and moreover provide faster convergence theoretically. We numerically illustrate the convergence and convergence rates of AD and FPAD on Lasso and Group Lasso problems and demonstrate the working of FPAD on prototypical image denoising problems by learning the regularization term.