2025-11-24T00:19:17.738116

Overlap Gap and Computational Thresholds in the Square Wave Perceptron

Benedetti, Bogdanov, Malatesta et al.
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional limit at a fixed constraint density $α= O(1)$. In this work, we examine two key aspects of these models. The first is related to the so-called \emph{overlap-gap property}, that is a disconnectivity feature of the geometry of the solution space of combinatorial optimization problems proven to cause the failure of a large family of solvers, and conjectured to be a symptom of algorithmic hardness. We identify, both in the storage and in the teacher-student settings, the emergence of an overlap gap at a threshold $α_{\mathrm{OGP}}(δ)$, which can be made arbitrarily small by suitably increasing the frequency of oscillations $1/δ$ of the activation. This suggests that in this small-$δ$ regime, typical instances of the problem are hard to solve even for small values of $α$. Second, in the teacher-student setup, we show that the recovery threshold of the planted signal for message-passing algorithms can be made arbitrarily large by reducing $δ$. These properties make SWPs both a challenging benchmark for algorithms and an interesting candidate for cryptographic applications.
academic

वर्गीय तरंग परसेप्ट्रॉन में ओवरलैप गैप और कम्प्यूटेशनल थ्रेशहोल्ड

मूल जानकारी

  • पेपर ID: 2506.05197
  • शीर्षक: वर्गीय तरंग परसेप्ट्रॉन में ओवरलैप गैप और कम्प्यूटेशनल थ्रेशहोल्ड
  • लेखक: मार्को बेनेडेट्टी, एंड्रेज बोगडानोव, एनरिको एम. मलातेस्ता, मार्क मेजर्ड, जियानमार्को पेरुपाटो, एलोन रोसेन, निकोलाज आई. श्वार्ट्सबैक, रिकार्डो जेकिना
  • वर्गीकरण: cond-mat.dis-nn (संघनित पदार्थ - विकृत प्रणालियाँ और तंत्रिका नेटवर्क)
  • प्रकाशन समय: 13 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2506.05197

सारांश

वर्गीय तरंग परसेप्ट्रॉन (SWP) दोलनशील सक्रियण फलन वाले तंत्रिका नेटवर्क मॉडल का एक वर्ग है, जो निश्चित बाधा घनत्व α = O(1) के साथ उच्च-आयामी सीमा में दिलचस्प "कठोरता" विशेषताएं प्रदर्शित करता है। यह अनुसंधान इन मॉडलों के दो महत्वपूर्ण पहलुओं की जांच करता है: पहला, ओवरलैप-गैप गुण (overlap-gap property), जो समाधान स्थान की ज्यामिति का एक असंबद्ध विशेषता है, जिसे कई समाधानकर्ताओं की विफलता का कारण माना गया है और एल्गोरिथ्मिक कठोरता का संकेत माना जाता है; दूसरा, शिक्षक-छात्र सेटिंग में, संदेश-पारण एल्गोरिथ्म की पुनर्प्राप्ति थ्रेशहोल्ड δ को कम करके मनमाने ढंग से बड़ी हो सकती है। ये विशेषताएं SWP को एल्गोरिथ्मिक चुनौतियों के लिए एक बेंचमार्क और क्रिप्टोग्राफिक अनुप्रयोगों के लिए एक दिलचस्प उम्मीदवार दोनों बनाती हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

यह अनुसंधान परसेप्ट्रॉन समस्या की कम्प्यूटेशनल जटिलता पर केंद्रित है, विशेष रूप से सांख्यिकीय भौतिकी और सैद्धांतिक कंप्यूटर विज्ञान के अंतर्विभागीय क्षेत्र में कठोरता विश्लेषण पर। परसेप्ट्रॉन सबसे बुनियादी तंत्रिका नेटवर्क मॉडल के रूप में, इसकी सीखने और भंडारण समस्याएं अधिक जटिल तंत्रिका नेटवर्क की कम्प्यूटेशनल सीमाओं को समझने में महत्वपूर्ण हैं।

