2025-11-21T05:43:14.438076

An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds

Shi, Xiao, Jiang

Existing methods for solving Riemannian bilevel optimization (RBO) problems require prior knowledge of the problem's first- and second-order information and curvature parameter of the Riemannian manifold to determine step sizes, which poses practical limitations when these parameters are unknown or computationally infeasible to obtain. In this paper, we introduce the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm for solving RBO problems. To our knowledge, AdaRHD is the first method to incorporate a fully adaptive step size strategy that eliminates the need for problem-specific parameters in RBO. We prove that AdaRHD achieves an $\mathcal{O}(1/Îµ)$ iteration complexity for finding an $Îµ$-stationary point, thus matching the complexity of existing non-adaptive methods. Furthermore, we demonstrate that substituting exponential mappings with retraction mappings maintains the same complexity bound. Experiments demonstrate that AdaRHD achieves comparable performance to existing non-adaptive approaches while exhibiting greater robustness.

academic

रीमैनियन मैनिफोल्ड्स पर द्विस्तरीय अनुकूलन के लिए एक अनुकूली एल्गोरिदम

मूल जानकारी

पेपर ID: 2504.06042
शीर्षक: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
लेखक: Xu Shi, Rufeng Xiao, Rujun Jiang (फुडान विश्वविद्यालय डेटा विज्ञान संस्थान)
वर्गीकरण: math.OC (अनुकूलन और नियंत्रण)
प्रकाशन सम्मेलन: NeurIPS 2025 (39वां तंत्रिका सूचना प्रसंस्करण प्रणाली सम्मेलन)
पेपर लिंक: https://arxiv.org/abs/2504.06042

सारांश

रीमैनियन द्विस्तरीय अनुकूलन (RBO) समस्याओं को हल करने के लिए मौजूदा विधियों को समस्या की प्रथम-क्रम, द्वितीय-क्रम जानकारी और रीमैनियन मैनिफोल्ड की वक्रता मापदंडों को पहले से जानने की आवश्यकता होती है ताकि चरण आकार निर्धारित किया जा सके। यह व्यावहारिक सीमाएं लाता है जब मापदंड अज्ञात या गणना योग्य नहीं होते हैं। यह पेपर RBO समस्याओं को हल करने के लिए अनुकूली रीमैनियन हाइपरग्रेडिएंट डिसेंट (AdaRHD) एल्गोरिदम प्रस्तावित करता है। हमारे ज्ञान के अनुसार, AdaRHD RBO में पूरी तरह से अनुकूली चरण आकार रणनीति अपनाने वाली पहली विधि है, जो समस्या-विशिष्ट मापदंडों की आवश्यकता को समाप्त करती है। हम सिद्ध करते हैं कि AdaRHD ε-स्थिर बिंदु खोजने के लिए O(1/ε) पुनरावृत्ति जटिलता प्राप्त करता है, जो मौजूदा गैर-अनुकूली विधियों की जटिलता से मेल खाता है। इसके अलावा, हम सिद्ध करते हैं कि घातीय मानचित्र को संकुचन मानचित्र से बदलने से भी समान जटिलता सीमा बनी रहती है। प्रयोग दिखाते हैं कि AdaRHD मौजूदा गैर-अनुकूली विधियों के समान प्रदर्शन प्राप्त करते हुए अधिक मजबूतता प्रदर्शित करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

