A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

तकनीकी सारांश: कंपोजिशनल लर्निंग के लिए एक फंक्शन-स्पेस द्वैत (A Function-Space Dichotomy for Compositional Learning)

समस्या विवरण (Problem Statement)
डीप लर्निंग में एक निरंतर अनुभवजन्य अवलोकन (empirical observation) यह है कि प्रशिक्षित न्यूरल नेटवर्क कंपोजिशनल या पदानुक्रमित (hierarchical) संरचना वाले कार्यों पर अपने न्यूरल टैनजेंट कर्नेल (NTK) की सीमाओं से लगातार बेहतर प्रदर्शन करते हैं। जबकि मौजूदा साहित्य इस कर्नेल-नेटवर्क अंतराल को मुख्य रूप से 'डायमेंशनलिटी के अभिशाप' (curse of dimensionality) के रूप में देखता है (जहाँ कर्नेल उच्च-आयामी इनपुट के निम्न-आयामी प्रोजेक्शन के साथ संघर्ष करते हैं), निश्चित इनपुट आयाम पर इस अंतराल का मात्रात्मक विवरण—विशेष रूप से नेटवर्क की गहराई और कंपोजिशनल संरचना द्वारा संचालित—अनुपलब्ध रहा है। यह शोध पत्र इस प्रश्न को संबोधित करता है: किन लक्ष्यों (targets) पर, और कितनी मात्रा में, NTK उप-इष्टतम (sub-optimal) है, और उस लक्ष्य का कौन सा विशिष्ट गुण कर्नेल को उनका लाभ उठाने से रोकता है?

कार्यप्रणाली और सेटअप (Methodology and Setup)
लेखक इस समस्या का विश्लेषण यूनिट सर्कल $S^1$ पर करते हैं, जहाँ NTK एक स्पष्ट फूरियर विवरण (Fourier description) स्वीकार करता है। वे एक लक्ष्य फलन $f^*$ के लिए दो जटिलता मापों के बीच एक द्वैत (dichotomy) पेश करते हैं:

1. फूरियर जटिलता (Fourier Complexity): यह NTK के माध्यम से सीखने की लागत को नियंत्रित करती है (लेजी रिजीम)। NTK रिप्रोड्यूसिंग कर्नेल हिल्बर्ट स्पेस (RKHS) नॉर्म को सोबोलेव $H^1$ नॉर्म के समतुल्य दिखाया गया है (एक गहराई-निर्भर स्थिरांक तक), जो उच्च-आवृत्ति दोलनों (high-frequency oscillations) को दंडित करता है।
2. आर्किटेक्चरल जटिलता (Architectural Complexity): यह "रिच" रिजीम में वेट-डिके ट्रेनिंग के माध्यम से सीखने की लागत को नियंत्रित करती है। इसे डीप वेरिएशन नॉर्म ($RBV^2_{deep}$) द्वारा मापा जाता है, जो उस न्यूनतम गहराई-$L$, चौड़ाई-$w$ वाले ReLU नेटवर्क के आकार को दर्शाता है जिसकी आवश्यकता लक्ष्य के निर्माण के लिए होती है।

लेखक आर्किटेक्चर क्लास $\mathcal{C}_{L,w,R}$ को गहराई-$L$, चौड़ाई-$w$ वाले ReLU नेटवर्कों के रूप में परिभाषित करते हैं जिनका डीप वेरिएशन नॉर्म $R$ सीमित है। वे NTK एस्टीमेटर (कर्नेल रिज रिग्रेशन) की सैंपल कॉम्प्लेक्सिटी की तुलना इस आर्किटेक्चर क्लास के मिनिमैक्स लोअर बाउंड (minimax lower bound) से करते हैं।

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

1. डीप आर्किटेक्चर क्लासेस का मिनिमैक्स लक्षण वर्णन (Minimax Characterization of Deep Architecture Classes):
   यह शोध पत्र $\mathcal{C}_{L,w,R}$ क्लास के लिए मिनिमैक्स $L^2$ दर स्थापित करता है। यह दर $\Omega(Lw^2R^2/n)$ और $\tilde{O}(L^2w^2R^2/n)$ के बीच निर्धारित की गई है। यह परिणाम एक एकल $L$ कारक तक सटीक (tight) है, जो इस क्लास के लिए किसी भी एस्टीमेटर के सांख्यिकीय फ्लोर (statistical floor) का प्रतिनिधित्व करता है। विशेष रूप से, यह दर लक्ष्य की स्मूथनेस एक्सपोनेंट्स के बजाय आर्किटेक्चरल मापदंडों $(L, w, R)$ द्वारा इंडेक्स की जाती है।

2. घातांकीय NTK उप-इष्टतमता (Exponential NTK Sub-Optimality):
   लेखक सिद्ध करते हैं कि NTK एस्टीमेटर तब घातांकीय रूप से मिनिमैक्स फ्लोर से ऊपर होता है जब लक्ष्य की फूरियर जटिलता और आर्किटेक्चरल जटिलता अलग-अलग (decouple) हो जाती हैं। विशेष रूप से, एक लक्ष्य के लिए जिसकी प्रभावी आवृत्ति $k^*$ है, NTK को $\Omega((k^*)^2)$ नमूनों की आवश्यकता होती है, जबकि आर्किटेक्चर क्लास को अपने संरचनात्मक मापदंडों में केवल बहुपद (polynomial) संसाधनों की आवश्यकता होती है।

