EAPSI: Computationally Efficient Adaption to Data Irregularities

Spece Michael, Pittsburgh PA

Investigators

Abstract

The PI and others have shown that in many interesting cases (e.g. in estimating a linear regression model or learning to play a game well) learning from highly irregular data (e.g. macroeconomic variables or the observed play of an unpredictable opponent) is not much harder than learning from regular data, provided exponentially high computational resources. The PI will therefore investigate computationally efficient methods for learning from data with minimal assumptions about its regularity. Though statistical machines are often designed for specific forms of theoretical regularity, theoretical assumptions are often violated in practice. In particular, it may not be known how representative of the future data is. For example, macroeconomic data is highly irregular yet is typically modeled as if it were. Fortunately, when learning from highly irregular data is not much harder than learning from regular data, methods optimal for irregular data will automatically be competitive with (if not vastly superior to) methods designed specifically for regular data, even when the data happens to be regular. Designing learners for irregular data is therefore a statistically sound and flexible approach, but one which requires computational advances, as is to be addressed by the proposed work. This research is part of an international collaboration with Dr. Jian Li at Tsinghua University, China. The proposed work relies on methods from online regret-based learning, namely expert ensembles. In the experts setting, learning takes the form of doing almost as well as the best expert in hindsight, and is accomplished by mixing the experts' advice. The PI proposes to attain computational efficiency by limiting the feedback from the ensemble, via sampling a subset of experts every period of time. In that way, per period, less resources are spent on computing expert advice and less read and writes on updating expert weights; and the storage required for expert weights grows more slowly over time. In particular, limiting feedback to one expert per period corresponds to the bandits setting from the literature. The East Asia and Pacific Summer Institutes program award supports summer U.S. graduate student research, and is jointly funded by the National Science Foundation and the Chinese Ministry of Science and Technology.