# Exploiting Subgradient Sparsity in Max-Plus Neural Networks

arXiv: https://arxiv.org/abs/2603.04133 · HTML: https://mlsanity.com/paper/2603.04133/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 14 references that are in the map.
- First posted on arXiv 4 Mar 2026.

## Builds on (most cited first, 8 of 8)

- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning](https://mlsanity.com/paper/1909.10300/) (2019)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [Morphological Network: How Far Can We Go with Morphological Neurons?](https://mlsanity.com/paper/1901.00109/) (2019)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Min-Max-Plus Neural Networks](https://mlsanity.com/paper/2102.06358/) (2021)
- [Max-plus Operators Applied to Filter Selection and Model Pruning in Neural Networks](https://mlsanity.com/paper/1903.08072/) (2019)
- [Sparsity in Max-Plus Algebra and Systems](https://mlsanity.com/paper/1801.09850/) (2018)

## Built on by (most cited first, 1 of 1)

- [On the explainability of max-plus neural networks](https://mlsanity.com/paper/2605.00889/) (2026)

## Abstract (arXiv)

Deep Neural Networks are powerful tools for solving machine learning problems, but their training often involves dense and costly parameter updates. In this work, we use a novel Max-Plus neural architecture in which classical addition and multiplication are replaced with maximum and summation operations respectively. This is a promising architecture in terms of interpretability, but its training is challenging. A particular feature is that this algebraic structure naturally induces sparsity in the subgradients, as only neurons that contribute to the maximum affect the loss. However, standard backpropagation fails to exploit this sparsity, leading to unnecessary computations. In this work, we focus on the minimization of the worst sample loss which transfers this sparsity to the optimization loss. To address this, we propose a sparse subgradient algorithm that explicitly exploits the algebraic sparsity. By tailoring the optimization procedure to the non-smooth nature of Max-Plus models, our method achieves more efficient updates while retaining theoretical guarantees. This highlights a principled path toward bridging algebraic structure and scalable learning.