📊 statistics

The Stability of Online Algorithms in Performative Prediction

यह शोधपत्र एक बिना शर्त रिडक्शन (unconditional reduction) स्थापित करता है जो यह सिद्ध करता है कि परफॉर्मेटिव प्रेडिक्शन सेटिंग्स में तैनात कोई भी नो-रिग्रेट ऑनलाइन एल्गोरिदम एक परफॉर्मेटिवली स्टेबल इक्विलिब्रियम (performatively stable equilibrium) की ओर अभिसरित होता है, जिससे यह प्रदर्शित होता है कि ऐसे एल्गोरिदम मॉडल के डेटा वितरण को कैसे प्रभावित करते हैं, इस पर प्रतिबंधात्मक धारणाओं की आवश्यकता के बिना स्वाभाविक रूप से रनवे फीडबैक लूप्स को रोकते हैं।

मूल लेखक: Gabriele Farina, Juan Carlos Perdomo

प्रकाशित 2026-03-02

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

CC BY 4.0

मूल लेखक: Gabriele Farina, Juan Carlos Perdomo

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

यहाँ पेपर "The Stability of Online Algorithms in Performative Prediction" का सरल भाषा और रचनात्मक उपमाओं (analogies) के साथ अनुवाद दिया गया है।

बड़ी तस्वीर: "स्वयं-सिद्ध भविष्यवाणी" (Self-Fulfilling Prophecy) की समस्या

कल्पना कीजिए कि आप एक मौसम विज्ञानी हैं।

परिदृश्य A (सामान्य): आप बारिश की भविष्यवाणी करते हैं। लोग छाते साथ लाते हैं। बारिश होती है। आप सही थे। आपकी भविष्यवाणी से दुनिया नहीं बदली।
परिदृश्य B (परफॉर्मेटिव): आप एक भारी ट्रैफिक जाम की भविष्यवाणी करते हैं। आपकी भविष्यवाणी के कारण, हर कोई घर पर रुकने या दूसरा रास्ता चुनने का फैसला करता है। अचानक, सड़कें खाली हो जाती हैं! आपकी भविष्यवाणी ने ट्रैफिक जाम को होने ही नहीं दिया।

यही वह मुख्य समस्या है जिसे यह पेपर संबोधित करता है: जब एल्गोरिदम भविष्यवाणियाँ करते हैं, तो वे अक्सर मानवीय व्यवहार को बदल देते हैं, जिससे वह डेटा बदल जाता है जिसे एल्गोरिदम अगली बार देखता है।

यदि किसी बैंक का AI भविष्यवाणी करता है कि आप ऋण (loan) के लिए "उच्च जोखिम" (high risk) वाले व्यक्ति हैं, तो आपको क्रेडिट देने से मना किया जा सकता है। बिना क्रेडिट के, आप एक अच्छा वित्तीय इतिहास नहीं बना सकते, इसलिए आप वास्तव में "उच्च जोखिम" बन जाते हैं। AI की भविष्यवाणी ने उसी वास्तविकता को पैदा कर दिया जिससे वह डर रहा था। यह एक ऐसा फीडबैक लूप बनाता है जो नियंत्रण से बाहर हो सकता है, जिससे सिस्टम अस्थिर और अप्रत्याशित हो जाता है।

पुराना तरीका: दुनिया को नियंत्रित करने की कोशिश

वर्षों तक, शोधकर्ताओं ने इसे इस धारणा के साथ ठीक करने की कोशिश की कि दुनिया "कोमल" (gentle) है। उन्होंने माना कि यदि एक एल्गोरिदम अपना निर्णय थोड़ा बदलता है, तो दुनिया भी प्रतिक्रिया में थोड़ा ही बदलेगी। उन्होंने इसे "लिप्सचिट्ज़ कंडीशन" (Lipschitz condition) कहा (एक फैंसी गणितीय तरीका जिसका अर्थ है "अचानक उछाल न होना")।

उपमा: कल्पना कीजिए कि आप अपने हाथ पर एक झाड़ू संतुलित करने की कोशिश कर रहे हैं।

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

नई खोज: "गिरगिट रणनीति" (Chameleon Strategy)

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

उपमा: "ब्लाइंड टेस्ट" (Blind Taste Test)
कल्पना कीजिए कि एक रेस्टोरेंट सूप की सही रेसिपी खोजने की कोशिश कर रहा है।

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

जादुई तत्व: "नो-रिग्रेट" (No-Regret) एल्गोरिदम

