Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913474450292736 |
|---|---|
| author | Linehan, Kathryn Balan, Radu |
| author_facet | Linehan, Kathryn Balan, Radu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_11211 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network Linehan, Kathryn Balan, Radu Numerical Analysis Machine Learning 65K10, 68T07 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. |
| title | Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network |
| topic | Numerical Analysis Machine Learning 65K10, 68T07 |
| url | https://arxiv.org/abs/2408.11211 |