A $\sqrt{2}$-accelerated FISTA for composite strongly convex problems

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। यह सिर्फ कोई साधारण घाटी नहीं है; यह एक गणितीय परिदृश्य है जहाँ ज़मीन दो अलग-अलग सामग्रियों से बनी है। उसका एक हिस्सा चिकना और फिसलन भरा है, जैसे कि एक पॉलिश किया हुआ बर्फ का मैदान हो। दूसरा हिस्सा ऊबड़-खाबड़, पथरीला और अचानक आने वाली चट्टानों से भरा है, जैसे कि एक पथरीला पहाड़ी रास्ता। इस "घाटी" का अर्थ कंप्यूटर विज्ञान और डेटा की दुनिया में एक जटिल समस्या को हल करना है, जैसे कि किसी चेहरे को पहचानने के लिए एक स्मार्ट AI को प्रशिक्षित करना या किसी बड़ी इमेज को कंप्रेस करने का सबसे अच्छा तरीका खोजना। चिकना हिस्सा आमतौर पर उस डेटा का प्रतिनिधित्व करता है जो हमारे पास है, जबकि ऊबड़-खाबड़ हिस्सा उन नियमों का प्रतिनिधित्व करता है जिनका हमें पालन करना है, जैसे कि समाधान को सरल या स्पार्स (sparse) रखना।

इस घाटी के निचले हिस्से तक पहुँचने के लिए, कंप्यूटर एक रणनीति का उपयोग करते हैं जिसे "ग्रेडिएंट डिसेंट" (gradient descent) कहा जाता है। इसे एक हाइकर (पर्वतारोही) के रूप में सोचें जो उस दिशा में कदम बढ़ाता है जो उसे सबसे अधिक ढलान वाली लगती है। यदि ज़मीन चिकनी है, तो हाइकर तेज़ी से फिसल सकता है। लेकिन यदि ज़मीन ऊबड़-खाबड़ है, तो हाइकर को रुकना होगा, सावधानी से आसपास महसूस करना होगा और एक सतर्क कदम उठाना होगा। दशकों तक, विज्ञान में ज्ञात सबसे अच्छे हाइकर (एल्गोरिदम) नीचे तक पहुँच सकते थे, लेकिन वे कभी-कभी बहुत लंबा समय लेते थे, खासकर यदि घाटी कठिन हो। वे टेढ़े-मेढ़े चलते थे, लक्ष्य से आगे निकल जाते थे, या छोटे गड्ढों में फंस जाते थे। मुख्य सवाल जो शोधकर्ताओं के मन में हमेशा रहा है, वह था: "क्या हम एक ऐसा हाइकर बना सकते हैं जो न केवल ऊबड़-खाबड़ रास्तों पर सावधान हो, बल्कि चिकने हिस्सों पर अविश्वसनीय रूप से तेज़ भी हो, और रास्ता न भटके?"

यह पेपर एक नए, सुपर-चार्ज्ड हाइकर SR2-FISTA को पेश करता है। लेखक, कानसेई उशियामा ने एक ऐसा तरीका डिज़ाइन किया है जो इस मिश्रित इलाके से पहले की किसी भी ज्ञात तकनीक की तुलना में अधिक तेज़ी से गुजरता है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने एक निरंतर, बहती हुई गति (जैसे कि ढलान की ओर बहती एक नदी) को चरणों की एक श्रृंखला में बदलकर अपना नया हाइकर बनाया जिसे एक कंप्यूटर ले सकता है। उनका मुख्य निष्कर्ष यह है कि यह नया एल्गोरिदम पुराने चैंपियनों की तुलना में काफी तेज़ी से घाटी के निचले हिस्से तक पहुँचता है, विशेष रूप से जब घाटी का आकार विशिष्ट होता है जो इसे "स्ट्रॉन्गली कॉनवेक्स" (strongly convex) बनाता है (अर्थात यह ऊपर की ओर तीव्रता से मुड़ता है, जो एक स्पष्ट, एकल निचले बिंदु की गारंटी देता है)।

यह पेपर गणितीय रूप से सिद्ध करता है कि यह नई विधि एक विशिष्ट कारक के माध्यम से तेज़ है जिसमें 2 का वर्गमूल (लगभग 1.41 गुना तेज़) शामिल है। सरल शब्दों में, यदि पुराने सबसे अच्छे तरीके को उत्तर के करीब पहुँचने में 100 कदम लगे, तो यह नया तरीका कम कदमों में वहाँ पहुँच सकता है, या समान समय में अधिक सटीक उत्तर दे सकता है। लेखक यह भी दिखाते हैं कि उनका तरीका तब भी काम करता है जब घाटी का "ऊबड़-खाबड़" हिस्सा थोड़ा अजीब या "वीकली कॉनवेक्स" (weakly convex) हो (एक तकनीकी तरीका कहने का कि यह पूरी तरह से ऊबड़-खाबड़ नहीं है लेकिन इसमें कुछ कोमल वक्र हैं), जो मेडिकल इमेजिंग या वित्तीय मॉडलिंग जैसे वास्तविक दुनिया के परिदृश्यों में एक सामान्य स्थिति है। उन्होंने इसे केवल कंप्यूटर पर सिम्युलेट नहीं किया; उन्होंने एक कठोर गणितीय प्रमाण प्रदान किया कि उनका हाइकर हमेशा नीचे का रास्ता खोज लेगा, और उन्होंने यह भी दिखाया कि वे उन मामलों को कैसे संभाल सकते हैं जहाँ कंप्यूटर को ठीक से पता नहीं होता कि चिकना हिस्सा कितना फिसलन भरा है।

इस पेपर की कहानी

समस्या: मिश्रित-इलाके वाली घाटी
यह पेपर एक क्लासिक ऑप्टिमाइज़ेशन समस्या को संबोधित करता है: एक फलन $f(x)$ का न्यूनतम मान खोजना जो $g(x)$ और $h(x)$ के दो भागों का योग है।

• $g(x)$ "चिकना" भाग है। एक चिकनी, लुढ़कती हुई पहाड़ी की कल्पना करें। इस पर फिसलना आसान है, लेकिन यह बहुत चौड़ी हो सकती है।
• $h(x)$ "ऊबड़-खाबड़" भाग है। ऊबड़-खाबड़ चट्टानों या एक दीवार की कल्पना करें। आप इस पर सुचारू रूप से नहीं फिसल सकते; आपको कूदना या सावधानी से कदम रखना होगा।
• लक्ष्य: वह पूर्ण निचला बिंदु खोजना जहाँ ये दोनों मिलते हैं।

वास्तविक दुनिया में, यह हर समय होता है। उदाहरण के लिए, LASO (सांख्यिकी में उपयोग की जाने वाली एक विधि) में, $g(x)$ एक भविष्यवाणी और वास्तविक डेटा के बीच की त्रुटि (चिकना) हो सकती है, जबकि $h(x)$ बहुत अधिक वेरिएबल्स होने के लिए एक दंड (penalty) है (ऊबड़-खाबड़, जैसे कि एक तीखा कोना)। चुनौती यह है कि मानक विधियाँ अक्सर चिकने भाग पर गति और ऊबड़-खाबड़ भाग पर सावधानी के बीच संतुलन बनाने में संघर्ष करती हैं।

पुराने चैंपियन और उनकी खामियां
वर्षों से, "फास्ट इटरेटिव श्रिंकेज/थ्रेशोल्डिंग एल्गोरिदम" (FISTA) स्वर्ण मानक रहा है। यह एक ऐसे हाइकर की तरह है जो चिकने हिस्सों पर गति बढ़ाने के लिए मोमेंटम (momentum) का उपयोग करता है लेकिन चट्टानों पर अपने पैरों की पकड़ की जांच करने के लिए रुक जाता है। यह तेज़ है, लेकिन इसकी एक सीमा है।
वहाँ ADR (एक्सेलरेटेड डुअल रेगुलराइजेशन) नामक एक विधि भी थी जिसने दावा किया था कि वह अधिक तेज़ है। हालाँकि, पेपर बताता है कि जबकि ADR अच्छा है, यह बिल्कुल सबसे तेज़ नहीं है। लेखक नोट करते हैं कि पिछली विधियों की एक "गति सीमा" थी जो घाटी की चिकनाई और वक्रता के अनुपात के वर्गमूल से जुड़े एक विशिष्ट सूत्र द्वारा निर्धारित होती थी।

