🔢 mathematics

Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

यह शोध पत्र द्विघात फलनों के भागफल (quotients) को अनुकूलित करने के लिए एक अनकन्स्ट्रेंड सैंपलिंग-आधारित ज़ीरो-ऑर्डर विधि प्रस्तावित करता है जो विशिष्ट सरोगेट्स के माध्यम से रीमानियन ग्रेडिएंट और हेसियन का अनुमान लगाता है, जिससे एक क्लोज्ड-फॉर्म ऑप्टिमल स्टेप साइज और एक त्वरित एल्गोरिदम सक्षम होता है जो अत्याधुनिक प्रदर्शन प्राप्त करता है।

मूल लेखक: Jonas Bresch

प्रकाशित 2026-04-30

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

CC BY 4.0

मूल लेखक: Jonas Bresch

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

कल्पना कीजिए कि आप एक जटिल, अदृश्य परिदृश्य में सबसे "मजबूत" दिशा खोजने की कोशिश कर रहे हैं। गणित और डेटा साइंस की दुनिया में, यह परिदृश्य संख्याओं के दो विशाल ग्रिडों (मैट्रिक्स) A और B द्वारा परिभाषित होता है। आपका लक्ष्य एक विशिष्ट तीर (एक वेक्टर) खोजना है, जो इन ग्रिडों के माध्यम से गुजरने पर, उस "प्रतिरोध" के सापेक्ष सबसे बड़ा संभव "खिंचाव" पैदा करे जिसका वह सामना करता है।

गणितज्ञ इसे सामान्यीकृत ऑपरेटर नॉर्म (Generalized Operator Norm) कहते हैं। यह कुछ ऐसा पूछने जैसा है: "यदि मैं एक वस्तु को एक फिल्टर (मैट्रिक्स B) के माध्यम से धकेलता हूँ और फिर मापता हूँ कि वह कितनी बड़ी हो जाती है (मैट्रिक्स A), तो वह अधिकतम कितना आकार प्राप्त कर सकती है?"

समस्या: "ब्लैक बॉक्स" का रहस्य

आमतौर पर, इस समस्या को हल करने के लिए आपको इलाके के विस्तृत मानचित्र की आवश्यकता होती है। आपको यह जानने की आवश्यकता है कि पहाड़ियों और घाटियों का सटीक आकार (गणितीय डेरिवेटिव) क्या है ताकि आप जान सकें कि किस दिशा में चलना है।

हालाँकि, कई आधुनिक वास्तविक दुनिया की समस्याओं में (जैसे मौसम का अनुकरण करना या मेडिकल स्कैन का विश्लेषण करना), आपके पास मानचित्र नहीं होता है। आपके पास केवल एक ब्लैक बॉक्स (Black Box) होता है। आप एक तीर अंदर डाल सकते हैं, और बॉक्स आपको परिणाम बताता है, लेकिन आप यह नहीं देख सकते कि वह वहाँ कैसे पहुँचा। आप यह नहीं देख सकते कि पहाड़ी का "ढलान" (slope) या "वक्रता" (curvature) क्या है। इसे जीरो-ऑर्डर (Zeroth-Order) समस्या कहा जाता है। आप अंधेरे में नेविगेट कर रहे हैं, आँखों पर पट्टी बंधी हुई है, और आपके पास केवल एक टॉर्च है जो बताती है कि आप "ऊपर" जा रहे हैं या "नीचे"।

पुराना तरीका: रस्सी पर चलना (Walking on a Tightrope)

अंधेरे में इसे हल करने के लिए पिछले तरीकों ने बहुत सावधानी बरतने की कोशिश की। उन्होंने कहा, "चूंकि हम एक गोले (sphere) पर हैं, इसलिए हम केवल सतह पर ही चल सकते हैं। हमें अपने वर्तमान स्थान पर स्पर्श रेखा (tangent line) यानी एक तंग रस्सी के साथ ही रहना चाहिए।"

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

नया तरीका: "अनकन्स्ट्रेंड" छलांग (The "Unconstrained" Leap)

यह शोध पत्र एक अधिक साहसी और सहज दृष्टिकोण पेश करता है। स्पर्श रेखा (tightrope) तक सीमित रहने के बजाय, लेखक सुझाव देता है कि पूरे गोले पर किसी भी दिशा में कूदें।

