Online Prediction in Sub-linear Space
We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret $o(T)$ algorithm to $T^{1-\alpha}$ regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary.
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question AnsweringPredictionSimilar Papers 제목 키워드 기반
Linear Tensor Projection Revealing Nonlinearity
Dimensionality reduction is an effective method for learning high-dimensional data, which can provide better understanding of decision boundaries in human-readable low-dimensional subspace. Linear methods, such as princi…
Dimensionality ReductionPredictionOn the relationship between Koopman operator approximations and neural ordinary differential equations for data-driven time-evolution predictions
This work explores the relationship between state space methods and Koopman operator-based methods for predicting the time-evolution of nonlinear dynamical systems. We demonstrate that extended dynamic mode decomposition…
Dictionary LearningTrajectory PredictionData-driven quantum Koopman method for simulating nonlinear dynamics
Quantum computation offers potential exponential speedups for simulating certain physical systems, but its application to nonlinear dynamics is inherently constrained by the requirement of unitary evolution. We propose t…
Deep Koopman Operator with Control for Nonlinear Systems
Recently Koopman operator has become a promising data-driven tool to facilitate real-time control for unknown nonlinear systems. It maps nonlinear systems into equivalent linear systems in embedding space, ready for real…
Experimental assessment of polynomial nonlinear state-space and nonlinear-mode models for near-resonant vibrations
In the present paper, two existing nonlinear system identification methodologies are used to identify data-driven models. The first methodology focuses on identifying the system using steady-state excitations. To accompl…
Cantilever BeamState Space Models