2025-11-18T22:10:13.514792

Time-Varying Optimization for Streaming Data Via Temporal Weighting

Abrar, Michelusi, Larsson
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.
academic

Time-Varying Optimization for Streaming Data Via Temporal Weighting

基本信息

  • 论文ID: 2510.13052
  • 标题: Time-Varying Optimization for Streaming Data Via Temporal Weighting
  • 作者: Muhammad Faraz Ul Abrar (Arizona State University), Nicolò Michelusi (Arizona State University), Erik G. Larsson (Linköping University)
  • 分类: cs.LG cs.AI cs.SY eess.SP eess.SY math.OC
  • 发表时间: 2025年10月15日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.13052

摘要

传统优化理论处理的是固定、时不变的目标函数。然而，时变优化已成为动态环境中决策制定的重要主题。本文通过时变优化的视角研究流数据学习问题。与专注于通用公式的先前工作不同，我们引入了一种结构化的基于权重的公式，明确捕获时变目标的流数据来源，其中智能体在每个时间步旨在最小化所有过去数据样本的加权平均损失。我们专注于两种特定的加权策略：(1) 均匀权重，平等对待所有样本；(2) 折扣权重，几何衰减旧数据的影响。对于两种方案，我们在梯度下降(GD)更新下推导了"跟踪误差"(TE)的紧界，TE定义为模型参数与给定时间步的时变最优解之间的偏差。我们证明在均匀加权下，TE以O(1/t)的衰减率渐近消失，而折扣加权产生由折扣因子和每个时间步执行的梯度更新次数控制的非零误差下界。

研究背景与动机

问题定义

本文要解决的核心问题是在流数据环境中的时变优化学习问题。具体来说：

  1. 传统优化的局限性：经典机器学习优化静态目标函数，假设静态数据分布，但现实世界的解决方案在动态演化环境中运行
  2. 流数据的挑战：数据顺序到达，目标函数随时间演化，导致非平稳优化问题
  3. 计算约束：在实时或资源受限设置中，每个时间步只能执行有限次数的更新

重要性

该问题在多个关键应用领域具有重要意义：

  • 自动驾驶车辆中的移动机器人跟踪
  • 移动目标定位
  • 投资组合优化
  • 波动金融市场中的风险管理
  • 时变系统动态的控制器适应

现有方法的局限性

  1. 通用公式的松散界限：大多数现有工作专注于通用时变公式(1)，忽略了流数据的固有结构，可能导致跟踪误差的松散界限
  2. 缺乏结构化分析：现有方法没有明确利用流数据的权重结构来获得更紧的性能界限
  3. 理论与实践脱节：持续学习领域的方法大多是经验性的，缺乏理论基础

核心贡献

  1. 提出结构化权重公式：引入明确捕获流数据结构的时变目标函数，定义为所有过去样本损失的加权平均
  2. 两种加权策略的理论分析：
    • 均匀权重：证明跟踪误差以O(1/t)速率渐近消失
    • 折扣权重：推导出明确的非零渐近跟踪误差界限
  3. 紧致界限推导：利用流数据结构获得比现有通用时变分析更紧的TE界限
  4. 理论与实验验证：通过数值仿真验证理论发现的有效性

方法详解

任务定义

考虑单个智能体(如边缘或云服务器)旨在跟踪时变机器学习模型参数的学习设置：

  • 输入：在每次迭代t≥1，智能体接收新数据样本(xt, yt)
  • 输出：模型参数wt，最小化累积数据的加权平均损失
  • 约束：每个时间步只能执行E次梯度更新

核心数学公式

时变目标函数： wt∗=arg⁡min⁡w∈RdFt(w),其中Ft(w)=∑i=1tai(t)fi(w)w_t^* = \arg\min_{w \in \mathbb{R}^d} F_t(w), \quad \text{其中} \quad F_t(w) = \sum_{i=1}^t a_i(t)f_i(w)

其中：

  • ai(t)a_i(t)是第i个样本在时间t的权重
  • fi(w)f_i(w)是第i个数据样本的损失函数
  • 权重满足：0≤ai(t)≤10 \leq a_i(t) \leq 1且∑i=1tai(t)=1\sum_{i=1}^t a_i(t) = 1

