🔢 mathematics

An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

यह शोध पत्र iR2N को प्रस्तुत करता है, जो एक इनएक्सैक्ट मॉडिफाइड प्रॉक्सिमल क्वाजी-न्यूटन विधि है नॉनकॉन्वेक्स रेगुलराइज्ड ऑप्टिमाइज़ेशन के लिए, जो फंक्शन, ग्रेडिएंट और प्रॉक्सिमल ऑपरेटर इवैल्यूएशन में नियंत्रित अशुद्धियों की अनुमति देकर कंप्यूटेशनल प्रयास को महत्वपूर्ण रूप से कम करके $O(\epsilon^{-2})$ कॉम्प्लेक्सिटी के साथ ग्लोबल कन्वर्जेंस प्राप्त करता है।

मूल लेखक: Nathan Allaire, Sébastien Le Digabel, Dominique Orban

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

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

CC BY 4.0

मूल लेखक: Nathan Allaire, Sébastien Le Digabel, Dominique Orban

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

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

आमतौर पर, ये घाटियाँ पेचीदा होती हैं। वे केवल चिकनी पहाड़ियों जैसी नहीं होतीं; उनमें ऊबड़-खाबड़ चट्टानें, नुकीले कोने और छिपे हुए जाल होते हैं। गणितीय भाषा में, इसका अर्थ है कि इन परिदृश्यों का वर्णन करने वाले फलन (functions) "नॉनस्मूथ" (nonsmooth) होते हैं और कभी-कभी "नॉनकॉन्वेक्स" (nonconvex) भी होते हैं (जिसका अर्थ है कि उनमें कई स्थानीय गड्ढे हैं जो असली तल की तरह दिखते हैं लेकिन वास्तव में नहीं हैं)। इस राह को पार करने के लिए, कंप्यूटर प्रॉक्सिमल ऑपरेटर्स (proximal operators) नामक विशेष उपकरणों का उपयोग करते हैं। इन्हें एक जादुई दिशा-सूचक यंत्र (compass) की तरह समझें जो, जब आप किसी ऊबड़-खाबड़ चट्टान पर फंस जाते हैं, तो आपको बताता है कि निकटतम समतल जमीन पर कदम कैसे रखना है। हालाँकि, इस दिशा-सूचक यंत्र की गणना को पूरी तरह से करना अविश्वसनीय रूप से धीमा और महंगा हो सकता है, जैसे हीरे से बनी रूलर से हवा को मापने की कोशिश करना। कभी-कभी, डेटा स्वयं धुंधला या अधूरा होता है, जैसे कि थोड़े आउट-ऑफ-फोकस सैटेलाइट इमेज से तटरेखा का मानचित्र बनाने की कोशिश करना। बड़ा सवाल इस विज्ञान के कोने में यह है: क्या हम अभी भी घाटी के तल को पा सकते हैं यदि हम एक थोड़े धुंधले दिशा-सूचक यंत्र का उपयोग करें और कुछ अस्पष्ट मापों को स्वीकार करें, बिना हमेशा के लिए खो जाए?

यह शोध पत्र एक नई विधि पेश करता है जिसे iR2N (Inexact Regularized Quasi-Newton) कहा जाता है, जो एक हाइकर को स्मार्ट, अनुकूलन योग्य जूतों की जोड़ी देने जैसा है जो जानते हैं कि कब सटीक होना है और कब शॉर्टकट लेना है। लेखक, नाथन एलर, सेबस्टियन ले डिगाबेल और डोमिनिक ऑर्बन, यह प्रस्ताव देते हैं कि हमें हमेशा सटीक कदम या भूभाग के सटीक आकार की आवश्यकता नहीं होती है। इसके बजाय, iR2N कंप्यूटर को "इनएक्सैक्ट" (inexact) यानी अपूर्ण कदम उठाने की अनुमति देता—ऐसे अनुमान जो उस क्षण के लिए "काफी अच्छे" हैं।