इसे इस तरह सोचें:

पुराना तरीका: आप एक पहाड़ी पर खड़े हैं। आप केवल कंटूर लाइन (contour line) के साथ बाएँ या दाएँ पैर खिसकाकर चल सकते हैं।
नया तरीका: आप एक पहाड़ी पर खड़े हैं, और आपको हवा में किसी भी दिशा में एक तीर (dart) फेंकने की अनुमति है। यदि तीर किसी ऐसे स्थान पर गिरता है जो ऊँचा है, तो आप वहाँ पहुँच जाते हैं।

शोध पत्र यह सिद्ध करता है कि भले ही आप "अनकन्स्ट्रेंड" (बिना किसी प्रतिबंध के) कूद रहे हों, फिर भी आप गणितीय रूप से सटीक कदम का आकार (step size) निर्धारित कर सकते हैं। यह एक जादुई कैलकुलेटर होने जैसा है जो आपको बताता है कि उस यादृच्छिक (random) दिशा में ठीक कितनी दूर कूदना है ताकि आप उस विशिष्ट कूद के लिए उच्चतम संभव स्थान पर पहुँच सकें।

"सरोगेट" उपकरण (The "Surrogate" Tools)

चूंकि आप पहाड़ी के ढलान (gradient) या वक्रता (Hessian) को देख नहीं सकते, इसलिए यह शोध पत्र इन यादृच्छिक छलांगों का उपयोग करके सरोगेट उपकरण (अनुमानक) बनाता है:

ग्रेडिएंट एस्टिमेटर (The Gradient Estimator): कुछ यादृच्छिक छलांगें लेकर और यह देखकर कि "स्कोर" में कितना परिवर्तन हुआ, एल्गोरिदम इस बात का अनुमान लगाता है कि "ऊपर" जाने का रास्ता कौन सा है।
कर्वचर एस्टिमेटर (The Quasi-Newton Step): यह सबसे चतुर हिस्सा है। एल्गोरिदम न केवल दिशा का अनुमान लगाता है; यह यह भी अनुमान लगाता है कि पहाड़ी कितनी "घुमावदार" है। यह इलाके के आकार का एक मानसिक मॉडल बनाने के लिए समीकरणों की एक प्रणाली का उपयोग करता है। यह इसे बहुत बड़े और स्मार्ट कदम उठाने की अनुमति देता है, विशेष रूप से जब यह शिखर के करीब पहुँच जाता है।

परिणाम: तेज़ और स्मार्ट

लेखक ने सिंथेटिक डेटा (यादृच्छिक रूप से उत्पन्न संख्याएँ) का उपयोग करके इस नए तरीके का परीक्षण पुराने "रस्सी पर चलने वाले" तरीकों के विरुद्ध किया।

गति (Speed): नए तरीके ने समाधान को तेज़ी से खोजा, विशेष रूप से उच्च-आयामी (high-dimensional) स्थानों में (जहाँ "परिदृश्य" में सैकड़ों या हजारों दिशाएँ होती हैं)।
दक्षता (Efficiency): क्योंकि इसे हर कदम पर जटिल प्रोजेक्शन (रस्सी पर बने रहने के लिए) की गणना करने की आवश्यकता नहीं होती है, इसलिए यह कंप्यूटर के बहुत सारे समय की बचत करता है।
सटीकता (Accuracy): यह पिछले सर्वोत्तम तरीकों की तुलना में अधिक विश्वसनीयता और कम त्रुटियों के साथ "शिखर" तक पहुँचा।

निष्कर्ष (The Bottom Line)

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

यहाँ जोनास ब्रेश (Jonas Bresch) के शोध पत्र "Generalization of Zeroth-Order Method for Quotients of Quadratic Functions" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र शून्य-क्रम (zeroth-order/derivative-free) बाधाओं के तहत सामान्यीकृत ऑपरेटर नॉर्म (generalized operator norm) और चरम सामान्यीकृत रेले कोटिएंट (extremal generalized Rayleigh quotient) के अनुकूलन (optimization) को संबोधित करता है। विशेष रूप से, लक्ष्य को हल करना है:
$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$
जहाँ $A \in \mathbb{R}^{m \times d}$ और $B \in \mathbb{R}^{\ell \times d}$ ऐसी मैट्रिसेस (matrices) हैं जो केवल फॉरवर्ड इवैल्यूएशन (forward evaluations) के माध्यम से सुलभ हैं (ब्लैक-बॉक्स एक्सेस)।

