提出SILAGE算法,在低内存下实现无全梯度刷新的非凸优化。
SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums
- 利用双层数据结构,每轮仅计算一个子组梯度
- 内存仅需O(n),比现有方法减少约90%以上
- 适合大规模分布式学习场景,如数据分片或外存训练
在海量数据上进行经验风险最小化时,自然形成嵌套双有限求和结构,其中总样本数N=nm被逻辑或物理划分为n个大小为m的块(如合并数据池、外存学习或人为分层)。尽管方差缩减方法在非凸目标下达到最优查询复杂度,但在集中式场景中面临严重扩展瓶颈。递归估计器如PAGE需定期对所有nm样本进行全局全梯度刷新,计算开销大;而单循环方法如SILVER虽避免刷新,但需存储每个样本的控制变量,内存达O(nm),不切实际。本文提出SILAGE,一种方差缩减算法,通过主动利用双求和结构,消除对所有nm成分的周期性全局全梯度刷新(每轮最多评估一个局部组梯度),同时仅需O(n)内存。此外,我们提供紧致收敛分析,避免使用悲观最坏情况下的Lipschitz常数。SILAGE的复杂度天然适应数据几何结构:组间异质性(δ₁)与组内异质性(δ₂)。结果在多个实际相关场景中优于现有最先进界。
原文摘要 · Abstract (English)
Empirical risk minimization on massive datasets naturally exhibits a nested double finite-sum structure, where $N=nm$ total samples are logically or physically partitioned into $n$ blocks of size $m$ (e.g., in pooled data silos, out-of-core learning, or deliberate stratification). While variance-reduced methods achieve optimal oracle complexities for nonconvex objectives, they suffer from severe scaling bottlenecks in this centralized regime. Recursive estimators, such as PAGE, require periodic global full-gradient refreshes over all $nm$ samples, which are computationally expensive. Conversely, single-loop methods, such as SILVER, avoid such refreshes but require an impractical $\mathcal{O}(nm)$ memory footprint to store a control variate for every sample. In this paper, we propose SILAGE, a variance-reduced algorithm that addresses this trade-off. By actively exploiting the double-sum structure, SILAGE eliminates periodic global full-gradient refreshes over all $nm$ components (evaluating at most one local group gradient per iteration) while requiring only $\mathcal{O}(n)$ memory. Furthermore, we provide a tight convergence analysis that avoids pessimistic worst-case Lipschitz constants. Instead, SILAGE's complexity natively adapts to the underlying data geometry via nested functional similarities: across-group ($δ_1$) and within-group ($δ_2$) heterogeneity. Our results improve existing state-of-the-art bounds in several practically relevant regimes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。