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 (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
प्रकाशन समय: 15 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.13052

सारांश

परंपरागत अनुकूलन सिद्धांत निश्चित, समय-अपरिवर्तनीय उद्देश्य कार्यों से संबंधित है। हालांकि, समय-परिवर्तनशील अनुकूलन गतिशील वातावरण में निर्णय लेने के लिए एक महत्वपूर्ण विषय बन गया है। यह पेपर समय-परिवर्तनशील अनुकूलन के दृष्टिकोण से स्ट्रीमिंग डेटा शिक्षण समस्या का अध्ययन करता है। पिछले कार्यों से भिन्न जो सामान्य सूत्रों पर ध्यान केंद्रित करते हैं, हम एक संरचित भार-आधारित सूत्र प्रस्तुत करते हैं जो स्पष्ट रूप से समय-परिवर्तनशील उद्देश्य के स्ट्रीमिंग डेटा स्रोत को कैप्चर करता है, जहां एजेंट प्रत्येक समय चरण पर सभी पिछले डेटा नमूनों के भारित औसत नुकसान को कम करने का लक्ष्य रखता है। हम दो विशिष्ट भारण रणनीतियों पर ध्यान केंद्रित करते हैं: (1) समान भार, सभी नमूनों को समान रूप से मानते हैं; (2) छूट भार, पुराने डेटा के प्रभाव को ज्यामितीय रूप से क्षय करते हैं। दोनों योजनाओं के लिए, हम ग्रेडिएंट डिसेंट (GD) अपडेट के तहत "ट्रैकिंग त्रुटि" (TE) की तंग सीमाएं प्राप्त करते हैं, TE को मॉडल पैरामीटर और दिए गए समय चरण के समय-परिवर्तनशील इष्टतम समाधान के बीच विचलन के रूप में परिभाषित किया जाता है। हम साबित करते हैं कि समान भारण के तहत, TE O(1/t) की क्षय दर पर渐近रूप से गायब हो जाता है, जबकि छूट भारण छूट कारक और प्रत्येक समय चरण पर निष्पादित ग्रेडिएंट अपडेट की संख्या द्वारा नियंत्रित एक गैर-शून्य त्रुटि निचली सीमा उत्पन्न करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

यह पेपर स्ट्रीमिंग डेटा वातावरण में समय-परिवर्तनशील अनुकूलन शिक्षण समस्या को हल करने के लिए है। विशेष रूप से:

परंपरागत अनुकूलन की सीमाएं: शास्त्रीय मशीन लर्निंग अनुकूलन स्थिर उद्देश्य कार्यों को मानता है, स्थिर डेटा वितरण मानता है, लेकिन वास्तविक दुनिया के समाधान गतिशील विकसित वातावरण में काम करते हैं
स्ट्रीमिंग डेटा की चुनौतियां: डेटा क्रमिक रूप से आता है, उद्देश्य कार्य समय के साथ विकसित होता है, जिससे गैर-स्थिर अनुकूलन समस्या होती है
कम्प्यूटेशनल बाधाएं: वास्तविक समय या संसाधन-सीमित सेटिंग में, प्रत्येक समय चरण पर केवल सीमित संख्या में अपडेट निष्पादित किए जा सकते हैं

महत्व

यह समस्या कई महत्वपूर्ण अनुप्रयोग क्षेत्रों में महत्वपूर्ण है:

स्वायत्त वाहनों में मोबाइल रोबोट ट्रैकिंग
गतिशील लक्ष्य स्थानीयकरण
पोर्टफोलियो अनुकूलन
अस्थिर वित्तीय बाजारों में जोखिम प्रबंधन
समय-परिवर्तनशील प्रणाली गतिशीलता का नियंत्रक अनुकूलन

मौजूदा विधियों की सीमाएं

सामान्य सूत्रों की ढीली सीमाएं: अधिकांश मौजूदा कार्य सामान्य समय-परिवर्तनशील सूत्रों पर ध्यान केंद्रित करते हैं, स्ट्रीमिंग डेटा की अंतर्निहित संरचना को नजरअंदाज करते हैं, जिससे ट्रैकिंग त्रुटि की ढीली सीमाएं हो सकती हैं
संरचित विश्लेषण की कमी: मौजूदा विधियां अधिक तंग प्रदर्शन सीमाएं प्राप्त करने के लिए स्ट्रीमिंग डेटा की भार संरचना का स्पष्ट रूप से उपयोग नहीं करती हैं
सिद्धांत और व्यवहार में अंतराल: सतत शिक्षा क्षेत्र की विधियां अधिकतर अनुभवजन्य हैं, सैद्धांतिक आधार की कमी है

मूल योगदान

संरचित भार सूत्र प्रस्तुत करना: स्ट्रीमिंग डेटा की संरचना को स्पष्ट रूप से कैप्चर करने वाले समय-परिवर्तनशील उद्देश्य कार्य को पेश करना, सभी पिछले नमूनों के नुकसान के भारित औसत के रूप में परिभाषित
दो भारण रणनीतियों का सैद्धांतिक विश्लेषण:
- समान भार: साबित करता है कि ट्रैकिंग त्रुटि O(1/t) दर पर渐近रूप से गायब हो जाती है
- छूट भार: स्पष्ट गैर-शून्य渐近ट्रैकिंग त्रुटि सीमाएं प्राप्त करता है
तंग सीमाएं प्राप्त करना: स्ट्रीमिंग डेटा संरचना का उपयोग करके मौजूदा सामान्य समय-परिवर्तनशील विश्लेषण की तुलना में अधिक तंग 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 (परिबद्ध न्यूनतमकर्ता): $C > 0$ मौजूद है जैसे कि $\|w_t^*\| \leq C$ सभी 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) दर पर क्षय करती है,渐近ट्रैकिंग त्रुटि शून्य है।

