Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm

Mimoun Mohamed, Francois Malgouyres, Valentin Emiya, Caroline Chaux
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:35968-36011, 2024.

Abstract

The straight-through estimator (STE) is commonly used to optimize quantized neural networks, yet its contexts of effective performance are still unclear despite empirical successes. To make a step forward in this comprehension, we apply STE to a well-understood problem: sparse support recovery. We introduce the Support Exploration Algorithm (SEA), a novel algorithm promoting sparsity, and we analyze its performance in support recovery (a.k.a. model selection) problems. SEA explores more supports than the state-of-the-art, leading to superior performance in experiments, especially when the columns of $A$ are strongly coherent. The theoretical analysis considers recovery guarantees when the linear measurements matrix $A$ satisfies the Restricted Isometry Property (RIP). The sufficient conditions of recovery are comparable but more stringent than those of the state-of-the-art in sparse support recovery. Their significance lies mainly in their applicability to an instance of the STE.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-mohamed24a, title = {Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm}, author = {Mohamed, Mimoun and Malgouyres, Francois and Emiya, Valentin and Chaux, Caroline}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {35968--36011}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/mohamed24a/mohamed24a.pdf}, url = {https://proceedings.mlr.press/v235/mohamed24a.html}, abstract = {The straight-through estimator (STE) is commonly used to optimize quantized neural networks, yet its contexts of effective performance are still unclear despite empirical successes. To make a step forward in this comprehension, we apply STE to a well-understood problem: sparse support recovery. We introduce the Support Exploration Algorithm (SEA), a novel algorithm promoting sparsity, and we analyze its performance in support recovery (a.k.a. model selection) problems. SEA explores more supports than the state-of-the-art, leading to superior performance in experiments, especially when the columns of $A$ are strongly coherent. The theoretical analysis considers recovery guarantees when the linear measurements matrix $A$ satisfies the Restricted Isometry Property (RIP). The sufficient conditions of recovery are comparable but more stringent than those of the state-of-the-art in sparse support recovery. Their significance lies mainly in their applicability to an instance of the STE.} }
Endnote
%0 Conference Paper %T Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm %A Mimoun Mohamed %A Francois Malgouyres %A Valentin Emiya %A Caroline Chaux %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-mohamed24a %I PMLR %P 35968--36011 %U https://proceedings.mlr.press/v235/mohamed24a.html %V 235 %X The straight-through estimator (STE) is commonly used to optimize quantized neural networks, yet its contexts of effective performance are still unclear despite empirical successes. To make a step forward in this comprehension, we apply STE to a well-understood problem: sparse support recovery. We introduce the Support Exploration Algorithm (SEA), a novel algorithm promoting sparsity, and we analyze its performance in support recovery (a.k.a. model selection) problems. SEA explores more supports than the state-of-the-art, leading to superior performance in experiments, especially when the columns of $A$ are strongly coherent. The theoretical analysis considers recovery guarantees when the linear measurements matrix $A$ satisfies the Restricted Isometry Property (RIP). The sufficient conditions of recovery are comparable but more stringent than those of the state-of-the-art in sparse support recovery. Their significance lies mainly in their applicability to an instance of the STE.
APA
Mohamed, M., Malgouyres, F., Emiya, V. & Chaux, C.. (2024). Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:35968-36011 Available from https://proceedings.mlr.press/v235/mohamed24a.html.

Related Material