🤖 machine learning

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

यह शोध पत्र \textsc{Lexi-LowGLM} को प्रस्तुत करता है, जो कई प्राथमिकता वाले उद्देश्यों वाले सामान्यीकृत लो-रैंक मैट्रिक्स बैंडिट्स के लिए एक कुशल ऑनलाइन एल्गोरिदम है, जो प्रभावी लो-रैंक आयाम पर निर्भर लेक्सिकोग्राफिक रिग्रेट बाउंड प्राप्त करता है और ऑनलाइन न्यूटन स्टेप्स के माध्यम से एस्टीमेटर-अपडेट जटिलता को $O(T^2)$ से घटाकर $O(T)$ कर देता है।

मूल लेखक: Bo Xue, Ji Cheng, Haodong Jing, Hongzong Li, Shuang Qiu

प्रकाशित 2026-08-06

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Bo Xue, Ji Cheng, Haodong Jing, Hongzong Li, Shuang Qiu

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक अंतरिक्ष यान के कप्तान हैं जो एक ऐसे आकाशगंगा में नेविगेट करने की कोशिश कर रहे हैं जहाँ हर निर्णय के कई परिणाम होते हैं। आप निकटतम तारे तक पहुँचना चाहते हैं, लेकिन आपको ईंधन भी बचाना है, चालक दल को खुश रखना है, और खतरनाक विकिरण से बचना है। वास्तविक दुनिया में, कंप्यूटर भी हर सेकंड इसी तरह की दुविधाओं का सामना करते हैं: एक स्ट्रीमिंग सेवा चाहती है कि वह आपको ऐसी फिल्म सुझाए जिसे आप पसंद करेंगे, लेकिन उसे आपको सब्सक्राइबित भी रखना है, विज्ञापनों से आपको परेशान नहीं करना है, और आपकी गोपनीयता का सम्मान भी करना है। इस अध्ययन के क्षेत्र को "बैंडिट्स" (bandits) कहा जाता है, जिसका नाम कैसीनो में मिलने वाली एक-आर्म स्लॉट मशीनों पर रखा गया है। बिल्कुल एक जुआरी की तरह जो यह पता लगाने की कोशिश करता है कि कौन सी मशीन बिना पैसा बर्बाद किए सबसे अच्छा भुगतान करती है, एक कंप्यूटर एल्गोरिदम को यह सीखने के लिए कि सबसे अच्छा कार्य क्या है, उन्हें आजमाकर और यह देखकर सीखना होता है कि क्या होता है।

आमतौर पर, इन समस्याओं को एक समय में एक लक्ष्य को देखकर हल किया जाता है, जैसे कि केवल अधिक अंक प्राप्त करने की कोशिश करना। लेकिन जीवन शायद ही कभी इतना सरल होता है। कभी-कभी, लक्ष्यों का एक सख्त क्रम होता है। आप कह सकते हैं, "पहले, यह सुनिश्चित करें कि जहाज विस्फोट न हो; उसके बाद ही ईंधन बचाने के बारे में सोचें।" इसे "लेक्सिकोग्राफिक प्रेफरेंस" (lexicographic preference) कहा जाता है, जो एक फैंसी तरीका है यह कहने का कि "प्राथमिकताएं मायने रखती हैं।" इसके अलावा, डेटा जिसके साथ ये कंप्यूटर काम करते हैं, वह अक्सर बहुत विशाल और अव्यवस्थित होता है, जैसे कि उपयोगकर्ता की प्राथमिकताओं का एक विशाल स्प्रेडशीट। इसे समझने के लिए, वैज्ञानिक मान लेते हैं कि इस अराजकता के नीचे एक छिपा हुआ, सरल पैटर्न है, जैसे कि यह महसूस करना कि भले ही लाखों उपयोगकर्ता हैं, वे वास्तव में कुछ अलग व्यक्तित्व प्रकारों में आते हैं। इसे "लो-रैंक" (low-rank) संरचना के रूप में जाना जाता है। चुनौती यह है: आप एक कंप्यूटर को इन सख्त प्राथमिकताओं को कैसे सिखाएंगे जबकि वह डेटा की विशाल मात्रा में उस छिपे हुए सरलता को भी खोज सके, और वह भी बिना कंप्यूटर के मस्तिष्क को ओवरहीट किए?

