The Practicality of Stochastic Optimization in Imaging Inverse Problems

Abstract

In this work we investigate the practicality of stochastic gradient descent and recently introduced variants with variance-reduction techniques in imaging inverse problems. Such algorithms have been shown in the machine learning literature to have optimal complexities in theory, and provide great improvement empirically over the deterministic gradient methods. Surprisingly, in some tasks such as image deblurring, many of such methods fail to converge faster than the accelerated deterministic gradient methods, even in terms of epoch counts. We investigate this phenomenon and propose a theory-inspired mechanism for the practitioners to efficiently characterize whether it is beneficial for an inverse problem to be solved by stochastic optimization techniques or not. Using standard tools in numerical linear algebra, we derive conditions on the spectral structure of the inverse problem for being a suitable application of stochastic gradient methods. Particularly, we show that, for an imaging inverse problem, if and only if its Hessain matrix has a fast-decaying eigenspectrum, then the stochastic gradient methods can be more advantageous than deterministic methods for solving such a problem. Our results also provide guidance on choosing appropriately the partition minibatch schemes, showing that a good minibatch scheme typically has relatively low correlation within each of the minibatches. Finally, we propose an accelerated primal-dual SGD algorithm in order to tackle another key bottleneck of stochastic optimization which is the heavy computation of proximal operators. The proposed method has fast convergence rate in practice, and is able to efficiently handle non-smooth regularization terms which are coupled with linear operators.

References in corpus (30)

• Adam: A Method for Stochastic Optimization
• Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Fast Image Recovery Using Variable Splitting and Constrained Optimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• User-friendly tail bounds for sums of random matrices
• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
• An Online Plug-and-Play Algorithm for Regularized Image Reconstruction
• A Universal Catalyst for First-Order Optimization
• Optimization for deep learning: theory and algorithms
• Deconvolving Images with Unknown Boundaries Using the Alternating Direction Method of Multipliers
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• A quasi-Newton proximal splitting method
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• A Simple Practical Accelerated Method for Finite Sums
• SIMBA: Scalable Inversion in Optical Tomography using Deep Denoising Priors
• Faster PET Reconstruction with Non-Smooth Priors by Randomization and Preconditioning
• On the convergence analysis of the optimized gradient method
• An optimal randomized incremental gradient method
• SGD: General Analysis and Improved Rates
• Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization
• Optimal mini-batch and step sizes for SAGA
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• UNLocBoX: A MATLAB convex optimization toolbox for proximal-splitting methods
• Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes
• Accelerated Reconstruction of Perfusion-Weighted MRI Enforcing Jointly Local and Nonlocal Spatio-temporal Constraints

Cited by in corpus (4)

• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• A Fast Stochastic Plug-and-Play ADMM for Imaging Inverse Problems
• Proximal and Federated Random Reshuffling
• Compressive MRI quantification using convex spatiotemporal priors and deep auto-encoders