Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network
This work addresses a computational bottleneck in optimization for machine learning practitioners, offering a faster alternative to sorting-based methods, though it is incremental as it builds on existing proximal operator techniques.
The paper tackles the problem of computing the proximal operator of the ℓ∞ norm, which typically requires sorting, by proposing an O(m) approximation using a neural network with feature selection for varying input lengths, achieving improved accuracy and efficiency compared to a vanilla neural network.
Computing the proximal operator of the $\ell_\infty$ norm, $\textbf{prox}_{α||\cdot||_\infty}(\mathbf{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 $\textbf{prox}_{α||\cdot||_\infty}(\mathbf{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 $\textbf{prox}_{α||\cdot||_\infty}(\mathbf{x})$ exactly, relate it to the Moreau decomposition, and compare its computational efficiency to that of the approximation.