Globally Optimal Design of a Distributed Scalar Quantizer for Linear Classification

This work is concerned with the design of a distributed scalar quantizer (DSQ) with two encoders, for linear classification. The objective of the optimization is to minimize the classification error of the classifier applied to the quantized inputs in the training sequence with respect to the classifier applied on unquantized inputs. We prove that the optimal DSQ design problem is equivalent to a minimum weight path problem with some constraints on the number and types of edges in a certain weighted directed acyclic graph. Further, we propose a solution algorithm with time complexity $O(K_{1}K_{2}N^{4})$, where $N$ is the size of the training sequence while $K_{1}$ and $K_{2}$ are the numbers of cells of the two encoders, respectively. In addition, we develop faster design algorithms for the equal-rate case (i.e., $K_{1}=K_{2}=K$). Specifically, when the training sequence is symmetric, we prove that there exists an optimal DSQ where the thresholds of the encoders' partitions are interleaved. By leveraging this property and the symmetry of the training sequence, we propose a $O(KN^{2})$ time solution algorithm. For the case when the training sequence is not symmetric, we propose an algorithm with the same time complexity that minimizes an upper bound on the misclassification ratio. Experimental results prove the considerable superiority of the proposed approaches in comparison with prior work in both symmetric and asymmetric scenarios.