मुख्य विचार एक संतुलन बनाना है। कल्पना कीजिए कि आप अंधेरे में पहाड़ से नीचे उतर रहे हैं। एक पारंपरिक विधि हर एक कदम पर अपने सटीक स्थान की जांच करने पर जोर देती है, जिसमें बहुत समय लगता है। iR2N कहता है, "आइए बस अनुमान लगाएं कि जमीन कहाँ है, एक कदम उठाएं, और यदि हमें लगता है कि हम गलत दिशा में फिसल रहे हैं, तो हम इसे ठीक कर लेंगे।" यह विधि एक "रेगुलराइजेशन" (regularization) पद का उपयोग करती है, जो एक सुरक्षा रस्सी की तरह कार्य करता है, यह सुनिश्चित करता है कि भले ही कदम खुरदरे हों, हाइकर खाई में नहीं भटक जाएगा। यह पत्र गणितीय रूप से सिद्ध करता है कि इन अस्पष्ट कदमों और अनुमानित मापों के साथ भी, हाइकर अंततः घाटी के तल तक पहुँच जाएगा। वास्तव में, वे दिखाते हैं कि वहां पहुँचने में लगने वाला समय (जटिलता/complexity) उतना ही अच्छा है जितना कि यदि उन्होंने पूरी तरह से सटीक, महंगे लेजर मापों का उपयोग किया होता।

शोधकर्ताओं ने इसे केवल सपना नहीं देखा; उन्होंने जूलिया (Julia) नामक एक प्रोग्रामिंग भाषा में iRne का एक कार्यात्मक संस्करण बनाया और तीन अलग-अलग प्रकार के "पहाड़ों" पर इसका परीक्षण किया। पहले, उन्होंने बेसिस पर्पस डिनोइजिंग (Basis Pursuit Denoising) नामक एक समस्या का प्रयास किया, जो एक शोर भरी ऑडियो रिकॉर्डिंग को साफ करके मूल गाना खोजने जैसा है। दूसरा, उन्होंने मैट्रिक्स कम्प्लीशन (Matrix Completion) को हल किया, जो एक पहेली को पूरा करने के समान है जहाँ कई टुकड़े गायब हैं, जैसे कि एक क्षतिग्रस्त छवि को पुनर्गठित करना। अंत में, उन्होंने फिट्ज़हुग-नागुमो इनवर्स प्रॉब्लम (FitzHugh-Nagumo inverse problem) पर परीक्षण किया, जिसमें देखे गए डेटा के आधार पर एक न्यूरॉन की विद्युत गतिविधि के छिपे हुए सेटिंग्स का पता लगाना शामिल है।

इन परीक्षणों में, उन्होंने एक "नॉब" के साथ प्रयोग किया जिसे $\kappa_s$ (कप्पा-एस) कहा जाता है, जो यह नियंत्रित करता है कि कदम कितने सटीक होने चाहिए। जब उन्होंने कम सटीकता (एक छोटा $\kappa_s$ ) के लिए नॉब घुमाया, तो कंप्यूटर ने प्रत्येक व्यक्तिगत कदम की गणना करने में बहुत कम समय खर्च किया। हालाँकि, इसके साथ एक समझौता भी आता है: क्योंकि कदम अधिक खुरदरे होते हैं, एल्गोरिदम को अक्सर कुल अधिक कदम (outer iterations) लेने की आवश्यकता होती है। कदमों की संख्या में इस वृद्धि के बावजूद, समस्या को हल करने का कुल समय अक्सर काफी कम हो गया। उदाहरण के लिए, इमेज रिकंस्ट्रक्शन टेस्ट में, कम-सटीक कदमों (छोटा $\kappa_s$ ) का उपयोग करने से कुछ कॉन्फ़िगरेशन में समाधान का समय 300 सेकंड से घटकर लगभग 94 सेकंड हो गया, जबकि इसने एक ऐसा समाधान खोजा जो सटीक गणनाओं द्वारा पाए गए समाधान के लगभग समान था। यहाँ तक कि जब डेटा स्वयं धुंधला था (वास्तविक दुनिया के शोर का अनुकरण करते हुए), तो विधि ने खुद को तब तक सटीक बनाकर अनुकूलित किया जब वह फंस गई थी, जिससे भारी मात्रा में समय बचा।

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

