signProx: One-Bit Proximal Algorithm for Nonconvex Stochastic Optimization

Ulugbek S. Kamilov

Abstract

Stochastic gradient descent (SGD) is one of the most widely used optimization methods for parallel and distributed processing of large datasets. One of the key limitations of distributed SGD is the need to regularly communicate the gradients between different computation nodes. To reduce this communication bottleneck, recent work has considered a one-bit variant of SGD, where only the sign of each gradient element is used in optimization. In this paper, we extend this idea by proposing a stochastic variant of the proximal-gradient method that also uses one-bit per update element. We prove the theoretical convergence of the method for non-convex optimization under a set of explicit assumptions. Our results indicate that the compressed method can match the convergence rate of the uncompressed one, making the proposed method potentially appealing for distributed processing of large datasets.

Introduction

In modern machine learning and signal processing, models are frequently trained across distributed computation nodes. While Stochastic Gradient Descent (SGD) is the standard approach, its performance is often limited by communication overhead. As model parameters grow into the millions, the time required to transmit high-precision gradient vectors across a network can exceed the time spent on local computation.

To mitigate this, researchers previously introduced "signSGD," which transmits only the sign (+1 or -1) of each gradient element. However, signSGD does not naturally accommodate proximal-gradient methods, which are essential for optimization problems involving constraints or regularizers (e.g., sparsity-inducing $L_1$ penalties). This paper introduces signProx, a one-bit stochastic variant of the proximal-gradient method designed to bridge this gap.

The signProx Algorithm

The core innovation of signProx is the compression of the proximal-gradient update into a single bit per element. Instead of transmitting a full floating-point vector, the algorithm communicates only the sign of the difference between the current iterate and the proximal mapping.

Comparison of the standard Stochastic Proximal Gradient Method (SPGM) and the proposed signProx algorithm.

As shown in Algorithm 2, the update rule is defined as: $$x^t \leftarrow x^{t-1} - \gamma \text{sgn}(x^{t-1} - \widehat{P}_k(x^{t-1}))$$ where $\widehat{P}_k$ represents the stochastic proximal operator. Notably, signProx is a generalization of signSGD; if the regularizer is removed, the algorithm reduces to standard signSGD. The authors provide a rigorous convergence analysis for non-convex objectives, demonstrating that signProx achieves a convergence rate of $O(1/\sqrt{T})$, matching the rate of uncompressed methods.

Experimental Results

The algorithm was evaluated on a Generalized Phase Retrieval task using a $50 \times 50$ Shepp-Logan phantom image. The setup involved $m = 3000$ nonlinear intensity measurements with Total Variation (TV) regularization to preserve edges.

Convergence performance and image reconstruction results comparing SPGM and signProx.

The results highlight a significant advantage for signProx in the presence of "sparse" stochasticity—where noise is infrequent but high-amplitude. Because the sign() function acts as a natural limiter, it prevents massive outlier gradients from derailing the optimization process. In these scenarios, signProx not only converged faster but also achieved superior reconstruction quality. Specifically, signProx reached a Peak Signal-to-Noise Ratio (PSNR) of 21.15 dB, outperforming the 19.01 dB achieved by the uncompressed Stochastic Proximal Gradient Method (SPGM).

Conclusion and Future Work

signProx offers a compelling solution to the communication bottleneck in distributed optimization. By reducing the data volume per update by 32x to 64x (compared to 32-bit or 64-bit floats) while maintaining theoretical convergence rates and improving robustness to outliers, it is well-suited for large-scale non-convex problems. Future work will focus on evaluating the algorithm in physical distributed clusters and exploring the impact of data-fidelity term convexity on convergence bounds.

Summary updated

Abstract

Stochastic gradient descent (SGD) is one of the most widely used optimization methods for parallel and distributed processing of large datasets. One of the key limitations of distributed SGD is the need to regularly communicate the gradients between different computation nodes. To reduce this communication bottleneck, recent work has considered a one-bit variant of SGD, where only the sign of each gradient element is used in optimization. In this paper, we extend this idea by proposing a stochastic variant of the proximal-gradient method that also uses one-bit per update element. We prove the theoretical convergence of the method for non-convex optimization under a set of explicit assumptions. Our results indicate that the compressed method can match the convergence rate of the uncompressed one, making the proposed method potentially appealing for distributed processing of large datasets.
BibTeX
@inproceedings{kamilov2018signprox,
  author = {Ulugbek S. Kamilov},
  title = {{signProx: One-Bit Proximal Algorithm for Nonconvex Stochastic Optimization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  doi = {10.1109/icassp.2019.8682059},
}
Figure