Memory-sample tradeoffs for linear regression with small error
Memory-sample tradeoffs for linear regression with small error
复制标题
DOI：
10.1145/3313276.3316403
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Vatsal Sharan;Aaron Sidford;G. Valiant
中科院分区：
文献类型：
--
作者：
Vatsal Sharan;Aaron Sidford;G. Valiant
我们考虑的问题进行线性回归流的d维的例子，并表明，任何算法，使用次二次量的内存表现出更慢的收敛速度比可以实现没有内存约束。具体地，考虑一系列标记的示例（a1，b1），（a2，b2）...，其中ai独立于d维各向同性高斯分布绘制，并且其中bi = ai，x + ηi，对于固定的x ∈ d，||X|| 2 = 1，且独立噪声ηi均匀地从区间[−2−d/5，2 −d/5]中抽取。我们表明，任何算法与最多d2/4位的内存需要至少Ω（dloglog 1/）的样本，以近似x到102错误成功的概率至少为2/3，足够小的函数d。相比之下，对于这样的k，x可以以1−o（1）的概率恢复到错误k，使用d个例子，内存为O（d2 log（1/k））。这代表了具有超线性记忆的回归的第一个非平凡下限，并且可能为连续优化的强记忆/样本权衡打开大门。
We consider the problem of performing linear regression over a stream of d-dimensional examples, and show that any algorithm that uses a subquadratic amount of memory exhibits a slower rate of convergence than can be achieved without memory constraints. Specifically, consider a sequence of labeled examples (a1,b1), (a2,b2)…, with ai drawn independently from a d-dimensional isotropic Gaussian, and where bi = ⟨ ai, x⟩ + ηi, for a fixed x ∈ ℝd with ||x||2 = 1 and with independent noise ηi drawn uniformly from the interval [−2−d/5,2−d/5]. We show that any algorithm with at most d2/4 bits of memory requires at least Ω(d loglog1/є) samples to approximate x to ℓ2 error є with probability of success at least 2/3, for є sufficiently small as a function of d. In contrast, for such є, x can be recovered to error є with probability 1−o(1) with memory O(d2 log(1/є)) using d examples. This represents the first nontrivial lower bounds for regression with super-linear memory, and may open the door for strong memory/sample tradeoffs for continuous optimization.