Alternating Direction Method of Multipliers for Quantization

Abstract

Quantization of the parameters of machine learning models, such as deep neural networks, requires solving constrained optimization problems, where the constraint set is formed by the Cartesian product of many simple discrete sets. For such optimization problems, we study the performance of the Alternating Direction Method of Multipliers for Quantization ($\text{ADMM-Q}$) algorithm, which is a variant of the widely-used ADMM method applied to our discrete optimization problem. We establish the convergence of the iterates of $\text{ADMM-Q}$ to certain $\text{stationary points}$. To the best of our knowledge, this is the first analysis of an ADMM-type method for problems with discrete variables/constraints. Based on our theoretical insights, we develop a few variants of $\text{ADMM-Q}$ that can handle inexact update rules, and have improved performance via the use of "soft projection" and "injecting randomness to the algorithm". We empirically evaluate the efficacy of our proposed approaches.

References in corpus (17)

• Intriguing properties of neural networks
• Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients
• Searching for Activation Functions
• A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers
• Federated Optimization in Heterogeneous Networks
• AIDE: Fast and Communication Efficient Distributed Optimization
• Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM
• Neon2: Finding Local Minima via First-Order Oracles
• Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
• Progressive Weight Pruning of Deep Neural Networks using ADMM
• Progressive DNN Compression: A Key to Achieve Ultra-High Weight Pruning and Quantization Rates using ADMM
• Toward Extremely Low Bit and Lossless Accuracy in DNNs with Progressive ADMM
• An Ultra-Efficient Memristor-Based DNN Framework with Structured Weight Pruning and Quantization Using ADMM
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization
• SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems