用少量固定变换实现高效优化,保证收敛性。
Sparse Data Augmentation for Optimization with Provable Guarantees
- 预先采样少量变换,重复使用以替代全量数据增强。
- 迭代次数仅需 $\mathcal{O}((\log |G|+\log(1/\delta))/\varepsilon^2)$ 次查询。
- 适用于大规模对称变换场景,如几何机器学习中的数据增强。
在几何机器学习的非凸优化问题中,数据增强常通过平均数据变换下的经验损失来促进不变性。然而,计算完全增强目标需要访问变换群 $G$ 的所有元素,当 $G$ 很大或仅可通过采样获取时,代价极高。本文研究是否可用预先获取的少量固定变换样本近似全量增强。在合适正则性条件下,我们证明:以至少 $1-\delta$ 的概率,梯度下降(GD)在稀疏增强目标上运行,只需 $\mathcal{O}\bigl((\log |G|+\log(1/\delta))/\varepsilon^2\bigr)$ 次群变换查询即可达到全增强目标的 $\varepsilon$-驻点。相比之下,标准群随机梯度下降(group-SGD)每轮采样新变换,需 $\mathcal{O}(1/\varepsilon^4)$ 次查询。因此,固定稀疏增强的梯度下降在变换查询次数上优于全增强的梯度下降和 group-SGD。证明方法基于群诱导算子的谱性质与表示论工具,建立了全群平均梯度场的统一近似。
原文摘要 · Abstract (English)
In nonconvex optimization problems arising in geometric machine learning, data augmentation is commonly used to promote invariance by averaging empirical losses over transformations of the data. Computing the fully augmented objective, however, requires access to every element of the transformation group $G$, which may be prohibitively expensive when $G$ is large or accessible only through sampling. We study whether full augmentation can instead be approximated using a small, fixed sample of transformations acquired before optimization and reused thereafter. Under suitable regularity conditions, we show that, with probability at least $1-\delta$, gradient descent (GD) on the resulting sparsely augmented objective returns an $\varepsilon$-stationary point of the fully augmented objective using $\mathcal{O}\bigl((\log |G|+\log(1/\delta))/\varepsilon^2\bigr)$ group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses $\mathcal{O}(1/\varepsilon^4)$ transformation queries. Therefore, gradient descent with fixed sparse augmentation requires fewer transformation queries than both GD applied to the fully augmented objective and group-SGD. Our proof techniques, which may be of independent interest, establish a uniform approximation of the full group-averaged gradient field by a random group average using spectral properties of group-induced operators and tools from representation theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。