मूल समस्याएं

  1. सांख्यिकीय-कम्प्यूटेशनल अंतराल: कई बाधा संतुष्टि समस्याओं में, सूचना-सैद्धांतिक रूप से व्यवहार्य पैरामीटर क्षेत्र और ज्ञात बहुपद-समय एल्गोरिथ्म के कार्य करने वाले क्षेत्र के बीच एक अंतराल मौजूद है
  2. ज्यामितीय कठोरता विशेषताएं: समाधान स्थान की ज्यामितीय संरचना एल्गोरिथ्मिक कम्प्यूटेशनल जटिलता को कैसे प्रभावित करती है
  3. ओवरलैप-गैप गुण: एल्गोरिथ्मिक कठोरता के भविष्यवाणी संकेतक के रूप में ज्यामितीय असंबद्धता

अनुसंधान प्रेरणा

  • मौजूदा द्विआधारी परसेप्ट्रॉन (जैसे ABP, SBP) हालांकि सांख्यिकीय-कम्प्यूटेशनल अंतराल प्रदर्शित करते हैं, लेकिन उनकी कठोरता थ्रेशहोल्ड अपेक्षाकृत निश्चित है
  • एक ऐसा मॉडल आवश्यक है जो कठोरता विशेषताओं को समायोजित कर सके ताकि एल्गोरिथ्मिक विफलता के ज्यामितीय कारणों को बेहतर ढंग से समझा जा सके
  • चरम कठोरता विशेषताओं वाले मॉडलों की क्रिप्टोग्राफी में अनुप्रयोग संभावना का अन्वेषण

मूल योगदान

  1. वर्गीय तरंग परसेप्ट्रॉन मॉडल का परिचय: दोलनशील सक्रियण फलन φ_δ(h) = -sgn(sin(πh/δ)) के साथ एक नया परसेप्ट्रॉन मॉडल प्रस्तावित किया गया है
  2. ओवरलैप-गैप थ्रेशहोल्ड विश्लेषण: भंडारण और शिक्षक-छात्र सेटिंग में ओवरलैप-गैप थ्रेशहोल्ड α_OGP(δ) की पहचान की गई, जो दोलन आवृत्ति 1/δ को बढ़ाकर मनमाने ढंग से छोटा किया जा सकता है
  3. चरम कठोरता विशेषताएं: δ→0 सीमा में, किसी भी α>0 के लिए ओवरलैप-गैप मौजूद है, यह दर्शाता है कि बहुत छोटे बाधा घनत्व पर भी समस्या कठिन है
  4. पुनर्प्राप्ति थ्रेशहोल्ड की समायोजनशीलता: शिक्षक-छात्र सेटिंग में, यह दर्शाया गया है कि संदेश-पारण एल्गोरिथ्म की पुनर्प्राप्ति थ्रेशहोल्ड δ को कम करके मनमाने ढंग से बड़ी हो सकती है
  5. क्रिप्टोग्राफिक अनुप्रयोग संभावना: परसेप्ट्रॉन-आधारित क्रिप्टोग्राफिक निर्माणों (जैसे टकराव-प्रतिरोधी हैश फलन) के लिए सैद्धांतिक आधार प्रदान किया गया है

विधि विवरण

कार्य परिभाषा

भंडारण समस्या

डेटा सेट D = {(x^μ, y^μ)}^P_{μ=1} दिया गया है, वजन वेक्टर w ∈ {-1,+1}^N खोजें जैसे कि:

y^μ = φ(1/√N · w · x^μ) ∀μ ∈ [P]

जहाँ x^μ_i ~ N(0,1) स्वतंत्र और समान रूप से वितरित, y^μ = ±1 समान संभावना के साथ यादृच्छिक।

शिक्षक-छात्र समस्या

एक "शिक्षक" वजन w* ∈ {-1,+1}^N मौजूद है, लेबल शिक्षक द्वारा उत्पन्न:

y^μ = φ(1/√N · w* · x^μ) ∀μ ∈ [P]

लक्ष्य शिक्षक वजन को पुनः प्राप्त करना या कोई भी समाधान खोजना है।

मॉडल आर्किटेक्चर

वर्गीय तरंग सक्रियण फलन

φ_δ(h) = -sgn(sin(πh/δ))

यह सक्रियण फलन अवधि T = 2δ रखता है, पैरामीटर δ के माध्यम से दोलन आवृत्ति को नियंत्रित करता है।

फूरियर प्रतिनिधित्व

φ_δ(h) = -4/π ∑_{n=0}^∞ 1/(2n+1) sin((2n+1)πh/δ)

ओवरलैप-गैप गुण विश्लेषण

m-OGP परिभाषा

