The Limitation and Practical Acceleration of Stochastic Gradient Algorithms in Inverse Problems

Junqi Tang, Karen O. Egiazarian, Mike E. DaviesICASSP 2019 · DOI

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.

The Stochastic Acceleration (SA) factor across different datasets. Note the low, flat profile for deblurring compared to the linear growth in CT and ML datasets.

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.

Comparison of FISTA and various stochastic methods. In terms of wall-clock time (left), the deterministic FISTA often outperforms advanced stochastic methods like Katyusha and SVRG in imaging tasks.

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

BibTeX
@inproceedings{tang2019limitation,
  author = {Junqi Tang and Karen O. Egiazarian and Mike E. Davies},
  title = {{The Limitation and Practical Acceleration of Stochastic Gradient Algorithms in Inverse Problems}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  doi = {10.1109/icassp.2019.8683368},
}
Figure