मुख्य बाधाएं और चुनौतियां:

एडजॉइंट-मुक्त/मैट्रिक्स-मुक्त (Adjoint-Free/Matrix-Free): एडजॉइंट्स $A^T$ और $B^T$ अनुपलब्ध हैं या फॉरवर्ड ऑपरेटर्स के साथ असंगत हैं (जो लेगेसी कोड, PDE सॉल्वर और टोमोग्राफी में आम है)।
सुव्यवस्थितता (Well-posedness): $B$ का फुल कॉलम रैंक ( $\text{rank}(B)=d$ ) होना चाहिए ताकि $B^TB \succ 0$ हो सके।
मौजूदा विधियों की सीमाएं: हालिया अत्याधुनिक शून्य-क्रम विधियाँ (जैसे, ब्रेश एट अल. [7–9]) एक सामान्यीकृत गोले ( $S^{d-1}_{B^TB}$ ) पर टैंजेंट-स्पेस सैंपलिंग (tangent-space sampling) पर निर्भर करती हैं। इसके लिए सर्च डायरेक्शंस को प्रोजेक्ट करने के लिए मेट्रिक $B^TB$ या उसके वर्गमूल (square root) के ज्ञान की आवश्यकता होती है, जो सख्त ब्लैक-बॉक्स सेटिंग्स में अव्यवहारिक है।

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

यह शोध पत्र एक मौलिक रूप से भिन्न दृष्टिकोण प्रस्तावित करता है जो प्रतिबंधित टैंजेंट स्पेस के बजाय संपूर्ण यूनिट स्फीयर (unit sphere) पर अनकन्स्ट्रेंड सैंपलिंग (unconstrained sampling) पर आधारित है।

A. अनकन्स्ट्रेंड सैंपलिंग रणनीति (Unconstrained Sampling Strategy)

एक सामान्यीकृत गोले के टैंजेंट स्पेस से सर्च डायरेक्शंस $x_k$ को सैंपल करने के बजाय (जिसके लिए $B^TB$ की आवश्यकता होती है), यह विधि $x_k$ को मानक यूनिट स्फीयर $S^{d-1}$ से यूनिफॉर्मली सैंपल करती है:
$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$
यह मेट्रिक-डिपेंडेंट प्रोजेक्शन या एडजॉइंट जानकारी की आवश्यकता को समाप्त कर देता है।

B. क्लोज्ड-फॉर्म समाधान के माध्यम से इष्टतम स्टेप साइज (Optimal Step Size via Closed-Form Solution)

वर्तमान इटरैट (iterate) $v_k$ और सर्च डायरेक्शन $x_k$ के लिए, एल्गोरिदम रिट्रैक्शन पाथ (retraction path) के साथ एक इष्टतम स्टेप साइज $\tau_k$ खोजने का प्रयास करता है। पाथ के साथ ऑब्जेक्टिव फंक्शन एक क्वाड्रेटिक फंक्शन्स का कोटिएंट (quotient of quadratic functions) बन जाता है:
$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$
गुणांकों ( $a_k, \dots, f_k$ ) की गणना केवल $A$ और $B$ के फॉरवर्ड इवैल्यूएशन का उपयोग करके की जाती है।

सैद्धांतिक सफलता: यह शोध पत्र सिद्ध करता है कि इष्टतम $\tau_k$ खोजना $2 \times 2$ ग्राम मैट्रिसेस $M_k$ और $N_k$ से जुड़ी एक 2D सामान्यीकृत आइगेनवैल्यू समस्या (2D generalized eigenvalue problem) को हल करने के समान है।
परिणाम: $\tau_k$ के लिए एक क्लोज्ड-फॉर्म समाधान प्राप्त किया गया है (Theorem 3.1), जो यह सुनिश्चित करता है कि स्टेप साइज विशिष्ट रैंडम डायरेक्शन के लिए इष्टतम है, जिससे लाइन सर्च ह्यूरिस्टिक्स की आवश्यकता नहीं रहती।