द्विस्तरीय अनुकूलन समस्याओं का मशीन लर्निंग क्षेत्र में व्यापक अनुप्रयोग है, जिसमें सुदृढ़ीकरण सीखना, मेटा-लर्निंग, हाइपरपैरामीटर अनुकूलन, प्रतिकूल सीखना आदि शामिल हैं। रीमैनियन द्विस्तरीय अनुकूलन (RBO) रीमैनियन मैनिफोल्ड्स पर द्विस्तरीय अनुकूलन का विस्तार है, जिसका सामान्य रूप है:

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$ $\text{s.t. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

जहां $\mathcal{M}_x, \mathcal{M}_y$ रीमैनियन मैनिफोल्ड्स हैं, $f,g$ सुचिक्ण फलन हैं, और $g(x,y)$ $y$ के संबंध में भूगणितीय रूप से दृढ़ता से उत्तल है।

मौजूदा विधियों की सीमाएं

मापदंड निर्भरता: मौजूदा RBO विधियां (जैसे RHGD, RieBO आदि) को दृढ़ता से उत्तल मापदंड, Lipschitz स्थिरांक, वक्रता मापदंड आदि को पहले से जानने की आवश्यकता होती है
व्यावहारिक सीमाएं: ये मापदंड वास्तविक अनुप्रयोगों में अक्सर अनुमान लगाना कठिन या गणना करना महंगा होता है
अपर्याप्त मजबूतता: निश्चित चरण आकार रणनीति प्रारंभिकीकरण और समस्या स्थितियों के प्रति संवेदनशील होती है

अनुसंधान प्रेरणा

इस पेपर की मूल प्रेरणा एक पूरी तरह से अनुकूली RBO एल्गोरिदम डिजाइन करना है जो:

समस्या-विशिष्ट मापदंडों को पहले से जानने की आवश्यकता नहीं है
समस्या की विशेषताओं के अनुकूल चरण आकार को स्वचालित रूप से समायोजित करता है
गैर-अनुकूली विधियों के समान सैद्धांतिक जटिलता बनाए रखता है
अधिक मजबूत व्यावहारिक उपयोगिता प्रदान करता है

मुख्य योगदान

पहला अनुकूली RBO एल्गोरिदम: AdaRHD प्रस्तावित करता है, जो पूरी तरह से अनुकूली चरण आकार रणनीति अपनाने वाली पहली रीमैनियन द्विस्तरीय अनुकूलन एल्गोरिदम है, जो दृढ़ता से उत्तलता, Lipschitz स्थिरांक और वक्रता मापदंडों की निर्भरता को समाप्त करती है
सैद्धांतिक जटिलता मिलान: सिद्ध करता है कि AdaRHD ε-स्थिर बिंदु खोजने के लिए O(1/ε) पुनरावृत्ति जटिलता प्राप्त करता है, जो मौजूदा गैर-अनुकूली विधियों की जटिलता से मेल खाता है
संकुचन मानचित्र विस्तार: सिद्ध करता है कि घातीय मानचित्र को अधिक कुशल संकुचन मानचित्र से बदलने से भी समान जटिलता गारंटी बनी रहती है
प्रायोगिक सत्यापन: कई RBO समस्याओं पर एल्गोरिदम की प्रभावशीलता और मजबूतता को सत्यापित करता है, जिसमें रीमैनियन हाइपर-प्रतिनिधित्व सीखना और मजबूत अनुकूलन समस्याएं शामिल हैं

विधि विवरण

कार्य परिभाषा

रीमैनियन द्विस्तरीय अनुकूलन समस्या पर विचार करें:

ऊपरी-स्तर की समस्या: मैनिफोल्ड $\mathcal{M}_x$ पर $F(x) = f(x, y^*(x))$ को न्यूनतम करना
निचली-स्तर की समस्या: दिए गए $x$ के लिए, मैनिफोल्ड $\mathcal{M}_y$ पर $y^*(x) = \arg\min_y g(x,y)$ को हल करना
बाधाएं: $g(x,y)$ $y$ के संबंध में भूगणितीय रूप से दृढ़ता से उत्तल है, $f$ को उत्तलता की आवश्यकता नहीं है

मुख्य तकनीक: रीमैनियन हाइपरग्रेडिएंट

रीमैनियन हाइपरग्रेडिएंट को इस प्रकार परिभाषित किया गया है: $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

सटीक गणना कठिन होने के कारण, अनुमानित रीमैनियन हाइपरग्रेडिएंट का उपयोग किया जाता है: $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

जहां $\hat{y}$ निचली-स्तर की समस्या का अनुमानित समाधान है, $\hat{v}$ रैखिक प्रणाली का अनुमानित समाधान है।

AdaRHD एल्गोरिदम आर्किटेक्चर

एल्गोरिदम 1: AdaRHD मुख्य चरण

निचली-स्तर की समस्या का समाधान: अनुकूली ग्रेडिएंट डिसेंट का उपयोग
- चरण आकार अपडेट: $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
- पुनरावृत्ति अपडेट: $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
रैखिक प्रणाली का समाधान: दो रणनीतियां
- ग्रेडिएंट डिसेंट: निचली-स्तर की समस्या के समान अनुकूली चरण आकार
- संयुग्मित ग्रेडिएंट: स्पर्शरेखा स्थान संयुग्मित ग्रेडिएंट विधि का उपयोग
ऊपरी-स्तर का अपडेट: अनुकूली हाइपरग्रेडिएंट डिसेंट
- चरण आकार अपडेट: $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
- पुनरावृत्ति अपडेट: $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

तकनीकी नवाचार बिंदु

संचयी ग्रेडिएंट मानदंड रणनीति: "संचयी रीमैनियन ग्रेडिएंट मानदंड के व्युत्क्रम" को अनुकूली चरण आकार के रूप में अपनाता है, समस्या मापदंडों को पहले से जानने की आवश्यकता नहीं है
तीन-स्तरीय अनुकूलन: ऊपरी-स्तर, निचली-स्तर और रैखिक प्रणाली सभी के लिए अनुकूली चरण आकार, एक पूर्ण अनुकूली ढांचा बनाता है
संकुचन मानचित्र अनुकूलन: घातीय मानचित्र को संकुचन मानचित्र से बदलने का संस्करण प्रदान करता है, गणना जटिलता को कम करता है
सैद्धांतिक गारंटी: कठोर अभिसरण विश्लेषण, रीमैनियन मैनिफोल्ड्स की ज्यामिति द्वारा लाई गई तकनीकी चुनौतियों को संभालता है

प्रायोगिक सेटअप

डेटासेट और समस्याएं

सरल मैट्रिक्स समानता समस्या: Stiefel मैनिफोल्ड और SPD मैनिफोल्ड पर अनुकूलन
- डेटा आकार: n=100 और n=1000
- मापदंड सेटिंग: d=50, r=20, λ=0.01
गहन हाइपर-प्रतिनिधित्व सीखना: AFEW भावना पहचान डेटासेट
- 3-स्तरीय SPD नेटवर्क आर्किटेक्चर
- 7 भावना श्रेणियां, 1747 प्रशिक्षण नमूने
- असंतुलित वर्ग वितरण
मजबूत अनुकूलन समस्याएं:
- मजबूत Karcher माध्य समस्या
- मजबूत अधिकतम संभावना अनुमान समस्या

तुलना विधियां

RHGD-20/50: रीमैनियन हाइपरग्रेडिएंट डिसेंट, निचली-स्तर की समस्या के लिए अधिकतम 20/50 पुनरावृत्तियां
AdaRHD-GD: रैखिक प्रणाली को हल करने के लिए ग्रेडिएंट डिसेंट का उपयोग करने वाला AdaRHD
AdaRHD-CG: रैखिक प्रणाली को हल करने के लिए संयुग्मित ग्रेडिएंट का उपयोग करने वाला AdaRHD

मूल्यांकन मेट्रिक्स

ऊपरी-स्तर का उद्देश्य फलन मान
हाइपरग्रेडिएंट अनुमान त्रुटि
सत्यापन सटीकता
अभिसरण समय और पुनरावृत्ति संख्या

प्रायोगिक परिणाम

मुख्य परिणाम

सरल समस्या प्रयोग:

AdaRHD दोनों डेटा आकारों पर तेजी से अभिसरण प्रदर्शित करता है
हाइपरग्रेडिएंट अनुमान त्रुटि कम है, विशेष रूप से AdaRHD-CG
गणना समय में लाभ है, विशेष रूप से बड़ी समस्याओं पर

मजबूतता विश्लेषण:

विभिन्न प्रारंभिक चरण आकार सेटिंग्स के तहत, AdaRHD उल्लेखनीय मजबूतता प्रदर्शित करता है
RHGD बड़े चरण आकार (5, 1, 0.5) पर विफल होता है, जबकि AdaRHD स्थिर रूप से अभिसरित होता है
AdaRHD-CG 85% सत्यापन सटीकता तक पहुंचने में सबसे तेज है

मुख्य निष्कर्ष

मजबूतता लाभ: AdaRHD प्रारंभिक चरण आकार चयन के प्रति असंवेदनशील है, जबकि RHGD अनुपयुक्त चरण आकार पर पूरी तरह विफल होता है
दक्षता सुधार: हालांकि AdaRHD को अधिक बाहरी पुनरावृत्तियों की आवश्यकता होती है, अनुकूली रणनीति के कारण कुल गणना समय अभी भी प्रतिस्पर्धी है
विधि चयन: AdaRHD-CG सटीकता और मजबूतता दोनों में AdaRHD-GD से बेहतर है, लेकिन बाद वाला प्रारंभिक अभिसरण में तेजी से है

सैद्धांतिक विश्लेषण

जटिलता परिणाम

प्रमेय 3.1: मानक मान्यताओं के तहत, AdaRHD संतुष्ट करता है: $\frac{1}{T}\sum_{t=0}^{T-1} \|G_F(x_t)\|^2_{x_t} \leq \frac{C}{T} = O\left(\frac{1}{T}\right)$

परिणाम 3.1: ε-स्थिर बिंदु तक पहुंचने की जटिलता:

कुल पुनरावृत्तियां: T = O(1/ε)
ग्रेडिएंट जटिलता: $G_f = O(1/ε)$ , $G_g = O(1/ε^2)$
Hessian-वेक्टर उत्पाद जटिलता: AdaRHD-GD के लिए O(1/ε²), AdaRHD-CG के लिए Õ(1/ε)

तकनीकी चुनौतियां

ज्यामितीय संरचना: रीमैनियन मैनिफोल्ड्स की वक्रता अतिरिक्त विश्लेषण जटिलता लाती है
त्रिकोण दूरी सीमाएं: यूक्लिडियन समकक्षों के बजाय रीमैनियन मैनिफोल्ड्स के लिए विशिष्ट त्रिकोण दूरी सीमाओं का उपयोग करना आवश्यक है
अनुकूली चरण आकार विश्लेषण: अनुकूली रणनीति प्रारंभ में विचलन व्यवहार का कारण बन सकती है, कठोर सैद्धांतिक उपचार की आवश्यकता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

AdaRHD पहली पूरी तरह से अनुकूली रीमैनियन द्विस्तरीय अनुकूलन एल्गोरिदम है, जो समस्या-विशिष्ट मापदंडों की निर्भरता को समाप्त करती है
सैद्धांतिक रूप से गैर-अनुकूली विधियों के समान O(1/ε) जटिलता प्राप्त करता है
प्रयोग एल्गोरिदम की प्रभावशीलता और उल्लेखनीय मजबूतता लाभों को सत्यापित करते हैं

सीमाएं

जटिलता अंतर: ग्रेडिएंट और Hessian-वेक्टर उत्पाद जटिलता में गैर-अनुकूली विधियों से 1/ε गुना अधिक
मान्यता शर्तें: अभी भी निचली-स्तर की समस्या की भूगणितीय दृढ़ता से उत्तलता की आवश्यकता है
एकल-लूप बनाम दोहरा-लूप: वर्तमान में केवल दोहरे-लूप एल्गोरिदम पर विचार किया गया है

भविष्य की दिशाएं

एकल-लूप एल्गोरिदम: अनुकूली एकल-लूप रीमैनियन द्विस्तरीय अनुकूलन एल्गोरिदम डिजाइन करना
यादृच्छिक सेटिंग: यादृच्छिक रीमैनियन द्विस्तरीय अनुकूलन तक विस्तार करना
कमजोर उत्तलता: भूगणितीय उत्तलता (गैर-दृढ़ता से उत्तल) निचली-स्तर के उद्देश्य को संभालना
जटिलता अनुकूलन: 1/ε अंतर को समाप्त करने वाली अनुकूली रणनीतियों की खोज करना

गहन मूल्यांकन

शक्तियां

सैद्धांतिक नवाचार: RBO में पहली बार पूरी तरह से अनुकूली प्राप्त करना, कठोर सैद्धांतिक विश्लेषण
व्यावहारिक मूल्य: एल्गोरिदम की मजबूतता और उपयोग में आसानी में उल्लेखनीय सुधार
तकनीकी गहराई: रीमैनियन ज्यामिति द्वारा लाई गई तकनीकी चुनौतियों को सफलतापूर्वक संभालना
पर्याप्त प्रयोग: कई अनुप्रयोग परिदृश्यों का व्यापक सत्यापन

कमियां

जटिलता लागत: अनुकूलन अतिरिक्त गणना जटिलता की कीमत पर आता है
मान्यता सीमाएं: अभी भी मजबूत मान्यता शर्तों की आवश्यकता है
अनुप्रयोग सीमा: मुख्य रूप से विशिष्ट रीमैनियन मैनिफोल्ड्स पर केंद्रित

प्रभाव

शैक्षणिक योगदान: रीमैनियन अनुकूलन और द्विस्तरीय अनुकूलन के अंतर-अनुशासनात्मक क्षेत्र में महत्वपूर्ण प्रगति
व्यावहारिक मूल्य: वास्तविक अनुप्रयोगों में रीमैनियन द्विस्तरीय अनुकूलन के लिए अधिक मजबूत उपकरण प्रदान करता है
अनुवर्ती अनुसंधान: आगे की अनुकूली रीमैनियन अनुकूलन अनुसंधान के लिए आधार स्थापित करता है

लागू परिदृश्य

रीमैनियन मेटा-लर्निंग और तंत्रिका आर्किटेक्चर खोज
छवि विभाजन और निम्न-रैंक अनुकूलन
मजबूत सांख्यिकी और ज्यामितीय मशीन लर्निंग
कोई भी अनुप्रयोग जिसमें मैनिफोल्ड बाधाओं के तहत द्विस्तरीय अनुकूलन की आवश्यकता होती है

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