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

রিমানিয়ান ম্যানিফোল্ডে দ্বিস্তরীয় অপ্টিমাইজেশনের জন্য একটি অভিযোজনশীল অ্যালগরিদম

মৌলিক তথ্য

পেপার আইডি: 2504.06042
শিরোনাম: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
লেখক: Xu Shi, Rufeng Xiao, Rujun Jiang (ফুডান বিশ্ববিদ্যালয়ের ডেটা বিজ্ঞান কলেজ)
শ্রেণীবিভাগ: math.OC (অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
প্রকাশনা সম্মেলন: NeurIPS 2025 (৩৯তম নিউরাল ইনফরমেশন প্রসেসিং সিস্টেম সম্মেলন)
পেপার লিংক: 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 ইত্যাদি) ধাপের আকার নির্ধারণের জন্য দৃঢ় উত্তলতা পরামিতি, লিপশিৎজ ধ্রুবক এবং বক্রতা পরামিতি পূর্বে জানা প্রয়োজন
ব্যবহারিক সীমাবদ্ধতা: এই পরামিতিগুলি বাস্তব প্রয়োগে প্রায়শই অনুমান করা কঠিন বা গণনা খরচ অত্যধিক
অপর্যাপ্ত দৃঢ়তা: নির্দিষ্ট ধাপের আকার কৌশল প্রাথমিকীকরণ এবং সমস্যার শর্তের প্রতি সংবেদনশীল

গবেষণা প্রেরণা

এই পেপারের মূল প্রেরণা হল একটি সম্পূর্ণ অভিযোজনশীল RBO অ্যালগরিদম ডিজাইন করা যা:

সমস্যা-নির্দিষ্ট পরামিতি পূর্বে জানার প্রয়োজন নেই
সমস্যার বৈশিষ্ট্যের সাথে খাপ খাইয়ে নিতে স্বয়ংক্রিয়ভাবে ধাপের আকার সামঞ্জস্য করে
অ-অভিযোজনশীল পদ্ধতির সাথে তুলনীয় তাত্ত্বিক জটিলতা বজায় রাখে
শক্তিশালী ব্যবহারিক দৃঢ়তা প্রদান করে

মূল অবদান

প্রথম অভিযোজনশীল RBO অ্যালগরিদম: AdaRHD প্রস্তাব করা হয়েছে, যা প্রথম সম্পূর্ণ অভিযোজনশীল ধাপের আকার কৌশল ব্যবহার করে এমন রিমানিয়ান দ্বিস্তরীয় অপ্টিমাইজেশন অ্যালগরিদম, যা দৃঢ় উত্তলতা, লিপশিৎজ ধ্রুবক এবং বক্রতা পরামিতির উপর নির্ভরতা দূর করে
তাত্ত্বিক জটিলতা মিলান: প্রমাণ করা হয় যে 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-তে প্রথমবার সম্পূর্ণ অভিযোজন বাস্তবায়ন, কঠোর তাত্ত্বিক বিশ্লেষণ
ব্যবহারিক মূল্য: অ্যালগরিদমের দৃঢ়তা এবং ব্যবহারযোগ্যতা উল্লেখযোগ্যভাবে উন্নত করা
প্রযুক্তিগত গভীরতা: রিমানিয়ান জ্যামিতি দ্বারা আনা প্রযুক্তিগত চ্যালেঞ্জ সফলভাবে পরিচালনা করা
পরীক্ষা সম্পূর্ণ: একাধিক প্রয়োগ পরিস্থিতিতে ব্যাপক যাচাইকরণ

অসুবিধা

জটিলতা খরচ: অভিযোজনশীলতা অতিরিক্ত গণনা জটিলতার খরচে আসে
অনুমান সীমাবদ্ধতা: এখনও শক্তিশালী অনুমান শর্তাবলী প্রয়োজন
প্রয়োগের পরিধি: প্রধানত নির্দিষ্ট রিমানিয়ান ম্যানিফোল্ডে কেন্দ্রীভূত

প্রভাব

একাডেমিক অবদান: রিমানিয়ান অপ্টিমাইজেশন এবং দ্বিস্তরীয় অপ্টিমাইজেশনের ক্রস-ডোমেইনে গুরুত্বপূর্ণ অগ্রগতি প্রদান করা
ব্যবহারিক মূল্য: বাস্তব প্রয়োগে রিমানিয়ান দ্বিস্তরীয় অপ্টিমাইজেশনের জন্য আরও শক্তিশালী সরঞ্জাম প্রদান করা
পরবর্তী গবেষণা: আরও অভিযোজনশীল রিমানিয়ান অপ্টিমাইজেশন গবেষণার ভিত্তি স্থাপন করা

প্রযোজ্য পরিস্থিতি

রিমানিয়ান মেটা-লার্নিং এবং নিউরাল আর্কিটেকচার অনুসন্ধান
চিত্র বিভাজন এবং নিম্ন-র্যাঙ্ক অভিযোজন
শক্তিশালী পরিসংখ্যান এবং জ্যামিতিক মেশিন লার্নিং
ম্যানিফোল্ড সীমাবদ্ধতার অধীনে দ্বিস্তরীয় অপ্টিমাইজেশনের প্রয়োজন এমন যেকোনো প্রয়োগ

এই পেপারটি রিমানিয়ান দ্বিস্তরীয় অপ্টিমাইজেশন ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, প্রথমবার সম্পূর্ণ অভিযোজনশীল অ্যালগরিদম ডিজাইন বাস্তবায়ন করে, তাত্ত্বিক জটিলতা বজায় রেখে ব্যবহারিকতা এবং দৃঢ়তা উল্লেখযোগ্যভাবে উন্নত করে। যদিও নির্দিষ্ট জটিলতা খরচ রয়েছে, এর তাত্ত্বিক উদ্ভাবন এবং ব্যবহারিক মূল্য এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।