Abstract
Differentiable $k$-Means (DKM) is a powerful technique for quantization-aware training, yet it is severely limited by a "memory wall" caused by storing intermediate clustering states for backpropagation. We introduce Implicit Differentiable $k$-Means (IDKM), which reformulates soft $k$-means clustering as a fixed-point problem. By applying implicit differentiation, IDKM achieves constant memory complexity relative to clustering iterations. This allows for full convergence during training and enables the quantization of large-scale models like ResNet18 on standard hardware. Our results demonstrate that IDKM maintains or improves accuracy while significantly reducing training time and memory overhead.
Introduction
Deploying deep neural networks on edge devices requires aggressive compression. Quantization—limiting weights to a small set of unique values (a codebook)—is a primary solution. Differentiable $k$-Means (DKM) recently emerged as a state-of-the-art approach by integrating soft $k$-means clustering into the training loop. However, DKM requires storing the results of every clustering iteration to compute gradients, leading to an explosion in memory usage. This constraint often forces practitioners to use fewer iterations, sacrificing convergence, or limits the method to small models.
Methods: Implicit Differentiable $k$-Means
IDKM addresses the memory bottleneck by framing soft $k$-means as a fixed-point problem: $C^* = F(C^*, W)$, where $C^*$ represents the converged cluster centers and $W$ the weights. Instead of backpropagating through the entire unrolled loop of the clustering algorithm, IDKM employs implicit differentiation.
This mathematical shift allows the gradient of the converged centers to be calculated using only the final state, decoupling memory complexity from the number of iterations ($t$). The memory requirement drops from $O(t \cdot m \cdot 2^b)$ to $O(m \cdot 2^b)$.
Furthermore, the authors propose IDKM-JFB, which utilizes Jacobian-Free Backpropagation. By using a zeroth-order approximation to avoid the expensive matrix inversion typically required by implicit differentiation, IDKM-JFB significantly accelerates the backward pass.
Experimental Results
The authors evaluated IDKM on MNIST (using a small CNN) and CIFAR-10 (using ResNet18).
Efficiency and Speed
On the MNIST benchmark, IDKM demonstrated substantial improvements in training efficiency. IDKM-JFB, in particular, proved to be the fastest method, consistently outperforming DKM across various compression regimes.
Scalability to Large Models
The primary advantage of IDKM is its scalability. In experiments with ResNet18 on CIFAR-10, DKM was unable to complete training on the available hardware, running out of memory after only 5 iterations—insufficient for effective learning. In contrast, IDKM and IDKM-JFB successfully quantized the 11.1-million-parameter model to high accuracy by running clustering to full convergence.
Conclusion and Future Work
IDKM overcomes the "memory wall" of differentiable clustering, making high-quality quantization accessible for modern architectures. By decoupling the forward clustering iterations from backward gradient memory, it enables better convergence and faster training. Future work may explore more complex temperature annealing schemes and investigate the stability of implicit differentiation in diverse architectural settings.
Summary updated