Résumé technique : Apprentissage efficace de matrices structurées par requêtes

Énoncé du problème

L'article traite du problème de l'apprentissage d'une approximation structurée d'une matrice $n \times n$ inconnue $A$, en ayant accès uniquement à des requêtes de produit matrice-vecteur (matvec) de la forme $x \to Ax$ et $x \to A^Tx$, où les vecteurs de requête $x$ peuvent être choisis de manière adaptative en fonction des réponses précédentes.

L'objectif est défini par le Problème 1 : Étant donné une classe d'hypothèses (famille de matrices) $\mathcal{F} \subset \mathbb{R}^{n \times n}$, trouver une matrice $\tilde{B} \in \mathcal{F}$ telle que :
$$\|A - \tilde{B}\|_F \leq \gamma \cdot \inf_{B \in \mathcal{F}} \|A - B\|_F$$
pour un certain facteur d'approximation $\gamma \geq 1$, en utilisant le nombre minimum de requêtes matvec. Ce cadre est « agnostique », ce qui signifie que $A$ n'appartient pas nécessairement à $\mathcal{F}$ et n'est pas générée par une distribution spécifique au sein de celle-ci.

Les travaux antérieurs se sont largement concentrés sur des familles structurées spécifiques (par exemple, matrices de rang-$k$, creuses ou hiérarchiques) et ont établi des bornes de complexité de requête, montrant souvent que $O(\log |\mathcal{F}|)$ requêtes suffisent en utilisant des techniques de sketching standard ou des requêtes de type vecteur-matrice-vecteur ($x^T A y$). L'article cherche à généraliser cela à des familles finies arbitraires et à déterminer si la nature multidimensionnelle des sorties matvec (où $Ax$ est un vecteur, et non un scalaire) permet d'améliorer la complexité de requête par rapport au modèle vecteur-matrice-vecteur.

Méthodologie

1. Base de référence unilatérale (Affinement itératif)

Les auteurs analysent d'abord un algorithme unilatéral (utilisant uniquement $x \to Ax$) qui sert de base de référence. Cet algorithme affine de manière itérative un ensemble de candidats $\mathcal{C} \subseteq \mathcal{F}$ :

1. Extraire une matrice de sketching aléatoire $\Pi$ possédant $\ell = O(\log \log |\mathcal{F}|)$ colonnes.
2. Calculer $Z = A\Pi$.
3. Éliminer tous les $B \in \mathcal{C}$ où $\|Z - B\Pi\|_F$ est significativement plus grand que la borne d'erreur optimale.
4. Répéter pour $T = O(\log |\mathcal{F}| / \log \log |\mathcal{F}|)$ itérations.

Cette approche atteint une complexité de requête de $O(\log |\mathcal{F}|)$, ce qui correspond aux bornes connues pour les requêtes vecteur-matrice-vecteur.

