Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

तकनीकी सारांश: दुर्बलतः उत्तलीय (Weakly Convex) फलनों के लिए त्रुटि सीमाएँ, PL स्थिति, और द्विघातीय वृद्धि (Quadratic Growth), तथा प्रॉक्सिमल पॉइंट विधियों (Proximal Point Methods) का रैखिक अभिसरण

समस्या विवरण
कई व्यावहारिक अनुकूलन समस्याएँ, विशेष रूप से मशीन लर्निंग और सिग्नल प्रोसेसिंग में, सुदृढ़ उत्तलता (strong convexity) का अभाव रखती हैं। जबकि प्रथम-क्रम एल्गोरिदम सुदृढ़ उत्तलता के तहत रैखिक अभिसरण (linear convergence) प्राप्त करने के लिए जाने जाते हैं, हालिया अध्ययनों से पता चला है कि सुचारू (smooth) और उत्तल (convex) फलनों के लिए कमजोर नियमितता स्थितियों (जैसे, पोल्याक-लोजासिएविक (Polyak-Lojasiewicz) असमानता, त्रुटि सीमा (error bounds), द्विघातीय वृद्धि) के तहत भी रैखिक अभिसरण सुनिश्चित किया जा सकता है। हालाँकि, गैर-सुचारू (nonsmooth), गैर-उत्तल (nonconvex) फलनों के संदर्भ में इन स्थितियों के बीच संबंध अच्छी तरह से समझ में नहीं आए थे। विशेष रूप से, दुर्बलतः उत्तलीय फलनों (ऐसे फलन जहाँ $f + \frac{\rho}{2}\|\cdot\|^2$ उत्तल है, किसी $\rho \geq 0$ के लिए) का वर्ग (जैसे, गैर-सुचारू डीप नेटवर्क, उत्तल और सुचारू फलनों का संयोजन) एक एकीकृत ढांचे की कमी रखता था जो इन नियमितता स्थितियों को जोड़ता हो। इसके अलावा, प्रॉक्सिमल पॉइंट मेथड (PPM) के रैखिक अभिसरण के लिए मौजूदा प्रमाण अक्सर प्रतिबंधात्मक धारणाओं (जैसे, अद्वितीय मिनिमाइज़र, व्युत्क्रम उप-विभेदक (inverse subdifferential) की स्थानीय लिप्सचिट्ज़ निरंतरता) पर निर्भर करते थे या जटिल तर्कों का उपयोग करते थे।

