तकनीकी सारांश: वासेरस्टीन दूरी अनुमान के लिए कम्प्यूटेशनल-सांख्यिकीय रनटाइम का अनुकूलन (Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation)

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

वर्ग वासेरस्टीन दूरी (squared Wasserstein distance), $W_2^2(P, Q)$, $\mathbb{R}^d$ में प्रायिकता वितरणों $P$ और $Q$ के बीच विसंगति को मापने के लिए एक मानक मीट्रिक है। व्यावहारिक डेटा विश्लेषण और मशीन लर्निंग कार्यों (जैसे, पैरामीटर अनुमान, परिकल्पना परीक्षण) में, ये वितरण अज्ञात होते हैं और इन्हें आकार $n$ के प्रायोगिक नमूनों $\hat{P}_n$ और $\hat{Q}_n$ से अनुमानित किया जाना चाहिए।

मौजूदा दृष्टिकोण एक मौलिक बाधा का सामना करते हैं: $W_2^2(\hat{P}_n, \hat{Q}_n)$ की गणना करने के लिए, जो $\epsilon$-एडिटिव एरर (additive error) के साथ सटीक होती है, आमतौर पर ऐसा रनटाइम आवश्यक होता है जो $n$ और $\epsilon$ के साथ खराब तरीके से स्केल करता है (जैसे, $O(n^2/\epsilon^2)$ या इससे भी बदतर)। इसके विपरीत, विशुद्ध रूप से सांख्यिकीय दृष्टिकोण, जो प्रायोगिक मापों के अभिसरण दर (convergence rate) पर निर्भर करते हैं, अक्सर बड़े डेटासेट पर ऑप्टिमल ट्रांसपोर्ट समस्या को हल करने की कम्प्यूटेशनल लागत को अनदेखा कर देते हैं।

यह शोध पत्र कम्प्यूटेशनल-सांख्यिकीय रनटाइम (CSR) को संबोधित करता है। लक्ष्य एक रैंडमाइज्ड एल्गोरिदम डिजाइन करना है जो $\epsilon$-एडिटिव एरर इन एक्सपेक्टेशन (expectation) के भीतर $W_2^2(P, Q)$ का अनुमान लगा सके, जहाँ रनटाइम $O(f(\epsilon))$ में नमूनों को एकत्र करने की लागत (प्रति नमूना $O(1)$ मानी गई है) और गणना की लागत दोनों शामिल हैं। लेखक तर्क देते हैं कि लक्षित सटीकता को केवल ग्राउंड ट्रुथ के रूप में प्रायोगिक मापों के बजाय, नमूना आकार द्वारा प्रेरित सांख्यिकीय त्रुटि के अनुरूप होना चाहिए।

कार्यप्रणाली: सैंपल-स्केच-सॉल्व प्रतिमान (Methodology: Sample-Sketch-Solve Paradigm)

लेखक एक तेज़ CSR प्राप्त करने के लिए एक तीन-चरणीय प्रतिमान प्रस्तावित करते हैं, विशेष रूप से $(0, 1)^d$ डोमेन पर होल्डर स्मूथ (Hölder smooth) डेंसिटी वाले वितरणों के लिए:

1. सैंपल (Sample): $P$ और $Q$ से $n$ रैंडम नमूने एकत्र करें ताकि प्रायोगिक माप $\hat{P}_n$ और $\hat{Q}_n$ बन सकें।
2. स्केच (Sketch): इन नमूनों को एक नियमित कार्टेशियन ग्रिड $G_h$ पर मैप करें, जहाँ सेल की चौड़ाई $h = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$ है। ग्रिड सेल के भीतर के सभी द्रव्यमान (mass) को सेल के केंद्र में संकुचित (collapse) कर दिया जाता है। यह संकुचित डिस्क्रीट मेजर $G_h\#\hat{P}_n$ और $G_h\#\hat{Q}_n$ बनाता है।
3. सॉल्व (Solve): एक विशेष एल्गोरिदम का उपयोग करके स्केच किए गए मापों के बीच सटीक वर्ग वासेरस्टीन दूरी की गणना करें जो नियमित ग्रिड संरचना का लाभ उठाता है।

मुख्य तकनीकी घटक (Key Technical Components)

1. ग्रिड-आधारित विवक्तीकरण त्रुटि सीमाएं (Grid-Based Discretization Error Bounds - Section 2)

यह शोध पत्र द्रव्यमान को ग्रिड केंद्रों में संकुचित करने से उत्पन्न होने वाली सन्निकटन त्रुटि (approximation error) पर एक नया ऊपरी बाउंड स्थापित करता है।