दिए गए उदाहरण D के लिए, समुच्चय S_m(q,ε,D) को परिभाषित करें जिसमें सभी m कॉन्फ़िगरेशन के समुच्चय {w^1,...,w^m} शामिल हैं, जो संतुष्ट करते हैं:

  1. प्रत्येक w^a बाधा को संतुष्ट करता है
  2. किसी भी a≠b के लिए: q < (w^a·w^b)/N < q+ε

यदि Pr_DS_m(q,ε,D) ≠ ∅ → 0 (N→∞), तो m-OGP गुण मौजूद है।

क्लोन विभाजन फलन

N_m(q;D) = ∑_{w^1,...,w^m} ∏_{a=1}^m X_D(w^a) ∏_{a<b} δ(q - w^a·w^b/N)

अनीलिंग मुक्त एन्ट्रॉपी

φ^{ann}_m(q) = lim_{N→∞} 1/(mN) ln E_D N_m(q;D)

तकनीकी नवाचार बिंदु

  1. समायोजनशील कठोरता: पैरामीटर δ के माध्यम से समस्या की कम्प्यूटेशनल कठोरता को निरंतर समायोजित करना, δ→0 पर चरम कठोरता तक पहुंचना
  2. ज्यामितीय विश्लेषण: समाधान स्थान की ज्यामितीय संरचना का विश्लेषण करने के लिए सांख्यिकीय भौतिकी विधि का उपयोग
  3. बहु-स्तरीय विश्लेषण: विभिन्न सटीकता के साथ सैद्धांतिक भविष्यवाणी प्रदान करने के लिए अनीलिंग सन्निकटन और प्रतिकृति समरूपता विश्लेषण को संयोजित करना
  4. छोटे δ सीमा का विश्लेषणात्मक उपचार: सूक्ष्म विस्तार के माध्यम से सीमा स्थिति का सटीक विश्लेषण

प्रायोगिक सेटअप

सैद्धांतिक विश्लेषण विधि

  • अनीलिंग गणना: OGP थ्रेशहोल्ड के ऊपरी सीमा अनुमान प्रदान करता है
  • प्रतिकृति समरूपता (RS) विश्लेषण: अधिक सटीक मुक्त एन्ट्रॉपी गणना
  • छोटे δ विस्तार: δ→0 सीमा के लिए सूक्ष्म विश्लेषण

संख्यात्मक प्रयोग

  • प्रणाली आकार: N = 4000-5000
  • नमूना संख्या: प्रत्येक डेटा बिंदु के लिए औसतन 80 स्वतंत्र नमूने
  • एल्गोरिथ्म परीक्षण: प्रबलित अनुमानित संदेश-पारण (RAMP) एल्गोरिथ्म का उपयोग

मूल्यांकन मेट्रिक्स

  • संतुष्टि थ्रेशहोल्ड: α_c(δ) - समाधान के अस्तित्व की महत्वपूर्ण बाधा घनत्व
  • OGP थ्रेशहोल्ड: α_OGP(m,δ) - m-ओवरलैप-गैप के प्रकट होने की थ्रेशहोल्ड
  • शिक्षक थ्रेशहोल्ड: α_T(δ) - शिक्षक के अद्वितीय समाधान बनने की थ्रेशहोल्ड
  • एल्गोरिथ्मिक थ्रेशहोल्ड: α_alg(δ) - RAMP एल्गोरिथ्म की विफलता की थ्रेशहोल्ड

प्रायोगिक परिणाम

मुख्य परिणाम

संतुष्टि थ्रेशहोल्ड

  • δ→∞ के लिए, ABP की क्षमता α^{ABP}_c ≈ 0.833 को पुनः प्राप्त करता है
  • δ→0 के लिए, क्षमता ऊपरी सीमा की ओर प्रवृत्त होती है α_c(0) = 1
  • RS अनुमान छोटे δ सीमा में अनीलिंग ऊपरी सीमा के साथ मेल खाता है

ओवरलैप-गैप थ्रेशहोल्ड

δ→0 सीमा में:

α^{ann}_{OGP}(m) = 1/m

इसलिए α_(∞) = 0, जिसका अर्थ है कि किसी भी α > 0 के लिए ओवरलैप-गैप मौजूद है।

