High order momentum-based parameter update algorithms have seen widespread applications in training machine learning models. Recently, connections with variational approaches have led to the derivation of new learning algorithms with accelerated learning guarantees. Such methods however, have only considered the case of static regressors. There is a significant need for parameter update algorithms which can be proven stable in the presence of adversarial time-varying regressors, as is commonplace in control theory. In this paper, we propose a new discrete time algorithm which 1) provides stability and asymptotic convergence guarantees in the presence of adversarial regressors by leveraging insights from adaptive control theory and 2) provides non-asymptotic accelerated learning guarantees leveraging insights from convex optimization. In particular, our algorithm reaches an $\epsilon$ sub-optimal point in at most $\tilde{\mathcal{O}}(1/\sqrt{\epsilon})$ iterations when regressors are constant - matching lower bounds due to Nesterov of $\Omega(1/\sqrt{\epsilon})$, up to a $\log(1/\epsilon)$ factor and provides guaranteed bounds for stability when regressors are time-varying. We provide numerical experiments for a variant of Nesterov's provably hard convex optimization problem with time-varying regressors, as well as the problem of recovering an image with a time-varying blur and noise using streaming data.
翻译:以动力为基础的高顺序参数更新算法在培训机器学习模型中广泛应用。 最近, 与变异方法的连接导致新学习算法的衍生, 并加速学习保证。 然而, 这种方法只考虑了静态回归者的情况。 极有必要使用参数更新算法, 这一点在对抗性时间变化递减者的存在中可以证明是稳定的, 控制理论中很常见。 在本文中, 我们提议一种新的离散时间算法, 它将1 提供稳定性和无症状融合保证, 在对抗性递增者出现时, 利用适应性控制理论和2 的洞察力, 提供非痛苦加速学习保证, 利用 convex 优化的洞察力。 特别是, 我们的算法在最大程度上 $\ tilde_ {O\\ (1/\\ qrt lipislonlon) 存在时, 可以证明参数更新值。 当递增的递增时, 我们的递增性时间- 和递增性变压的变压性 提供了一个稳定性 数据, 当我们 的变压的变压性 时, 当我们的变压的变压的变压性 时, 的变压的变压的变压的变压的变压性的变压的变压的变压的变压的变压的变压的变压的变压的变压的变压的变压的 。