Approximation of the Proximal Operator of the ℓ_∞ Norm Using a Neural Network

Computing the proximal operator of the ℓ_∞ norm, proxα ||·||_∞(x), generally requires a sort of the input data, or at least a partial sort similar to quicksort. In order to avoid using a sort, we present an O(m) approximation of proxα ||·||_∞(x) using a neural network. A novel aspect of the network is that it is able to accept vectors of varying lengths due to a feature selection process that uses moments of the input data. We present results on the accuracy of the approximation, feature importance, and computational efficiency of the approach. We show that the network outperforms a "vanilla neural network" that does not use feature selection. We also present an algorithm with corresponding theory to calculate proxα ||·||_∞(x) exactly, relate it to the Moreau decomposition, and compare its computational efficiency to that of the approximation.