शिक्षक-छात्र समस्या परिणाम

  • शिक्षक थ्रेशहोल्ड α_T(δ) δ→0 पर 1 की ओर प्रवृत्त होता है
  • पुनर्प्राप्ति थ्रेशहोल्ड α_r(δ) को δ को कम करके मनमाने ढंग से बड़ा किया जा सकता है
  • विपरीत वेज परसेप्ट्रॉन में पुनर्प्राप्ति थ्रेशहोल्ड का विचलन प्राप्त किया गया है

एल्गोरिथ्मिक प्रदर्शन विश्लेषण

RAMP एल्गोरिथ्म के प्रदर्शन परीक्षण से पता चलता है:

  • एल्गोरिथ्मिक थ्रेशहोल्ड α_alg(δ) δ में कमी के साथ घटता है
  • RS अनुमान की OGP थ्रेशहोल्ड और एल्गोरिथ्मिक थ्रेशहोल्ड के बीच अंतराल मौजूद है
  • δ = 1.5 के लिए, अंतराल शून्य के करीब है, ABP के ज्ञात परिणामों के साथ सामंजस्यपूर्ण है

केस विश्लेषण: विपरीत वेज परसेप्ट्रॉन

सक्रियण फलन को डिजाइन करके:

φ(h) = sgn((h-γ)h(h+γ))

γ = γ* = √(2log2) पर, पुनर्प्राप्ति थ्रेशहोल्ड विचलित होता है:

α_r ≈ (π/8)(log2)^{-3/2} ε^{-1}

जहाँ ε = |γ - γ*|।

संबंधित कार्य

परसेप्ट्रॉन सिद्धांत

  • शास्त्रीय परिणाम: गार्डनर-डेरिडा की भंडारण क्षमता विश्लेषण
  • द्विआधारी परसेप्ट्रॉन: ABP और SBP मॉडल की कठोरता विशेषताएं
  • सांख्यिकीय-कम्प्यूटेशनल अंतराल: बंसल-स्पेंसर एल्गोरिथ्म और सूचना-सैद्धांतिक सीमा के बीच अंतर

ओवरलैप-गैप गुण

  • परिभाषा और विकास: गामर्निक-जादिक की मूल परिभाषा
  • एल्गोरिथ्मिक विफलता प्रमाण: स्थिर एल्गोरिथ्म वर्गों के लिए सार्वभौमिक परिणाम
  • अनुप्रयोग उदाहरण: यादृच्छिक ग्राफ, संतुष्टि समस्याएं आदि

सांख्यिकीय भौतिकी विधि

  • प्रतिकृति विधि: विभाजन फलन और चरण संक्रमण की गणना
  • ज्यामितीय चरण संक्रमण: समाधान स्थान समूहन संरचना में परिवर्तन
  • संदेश-पारण: BP और AMP एल्गोरिथ्म का सैद्धांतिक विश्लेषण

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. चरम कठोरता: SWP δ→0 सीमा में चरम कम्प्यूटेशनल कठोरता प्रदर्शित करता है, किसी भी सकारात्मक बाधा घनत्व पर ओवरलैप-गैप मौजूद है
  2. समायोजनशीलता: पैरामीटर δ के माध्यम से समस्या की कठोरता विशेषताओं को निरंतर समायोजित किया जा सकता है
  3. क्रिप्टोग्राफिक संभावना: ये विशेषताएं SWP को क्रिप्टोग्राफिक अनुप्रयोगों के लिए एक शक्तिशाली उम्मीदवार बनाती हैं
  4. ज्यामितीय समझ: दोलनशील सक्रियण फलन समाधान स्थान की कनेक्टिविटी को तोड़ता है, जिससे एल्गोरिथ्मिक विफलता होती है

सीमाएं

  1. प्रतिकृति समरूपता: RS विश्लेषण कुछ पैरामीटर क्षेत्रों में अनुचित हो सकता है, उच्च-क्रम प्रतिकृति समरूपता-विभंजन की आवश्यकता है
  2. परिमित आकार प्रभाव: सैद्धांतिक विश्लेषण ऊष्मागतिकीय सीमा पर आधारित है, वास्तविक परिमित प्रणाली में विचलन हो सकता है
  3. एल्गोरिथ्मिक सीमा: केवल RAMP एल्गोरिथ्म का परीक्षण किया गया है, अन्य एल्गोरिथ्म का प्रदर्शन अभी तक अनुसंधान की प्रतीक्षा में है
  4. पैरामीटर निर्भरता: परिणाम δ पैरामीटर की पसंद पर दृढ़ता से निर्भर हैं

