तकनीकी सारांश: नियततम एकीकरण समय के साथ हैमिल्टोनियन डायनेमिक्स के माध्यम से त्वरित उत्तल अनुकूलन (Accelerated Convex Optimization)

समस्या विवरण

यह शोध पत्र प्रथम-क्रम उत्तल अनुकूलन (first-order convex optimization) की समस्या को संबोधित करता है, विशेष रूप से एक अवकलनीय (differentiable) उत्तल फलन $f: \mathbb{R}^d \to \mathbb{R}$ को न्यूनतम करने के लिए, जहाँ $\nabla f$ तक पहुँच उपलब्ध है। लेखक सुचारू उत्तल (smooth convex) और $\alpha$-दृढ़ उत्तल ( $\alpha$-strongly convex) उद्देश्यों के लिए त्वरित अभिसरण दरों (accelerated rates of convergence) प्राप्त करने पर ध्यान केंद्रित करते हैं।

जबकि क्लासिकल ग्रेडिएंट डिसेंट सुलभ उत्तल फलनों के लिए $O(1/\epsilon)$ और दृढ़ उत्तल फलनों के लिए $O(\log(1/\epsilon))$ की अभिसरण दर प्राप्त करता है, नेस्टरोव का त्वरित ग्रेडिएंट विधि (Nesterov's accelerated gradient method) इन्हें क्रमशः $O(1/\sqrt{\epsilon})$ और $O(\sqrt{\kappa}\log(1/\epsilon))$ में सुधार कर देती है। हाल के कार्यों ने अक्सर द्वितीय-क्रम के अवकल समीकरणों (second-order differential equations) का उपयोग करते हुए, निरंतर-समय गतिशील प्रणालियों (continuous-time dynamical systems) के माध्यम से इन दरों को प्राप्त करने का प्रयास किया है। हालाँकि, हैमिल्टोनियन डायनेमिक्स-आधारित मौजूदा दृष्टिकोण सीमित रहे हैं:

1. उन्हें अक्सर द्विघात (quadratic) फलन की आवश्यकता होती है।
2. सामान्य उत्तल फलनों पर लागू होने पर, पिछले गारंटी (जैसे फु और विबिसोनो, 2025) स्टोकेस्टिक (stochastic) थे, जो यादृच्छिक एकीकरण समय (randomized integration times) पर अपेक्षा (expectation) के रूप में ही मान्य थे।
3. वे आमतौर पर प्रक्षेपवक्र (trajectory) के अंत बिंदु (endpoint) पर निर्भर करते हैं, जो विशिष्ट संरचनात्मक धारणाओं के बिना सामान्य उत्तल फलनों के लिए त्वरण प्रदान नहीं करता है।

लक्ष्य एक नियततम (deterministic), हैमिल्टोनियन डायनेमिक्स-आधारित एल्गोरिदम विकसित करना है जो विशिष्ट संरचनात्मक धारणाओं या रैंडमाइजेशन पर निर्भर किए बिना, सामान्य सुचारू उत्तल और दृढ़ उत्तल फलनों के लिए इष्टतम प्रथम-क्रम जटिलता प्राप्त कर सके।

कार्यप्रणाली (Methodology)

प्रस्तावित दृष्टिकोण हैमिल्टोनियन फ्लो (HF) का लाभ उठाता है, लेकिन यह अनुकूलन के लिए प्रक्षेपवक्रम (trajectory) का उपयोग करने के तरीके पर एक नया दृष्टिकोण पेश करता है।

1. हैमिल्टोनियन डायनेमिक्स ढांचा

लेखक चरण स्थान (phase space) $\mathbb{R}^{2d}$ (स्थिति $X_t$ और वेग $Y_t$) पर एक ऊर्जा फलन के साथ एक हैमिल्टोनियन प्रणाली को परिभाषित करते हैं:
$$H(x, y) = f(x) + \frac{1}{2}\|y\|^2$$
गतिशीलता निम्नलिखित द्वारा नियंत्रित होती है:
$$\dot{X}_t = Y_t, \quad \dot{Y}_t = -\nabla f(X_t)$$
इस प्रणाली का एक प्रमुख गुण ऊर्जा संरक्षण (energy conservation) है: $f(X_t) + \frac{1}{2}\|Y_t\|^2 = f(X_0) + \frac{1}{2}\|Y_0\|^2$। यदि इसे $Y_0=0$ के साथ प्रारंभ किया जाता है, तो फलन मान $f(X_t)$ कभी भी $f(X_0)$ से अधिक नहीं होता है।

2. मुख्य अंतर्दृष्टि: औसत बनाम अंत बिंदु (Averaging vs. Endpoints)

मुख्य सैद्धांतिक योगदान यह अवलोकन है कि हैमिल्टोनियन प्रक्षेपवक्रम के साथ समय-औसत स्थिति (time-averaged position), प्रक्षेपवक्रम के अंत बिंदु की तुलना में अधिक मजबूत अवरोहण गारंटी (descent guarantee) प्रदान करती है।

• लेम्मा 2 (Lemma 2) एक अवकल असमानता (differential inequality) स्थापित करता है जो दिखाता है कि प्रक्षेपवक्रम का औसत अनुकूलता अंतराल (optimality gap) को संकुचित करता है।
• कोरोलरी 1 (Corollary 1) यह प्रदर्शित करता है कि स्थितियों का एक विशिष्ट भारित औसत (weighted average), जिसे $X_{\text{avg}}(X_0; T) = \frac{2}{T^2} \int_0^T (T-t)X_t dt$ के रूप में परिभाषित किया गया है, एक संकुचन गुण (contraction property) प्रदर्शित करता है:
  $$f(X_{\text{avg}}) - f(z) + \frac{1}{3T^2}\|X_T - z\|^2 \leq \frac{2}{3}(f(X_0) - f(z)) + \frac{1}{3T^2}\|X_0 - z\|^2$$
  यह यह दर्शाता है कि यदि एकीकरण समय $T$ को उचित रूप से चुना जाता है, तो यह अनुकूलता अंतराल के लिए एक सार्वभौमिक संकुचन कारक $2/3$ प्रदान करता है।

3. एल्गोरिदम डिज़ाइन

लेखक इस अंतर्दृष्टि के आधार पर दो एल्गोरिदम प्रस्तावित करते हैं:

• HFA (एवरेजिंग के साथ अनुकूलन के लिए हैमिल्टोनियन फ्लो): एक आदर्श निरंतर-समय एल्गोरिदम। यह वर्तमान इटरट (iterate) को चरण स्थान में ऊपर उठाता है, सटीक हैमिल्टोनियन फ्लो के लिए समय $T_k$ तक सिमुलेशन करता है, प्रक्षेपवक्रम के भारित औसत की गणना करता है, और वैकल्पिक रूप से इस औसत को अगले इटरट बनाने के लिए अंत बिंदु के साथ मिश्रित करता है।

  • दृढ़ उत्तल (strongly convex) फलनों के लिए, एल्गोरिदम केवल भारित औसत ($\lambda=0$) का उपयोग करता है।
  • उत्तल (convex) फलनों के लिए, यह द्विघात वृद्धि की कमी को संभालने के लिए औसत और अंत बिंदु का मिश्रण ($\lambda=1$) उपयोग करता है।

• dHFA-eg (एक्स्ट्राग्रेडिएंट के साथ विविक्त HFA): एक व्यावहारिक विविक्त-समय (discrete-time) कार्यान्वयन। चूंकि HF का सटीक सिमुलेशन सामान्यतः असंभव है, लेखक प्रवाह को एक्स्ट्राग्रेडिएंट इंटीग्रेटर (extragradient integrator) का उपयोग करके विविक्त (discretize) करते हैं (जो एक इनडायरेक्ट इंटीग्रेटर का अनुमान लगाने वाला प्रथम-क्रम विधि है)।

  • निरंतर समाकलन (integral) को एक विविक्त भारित योग (discrete weighted sum) से बदल दिया जाता है।
  • एल्गोरिदम समान संरचना बनाए रखता है: $N_k$ चरणों का अनुकरण करें, विविक्त भारित औसत की गणना करें, और अंतिम इटरट के साथ मिश्रित करें।

मुख्य योगदान

1. एवरेजिंग के माध्यम से नियततम त्वरण: शोध पत्र सिद्ध करता है कि हैमिल्टोनियन डायनेमिक्स-आधारित विधियाँ सामान्य सुचारू उत्तल और दृढ़ उत्तल फलनों के लिए नियततम (deterministically) रूप से त्वरित अभिसरण दरें प्राप्त कर सकती हैं। यह पिछले कार्यों (फु और विबिसोनो, 2025) के विपरीत है जिन्हें समान दरें अपेक्षा के रूप में प्राप्त करने के लिए यादृच्छिक एकीकरण समय की आवश्यकता थी।
2. नया संकुचन लेम्मा (Contraction Lemma): लेखक लेम्मा 2 और कोरोलरी 1 को औपचारिक रूप देते हैं, जो यह स्थापित करते हैं कि हैमिल्टोनियन प्रक्षेपवक्रम का समय-औसत अनुकूलता अंतराल को $2/3$ के कारक से संकुचित करता है (एक अवशेष पद के साथ)। यह गुण पहले सामान्य उत्तल उद्देश्यों के लिए स्थापित नहीं किया गया था।
3. इष्टतम जटिलता: प्रस्तावित विविक्त एल्गोरिदम, dHFA-eg, नेस्टरोव की त्वरित ग्रेडिएंट विधि के समान इटरेशन जटिलता प्राप्त करता है:
   • दृढ़ उत्तल: $O(\sqrt{\kappa} \log(1/\epsilon))$ ग्रेड मूल्यांकन।
   • उत्तल: $O(\sqrt{L/\epsilon})$ ग्रेड मूल्यांकन।
     यहाँ, $\kappa = L/\alpha$ है।
4. व्यावहारिक विवक्तीकरण (Practical Discretization): यह कार्य एक्स्ट्राग्रेडिएंट इंटीग्रेटर का उपयोग करके निरंतर-समय गतिशील प्रणालियों और कार्यान्वयन योग्य प्रथम-क्रम एल्गोरिदम के बीच के अंतर को पाटता है, जिसके लिए केवल ग्रेडिएंट एक्सेस की आवश्यकता होती है (कोई प्रॉक्सिमल ऑरेकल नहीं)।

परिणाम

शोध पत्र प्रस्तावित एल्गोरिदम के लिए कठोर सैद्धांतिक गारंटी प्रदान करता है:

• दृढ़ उत्तल मामला: उन फलनों के लिए जो $\alpha$-द्विघात वृद्धि ( $\alpha$-strong convexity द्वारा निहित) को संतुष्ट करते हैं, एक स्थिर एकीकरण समय (या विवक्तीकरण चरणों) $T \propto 1/\sqrt{\alpha}$ के साथ HFA (या dHFA-eg) चलाने से ज्यामितीय अभिसरण दर प्राप्त होती है। प्रमेय 1 और प्रमेय 3 दिखाते हैं कि त्रुटि $(2/3 + \delta)^K$ के रूप में घटती है, जिससे इष्टतम $O(\sqrt{\kappa} \log(1/\epsilon))$ जटिलता प्राप्त होती है।
• उत्तल मामला: सामान्य उत्तल फलनों के लिए, एल्गोरिदम को ज्यामितीय रूप से बढ़ते हुए एकीकरण समय $T_k$ (या विवक्तीकरण चरणों $N_k$) की आवश्यकता होती है। प्रमेय 2 और प्रमेय 4 दिखाते हैं कि प्रति इटरेशन बढ़ती हुई लागत के बावजूद, $\epsilon$-सटीकता तक पहुँचने के लिए कुल जटिलता $O(1/\sqrt{\epsilon})$ है।
• नियततम गारंटी: सभी अभिसरण सीमाएँ एल्गोरिदम के प्रत्येक निष्पादन के लिए मान्य हैं, न कि केवल अपेक्षा (expectation) के रूप में।

महत्व और दावे

लेखक दावा करते हैं कि यह कार्य नियततम त्वरित उत्तल अनुकूलन के लिए एक उपयोगी एल्गोरिद्मिक प्रिमिटिव (algorithmic primitive) के रूप में हैमिल्टोनियन डायनेमिक्स को स्थापित करता है।

• प्रतिमान परिवर्तन (Paradigm Shift): यह कार्य परिप्रेक्ष्य को "सैंपलिंग के रूप में अनुकूलन" (अनुकूलन विचारों का उपयोग करके सैंपलिंग में सुधार करना) से "सैंपलिंग विचारों के माध्यम से अनुकूलन" (अनुकूलन में सुधार के लिए हैमिल्टोनियन फ्लो अवधारणाओं का उपयोग करना) की ओर स्थानांतरित करता है।
• मजबूती (Robustness): पिछले हैमिल्टोनियन-आधारित अनुकूलन विधियों के विपरीत जो द्विघात फलनों तक सीमित थीं या जिन्हें रैंडमाइजेशन की आवश्यकता थी, यह दृष्टिकोण नियततम गारंटियों के साथ सामान्य सुचारू उत्तल फलनों के लिए कार्य करता है।
• सैद्धांतिक आधार: शोध पत्र एक नई अवकल असमानता (लेम्मा 2) प्रदान करता है जो यह स्पष्ट करती है कि प्रक्षेपवक्रम का औसत (averaging) क्यों काम करता है, जो निरंतर-समय गतिशीलता और विविक्त त्वरित विधियों के बीच संबंध की गहरी समझ प्रदान करता है।

लेखक नोट करते हैं कि हालांकि उनका विश्लेषण उत्तल फलनों पर केंद्रित है, इन तकनीकों के गैर-उत्तल (non-convex) अनुकूलन और त्वरित सैंपलिंग (HMC) के लिए निहितार्थ हो सकते हैं, हालांकि ये भविष्य की दिशाओं के रूप में छोड़े गए हैं। शोध पत्र यह दावा नहीं करता है कि यह नेस्टरोव की विधि की तुलना में एसिम्प्टोटिक जटिलता में बेहतर प्रदर्शन करता है, बल्कि यह एक वैकल्पिक, डायनेमिक्स-आधारित व्युत्पत्ति प्रदान करता है जो समान इष्टतम दरें नियततम रूप से प्राप्त करता है।