Abstract
In this paper, we develop a new algorithm, Annealed Skewed SGD - AskewSGD - for training deep neural networks (DNNs) with quantized weights. First, we formulate the training of quantized neural networks (QNNs) as a smoothed sequence of interval-constrained optimization problems. Then, we propose a new first-order stochastic method, AskewSGD, to solve each constrained optimization subproblem. Unlike algorithms with active sets and feasible directions, AskewSGD avoids projections or optimization under the entire feasible set and allows iterates that are infeasible. The numerical complexity of AskewSGD is comparable to existing approaches for training QNNs, such as the straight-through gradient estimator used in BinaryConnect, or other state of the art methods (ProxQuant, LUQ). We establish convergence guarantees for AskewSGD (under general assumptions for the objective function). Experimental results show that the AskewSGD algorithm performs better than or on par with state of the art methods in classical benchmarks.
Introduction
Training deep neural networks (DNNs) for deployment on resource-constrained mobile and IoT devices often requires quantization—the process of reducing weight and activation precision from 32-bit floating-point to as little as 1-bit. While this significantly reduces memory and energy consumption, it introduces severe optimization challenges. The resulting loss landscape becomes a "staircase" where gradients are zero almost everywhere, rendering standard gradient descent ineffective.
The standard industry solution, the Straight-Through Estimator (STE), bypasses this by ignoring the quantization function during the backward pass. However, STE is mathematically unstable and lacks convergence guarantees. Alternative methods that treat quantization as a constrained optimization problem often rely on hard projections, which can be computationally expensive and may trap the optimizer in poor local minima.
Methodology: The ASkewSGD Framework
ASkewSGD addresses these limitations by reformulating quantization as a sequence of interval-constrained optimization problems that are gradually annealed. The framework relies on two core innovations:
1. Interval Relaxation and Annealing
Instead of forcing weights to discrete values immediately, ASkewSGD defines a "feasible" interval around target quantization levels. A parameter $\epsilon$ controls the width of these intervals. Over the course of training, $\epsilon$ is gradually reduced (annealed) until the intervals collapse into the final discrete values.
2. Skewed Search Directions
To solve the optimization problem at each annealing step, the authors propose a method that skews the search direction rather than using hard projections.
- Dynamic Velocity: If a weight moves toward a boundary, the algorithm modifies its velocity to ensure it stays within (or returns to) the feasible set.
- Infeasible Iterates: Crucially, the algorithm allows weights to temporarily step outside the allowed zone, helping the optimizer navigate complex non-convex landscapes without getting stuck.
- Efficiency: By only considering "active" constraints near boundaries, ASkewSGD maintains a computational complexity comparable to standard SGD.
Experimental Results
The authors evaluated ASkewSGD across a variety of tasks, from synthetic toy examples to large-scale computer vision benchmarks like ImageNet (ILSVRC12).
Stability and Convergence
In toy convex problems where STE variants often oscillate wildly and fail to reach the optimum, ASkewSGD demonstrates smooth and reliable convergence. This theoretical stability is a key differentiator from heuristic-based methods.
Benchmark Performance
ASkewSGD consistently matched or outperformed state-of-the-art (SOTA) methods:
- Binary Weights (1-bit): On CIFAR-10, ASkewSGD achieved 88.98% accuracy. On the challenging ImageNet task, it reached 46.95% Top-1 accuracy, significantly outperforming other annealed methods like AdaSTE (35.37%).
- Low-Bit Quantization: When quantizing both weights and activations to 4 bits (W4/A4) on ImageNet, ASkewSGD reached 68.51% accuracy—remarkably close to the full 32-bit floating-point baseline of 69.32%.
Conclusion and Future Work
ASkewSGD provides a principled, theoretically grounded alternative to the "hacks" commonly used in QNN training. By replacing projections with skewed search directions and employing an annealing schedule, it achieves SOTA results with formal convergence guarantees even for non-convex functions.
Future research directions include the development of more complex, automated annealing schedules and the application of ASkewSGD to diverse architectures such as Transformers. The authors also noted the environmental impact of their research, estimating that the experiments generated approximately 180 kg of CO2e, underscoring the need for efficient optimization in deep learning.
Summary updated