कार्यप्रणाली
यह शोध पत्र गैर-सुचारू विश्लेषण के उपकरणों का उपयोग करता है, विशेष रूप से ढलान (slope) की अवधारणा, एकेलैंड के वेरिएशनल सिद्धांत (Ekeland's variational principle), और दूरी अनुमान लेम्मा (distance estimation lemmas) का उपयोग करके, नियमितता स्थितियों के बीच संबंधों का विश्लेषण करने के लिए। लेखक एक सबलेवल सेट $[f \leq f^\star + \nu]$ पर पाँच प्रमुख स्थितियों को परिभाषित करते हैं:

1. सुदृढ़ उत्तलता (Strong Convexity - SC)
2. प्रतिबंधित सेकेंट असमानता (Restricted Secant Inequality - RSI)
3. उप-विभेदक त्रुटि सीमा (Subdifferential Error Bound - EB)
4. पोल्याक-लोजासिएविक (PL) असमानता
5. द्विघातीय वृद्धि (Quadratic Growth - QG)

लेखक सुचारू और गैर-सुचारू सेटिंग्स के बीच के अंतर को पाटने के लिए ढलान $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (जहाँ $\hat{\partial}f$ फ्रेचेट उप-विभेदक है) का उपयोग करते हैं। वे इन स्थितियों के बीच तार्किक निहितार्थ और तुल्यता स्थापित करते हैं, विशेष रूप से उस मामले पर ध्यान केंद्रित करते हैं जहाँ द्विघातीय वृद्धि स्थिरांक $\mu_q$, दुर्बल उत्तलता पैरामीटर $\rho$ से अधिक होता है।

इन तुल्याओं पर निर्माण करते हुए, शोध पत्र प्रॉक्सिमल पॉइंट मेथड (PPM) का विश्लेषण करता है:
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
लेखक उत्तल और दुर्बलतः उत्तल दोनों सेटिंग्स के लिए रैखिक अभिसरण के लिए एक मॉड्यूलर प्रमाण प्रदान करते हैं। वे अपूर्ण (Inexact) PPM (iPPM) के विश्लेषण का भी विस्तार करते हैं, जहाँ उप-समस्याओं को अनुमानित रूप से हल किया जाता है, जिसमें रुकने के मानदंडों (stopping criteria) और व्यवहार्यता (यह सुनिश्चित करना कि इटरेट्स $f$ के डोमेन के भीतर रहें) के सूक्ष्म पहलुओं को संबोधित किया गया है।

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

1. दुर्बलतः उत्तल फलनों के लिए नियमितता स्थितियों का एकीकरण:
   शोध पत्र $\rho$-दुर्बलतः उत्तल फलनों के लिए नियमितता स्थितियों के पदानुक्रम और तुल्यता को स्थापित करता है।

   • सामान्य निहितार्थ श्रृंखला: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$।
   • $\mu_q > \rho$ के तहत तुल्यता: यदि एक $\rho$-दुर्बलतः उत्तल फलन $\mu_q > \rho$ स्थिरांक के साथ द्विघातीय वृद्धि (Quadratic Growth) को संतुष्ट करता है, तो चारों स्थितियाँ $(RSI), (EB), (PL),$और$(QG)$ तुल्य हैं।
   • लेखक इन स्थितियों के बीच स्पष्ट गुणांक रूपांतरण (जो शोध पत्र की तालिका 1 में संक्षेपित है) प्राप्त करते हैं, जिससे चिकित्सकों को एक स्थिति से दूसरी स्थिति में स्थिरांकों को अनुवादित करने की अनुमति मिलती है।

2. PPM के लिए सरल रैखिक अभिसरण प्रमाण:
   शोध पत्र उत्तल और दुर्बलतः उत्तल दोनों फलनों के लिए PPM के रैखिक अभिसरण के लिए एक सरल, मॉड्यूलर प्रमाण प्रस्तुत करता है।

   • उत्तल मामला: किसी भी तुल्य नियमितता स्थिति (PL, EB, RSI, QG) के तहत, PPM फंक्शन वैल्यू और समाधान सेट की दूरी दोनों के लिए रैखिक अभिसरण प्राप्त करता है। प्रमाण पिछले प्रतिबंधों को शिथिल करता है, जिसमें अद्वितीय मिनिमाइज़र या व्युत्क्रम उप-विभेदक की स्थानीय लिप्सचिट्ज़ निरंतरता की आवश्यकता को हटा दिया गया है।
   • दुर्बलतः उत्तल मामला: परिणामों को $\rho$-दुर्बलतः उत्तल फलनों के लिए विस्तारित किया गया है, बशर्ते कि प्रारंभिक स्थिति (initialization) एक ऐसे सबलेवल सेट के भीतर हो जो $\mu_q > \rho$ के साथ QG को संतुष्ट करता हो और स्टेप साइज़ $1/c_k > \rho$ को संतुष्ट करते हों।

3. अपूर्ण PPM (iPPM) का विश्लेषण:
   लेखक iPPМ में अपूर्णता और व्यवहार्यता के सूक्ष्म अंतरों को स्पष्ट करते हैं। वे मानक स्टॉपिंग क्राइटेरिया (रॉकैफ़र के मानदंड A और B) के तहत iPPM के लिए रैखिक अभिसरण स्थापित करते हैं, बशर्ते कि फलन समाधान सेट के पड़ोस में QG को संतुष्ट करता हो। प्रमाण पूर्व साहित्य के एक प्रमुख असमिका (inequality) को मॉड्यूलर नियमितता स्थिति ढांचे के साथ जोड़ता है।

परिणाम

• सैद्धांतिक: प्रमेय 3.1 पुष्टि करता है कि दुर्बलतः उत्तल फलनों के लिए, नियमितता स्थितियों की तुल्यता तब मान्य होती है जब $\mu_q > \rho$ हो। यह पिछले परिणामों का सामान्यीकरण करता जो केवल सुचारू या उत्तल फलनों तक सीमित थे।
• एल्गोरिद्मिक: प्रमेय 4.2 और 4.3 दर्शाते हैं कि PPM नियमितता स्थिरांकों (जैसे, $\omega_k = \frac{1}{1+c_k\mu_p}$) पर निर्भर दरों के साथ रैखिक अभिसरण प्राप्त करता है। प्रमेय 5.3 इसे अपूर्ण PPM (iPPM) तक विस्तारित करता, यह दिखाते हुए कि जब तक अपूर्णता नियंत्रित है (त्रुटियों का योग परिमित है), रैखिक अभिसरण दर स्पर्शोन्मुख रूप से (asymptotically) संरक्षित रहती है।
• संख्यात्मक: लीनियर SVM, लासो (Lasso), और इलास्टिक-नेट (Elastic-Net) समस्याओं पर प्रयोग PPM के सैद्धांतिक रैखिक अभिसरण की पुष्टि करते हैं। प्रयोग YALMIP मॉडलिंग पैकेज और MOSEK सॉल्वर का उपयोग करते हैं, जो लागत मान अंतराल (cost value gaps) और समाधान सेट की दूरी दोनों में तेज़ अभिसरण दिखाते हैं।

महत्व और दावे
शोध पत्र यह दावा करता है कि वह सुचारू/उत्तल सेटिंग्स से व्यापक श्रेणी के गैर-सुचारू दुर्बलतः उत्तल फलनों तक नियमितता स्थितियों की समझ को सामान्यीकृत करता है। इन स्थितियों के बीच संबंधों को स्पष्ट करके, लेखक पुनरावृत्त एल्गोरिदम (iterative algorithms) के विश्लेषण को सरल बनाने के लिए एक एकीकृत ढांचा प्रदान करते हैं।

विशेष रूप से, शोध पत्र यह दावा करता है कि:

• $\mu_q > \rho$ के तहत स्थितियों की तुल्यता (RSI, EB, PL, QG) लचीले विश्लेषण की अनुमति देती; एक स्थिति को स्थापित करके अन्य स्थितियों के माध्यम से अभिसरण परिणाम प्राप्त किए जा सकते हैं।
• PPM रैखिक अभिसरण के प्रमाण मौजूदा साहित्य की तुलना में सरल और अधिक पारदर्शी हैं, जो अद्वितीय मिनिमाइज़र जैसे प्रतिबंधात्मक धारणाओं से बचते हैं।
• परिणाम गैर-सुचारू अनुकूलन के लिए एल्गोरिदम विकास की सुविधा प्रदान करते हैं, विशेष रूप से बड़े पैमाने के कॉनिक अनुकूलन और मशीन लर्निंग अनुप्रयोगों में जहाँ दुर्बल उत्तलता प्रचलित है।

लेखक नोट करते हैं कि जबकि इन स्थितियों की तुल्यता सुचारू या उत्तल फलनों के लिए ज्ञात थी, इसे दुर्बलतः उत्तल सेटिंग में विस्तारित करना और PPM (अपूर्ण संस्करण सहित) के लिए एक स्वच्छ प्रमाण प्रदान करना प्राथमिक नवीनता है। यह कार्य एक कॉन्फ्रेंस पेपर का विस्तारित संस्करण है, जिसमें विस्तृत प्रमाण, गुणांक रूपांतरण और अपूर्ण PPM का विस्तारित विश्लेषण जोड़ा गया है।