Sharp local sparsity of regularized optimal transport

यहाँ अल्बर्टो गोंज़ालेस-सांज़, ऋषभ एस. ग्वालानी और लुकास कोच के शोध पत्र "Sharp local sparsity of regularized optimal transport" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण और संदर्भ

मुख्य समस्या:
यह शोध पत्र $L_p$-प्रकार के एंट्रॉपी ($p \in (1, 2]$) के साथ नियमित अनुकूलित परिवहन (Regularized Optimal Transport - ROT) की जांच करता है। शास्त्रीय अनुकूलित परिवहन (OT) समस्या के विपरीत, जो दो प्रायिकता मापों $\lambda$ और $\mu$ के बीच एक नियतात्मक मानचित्र (या योजना) खोजती है, ROT लागत फलन (cost function) में एक नियमितीकरण पद (regularization term) जोड़ता है। यह समस्या को पूर्णतः उत्तल (strictly convex) और गणनात्मक रूप से सुलभ बनाता है।

विशिष्ट चुनौती:
जबकि एंट्रोपिक ऑप्टिमल ट्रांसपोर्ट (EOT, $p=1$ के अनुरूप) व्यापक रूप से उपयोग किया जाता है, यह "आयामों के अभिशाप" (curse of dimensionality) से ग्रस्त है और ऐसे परिवहन योजनाओं का उत्पादन करता है जिनका अधिकतम समर्थन (maximal support) होता है (अर्थात घनत्व हर जगह धनात्मक होता है)। इसके विपरीत, $p > 1$ वाले ROT योजनाएँ विरलता (sparsity) प्रदर्शित करती हैं: जैसे-जैसे नियमितीकरण पैरामीटर $\varepsilon \to 0$ होता है, अनुकूलित युग्मन (optimal coupling) $\pi_\varepsilon$ का समर्थन सिकुड़ता जाता है, और यह अन-रेगुलराइज्ड OT योजना $\pi_0$ के समर्थन की ओर अभिसरित होता है।

खुला प्रश्न:
पिछले कार्यों (जैसे, गोंज़ालेस-सांज़ और नुट्ज़, वीसेल और एक्सु) ने यह स्थापित किया कि समर्थन सिकुड़ता है, लेकिन सामान्य बहुभिन्नतीय डेटा (univariate या self-transport मामलों से परे) के लिए इस अभिसरण की सटीक दर (sharp rate of convergence) एक खुला प्रश्न बना हुआ था। लेखक यह निर्धारित करने का लक्ष्य रखते हैं कि परिवहन योजना के समर्थन के खंड (sections) किस ज्यामिति और दर से संकुचित होते हैं।

2. गणितीय सूत्रीकरण

ROT समस्या को इस प्रकार परिभाषित किया गया है:
$$\text{ROT}_{\varepsilon, p} := \inf_{\pi \in \Pi(\lambda, \mu), \pi \ll \lambda \otimes \mu} \left( \int \frac{1}{2}\|x - y\|^2 d\pi + \varepsilon \int h_p\left(\frac{d\pi}{d(\lambda \otimes \mu)}\right) d(\lambda \otimes \mu) \right)$$
जहाँ $h_p(z) = \frac{|z|^p}{p-1}$ (जहाँ $p \in (1, 2]$)।

अनुकूलित योजना $\pi_\varepsilon$ का घनत्व इस प्रकार दिया गया है:
$$\rho_\varepsilon(x, y) = \frac{1}{\varepsilon^{q-1} q^{q-1}} \left( f_\varepsilon(x) + g_\varepsilon(y) - \frac{1}{2}\|x - y\|^2 \right)_+^{q-1}$$
जहाँ $q = \frac{p}{p-1}$ यंग संयुग्मी (Young conjugate) है, और $(\cdot)_+$ धनात्मक भाग को दर्शाता है। $(\cdot)_+$ पद घनत्व को शून्य होने की अनुमति देता है, जिससे विरल समर्थन (sparse support) बनता है।

लेखक एक निश्चित $x$ के लिए समर्थन के खंडों (sections) को परिभाषित करते हैं:
$$S_x = \{ y : \rho_\varepsilon(x, y) > 0 \}$$
लक्ष्य $\varepsilon \to 0$ होने पर $S_x$ के व्यास (diameter) और ज्यामिति को निर्धारित करना है।

3. कार्यप्रणाली और धारणाएँ

धारणाएँ:

