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

스트리밍 데이터를 위한 시간 가변 최적화: 시간 가중치 기반 접근

기본 정보

논문 ID: 2510.13052
제목: Time-Varying Optimization for Streaming Data Via Temporal Weighting
저자: Muhammad Faraz Ul Abrar (애리조나 주립대학교), Nicolò Michelusi (애리조나 주립대학교), Erik G. Larsson (린셰핑 대학교)
분류: 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)의 감소율로 점근적으로 소멸하는 반면, 할인 가중치는 할인 인자 및 각 시간 단계에서 수행되는 경사 업데이트 횟수에 의해 제어되는 0이 아닌 오차 하한을 생성함을 증명한다.

연구 배경 및 동기

문제 정의

본 논문이 해결하고자 하는 핵심 문제는 스트리밍 데이터 환경에서의 시간 가변 최적화 학습 문제이다. 구체적으로:

전통적 최적화의 한계: 고전적 기계학습 최적화는 정적 목적 함수를 가정하며, 정적 데이터 분포를 전제하지만, 현실의 솔루션은 동적으로 진화하는 환경에서 작동한다
스트리밍 데이터의 도전: 데이터가 순차적으로 도착하고, 목적 함수가 시간에 따라 진화하여 비정상 최적화 문제를 야기한다
계산 제약: 실시간 또는 자원 제한 설정에서 각 시간 단계마다 제한된 횟수의 업데이트만 수행할 수 있다

중요성

이 문제는 여러 핵심 응용 분야에서 중요한 의미를 갖는다:

자율주행 차량의 이동 로봇 추적
이동 목표 위치 결정
포트폴리오 최적화
변동성 금융 시장에서의 위험 관리
시간 가변 시스템 동역학의 제어기 적응

기존 방법의 한계

일반적 공식의 느슨한 경계: 대부분의 기존 연구는 일반적 시간 가변 공식(1)에 중점을 두며, 스트리밍 데이터의 내재적 구조를 무시하여 추적 오차의 느슨한 경계를 초래할 수 있다
구조화된 분석의 부재: 기존 방법은 스트리밍 데이터의 가중치 구조를 명시적으로 활용하여 더 타이트한 성능 경계를 얻지 못한다
이론과 실제의 괴리: 지속적 학습 분야의 방법은 대부분 경험적이며, 이론적 기초가 부족하다

핵심 기여

구조화된 가중치 공식 제안: 스트리밍 데이터의 구조를 명시적으로 포착하는 시간 가변 목적 함수를 도입하며, 이는 모든 과거 샘플 손실의 가중 평균으로 정의된다
두 가지 가중치 전략의 이론적 분석:
- 균등 가중치: 추적 오차가 O(1/t) 속도로 점근적으로 소멸함을 증명
- 할인 가중치: 명시적인 0이 아닌 점근 추적 오차 경계 도출
타이트한 경계 도출: 스트리밍 데이터 구조를 활용하여 기존 일반적 시간 가변 분석보다 더 타이트한 TE 경계 획득
이론 및 실험 검증: 수치 시뮬레이션을 통해 이론적 발견의 유효성 검증

방법론 상세 설명

작업 정의

단일 에이전트(예: 엣지 또는 클라우드 서버)가 시간 가변 기계학습 모델 매개변수를 추적하는 학습 설정을 고려한다:

입력: 각 반복 t≥1에서, 에이전트는 새로운 데이터 샘플(xt, yt)을 수신한다
출력: 모델 매개변수 wt는 누적 데이터의 가중 평균 손실을 최소화한다
제약: 각 시간 단계마다 E번의 경사 업데이트만 수행할 수 있다

핵심 수학 공식

시간 가변 목적 함수: $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)$

여기서:

$a_i(t)$ 는 시간 t에서 i번째 샘플의 가중치
$f_i(w)$ 는 i번째 데이터 샘플의 손실 함수
가중치는 다음을 만족: $0 \leq a_i(t) \leq 1$ 및 $\sum_{i=1}^t a_i(t) = 1$

경사 하강법 업데이트: $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})$

추적 오차 정의: $\text{TE}(t) = \|w_t - w_t^*\|$

두 가지 가중치 전략

1. 균등 가중치

모든 $i = 1, \ldots, t$ 에 대해 $a_i(t) = 1/t$ 로 설정하면, 목적 함수는 다음과 같이 변환된다: $F_{t+1}(w) = \frac{t}{t+1}F_t(w) + \frac{1}{t+1}f_{t+1}(w)$

2. 할인 가중치

기하 할인을 사용: $a_i(t) = \frac{1-\gamma}{1-\gamma^t}\gamma^{t-i}$ , 여기서 $0 < \gamma < 1$ 은 할인 인자이다.

기술적 혁신점

구조화된 분석: 일반적 시간 가변 최적화와 달리, 스트리밍 데이터의 가중치 구조를 명시적으로 활용한다
최소화기 표류 분석: $\|w_{i+1}^* - w_i^*\|$ 를 분석하여 목적 함수 변화를 이해한다
재귀적 오차 분석: 오차 진화를 추적하기 위한 재귀 관계를 수립한다

이론적 분석

기본 가정

가정 1 (L-평활성 및 μ-강볼록성): 각 데이터 샘플의 손실 함수는 다음을 만족한다:

$\|\nabla f_t(x) - \nabla f_t(y)\| \leq L\|x-y\|$
$f_t(y) \geq f_t(x) + \nabla f_t(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2$

가정 2 (유계 최소화기): $\|w_t^*\| \leq C$ 를 만족하는 $C > 0$ 이 모든 t에 대해 존재한다.

주요 이론적 결과

균등 가중치의 추적 오차

명제 1: 균등 가중치에 대해, 추적 오차는 다음을 만족한다: $\text{TE}(t) \leq \alpha^t\|w_0 - w_1^*\| + \frac{C'A}{t}$

여기서 $\alpha = (1-\eta\mu)^E < 1$ , $C' = (1+\sqrt{L/\mu})\frac{LC}{\mu}$ 이다.

핵심 결론: TE는 O(1/t) 속도로 감소하며, 점근 추적 오차는 0이다.

할인 가중치의 추적 오차

명제 2: 할인 가중치에 대해, 점근 추적 오차는 다음을 만족한다: $\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}$

핵심 결론: 0이 아닌 오차 하한이 존재하며, 할인 인자 γ 및 경사 업데이트 횟수 E에 의해 제어된다.

실험 설정

데이터 생성

스칼라 이차 손실 함수를 사용: $f_t(w) = \frac{\mu}{2}(w-c_t)^2$

매개변수 설정:

$c_t$ 는 유계 무작위 보행으로 생성: $c_{t+1} = \max(-C_{\max}, \min(c_t + z_{t+1}, C_{\max}))$
$z_t \sim \mathcal{N}(0, \sigma^2)$ , $C_{\max} = 100$ , $\sigma^2 = 100$ , $\mu = 0.1$

평가 지표

제곱 평균 제곱근 추적 오차
최대(최악의 경우) 추적 오차
1000회 독립 실행의 통계 결과

실험 결과

균등 가중치 결과

O(1/t) 감소 검증: 실험은 이론적 예측과 일치하는 단조 감소를 명확히 보여준다
경사 업데이트 횟수의 영향: E를 10에서 20으로 증가시키면, 경험적 TE는 약 0.09의 개선 인자를 보이며, 이는 이론적 예측과 정량적으로 일치한다
장기 행동: 큰 t에 대해, TE는 최소화기 표류의 잔여 오차에 의해 지배된다