🤖 machine learning

Parameterized Complexity of $L_p$ -Lipschitz Constants for Input Convex Neural Networks and $L_p$ -Norm Maximization over Zonotopes

यह शोध पत्र यह सिद्ध करके एक खुली समस्या का समाधान करता है कि दो-परत वाले इनपुट-कॉन्वेक्स न्यूरल नेटवर्क के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक (Lipschitz constants) की गणना करना और ज़ोनोटोप्स (zonotopes) पर $L_p$ -मानों को अधिकतम करना, सभी निश्चित परिमेय $p \in (1, \infty)$ के लिए आयाम के संबंध में W[1]-कठिन (W[1]-hard) है, जिससे एक्सपोनेंशियल टाइम हाइपोथीसिस (Exponential Time Hypothesis) के तहत ब्रूट-फोर्स एन्यूरेशन (brute-force enumeration) की इष्टतमता स्थापित होती है।

मूल लेखक: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla

प्रकाशित 2026-08-26

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

CC BY 4.0

मूल लेखक: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla

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

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

हाल ही में इन प्रणालियों को अधिक स्थिर और विश्लेषण करने में आसान बनाने के तरीके के रूप में एक विशिष्ट प्रकार के नेटवर्क, जिसे 'इनपुट-कॉन्वेक्स न्यूरल नेटवर्क' कहा जाता है, प्रस्तावित किया गया था। इन नेटवर्कों में, नियम अधिक सख्त हैं: परतों के बीच के कनेक्शनों को गैर-ऋणात्मक (non-negative) होना अनिवार्य है, जो यह गारंटी देता है कि नेटवर्क गणितीय रूप से एक अनुमानित, कॉन्वेक्स तरीके से व्यवहार करेगा। यह प्रतिबंध एक आशाजनक शॉर्टकट जैसा लग रहा था। संवेदनशीलता के कुछ प्रकार के मापों के लिए, इस प्रतिबंध ने वास्तव में समस्या को उचित समय में हल करने योग्य बना दिया। हालांकि, मानक दूरी गणनाओं से जुड़े एक व्यापक और महत्वपूर्ण वर्ग के मापों के लिए, यह एक खुला प्रश्न बना हुआ था कि क्या यह वास्तुशिल्प संबंधी प्रतिबंध इस समस्या को आसानी से हल करने के लिए पर्याप्त था, या कठिनाई बनी रहेगी।

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

शोधकर्ताओं ने इस समस्या को एक ज्यामितीय आकार में अनुवादित करके इस समस्या के करीब पहुँचने का प्रयास किया जिसे 'ज़ोनोटोप' (zonotope) कहा जाता है। आप ज़ोनोटोप की कल्पना एक बहु-आयामी ब्लॉक के रूप में कर सकते हैं जो कई छोटे रेखा खंडों को एक साथ जोड़कर बनाया गया है। नेटवर्क कितना संवेदनशील है, यह सवाल इस ब्लॉक के केंद्र से इसके किनारे तक खींची जा सकने वाली सबसे लंबी संभव रेखा खोजने का प्रश्न बन जाता है। जबकि लंबी रेखा खोजना कुछ आकृतियों के लिए आसान है और कुछ प्रकार के दूरी मापों के लिए आसान है, शोधकर्ताओं ने पाया कि इन नेटवर्कों के लिए प्रासंगिक विशिष्ट मापों के लिए, यह समस्या आयामों (dimensions) की संख्या बढ़ने के साथ तेजी से कठिन होती जाती है।

