Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm
Mimoun Mohamed, Francois Malgouyres, Valentin Emiya, Caroline Chaux
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.
BibTeX
@inproceedings{
mohamed2024straightthrough,
title={Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm},
author={Mimoun Mohamed and Francois Malgouyres and Valentin Emiya and Caroline Chaux},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
url={https://openreview.net/forum?id=Oj18qGN1gC}
}