• $\lambda$ और $\mu$ कॉम्पैक्ट सपोर्ट $\Omega_0$ और $\Omega_1$ वाले प्रायिकता माप हैं।
• उनके पास शून्य और अनंत से दूर $C^{0, \alpha}$ घनत्व हैं।
• अन-रेगुलराइज्ड OT मानचित्र $T = \nabla \phi$ एक $C^{1, \alpha}$ डिफ़ियोमोर्फिज्म (bi-Lipschitz) है।
• विश्लेषण समर्थन के आंतरिक भाग (interior) पर केंद्रित है ($x \in \text{int}(\Omega_0)$) ताकि सीमा प्रभावों (boundary effects) से बचा जा सके।

प्रमुख तकनीकी उपकरण:

1. उत्तल क्षमताएँ (Convex Potentials): लेखक उत्तल क्षमताओं $\varphi_\varepsilon = \|\cdot\|^2/2 - f_\varepsilon$ और $\psi_\varepsilon = \|\cdot\|^2/2 - g_\varepsilon$ के साथ कार्य करते हैं।
2. समान नियमितता (Uniform Regularity): वे एक पूर्व परिणाम (गोंज़ालेस-सांज़ और कोच, 2026) पर भरोसा करते है जो यह स्थापित करता है कि $\varepsilon \to 0$ होने पर क्षमताओं का हेसियन (Hessian), $\nabla^2 \varphi_\varepsilon$, $L^\infty_{loc}$ में समान रूप से सीमित है।
3. फेन्सेल द्वैतता और ज्यामिति (Fenchel Duality & Geometry): प्रमाण क्षमताओं के उप-विभेदकों (subdifferentials) और $S_x$ की ज्यामिति के बीच संबंध का उपयोग करता है। विशेष रूप से, $S_x$ को एक उत्तल सेट (convex set) के रूप में दिखाया गया है।
4. रेनॉल्ड्स ट्रांसपोर्ट प्रमेय (Reynolds' Transport Theorem): जब एकीकरण का डोमेन ($S_x$) $x$ पर निर्भर करता है, तो क्षमताओं के दूसरे डेरिवेटिव की गणना करने के लिए एक गैर-मानक संस्करण (परिशिष्ट A में) व्युत्पन्न किया गया है।
5. स्केलिंग तर्क (Scaling Arguments):ities): $\varepsilon$ पर निर्भरता निकालने के लिए घनत्व को परिभाषित करने वाले इंटीग्रल्स के सावधानीपूर्वक स्केलिंग में प्रमाण शामिल है।

4. प्रमुख योगदान और परिणाम

A. शार्प लोकल स्पार्सिटी (उपपत्ति 3.1)

मुख्य परिणाम समर्थन खंड $S_x$ की ज्यामिति को स्पष्ट करता है। किसी भी कॉम्पैक्ट उपसमुच्चय $K_0$ के लिए, जो $\Omega_0$ के ठीक अंदर है, एक स्थिरांक $R_0$ मौजूद है कि छोटे $\varepsilon$ के लिए:
$$B\left(\nabla \varphi_\varepsilon(x), \frac{1}{R_0} \varepsilon^{\frac{1}{d(p-1)+2}}\right) \subset S_x \subset B\left(\nabla \varphi_\varepsilon(x), R_0 \varepsilon^{\frac{1}{d(p-1)+2}}\right)$$
महत्व:

• समर्थन खंड $\nabla \varphi_\varepsilon(x)$ के चारों ओर गोलों (balls) की तरह व्यवहार करते हैं।
• त्रिज्या $\varepsilon^{\frac{1}{d(p-1)+2}}$ के रूप में स्केल होती है।
• यह दर (rate) टोरस (torus) पर एक स्पष्ट निर्माण के माध्यम से सिद्ध की गई है कि यह शार्प (sharp) है (इसे सुधारा नहीं जा सकता)।
• यह पिछले यूनिवैरिएट परिणामों और सेल्फ-ट्रांसपोर्ट ($\lambda = \mu$) तक सीमित परिणामों को सामान्यीकृत करता है।

B. यूनिफॉर्म स्ट्रॉन्ग कॉनवेक्सिटी (उपपत्ति 3.2)

लेखक सिद्ध करते हैं कि नियमित क्षमताएँ $\varphi_\varepsilon$ समर्थन के आंतरिक भाग के कॉम्पैक्ट उपसमुच्चयों पर समान रूप से स्ट्रॉन्गली कॉनवेक्स (uniformly strongly convex) हैं।
$$\inf_{\|h\|=1} \langle \nabla^2 \varphi_\varepsilon(x) h, h \rangle \geq \frac{1}{C}$$
यह गुण परिवहन मानचित्र की स्थिरता और संख्यात्मक योजनाओं की सुव्यवस्थितता (well-posedness) सुनिश्चित करने के लिए महत्वपूर्ण है।

