Strategic learning : models and solutions

Dans cette thèse, nous considérons le problème de l'apprentissage lorsque les données sont produites de manière stratégique. Cela remet en question l'hypothèse largement utilisée dans l'apprentissage automatique selon laquelle les données de test sont indépendantes des données d'apprentissage. Cette hypothèse est invalide lorsque le résultat de l'apprentissage a un intérêt stratégique pour certains agents. Nous étudions les deux problèmes omniprésents de classification et régression linéaire et plus particulièrement leur propriétés fondamentales par rapport aux modèles classiques où les données ne sont pas produites stratégiquement.Nous considérons d'abord le problème de la classification dans un contexte antagoniste où les données de classe 1 sont générées par un attaquant dont l'objectif n'est pas connu du défenseur --- un aspect qui est essentiel pour des applications réalistes mais qui a jusqu'à présent été négligé dans la littérature. Nous proposons un jeu bayésien où le défenseur choisit un classificateur sans restriction a priori sur l'ensemble des classificateurs possibles. La principale difficulté de ce modèle est que l'ensemble des classificateurs possibles est exponentiel dans l'ensemble des données possibles, qui est lui-même exponentiel dans le nombre de caractéristiques utilisées pour la classification. Pour contrer cela, nous montrons tout d'abord que les équilibres de Nash Bayésiens peuvent être caractérisés complètement via des classificateurs à seuils exprimés avec un faible nombre de paramètres. Nous montrons ensuite que cette caractérisation de faible dimension permet de développer une méthode d'apprentissage utilisant des données d'entraînement pour calculer des classificateurs approximativement optimaux avec de fortes garanties et de développer un algorithme d'apprentissage en ligne satisfaisant la propriété du “no-regret” (nos résultats sont indépendants de la dimension de l'ensemble de données possibles).Nous considérons ensuite le problème de la régression linéaire à partir de sources de données stratégiques. Dans le cadre classique où la précision de chaque point de données est fixe, le théorème d'Aitken/Gauss-Markov en statistique énonce que l'estimateur des moindres carrés généralisés (GLS) est ce que l'on appelle le “meilleur estimateur linéaire sans biais” et est consistant. Dans les applications récentes, cependant, les données peuvent être stratégiques, c'est-à-dire que la production de données précises est coûteuse. Nous modélisons cela comme l'apprentissage en présence de données stratégiques avec un bien public, c'est-à-dire que les données sont fournies par des agents stratégiques qui minimisent un coût individuel de production de données précises tout en bénéficiant de la précision globale du modèle. Nous modélisons l'incertitude sur les données des agents - un aspect critique du problème lorsque le nombre d'agents est important. Nous montrons qu'en général, le théorème d'Aitken n'est plus valide dans ce cadre, bien qu'il soit maintenu si les individus ont des coûts de provision identiques. Lorsque les individus ont des coûts non identiques, nous donnons une borne sur l'amélioration du coût d'estimation à l'équilibre qui peut être obtenu en s'écartant de GLS. Nous caractérisons aussi l’équilibre du jeu, révélant une connexion intéressante avec le problème de design optimal. Par la suite, nous étudions le comportement asymptotique de la covariance des paramètres de régression linéaire estimés par GLS. Nous fournissons des bornes pour cette covariance et montrons que, lorsque les coûts de production des agents sont super-linéaires, la covariance du modèle converge vers zéro mais à un rythme plus lent que les problèmes d'apprentissage classiques. En revanche, si les coûts de production des agents sont linéaires, cette covariance ne converge pas. Cela montre que même la propriété de base de consistance GLS est compromise lorsque les sources de données sont stratégiques.In this thesis, we consider the problem of learning when data are strategically produced. This challenges the widely used assumptions in machine learning that test data are independent from training data which has been proved to fail in many applications where the result of the learning problem has a strategic interest to some agents. We study the two ubiquitous problems of classification and linear regression and focus on fundamental learning properties on these problems when compared to the classical setting where data are not strategically produced.We first consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender---an aspect that is key to realistic applications but has so far been overlooked in the literature.To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no a priori restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the set of possible data, which is itself exponential in the number of features used for classification. To counter this, we first show that Bayesian Nash equilibria can be characterized completely via functional threshold classifiers with a small number of parameters. We then show that this low-dimensional characterization enables us to develop a training method to compute provably approximately optimal classifiers in a scalable manner; and to develop a learning algorithm for the online setting with low regret (both independent of the dimension of the set of possible data).We then consider the problem of linear regression from strategic data sources. In the classical setting where the precision of each data point is fixed, the famous Aitken/Gauss-Markov theorem in statistics states that generalized least squares (GLS) is a so-called ``Best Linear Unbiased Estimator'' (BLUE) and is consistent (the model is perfectly learned when the amount of data grows). In modern data science, however, one often faces strategic data sources, namely, individuals who incur a cost for providing high-precision data. We model this as learning from strategic data sources with a public good component, i.e., when data is provided by strategic agents who seek to minimize an individual provision cost for increasing their data's precision while benefiting from the model's overall precision. Our model tackles the case where there is uncertainty on the attributes characterizing the agents' data---a critical aspect of the problem when the number of agents is large. We show that, in general, Aitken's theorem does not hold under strategic data sources, though it does hold if individuals have identical provision costs (up to a multiplicative factor) . When individuals have non-identical costs, we derive a bound on the improvement of the equilibrium estimation cost that can be achieved by deviating from GLS, under mild assumptions on the provision cost functions and on the possible deviations from GLS. We also provide a characterization of the game's equilibrium, which reveals an interesting connection with optimal design. Subsequently, we focus on the asymptotic behavior of the covariance of the linear regression parameters estimated via generalized least squares as the number of data sources becomes large. We provide upper and lower bounds for this covariance matrix and we show that, when the agents' provision costs are superlinear, the model's covariance converges to zero but at a slower rate relative to virtually all learning problems with exogenous data. On the other hand, if the agents' provision costs are linear, this covariance fails to converge. This shows that even the basic property of consistency of generalized least squares estimators is compromised when the data sources are strategic