हम इस मिश्रण को कैसे बनाते हैं? यह पेपर ऑनलाइन लर्निंग की एक अवधारणा का उपयोग करता है जिसे "नो-रिग्रेट" कहा जाता है।

एक कैसीनो में जुआ खेलने वाले खिलाड़ी के बारे में सोचें।

एक "नो-रिग्रेट" जुआरी भविष्य की सटीक भविष्यवाणी करने की कोशिश नहीं करता है। इसके बजाय, वह बस यह सुनिश्चित करता है कि समय के साथ, उसने उस बेहतर रणनीति को नहीं छोड़ा जिसे वह इस्तेमाल कर सकता था।
यदि उसने 1,000 बार खेल खेला, तो उसकी कुल जीत लगभग उतनी ही अच्छी होगी जितनी कि उसे यह पता होता कि पीछे मुड़कर देखने पर (in hindsight) हर हाथ के लिए सबसे अच्छा कदम क्या था।

पेपर एक जादुई संबंध सिद्ध करता है: यदि आप अपने मॉडलों को समय के साथ अपडेट करने के लिए एक "नो-रिग्रेट" एल्गोरिदम का उपयोग करते हैं, और फिर अपने द्वारा बनाए गए सभी मॉडलों में से एक रैंडम सैंपल लेते हैं, तो वह मिश्रण गारंटी के साथ स्थिर रहेगा।

इससे कोई फर्क नहीं पड़ता कि दुनिया अराजक है, डेटा उछल-कूद कर रहा है, या नियम अचानक बदल रहे हैं। जब तक एल्गोरिदम समय के साथ अपने 'रिग्रेट' (पछतावे) को कम करने में "पर्याप्त स्मार्ट" है, तब तक उसके द्वारा बनाए गए मॉडलों का मिश्रण उस अनियंत्रित फीडबैक लूप को रोक देगा।

यह क्यों मायने रखता है (The "Aha!" Moment)

यह हर जगह काम करता है: पुराने तरीके विफल हो जाते थे यदि डेटा "उछल-कूद" वाला था (जैसे एक छात्र का सख्त कट-ऑफ स्कोर के आधार पर पास या फेल होना)। यह नया तरीका उन "जंपी" या विच्छिन्न (discontinuous) नियमों के साथ भी काम करता है।
यह बताता है कि हम क्रैश क्यों नहीं होते: आप सोच सकते हैं, "हमारे वर्तमान AI सिस्टम (जैसे रिकमेंडेशन इंजन) अर्थव्यवस्था या समाज को क्रैश क्यों नहीं करते?" पेपर सुझाव देता है कि ऐसा इसलिए है क्योंकि ये सिस्टम स्वाभाविक रूप से "नो-रिग्रेट" एल्गोरिदम की तरह काम करते हैं। वे लगातार खुद को ट्यून और रिट्रेन करते रहते हैं, और भले ही वे एक चलते हुए लक्ष्य (moving target) का पीछा कर रहे हों, उनके व्यवहार का औसत स्वाभाविक रूप से एक स्थिर अवस्था में बस जाता है।
किसी जादुई धारणा की आवश्यकता नहीं: हमें यह मानने की आवश्यकता नहीं है कि दुनिया बहुत सुचारू (smooth) है। हमें बस यह आवश्यकता है कि एल्गोरिदम सीखते और अनुकूलित होते रहे।

एक वाक्य में सारांश

एक ऐसे पूर्ण, अपरिवर्तनीय क्रिस्टल बॉल को खोजने के बजाय जो भविष्य की भविष्यवाणी करता है (जो असंभव है जब भविष्य भविष्यवाणी के कारण ही बदल जाता है), हमें एक "नो-रिग्रेट" लर्निंग प्रक्रिया का उपयोग करना चाहिए जो लगातार अनुकूलित होती रहे; इसके द्वारा बनाए गए सभी मॉडलों का औसत स्वाभाविक रूप से सिस्टम को स्थिर कर देगा, जिससे अराजक वातावरण में भी अनियंत्रित फीडबैक लूप को रोका जा सकेगा।

यहाँ गैब्रिएल फरीना और जुआन कार्लोस पेरडोमो के शोध पत्र "The Stability of Online Algorithms in Performative Prediction" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र परफॉर्मेटिव प्रेडिक्शन (Performative Prediction) की चुनौती को संबोधित करता है, जो एक ऐसा ढांचा है जहाँ एक प्रेडिक्टिव मॉडल का परिनियोजन (deployment) सक्रिय रूप से उस डेटा वितरण (data distribution) को प्रभावित करता है जिसका वह बाद में सामना करेगा।