C. परिवहन मानचित्र की अभिसरण दरें (उपपत्ति 3.3)

यह शोध पत्र नियमित परिवहन मानचित्र $\nabla \varphi_\varepsilon$ के अन-रेगुलराइज्ड OT मानचित्र $\nabla \phi$ के अभिसरण की दर को निर्धारित करता है:
$$\|\nabla \varphi_\varepsilon - \nabla \phi\|_{L^2(K_0)} \leq C \varepsilon^{\frac{1}{d(p-1)+2}}$$
यह मात्रात्मक रूप से बताता है कि नियमित समाधान $L^2$ नॉर्म में वास्तविक अनुकूलित परिवहन मानचित्र का कितनी तेज़ी से अनुमान लगाता है।

5. स्पष्ट सत्यापन (अनुभाग 6)

व्युत्पन्न दरों की शार्पनेस (sharpness) को प्रदर्शित करने के लिए, लेखक फ्लैट टोरस पर सेल्फ-ट्रांसपोर्ट ($\lambda = \mu = \text{Lebesgue}$) के लिए ROT समस्या को स्पष्ट रूप से हल करते हैं।

• समरूपता (symmetry) के कारण, द्वैत क्षमताएँ (dual potentials) स्थिर होती हैं।
• समर्थन $S_x$ एक जियोडेसिक बॉल (geodesic ball) है जिसकी त्रिज्या $R_\varepsilon$ है।
• मार्जिनल बाधा (marginal constraint) को हल करने से प्राप्त होता है कि $R_\varepsilon \approx \varepsilon^{\frac{1}{d(p-1)+2}}$।
• यह स्पष्ट गणना पुष्टि करती है कि उपपत्ति 3.1 में व्युत्पन्न सैद्धांतिक ऊपरी और निचली सीमाएँ सटीक (tight) हैं।

6. महत्व और प्रभाव

1. सैद्धांतिक प्रगति: यह कार्य उच्च आयामों में $L_p$-रेगुलराइज्ड OT के लिए समर्थन संकुचन (support contraction) की सटीक दर के खुले प्रश्न को हल करता है। यह EOT के "अधिकतम समर्थन" और ROT की "विरल समर्थन" के बीच के अंतर को पाटता है।
2. एल्गोरिद्मिक निहितार्थ: स्पर्सिटी दर को समझना कुशल एल्गोरिदम डिजाइन करने के लिए महत्वपूर्ण है। चूंकि समर्थन $R_\varepsilon \approx \varepsilon^{\frac{1}{d(p-1)+2}}$ त्रिज्या वाले गोले के रूप में सिकुड़ता है, संख्यात्मक विधियाँ इस स्थानीयता (locality) का लाभ उठाकर कम्प्यूटेशनल जटिलता को कम कर सकती हैं, जिससे सघन विधियों (dense methods) के लिए आवश्यक पूर्ण $N \times N$ मैट्रिक्स ऑपरेशन्स से बचा जा सकता है।
3. सामान्यीकरण: परिणाम केवल $p=2$ (क्वाड्रेटिक रेगुलराइजेशन) और सेल्फ-ट्रांसपोर्ट से परे जाते हैं, जो रेगुलराइजेशन फंक्शनों के एक विस्तृत वर्ग और सामान्य माप युग्मों को कवर करते हैं।
4. स्थिरता विश्लेषण: यूनिफॉर्म स्ट्रॉन्ग कॉनवेक्सिटी का प्रमाण ROT समाधानों की स्थिरता के लिए एक सैद्धांतिक आधार प्रदान करता है, जो मशीन लर्निंग और सांख्यिकी में अनुप्रयोगों के लिए आवश्यक है जहाँ डेटा शोरयुक्त (noisy) होता है।

संक्षेप में, यह शोध पत्र एक कठोर ज्यामितीय लक्षण वर्णन प्रदान करता है कि कैसे नियमित अनुकूलित परिवहन योजनाएं जैसे-जैसे रेगुलराइजेशन शून्य की ओर जाता है, वास्तविक अनुकूलित मानचित्र के आसपास केंद्रित होती हैं, जो आयाम $d$ और नियमितीकरण पैरामीटर $p$ पर निर्भर शार्प अभिसरण दरें स्थापित करती है।