यह शोध पत्र, जिसका शीर्षक "एफिशिएंट ऑनलाइन लेक्सिकोग्राफिक जनरलाइज्ड लो-रैंक मैट्रिक्स बैंडिट्स" (Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits) है, ठीक उसी पहेली को सुलझाता है। लेखक, बो ज़्यू (Bo Xue) और उनकी टीम, एक नई समस्या पेश करते हैं जहाँ एक कंप्यूटर को "आर्म्स" (जो वास्तव में संख्याओं के जटिल ग्रिड या मैट्रिसेस हैं) के एक विशाल पुस्तकालय से चुनना होता है ताकि कई लक्ष्यों को एक साथ अधिकतम किया जा सके, लेकिन एक सख्त पदानुक्रम के साथ। इसे एक रोबोट शेफ की तरह समझें जिसे पहले यह सुनिश्चित करना है कि भोजन खाने के लिए सुरक्षित है (प्राथमिकता 1), फिर यह सुनिश्चित करना है कि वह स्वादिष्ट है (प्राथमिकता 2), और अंत में, यह कि वह बनाने में सस्ता है (प्राथमिकता 3)। रोबोट पैसे बचाने के लिए सुरक्षा की अनदेखी नहीं कर सकता; उसे अगले स्तर पर सोचने से पहले शीर्ष प्राथमिकता को संतुष्ट करना ही होगा।

शोधकर्ताओं ने पाया कि मौजूदा तरीके या तो बहुत धीमे थे या इस काम के लिए बहुत कम बुद्धिमान थे। कुछ पुराने एल्गोरिदम पूरी समस्या को एक साथ हल करने की कोशिश करते थे, जैसे कि हर बार जब नया डेटा आता है, तो सब कुछ शुरू से ही पुनर्गणना करना। कल्पना कीजिए कि आप हर सुबह स्कूल जाने का सबसे अच्छा रास्ता खोजने के लिए अपने द्वारा देखे गए हर एक मानचित्र को फिर से पढ़ रहे हैं, ताकि यह तय किया जा सके कि किस सड़क पर मुड़ना है। यह काम करता है, लेकिन यह अविश्वसनीय रूप से धीमा और अक्षम है। अन्य विधियाँ प्राथमिकताओं को संभाल सकती थीं लेकिन डेटा में छिपे पैटर्न को अनदेखा कर देती थीं, एक जटिल मैट्रिक्स को एक विशाल, अव्यवस्थित सूची की तरह मानती थीं, जिससे वे सांख्यिकीय रूप से भद्दी हो जाती थीं।

इसे ठीक करने के लिए, टीम ने लेक्सी-लोजीएलएम (Lexi-LowGLM) नामक एक नया एल्गोरिदम बनाया। वे इसे दो-चरणीय नृत्य के रूप में वर्णित करते हैं। पहला, एल्गोरिदम डेटा पर एक त्वरित नज़र डालता है ताकि "गुप्त उप-स्थानों" (secret subspaces) को खोजा जा सके—वे छिपे हुए, सरल पैटर्न जहाँ वास्तविक गतिविधि होती है। यह उन शॉर्टकटों को खोजने जैसा है कि भले ही दस लाख अलग-अलग गाने हों, वे सभी मुख्य रूप से उन्हीं दस कॉर्ड्स का उपयोग करते हैं। एक बार जब यह इन शॉर्टकटों को खोज लेता है, तो यह पूरे अस्त-व्यस्त स्प्रेडशीट को देखना बंद कर देता है और केवल महत्वपूर्ण हिस्सों पर ध्यान केंद्रित करता है। दूसरा, अपनी पूरी गलतियों के इतिहास को हर बार फिर से पढ़ने के बजाय, यह एक चतुर "ऑनलाइन अपडेट" ट्रिक का उपयोग करता है। यह एक छात्र की तरह है जो, टेस्ट देने के बाद, पूरी पाठ्यपुस्तक को फिर से नहीं पढ़ता बल्कि केवल उस एक प्रश्न के आधार पर अपनी समझ को थोड़ा बदल देता है जो उसने गलत किया था। यह सीखने की प्रक्रिया को बिजली की तरह तेज़ बनाता है।

