Extragradient methods with complexity guarantees for hierarchical variational inequalities

तकनीकी सारांश: पदानुक्रमित वेरिएशनल इनइक्वेलिटीज़ के लिए जटिलता गारंटी के साथ एक्स्ट्राग्रेडिएंट विधियाँ

समस्या का सूत्रण
यह शोध पत्र एक वास्तविक पृथक हिल्बर्ट स्पेस (Hilbert space) $Z$ के भीतर पदानुक्रमित संतुलन समस्याओं (hierarchical equilibrium problems) को हल करने की समस्या को संबोधित करता है। मुख्य उद्देश्य एक अन्य HVI के समाधान सेट के ऊपर परिभाषित एक हेमी-वेरिएशनल इनइक्वेलिटी (HVI) के लिए $z^*$ समाधान खोजने का है। औपचारिक रूप से, समस्या (P) में $z^* \in S_2$ खोजना है ताकि:
$$\langle F_1(z^*), z - z^* \rangle + \ell_1(z) - \ell_1(z^*) \geq 0 \quad \forall z \in S_2$$
जहाँ $S_2 = \text{zer}(F_2 + \partial \ell_2)$ निचले स्तर के HVI का समाधान सेट है। यहाँ, $F_1, F_2$ मोनोटोन ऑपरेटर्स हैं, और $\ell_1, \ell_2$ उचित (proper), उत्तल (convex), और निम्न-अर्ध-सतत (lower-semicontinuous) फलन हैं।

यह सूत्रण कई समस्या वर्गों को एकीकृत करता है, जिनमें शामिल हैं:

• सरल बाइलेवल ऑप्टिमाइज़ेशन (जहाँ $\ell_1, \ell_2$ स्मूथ या कंपोजिट हैं)।
• नेस्टेड वेरिएशनल इनइक्वेलिटीज़ (जहाँ $\ell_1=0$ और $\ell_2$ एक इंडिकेटर फंक्शन है)।
• पदानुक्रमित संयुक्त रूप से उत्तल सामान्यीकृत नैश इक्विलिब्रियम समस्याएं (GNEPs)।
• VI बाधाओं के तहत अनुकूल नियंत्रण (Optimal control)।

कार्यप्रणाली
लेखक टिखोनोव रेगुलराइजेशन (Tikhonov regularization) पर आधारित एक ऑप्टिमिस्टिक एक्स्ट्राग्रेडिएंट विधि (एल्गोरिदम 1) प्रस्तावित करते हैं। पिछले दृष्टिकोणों के विपरीत, जिन्हें प्रति पुनरावृत्ति (iteration) दो बार ऑपरेटर मूल्यांकन की आवश्यकता होती है (जैसे मानक एक्स्ट्राग्रेडिएंट), यह विधि प्रति पुनरावृत्ति गणना लागत को कम करने के लिए एक "पिछले" ऑपरेटर मूल्यांकन का उपयोग करती है।

एल्गोरिदम एक अनुक्रमित नियमित ऑपरेटरों $V_k = F_2 + \sigma_k F_1$ और नियमित फलन $G_k = \ell_2 + \sigma_k \ell_1$ का निर्माण करता है, जहाँ $(\sigma_k)$ एक घटता हुआ रेगुलराइजेशन अनुक्रम है जो शून्य की ओर अभिसरित होता है। पुनरावृत्ति योजना इस प्रकार है:

1. प्रेडिक्शन (Prediction): $z_{k+1/2} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k-1/2}) + \sigma_k F_1(z_{k-1/2})))$
2. करेक्शन (Correction): $z_{k+1} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k+1/2}) + \sigma_k F_1(z_{k+1/2})))$

विश्लेषण विशिष्ट ज्यामितीय धारणाओं पर निर्भर करता है:

• वीक शार्पनेस (Weak Sharpness): यह माना गया है कि निचले स्तर का समाधान सेट $S_2$, गैप फंक्शन और समाधान सेट से दूरी के बीच संबंध स्थापित करने वाली एक $(\alpha, \rho)$-वीक शार्पनेस स्थिति को संतुष्ट करता है।
• अट्टौच-ज़ारनेकी (Attouch-Czarnecki) स्थिति: पुनरावृत्तियों और रेगुलराइजेशन मापदंडों की अभिसरण (summability) सुनिश्चित करने के लिए स्टेप साइज़ और रेगुलराइजेशन मापदंडों पर एक स्थिति लगाई गई है ताकि पुनरावृत्तियों की परिबद्धता (boundedness) बनी रहे।
• पदानुक्रमित सुसंगति (Hierarchical Coherence): एक स्थिति जो यह सुनिश्चित करती है कि ऊपरी स्तर के फलन का डोमेन निचले स्तर के डोमेन के भीतर निहित है।

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