梯度下降更新： wt,k+1=wt,k−η∇Ft+1(wt,k)=wt,k−η∑i=1t+1ai(t+1)∇fi(wt,k)w_{t,k+1} = w_{t,k} - \eta\nabla F_{t+1}(w_{t,k}) = w_{t,k} - \eta\sum_{i=1}^{t+1} a_i(t+1)\nabla f_i(w_{t,k})

跟踪误差定义： TE(t)=∥wt−wt∗∥\text{TE}(t) = \|w_t - w_t^*\|

两种加权策略

1. 均匀权重

设置ai(t)=1/ta_i(t) = 1/t对所有i=1,…,ti = 1, \ldots, t，目标函数变为： Ft+1(w)=tt+1Ft(w)+1t+1ft+1(w)F_{t+1}(w) = \frac{t}{t+1}F_t(w) + \frac{1}{t+1}f_{t+1}(w)

2. 折扣权重

使用几何折扣：ai(t)=1−γ1−γtγt−ia_i(t) = \frac{1-\gamma}{1-\gamma^t}\gamma^{t-i}，其中0<γ<10 < \gamma < 1是折扣因子。

技术创新点

  1. 结构化分析：与通用时变优化不同，明确利用流数据的权重结构
  2. 最小化器漂移分析：通过分析∥wi+1∗−wi∗∥\|w_{i+1}^* - w_i^*\|来理解目标函数变化
  3. 递归误差分析：建立递归关系来跟踪误差演化

理论分析

基础假设