यह पत्र गणितीय रूप से सिद्ध करता है कि यह नया तरीका अच्छा काम करता है। उन्होंने दिखाया कि "रिग्रेट" (regret)—वह अंक या मूल्य जो रोबोट तब खो देता है जब वह पूर्ण नहीं होता—बहुत धीरे बढ़ता है, पुराने तरीकों की तुलना में बहुत धीमा। विशेष रूप से, त्रुटि कच्चे डेटा के विशाल आकार के बजाय छिपे हुए पैटर्न (लो-रैंक डायमेंशन) के आकार पर निर्भर करती है। अपने कंप्यूटर सिमुलेशन में, उन्होंने अन्य विधियों के विरुद्ध इसका परीक्षण किया। परिणामों ने दिखाया कि जबकि अन्य एल्गोरिदम फंस गए या बहुत धीरे चले, लेक्सी-लोजीएलएम ने तेजी से सीखा और केवल शीर्ष उद्देश्य के लिए ही नहीं, बल्कि सभी उद्देश्यों के लिए कम रिग्रेट बनाए रखा। सबसे प्रभावशाली बात यह है कि यह नाटकीय रूप से तेज़ था: उनके परीक्षणों में, इसने 10,000 राउंड का सिमुलेशन केवल 4 सेकंड से कुछ अधिक समय में पूरा कर लिया, जबकि अगली सबसे तेज़ विधि को 87 सेकंड से अधिक समय लगा, और सबसे गहन (लेकिन सबसे धीमी) विधि को लगभग 228 सेकंड लगे।

लेखक सावधानीपूर्वक नोट करते हैं कि यह सिमुलेशन द्वारा समर्थित एक सैद्धांतिक सफलता है, न कि अभी हर वास्तविक दुनिया की समस्या के लिए एक जादू की छड़ी। वे इस विचार को स्पष्ट रूप से खारिज करते हैं कि सभी लक्ष्यों को एक बड़े स्कोर में जोड़ना सबसे अच्छा तरीका है, यह दिखाते हुए कि जब लक्ष्य आपस में टकराते हैं तो सख्त प्राथमिकता आवश्यक है। वे पुराने तरीके के खिलाफ भी तर्क देते हैं जिसमें सब कुछ शुरू से पुनर्गणना की जाती है, यह सिद्ध करते हुए कि उनका "ऑनलाइन" अपडेट तरीका लंबे समय तक सीखने के लिए कहीं अधिक श्रेष्ठ है। हालांकि गणित जटिल है, मूल विचार सरल है: डेटा में छिपे शॉर्टकटों को खोजने और महत्व के क्रम का सम्मान करने के साथ, आप एक कंप्यूटर को स्मार्ट, तेज़ और सुरक्षित निर्णय लेने के लिए सिखा सकते हैं बिना उसके प्रोसेसर को थकाए।

तकनीकी सारांश: कुशल ऑनलाइन लेक्सिकोग्राफिक जनरलाइज्ड लो-रैंक मैट्रिक्स बैंडिट्स

समस्या का निरूपण (Problem Formulation)