C. ज़ीरोथ-ऑर्डर रीमानियन ऑप्टिमाइज़ेशन फ्रेमवर्क (Zeroth-Order Riemannian Optimization Framework)

यह विधि केवल फंक्शन इवैल्यूएशन का उपयोग करके रीमानियन ऑप्टिमाइज़ेशन मात्राओं के एस्टिमेटर्स (estimators) का निर्माण करती है:

ग्रेडिएंट एस्टिमेटर (Gradient Estimator): रैंडम डायरेक्शन $x_k$ और इष्टतम स्टेप साइज लॉजिक का उपयोग करके रीमानियन ग्रेडिएंट का एक अनबायस्ड (unbiased) एस्टिमेटर बनाया गया है।
हेसियन एस्टिमेटर (Hessian Estimator - Quasi-Newton): यह शोध पत्र यूनिट स्फीयर पर यूनिफॉर्म डिस्ट्रीब्यूशन के फोर्थ-ऑर्डर मोमेंट्स का उपयोग करके रीमानियन हेसियन के लिए एक अनबायस्ड एस्टिमेटर (Corollary 3.3) व्युत्पन्न करता है। यह एक ज़ीरोथ-ऑर्डर क्वाज़ी-न्यूटन विधि (Algorithm 3) को सक्षम बनाता है।
वेरिएंस रिडक्शन (Variance Reduction): $m$ स्वतंत्र सैंपल्स को औसत (average) करके (Algorithm 2), ग्रेडिएंट एस्टिमेटर के वेरिएंस को कम किया जाता है, जिससे अभिसरण (convergence) तेज होता है।

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

$S^{d-1}$ पर अनकन्स्ट्रेंड सैंपलिंग: यह शोध पत्र एक ऐसी सैंपलिंग स्कीम पेश करता है जो सामान्यीकृत गोले के टैंजेंट स्पेस के बजाय पूर्ण यूनिट स्फीयर पर काम करती है। यह $B^TB$ या इसके एडजॉइंट की आवश्यकता को समाप्त करता है, जिससे यह विधि उन सख्त ब्लैक-बॉक्स परिदृश्यों के लिए भी लागू हो जाती है जहाँ पिछली विधियाँ विफल रही थीं।
क्लोज्ड-फॉर्म इष्टतम स्टेप साइज: स्टैंडर्ड ज़ीरोथ-ऑर्डर विधियों के विपरीत, जो फिक्स्ड या ह्यूरिस्टिक स्टेप साइज का उपयोग करती हैं, यह कार्य विशिष्ट क्वाड्रेटिक कोटिएंट ऑब्जेक्टिव के लिए इष्टतम स्टेप साइज $\tau_k$ का एक सटीक, क्लोज्ड-फॉर्म समाधान प्रदान करता है। यह सब-प्रॉब्लम को एक समाधान योग्य 2D सामान्यीकृत आइगेनवैल्यू समस्या में बदल देता है।
अनबायस्ड हेसियन एस्टिमेशन: लेखक डेरिवेटिव-फ्री सेटिंग में रीमानियन हेसियन के लिए एक सिद्धांत-आधारित अनबायस्ड एस्टिमेटर प्रदान करते हैं। यह बिना किसी स्पष्ट डेरिवेटिव के कर्वेचर (curvature) जानकारी को कैप्चर करने के लिए एक सेकंड-ऑर्डर ज़ीरोथ-ऑर्डर एल्गोरिदम (Quasi-Newton) के निर्माण की अनुमति देता है।
सैद्धांतिक अभिसरण गारंटी (Theoretical Convergence Guarantees):
- लगभग निश्चित अभिसरण (Almost Sure Convergence): इटरैट्स का अनुक्रम (sequence) लीडिंग सामान्यीकृत आइगेनस्पेस की ओर लगभग निश्चित रूप से अभिसरित होता है (Theorem 3.7)।
- क्रिटिकल पॉइंट विश्लेषण: शोध पत्र सिद्ध करता है कि ग्रेडिएंट प्रॉक्सी ( $\alpha_k$ ) का अनुक्रम लगभग निश्चित रूप से शून्य की ओर अभिसरित होता है, जो यह सुनिश्चित करता है कि एल्गोरिदम गैर-इष्टतम क्रिटिकल पॉइंट्स पर नहीं फंसता (हल्की स्पेक्ट्रल धारणाओं के तहत)।
- सुव्यवस्थितता (Well-Definiteness): यह सिद्ध किया गया है कि स्टेप साइज गणना में डिनोमिनेटर (denominator) लगभग निश्चित रूप से गैर-शून्य रहता है, जिससे एल्गोरिदम सुव्यवस्थित रहता है।