2. Simulation bilatérale (L'innovation centrale)

La contribution principale est un algorithme qui utilise à la fois $A$ et $A^T$ pour obtenir une amélioration quasi quadratique de la complexité de requête, réduisant la dépendance vis-à-vis de $|\mathcal{F}|$ de $O(\log |\mathcal{F}|)$ à $\tilde{O}(\sqrt{\log |\mathcal{F}|})$.

L'algorithme simule l'affinement itératif unilatéral mais évite de calculer directement $A\Pi$ à chaque étape. Au lieu de cela, il pré-calcule un sketch gauche $W = \Psi^T A$ en utilisant $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ requêtes vers $A^T$. À chaque itération, il extrait un sketch droit $\Pi$ et tente de déterminer si $\Pi$ est « productif » (c'est-à-dire s'il élimine une grande fraction des mauvais candidats) sans interroger $A$ à nouveau.

La simulation repose sur une dichotomie :

• Cas 1 (Sketch productif) : Si le sketch aléatoire $\Pi$ élimine une grande fraction de candidats, l'algorithme effectue les requêtes à droite $A\Pi$ pour filtrer l'ensemble.
• Cas 2 (Sketch improductif) : Si $\Pi$ éliminerait peu de candidats, l'algorithme utilise le sketch gauche pré-calculé $W$ pour trouver une matrice « représentative » $R \in \mathcal{C}$ telle que $\|A\Pi - R\Pi\|_F$ soit faible. Cela est fait en échantillonnant des candidats et en vérifiant $\|W\Pi - \Psi^T B \Pi\|_F$. Si un représentant est trouvé, l'algorithme peut filtrer l'ensemble des candidats en utilisant la règle de proxy $\|R\Pi - B\Pi\|_F$ sans jamais calculer $A\Pi$.

Pour gérer la dépendance entre l'ensemble des candidats et le sketch gauche $\Psi$, l'algorithme extrait $r = O(\log |\mathcal{F}|)$ sketches droits par itération et utilise une borne d'union sur tous les ensembles de candidats possibles qui pourraient résulter, garantant que le sketch gauche reste précis pour tous les représentants potentiels.

3. Gestion de l'erreur optimale inconnue

Les algorithmes nécessitent initialement une borne supérieure $M$ sur l'erreur optimale $\text{OPT} = \min_{B \in \mathcal{F}} \|A - B\|_F$. Les auteurs fournissent une procédure de recherche binaire (Algorithme 4) qui :

1. Calcule une borne initiale grossière $M_{init}$ à l'aide d'un algorithme de sketching simple.
2. Affine cette borne via une recherche binaire, en utilisant le principal algorithme bilatéral comme sous-routine pour tester des bornes candidates.
3. Atteint une approximation $(3+\epsilon)$ avec une haute probabilité.

4. Extension aux familles infinies

En utilisant des arguments de nombre de recouvrement (covering number), les résultats pour les familles finies sont étendus aux familles infinies. Pour une famille ayant un nombre de recouvrement $\Gamma_\alpha$, la complexité de requête devient $\tilde{O}(\sqrt{\log \Gamma_\alpha})$. Plus précisément, pour les familles linéairement paramétrées de dimension $q$ (par exemple, matrices de bandes, de Toeplitz, de Hankel), le nombre de recouvrement passe proportionnellement à $q$, conduisant à une complexité de requête de $\tilde{O}(\sqrt{q})$.

Résultats clés

Bornes théoriques

• Théorème 1 (Borne supérieure pour famille finie) : Pour toute famille finie $\mathcal{F}$, il existe un algorithme utilisant $\tilde{O}(\sqrt{\log |\mathcal{F}|}/\epsilon^2)$ requêtes matvec pour trouver $\tilde{B} \in \mathcal{F}$ satisfaisant $\|A - \tilde{B}\|_F \leq (3+\epsilon) \min_{B \in \mathcal{F}} \|A - B\|_F$ avec une haute probabilité.
• Théorème 2 (Borne inférieure) : Tout algorithme résolvant le Problème 1 pour des familles finies générales avec un facteur d'approximation constant $\gamma$ nécessite $\Omega(\sqrt{\log |\mathcal{F}|}/\log \gamma)$ requêtes matvec. Cela établit que la dépendance $\sqrt{\log |\mathcal{F}|}$ dans la borne supérieure est serrée à des facteurs $\log\text{-}\log$ près.
• Corollaire 1 (Familles linéaires) : Pour les familles linéairement paramétrées de dimension $q$, une approximation quasi optimale peut être apprise avec $\tilde{O}(\sqrt{q})$ requêtes. Cela améliore la borne $O(q)$ atteignable via le sketching unilatéral ou les requêtes vecteur-matrice-vecteur.

Améliorations spécifiques

• Amélioration quadratique : Ce travail démontre que les requêtes matvec ($x \to Ax$) offrent un avantage quasi quadratique par rapport aux requêtes vecteur-matrice-vecteur ($x^T A y$) pour l'apprentissage de matrices structurées. Alors que les requêtes vecteur-matrice-vecteur nécessitent $O(\log |\mathcal{F}|)$ requêtes, les requêtes matvec n'en nécessitent que $\tilde{O}(\sqrt{\log |\mathcal{F}|})$.
• Matrices Butterfly : La borne inférieure implique que pour les matrices butterfly de rang constant (qui possèdent $\tilde{O}(n)$ paramètres), $\tilde{O}(\sqrt{n})$ requêtes sont nécessaires et suffisantes, ce qui correspond aux meilleures bornes supérieures connues à des facteurs logarithmiques près.

Signification et affirmations

L'article affirme initier l'étude de l'approximation de matrices structurées dans une plus grande généralité, allant au-delà des familles de matrices spécifiques vers des familles finies et infinies arbitraires. Sa principale importance réside dans :

1. L'établissement d'une théorie générale : Fournir un cadre pour caractériser la complexité de requête basée sur la taille (ou le nombre de recouvrement) de la classe d'hypothèses, de manière analogue à la dimension VC dans l'apprentissage supervisé, mais adaptée au modèle matvec.
2. La démonstration de la puissance de la sortie multidimensionnelle : Prouver que la capacité d'interroger $A$ et $A^T$ et d'observer des sorties vectorielles permet une réduction fondamentale de la complexité de requête par rapport aux modèles à sortie scalaire (vecteur-matrice-vecteur).
3. La précision des bornes : Montrer que la borne $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ est essentiellement optimale pour les familles finies, comblant l'écart entre les bornes supérieures et inférieures pour ce cadre général.

Les auteurs notent que leurs résultats actuels atteignent une approximation à facteur constant ($\gamma = 3+\epsilon$) et qu'obtenir une approximation $(1+\epsilon)$ avec la même complexité de requête reste un problème ouvert. Ils soulignent également que leur algorithme repose sur l'adaptativité pour les requêtes du côté droit, et que la nécessité de l'adaptivité pour atteindre la borne $\sqrt{\log |\mathcal{F}|}$ n'est pas encore prouvée.