नई खोज: SR2-FISTA
लेखक एक नया एल्गोरिदम प्रस्तावित करते हैं, जिसे वे SR2-FISTA (स्क्वायर रूट 2 स्ट्रॉन्गली कॉनवेक्स FISTA) कहते हैं।

• उन्होंने इसे कैसे बनाया: पुराने चरणों को केवल बदलने के बजाय, उन्होंने भौतिकी के लेंस के माध्यम से समस्या को देखा। उन्होंने एक निरंतर-समय मॉडल (एक समीकरण जो समय के माध्यम से एक कण के संचलन का वर्णन करता है) से शुरुआत की जिसे ITEM (इंफॉर्मेशन-थ्योरेटिक एक्जैक्ट मेथड) कहा जाता है। यह मॉडल एक कण के ढलान से नीचे गिरने का वर्णन करता है जिसमें एक बहुत ही विशिष्ट, बदलती हुई घर्षण (friction) होती है।
• जादुई सामग्री: इस मॉडल में घर्षण स्थिर नहीं है; यह एक हाइपरबोलिक कोटेंजेंट फंक्शन (एक फैंसी गणितीय वक्र) द्वारा वर्णित तरीके से समय के साथ बदलता है। इस चिकनी, बहती हुई गति को उन चरणों में सावधानीपूर्वक "डिस्क्रीटाइज" (विभाजित) करके, उन्होंने एक नया एल्गोरिदम बनाया जिसे कंप्यूटर ले सकता है।
• परिणाम: पेपर सिद्ध करता है कि यह नया एल्गोरिदम FISTA और ADR की तुलना में तेज़ दर से अभिसरण (converge) करता है। विशेष रूप से, इसकी गति के सूत्र में "एक्सपोनेंट" (exponent) $\sqrt{2}$ के कारक से बेहतर हो जाता है।
  • यदि पुराने तरीके 100 मील प्रति घंटे की गति से चलने वाली कार की तरह थे, तो यह नया तरीका एक ऐसी कार की तरह है जो समय के साथ बढ़ते हुए प्रभाव के साथ तेज़ चलती है, जिससे वह गंतव्य तक काफी पहले पहुँच जाती है।
  • पेपर एक प्रमाण (Theorem 6) प्रदान करता है जो दिखाता है कि त्रुटि (निचले बिंदु से दूरी) प्रति चरण लगभग $(1 + \sqrt{2q})^{-k}$ के कारक से घटती है, जहाँ $q$ इस बात का माप है कि घाटी कितनी "स्ट्रॉन्गली" मुड़ती है। यह पिछले सर्वोत्तम ज्ञात दर $(1 + \sqrt{2q} - 6q)^{-k}$ से तेज़ है।

"अजीब" चट्टानों को संभालना
इस पेपर की एक अनूठी विशेषता यह है कि यह उन मामलों को भी संभालता है जहाँ "ऊबड़-खाबड़" भाग ($h(x)$) पूरी तरह से कॉनवेक्स नहीं है। गणितीय शब्दों में, $h(x)$ "वीकली कॉनवेक्स" (weakly convex) हो सकता है (यह थोड़ा गलत दिशा में मुड़ सकता है, लेकिन इतना नहीं कि पूरे समस्या को खराब कर दे)।

• कई पुरानी विधियों के लिए आवश्यक था कि उपयोगकर्ता समस्या को फिर से लिखे ताकि ऊबड़-खाबड़ भाग को "अच्छा" (कॉनवेक्स) बनाया जा सके।
• लेखक का तरीका मूल समस्या पर सीधे काम करता है। वे दिखाते हैं कि भले ही ऊबड़-खाबड़ भाग थोड़ा "लहराता" हो, जब तक कि कुल योग अभी भी कॉनवेक्स है (घाटी में अभी भी एक निचला बिंदु है), उनका एल्गोरिदम काम करता है। यह एक बड़ी बात है क्योंकि इसका मतलब है कि आपको इस टूल का उपयोग करने के लिए अतिरिक्त गणितीय होमवर्क करने की आवश्यकता नहीं है; आप बस अपनी अव्यवस्थित, वास्तविक दुनिया की समस्या को सीधे डाल सकते हैं।