यह शोध पत्र लेक्सिकोग्राफिक जनरलाइज्ड लो-रैंक मैट्रिक्स बैंडिट्स की समस्या को संबोधित करता है। यह सेटिंग मानक कॉन्टेक्स्टुअल बैंडिट फ्रेमवर्क का विस्तार करती है और निम्नलिखित परिदृश्यों को शामिल करती है:

मैट्रिक्स-वैल्यूड आर्म्स (Matrix-valued arms): क्रियाओं (actions) को वेक्टर्स के बजाय मैट्रसेज़ $X \in \mathbb{R}^{d_1 \times d_2}$ के रूप में दर्शाया जाता है, जो युग्मवार इंटरैक्शन (जैसे, यूजर-आइटम, एजेंट-टास्क) को कैप्चर करते हैं जहाँ वेक्टरकरण करने से संरचनात्मक जानकारी लुप्त हो जाती है और अक्षमता उत्पन्न होती है।
बहु-प्राथमिकता वाले उद्देश्य (Multiple prioritized objectives): लर्नर को एक वेक्टर-वैल्यूड रिवॉर्ड $y_t \in \mathbb{R}^m$ प्राप्त होता है, जहाँ प्रत्येक घटक एक अलग उद्देश्य के अनुरूप होता है। इन उद्देश्यों में एक सख्त प्राथमिकता क्रम (लेक्सिकोग्राफिक वरीयता) होता है, जिसका अर्थ है कि उच्च-प्राथमिकता वाले उद्देश्यों को अनुकूलित करना अनिवार्य है, इससे पहले कि निचले-प्राथमिकता वाले उद्देश्यों पर विचार किया जाए।
जनरलाइज्ड लो-रैंक संरचना (Generalized Low-Rank Structure): प्रत्येक उद्देश्य $i$ के लिए अपेक्षित रिवॉर्ड को $\mu_i(\langle X_t, \Theta^*_i \rangle)$ के रूप में मॉडल किया गया है, जहाँ $\mu_i$ एक इनवर्स लिंक फंक्शन है और $\Theta^*_i$ एक अज्ञात पैरामीटर मैट्रिक्स है जिसका रैंक $r \ll \min\{d_1, d_2\}$ है।

लक्ष्य एक ऐसा एल्गोरिदम डिजाइन करना है जो लेक्सिकोग्राफिक रूप से इष्टतम आर्म के सापेक्ष प्रत्येक उद्देश्य $i \in [m]$ के लिए सबलीनियर संचयी रिग्रेट (cumulative regret) प्राप्त करे, और साथ ही लंबे समय तक चलने वाले ऑनलाइन लर्निंग के लिए उपयुक्त कम्प्यूटेशनल दक्षता बनाए रखे।

कार्यप्रणाली (Methodology)

लेखक Lexi-LowGLM का प्रस्ताव करते हैं, जो एक कुशल ऑनलाइन एल्गोरिदम है जो तीन मुख्य घटकों को एकीकृत करता है:

1. सुदृढ़ उद्देश्य-विशिष्ट सबस्पेस अनुमान (Robust Objective-Specific Subspace Estimation)

एम्बिएंट डायमेंशन लागत ( $d_1 d_2$ ) से बचने के लिए लो-रैंक संरचना का लाभ उठाने हेतु, एल्गोरिदम पहले एक अन्वेषण चरण ( $T_1$ राउंड) करता है। इस चरण के दौरान, यह एक विशिष्ट अन्वेषण वितरण से आर्म्स को सैंपल करता है और एक स्टीन-टाइप सबस्पेस एस्टीमेशन दृष्टिकोण का उपयोग करता है।

