Simulation et optimisation pour les problèmes de grandes tailles
Les méthodes de simulation Monte Carlo sont des outils numériques fondamentaux pour l’estimation de modèles à données latentes et la résolution de problèmes inverses. Cependant les problématiques d’apprentissage modernes supposent le traitement de données massives, pouvant être elles-mêmes de très grande dimension. Dans ce double contexte de données massives et/ou de grande dimension, d’importants défis restent encore à relever. En effet, peu de travaux ont été dédiés à l’étude des méthodes de Monte Carlo séquentielles ou des méthodes MCMC lorsque la dimension du problème augmente ; les défis tiennent à la taille des supports à explorer, à la possible multi-modalité des lois, et à une structure de dépendance possiblement complexe entre les données.
Il est nécessaire de développer de nouveaux algorithmes capables de traiter efficacement, rapidement et de façon robuste les problèmes impliquant une grande masse de données ou portant sur des données de grande dimension. Les progrès récents dans le domaine des capteurs d’images engendrent des masses de données toujours plus grandes, ce qui met en difficulté les algorithmes traditionnels d’optimisation. Dans ce contexte, il devient préférable de concevoir des algorithmes d’optimisation capables de prendre en compte la structure du problème ; de gérer des jeux de données incomplets, distribués et variables dans le temps ; et/ou d’utiliser des infrastructures de calcul et de stockage massivement parallèles.
En particulier, un défi actuel consiste à étendre les stratégies parallèles alternées par blocs dans un contexte plus général (distribué, non convexe ou non lisse). Une autre façon de traiter les problèmes de grande dimension consiste à utiliser une stratégie de minimisation au fil de l’eau. Cependant de nombreuses méthodes du premier ordre (tels que les algorithmes de descente de gradient stochastique) pâtissent d’une vitesse de convergence lente. Il convient donc de rechercher des stratégies d’accélération applicables à une large classe d’algorithmes.
Optimisation distribuée
Le scénario commun à l’ensemble des travaux sur l’optimisation distribuée consiste en l’existence d’entités indépendantes (les agents), dotées de capacités de calcul et capables de communiquer entre elles au sein d’un graphe dont les arêtes correspondent aux paires d’agents capables d’échanger des messages. Une telle architecture distribuée apparaît naturellement dans les réseaux de capteurs, mais aussi en apprentissage statistique, où la volumétrie des données impose de résoudre des problèmes d’optimisation en tirant parti de plusieurs entités de calcul oeuvrant simultanément.
Au cours de la dernière décennie, de nombreux algorithmes ont été proposés afin de permettre à des agents d’atteindre un consensus sur la solution d’un problème d’optimisation, dont la fonction de coût ne serait que partiellement connue de chaque agent. Les méthodes ont bénéficié de fortes interactions avec le domaine de l’optimisation (algorithmes primaux, primaux-duaux, etc.) et du traitement adaptatif du signal (filtrage, approximation stochastique, etc.). L’optimisation distribuée entre aujourd’hui dans une phase de maturation où il convient de démontrer l’applicabilité des méthodes à des contextes applicatifs précis : cluster computing, localisation dans les réseaux de capteurs, clustering d’utilisateurs dans les réseaux mesh, contrôle ou planification de flottille, etc. D’un point de vue théorique, il s’agit de pousser plus avant l’extension des méthodes nouvelles d’optimisation, déterministes ou stochastiques, dans un contexte distribué. Enfin, un enjeu important consiste à établir des rapprochements théoriques avec la théorie des jeux.
Matrices aléatoires
Compte tenu du développement considérable des dispositifs d’acquisition et des réseaux de capteurs, il est aujourd’hui courant d’être confronté à des signaux de grandes dimensions dans des contextes applicatifs aussi divers que les communications numériques (systèmes multi-antennes massifs, OFDM), le traitement des signaux radar (STAP, MIMO), le bio-médical (génomique, détection de biomarqueurs), la surveillance de l’environnement ou des procédés industriels, l’analyse des séries temporelles financières, etc.
En pratique, le nombre d’observations disponibles des signaux pouvant être relativement limité (durée et/ou stationnarité courtes), on est alors confronté à des signaux dont la dimension M est du même ordre de grandeur que le nombre d’échantillons N (avec M, N potentiellement grands). Dans ce régime où M est d’ordre de grandeur de N, nombre de méthodes statistiques classiques ne se comportent plus comme dans le cas standard où N >> M. Il s’agit du cas des méthodes mettant en jeu des fonctionnelles de la matrice de covariance empirique des observations, en particulier ses valeurs propres et vecteurs propres. Les avancées théoriques vers la caractérisation des vecteurs propres (et non plus seulement des valeurs propres), ainsi que de certains modèles nouveaux (tels que les modèles dits spiked), ont permis au spectre applicatif de s’étendre aux méthodes de détection et d’estimation en traitement du signal (par exemple les méthodes de sous-espaces de type MUSIC).
Il est à noter que peu d’études ont été réalisées jusqu’à présent pour le modèle dit factoriel dynamique, où le signal observé est une version bruitée de la sortie d’un système linéaire K entrées / M sorties (K < M) excité par un signal utile de dimension K non observable. Les problèmes d’inférence statistique liés à ce modèle très populaire ont bien sûr été très abondamment étudiés depuis une cinquantaine d’années (estimation de paramètres de modèles ARMA vectoriels, de modèles d’état et des filtres de Kalman associés, estimation non paramétrique des densités spectrales, tests d’indépendance mutuelle entre les M composantes de l’observation, test de blancheur temporelle de l’observation, tests de détection d’un signal utile, etc.) dans le contexte des petites dimensions. Cependant, le cas où M et N tendent vers l’infini n’a été que très peu abordé. Pour aborder ces problématiques, il va s’avérer nécessaire d’étudier finement, dans le régime des grandes dimensions, le comportement de diverses fonctionnelles de statistiques telles que les matrices de covariance spatio-temporelles empiriques, les matrices d’auto-covariance empiriques entre passé et futur, les estimateurs non paramétriques usuels de densité spectrale, et d’en déduire des techniques d’inférence statistique adaptées aux modèles linéaires factoriels de grandes dimensions.
