在线学习是一个计算高效且具备理论保障的通用学习框架,能够利用实时收集的数据快速地进行参数更新。随着大数据时代的来临,为了处理规模大、增长快的数据,在线学习受到越来越多的关注。自适应次梯度方法由于可以动态地利用已观测数据的几何结构去指导参数更新而成为常用的在线学习方法。根据使用的信息量大小,自适应次梯度方法可以被划分为对角矩阵版本和全矩阵版本。由于全矩阵版本处理高维数据时需要难以接受的开销,对角矩阵版本在实践中被广泛应用。然而,对角矩阵版本仅仅维护了梯度外积矩阵的对角线元素,无法捕捉梯度之间的相关性。当高维数据是稠密且具备低秩或近似低秩特性时,它的效果会比全矩阵版本差。本文主要研究如何在不影响性能的前提下降低自适应次梯度方法的复杂度,取得了以下进展:第一,针对全矩阵版本自适应次梯度方法复杂度过高的问题,提出基于梯度投影的高效自适应次梯度方法。该方法的核心思想是利用随机投影方法去生成一个可以近似梯度外积矩阵的低秩矩阵。在后续的计算过程中,我们通过维护和操作这个低秩矩阵去加速梯度外积矩阵的开方和求逆运算,从而得到一种更加高效的自适应次梯度方法。实验结果表明,该方法取得了与全矩阵版本自适应梯度方法相接近的效果,并显著地降低了运行时间。然而,该方法在参数更新过程中存在依赖性问题,我们难以利用现有的数学工具从理论上分析其遗憾上界。第二,针对基于梯度投影的高效自适应梯度方法不具备遗憾上界的问题,进一步提出基于数据投影的高效自适应次梯度方法。具体而言,对于机器学习领域常见的广义线性模型,我们首先提出将全矩阵版本自适应次梯度方法中的梯度外积矩阵替换为数据外积矩阵,这一简单的变化直接避免了基于梯度投影的方法中存在的依赖性问题。然后再利用随机投影方法去生成一个可以近似数据外积矩阵的低秩矩阵,并利用该低秩矩阵加速参数更新,得到与基于梯度投影的方法相同的存储和计算复杂度。更重要的是,我们通过理论分析建立了该方法的遗憾上界。理论结果表明,针对广义线性模型,当数据具备低秩或近似低秩特性时,该方法的性能与全矩阵版本的性能相接近。实验结果表明,该方法取得了与基于梯度投影的方法相似的效果,成功降低了全矩阵版本的复杂度。