where \(\mathcal {Q}\)  is the set of quantization levels, \(d\)  is the number of parameters (network weights and biases), \(\ell \)  is the training loss (e.g. the cross-entropy or square loss), \(f(x,w)\)  is the DNN prediction function, \(p_{\operatorname{data}}\)  is the training distribution. The quantization constraints in the above program make it an extremely difficult task: the underlying optimization problem is non-convex, non-differentiable, and combinatorial in nature. Optimization of smooth functions of integer valued variables (and even quadratic ones like the max-cut problem in graph theory) is known to be NP-hard [1]}. The challenge is to find algorithms that can produce a sensible approximate solution with a manageable computational effort.
Inspired by mixed-integer nonlinear programming (MINLP) problems, several approaches using geometric, analytic, and algebraic techniques have been proposed to transform the discrete problem into a continuous problem. Examples include the use of global or concave optimization formulations, semidefinite programming, and spectral theory (see e.g. [2]}, [3]}, [4]}, [5]}, [6]}).
However, these types of approaches are doomed to fail in the NN context because the number of parameters is several orders of magnitude larger than for classical MINLP problems.
