Charting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...
summary
Constrained-memory algorithms either store a basis or pay huge sample costs: over F2, algorithms with <~d^2/4 bits of memory require exponentially many samples to learn a random parity (Raz’s result formalizes this via branching program reductions). The continuous analogue shows subquadratic space forces at least D · log log(1/ε) samples for linear regression; conjectured optimal is D · log(1/ε). Tools: information-theoretic posteriors, branching programs, and hardness-of-polynomial arguments in the cell probe model.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 2:15Question
- 5:25Discrete vs Continuous
- 12:55Other Models
- 14:26Algorithms
- 19:54Memory via branching programs
- 23:43Memory via cellpro
- 26:48Linear regression
- 42:43Conclusion
related talks
44mParsimonious Learning-Augmented Algorithms
12mTheoretical understanding of learning through the computational lens
01h 08mData Driven Optimization Models and Algorithms
58mMemory-Regret Tradeoff for Online Learning
01h 01mRobustness, Stochastics, Uncertainty 2
01h 14mMachine Learning For Algorithm Design
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs