🔢 mathematics

Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach

यह शोधपत्र एक ज़ीरो-ऑर्डर एल्गोरिदम का प्रस्ताव और विश्लेषण करता है जो सबमॉड्यूलर-कॉन्केव (submodular-concave) फलनों से जुड़ी नॉन-स्मूथ मिन-मैक्स समस्याओं को हल करने के लिए लोवाज़ एक्सटेंशन (Lovász extension) सबग्रेडिएंट्स और गॉसियन स्मूथिंग (Gaussian smoothing) को संयोजित करता है, जो ऑफलाइन सेटिंग में $\epsilon$ -सैडल पॉइंट (saddle point) की अभिसरण (convergence) को सिद्ध करता है और $O(\sqrt{N\bar{P}_N})$ ऑनलाइन डुअलिटी गैप बाउंड स्थापित करता है।

मूल लेखक: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

प्रकाशित 2026-05-29

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Amir Ali Farzin, Yuen-Man Pun, Philipp Braun, Tyler Summers, Iman Shames

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

मुख्य चित्र: बिल्ली और चूहे का खेल

कल्पना कीजिए कि शतरंज का एक उच्च-दांव वाला खेल चल रहा है, लेकिन बोर्ड पर मोहरे चलाने के बजाय, दो खिलाड़ी मिलकर एक पहेली को हल करने की कोशिश कर रहे हैं।

खिलाड़ी A (मिनिमाइज़र - कम करने वाला): किसी समस्या का "सर्वश्रेष्ठ" समाधान ढूंढना चाहता है (जैसे केक को पूरी तरह से काटना या लोगों को टीमों में बांटना)।
खिलाड़ी B (मैक्सिमाइज़र - बढ़ाने वाला): एक विरोधी है जो चीज़ों को बिगाड़ने की कोशिश कर रहा है। वे समाधान को जितना हो सके उतना खराब बनाना चाहते हैं (जैसे डेटा में शोर जोड़ना या सिस्टम को धोखा देना)।

इसे मिन-मैक्स (Min-Max) समस्या कहा जाता है। लक्ष्य एक "सैडल पॉइंट" (saddle point) ढूंढना है—एक ऐसा मधुर बिंदु जहाँ खिलाड़ी A ने वह सर्वश्रेष्ठ किया है जो वह खिलाड़ी B के पूरी कोशिश के बावजूद कर सकता है, और खिलाड़ी B इसे इससे अधिक खराब नहीं कर सकता चाहे वह कितनी भी कोशिश करे।

समस्या: एक ऊबड़-खाबड़, पथरीला इलाका

इस शोध पत्र में, लेखक एक बहुत ही विशिष्ट, कठिन प्रकार की पहेली से निपट रहे हैं:

"सबमॉड्यूलर" (Submodular) भाग: इसे आप "घटते प्रतिफल" (diminishing returns) के नियम की तरह समझ सकते हैं। यदि आप एक टोकरी के लिए वस्तुएं चुन रहे हैं, तो पहली वस्तु जो आप चुनते हैं वह बहुत मूल्य जोड़ती है। दूसरी वस्तु कुछ मूल्य जोड़ती है, लेकिन पहली से कम। 100वीं वस्तु लगभग कुछ भी नहीं जोड़ती। यह वास्तविक जीवन में आम है (जैसे नेटवर्क के लिए सर्वश्रेष्ठ सेंसर चुनना या सोशल ग्राफ में सबसे प्रभावशाली लोगों को चुनना)।
"नॉन-स्मूथ" (Non-Smooth) भाग: कल्पना कीजिए कि समस्या का परिदृश्य एक चिकनी पहाड़ी नहीं है; यह एक ऊबड़-खाबड़, पथरीला पहाड़ है जिसमें तीखी चट्टानें और कोई स्पष्ट रास्ता नहीं है। आप केवल नीचे जाने के लिए गेंद को लुढ़काकर तल तक नहीं पहुँच सकते क्योंकि गेंद फंस जाएगी या किसी नुकीले पत्थर से टकराकर उछल जाएगी।
"कॉन्केव" (Concave) भाग: खिलाड़ी B के कदम गणितीय अर्थों में चिकने और अनुमानित हैं, लेकिन खिलाड़ी A के कदम ऊबड़-खाबड़ और पथरीले हैं।