भविष्य की दिशाएं

  1. पूर्ण RSB विश्लेषण: संपूर्ण प्रतिकृति समरूपता-विभंजन सिद्धांत विकसित करना
  2. अन्य एल्गोरिथ्म: वर्णक्रमीय विधि, SDP शिथिलीकरण आदि अन्य एल्गोरिथ्म वर्गों का परीक्षण
  3. क्रिप्टोग्राफिक कार्यान्वयन: SWP पर आधारित ठोस क्रिप्टोग्राफिक प्रोटोकॉल विकसित करना
  4. सामान्यीकरण: अन्य दोलनशील सक्रियण फलनों की समान विशेषताओं का अनुसंधान

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक नवाचार: दोलनशील सक्रियण फलनों की कम्प्यूटेशनल कठोरता का पहली बार व्यवस्थित अध्ययन, नई सैद्धांतिक दृष्टिकोण प्रदान करता है
  2. विधि कठोरता: सांख्यिकीय भौतिकी और सैद्धांतिक कंप्यूटर विज्ञान विधियों को संयोजित करके, व्यापक और गहन विश्लेषण
  3. परिणाम गहराई: समायोजनशील कठोरता की नई तंत्र की खोज, एल्गोरिथ्मिक सीमाओं को समझने के लिए महत्वपूर्ण
  4. अनुप्रयोग संभावना: क्रिप्टोग्राफी के लिए नई सैद्धांतिक उपकरण प्रदान करता है

कमियां

  1. तकनीकी जटिलता: विश्लेषण विधि काफी जटिल है, परिणामों की पहुंच को सीमित कर सकता है
  2. प्रायोगिक सत्यापन: मुख्य रूप से सैद्धांतिक विश्लेषण पर निर्भर, संख्यात्मक प्रयोग अपेक्षाकृत सीमित हैं
  3. व्यावहारिकता: चरम पैरामीटर (δ→0) के तहत वास्तविक कार्यान्वयन की संभावना संदिग्ध है
  4. सामान्यीकरण: परिणामों की सार्वभौमिकता और अन्य समस्याओं पर प्रयोज्यता को आगे सत्यापन की आवश्यकता है

प्रभाव

  1. सैद्धांतिक योगदान: कम्प्यूटेशनल जटिलता सिद्धांत के लिए नई विश्लेषण उपकरण और दृष्टिकोण प्रदान करता है
  2. अंतर-विषय मूल्य: सांख्यिकीय भौतिकी, मशीन लर्निंग और क्रिप्टोग्राफी को जोड़ता है
  3. प्रेरणा महत्व: ज्यामितीय कठोरता पर अधिक अनुसंधान को प्रेरित कर सकता है
  4. व्यावहारिक संभावना: क्रिप्टोग्राफी और एल्गोरिथ्म डिजाइन में अनुप्रयोग संभावना है

प्रयोज्य परिदृश्य

  1. सैद्धांतिक अनुसंधान: कम्प्यूटेशनल जटिलता सिद्धांत और सांख्यिकीय भौतिकी अनुसंधान
  2. एल्गोरिथ्म विश्लेषण: संदेश-पारण एल्गोरिथ्म की सीमा और विफलता तंत्र को समझना
  3. क्रिप्टोग्राफिक डिजाइन: कठोरता धारणा पर आधारित नई क्रिप्टोग्राफिक आदिम विकसित करना
  4. मशीन लर्निंग: तंत्रिका नेटवर्क प्रशिक्षण की कम्प्यूटेशनल बाधाओं को समझना

संदर्भ

पेपर 75 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से शामिल हैं:

  1. रोसेनब्लैट (1958): परसेप्ट्रॉन की मूल परिभाषा
  2. गार्डनर और डेरिडा (1989): परसेप्ट्रॉन भंडारण क्षमता के शास्त्रीय परिणाम
  3. गामर्निक और जादिक (2019): ओवरलैप-गैप गुण की परिभाषा
  4. बाल्डासी एट अल. (2015): द्विआधारी परसेप्ट्रॉन की एल्गोरिथ्मिक थ्रेशहोल्ड विश्लेषण
  5. मेजर्ड और मोंटानारी (2009): सांख्यिकीय भौतिकी विधि का व्यवस्थित परिचय

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