अंततः, iR2N "काफी अच्छे" (good enough) की शक्ति का प्रमाण है। यह सुझाव देता है कि जटिल ऑप्टिमाइज़ेशन की दुनिया में, हम अनुमान को अपनाकर महत्वपूर्ण कंप्यूटेशनल प्रयास और समय बचा सकते हैं, बशर्ते हमारे पास एक स्मार्ट रणनीति हो कि कब सटीक होना है और कब गणित को ढीला छोड़ देना है। लेखक इस परीक्षण को आज़माने के लिए किसी के लिए भी एक मुफ्त, ओपन-सोर्स टूल प्रदान करते हैं, जो यह सिद्ध करता है कि कभी-कभी, घाटी के तल तक पहुँचने का सबसे तेज़ तरीका अपने पैरों को माइक्रोस्कोप से देखना नहीं, बल्कि एक स्थिर, अनुकूलन योग्य चाल के साथ आगे बढ़ते रहना है।

तकनीकी सारांश: एक नॉनस्मूथ रेगुलराइज्ड ऑप्टिमाइज़ेशन के लिए इनएक्सैक्ट मॉडिफाइड क्वासी-न्यूटन विधि

समस्या विवरण
यह शोध पत्र नॉनस्मूथ रेगुलराइज्ड ऑप्टिमाइज़ेशन समस्या को संबोधित करता है:
$\min_{x \in \mathbb{R}^n} f(x) + h(x)$
जहाँ $f: \mathbb{R}^n \to \mathbb{R}$ निरंतरतः अवकलनीय (संभावित रूप से नॉनकॉन्वेक्स) है और $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ उचित (proper), लोअर सेमी-कंटीन्यूअस और संभावित रूप से नॉनकॉन्वेक्स है। फलन $h$ विशिष्ट समाधान गुणों को बढ़ावा देने के लिए एक रेगुलराइज़र के रूप में कार्य करता है, जैसे कि स्पर्सिटी (sparsity)।

प्राथमिक चुनौती $f$ , इसके ग्रेडिएंट $\nabla f$ , और $h$ के प्रॉक्सिमल ऑपरेटर के सटीक मूल्यांकन (exact evaluations) प्राप्त करने की कम्प्यूटेशनल लागत या अव्यवहारिकता है। ऐसी इनएक्सैक्टनेस (inexactness) निम्नलिखित परिदृश्यों में उत्पन्न होती है:

डिफरेंशियल या इंटीग्रल ऑपरेटर्स का विवेकीकरण (Discretization)।
मशीन लर्निंग में स्टोकेस्टिक सैंपलिंग (बड़ी संख्याओं के योगों के रूप में)।
वे पुनरावृत्ति प्रक्रियाएं जिनमें प्रॉक्सिमल ऑपरेटर्स के मूल्यांकन के लिए क्लोज्ड-फॉर्म समाधानों की कमी होती है (जैसे, $\ell_p$ -norm टोटल वेरिएशन, नॉनकॉन्वेक्स $\ell_p$ -pseudo norm बॉल्स)।
मल्टी-प्रिसिजन फ्लोटिंग-पॉइंट अरिथमेटिक।

कार्यप्रणाली: iR2N एल्गोरिदम
लेखक iR2N (Inexact Regularized R2N) पेश करते हैं, जो एक मॉडिफाइड प्रॉक्सिमल क्वासी-न्यूटन विधि है जो इनएक्सैक्ट मूल्यांकनों को संभालने के लिए Diouane et al. [26] के R2N एल्गोरिदम का विस्तार करती है।

