तकनीकी सारांश: ऑनलाइन रियलाइज़ेबल रिग्रेशन और ReLU नेटवर्क के लिए अनुप्रयोग

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

यह शोध पत्र प्रतिकूल (adversarial) परिवेश में रियलाइज़ेबल ऑनलाइन रिग्रेशन की जांच करता है, जहाँ कोई स्टोकेस्टिक धारणा या मार्जिन स्थितियाँ लागू नहीं की जाती हैं। मुख्य समस्या यह निर्धारित करना है कि कब रियलिज़ेबिलिटी (एक लक्ष्य परिकल्पना $h^* \in \mathcal{H}$ का अस्तित्व जो लेबल को पूरी तरह से उत्पन्न करती है) एक होराइजन-फ्री (सीमित) संचयी हानि (cumulative loss) सीमा की ओर ले जाती है, और उन जटिलता मापदंडों की पहचान करना है जो इस सीमा को नियंत्रित करते हैं।

लेखक इसकी तुलना ऑनलाइन वर्गीकरण (classification) से करते हैं, जहाँ साधारण क्लास जैसे कि परसेप्ट्रॉन (Perceptrons) भी बिना मार्जिन धारणाओं के अनंत मिस्टेक बाउंड रख सकते हैं। हालाँकि, रिग्रेशन में, रियलिज़ेबिलिटी मेट्रिक-जैसे लॉस फंक्शन के तहत सीमित कुल हानि (finite total loss) को लागू कर सकती है, भले ही समतुल्य वर्गीकरण समस्या सीखने योग्य न हो। यह अध्ययन उन लॉस फंक्शन $\ell$ पर केंद्रित है जो एक अनुमानित त्रिकोण असमानता (approximate triangle inequality) यानी अनुमानित छद्म-मीट्रिक (approximate pseudo-metrics) को संतुष्ट करते हैं, जो इस स्थिति को रोकने के लिए आवश्यक है जहाँ एक शिक्षार्थी (learner) हाइपोथीसिस स्पेस में बड़े अंतराल के बावजूद नगण्य हानि के साथ मध्यवर्ती लेबल का अनुमान लगा सकता है।

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

यह शोध पत्र स्केल्ड लिटिलस्टोन डायमेंशन ($D_{\text{onl}}$) को ऊपरी सीमा देने के लिए एक जेनेरिक पोटेंशियल मेथड पेश करता है, जो एक अमूर्त डायमेंशन है जिसे अत्तियास एट अल. [2] द्वारा मैक्सिमिन रियलाइज़ेबल संचयी हानि को चरित्रित करने के लिए पेश किया गया था।

एंट्रॉपी पोटेंशियल फ्रेमवर्क (The Entropy Potential Framework)

$D_{\text{onl}}$ की सीधे गणना करने के बजाय (जो कठिन हो सकती है), लेखक इसे प्रेरित सुप (sup) छद्म-मीट्रिक $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$ के तहत हाइपोथीसिस क्लास $\mathcal{H}$ के कवरिंग नंबर्स पर आधारित एक डडली-टाइप एंट्रॉपी इंटीग्रल का उपयोग करके इसे ऊपरी सीमा देते हैं।

1. एंट्रॉपी पोटेंशियल परिभाषा: एक हाइपोथीसिस क्लास $\mathcal{H}$ के लिए जिसका व्यास (diameter) परिमित है, एंट्रॉपी पोटेंशियल को इस प्रकार परिभाषित किया गया है:
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   जहाँ $N(\mathcal{H}, \varepsilon)$ $d_\ell$ के सापेक्ष $\mathcal{H}$ का $\varepsilon$-कवरिंग नंबर है।

2. मुख्य प्रमेय: लेखक सिद्ध करते हैं कि किसी भी $c$-अनुमानित छद्म-मीट्रिक लॉस के लिए, स्केल्ड लिटिलस्टोन डायमेंशन एंट्रॉपी पोटेंशियल द्वारा सीमित है:
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   प्रमाण रियलाइज़ेबल स्केल्ड लिटिलस्टोन पेड़ों पर एक ब्रांच बाउंड तर्क का उपयोग करता है। प्रत्येक नोड पर वर्जन स्पेस (version spaces) का विश्लेषण करके, वे दिखाते हैं कि अनुमानित त्रिकोण असमानता किसी भी $\varepsilon$-कवर को $\gamma$ अंतराल वाले नोड के बच्चों के बीच विभाजित करने के लिए मजबूर करती है जब $\varepsilon < \gamma/(2c)$ हो। विभिन्न पैमानों (scales) पर इस "कवर स्प्लिटिंग" को एकीकृत करने से एक पोटेंशियल ड्रॉप प्राप्त होता है जो गैप के समानुपाती है, जिससे किसी भी ब्रांच के साथ कुल गैप $\Phi(\mathcal{H})$ द्वारा सीमित हो जाता है।