假设1（L-光滑和μ-强凸）：每个数据样本的损失函数满足：

  • ∥∇ft(x)−∇ft(y)∥≤L∥x−y∥\|\nabla f_t(x) - \nabla f_t(y)\| \leq L\|x-y\|
  • ft(y)≥ft(x)+∇ft(x)T(y−x)+μ2∥y−x∥2f_t(y) \geq f_t(x) + \nabla f_t(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2

假设2（有界最小化器）：存在C>0C > 0使得∥wt∗∥≤C\|w_t^*\| \leq C对所有t成立。

主要理论结果

均匀权重的跟踪误差

命题1：对于均匀权重，跟踪误差满足： TE(t)≤αt∥w0−w1∗∥+C′At\text{TE}(t) \leq \alpha^t\|w_0 - w_1^*\| + \frac{C'A}{t}

其中α=(1−ημ)E<1\alpha = (1-\eta\mu)^E < 1，C′=(1+L/μ)LCμC' = (1+\sqrt{L/\mu})\frac{LC}{\mu}。

关键结论：TE以O(1/t)速率衰减，渐近跟踪误差为零。

折扣权重的跟踪误差

命题2：对于折扣权重，渐近跟踪误差为： ATEγ=lim sup⁡t→∞∥wt−wt∗∥≤(1+Lμ)LCμ⋅(1−γ)α1−α\text{ATE}_\gamma = \limsup_{t\to\infty} \|w_t - w_t^*\| \leq \left(1+\sqrt{\frac{L}{\mu}}\right)\frac{LC}{\mu} \cdot \frac{(1-\gamma)\alpha}{1-\alpha}

关键结论：存在非零误差下界，由折扣因子γ和梯度更新次数E控制。

实验设置

数据生成

使用标量二次损失函数：ft(w)=μ2(w−ct)2f_t(w) = \frac{\mu}{2}(w-c_t)^2

参数设置：

  • ctc_t按有界随机游走生成：ct+1=max⁡(−Cmax⁡,min⁡(ct+zt+1,Cmax⁡))c_{t+1} = \max(-C_{\max}, \min(c_t + z_{t+1}, C_{\max}))
  • zt∼N(0,σ2)z_t \sim \mathcal{N}(0, \sigma^2)，Cmax⁡=100C_{\max} = 100，σ2=100\sigma^2 = 100，μ=0.1\mu = 0.1

评价指标

  • 均方根跟踪误差
  • 最大（最坏情况）跟踪误差
  • 1000次独立运行的统计结果

实验结果

均匀权重结果

  • O(1/t)衰减验证：实验清晰展示了与理论预测一致的单调衰减
  • 梯度更新次数影响：增加E从10到20，经验TE改善因子约为0.09，与理论预测定量匹配
  • 长期行为：对于大t，TE由最小化器漂移的残余误差主导

折扣权重结果

  • 非零误差下界：所有误差指标收敛到非消失的渐近误差下界
  • 折扣因子影响：较大的γ产生较低的渐近跟踪误差
  • 理论验证：当γ=0.99时，TE接近均匀权重情况，验证了理论分析

梯度复杂度

命题3：为确保ATEγ≤ϵ\text{ATE}_\gamma \leq \epsilon，需要执行： E≥ln⁡(ϵC′(1−γ)+ϵ)ln⁡(1−ημ)E \geq \frac{\ln\left(\frac{\epsilon}{C'(1-\gamma)+\epsilon}\right)}{\ln(1-\eta\mu)} 次梯度更新，导致O(ln(1/ε))的梯度迭代复杂度。

相关工作

时变优化

  • 早期工作：Newton型算法利用二阶信息实现指数收敛
  • 有界漂移条件：假设∥wt+1∗−wt∗∥≤C\|w_{t+1}^* - w_t^*\| \leq C的方法
  • 预测-校正方案：结合预测和梯度校正的方法

持续学习

  • 任务序列学习：在任务序列上学习ML模型
  • 灾难性遗忘：学习新任务时旧任务性能退化的挑战
  • 经验性方法：现有方法主要是经验性的，缺乏理论基础

本文贡献的独特性

本文首次将时变优化和持续学习从理论角度桥接，提供了明确的流数据结构分析。

结论与讨论

主要结论

  1. 均匀权重：实现O(1/t)衰减的跟踪误差，渐近完美跟踪
  2. 折扣权重：产生可明确量化的非零渐近误差，反映了对旧数据的遗忘
  3. 结构化分析：利用流数据结构获得比通用方法更紧的界限

理论洞察

  • 均匀 vs 折扣：均匀权重将每个新样本的影响稀释为O(1/t)，而折扣权重保持O(1)的漂移
  • 权重收敛性：当γ→1时，折扣权重收敛到均匀权重，相应地ATE_γ→0
  • 计算预算权衡：更多梯度更新E可以减少跟踪误差，但增加计算成本

局限性

  1. 内存假设：假设可以访问所有历史样本梯度，未考虑内存约束
  2. 特定损失函数：理论分析基于L-光滑和μ-强凸假设
  3. 有界最小化器：需要假设最小化器均匀有界

未来方向

  1. 内存受限分析：研究内存约束下的时变学习
  2. 更一般的损失函数：扩展到非凸或其他类型的损失
  3. 分布式设置：在联邦学习等分布式环境中的应用
  4. 自适应权重：研究数据驱动的动态权重策略

深度评价

优点

  1. 理论严谨性：提供了完整的数学分析和紧致界限推导
  2. 结构化方法：明确利用流数据结构，获得比通用方法更精确的结果
  3. 实用价值：两种权重策略对应不同的实际应用场景
  4. 实验验证：数值结果与理论预测高度一致
  5. 清晰表述：论文组织良好，数学推导清晰

不足

  1. 假设限制：L-光滑和μ-强凸假设在实际应用中可能过于严格
  2. 内存要求：需要存储所有历史梯度，在大规模应用中不现实
  3. 单一智能体：只考虑单智能体设置，未涉及多智能体或分布式场景
  4. 简单实验：实验使用的是简单的二次损失函数，缺乏复杂场景验证

影响力

  1. 理论贡献：为时变优化和持续学习提供了重要的理论基础
  2. 方法论价值：结构化分析方法可以推广到其他时变学习问题
  3. 实际应用：为在线学习和自适应系统设计提供了理论指导
  4. 可复现性：理论结果和实验设置描述详细，便于复现

适用场景

  1. 在线学习系统：需要持续适应新数据的机器学习系统
  2. 自适应控制：时变系统的控制器设计
  3. 金融建模：需要适应市场变化的投资策略
  4. 物联网应用：传感器网络中的实时数据处理
  5. 推荐系统：需要适应用户偏好变化的推荐算法

参考文献

论文引用了40篇相关文献，涵盖了时变优化、持续学习、凸优化等关键领域的重要工作，为研究提供了坚实的理论基础。