• Straight-Through meets Sparse...

Result: Straight-Through meets Sparse Recovery: the Support Exploration Algorithm

Title:
Straight-Through meets Sparse Recovery: the Support Exploration Algorithm
Authors:
Mohamed, Mimoun, Malgouyres, François, Emiya, Valentin, Chaux, Caroline
Contributors:
éQuipe d'AppRentissage de MArseille (QARMA), Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Image & Pervasive Access Lab (IPAL), National University of Singapore (NUS)-Agency for science, technology and research [Singapore] (A*STAR)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institute for Infocomm Research - I²R [Singapore], Région Sud - Provence-Alpes-Côte d’Azur et Euranova France, ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019)
Publisher Information:
HAL CCSD, 2023.
Publication Year:
2023
Collection:
collection:UNIV-TLSE2
collection:UNIV-TLSE3
collection:UNIV-TLN
collection:CNRS
collection:UNIV-AMU
collection:INSA-TOULOUSE
collection:EC-MARSEILLE
collection:INSMI
collection:IMT
collection:IPAL
collection:I2M
collection:I2M-2014-
collection:UT1-CAPITOLE
collection:TDS-MACS
collection:LIS-LAB
collection:INSA-GROUPE
collection:SORBONNE-UNIVERSITE
collection:SORBONNE-UNIV
collection:SU-SCIENCES
collection:PNRIA
collection:SU-TI
collection:ANR
collection:ANITI
collection:ALLIANCE-SU
collection:INCIAM
collection:UNIV-UT3
collection:UT3-INP
collection:UT3-TOULOUSEINP
Subject Terms:
model selection, support recovery, restricted isometry property, straight-through estimator, sparsity, greedy algorithm, [MATH.MATH-OC]Mathematics [math], Optimization and Control [math.OC], [INFO.INFO-AI]Computer Science [cs], Artificial Intelligence [cs.AI], [INFO.INFO-LG]Computer Science [cs], Machine Learning [cs.LG], [MATH.MATH-ST]Mathematics [math], Statistics [math.ST]
Original Identifier:
ARXIV: 2301.13584
HAL: hal-03964976
Document Type:
Electronic Resource preprint<br />Preprints<br />Working Papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/2301.13584
Access URL:
https://hal.science/hal-03964976
https://hal.science/hal-03964976v2/document
https://hal.science/hal-03964976v2/file/Main_hal.pdf
Rights:
info:eu-repo/semantics/OpenAccess
URL: http://hal.archives-ouvertes.fr/licences/publicDomain/
Accession Number:
edshal.hal.03964976v2
Database:
HAL

Further Information

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.