On adaptivity in active sequential learning

Abstract

In this thesis, we address several problems in active and sequential learning. Using the frameworks of the stochastic multi-armed bandit problem and nonparametric statistics, we make several contributions in active learning and zeroth order stochastic optimization. We are particularly interested in the problem of designing adaptive algorithmic strategies, in the sense that they do not require the careful tuning of parameters that are out of reach for practitioners. This is particularly important in the context of active sequential learning, as the careful selection of which data to label, in the abundance of unlabeled data, depends on these tuning parameters. Therefore, sub-optimal learning may incur avoidable labeling costs or lead to poor performance. In some settings, we design such adaptive algorithms and show their optimality. In others, we prove impossibility theorems that preclude their existence.

In dieser Dissertation beschäftigen wir uns mit verschiedenen Problemen des aktiven und sequentiellen Maschinenlernens. Unter Verwendung der Rahmenbedingungen des stochastischen mehrarmigen Banditenproblems und der nichtparametrischen Statistik leisten wir verschiedene Beiträge zum aktiven Lernen und zur stochastischen Optimierung nullter Ordnung. Wir sind besonders an dem Problem interessiert, adaptive algorithmische Strategien zu entwerfen, in dem Sinne, dass sie keine sorgfältige Abstimmung von Parametern erfordern, die für Praktiker unerreichbar sind. Dies ist besonders wichtig im Zusammenhang mit aktivem sequentiellem Lernen, da die sorgfältige Auswahl der zu kennzeichnenden Daten in der Fülle nicht beschrifteter Daten von diesen Abstimmungsparametern abhängen kann. Daher kann suboptimales Lernen vermeidbare Kennzeichnungskosten verursachen oder zu einer schlechten Leistung führen. In einigen Einstellungen entwerfen wir solche adaptiven Algorithmen und zeigen ihre Optimalität. In anderen beweisen wir Unmöglichkeitssätze, die ihre Existenz ausschließen.