इसे सिद्ध करने के लिए, टीम ने कंप्यूटर विज्ञान की एक प्रसिद्ध, अत्यंत कठिन पहेली—'मल्टीकलर्ड क्लीक' (Multicolored Clique) समस्या—से जुड़ी तार्किक कड़ियों का एक श्रृंखला बनाई। यह पहेली पूछती है कि क्या आप विभिन्न समूहों से एक विशिष्ट संख्या में वस्तुओं को इस प्रकार चुन सकते हैं कि चुनी गई प्रत्येक जोड़ी आपस में जुड़ी हो। शोधकर्ताओं ने दिखाया कि यदि आप उनके ज्यामितीय आकारों में सबसे लंबी रेखा को जल्दी से खोज सकते हैं, तो आप इस कठिन पहेली को भी जल्दी हल कर सकते हैं। चूंकि कंप्यूटर वैज्ञानिक व्यापक रूप से मानते हैं कि इस पहेली को जल्दी हल नहीं किया जा सकता, इसलिए यह निहितार्थ है कि इन आकारों में सबसे लंबी रेखा को जल्दी से नहीं खोजा जा सकता। उन्होंने दो अलग-अलग गणितीय निर्माणों का उपयोग करके इस संबंध को प्रदर्शित किया, जिनमें से एक मौलिक तकनीकों पर आधारित था और दूसरा गहरे ज्यामितीय अंतर्दृष्टि पर, जो दोनों एक ही निष्कर्ष की ओर ले गए।

अध्ययन ने आगे यह अन्वेषण किया कि दूरी के मापन के प्रकार को बदलने पर यह कठिनाई कैसे बदलती है। हालांकि कुछ मापों के लिए समस्या पहले से ही कठिन थी, लेकिन यह स्पष्ट नहीं था कि क्या यह गणित और इंजीनियरिंग में उपयोग किए जाने वाले अन्य मानक मापों की एक विस्तृत श्रृंखला के लिए भी कठिन बनी रहती है। टीम ने सिद्ध किया कि यह कठिनाई प्रत्येक निश्चित प्रकार के मानक दूरी मापन के लिए सत्य है। उन्होंने यह दिखाकर इसे प्राप्त किया कि एक प्रकार के मापन के लिए उपयोग किए जाने वाले ज्यामितीय आकारों को बिना मूल कठिनाई खोए दूसरे प्रकार के आकारों में परिवर्तित किया जा सकता है। इसका अर्थ है कि इन समस्याओं को हल करने में बाधा किसी एक मापन पद्धति की विचित्रता नहीं है, बल्कि इसमें शामिल ज्यामिति का एक मौलिक गुण है।

आर्टिफिशियल इंटेलिजेंस की सुरक्षा और डिजाइन के भविष्य के लिए इस कार्य के निहितार्थ महत्वपूर्ण हैं। यह स्पष्ट करता है कि केवल एक न्यूरल नेटवर्क को इनपुट-कॉन्वेक्स बनाना एक 'सिल्वर बुलेट' नहीं है जो इसके व्यवहार के सभी पहलुओं को सत्यापित करना आसान बना दे। जबकि ये नेटवर्क आउटपुट को कॉन्वेक्स सुनिश्चित करने के लिए उपयोगी हैं, वे स्वचालित रूप से यह गणना करने की क्षमता प्रदान नहीं करते हैं कि वे छोटी त्रुटियों या हमलों के प्रति कितने संवेदनशील हैं। शोधकर्ताओं ने यह भी उल्लेख किया कि उनके निष्कर्ष यह सुझाव देते हैं कि वैज्ञानिकों द्वारा वर्तमान में उपयोग की जाने वाली 'ब्रूट-फोर्स' विधियाँ—हर संभावित परिदृश्य की जाँच करना—वर्तमान धारणाओं के तहत हम जो सर्वश्रेष्ठ उम्मीद कर सकते हैं, वही हैं। कोई छिपा हुआ शॉर्टकट नहीं है जो इन गणनाओं को बड़े नेटवर्कों पर तेजी से करने की अनुमति दे सके।