मुख्य तंत्र: प्रत्येक इटरेशन में, iR2N $f$ के एक क्वाड्रेटिक एप्रोक्सिमेशन, $h$ के एक मॉडल, और एक एडेप्टिव क्वाड्रेटिक रेगुलराइजेशन टर्म वाले मॉडल को लगभग न्यूनतम करने के लिए एक स्टेप कंप्यूट करता है।
इनएक्सैक्टनेस हैंडलिंग:
- ऑब्जेक्टिव और ग्रेडिएंट: एल्गोरिदम $\tilde{f}$ और $\tilde{\nabla}f$ का उपयोग करता है। एरर बाउंड्स को यह मानते हुए स्केल किया जाता है कि वे स्टेप साइज के साथ बदलते हैं (विशेष रूप से, $|f(x) - \tilde{f}(x)| \leq \kappa_f \|s\|^2$ और $\|\nabla f(x) - \tilde{\nabla}f(x)\| \leq \kappa_\nabla \|s\|$ )।
- प्रॉक्सिमल ऑपरेटर: सबप्रॉब्लम में एक प्रॉक्सिमल ऑपरेटर शामिल है जिसे इनएक्सैक्टली मूल्यांकित किया जाता है। विधि प्रॉक्सिमल ऑपरेटर को हल करने के लिए एक प्रॉक्सिमल-ग्रेडिएंट विधि (जिसे iR2 कहा जाता है) का उपयोग करती है। महत्वपूर्ण रूप से, प्रॉक्सिमल ऑपरेटर के लिए पुनरावृत्ति प्रक्रिया को समय से पहले समाप्त किया जा सकता है।
प्रॉक्सिमल स्टेप्स के लिए स्टॉपिंग क्राइटेरिया: प्रॉक्सिमल सॉल्वर के लिए स्टॉपिंग कंडीशन एक प्रमुख नवाचार है। वैश्विक मिनिमाइज़र तक अभिसरण (convergence) की आवश्यकता के बजाय, प्रक्रिया तब रुक जाती है जब वर्तमान इटरट $\|\tilde{s}_{k,cp}\|$ सटीक कॉची स्टेप (Cauchy step) के नॉर्म के ऊपरी बाउंड $M_k$ के एक अंश $\kappa_s$ से अधिक हो जाता है। यह स्थिति साहित्य (जैसे, रॉकैफेलर के समेबल एरर क्राइटेरिया) की मानक आवश्यकताओं की तुलना में कमजोर है लेकिन अभिसरण के लिए पर्याप्त है।
एक्सेप्टेंस क्राइटेरिया: एल्गोरिदम प्राप्त और अनुमानित कमी (इनएक्सैक्ट मूल्यांकनों पर आधारित) के अनुपात का उपयोग स्टेप को स्वीकार या अस्वीकार करने के लिए करता है, और डायनामिक रूप से अपने रेगुलराइजेशन पैरामीटर $\sigma_k$ को अपडेट करता है।

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

एल्गोरिदम डिज़ाइन: i-R2N का फॉर्मूलेशन, जो एक मॉडिफाइड क्वासी-न्यूटन फ्रेमवर्क के भीतर $f$ , ग्रेडिएंट और प्रॉक्सिमल ऑपरेटर्स के इनएक्सैक्ट मूल्यांकनों को एकीकृत करता है।
अभिसरण विश्लेषण (Convergence Analysis):
- ग्लोबल कन्वर्जेंस: मानक धारणाओं (ग्रेडिएंट की लिप्सचिट्ज़ निरंतरता, हेसियन एप्रोक्सिमेशन की बाउंडेडनेस और विशिष्ट इनएक्सैक्टनेस स्थितियों) के तहत, लेखक सिद्ध करते हैं कि फर्स्ट-ऑर्डर स्टेशनैरिटी मेजर शून्य की ओर अभिसरित होता है।
- जटिलता (Complexity): पेपर स्टेशनैरिटी मेजर को $\epsilon > 0$ से नीचे लाने के लिए $O(\epsilon^{-2})$ का वर्स्ट-केस इवैल्यूएशन कॉम्प्लेक्सिटी स्थापित करता है। यह सटीक R2N विधि की जटिलता से मेल खाता है, जो यह दर्शाता है कि इनएक्सैक्ट मूल्यांकन एसिम्प्टोटिक वर्स्ट-केस परफॉर्मेंस को खराब नहीं करते हैं।
इनएक्सैक्टनेस का व्यावहारिक कार्यान्वयन: लेखक तीन चुनौतीपूर्ण रेगुलराइजर्स के लिए सटीक कॉची स्टेप के नॉर्म पर विशिष्ट सैद्धांतिक सीमाएं प्रदान करते हैं:
- $\ell_p$ -norm ( $1 \leq p < \infty$ )।
- $\ell_p$ -total variation ( $1 \leq p < \infty$ )।
- नॉनकॉन्वेक्स $\ell_p$ -pseudo norm बॉल का इंडिकेटर ( $0 < p < 1$ )।
  ये सीमाएं इनर इटरेटिव सॉल्वर्स के लिए प्रभावी अर्ली-स्टॉपिंग कंडीशंस बनाने की अनुमति देती हैं।