फीडबैक लूप (The Feedback Loop): जब एक मॉडल $\theta$ तैनात किया जाता है, तो यह एक वितरण $D(\theta)$ को प्रेरित करता है। फिर लर्नर (learner) डेटा $z \sim D(\theta)$ को देखता है, जिसका उपयोग मॉडल को अपडेट करने के लिए किया जाता है। यह एक गतिशील फीडबैक लूप बनाता है जहाँ मॉडल डेटा को आकार देता है, और डेटा मॉडल को आकार देता है।
लक्ष्य (The Goal): उद्देश्य एक परफॉर्मेटिवली स्टेबल (Performatively Stable) समाधान खोजना है। एक मॉडल (या मॉडलों का मिश्रण) तब स्थिर होता है जब, तैनात होने पर, इसके द्वारा प्रेरित डेटा मॉडल के भविष्य के अनुमानों को 'इन ह hindsight' (hindsight में) इष्टतम बनाता है। औपचारिक रूप से, एक मिश्रण $\mu$ स्थिर है यदि:
$\mathbb{E}_{\theta \sim \mu} \mathbb{E}_{z \sim D(\theta)} [\ell(z; \theta)] \leq \min_{\theta'} \mathbb{E}_{\theta \sim \mu} \mathbb{E}_{z \sim D(\theta)} [\ell(z; \theta')] + \epsilon$
पूर्ववर्ती कार्यों की सीमाएँ (Limitations of Prior Work): पिछले सकारात्मक परिणाम मजबूत धारणाओं पर निर्भर थे:
1. लिप्सचिट्ज़ निरंतरता (Lipschitz Continuity): वितरण मानचित्र $D(\cdot)$ को लिप्सचिट्ज़ निरंतर होना चाहिए (अर्थात $\theta$ में छोटे बदलावों से $D(\theta)$ में छोटे बदलाव होने चाहिए)। यह थ्रेशोल्डिंग (जैसे क्रेडिट अप्रूवल कटऑफ, मेडिकल इंटरवेंशन) वाले वास्तविक परिदृश्यों में विफल रहता है।
2. कन्वेक्सिटी/स्मूथनेस (Convexity/Smoothness): लॉस फंक्शन (loss functions) के लिए अक्सर स्ट्रॉन्गली कॉन्वेक्स (strongly convex) और स्मूथ होने की आवश्यकता होती थी।
3. कॉन्ट्रैक्शन (Contraction): फीडबैक लूप को एक कॉन्ट्रैक्शन ( $\rho < 1$ ) माना गया था।
4. कठिनाई (Hardness): हाल के परिणामों (Anagnostides et al., 2026) ने दिखाया कि इन अनुकूल धारणाओं के तहत भी एक एकल स्थिर मॉडल खोजना PPAD-complete है, और यदि $D(\cdot)$ विच्छिन्न (discontinuous) है, तो स्थिर मॉडल अस्तित्व में भी नहीं हो सकते।

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

लेखक एक अभिनव दृष्टिकोण प्रस्तावित करते हैं जो ध्यान को एक एकल नियत (deterministic) स्थिर मॉडल खोजने से हटाकर एक स्थिर मिश्रण (stable mixture) खोजने की ओर केंद्रित करता है।