3. निहितार्थ: यदि $\mathcal{H}$ के लिए बहुपद कवरिंग नंबर्स (अर्थात, $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$) हैं, तो $\Phi(\mathcal{H}) < \infty$ होता है, जिसका अर्थ है कि एक होराइजन-फ्री रियलाइज़ेबल संचयी-हानि सीमा मौजूद है।

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

1. $\ell_q$ लॉस के तहत लिप्सचिट्ज़ रिग्रेशन (Lipschitz Regression under $\ell_q$ Loss)

लेखक अपने फ्रेमवर्क को $[-1, 1]^d$ पर $L$-लिप्सचिट्ज़ फलनों की क्लास $\mathcal{H}_L$ पर लॉस $\ell_q(y, y') = |y - y'|^q$ के तहत लागू करते हैं। वे $q$ और आयाम $d$ के बीच संबंध के आधार पर एक तीक्ष्ण चरण संक्रमण (sharp phase transition) स्थापित करते हैं:

• सीखने योग्य क्षेत्र (Learnable Regime) ($q > d$): एंट्रॉपी पोटेंशियल परिमित है। मैक्सिमिन रियलाइज़ेबल संचयी हानि $\Theta_{d,q}(L^d)$ है। लेखक लिप्सचिट्ज़ एनवेलप्स (लोअर और अपर बाउंड्स) पर आधारित एक कुशल नियतात्मक प्रॉपर एल्गोरिदम प्रदान करते हैं जो इस सीमा को प्राप्त करता है।
• असीखने योग्य क्षेत्र (Unlearnable Regime) ($q \leq d$): एंट्रॉपी पोटेंशियल अपसारी (diverge) होता है।
  • यदि $q < d$, तो संचयी हानि क्षितिज (horizon) $T$ के साथ बहुपद रूप से बढ़ती है।
  • यदि $q = d$, तो हानि $T$ के साथ लॉगरिदमिक रूप से बढ़ती है।
  • दोनों ही मामलों में, $D_{\text{onl}}(\mathcal{H}) = \infty$ है।
• अंततः सीखने की क्षमता (Eventual Learnability): किसी भी निरंतर लॉस $\ell$ के लिए जिसमें $\ell(y,y)=0$ है, लेखक दिखाते हैं कि $L$-लिप्सचिट्ज़ फलनों के लिए, तात्कालिक हानि $\ell(\hat{y}_t, y_t)$ जैसे-जैसे $t \to \infty$ होता है, 0 की ओर अभिसरित होती है, चाहे कुल संचयी हानि परिमित हो या न हो।

2. बाउंडेड $k$-ReLU नेटवर्क (Bounded $k$-ReLU Networks)

यह शोध पत्र स्क्वेयर्ड लॉस के साथ $[-1, 1]^d$ पर बाउंडेड $k$-ReLU नेटवर्क ($\mathcal{H}_{k,d}$) की क्लास का अध्ययन करता है।

• रिग्रेशन बनाम वर्गीकरण पृथक्करण (Regression vs. Classification Separation):
  • वर्गीकरण: 0/1 लॉस के तहत, $\mathcal{H}_{2,1}$ (दो हिडन न्यूरॉन्स, 1D इनपुट) के लिए रियलाइज़ेबल ऑनलाइन वर्गीकरण असंभव है, क्योंकि बाउंडेड वेट्स के साथ भी लिटिलस्टोन डायमेंशन अनंत है।
  • रिग्रेशन: स्क्वेयर्ड लॉस के तहत, रियलाइज़ेबल ऑनलाइन रिग्रेशन परिमित कुल हानि को स्वीकार करता है।
• ऊपरी सीमाएँ (Upper Bounds):
  • एक (सूचना-सैद्धांतिक) ऑनलाइन एल्गोरिदम मौजूद है जिसकी संचयी हानि $O(k^2 \log^4 d) = \tilde{O}(k^2)$ है।
  • एक सिंगल ReLU ($k=1$) के लिए, एक कुशल एल्गोरिदम है जिसकी संचयी हानि $O(1)$ है, जो आयाम $d$ से स्वतंत्र है।
• निम्न सीमाएँ (Lower Bounds):
  • $\Omega(k^2 \log(d/k^2))$ की एक निम्न सीमा सिद्ध की गई है, जो दिखाती है कि $k$ और $\log d$ पर निर्भरता आवश्यक है।
• कंप्यूटेशनल हार्डनेस (Computational Hardness):
  • Gap-ETH परिकल्पना को मानते हुए, लेखक $k \geq 2$ के लिए एक कुशल प्रॉपर ऑनलाइन लर्नर के अस्तित्व को खारिज करते हैं जो $d$ के बहुपद समय में संचित हानि $e^{o(d)}$ प्राप्त करता है। यह सुझाव देता है कि जबकि परिमित हानि सूचना-सैद्धांतिक रूप से संभव है, प्रॉपर लर्नर्स के लिए इसे कुशलतापूर्वक गणना करना संभवतः कठिन है।

3. डीप नेटवर्क में सामान्यीकरण (Generalization to Deep Networks)

इन परिणामों को डेप्थ-$L$, विड्थ-$k$ नेटवर्क तक विस्तारित किया गया है। दिखाया गया है कि मैक्सिमिन रियलाइज़ेबल संचयी स्क्वेयर्ड लॉस $\tilde{O}(k^L)$ है, जिसमें $\Omega(k^L \log(d/k^L))$ की मिलान निम्न सीमा है जब $d/k^L \to \infty$ हो।

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

यह शोध पत्र दावा करता है कि रियलिज़ेबिलिटी एग्नोस्टिक सेटिंग की तुलना में ऑनलाइन लर्निंग के परिदृश्य को मौलिक रूप से बदल देती है। विशेष रूप से:

1. जटिलता माप के रूप में मेट्रिक एंट्रॉपी: लेखक स्थापित करते हैं कि अनुमानित छद्म-मीट्रिक के तहत रियलाइज़ेबल रिग्रेशन के लिए, मेट्रिक एंट्रॉपी (एंट्रॉपी पोटेंशियल $\Phi$ के माध्यम से) $D_{\text{onl}}$ के लिए एक पर्याप्त और अक्सर सटीक प्रॉक्सी है। यह उन स्थानों पर सीखने की क्षमता का विश्लेषण करने के लिए एक ठोस, गणना योग्य उपकरण प्रदान करता है जहाँ अमूर्त डायमेंशन कठिन होते हैं।
2. नॉनपैरामीट्रिक रिग्रेशन में चरण संक्रमण: यह कार्य उन सटीक स्थितियों ($q > d$) की पहचान करता है जिनमें नॉनपैरामीट्रिक लिप्सचिट्ज़ रिग्रेशन होराइजन-फ्री होता है, जो वर्गीकरण या $q \leq d$ वाले रिग्रेशन की सीखने की अक्षमता के विपरीत है।
3. न्यूरल नेटवर्क सीखने की क्षमता: यह शोध पत्र ReLU नेटवर्क के लिए वर्गीकरण और रिग्रेशन के बीच एक स्पष्ट अंतर को उजागर करता है। जबकि बाउंडेड ReLU नेटवर्क वर्गीकरण सेटिंग में सीखने के लिए असंभव (अनंत लिटिलस्टोन डायमेंशन) हैं, वे रिग्रेशन सेटिंग में परिमित संचयी हानि को स्वीकार करते हैं। हालाँकि, यह सीखने की क्षमता कुछ शर्तों के साथ आती है: $k \geq 2$ के लिए, प्रॉपर लर्नर्स के माध्यम से इसे कुशलतापूर्वक प्राप्त करना संभवतः कम्प्यूटेशनल रूप से कठिन है।
4. सीमाएँ: लेखक नोट करते हैं कि एंट्रॉपी पोटेंशियल बाउंड हमेशा सटीक नहीं होता है; ऐसे वर्ग मौजूद हैं जहाँ $\Phi(\mathcal{H}) = \infty$ है लेकिन $D_{\text{onl}}(\mathcal{H}) < \infty$ है। अतः, $\Phi$ एक पूर्ण लक्षण वर्णन के बजाय एक स्पष्ट ऊपरी सीमा सरोगेट के रूप में कार्य करता है।

यह कार्य हालिया ऑनलाइन डायमेंशन थ्योरी [2] की प्रगति पर निर्भर करता है और स्टोकैस्टिक प्रक्रियाओं (डडली इंटीग्रल्स) की तकनीकों को एडवर्सरियल ऑनलाइन सेटिंग में अनुकूलित करता है, जो रियलिज़ेबिलिटी धारणा के कारण सीक्वेंशियल चेनिंग के बजाय मानक कवर्स का उपयोग करता है।