🔢 mathematics

Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

यह शोध पत्र सटीक फलन मानों (exact function values) के लिए $\Omega(d^2/\log d)$ का एक नियर-क्वाड्रेटिक निचला स्तर (near-quadratic lower bound) स्थापित करके डेरिवेटिव-मुक्त उत्त럴 अनुकूलन (derivative-free convex optimization) की नियतात्मक क्वेरी जटिलता (deterministic query complexity) में एक लंबे समय से चले आ रहे अंतराल को भरता है, जिससे यह पॉलीलॉगैरिद्मिक कारकों (polylogarithmic factors) तक सर्वोत्तम ज्ञात ऊपरी सीमा (upper bound) से मेल खाता है और मिश्रित-पूर्णांक सेटिंग्स (mixed-integer settings) तक परिणाम का विस्तार करता है।

मूल लेखक: Phillip Kerger

प्रकाशित 2026-07-16

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

CC BY 4.0

मूल लेखक: Phillip Kerger

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

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। आप जमीन को देख नहीं सकते, और आपके पास कोई मानचित्र भी नहीं है। आपके पास एकमात्र उपकरण एक जादुई सेंसर है, जिसे जब आप जमीन पर रखते हैं, तो वह उस विशिष्ट स्थान पर सटीक ऊंचाई बताता है। आप जितनी जल्दी हो सके घाटी के तल तक पहुँचना चाहते हैं। लेकिन आप ढलान या पहाड़ी की दिशा नहीं देख सकते; आपको केवल एक संख्या मिलती है: "यहाँ, यह 100 फीट ऊँचा है।" यह डेरिवेटिव-फ्री ऑप्टिमाइज़ेशन (derivative-free optimization) की दुनिया है। विज्ञान और इंजीनियरिंग में, हम अक्सर ऐसी समस्याओं का सामना करते हैं जहाँ हम यह गणना नहीं कर सकते कि कोई सिस्टम कैसे बदलता है (वह "डेरिवेटिव" या ढलान जिसे हम जानते हैं), क्योंकि वह सिस्टम एक 'ब्लैक बॉक्स' है, एक जटिल सिमुलेशन है, या एक भौतिक प्रयोग है। हमें परीक्षण और त्रुटि (trial and error) पर निर्भर रहना पड़ता है, यह पूछते हुए कि "अगर मैं ऐसा करूँ तो क्या होगा?" और फिर एक सटीक उत्तर प्राप्त करना पड़ता है।

दशकों से, गणितज्ञ इस बात पर बहस कर रहे हैं कि इन "ऊंचाई की जाँचों" में से वास्तव में कितने की आवश्यकता है ताकि तल को खोजने की गारंटी दी जा सके। यदि आप ढलान (किस दिशा में नीचे है?) के बारे में भी पूछ पाते, तो आप बहुत जल्दी तल तक पहुँच सकते थे। लेकिन यदि आपको केवल ऊंचाई पूछने की अनुमति है, तो नियम बदल जाते हैं। अब तक, हमारी समझ में एक बड़ा अंतर था। कुछ स्मार्ट एल्गोरिदम ने सुझाव दिया था कि आपको बहुत बड़ी संख्या में जाँचों की आवश्यकता होगी (लगंतु आयामों के वर्ग के बराबर), जबकि सबसे अच्छे सैद्धांतिक प्रमाण ने कहा था कि आपको केवल आयामों के बराबर संख्या की आवश्यकता होगी। यह ऐसा था जैसे एक समूह कह रहा हो, "आपको फुटबॉल के मैदान के हर एक वर्ग इंच की जाँच करनी होगी," और दूसरा समूह कह रहा हो, "आपको केवल कुछ ही जगहों की जाँच करनी होगी।" यह पेपर इस विवाद को सुलझाने के लिए आया है, यह सिद्ध करते हुए कि "फुटबॉल के मैदान" वाला अनुमान "कुछ स्थानों" वाले विचार की तुलना में सच्चाई के बहुत करीब है।

पेपर, जिसका शीर्षक "Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization" है, फिलिप केरगर द्वारा लिखा गया है, और यह ठीक इसी पहेली को सुलझाता है। लेखक, उन्नत AI उपकरणों की महत्वपूर्ण मदद से, यह सिद्ध करते हैं कि जब आप एक नॉनस्मूथ, बाउल-शेप्ड (nonsmooth, bowl-shaped) फलन (विशेष रूप से, एक ऐसा फलन जो चपटे, रैखिक टुकड़ों से मिलकर बना है) के न्यूनतम मान को खोजने के लिए केवल सटीक ऊंचाई मानों (कोई ढलान नहीं) का उपयोग करने के लिए प्रतिबंधित हैं, तो आप पहले से सोचे गए विचार की तुलना में बहुत अधिक काम करने के लिए मजबूर हैं। विशेष रूप से, यह पेपर एक नया, बहुत मजबूत निचला स्तर (lower bound) स्थापित करता है: आपको आवश्यक जाँचों की संख्या आयामों के वर्ग (गणितीय रूप से $\tilde{\Omega}(d^2)$ के रूप में लिखा गया) के साथ बढ़ती है, न कि केवल रैखिक रूप से।