छूट भार के लिए ट्रैकिंग त्रुटि

प्रस्ताव 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}$

मुख्य निष्कर्ष: एक गैर-शून्य त्रुटि निचली सीमा मौजूद है, जो छूट कारक γ और ग्रेडिएंट अपडेट की संख्या 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 न्यूनतमकर्ता बहाव की अवशिष्ट त्रुटि द्वारा प्रभुत्व है

छूट भार परिणाम

गैर-शून्य त्रुटि निचली सीमा: सभी त्रुटि मेट्रिक्स गैर-लुप्त渐近त्रुटि सीमा में परिवर्तित होते हैं
छूट कारक प्रभाव: बड़े γ कम渐近ट्रैकिंग त्रुटि उत्पन्न करते हैं
सैद्धांतिक सत्यापन: जब γ=0.99 हो, TE समान भार स्थिति के करीब है, सैद्धांतिक विश्लेषण को सत्यापित करता है

ग्रेडिएंट जटिलता

प्रस्ताव 3: $\text{ATE}_\gamma \leq \epsilon$ सुनिश्चित करने के लिए, निष्पादित करने की आवश्यकता है: $E \geq \frac{\ln\left(\frac{\epsilon}{C'(1-\gamma)+\epsilon}\right)}{\ln(1-\eta\mu)}$ ग्रेडिएंट अपडेट, जिससे O(ln(1/ε)) की ग्रेडिएंट पुनरावृत्ति जटिलता होती है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

समान भार: O(1/t) क्षय ट्रैकिंग त्रुटि प्राप्त करता है,渐近पूर्ण ट्रैकिंग
छूट भार: स्पष्ट रूप से मात्रात्मक गैर-शून्य渐近त्रुटि उत्पन्न करता है, पुराने डेटा की विस्मृति को प्रतिबिंबित करता है
संरचित विश्लेषण: स्ट्रीमिंग डेटा संरचना का उपयोग करके सामान्य विधियों की तुलना में अधिक तंग सीमाएं प्राप्त करता है

सैद्धांतिक अंतर्दृष्टि

समान बनाम छूट: समान भार प्रत्येक नए नमूने के प्रभाव को O(1/t) में पतला करता है, जबकि छूट भार O(1) बहाव बनाए रखता है
भार अभिसरण: जब γ→1, छूट भार समान भार में परिवर्तित होता है, संबंधित रूप से ATE_γ→0
कम्प्यूटेशनल बजट व्यापार: अधिक ग्रेडिएंट अपडेट E ट्रैकिंग त्रुटि को कम कर सकते हैं, लेकिन कम्प्यूटेशनल लागत बढ़ाते हैं

सीमाएं

मेमोरी मान्यता: सभी ऐतिहासिक नमूने ग्रेडिएंट तक पहुंच मानता है, मेमोरी बाधाओं पर विचार नहीं करता है
विशिष्ट नुकसान कार्य: सैद्धांतिक विश्लेषण L-स्मूथ और μ-दृढ़ उत्तलता मान्यताओं पर आधारित है
परिबद्ध न्यूनतमकर्ता: न्यूनतमकर्ता को समान रूप से परिबद्ध मानने की आवश्यकता है

भविष्य की दिशाएं

मेमोरी-सीमित विश्लेषण: मेमोरी बाधाओं के तहत समय-परिवर्तनशील शिक्षा का अध्ययन करना
अधिक सामान्य नुकसान कार्य: गैर-उत्तल या अन्य प्रकार के नुकसान तक विस्तार करना
वितरित सेटिंग: संघीय शिक्षा जैसे वितरित वातावरण में अनुप्रयोग
स्वचालित भार: डेटा-संचालित गतिशील भार रणनीतियों का अध्ययन करना

गहन मूल्यांकन

शक्तियां

सैद्धांतिक कठोरता: पूर्ण गणितीय विश्लेषण और तंग सीमा व्युत्पत्ति प्रदान करता है
संरचित दृष्टिकोण: स्ट्रीमिंग डेटा संरचना का स्पष्ट रूप से उपयोग करता है, सामान्य विधियों की तुलना में अधिक सटीक परिणाम प्राप्त करता है
व्यावहारिक मूल्य: दो भारण रणनीतियां विभिन्न वास्तविक अनुप्रयोग परिदृश्यों के अनुरूप हैं
प्रायोगिक सत्यापन: संख्यात्मक परिणाम सैद्धांतिक भविष्यवाणियों के साथ अत्यधिक सुसंगत हैं
स्पष्ट अभिव्यक्ति: पेपर अच्छी तरह से संगठित है, गणितीय व्युत्पत्ति स्पष्ट है

कमियां

मान्यता सीमाएं: L-स्मूथ और μ-दृढ़ उत्तलता मान्यताएं व्यावहारिक अनुप्रयोगों में अत्यधिक कठोर हो सकती हैं
मेमोरी आवश्यकताएं: सभी ऐतिहासिक ग्रेडिएंट को संग्रहीत करने की आवश्यकता है, बड़े पैमाने के अनुप्रयोगों में अव्यावहारिक है
एकल एजेंट: केवल एकल-एजेंट सेटिंग पर विचार करता है, बहु-एजेंट या वितरित परिदृश्य शामिल नहीं है
सरल प्रयोग: प्रयोग सरल द्विघात नुकसान कार्य का उपयोग करते हैं, जटिल परिदृश्य सत्यापन की कमी है

प्रभाव

सैद्धांतिक योगदान: समय-परिवर्तनशील अनुकूलन और सतत शिक्षा के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान करता है
पद्धति मूल्य: संरचित विश्लेषण विधि अन्य समय-परिवर्तनशील शिक्षण समस्याओं तक सामान्यीकृत की जा सकती है
व्यावहारिक अनुप्रयोग: ऑनलाइन शिक्षा और स्वचालित प्रणाली डिजाइन के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है
पुनरुत्पादनीयता: सैद्धांतिक परिणाम और प्रायोगिक सेटअप विस्तार से वर्णित हैं, पुनरुत्पादन को सुविधाजनक बनाता है

लागू परिदृश्य

ऑनलाइन शिक्षण प्रणाली: नए डेटा के अनुकूल होने की आवश्यकता वाली मशीन लर्निंग प्रणाली
स्वचालित नियंत्रण: समय-परिवर्तनशील प्रणाली नियंत्रक डिजाइन
वित्तीय मॉडलिंग: बाजार परिवर्तनों के अनुकूल होने की आवश्यकता वाली निवेश रणनीतियां
IoT अनुप्रयोग: सेंसर नेटवर्क में वास्तविक समय डेटा प्रसंस्करण
सिफारिश प्रणाली: उपयोगकर्ता वरीयता परिवर्तनों के अनुकूल होने की आवश्यकता वाली सिफारिश एल्गोरिदम

संदर्भ

पेपर 40 संबंधित संदर्भों का हवाला देता है, जो समय-परिवर्तनशील अनुकूलन, सतत शिक्षा, उत्तल अनुकूलन आदि महत्वपूर्ण क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करता है, अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करता है।