• धारणा (Assumption): $P$ और $Q$ में $\alpha$-होल्डर स्मूथ डेंसिटीज़ ($0 < \alpha < 1$) हैं और वे शून्य और अनंत से दूर (bounded away from zero and infinity) हैं।
• परिणाम: लेखक सिद्ध करते हैं कि $|W_2^2(G_h\#P, G_h\#Q) - W_2^2(P, Q)| \leq K h^{1+\alpha}$।
• तंत्र (Mechanism): मानक त्रिकोण असमानता (triangle inequality) वाले तर्क जो $O(h)$ देते हैं, के विपरीत, यह परिणाम मिडपॉइंट नियम (midpoint rule) के समान ब्रेनियर मैप (Brenier map - जो कि ऑप्टिमल ट्रांसपोर्ट मैप है) की नियमितता पर आधारित एक नवीन कपलिंग तर्क का उपयोग करता है। कोलिन्स और टोंग [2025] के ब्रेनियर मैप की ग्लोबल होल्डर निरंतरता के संबंध में हालिया परिणामों का लाभ उठाते हुए, लेखक दिखाते हैं कि प्रथम-क्रम के त्रुटि पद रद्द हो जाते हैं, जिसके परिणामस्वरूप एक अधिक सटीक $O(h^{1+\alpha})$ बाउंड प्राप्त होता है।
• गैर-स्मूथ मामला (Non-Smooth Case): बिना स्मूथनेस धारणाओं वाले वितरणों के लिए, बाउंड $O(h)$ पर वापस आ जाता है, जो मानक त्रिकोण असमानता तर्कों के अनुरूप है।

2. नियमित ग्रिड पर कुशल सटीक गणना (Efficient Exact Computation on Regular Grids - Section 3)

एक बार जब डेटा को एक नियमित ग्रिड पर स्केच कर दिया जाता है, तो समस्या की संरचना सटीक गणना को काफी तेज़ बना देती है।

• संरचना: स्केच किए गए माप $L$ विभाजनों वाले ग्रिड पर समर्थित (supported) हैं, जहाँ प्रत्येक एटम (atom) का भार $1/n$ का गुणक है। ग्राउंड कॉस्ट (वर्ग यूक्लिडियन दूरी) आयामों के पार सेपरेबल (separable) है।
• रिडक्शन (Reduction): लेखक सेपरेबल कॉस्ट वाले $d$-आयामी हिस्टोग्राम के बीच ऑप्टिमल ट्रांसपोर्ट समस्या को एक $(d+1)$-पार्टाइट ग्राफ पर मिनिमम-कॉस्ट फ्लो समस्या में बदलने के लिए ऑरिकियो एट अल. [2018] के रिडक्शन का उपयोग करते हैं।
• एल्गोरिदम: डिमांड, कैपेसिटी और कॉस्ट को इंटीग्रल बनाने के लिए समस्या को स्केल करके, वे वैन डेन ब्रैंड एट अल. [2023] के डिटरमिनिस्टिक सटीक मिनिमम-कॉस्ट फ्लो एल्गोरिदम को लागू करते हैं।
• जटिलता (Complexity): स्केच पर सटीक गणना $\tilde{O}(L^{d+1+o(1)})$ समय में चलती है।

3. संश्लेषण: CSR एल्गोरिदम (Synthesis: The CSR Algorithm - Section 4)

अंतिम एल्गोरिदम सांख्यिकीय सैंपलिंग, ग्रिड स्केचिंग और फास्ट सॉल्वर को जोड़ता है।

• नमूना आकार (Sample Size): $n$ को सांख्यिकीय त्रुटि और विवक्तीकरण त्रुटि (discretization error) के बीच संतुलन बनाने के लिए चुना जाता है, जो आमतौर पर $n = \tilde{O}(\epsilon^{-\max(2, d/2)})$ होता है।
• ग्रिड रेजोल्यूशन (Grid Resolution): ग्रिड का आकार $L = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$ निर्धारित किया जाता है।
• कुल रनटाइम (Total Runtime): संयुक्त रनटाइम सॉल्वर स्टेप द्वारा डोमिनेट होता है, जिससे निम्नलिखित CSR प्राप्त होता है:
  $$\tilde{O}\left(\epsilon^{-\max\left(2, \frac{d+1+o(1)}{1+\alpha}\right)}\right)$$

मुख्य परिणाम और योगदान (Key Results and Contributions)

1. स्मूथ वितरणों के लिए बेहतर रनटाइम

शोध पत्र प्रदर्शित करता है कि $\alpha$-होल्डर स्मूथ वितरणों के लिए, CSR लगभग इष्टतम हो सकता है, जो विशिष्ट व्यवस्थाओं में सांख्यिकीय निचली सीमा (statistical lower bound) $\Omega(\epsilon^{-2})$ से मेल खाता है:

• आयाम $d=2$: $\alpha > 1/2$ के लिए, एल्गोरिदम $\tilde{O}(\epsilon^{-2})$ प्राप्त करता है। यह इष्टतम सांख्यिकीय दर से मेल खाता है, जिसका अर्थ है कि कम्प्यूटेशनल लागत पर्याप्त नमूने एकत्र करने की लागत से अधिक नहीं है।
• आयाम $d=3$: जैसे-जैसे $\alpha \to 1$ (लिप्सचिट्ज़ स्मूथनेस), रनटाइम $\tilde{O}(\epsilon^{-2})$ के करीब पहुँच जाता है। सामान्य $0 < \alpha < 1$ के लिए, रनटाइम $\tilde{O}(\epsilon^{-\frac{4}{1+\alpha}})$ है।
• सामान्य आयाम $d$: रनटाइम $\tilde{O}(\epsilon^{-\max(2, \frac{d+1}{1+\alpha})})$ है।

2. पूर्व कार्य के साथ तुलना

लेखक तालिका 2 में अपने परिणामों की तुलना मौजूदा विधियों से करते हैं:

• एम्पिरिकल प्लग-इन + लहन एट अल. [2019]: $d=2$ में $\tilde{O}(\epsilon^{-4})$ और $d=3$ में $\tilde{O}(\epsilon^{-5})$ प्राप्त करता है।
• एंट्रोपिक OT / सिंकहॉर्न (Sinkhorn) (चिज़त एट अल. [2020]): $d=2$ और $d=3$ में $\tilde{O}(\epsilon^{-6})$ प्राप्त करता है।
• यह कार्य: $d=2$ (के लिए $\alpha > 1/2$) में $\tilde{O}(\epsilon^{-2})$ और $d=3$ (के लिए $\alpha \to 1$) में $\tilde{O}(\epsilon^{-2})$ प्राप्त करता है।

3. गैर-स्मूथ मामला (Non-Smooth Case)

स्मूथनेस धारणाओं की अनुपस्थिति में ($\alpha \to 0$), विधि $\tilde{O}(\epsilon^{-\max(2, d+1)})$ का CSR प्रदान करती है। $d=2$ के लिए, यह $\tilde{O}(\epsilon^{-3})$ है, और $d=3$ के लिए, यह $\tilde{O}(\epsilon^{-4})$ है।

महत्व और दावे (Significance and Claims)

लेखक दावा करते हैं कि उनका प्राथमिक योगदान सैंपल-स्केच-सॉल्व प्रतिमान है, जो सफलतापूर्वक सांख्यिकीय अनुमान त्रुटि को कम्प्यूटेशनल जटिलता से अलग (decouple) करता है।

• त्रुटि के बिना संपीड़न (Compression without Error): लेखक दिखाते हैं कि नमूनों को एक नियमित ग्रिड पर मैप करना डेटा को संकुचित करता है बिना एसिम्प्टोटिक एरर (asymptotic error) को बढ़ाए, बशर्ते कि अंतर्निहित वितरण स्मूथ हों।
• गति के लिए रेगुलराइजेशन (Regularization for Speed): ग्रिड संरचना समस्या को रेगुलराइज़ करती है, जिससे फास्ट सटीक फ्लो एल्गोरिदम का उपयोग संभव होता है जो सामान्य डिस्क्रीट पॉइंट सेट्स के लिए अव्यवहार्य (intractable) होते हैं।
• इष्टतमता (Optimality): यह कार्य तर्क देता है कि कम आयामों ($d=2, 3$) में पर्याप्त स्मूथ वितरणों के लिए, $\epsilon^{-2}$ की इष्टतम सांख्यिकीय दर को कम्प्यूटेशनल रूप से प्राप्त करना संभव है। यह इस धारणा को चुनौती देता है कि वासेरस्टीन दूरी की गणना करने के लिए स्वाभाविक रूप से सुपर-लीनियर या सुपर-क्वाड्रेटिक रनटाइम की आवश्यकता होती है।

लेखक स्पष्ट रूप से कहते हैं कि उनके परिणाम इस धारणा पर निर्भर करते कि $P$ और $Q$ एक सीमित डोमेन (विशेष रूप से $(0, 1)^d$) पर समर्थित हैं और उनमें होल्डर स्मूथ डेंसिटीज हैं। वे यह दावा नहीं करते कि ये परिणाम बिना संशोधन के गैर-स्मूथ वितरणों या अनबाउंडेड डोमेन तक विस्तारित होते हैं। महत्व इस बात में निहित है कि यह सांख्यिकीय अनुमान सिद्धांत और कम्प्यूटेशनल ऑप्टिमल ट्रांसपोर्ट के बीच की खाई को पाटता है, यह प्रदर्शित करता है कि यथार्थवादी स्मूथनेस धारणाओं के तहत, "कम्प्यूटेशनल बॉटलनेक" को प्रभावी ढंग से हटाया जा सकता है।