चुनौती: आंखों पर पट्टी बांधकर अन्वेषण

आमतौर पर, इन समस्याओं को हल करने के लिए, आपको एक मानचित्र या दिशा-सूचक यंत्र (गणितीय ग्रेडिएंट्स) की आवश्यकता होती है जो आपको बताए कि "नीचे" की दिशा कौन सी है। लेकिन यहाँ, शोध पत्र कहता है: "हमारे पास कोई मानचित्र नहीं है। हम आंखों पर पट्टी बांधे हुए हैं।"

यह एक जीरोथ-ऑर्डर (Zeroth-Order) दृष्टिकोण है। एल्गोरिदम केवल यह पूछ सकता है, "यदि मैं यहाँ खड़ा हूँ तो स्कोर क्या होगा?" वह यह नहीं पूछ सकता कि "ढलान किस दिशा में है?" उसे अंधेरे में हाथ-पैर मारकर महसूस करना होगा।

समाधान: "गौसियन स्मूथिंग" (Gaussian Smoothing) टॉर्च

चूंकि इलाके का सीधा नेविगेशन बहुत पथरीला है, इसलिए लेखकों ने एक चतुर तरकीब निकाली:

लोवाज़ एक्सटेंशन (Lovász Extension): वे ऊबड़-खाबड़, असतत (discrete) समस्या (विशिष्ट वस्तुओं को चुनना) को एक निरंतर (continuous) समस्या (वस्तुओं के अंश चुनना) में बदल देते हैं। यह एक सीढ़ी को ढलान (ramp) में बदलने जैसा है।
गौसियन स्मूथिंग (Gaussian Smoothing): शेष खुरदरेपन को संभालने के लिए, वे एक "टॉर्च" का उपयोग करते हैं जो एक एकल किरण नहीं बल्कि एक नरम, धुंधली चमक (Gaussian smoothing) बिखेरती है। एक विशिष्ट पत्थर को महसूस करने के बजाय, एल्गोरिदम अपने आस-पास की जमीन की औसत बनावट को महसूस करता है। यह तीखी चट्टानों को इतना चिकना कर देता है कि एक रास्ता मिल सके।

एल्गोरिदम: "लुक-अहेड" (Look-Ahead) डांसर

लेखक एक ऐसा एल्गोरिदम (एल्गोरिदम 1) प्रस्तावित करते हैं जो एक कुशल डांसर की तरह काम करता है जो केवल संगीत पर प्रतिक्रिया नहीं देता बल्कि अगले बीट का पूर्वानुमान भी लगाता है।

चरण 1: एल्गोरिदम जमीन के अपने वर्तमान अहसास के आधार पर एक कदम उठाता है।
चरण 2 (लुक-अहेड): उस कदम को लेने से पहले, वह यह देखने के लिए एक "अभ्यास कदम" लेता है कि वहां जमीन कैसी दिखती है।
चरण 3: वह उस नई जानकारी का उपयोग एक बेहतर, अधिक स्थिर चाल चलने के लिए करता है।

यह "एक्स्ट्राग्रेडिएंट" (Extragradient) विधि एल्गोरिदम को स्थानीय जाल में फंसने या आगे-पीछे डगमगाने से बचने में मदद करती है।

परिणाम: ऑफलाइन बनाम ऑनलाइन

शोध पत्र इस परीक्षण को दो परिदृश्यों में परखता है:

1. ऑफलाइन परिदृश्य (स्थिर पहेली)
एक ऐसी पहेली को हल करने की कल्पना करें जहाँ टुकड़े कभी नहीं हिलते।

परिणाम: एल्गोरिदम सफलतापूर्वक "सैडल पॉइंट" (सबसे अच्छा संभव समझौता) ढूंढ लेता है। यह सिद्ध करता है कि पर्याप्त प्रयासों के साथ, यह बिना किसी मानचित्र के भी आदर्श उत्तर के करीब पहुँच जाएगा।

