One of the major mysteries in science is the remarkable success of machine learning. While its empirical achievements have captivated the field, our theoretical comprehension lags significantly behind. This thesis seeks for advancing our theoretical understanding of learning and intelligence from a computational perspective. By studying fundamental learning, optimization and decision making tasks, we aspire to shed lights on the impact of computation for artificial intelligence.
The first part of this thesis concerns the space resource needed for learning. By studying the fundamental role of memory for continual learning, online decision making and convex optimization, we find both continual learning and efficient convex optimization require a lot of memory; while for decision making, exponential savings are possible.
More concretely,
(1) We prove there is no memory deduction in continual learning, unless the continual learner takes multiple passes over the sequence of environments; (2) We prove in order to optimize a convex function in the most iteration efficient way, an algorithm must use a quadratic amount of space;
(3) We show polylogarithmic space is sufficient for making near optimal decisions in an oblivious adversary environment; in a sharp contrast, a quadratic saving is both sufficient and necessary to achieve vanishing regret in an adaptive adversarial environment.
The second part of this thesis uses learning as a tool, and resolves a series of long-standing open questions in algorithmic game theory. By giving an exponential faster no-swap-regret learning algorithm, we obtain algorithms that achieve near-optimal computation/communication/iteration complexity for computing an approximate correlated equilibrium in a normal-form game, and we give the first polynomial-time algorithm for computing approximate normal-form correlated equilibria in imperfect information games (including Bayesian and extensive-form games).
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/p1k2-w069 |
| Date | January 2024 |
| Creators | Peng, Binghui |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0026 seconds