मुख्य अंतर्दृष्टि (Core Insight): वे नो-रिग्रेट ऑनलाइन लर्निंग (No-Regret Online Learning) से परफॉर्मेटिव स्टेबिलिटी तक एक अनकंडीशनल रिडक्शन (unconditional reduction) स्थापित करते हैं।
तंत्र (The Mechanism):
1. एक ऑनलाइन लर्निंग एल्गोरिदम पर विचार करें जो मॉडलों का एक अनुक्रम $\theta_1, \dots, \theta_T$ चुनता है।
2. प्रत्येक चरण $t$ पर, लर्नर $\theta_t$ को तैनात करता है, एक सैंपल $z_t \sim D(\theta_t)$ देखता है, और एक लॉस $\ell(z_t, \theta_t)$ का सामना करता है।
3. एल्गोरिदम इस लॉस के आधार पर $\theta_{t+1}$ को अपडेट करता है।
4. अंतिम इटरैट (iterate) $\theta_T$ को तैनात करने के बजाय, लर्नर पूरे अनुक्रम $\{\theta_1, \dots, \theta_T\}$ पर एक यूनिफॉर्म मिक्सचर (uniform mixture) $\mu$ तैनात करता है।
सैद्धांतिक उपकरण (Theoretical Tool): प्रमाण एक मार्टिंगेल तर्क (martingale argument) का उपयोग करता है।
- मानक ऑनलाइन-टू-बैच रूपांतरण यह मानते हैं कि नमूने एक निश्चित वितरण से लिए जाते हैं। यहाँ, वितरण $D(\theta_t)$ लर्नर के चुनाव के साथ बदलता है।
- लेखक दिखाते हैं कि प्रेरित वितरण पर अपेक्षित लॉस (expected loss) और देखे गए लॉस के बीच का अंतर एक मार्टिंगेल डिफरेंस सीक्वेंस बनाता है।
- क्योंकि ऑनलाइन एल्गोरिदम एडेप्टिव एडवर्सरीज (जहाँ लॉस फंक्शन पिछले एक्शन पर निर्भर कर सकता है) के विरुद्ध कम रिग्रेट की गारंटी देता है, इसलिए संचयी रिग्रेट (cumulative regret) स्थिरता से विचलन को सीमित करता है।

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

अनकंडीशनल रिडक्शन (Unconditional Reduction): यह शोध पत्र सिद्ध करता है कि परफॉर्मेटिव सेटिंग में तैनात किया गया कोई भी नो-रिग्रेट एल्गोरिदम एक परफॉर्मेटिवली स्टेबल मिश्रण की ओर अभिसरित (converge) होता है। यह बिना किसी धारणा के संभव है (न तो वितरण मानचित्र $D(\cdot)$ के लिए लिप्सचिट्ज़ निरंतरता की आवश्यकता है और न ही लॉस फंक्शन $\ell$ के लिए स्ट्रॉन्ग कॉन्वेक्सिटी या स्मूथनेस की)।
कठिनाई के परिणामों को दरकिनार करना (Sidestepping Hardness Results): रैंडमाइजेशन (मिश्रणों) की अनुमति देकर, लेखक उन PPAD-completeness परिणामों को दरकिनिर्द करते हैं जो विच्छिन्न (discontinuous) सेटिंग्स में स्थिर एकल मॉडल खोजने से रोकते हैं।
मौजूदा एल्गोरिदम का सामान्यीकरण (Generalization of Existing Algorithms): यह कार्य एक एकीकृत सैद्धांतिक औचित्य प्रदान करता है कि क्यों सामान्य एल्गोरिदम (ग्रेडिएंट डिसेंट, फॉलो-द-लीडर, रिट्रेनिंग) गतिशील वातावरण में स्वाभाविक रूप से स्थिर होते हैं, यहाँ तक कि उन रेजीमों में भी जिन्हें पहले अस्थिर माना जाता था।
नए अभिसरण दर (New Convergence Rates): यह शोध पत्र निम्नलिखित के लिए पहले स्थिरता गारंटी स्थापित करता है:
- वीकली कॉन्वेक्स (weakly convex) या नॉन-स्मूथ लॉस।
- मनमाने (संभावित रूप से विच्छिन्न) वितरण मानचित्र।
- विशिष्ट लॉस प्रकारों (जैसे लॉग-लॉस के लिए exp-concave losses) के लिए बेहतर कन्वर्जेंस रेट ( $O(1/T)$ या $O(\log T / T)$ ) के साथ परिमित-नमूना (finite-sample) सेटिंग्स।

4. मुख्य परिणाम (Key Results)

मुख्य प्रमेय (Theorem 3) बताता है कि यदि एक ऑनलाइन एल्गोरिदम स्टोकेस्टिक लॉस $\ell_t(\theta) = \ell(z_t, \theta)$ (जहाँ $z_t \sim D(\theta_t)$ ) पर सबलीनियर रिग्रेट $Regret(T) $प्राप्त करता है, तो इटरैट्स$ \mu $पर यूनिफॉर्म मिक्सचर$ \frac{Regret(T)}{T}$-परफॉर्मेटिवली स्टेबल है।

विशिष्ट उप-प्रमेय (Corollaries) शामिल हैं:

