Stochastic Gradient Descent (SGD) is the dominant optimization paradigm in machine learning. However, in imaging inverse problems—such as deblurring or medical reconstruction—SGD frequently underperforms relative to deterministic methods like the Fast Iterative Soft-Thresholding Algorithm (FISTA). This work identifies the root causes of this "stochastic paradox" and proposes a novel framework to achieve practical acceleration.
The Smoothness Gap and the SA Factor
The theoretical advantage of stochastic methods relies on the assumption that processing small data subsets (mini-batches) is significantly cheaper while maintaining a similar "smoothness" to the full dataset. The authors quantify this through the Lipschitz constants of the full objective ($L_f$) and the individual mini-batches ($L_b$).
They introduce the Stochastic Acceleration (SA) factor, defined as: $$\Upsilon(\bar{S}) = \frac{K L_f}{L_b}$$ where $K$ is the number of mini-batches. This factor measures how much the global problem's smoothness compensates for the increased variance of stochastic sampling.
As shown in the figure above, the SA factor remains low for tasks like image deblurring, explaining why standard SGD variants struggle. In contrast, for X-ray CT or standard machine learning datasets (RCV1, Magic04), the SA factor grows linearly with $K$, indicating a high potential for stochastic speedup.
The Stochastic Paradox in Practice
In many imaging tasks, the computational cost of "proximal operators" (used to handle non-smooth regularization like Total Variation) creates a bottleneck. Stochastic methods typically require these calculations at every mini-batch iteration. If the proximal step is expensive, the overhead outweighs any gains from reduced gradient computations.
The figure above illustrates this phenomenon: while stochastic methods might appear competitive in terms of data passes, they often lag behind FISTA in actual wall-clock time due to these computational overheads.
Proposed Solution: Acc-PD-SGD
To address these limitations, the authors propose Acc-PD-SGD (Accelerated Primal-Dual SGD). This algorithm utilizes a saddle-point formulation to decouple linear operators (e.g., blur kernels) from non-smooth regularization. By integrating "Katyusha-X" style momentum, Acc-PD-SGD maintains Nesterov-type acceleration while drastically reducing the frequency of expensive proximal operator evaluations.
Key Results and Conclusion
The proposed Acc-PD-SGD effectively bridges the performance gap. In empirical tests on 512x512 image deblurring, it reached target error levels in approximately half the wall-clock time required by FISTA. The SA factor proved to be a reliable predictor of whether a stochastic approach would be beneficial for a given inverse problem. This work provides both a theoretical diagnostic tool and a practical algorithmic path forward for applying stochastic optimization to high-dimensional imaging challenges.
Summary updated