इसे समझने के लिए, सोचिए कि "आयाम" (dimensions) वे नॉब्स (knobs) हैं जिन्हें आपको एक मशीन पर घुमाना है। यदि आपके पास 10 नॉब्स हैं, तो पुराने, कमजोर प्रमाण ने सुझाव दिया था कि आपको शायद केवल 10 या 20 सेटिंग्स की जाँच करने की आवश्यकता होगी। नया प्रमाण दिखाता है कि, सबसे खराब स्थिति में, आपको वास्तव में सैकड़ों या हज़ारों सेटिंग्स की जाँच करने की आवश्यकता हो सकती है (लगभग $10^2$ या अधिक)। लेखक एक चतुर "एडवर्सरियल" (adversarial) परिदृश्य का निर्माण करते हैं जहाँ एक चालाक कंप्यूटर प्रोग्राम (ओरेकल) आपके सवालों का जवाब इस तरह देता है कि वह आपको लंबे समय तक भ्रमित रखता है। प्रत्येक उत्तर से वास्तव में कितनी जानकारी मिलती है, इसका सावधानीपूर्वक विश्लेषण करके, यह पेपर प्रदर्शित करता है कि "स्लोप-फ्री" (ढलान-रहित) विधि स्वाभाविक रूप से "स्लोप-अवेयर" (ढलान-सचेत) विधि की तुलना में बहुत धीमी है।

यह पेपर इस खोज को एक अधिक जटिल परिदृश्य तक विस्तारित करता है जिसे मिक्स्ड-इंटिजर ऑप्टिमाइज़ेशन (mixed-integer optimization) कहा जाता है। कल्पना कीजिए कि आपकी घाटी में न केवल निरंतर नॉब्स (जैसे वॉल्यूम डायल) हैं, बल्कि स्विच भी हैं जिन्हें केवल चालू या बंद किया जा सकता है (जैसे लाइट स्विच)। पेपर सिद्ध करता है कि, समस्या को खोजने की कठिनाई गुणा हो जाती है: यदि आपके पास $n$ स्विच और $d$ डायल हैं, तो आपको आवश्यक जाँचों की संख्या लगभग $2^n \times d^2$ तक बढ़ जाती है। इसका मतलब है कि केवल कुछ स्विच जोड़ने से समस्या डायल की द्विघात (quadratic) कठिनाई के ऊपर, घातांकीय (exponentially) रूप से कठिन हो जाती है।

महत्वपूर्ण बात यह है कि यह पेपर केवल अनुमान नहीं लगाता है; यह एक कठोर गणितीय प्रमाण प्रदान करता है। यह इस संभावना को खारिज करता है कि कोई चतुर, नियतात्मक (deterministic) एल्गोरिदम केवल सटीक मानों का उपयोग करके इस द्विघात बाधा को जादू से पार कर सकता है। लेखक ने यह सुनिश्चित करने के लिए कि तर्क सही है, औपचारिक सत्यापन सॉफ्टवेयर (एक ऐसा टूल जो गणितीय प्रमाणों की लाइन-दर-लाइन जाँच करता है) का उपयोग किया, और उन्होंने खुले तौर पर स्वीकार किया कि आधुनिक AI ने इस प्रमाण की खोज में प्रमुख भूमिका निभाई। परिणाम 1996 से खुले गणितीय ज्ञान के अंतर को भर देता है, यह दिखाते हुए कि जब आप अपनी समस्या की ढलानों के प्रति अंधे होते हैं, तो आपको वास्तव में अतिरिक्त समय और प्रयास के रूप में इसकी कीमत चुकानी पड़ती है।

तकनीकी सारांश: डेरिवेटिव-मुक्त उत्तरोत्तर अनुकूलन (Derivative-Free Convex Optimization) में ऑरेकल-जटिलता अंतराल को पाटना

समस्या विवरण
यह शोध पत्र एक $d$ -आयामी यूक्लिडियन बॉल ( $B_d$ ) पर एक उत्तल (convex), 1-लिप्सचिट्ज़ (1-Lipschitz) फलन को न्यूनतम करने के लिए नियतात्मक क्वेरी जटिलता (deterministic query complexity) की जांच करता है, जिसमें केवल सटीक फलन मानों (शून्य-क्रम ऑरेकल) का उपयोग किया जाता है। यह अध्ययन $\varepsilon = \Theta(d^{-1/2})$ की सटीकता पर, एक $\varepsilon$ -अनुमानित समाधान खोजने के लिए आवश्यक मूल्यांकनों की बदที่สุด (worst-case) संख्या पर केंद्रित है।