2. ऑनलाइन परिदृश्य (चलती-फिरती पहेली)
एक ऐसी पहेली को हल करने की कल्पना करें जहाँ टुकड़े लगातार फिसल रहे हैं, घूम रहे हैं और अपना आकार बदल रहे हैं (जैसे एक वीडियो गेम लेवल जो खेलते समय बदलता रहता है)।

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

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

इसे सिद्ध करने के लिए, लेखकों ने इमेज सेगमेंटेशन (छवि को भागों में काटना, जैसे किसी व्यक्ति को बैकग्राउंड से अलग करना) पर इसका परीक्षण किया।

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

सारांश

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

तकनीकी सारांश: नॉन-स्मूथ सबमॉड्यूलर-कॉन्केव फलनों के ऑफलाइन और ऑनलाइन मि-मैक्स (Min-Max) समस्या का समाधान

समस्या का स्वरूप
यह कार्य निम्नलिखित रूप वाले मिश्रित-पूर्णांक मि-मैक्स और मैक्स-मिन अनुकूलन (optimization) समस्याओं को संबोधित करता है:
$\max_{y \in Y} \min_{S \subset Q} f(S, y) \quad \text{तथा} \quad \min_{S \subset Q} \max_{y \in Y} f(S, y)$
जहाँ $Q = [n]$ एक ग्राउंड सेट है जिसमें $n$ तत्व हैं, $2^Q$ इसकी पावर सेट (power set) है, और $Y \subset \mathbb{R}^m$ एक कॉम्पैक्ट कॉन्वेक्स सेट है। फलन $f: 2^Q \times \mathbb{R}^m \to \mathbb{R}$ को सेट वेरिएबल $S$ के संबंध में सबमॉड्यूलर (submodular) और निरंतर वेरिएबल $y$ के संबंध में कॉन्केव (concave) माना गया है। महत्वपूर्ण रूप से, फलन दोनों वेरिएबल्स के संबंध में नॉन-स्मूथ (non-smooth/अघटित) होने की अनुमति देता है। लेखक एक $\epsilon$ -सैडल पॉइंट (saddle point) की गणना करने का लक्ष्य रखते हैं, जिसे एक ऐसे जोड़े $(\bar{S}, \bar{y})$ के रूप में परिभाषित किया गया है जहाँ ड्युअलिटी गैप (duality gap) $\epsilon$ द्वारा सीमित है।

कार्यप्रणाली (Methodology)
प्रस्तावित दृष्टिकोण एक्स्ट्राग्रेडिएंट मेथड (extragradient method) पर आधारित एक ज़ीरोथ-ऑर्डर (Zeroth-Order - ZO) फ्रेमवर्क का उपयोग करता है। यह कार्यप्रणाली नॉन-स्मूथनेस और मिश्रित-वेरिएबल संरचना को संभालने के लिए दो प्राथमिक तकनीकों पर निर्भर करती है:

सबमॉड्यूलरिटी के लिए लोवाज़ एक्सटेंशन (Lovász Extension): डिस्क्रीट सबमॉड्यूलर घटक को संभालने के लिए, लेखक लोवाज़ एक्सटेंशन $f^L$ का उपयोग करते हैं, जो सबमॉड्यूलर सेट फलन को हाइपरक्यूब $[0, 1]^n$ पर एक निरंतर, कॉन्वेक्स फलन में मैप करता है। सेट वेरिएबल के संबंध में $f^L$ के सबग्रेडिएंट (subgradient) को केवल फलन मूल्यांकन (एक मैक्सिमल चेन के माध्यम से) का उपयोग करके निकाला जा सकता है, जिससे उच्च-क्रम की जानकारी की आवश्यकता नहीं होती।
कॉन्केविटी के लिए गौसियन स्मूथिंग (Gaussian Smoothing): निरंतर कॉन्केव वेरिएबल $y$ के लिए, जहाँ फलन नॉन-स्मूथ हो सकता है, लेखक गौसियन स्मूथिंग का उपयोग करते हैं। वे स्मूद किए गए फलन के ग्रेडिएंट को अनुमानित करने के लिए टू-पॉइंट एस्टीमेटर (two-point estimator) के साथ एक रैंडम ऑरेकल (random oracle) को परिभाषित करते हैं। यह बिना स्पष्ट डेरिवेटिव्स के ग्रेडिएंट-आधारित अपडेट की अनुमति देता है।