यह प्रत्येक उद्देश्य $i$ के लिए एक अलग लो-रैंक एस्टीमेटर $\hat{\Theta}_i$ बनाता है, जो न्यूक्लियर-नॉर्म रेगुलराइज्ड ऑप्टिमाइज़ेशन समस्या को हल करता है।
इन एस्टीमेटर्स का उपयोग रोटेशन ऑपरेटर्स प्राप्त करने के लिए किया जाता है जो मूल मैट्रिक्स आर्म्स को कम किए गए फीचर रिप्रेजेंटेशन $f_i(X)$ में बदल देते हैं। यह रूपांतरण आर्म्स को अनुमानित रो (row) और कॉलम (column) सबस्पेस पर प्रोजेक्ट करता है, जिससे डायमेंशनलिटी $d_1 d_2$ से घटकर प्रभावी लो-रैंक डायमेंशन लगभग $(d_1 + d_2)r$ हो जाती है।

2. लेक्सिकोग्राफिक कैंडिडेट फ़िल्टरिंग (Lexicographic Candidate Filtering)

उद्देश्यों को एक एकल स्कोर में संयोजित करने वाले स्केलेराइजेशन विधियों के विपरीत, Lexi-LowGLM अनुक्रमिक फ़िल्टरिंग के माध्यम से लेक्सिकोग्राफिक संरचना को स्पष्ट रूप से सुरक्षित रखता है:

प्रत्येक राउंड में, एल्गोरिदम आर्म्स का एक कैंडिडेट सेट बनाए रखता है।
यह उच्चतम-प्राथमिकता वाले उद्देश्य ( $i=1$ ) से लेकर निम्नतम-प्राथमिकता वाले उद्देश्य ( $i=m$ ) तक इस सेट को पुनरावर्ती रूप से परिष्कृत करता है।
प्रत्येक उद्देश्य के लिए, यह वर्तमान कैंडिडेट सेट में सबसे अच्छे अनुभवजन्य (empirical) आर्म का चयन करता है और उन आर्म्स को हटा देता है जिनके अनुमानित रिवॉर्ड्स काफी कमतर हैं, जिसमें एक टॉलरेंस थ्रेशोल्ड का उपयोग किया जाता है जो लेक्सिकोग्राफिक ट्रेड-ऑफ से प्रेरित होता है।
यह प्रक्रिया सुनिश्चित करती है कि निचले-प्राथमिकता वाले उद्देश्यों को केवल उन्हीं आर्म्स के बीच अनुकूलित किया जाए जो सभी उच्च-प्राथमिकता वाले उद्देश्यों के संबंध में प्रतिस्पर्धी बने रहते हैं।

3. ऑनलाइन न्यूटन-टाइप अपडेट्स (Online Newton-Type Updates)

मौजूदा जनरलाइज्ड लो-रैंक मैट्रिक्स बैंडिट विधियों की कम्प्यूटेशनल बाधा (जो आमतौर पर बैच एस्टीमेटर्स को पुन: कंप्यूट करती हैं, जिससे $O(T^2)$ जटिलता आती है) को दूर करने के लिए, Lexi-LowGLM एक ऑनलाइन अपडेट मैकेनिज्म का उपयोग करता है:

हर राउंड में पूरे ऐतिहासिक डेटा पर बैच ऑप्टिमाइज़ेशन समस्या को फिर से हल करने के बजाय, एल्गोरिदम प्रत्येक उद्देश्य-विशिष्ट एस्टीमेटर को एक न्यूटन-टाइप प्रॉक्सिमल स्टेप के माध्यम से अपडेट करता है।
यह अपडेट केवल वर्तमान अवलोकन और पिछले एस्टीमेटर पर निर्भर करता है, जिससे $T$ राउंडों में संचयी एस्टीमेटर-अपडेट जटिलता $O(T^2)$ से घटकर $O(T)$ हो जाती है।

पेपर एक बेसलाइन एल्गोरिदम, Scalar-LowGLM भी पेश करता है, जो वेक्टर रिवॉर्ड्स को स्केलेराइज करता है और बैच अपडेट का उपयोग करता है, जो एक सैद्धांतिक और अनुभवजन्य तुलना बिंदु के रूप में कार्य करता है।