प्रमाण और संख्याएँ
लेखक अपने परिणामों को लेकर बहुत आश्वस्त हैं। उन्होंने केवल एक सिमुलेशन नहीं चलाया और यह नहीं कहा कि, "हे, यह तेज़ दिखता है।" उन्होंने एक कठोर गणितीय प्रमाण (एक 'ल्यपुनोव फंक्शन' का उपयोग करते हुए, जो एक ऊर्जा मीटर की तरह है जो यह सिद्ध करता है कि हाइकर हमेशा निचले बिंदु के करीब जा रहा है) प्रदान किया।

• उन्होंने सिद्ध किया कि एक विशिष्ट प्रकार की समस्या (कंपोजिट स्ट्रॉन्गली कॉनवेक्स) के लिए, उनकी विधि ऑब्जेक्टिव वैल्यू (घाटी की ऊंचाई) के लिए सबसे तेज़ ज्ञात अभिसरण दर प्राप्त करती है।
• उन्होंने 10,000 आयाम (एक बहुत ही उच्च-आयामी घाटी) की समस्या के साथ एक संख्यात्मक प्रयोग (सेक्शन 6) भी चलाया। इस परीक्षण में, उनका एल्गोरिदम (SR2FISTA) वास्तव में पुराने FISTA और ADR विधि की तुलना में तेज़ था, जो व्यवहार में उनके सिद्धांत की पुष्टि करता है।

वे क्या दावा नहीं करते
यह ध्यान रखना महत्वपूर्ण है कि पेपर क्या नहीं कहता है।

• वे यह दावा नहीं करते कि उन्होंने हर एक परिदृश्य के लिए सबसे तेज़ संभव विधि खोज ली है। वे स्वीकार करते हैं कि जबकि उनकी विधि ऑब्जेक्टिव वैल्यू ($f(x_k) - f^*$) के लिए सबसे तेज़ ज्ञात है, एक अन्य विधि जिसे Prox-ITEM कहा जाता है, कुछ संदर्भों में दूरी ($\|x_k - x^*\|^2$) के लिए तेज़ है। हालाँकि, इस पेपर के "रफ" (नॉन-स्मूथ) सेटिंग में, आप हमेशा दूरी की गति को ऑब्जेक्टिव वैल्यू की गति में अनुवादित नहीं कर सकते, इसलिए उनका परिणाम स्वयं वैल्यू के लिए सबसे अच्छा है।
• वे यह दावा नहीं करते कि उनका तरीका नॉन-कॉन्वेक्स (non-convex) समस्याओं के लिए काम करता है (जहाँ घाटी में कई निचले बिंदु हो सकते हैं और कोई स्पष्ट रास्ता नहीं होता)। वे सख्ती से मांग करते हैं कि कुल समस्या कॉनवेक्स होनी चाहिए।

यह क्यों मायने रखता है
एक जिज्ञासु किशोर या कोई भी जो यह समझने में रुचि रखता है कि कंप्यूटर कैसे सीखते हैं, उसके लिए यह पेपर एक रेस कार के इंजन को अपग्रेड करने जैसा है। यह एक ऐसी समस्या को लेता है जो पहले से ही हल करने योग्य है और समाधान को अधिक तेज़ी से और कुशलता से पहुँचाता है। एक ऐसी दुनिया में जहाँ डेटा तेजी से बढ़ रहा है, AI को प्रशिक्षित करने या जटिल इंजीनियरिंग समस्या को हल करने में लगने वाले समय में से थोड़े से प्रतिशत की भी बचत करना, करोड़ों डॉलर और कंप्यूटिंग घंटों को बचा सकता है। एक विशिष्ट, गणितीय रूप से सुंदर दृष्टिकोण (निरंतर-समय भौतिकी पर आधारित) के माध्यम से एक तेज़ डिस्क्रीट एल्गोरिदम को सिद्ध करके, लेखक ने हमें विज्ञान और प्रौद्योगिकी की कुछ सबसे कठिन चुनौतियों से निपटने के लिए एक नया, शक्तिशाली उपकरण दिया है।