सॉफ्टवेयर: जूलिया (Julia) में एक कुशल कार्यान्वयन, जो RegularizedOptimization.jl ओपन-सोर्स पैकेज में एकीकृत है।

परिणाम
संख्यात्मक प्रयोग तीन समस्या वर्गों पर किए गए:

बेसिस पर्पस डिनोइजिंग (BPDN): $\ell_p$ -norm रेगुलराइज़र का उपयोग करके।
मैट्रिक्स कंप्लीशन: $\ell_p$ -total variation रेगुलराइज़र का उपयोग करके।
फिट्ज़हुग-नैगमोग (FitzHugh-Nagumo) इनवर्स प्रॉब्लम: नॉनकॉन्वेक्स $\ell_p$ -pseudo norm बॉल इंडिकेटर का उपयोग करके।

प्रयोगों में इनएक्सैक्टनेस पैरामीटर $\kappa_s$ (प्रॉक्सिमल स्टेप की गुणवत्ता को नियंत्रित करता है) और ऑब्जेक्टिव/ग्रेडिएंट मूल्यांकनों की सटीकता (ODE सॉल्वर टॉलरेंस के माध्यम से) को अलग-अलग किया गया।

परफॉर्मेंस: छोटे $\kappa_s$ मानों के लिए (जो मोटे प्रॉक्सिमल स्टेप्स की अनुमति देते हैं), विधि ने प्रति इटरेशन कम्प्यूटेशनल समय को काफी कम कर दिया। हालांकि इससे कभी-कभी बाहरी इटरेशन की संख्या थोड़ी बढ़ गई, लेकिन शुद्ध परिणाम "एक्सेक्ट मोड" (जहाँ प्रॉक्सिमल ऑपरेटर्स को उच्च सटीकता तक हल किया जाता है) की तुलना में कुल CPU समय में पर्याप्त कमी थी।
रोबस्टनेस: इनएक्सैक्ट मोड में प्राप्त समाधान "एक्सेक्ट मोड" के लगभग समान पाए गए, जिन्होंने सफलतापूर्वक स्पर्स सपोर्ट को रिकवर किया और सिग्नल को पुनर्गठित किया।
इनएक्सैक्ट ग्रेडिएंट्स: जब इसे एडेप्टिव टॉलरेंस स्कीम द्वारा नियंत्रित इनएक्सैक्ट ग्रेडिएंट्स के साथ फिट्ज़हुग-नैगमोग समस्या पर लागू किया गया, तो विधि ने अभिसरण बनाए रखा और महत्वपूर्ण समय बचत हासिल की, बशर्ते कि असफल इटरेशन पर सटीकता को पर्याप्त रूप से बढ़ाया गया हो।

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

लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण प्रॉक्सिमल ऑपरेटर्स के लिए उन पुनरावृत्ति प्रक्रियाओं के उपयोग की अनुमति देता है जिन्हें समय से पहले रोका जा सकता है, जो विशेष रूप से नॉनकॉन्वेक्स रेगुलराइजर्स (जैसे $\ell_p$ -pseudo norm बॉल) के लिए मूल्यवान है जहाँ प्रॉक्सिमल सबप्रॉब्लम का ग्लोबल मिनिमाइजेशन कठिन या असंभव होता है। यह कार्य सैद्धांतिक जटिलता विश्लेषण और व्यावहारिक कम्प्यूटेशनल दक्षता के बीच के अंतर को पाटता है।

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