इस कार्य से पूर्व, इस सेटिंग के साहित्य में एक महत्वपूर्ण बहुपद अंतराल (polynomial gap) मौजूद था:

निम्नतम सीमा (Lower Bound): सबसे अच्छा ज्ञात निम्नतम सीमा $\Omega(d)$ थी, जो अधिक शक्तिशाली प्रथम-क्रम ऑरेकल (जहाँ सबग्रेड उपलब्ध होते हैं) से विरासत में मिली थी।
उच्चतम सीमा (Upper Bound): प्रोटासॉफ (1996) की नियतात्मक विधि को समान सटीकता प्राप्त करने के लिए $O(d^2 \log^2 d)$ मूल्यांकनों की आवश्यकता थी।

केंद्रित प्रश्न यह है कि क्या अवकलज (derivative) जानकारी की कमी मौलिक रूप से आयाम $d$ में रैखिक से द्विघातीय (quadratic) जटिलता को बढ़ा देती है, या क्या $\Omega(d)$ सीमा सटीक है।

कार्यप्रणाली
लेखक एक "कठिन परिवार" (hard family) के फलनों और एक "प्रतिरोधी ऑरेकल" (resisting oracle) का निर्माण करते हैं ताकि एक निकट-द्विघातीय निम्नतम सीमा स्थापित की जा सके। प्रमाण चार मुख्य घटकों के माध्यम से आगे बढ़ता है:

कठिन फलन परिवार: लेखक एक फलन वर्ग $f_W(x, z) = \max_{i \in [m]} \{ ax_i + \langle w_i, z \rangle \}$ को परिभाषित करते हैं, जहाँ $m = d/2$ , $x, z \in \mathbb{R}^m$ , और पंक्तियों $w_i$ के वेक्टर $\tau = \Theta(m^{-1/2})$ त्रिज्या वाले एक छोटे बॉल में हैं। ये फलन उत्तल और 1-लिप्सचिट्ज़ हैं। इन फलनों के न्यूनतमीकरण (minimizers) रैखिक टुकड़ों को परिभाषित करने वाले वेक्टर्स के उत्तल आवरण (convex hull) पर मूल बिंदु (origin) के यूक्लिडियन प्रोजेक्शन द्वारा निर्धारित होते हैं।
सटीक प्रतिरोधी ऑरेकल: एक एकल फलन प्रदान करने के बजाय, विरोधी (adversary) एक "आयताकार" अनिश्चितता सेट $P_1 \times \dots \times P_m$ बनाए रखता है, जहाँ प्रत्येक $P_i$ , पंक्ति वेक्टर्स $w_i$ के संभावित सेट का एक कॉम्पैक्ट उत्तल सेट है। इनवेरिएंट (invariant) यह है कि पंक्तियों के सेटों से किसी भी चयन से उत्पन्न होने वाला फलन क्वेरी प्रतिक्रियाओं के संपूर्ण इतिहास के अनुरूप होता है।
- जब एल्गोरिदम एक बिंदु पर क्वेरी करता है, तो विरोधी प्रत्येक पंक्ति सेट पर क्वेरी द्वारा परिभाषित एफाइन फंकशनल्स (affine functionals) का विश्लेषण करता है।
- यदि कोई पंक्ति गैर-स्थिर (non-constant) है, तो विरोधी सेट को एक हाइपरप्लेन द्वारा काट देता है (आयाम को 1 से कम करता है) लेकिन यह सुनिश्चित करता है कि शेष सेट अपने आंतरिक आयतन (intrinsic volume) के एक महत्वपूर्ण अंश को बनाए रखे।
- यदि सभी प्रासंगिक पंक्तियाँ स्थिर हैं, तो विरोधी बिना आयाम कम किए स्थिर मान लौटाता है।
कुल चौड़ाई और अविभेद्यता (Aggregate Width and Indistinguishability): प्रमाण सभी पंक्ति सेटों में कुल कोडायमेंशन (codimension) और आंतरिक आयतन के लॉगरिदमिक नुकसान को ट्रैक करता है। $T = O(m^2 / \log m)$ क्वेरी के बाद, विश्लेषण दिखाता है कि एक रैखिक संख्या में पंक्ति सेट उच्च-आयामी रहते हैं और उनका सामान्यीकृत आयतन बड़ा रहता है। उरीसन की असमानता (Urysohn's inequality) और औसत तर्क का उपयोग करते हुए, लेखक एक एकल दिशा $\theta$ की पहचान करते हैं जिसमें इन शेष सेटों की कुल चौड़ाई बड़ी है।
न्यूनतमों का पृथक्करण (Separation of Minimizers): दिशा $\theta$ में पंक्ति सेटों के चरम बिंदुओं (extreme points) को चुनने के लिए, विरोधी दो अलग-अलग फलन $f_{W^+}$ और $f_{W^-}$ का निर्माण करता है, जो एल्गोरिदम के लिए अविभेद्य (indistinguishable) हैं (वे समान ट्रांसक्रिप्ट उत्पन्न करते हैं)। हालाँकि, प्रोजेक्शन के "लगभग-समान" बेरसेंट्रिक संरचना (बैरसेंट्रिक स्ट्रक्चर - लेम्मा 8) के कारण, पंक्तियों का कुल विस्थापन इन दो फलनों के अद्वितीय न्यूनतमों को एक स्थिर दूरी द्वारा अलग कर देता है। फलस्वरूप, एल्गोरिदम का कोई भी एकल आउटपुट कम से कम एक फलन के वास्तविक न्यूनतम से दूर होना चाहिए, जिसके परिणामस्वरूप $\Omega(d^{-1/2})$ की त्रुटि होती है।

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

निकट-द्विघातीय निम्नतम सीमा: प्राथमिक परिणाम (प्रमेय 1) स्थापित करता है कि सटीकता $\varepsilon = \Theta(d^{-1/2})$ के लिए, नियतात्मक सटीक-मान जटिलता $\tilde{\Omega}(d^2)$ है। विशेष रूप से, ऐसे स्थिरांक मौजूद हैं कि:
$c \frac{d^2}{\log(d+1)} \leq Q_{\text{val}}^{\text{det}}\left(d, \frac{\varepsilon_0}{\sqrt{d}}\right) \leq C d^2 \log^2(d+1)$
यह धर्मी (polylogarithmic) कारकों तक निम्नतम और उच्चतम सीमाओं के बीच के अंतर को पाट देता है, यह सिद्ध करता है कि केवल सटीक मान पूर्ण प्रथम-क्रम जानकारी की तुलना में काफी कम सूचनात्मक हैं (जो $\Theta(d)$ है)।
मिश्रित-पूर्णांक विस्तार (Mixed-Integer Extension): बासु आदि से एक ट्रांसफर प्रमेय का उपयोग करते हुए, लेखक इस परिणाम को $n$ बाइनरी और $d$ निरंतर चरों वाले मिश्रित-पूर्णांक उत्तल अनुकूलन तक विस्तारित करते हैं। वे सिद्ध करते हैं कि जटिलता पूर्णांक आयाम के साथ गुणात्मक रूप से बढ़ती है:
$Q_{\text{MI,val}}^{\text{det}}(n, d, \varepsilon) = \tilde{\Theta}(2^n d^2)$
यह तब भी लागू होता है जब क्वेरी उत्पाद डोमेन में मनमाने भिन्नात्मक बिंदुओं पर की जाती है।
औपचारिक सत्यापन (Formal Verification): लेखक गणितीय तर्कों को विकसित करने में AI उपकरणों (GPT-5.6 Sol Pro) के व्यापक उपयोग को स्वीकार करते हैं। कठोरता सुनिश्चित करने के लिए, वे Lean प्रोग्रामिंग भाषा का उपयोग करके $\tilde{\Omega}(d^2)$ निम्नतम सीमा प्रमाण का औपचारिक सत्यापन प्रदान करते हैं।

महत्व और दावे

लेख दावा करता है कि यह 1996 से चले आ रहे जटिलता अंतराल को हल करता है। इसका महत्व शोर रहित (noiseless), सटीक-वास्तविक सेटिंग में सबग्रेड जानकारी की कमी की लागत को अलग करने में निहित है। लेखक इस बात पर जोर देते हैं कि यह पृथक्करण सीमित परिशुद्धता या मेमोरी बाधाओं का परिणाम नहीं है, बल्कि सटीक वास्तविक प्रतिक्रियाओं बनाम प्रथम-क्रम ऑरेकल से प्राप्त सूचना की अंतर्निहित विशेषता है।

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

लेखक निम्नतम और उच्चतम सीमाओं के बीच शेष लॉगरिदमिक कारकों के संबंध में विनम्र बने रहते हैं और नोट करते हैं कि वर्तमान कठिन परिवार एक विशिष्ट गहराई ( $\Theta(d^{-1/2})$ ) पर निर्भर करता है, जिससे आयाम-मुक्त सटीकता सीमा और चिकनाई (smoothness) जैसे अतिरिक्त नियमितता धारणाओं के तहत व्यवहार के प्रश्न खुले रह जाते हैं।

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