1. सामान्य समस्या सूत्रण: यह शोध पत्र [1, 57] के मौजूदा साहित्य का विस्तार करता है, जो संकुचित सेटों पर इंडिकेटर फंक्शन के बजाय संभावित रूप से अनंत-आयामी हिल्बर्ट स्पेस में सामान्य उत्तल कंपोजिट टर्म्स $\ell_1, \ell_2$ को संभालता है।
2. एल्गोरिद्मिक दक्षता: प्रस्तावित विधि को प्रति पुनरावृत्ति केवल एक बार $F_1, F_2$ के ऑपरेटर मूल्यांकन की आवश्यकता होती है, जो पूर्व कार्यों में उपयोग की जाने वाली डबल-कॉल एक्स्ट्राग्रेडिएंट विधियों की तुलना में बेहतर है।
3. जटिलता गारंटी (Complexity Guarantees): लेखक उपयुक्त रूप से निर्मित एर्गोडिक एवरेज (ergodic averages) का उपयोग करके व्यवहार्यता अंतराल (feasibility gap - निचला स्तर) और अनुकूलता अंतराल (optimality gap - पदानुक्रमित समस्या) दोनों के लिए वर्स्ट-केस इटरेशन कॉम्प्लेक्सिटी दरें स्थापित करते हैं।
4. संकुचन धारणा (Compactness Assumption) को हटाना: पिछले जटिलता विश्लेषणों के विपरीत, जिन्हें संकुचित डोमेन की आवश्यकता थी, यह कार्य बिना किसी संकुचित डोमेन की धारणा के, ज्यामितीय वीक शार्पनेस और एसिम्प्टोटिक विश्लेषण तकनीकों पर भरोसा करते हुए अभिसरण दर प्राप्त करता है।

मुख्य परिणाम
शोध पत्र एल्गोरिदम द्वारा उत्पन्न एर्गोडिक औसत $\bar{z}_K$ के लिए सबलीनियर अभिसरण दर स्थापित करता है। यह मानते हुए कि $\sigma_k = O(k^{-\delta})$ के साथ एक रेगुलराइजेशन अनुक्रम $\delta \in (0,1)$ है:

• व्यवहार्यता अंतराल (Feasibility Gap): निचले स्तर की समस्या के लिए गैप फंक्शन $O(k^{-\delta})$ की दर से अभिसरित होता है।
• अनुकूलता अंतराल (Optimality Gap): संपूर्ण पदानुक्रमित समस्या के लिए गैप फंक्शन $O(k^{-(1-\delta)})$ की दर से अभिसरित होता है।
• बेहतर दरें: इस धारणा के तहत कि ऊपरी स्तर का ऑपरेटर $F_1$ स्ट्रॉन्गली मोनोटोन है, शोध पत्र बेहतर दरें प्राप्त करता है, जो एक अद्वितीय समाधान की ओर अभिसरण को दर्शाता है।
• दुर्बल अभिसरण (Weak Convergence): ज्यामितीय वीक शार्पनेस स्थिति के तहत, पुनरावृत्तियों के अनुक्रम को $S_1$ में एक समाधान की ओर दुर्बल रूप से (weakly) अभिसरित होने के रूप में दिखाया गया है।

महत्व और दावे
लेखक दावा करते हैं कि उनके परिणाम इटरेशन कॉम्प्लेक्सिटी और समस्या सूत्रण की व्यापकता के मामले में अत्याधुनिक (state of the art) परिणामों से मेल खाते हैं और उनमें सुधार करते हैं। विशेष रूप से, शोध पत्र:

• सरल बाइलेवल ऑप्टिमाइज़ेशन और विशिष्ट VI मामलों से जटिलता गारंटी को अनंत-आयामी स्थानों में एक विस्तृत वर्ग के पदानुक्रमित HVI समस्याओं तक विस्तारित करता है।
• प्रदर्शित करता है कि "वीक शार्पनेस" की स्थिति, जिसे पहले मुख्य रूप से पदानुक्रमित अनुकूलन में उपयोग किया जाता था, को एकीकृत जटिलता कथनों को स्थापित करने के लिए वेरिएशनल सेटिंग में प्रभावी ढंग से अनुवादित किया जा सकता है।
• अनबाउंडेड डोमेन को संभालने के लिए नॉन-ऑटोनॉमस इवोल्यूशन इक्वेशन विश्लेषण तकनीकों का उपयोग करते हुए एक पद्धतिगत ढांचा प्रदान करता है, जो एक ऐसा योगदान है जिसे लेखक अन्य पदानुक्रमित संतुलन समस्याओं के लिए उपयोगी मान सकते हैं।

शोध पत्र यह नोट करते हुए समाप्त होता है कि जबकि वर्तमान विश्लेषण नियत (deterministic) सेटिंग्स को कवर करता है, भविष्य का कार्य स्टोकेस्टिक स्वरूपों और त्वरित विधियों (accelerated methods) की खोज कर सकता है। पदानुक्रमित नैश इक्विलिब्रियम और बाधित मिन-मैक्स समस्याओं (जीनरल एब्सोल्यूट वैल्यू इक्वेशंस सहित) पर संख्यात्मक प्रयोगों को सैद्धांतिक निष्कर्षों को मान्य करने के लिए प्रस्तुत किया गया है।