अपने शोध पत्र में एक अनूठे योगदान में, लेखकों ने अपनी शोध प्रक्रिया पर भी विचार किया, और स्वीकार किया कि उन्होंने अपने प्रमाणों के लिए प्रारंभिक विचार उत्पन्न करने में मदद के लिए आर्टिफिशियल इंटेलिजेंस उपकरणों का उपयोग किया। उन्होंने बताया कि कैसे एआई ने तकनीकी रूप से सही लेकिन स्पष्टता और सहज समझ की कमी वाले कच्चे गणितीय तर्क प्रदान किए। मानव शोधकर्ताओं ने उन तर्कों को परिष्कृत करने, अनावश्यक जटिलता को हटाने और उस ज्यामितीय अंतर्दृष्टि को उजागर करने में काफी समय बिताया जिसने प्रमाण को विश्वसनीय और स्पष्ट बनाया। उन्होंने तर्क दिया कि जबकि एआई विचारों को उत्पन्न करने के लिए एक शक्तिशाली उपकरण हो सकता है, उन विचारों को समझने योग्य, वैचारिक रूप से सुसंगत गणित में ढालने के लिए मानवीय भूमिका अपरिहार्य बनी हुई है। उनका कार्य इस विचार का प्रमाण है कि एआई के युग में, मानवीय अंतर्दृष्टि का मूल्य केवल उत्तर खोजने में नहीं, बल्कि उन्हें इस तरह समझाने में है जो अंतर्निहित सत्य को प्रकट करे।

तकनीकी सारांश: इनपुट कॉनवेक्स न्यूरल नेटवर्क के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक की पैरामीट्रिक जटिलता और ज़ोनोटोप्स पर $L_p$ -नॉर्म मैक्सिमाइजेशन

समस्या विवरण
यह शोध पत्र दो-परत वाले इनपुट कॉनवेक्स न्यूरल नेटवर्क (ICNN) के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक (Lipschitz constant) निर्धारित करने की कम्प्यूटेशनल जटिलता को संबोधित करता है, जिनमें ReLU एक्टिवेशन का उपयोग किया गया है। एक ICNN एक प्रतिबंधित आर्किटेक्चर है जहाँ आउटपुट वेट्स गैर-ऋणात्मक (nonnegative) होते हैं, जो यह सुनिश्चित करते हैं कि गणना की गई फलन (function) उत्तल (convex) है। जबकि सामान्य ReLU नेटवर्क के लिए सटीक $L_p$ -लिप्सचिट्ज़ स्थिरांक की गणना करना ज्ञात है कि $d$ इनपुट आयाम के सापेक्ष NP-hard और W[1]-hard है, ICNNs के लिए $p \in (1, \infty)$ हेतु इसकी जटिलता खुली हुई थी। विशेष रूप से, यह अज्ञात था कि क्या ICNN तक सीमित करना इस समस्या को फिक्स्ड-पैरामीटर ट्रैक्टेबल (FPT) या बहुपद-समय (polynomial-time) समाधान योग्य बनाता है, जो $L_1$ और $L_\infty$ के लिए ज्ञात स्थिति के विपरीत है।

पूर्व कार्य में स्थापित द्वैतता (duality) के माध्यम से, एक दो-परत वाले ReLU ICNN के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक की गणना करना, नेटवर्क के वेट्स द्वारा जनरेट किए गए ज़ोनोटोप (zonotope) पर $L_q$ -नॉर्म (जहाँ $1/p + 1/q = 1$ ) को अधिकतम करने के तुल्य है। फलस्वरूप, यह शोध पत्र $\mathbb{R}^d$ में ज़ोनोटोप्स पर $L_p$ -नॉर्म मैक्सिमाइजेशन समस्या पर ध्यान केंद्रित करता है, $p \in (1, \infty) \cap \mathbb{Q}$ के लिए।

कार्यप्रणाली
लेखक मल्टीकलर क्लीक (Multicolored Clique) समस्या से पैरामीट्रिक रिडक्शन के माध्यम से हार्डनेस परिणाम स्थापित करते हैं, जो क्लीक आकार $k$ के सापेक्ष W[1]-hard है। कार्यप्रणाली तीन मुख्य चरणों में आगे बढ़ती है:

