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

تحسين متغير مع الزمن لبيانات البث عبر الترجيح الزمني

المعلومات الأساسية

  • معرّف الورقة: 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
  • تاريخ النشر: 15 أكتوبر 2025 (نسخة arXiv التمهيدية)
  • رابط الورقة: https://arxiv.org/abs/2510.13052

الملخص

تتعامل نظرية التحسين التقليدية مع دوال هدف ثابتة وغير متغيرة مع الزمن. ومع ذلك، أصبح التحسين المتغير مع الزمن موضوعاً مهماً لاتخاذ القرارات في البيئات الديناميكية. تدرس هذه الورقة مشكلة التعلم من بيانات البث من منظور التحسين المتغير مع الزمن. بخلاف الأعمال السابقة التي تركز على صيغ عامة، نقدم صيغة منظمة قائمة على الترجيح تلتقط بشكل صريح مصادر البيانات المتدفقة للأهداف المتغيرة مع الزمن، حيث يهدف الوكيل في كل خطوة زمنية إلى تقليل متوسط الخسارة المرجح لجميع عينات البيانات السابقة. نركز على استراتيجيتي ترجيح محددتين: (1) الترجيح المنتظم، الذي يعامل جميع العينات بالتساوي؛ (2) الترجيح المخصوم، الذي يتسبب في تناقص هندسي لتأثير البيانات القديمة. بالنسبة لكلا المخطط، نشتق حدوداً ضيقة لـ "خطأ التتبع" (TE) تحت تحديثات الانحدار التدريجي (GD)، حيث يُعرّف TE بأنه الانحراف بين معاملات النموذج والحل الأمثل المتغير مع الزمن في خطوة زمنية معينة. نثبت أنه تحت الترجيح المنتظم، يختفي TE بشكل مقارب بمعدل تناقص O(1/t)، بينما ينتج الترجيح المخصوم حداً أدنى لخطأ غير صفري يتحكم فيه عامل الخصم وعدد تحديثات الانحدار التدريجي المنفذة في كل خطوة زمنية.

الخلفية البحثية والدافع

تعريف المشكلة

المشكلة الأساسية التي تعالجها هذه الورقة هي مشكلة التعلم بالتحسين المتغير مع الزمن في بيئة البيانات المتدفقة. بشكل محدد:

  1. قيود التحسين التقليدي: يقوم التحسين الكلاسيكي في التعلم الآلي بتحسين دوال هدف ثابتة، مع افتراض توزيع بيانات ثابت، لكن الحلول الواقعية تعمل في بيئات تتطور ديناميكياً
  2. تحديات البيانات المتدفقة: تصل البيانات بشكل متسلسل، وتتطور دالة الهدف مع الزمن، مما يؤدي إلى مشاكل تحسين غير ثابتة
  3. القيود الحسابية: في الإعدادات الفورية أو المحدودة الموارد، يمكن تنفيذ عدد محدود فقط من التحديثات في كل خطوة زمنية

الأهمية

تتمتع هذه المشكلة بأهمية كبيرة في عدة مجالات تطبيقية حاسمة:

  • تتبع الروبوتات المتحركة في المركبات ذاتية القيادة
  • تحديد موقع الأهداف المتحركة
  • تحسين المحفظة الاستثمارية
  • إدارة المخاطر في الأسواق المالية المتقلبة
  • التكيف الديناميكي للمتحكمات في الأنظمة المتغيرة مع الزمن

قيود الطرق الموجودة

  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/ε)).

الأعمال ذات الصلة

التحسين المتغير مع الزمن

  • الأعمال المبكرة: خوارزميات من نوع نيوتن تستفيد من المعلومات من الدرجة الثانية لتحقيق تقارب أسي
  • شروط الانجراف المحدود: طرق تفترض ∥wt+1∗−wt∗∥≤C\|w_{t+1}^* - w_t^*\| \leq C
  • مخططات التنبؤ والتصحيح: طرق تجمع بين التنبؤ والتصحيح الانحدار التدريجي

التعلم المستمر

  • التعلم على تسلسل المهام: التعلم من نماذج التعلم الآلي على تسلسل المهام
  • النسيان الكارثي: تحدي تدهور أداء المهام القديمة عند تعلم مهام جديدة
  • الطرق التجريبية: الطرق الموجودة هي في الغالب تجريبية، وتفتقر إلى الأساس النظري

تفرد مساهمة هذه الورقة

تربط هذه الورقة للمرة الأولى التحسين المتغير مع الزمن والتعلم المستمر من منظور نظري، مع توفير تحليل صريح لبنية البيانات المتدفقة.

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. الترجيح المنتظم: يحقق خطأ تتبع بتناقص O(1/t)، مع تتبع مقارب مثالي
  2. الترجيح المخصوم: ينتج خطأ مقارب غير صفري قابل للقياس الكمي، مما يعكس النسيان للبيانات القديمة
  3. التحليل المنظم: الاستفادة من بنية البيانات المتدفقة للحصول على حدود أضيق من الطرق العامة

الرؤى النظرية

  • المنتظم مقابل المخصوم: يخفف الترجيح المنتظم تأثير كل عينة جديدة إلى 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 مرجعاً ذا صلة، تغطي الأعمال المهمة في مجالات التحسين المتغير مع الزمن والتعلم المستمر والتحسين المحدب، مما يوفر أساساً نظرياً متيناً للبحث.