Résumé technique : Régression active pour les modèles à indice unique avec fonctions de lien inconnues

Formulation du problème

Cet article traite du problème de la régression active pour les modèles à indice unique sous une perte $\ell_p$ générale ($p \ge 1$). L'objectif est de trouver un vecteur $x \in \mathbb{R}^d$ et une fonction de lien $f$ appartenant à la classe des fonctions 1-Lipschitziennes ($\text{Lip}_1$) qui minimisent le résidu :
$$\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|f(Ax) - b\|_p^p$$
où $A \in \mathbb{R}^{n \times d}$ est une matrice de données connue ($n \gg d$) et $b \in \mathbb{R}^n$ est un vecteur d'étiquettes. Le cadre est actif, ce qui signifie que l'algorithme a un accès complet à $A$ mais ne peut accéder à $b$ que via des requêtes de coordonnées. Le défi spécifique abordé est le cas où la fonction de lien $f$ est inconnue, contrastant avec les travaux antérieurs qui supposaient que $f$ était connue.

Méthodologie

Borne supérieure : Algorithme d'échantillonnage non adaptatif

Les auteurs proposent un algorithme d'échantillonnage non adaptatif (Algorithme 2) qui étend le cadre de l'échantillonnage par poids de Lewis utilisé dans la régression linéaire et la régression à indice unique avec lien connu.

1. Construction du poids de Lewis : L'algorithme calcule les poids de Lewis $w_1, \dots, w_n$ pour la matrice $A$.
2. Division des lignes et échantillonnage : Conceptuellement, la $i$-ème ligne de $A$ est divisée en $k_i \approx w_i \cdot (n/d)$ copies. Ces lignes sont échantillonnées de manière indépendante avec une probabilité globale $\alpha$.
3. Optimisation par esquisse (Sketched Optimization) : L'algorithme résout un problème de minimisation régularisé sur l'instance esquissée :
   $$(\hat{f}, \hat{x}) := \arg\min_{f \in \text{Lip}_1, x \in \mathbb{R}^d} \|S(f(Ax) - b)\|_p^p + \epsilon \|Ax\|_p^p$$
   où $S$ est une matrice d'échantillonnage diagonale aléatoire.

Analyse technique : Contrôle de la fonction de lien inconnue

La contribution technique centrale réside dans la limitation de l'erreur d'échantillonnage uniforme lorsque $f$ est inconnue. L'analyse repose sur le contrôle d'un processus de Rademacher $\Psi$ sur l'ensemble $T \subseteq \text{Lip}_1 \times \mathbb{R}^d$.

• Symétrisation et intégrale de Dudley : L'erreur est bornée en utilisant l'intégrale de Dudley appliquée à un processus de Rademacher.
• Défi du découplage : Contra Contrairement aux travaux précédents où l'ensemble d'indice possédait une structure de produit (permettant un découplage facile de $f$ et $x$), l'exigence d'une approximation $(1+\epsilon)$ entraîne un ensemble d'indice non rectangulaire. Les auteurs découplent $f$ et $x$ à mi-chemin dans la chaîne d'inégalités plutôt qu'au niveau de l'ensemble.
• Entropie de métrique de $\text{Lip}_1$ : Une contribution novatrice est le contrôle de l'entropie métrique de la classe Lipschitzienne sous des normes de sup non standard. Les auteurs introduisent un lemme de recouvrement (Lemme 1.3) qui borne le nombre de recouvrement de $\text{Lip}_1$ sous une norme pondérée par le nombre de recouvrement $L_\infty$ standard sur $[-1, 1]$. Cela évite la surcharge technique d'une discrétisation explicite utilisée dans les résultats précédents pour $p=2$.
• Bootstrapping : Un argument de bootstrapping est employé pour affiner la solution d'une approximation à un facteur constant vers une approximation $(1+\epsilon)$.

Borne inférieure : Construction d'une instance difficile

Pour établir la compacité, les auteurs construisent une instance difficile pour $p > 2$ impliquant :

• Code sphérique : $N$ vecteurs unitaires presque orthogonaux avec cohérence $\tau$.
• Indice caché : Un indice $I \in [N]$ uniformément aléatoire est « planté » dans le vecteur de réponse $b$.
• Lien ReLU : La fonction de lien est fixée comme $f(t) = \max\{0, t\}$.
• Garantie de liste courte : L'analyse montre que tout algorithme satisfaisant la garantie d'approximation doit identifier une « liste courte » d'indices candidats contenant le vrai $I$. En bornant la taille de cette liste courte et en comparant les ensembles de requêtes de l'entrée de base $b(0)$ par rapport à $b(I)$, ils dérivent une borne inférieure de requêtes en utilisant le théorème minimax de Yao.

Contributions clés et résultats

1. Borne supérieure (Théorème 1.1 / 3.2)

Le papier présente un algorithme randomisé qui atteint une $(1+\epsilon)$-approximation pour un $p \ge 1$ général avec des fonctions de lien inconnues.

• Complexité de requête : L'algorithme effectue $O(d^{1 \vee p/2} / \epsilon^{p \vee 2} \cdot \text{poly}(\log n))$ requêtes non adaptatives à $b$.
• Signification : Ce résultat améliore strictement le seul résultat antérieur pour les liens inconnus (qui était limité à $p=2$ et une approximation à facteur constant) et correspond à la complexité de requête du cas avec lien connu à un facteur logarithmique près en $n$.

2. Borne inférieure (Théorème 1.2 / 4.2)

Pour $p > 2$, le papier établit une borne inférieure presque serrée sur la complexité de requête.

• Complexité : Tout algorithme randomisé atteignant la garantie d'approximation doit interroger $\Omega_p(d^{p/2} / (\epsilon^p (\log(d/\epsilon))^{p/2}))$ entrées de $b$ dans le pire des cas (en supposant que $d \gtrsim \log(d/\epsilon)$).
• Signification : Cela comble l'écart pour $p > 2$, montrant que la borne supérieure existante de $\tilde{O}(d^{p/2}/\epsilon^p)$ est serrée à des facteurs logarithmiques près, même pour les requêtes adaptatives.

Signification et affirmations

Le papier affirme combler une grande partie de l'écart restant dans la régression $\ell_p$ active pour les modèles à indice unique.

• Généralisation : Il étend la compréhension de la régression active des modèles linéaires et des modèles à indice unique à lien connu vers le cadre plus difficile de fonctions de lien inconnues pour un $p \ge 1$ général.
• Optimalité : En fournissant des bornes supérieure et inférieure correspondantes (à des facteurs logarithmiques près) pour $p > 2$ et en améliorant la garantie d'approximation pour $p=2$, ce travail fournit une caractérisation complète de la complexité de requête pour cette classe de problèmes.
• Nouveauté technique : Le développement d'un lemme de recouvrement pour les fonctions Lipschitziennes sous des normes pondérées et la gestion des ensembles d'indices non rectangulaires dans l'analyse de l'intégrale de Dudley sont présentés comme des avancées techniques clés permettant le résultat pour $p$ général.

Les auteurs notent explicitement que bien que les facteurs $\log n$ dans la borne supérieure soient actuellement présents en raison du nombre de recouvrement intrinsèque des fonctions Lipschitziennes, il reste une question ouverte de savoir si ces facteurs peuvent être éliminés. Le papier ne propose pas de validations expérimentales ou d'applications concrètes spécifiques au-delà du cadre théorique de l'algèbre linéaire numérique randomisée.