4. संख्यात्मक परिणाम (Numerical Results)

प्रयोग $d=1000$ तक के आयामों वाली सिंथेटिक रैंडम गॉसियन मैट्रिसेस पर किए गए।

स्टेट-ऑफ-द-आर्ट के विरुद्ध प्रदर्शन:
- कम आयामों में (Low dimensions): प्रस्तावित विधि हाल की टैंजेंट-स्पेस सैंपलिंग विधियों [9] के तुलनीय है।
- उच्च आयामों में ( $d \gg 10$ ): अनकन्स्ट्रेंड स्फीयर सैंपलिंग, टैंजेंट-स्पेस विधियों की तुलना में काफी बेहतर प्रदर्शन करती है। इसका श्रेय बड़े सर्च स्पेस और महंगे प्रोजेक्शन ऑपरेशंस (मैट्रिक्स-मैट्रिक्स मल्टीप्लिकेशन) से बचने को दिया जाता है जो टैंजेंट-स्पेस विधियों द्वारा आवश्यक होते हैं।
अभिसरण दरें (Convergence Rates):
- विधि रिलेटिव कोटिएंट एरर (RQE) के लिए लीनियर कन्वर्जेंस प्रदर्शित करती है।
- मिनिमल स्क्वेर्ड रेसिडुअल (MSQR) के लिए, जो सामान्यीकृत आइगेन-इक्वेशन को दर्शाता है, अभिसरण दर $O(1/k)$ है, जो अक्सर देखे जाने वाले सबलीनियर (sublinear) दरों की तुलना में बेहतर है।
- सेकंड-ऑर्डर लाभ: क्वाज़ी-न्यूटन वेरिएंट (Algorithm 3), फर्स्ट-ऑर्डर वेरिएंट (Algorithm 2) की तुलना में अधिक सख्त अभिसरण व्यवहार और क्रिटिकल पॉइंट्स के पास तेज़ एरर रिडक्शन प्रदर्शित करता है।

5. महत्व (Significance)

यह कार्य स्पेक्ट्रल समस्याओं के लिए डेरिवेटिव-फ्री ऑप्टिमाइज़ेशन में एक महत्वपूर्ण प्रगति है।

व्यावहारिक प्रभाव: यह उन परिदृश्यों में ऑपरेटर नॉर्म्स और रेले कोटिएंट्स की गणना को सक्षम बनाता है जहाँ एडजॉइंट ऑपरेटर्स अनुपलब्ध, असंगत, या बहुत महंगे हैं (जैसे, लेगेसी सिमुलेशन कोड, जटिल PDE सॉल्वर)।
सैद्धांतिक प्रभाव: यह स्पष्ट मैनिफोल्ड प्रोजेक्शन के बिना मैनिफोल्ड्स पर अनबायस्ड ग्रेडिएंट और हेसियन दोनों के लिए एस्टिमेटर्स प्रदान करके ज़ीरोथ-ऑर्डर रैंडम सर्च और रीमानियन ऑप्टिमाइज़ेशन के बीच के अंतर को पाटता है।
एल्गोरिद्मिक दक्षता: क्लोज्ड-फॉर्म स्टेप साइज और बिना टैंजेंट स्पेस प्रोजेक्शन के काम करने की क्षमता इस एल्गोरिदम को उच्च-आयामी समस्याओं के लिए कम्प्यूटेशनल रूप से कुशल और स्केलेबल बनाती है।

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