• साक्षी (The Witness): डेप्थ-$L$ इटरेटेड सॉटूथ फंक्शन (Telgarsky 2016) एक विश्लेषणात्मक साक्षी के रूप में कार्य करता है। इसे चौड़ाई-2, गहराई-$L$ वाले नेटवर्क के साथ $O(L)$ वेट्स के साथ बनाया जा सकता है (कम आर्किटेक्चरल जटिलता), लेकिन यह $2^{L-1}$ बार दोलन (oscillate) करता है (उच्च फूरियर जटिलता)।
• अंतराल (The Gap): सॉटूथ के लिए, NTK को $\Omega(4^L)$ नमूनों की आवश्यकता होती है, जबकि मिनिमैक्स फ्लोर $L$ के बहुपद में है (बीच में $L^3$ और $L^4$ के)। यह सैंपल कॉम्प्लेक्सिटी में एक घातांकीय अलगाव (exponential separation) प्रदान करता है।

3. अनुभवजन्य सत्यापन (Empirical Validation):
   संख्यात्मक प्रयोग तीन मोर्चों पर सैद्धांतिक दावों की पुष्टि करते हैं:

• NTK स्पेक्ट्रम: $S^1$ पर NTK का आइजनवैल्यू डिके (eigenvalue decay) अनुमानित $k^{-2}$ डिके का अनुसरण करता है, जो "डीप इक्वल्स शैलो" घटना की पुष्टि करता है जहाँ गहराई स्पेक्ट्रल डिके रेट को नहीं बदलती है।
• स्मूथ टारगेट्स: बैंडलिमिटेड (स्मूथ) लक्ष्यों पर, NTK वाइड नेटवर्कों के प्रतिस्पर्धी या उनसे बेहतर है, जिससे कोई घातांकीय अंतराल नहीं दिखता।
• कंपोजिशनल टारगेट्स: हाइपरक्यूब पर स्पार्स पैरिटी मॉडल पर (एक अलग डोमेन जहाँ SGD सफल होता है), एक मानक टू-लेयर नेटवर्क NTK को टेस्ट एरर में चार से छह ऑर्डर ऑफ मैग्नीट्यूड से पीछे छोड़ देता है, जो अनुमानित अलगाव को अंत-से-अंत (end-to-end) साकार करता है।

परिणाम और महत्व (Results and Significance)
यह शोध पत्र निष्कर्ष निकालता है कि NTK और प्रशिक्षित नेटवर्कों के बीच प्रदर्शन का अंतर एक सामान्य "कर्नेल-बनाम-नेटवर्क" घटना नहीं है, बल्कि एक विशिष्ट फंक्शन-स्पेस प्रॉपर्टी है। यह अंतराल लक्ष्य की कंपोजिशनल संरचना (जो कम आर्किटेक्चरल लागत के साथ उच्च-आवृत्ति दोलन उत्पन्न कर सकती है) और कर्नेल के अंतर्निहित स्मूथनेस बायस (जो निम्न-आवृत्ति फलनों को प्राथमिकता देता है) के बीच बेमेल (mismatch) से उत्पन्न होता है।

• सैद्धांतिक अंतर्दृष्टि (Theoretical Insight): यह कार्य बताता है कि गहराई क्यों मदद करती है: यह कंपोजिशन के माध्यम से उच्च-आवृत्ति, दोलनी फलनों को सस्ते में दर्शाने की अनुमति देती है, जो एक ऐसी क्षमता है जिसका NTK (जो एक निश्चित सोबोलेव कर्नेल की तरह व्यवहार करता है) में अभाव है।
• मिनिमैक्स फ्लोर (Minimax Floor): डीप वेरिएशन स्पेस के लिए मिनिमैक्स दर का व्युत्पन्न एक स्टैंडअलोन योगदान के रूप में प्रस्तुत किया गया है, जो आर्किटेक्चरल मापदंडों के आधार पर कंपोजिशनल समस्याओं के लिए सैंपल कॉम्प्लेक्सिटी का सीधा, कर्नेल-मुक्त अनुमान प्रदान करता है।
• दायरा (Scope): लेखक स्पष्ट करते हैं कि अंतराल सार्वभौमिक नहीं है; यह स्मूथ, बैंडलिमिटेड लक्ष्यों के लिए गायब हो जाता है जहाँ फूरियर और आर्किटेक्चरल जटिलताएं संरेखित (aligned) होती हैं। इसके अलावा, वे सांख्यिकीय सीमाओं और एल्गोरिद्मिक व्यवहार्यता के बीच अंतर करते हैं, यह नोट करते हुए कि जबकि सॉटूथ आर्किटेक्चर क्लास द्वारा सांख्यिकीय रूप से सीखने योग्य है, यह ग्रेडिएंट डिसेंट के लिए अनुकूलित करना अत्यंत कठिन है, जबकि स्पार्स पैरिटी सांख्यिकीय और एल्गोरिद्मिक दोनों रूप से सीखने योग्य है।

संक्षेप में, यह शोध पत्र तर्क देता है कि NTK $H^1$-स्मूथ लक्ष्यों के लिए निकट-इष्टतम है, लेकिन उन लक्ष्यों के लिए घातांकीय रूप से उप-इष्टतम है जहाँ कंपोजिशनल संरचना "सस्ते" उच्च-आवृत्ति प्रतिनिधित्व की अनुमति देती है, एक ऐसा क्षेत्र जहाँ रिच-रिजीम ट्रेनिंग सांख्यिकीय रूप से आवश्यक है।