Abstract
Classical optimization theory deals with fixed, time-invariant objective functions. However, time-varying optimization has emerged as an important subject for decision-making in dynamic environments. In this work, we study the problem of learning from streaming data through a time-varying optimization lens. Unlike prior works that focus on generic formulations, we introduce a structured, \emph{weight-based} formulation that explicitly captures the streaming-data origin of the time-varying objective, where at each time step, an agent aims to minimize a weighted average loss over all the past data samples. We focus on two specific weighting strategies: (1) uniform weights, which treat all samples equally, and (2) discounted weights, which geometrically decay the influence of older data. For both schemes, we derive tight bounds on the ``tracking error'' (TE), defined as the deviation between the model parameter and the time-varying optimum at a given time step, under gradient descent (GD) updates. We show that under uniform weighting, the TE vanishes asymptotically with a $\mathcal{O}(1/t)$ decay rate, whereas discounted weighting incurs a nonzero error floor controlled by the discount factor and the number of gradient updates performed at each time step. Our theoretical findings are validated through numerical simulations.
Abstract (translated)
经典优化理论主要处理固定且不随时间变化的目标函数。然而，在动态环境中，时变优化已经成为决策的重要课题。在本工作中，我们通过时变优化的视角研究从流数据中学习的问题。与之前侧重于通用公式化的工作不同，我们引入了一种结构化的、基于权重（weight-based）的方法，这种方法明确地捕捉到时间变化的目标函数源自流数据的本质，在每一时刻，一个代理试图最小化过去所有数据样本的加权平均损失。 本文重点关注两种特定的加权策略：(1) 均匀权重，即平等对待所有的样本；(2) 折扣权重，它使较旧数据的影响几何级数地衰减。对于这两种方案，在使用梯度下降（GD）更新时，我们推导出了“跟踪误差”（TE）的紧致界。“跟踪误差”定义为某一时刻模型参数与时间变化最优解之间的偏差。 我们的理论研究表明，在均匀加权的情况下，随着迭代次数增加，“跟踪误差”以$\mathcal{O}(1/t)$的速度渐近消失。而在使用折扣权重时，由于折扣因子和每个时间步执行的梯度更新数量的影响，会产生一个非零的误差下限。 这些理论结果通过数值模拟得到了验证。
URL
https://arxiv.org/abs/2510.13052