रिट्रेनिंग (Follow-the-Leader): $\gamma$ -स्ट्रॉन्गली कॉन्वेक्स लॉस के लिए, बार-बार रिट्रेनिंग करने से एक मिश्रण प्राप्त होता है जिसकी स्थिरता त्रुटि (stability error) $O(\frac{\log T}{T})$ है। यह $D(\cdot)$ पर लिप्सचिट्ज़ धारणाओं के बिना रिट्रेनिंग के लिए पहला परिमित-नमूना स्थिरता प्रमाण है।
ग्रेडिएंट डिसेंट (Gradient Descent):
- कॉन्वेक्स लॉस के लिए: स्थिरता त्रुटि $O(\frac{1}{\sqrt{T}})$ ।
- स्ट्रॉन्गली कॉन्वेक्स लॉस के लिए: स्थिरता त्रुटि $O(\frac{\log T}{T})$ ।
- महत्वपूर्ण रूप से, ये नॉन-स्मूथ लॉस और मनमाने $D(\cdot)$ के लिए भी मान्य हैं।
एक्सप-कॉन्केव लॉस (जैसे लॉग-लॉस, स्क्वेयर्ड लॉस): ऑनलाइन न्यूटन स्टेप एल्गोरिदम का उपयोग करके, यह शोध पत्र मानक मशीन लर्निंग लॉस के लिए $O(\frac{\log T}{T})$ स्थिरता दर प्राप्त करता है, जो पहले स्ट्रॉन्ग कॉन्वेक्सिटी के बिना परफॉर्मेटिव सेटिंग्स में विश्लेषण करना कठिन था।

5. महत्व और निहितार्थ (Significance and Implications)

सैद्धांतिक सफलता (Theoretical Breakthrough): यह कार्य परफॉर्मेटिव प्रेडिक्शन की समझ को मौलिक रूप से बदल देता है। यह प्रदर्शित करता है कि गतिशील सामाजिक प्रणालियों में डरे जाने वाले "रनवे फीडबैक लूप" (runaway feedback loops) स्वाभाविक रूप से नो-रिग्रेट लर्निंग डायनेमिक्स द्वारा नियंत्रित होते हैं, बशर्ते लर्नर अपने मॉडलों के इतिहास पर रैंडमाइजेशन करने के लिए तैयार हो।
व्यावहारिक प्रासंगिकता (Practical Relevance):
- यह उच्च-जोखिम वाले डोमेन (चिकित्सा, शिक्षा, वित्त) में मानक रिट्रेनिंग पाइपलाइनों के उपयोग को वैध बनाता है, जहाँ थ्रेशोल्ड के प्रति मानवीय प्रतिक्रिया के कारण डेटा वितरण विच्छिन्न रूप से बदल सकता है।
- यह समझाता है कि ग्रेडिएंट डिसेंट व्यवहार में अक्सर क्यों काम करता है, भले ही विच्छिन्न सेटिंग्स में सैद्धांतिक अस्थिरता हो: एल्गोरिदम स्पष्ट रूप से एक ऐसे पथ (trajectory) का अन्वेषण करता है जो एक स्थिर अवस्था तक औसत निकाल देता है।
भविष्य की दिशाएं (Future Directions): यह शोध पत्र ऑनलाइन ऑप्टिमाइज़ेशन और परफॉर्मेटिविटी के संगम पर अनुसंधान के नए मार्ग खोलता है, जिसमें शामिल हैं:
- मल्टी-प्लेयर सेटिंग्स (जहाँ कई एजेंट डेटा को प्रभावित करते हैं) तक परिणामों का विस्तार करना।
- स्टेटफुल (Stateful) सेटिंग्स (जहाँ डेटा मॉडलों के पूरे इतिहास पर निर्भर करता है) की जांच करना।
- यह जांचना कि किन परिस्थितियों में स्थिर मिश्रण न केवल स्थिरता, बल्कि परफॉर्मेटिव ऑप्टिमलिटी (वास्तविक परफॉर्मेटिव रिस्क को न्यूनतम करना) भी प्राप्त करते हैं।

संक्षेप में, फरीना और पेरडोमो एक मजबूत, धारणा-मुक्त सैद्धांतिक ढांचा प्रदान करते हैं जो दिखाता है कि नो-रिग्रेट एल्गोरिदम के प्रक्षेपवक्र (trajectory) पर रैंडमाइजेशन परफॉर्मेटिव प्रेडिक्शन में स्थिरता प्राप्त करने की कुंजी है, जो प्रभावी रूप से उन व्यापक श्रेणियों की समस्याओं को हल करता है जो पहले अगम्य (intractable) मानी जाती थीं।