परिणामी एल्गोरिदम (एल्गोरिदम 1, ZO-EG) एक पुनरावृत्ति लूप (iterative loop) में कार्य करता है:

फॉरवर्ड स्टेप (Forward Step): वर्तमान इटरैट $z_k = (x_k, y_k)$ पर ऑपरेटर का अनुमान लगाने के लिए $y$ के लिए रैंडम ऑरेकल की गणना करने हेतु गौसियन दिशाओं को सैंपल करना और $x$ के लिए सबग्रेडिएंट की गणना करना।
एक्स्ट्रापोलेशन स्टेप (Extrapolation Step): एक लुकअहेड पॉइंट $\hat{z}_k$ की ओर डिसेंट स्टेप (descent step) करना।
अपडेट स्टेप (Update Step): $\hat{z}_k$ पर ऑपरेटर को पुनः अनुमानित करना और $z_{k+1}$ को अपडेट करने के लिए दूसरा डिसेंट स्टेप करना।

इस पद्धति को केवल फलन मान प्रश्नों (ज़ीरोथ-ऑर्डर जानकारी) की आवश्यकता होती है और यह सीधे ग्रेडिएंट या सबग्रेडिएंट तक पहुँच का अनुमान नहीं लगाती है।

प्रमुख योगदान और सैद्धांतिक परिणाम
यह शोध दोनों ऑफलाइन और ऑनलाइन सेटिंग्स के लिए अभिसरण (convergence) गारंटी प्रदान करता है:

ऑफलाइन अभिसरण (Offline Convergence): लेखक सिद्ध करते हैं कि एल्गोरिदम, अपेक्षा (expectation) में, एक $\epsilon$ -सैडल पॉइंट की ओर अभिसत होता है। कुल सैंपल कॉम्प्लेक्सिटी को $O(nm^2\epsilon^{-2})$ दिखाया गया है, जहाँ $n$ ग्राउंड सेट का आकार है और $m$ निरंतर वेरिएबल का आयाम है। $n$ पर निर्भरता लोवाज़ एक्सटेंशन सबग्रेडिएंट्स की प्रति-इटरेशन लागत से आती है, जबकि इटरेशन काउंट $m$ पर निर्भर करता है।
ऑनलाइन अभिसरण (Online Convergence): ऑनलाइन सेटिंग में, जहाँ लागत फलन $f_k$ समय के साथ बदलता है, एल्गोरिदम एक अपेक्षित ऑनलाइन ड्युअलिटी गैप $O(\sqrt{N \bar{P}_N})$ प्राप्त करता है। यहाँ $N$ इटरेशन की संख्या है और $\bar{P}_N$ अनुकूल निर्णयों के अनुक्रम का पाथ लेंथ (path length) है। यह परिणाम ऑनलाइन ऑप्टिमाइज़ेशन में स्थापित डायनेमिक रिग्रेट बाउंड्स के अनुरूप है।
समाधानों का अस्तित्व (Existence of Solutions): पेपर में इस बात पर चर्चा की गई है कि मूल डिस्क्रीट समस्या के लिए सैडल पॉइंट्स कब मौजूद होते हैं, इसे निरंतर लोवाज़ एक्सटेंशन समस्या के समाधानों से जोड़कर, विशेष रूप से जब एक्सटेंशन का मिनिमाइज़र हाइपरक्यूब के वर्टेक्स (vertex) पर स्थित होता है।

संख्यात्मक परिणाम और अनुप्रयोग
सैद्धांतिक निष्कर्षों को विशिष्ट उदाहरणों के माध्यम से प्रदर्शित किया गया है, विशेष रूप से एडवर्सरियल इमेज सेगमेंटेशन (adversarial image segmentation) और सेमी-सुपरवाइज्ड क्लस्टरिंग (semi-supervised clustering) पर ध्यान केंद्रित करते हुए:

ऑफलाइन एडवर्सरियल सेगमेंटेशन: विधि को एक मि-मैक्स समस्या पर लागू किया गया है जहाँ एडवरसरी (adversary) सीड पिक्सल के ट्रस्ट वेट्स को बाधित करती है। एल्गोरिदम सफलतापूर्वक ग्राउंड ट्रुथ से मेल खाने वाला सेगमेंटेशन रिकवर करता है, जो एडवर्सरियल परटर्बेशन के विरुद्ध मजबूती प्रदर्शित करता है।
ऑनलाइन एडवर्सरियल सेगमेंटेशन: एल्गोरिदम का परीक्षण एक वीडियो स्ट्रीम पर किया गया है जहाँ आकृतियाँ और क्लस्टर चलते और घूमते हैं, जिससे प्रत्येक फ्रेम में कॉस्ट फंक्शन बदल जाता है। विधि बिना प्री-ट्रेनिंग के रियल-टाइम सेगमेंटेशन (CPU पर लगभग 80 fps) करती है।
डीप लर्निंग के साथ तुलना: ऑनलाइन एडवर्सरियल सेटिंग में, प्रस्तावित ZO विधि IoU, प्रिसिजन और रिकॉल के मामले में सुपरवाइज्ड और सेमी-सुपरवाइज्ड प्रशिक्षित U-Net मॉडल दोनों से बेहतर प्रदर्शन करती है। उल्लेखनीय रूप से, ZO विधि के लिए कोई प्री-ट्रेनिंग आवश्यक नहीं है, इसका मेमोरी फुटप्रिंट काफी छोटा है (~0.05 MB बनाम ~8 MB U-Net के लिए), और यह बड़े डेटासेट तक पहुँच के बिना भी अनदेखे वातावरण में प्रभावी ढंग से कार्य करती है।

महत्व और दावे
लेखक दावा करते हैं कि यह नॉन-स्मूथ सबमॉड्यूलर-कॉन्केव कॉस्ट फंक्शन्स वाली मि-मैक्स ऑप्टिमाइज़ेशन समस्याओं को हल करने के लिए समर्पित पहला अध्ययन है। इस कार्य का महत्व इन बातों में निहित है:

एक अंतर को भरना: यह उन कॉम्बिनेटोरियल मि-मैक्स समस्याओं के वर्ग को संबोधित करता है जिन्हें स्मूथनेस की कमी और मिश्रित डिस्क्रीट-कंटीन्यूअस प्रकृति के कारण पहले हल करना कठिन था।
ज़ीरोथ-ऑर्डर दक्षता: यह प्रदर्शित करता है कि ज़ीरोथ-ऑर्डर विधियों को, जो पारंपरिक रूप से निरंतर नॉन-स्मूथ समस्याओं के लिए उपयोग की जाती हैं, लोवाज़ एक्सटेंशन के माध्यम से सबमॉड्यूलर ऑप्टिमाइज़ेशन के लिए प्रभावी ढंग से अनुकूलित किया जा सकता है।
मजबूती और दक्षता: संख्यात्मक परिणाम बताते हैं कि यह दृष्टिकोण उन वास्तविक समय, संसाधन-बाधित और एडवर्सरियल वातावरणों के लिए एक व्यवहार्य विकल्प है, जहाँ प्री-ट्रेनिंग असंभव या गैर-स्थिर (non-stationary) है।

पेपर यह नोट करते हुए समाप्त होता है कि भविष्य के कार्य इन समाधानों और मिक्स-स्ट्रेटजी नैश इक्विलिब्रियम (mixed-strategy Nash equilibria) के बीच संबंध की खोज कर सकते हैं, परिणामों को सबमॉड्यूलर-सबमॉड्यूलर कॉस्ट फंक्शन्स तक विस्तारित कर सकते हैं, और अनबाउंडेड कंस्ट्रेंट सेट्स की जांच कर सकते हैं।