ज़ोनोटोप्स पर $L_2^2$ -Max के लिए रिडक्शन:
लेखक $d = O(k)$ आयाम में एक ज़ोनोटोप पर वर्गित $L_2$ -नॉर्म ( $L_2^2$ -Max) को अधिकतम करने की समस्या से मल्टीकलर क्लीक से दो अलग-अलग रिडक्शन प्रदान करते हैं।
- स्पष्ट रिडक्शन (2k+1 आयाम): यह निर्माण एक जनरेटर मैट्रिक्स को परिभाषित करने के लिए मौलिक तकनीकों का उपयोग करता है। यह नोड्स के चयन को एनकोड करने के लिए $L_2$ -यूनिट सर्कल पर वेक्टर्स (लेम्मा 4.1 से व्युत्पन्न) पर आधारित एक "गैजेट" का उपयोग करता है। रिडक्शन यह सुनिश्चित करता है कि एक उच्च $L_2^2$ -नॉर्म तभी प्राप्त होता है जब चयनित नोड्स एक क्लीक बनाते हैं। "नोड" और "एज" जनरेटर्स को सावधानीपूर्वक संतुलित करके आयाम को $k$ के रैखिक (linear) रखा गया है।
- गैर-स्पष्ट रिडक्शन (2k आयाम): यह दृष्टिकोण एक सेंट्रली सिमेट्रिक ज़ोनोटोप के सपोर्ट फंक्शन का उपयोग करता है। यह एक फलन $F = V + \eta E$ का निर्माण करता है जहाँ $V$ (नोड टर्म) वैध नोड चयन से विचलन को दंडित करता है और $E$ (एज टर्म) आसन्न नोड जोड़ों को पुरस्कृत करता है। एज टर्म को एक इंटरपोलेशन परिणाम (प्रपोजिशन 4.4) पर आधारित एक लीनियर प्रोग्राम को हल करके गैर-स्पष्ट रूप से निर्मित किया गया है, जो विशिष्ट दिशाओं में सपोर्ट फंक्शन के लिए मान निर्धारित करने की अनुमति देता है। यह रिडक्शन $2k$ का एक कड़ा (tighter) आयाम प्राप्त करता है।
$L_p^p$ -Max ( $p \in (1, \infty)$ के लिए स्थानांतरण):
$L_2^2$ से किसी भी $L_p^p$ तक हार्डनेस को विस्तारित करने के लिए, लेखक एक ज्यामितीय एम्बेडिंग तकनीक का उपयोग करते हैं। वे एक एफाइन मैप $\Phi_\varepsilon(x) = \mathbf{1} + \varepsilon Jx$ के माध्यम से मूल ज़ोनोटोप $Z(A)$ को उच्च-आयामी स्थान में एम्बेड करते हैं। यहाँ $Jx = (x, -x)$ है। यह ज़ोनोटोप को ऑल-वन्स वेक्टर पर $L_p$ -स्फीयर के एफाइन टेंजेंट हाइपरप्लेन में रखता है। टेलर एप्रोक्सिमेशन (लेम्मा 5.1) का उपयोग करते हुए, वे दिखाते हैं कि पर्याप्त छोटे $\varepsilon$ के लिए, एम्बेडेड पॉइंट्स का $L_p^p$ -नॉर्म, मूल $L_2^2$ -नॉर्म के आनुपातिक एक पद के साथ एक स्थिरांक को अनुमानित करता है। यह मल्टीकलर क्लीक समस्या के "हाँ" और "नहीं" उदाहरणों के बीच के अंतर को बनाए रखता है।
$L_p$ -Max में स्थानांतरण:
चूंकि $L_p$ -Max के लिए थ्रेशोल्ड परिमेय (rational) होना चाहिए, इसलिए लेखक केवल $L_p^p$ थ्रेशोल्ड का $p$ -वाँ मूल (root) नहीं ले सकते (जो अपरिमेय हो सकता है)। इसके बजाय, वे $L_p^p$ रिडक्शन द्वारा स्थापित सकारात्मक अंतराल का उपयोग करके एक परिमेय थ्रेशोल्ड $T$ की गणना करते हैं जो "नहीं" और "हाँ" बाउंड्स के $p$ -वें मूल के बीच स्थित है (लेम्मा 5.3), जिससे $L_p$ -नॉर्म मैक्सिमाइजेशन समस्या में हार्डनेस स्थानांतरित होती है।

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

