Straight-Through meets Sparse Recovery: the Support Exploration Algorithm

The {\it 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: {\it sparse support recovery}. We introduce the {\it 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 {\it 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.

Mots clés

model selection support recovery restricted isometry property straight-through estimator sparsity greedy algorithm

Domaines

Optimisation et contrôle [math.OC] Intelligence artificielle [cs.AI] Apprentissage [cs.LG] Statistiques [math.ST]

Fichier principal

Main_hal.pdf (540.06 Ko)

Main_hal.blg (1.12 Ko)

Main_hal.log (76.89 Ko)

Main_hal.out (10.02 Ko)

Main_hal.synctex.gz (451.8 Ko)

images/ICML2024/cal_housing.svg (32.39 Ko)

images/ICML2024/comp-activ-harder.svg (29.47 Ko)

images/ICML2024/f_mse_y.svg (48.96 Ko)

images/ICML2024/f_mse_y_noisy.svg (48.83 Ko)

images/ICML2024/full_signal.svg (113.41 Ko)

images/ICML2024/full_signal_noisy.svg (126.87 Ko)

images/ICML2024/hist.svg (59.73 Ko)

images/ICML2024/hist_noisy.svg (101.48 Ko)

images/ICML2024/ijcnn1.svg (31.94 Ko)

images/ICML2024/iter.svg (66.01 Ko)

images/ICML2024/iter_noisy.svg (107.89 Ko)

images/ICML2024/letter.svg (34.59 Ko)

images/ICML2024/multi_n_supports_log.svg (68.59 Ko)

images/ICML2024/multi_n_supports_log_noisy.svg (68.6 Ko)

images/ICML2024/slice.svg (39.73 Ko)

images/ICML2024/sota.svg (26.27 Ko)

images/ICML2024/sota_noisy.svg (26.27 Ko)

images/ICML2024/sup_dist.svg (45.52 Ko)

images/ICML2024/sup_dist_noisy.svg (45.51 Ko)

images/ICML2024/unifr1000.svg (37.95 Ko)

images/ICML2024/unifr1000_noisy_n1e2.svg (37.93 Ko)

images/ICML2024/unifr1000_noisy_n1e2_zoom.svg (19.46 Ko)

images/ICML2024/ws.svg (46.44 Ko)

images/ICML2024/ws_noisy.svg (46.17 Ko)

images/ICML2024/year.svg (38.64 Ko)

images/ICML2024/zoom_signal_complete.svg (99.73 Ko)

images/ICML2024/zoom_signal_complete_noisy.svg (107.96 Ko)

images/ICML2024/zoom_signal_light.svg (56.5 Ko)

images/ICML2024/zoom_signal_light_noisy.svg (57.26 Ko)

svg-inkscape/cal_housing_svg-tex.pdf (20.17 Ko)

svg-inkscape/cal_housing_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/comp-activ-harder_svg-tex.pdf (18.27 Ko)

svg-inkscape/comp-activ-harder_svg-tex.pdf_tex (2.04 Ko)

svg-inkscape/f_mse_y_noisy_svg-tex.pdf (27.66 Ko)

svg-inkscape/f_mse_y_noisy_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/f_mse_y_svg-tex.pdf (27.71 Ko)

svg-inkscape/f_mse_y_svg-tex.pdf_tex (2.01 Ko)

svg-inkscape/full_signal_noisy_svg-tex.pdf (130.92 Ko)

svg-inkscape/full_signal_noisy_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/full_signal_svg-tex.pdf (111.73 Ko)

svg-inkscape/full_signal_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/hist_noisy_svg-tex.pdf (48.39 Ko)

svg-inkscape/hist_noisy_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/hist_svg-tex.pdf (33.42 Ko)

svg-inkscape/hist_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/ijcnn1_svg-tex.pdf (21.32 Ko)

svg-inkscape/ijcnn1_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/iter_noisy_svg-tex.pdf (47.86 Ko)

svg-inkscape/iter_noisy_svg-tex.pdf_tex (2.01 Ko)

svg-inkscape/iter_svg-tex.pdf (33.62 Ko)

svg-inkscape/iter_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/letter_svg-tex.pdf (23.66 Ko)

svg-inkscape/letter_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/multi_n_supports_log_noisy_svg-tex.pdf (59.04 Ko)

svg-inkscape/multi_n_supports_log_noisy_svg-tex.pdf_tex (2.05 Ko)

svg-inkscape/multi_n_supports_log_svg-tex.pdf (59.03 Ko)

svg-inkscape/multi_n_supports_log_svg-tex.pdf_tex (2.04 Ko)

svg-inkscape/slice_svg-tex.pdf (24.71 Ko)

svg-inkscape/slice_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/sota_noisy_svg-tex.pdf (14.55 Ko)

svg-inkscape/sota_noisy_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/sup_dist_noisy_svg-tex.pdf (24.98 Ko)

svg-inkscape/sup_dist_noisy_svg-tex.pdf_tex (2.03 Ko)

svg-inkscape/sup_dist_svg-tex.pdf (24.97 Ko)

svg-inkscape/sup_dist_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/unifr1000_noisy_n1e2_svg-tex.pdf (24.02 Ko)

svg-inkscape/unifr1000_noisy_n1e2_svg-tex.pdf_tex (2.05 Ko)

svg-inkscape/unifr1000_noisy_n1e2_zoom_svg-tex.pdf (10.32 Ko)

svg-inkscape/unifr1000_noisy_n1e2_zoom_svg-tex.pdf_tex (2.05 Ko)

svg-inkscape/unifr1000_svg-tex.pdf (24.03 Ko)

svg-inkscape/unifr1000_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/ws_noisy_svg-tex.pdf (28.4 Ko)

svg-inkscape/ws_noisy_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/ws_svg-tex.pdf (28.46 Ko)

svg-inkscape/ws_svg-tex.pdf_tex (2 Ko)

svg-inkscape/year_svg-tex.pdf (24.79 Ko)

svg-inkscape/year_svg-tex.pdf_tex (2.02 Ko)

svg-inkscape/zoom_signal_complete_noisy_svg-tex.pdf (50.7 Ko)

svg-inkscape/zoom_signal_complete_noisy_svg-tex.pdf_tex (2.05 Ko)

svg-inkscape/zoom_signal_complete_svg-tex.pdf (43.87 Ko)

svg-inkscape/zoom_signal_complete_svg-tex.pdf_tex (2.04 Ko)

svg-inkscape/zoom_signal_light_noisy_svg-tex.pdf (23.45 Ko)

svg-inkscape/zoom_signal_light_noisy_svg-tex.pdf_tex (2.04 Ko)

Origine	Fichiers produits par l'(les) auteur(s)

Francois Malgouyres : Connectez-vous pour contacter le contributeur

https://hal.science/hal-03964976

Soumis le : mercredi 7 février 2024-14:40:14

Dernière modification le : lundi 10 juin 2024-16:50:19

Dates et versions

hal-03964976 , version 1 (31-01-2023)

hal-03964976 , version 2 (07-02-2024)

hal-03964976 , version 3 (24-06-2024)

Licence

Domaine public

Identifiants

HAL Id : hal-03964976 , version 2
ARXIV : 2301.13584

Citer

Mimoun Mohamed, François Malgouyres, Valentin Emiya, Caroline Chaux. Straight-Through meets Sparse Recovery: the Support Exploration Algorithm. 2023. ⟨hal-03964976v2⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

1235 Consultations

647 Téléchargements