मुख्य योगदान (Key Contributions)

पेपर निम्नलिखित प्राथमिक योगदानों का दावा करता है:

समस्या का निरूपण: यह मल्टी-ऑब्जेक्टिव फीडबैक के साथ जनरलाइज्ड लो-रैंक मैट्रिक्स बैंडिट्स को फॉर्म्युलेट करने वाला पहला कार्य है, जो स्केलर-रिवॉर्ड सेटिंग्स से आगे बढ़कर कई प्राथमिकता वाले उद्देश्यों को एक साथ संभालने में सक्षम है।
कुशल एल्गोरिदम: Lexi-LowGLM का प्रस्ताव, जो उद्देश्य-विशिष्ट सबस्पेस एस्टीमेशन को लेक्सिकोग्राफिक फ़िल्टरिंग और ऑनलाइन न्यूटन अपडेट्स के साथ जोड़ता है। यह दृष्टिकोण एस्टीमेटर अपडेट की संचयी कम्प्यूटेशनल जटिलता को $O(T^2)$ से घटाकर $O(T)$ कर देता है।
रिग्रेट गारंटी: ऑब्जेक्टिव-वाइज रिग्रेट बाउंड्स की स्थापना। प्रत्येक उद्देश्य $i$ $i$ के लिए, रिग्रेट $\tilde{O}(W^{\text{lex}}_i \sqrt{m} (d_1 + d_2)r \sqrt{T})$ $\tilde{O} (W_{i}^{lex} m (d_{1} + d_{2}) r T)$ के रूप में स्केल करता है, जहाँ $W^{\text{lex}}_i$ $W_{i}^{lex}$ लेक्सिकोग्राफिक ट्रेड-ऑफ प्रभाव को दर्शाता है।
- यह बाउंड एम्बिएंट डायमेंशन $d_1 d_2$ के बजाय प्रभावी लो-रैंक डायमेंशन $(d_1 + d_2)r$ पर निर्भर करता है।
- जब ट्रेड-ऑफ पैरामीटर $w=0$ होता है, तो रिग्रेट बाउंड बिना किसी अतिरिक्त प्रायोरिटी-प्रोपैगेशन पेनल्टी के सभी उद्देश्यों के लिए यूनिफॉर्म होता है।
अनुभवजन्य सत्यापन (Empirical Validation): सिंथेटिक इंस्टेंस पर संख्यात्मक प्रयोग दर्शाते हैं कि प्रस्तावित विधि बेसलाइन्स (G-ESTT और MTLO) की तुलना में निचले-प्राथमिकता वाले उद्देश्यों पर कम रिग्रेट प्राप्त करती है और परीक्षण किए गए सेटिंग में काफी तेज़ रनटाइम (G-ESTT से लगभग 21 $\times$ तेज़ और Scalar-LowGLM से 55 $\times$ तेज़) प्रदर्शित करती है।

परिणाम और महत्व (Results and Significance)

पेपर स्थापित करता है कि Lexi-LowGLM सिंगल-ऑब्जेक्टिव जनरलाइज्ड लो-रैंक बैंडिट्स की दरों से मेल खाते हुए, टाइम होराइजन $T$ और प्रभावी लो-रैंक डायमेंशन पर स्टेट-ऑफ-द-आर्ट डिपेंडेंस प्राप्त करता है, जबकि कई उद्देश्यों को संयुक्त रूप से सीखता है।

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

पेपर भविष्य की दिशाओं की पहचान करते हुए समाप्त होता है, जिसमें रैंक-एडेप्टिव लर्निंग तक विस्तार करना, नॉन-स्टेशनरी या डिलेड रिवॉर्ड्स को संभालना, और लेक्सिकोग्राफिक लो-रैंक मैट्रिक्स बैंडिट्स के लिए मैचिंग लोअर बाउंड्स प्राप्त करना शामिल है।