W[1]-Hardness: यह शोध पत्र सिद्ध करता है कि प्रत्येक निश्चित $p \in (1, \infty) \cap \mathbb{Q}$ के लिए, $\mathbb{R}^d$ में एक ज़ोनोटोप पर $L_p$ -नॉर्म (और $L_p^p$ -नॉर्म) को अधिकतम करना आयाम $d$ के सापेक्ष W[1]-hard है।
ETH लोअर बाउंड्स: एक्सपोनेंशियल टाइम हाइपोथेसिस (ETH) को मानते हुए, इस समस्या को $N^{o(d)}$ समय में हल नहीं किया जा सकता है, जहाँ $N$ इनपुट बिट-लेंथ है। इसका तात्पर्य है कि ज़ोनोटोप वर्टिसेस का ब्रूट-फोर्स एन्यूमरेशन (जो $O(N^{d-1})$ चलता है) अनिवार्य रूप से इष्टतम (optimal) है।
ICNN निहितार्थ: द्वैतता के माध्यम से, ये परिणाम यह भी दर्शाते हैं कि दो-परत वाले ReLU ICNN के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक की गणना करना भी इनपुट आयाम के सापेक्ष W[1]-hard है और इसमें ETH के तहत कोई सब-एक्सपोनेंशियल टाइम एल्गोरिदम नहीं है।
खुले प्रश्नों का समाधान: यह कार्य COLT 2025 में उठाए गए प्रश्न को हल करता है कि $p \in (1, \infty)$ के लिए ICNN लिप्सचिट्ज़ स्थिरांक और ज़ोनोटोप पर नॉर्म मैक्सिमाइजेशन की पैरामीट्रिक जटिलता क्या है।

महत्व और दावे
यह शोध पत्र दावा करता है कि ReLU नेटवर्क को इनपुट-कन्वेक्स होने के लिए प्रतिबंधित करना $p \in (1, \infty)$ के लिए $L_p$ -लिप्सचिट्ज़ स्थिरांक की गणना करने की समस्या को सुलभ (tractable) नहीं बनाता है, जो $L_1$ और $L_\infty$ के मामलों के विपरीत है। परिणाम प्रदर्शित करते हैं कि इस प्रतिबंधित, उत्तल आर्किटेक्चर के लिए भी "डायमेंशनलिटी का अभिशाप" (curse of dimensionality) बना रहता है।

लेखक स्पष्ट रूप से अपने योगदान को केवल एक हार्डनेस प्रूफ के रूप में नहीं, बल्कि अंतर्निहित गणितीय अंतर्दृष्टि के स्पष्टीकरण के रूप में प्रस्तुत करते हैं। वे नोट करते हैं कि हालांकि $L_2$ और $L_p$ के लिए W[1]-हार्डनेस के स्वतंत्र प्रमाण AI पाइपलाइनों और अन्य समूहों द्वारा उत्पन्न किए गए थे, उनका शोध पत्र रिडक्शन के पीछे के वैचारिक अंतर्ज्ञान के स्पष्ट प्रदर्शन को प्राथमिकता देता है। वे अपने गैर-स्पष्ट रिडक्शन (सपोर्ट फंक्शन और इंटरपोलेशन का उपयोग करके) की ज्यामितीय अंतर्दृष्टि और स्पष्ट गैजेट निर्माण को अपने आप में मूल्यवान योगदान के रूप में रेखांकित करते हैं। यह शोध पत्र AI के युग में एक केस स्टडी के रूप में भी कार्य करता है, जो मशीन-जनित प्रमाणों को पचाने और वैचारिक स्पष्टता एवं कठोर, बोधगम्य प्रदर्शन सुनिश्चित करने के लिए एक "मानवीय परत" (human layer) की वकालत करता है।

इसी तरह के और पेपर