2025-11-16T17:31:12.997131

On the convergence of stochastic variance reduced gradient for linear inverse problems

Jin, Zhou

Stochastic variance reduced gradient (SVRG) is an accelerated version of stochastic gradient descent based on variance reduction, and is promising for solving large-scale inverse problems. In this work, we analyze SVRG and a regularized version that incorporates a priori knowledge of the problem, for solving linear inverse problems in Hilbert spaces. We prove that, with suitable constant step size schedules and regularity conditions, the regularized SVRG can achieve optimal convergence rates in terms of the noise level without any early stopping rules, and standard SVRG is also optimal for problems with nonsmooth solutions under a priori stopping rules. The analysis is based on an explicit error recursion and suitable prior estimates on the inner loop updates with respect to the anchor point. Numerical experiments are provided to complement the theoretical analysis.

academic

रैखिक व्युत्क्रम समस्याओं के लिए स्टोकेस्टिक विचरण कम प्रवणता के अभिसरण पर

मूल जानकारी

पेपर ID: 2510.14759
शीर्षक: रैखिक व्युत्क्रम समस्याओं के लिए स्टोकेस्टिक विचरण कम प्रवणता के अभिसरण पर
लेखक: Bangti Jin, Zehui Zhou (हांगकांग चीनी विश्वविद्यालय गणित विभाग)
वर्गीकरण: math.NA cs.NA math.OC
प्रकाशन समय: 16 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.14759

सारांश

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

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

समस्या विवरण

यह पेपर हिल्बर्ट स्पेस में रैखिक व्युत्क्रम समस्या का अध्ययन करता है: $A_\dagger x = y_\dagger$

जहां:

$A_\dagger: X \to Y = Y_1 \times \cdots \times Y_n$ प्रणाली संचालक है
$x \in X$ अज्ञात संकेत है, $y_\dagger \in Y$ सटीक डेटा है
व्यावहारिक रूप से केवल शोर युक्त डेटा $y^\delta = y_\dagger + \xi$ प्राप्त किया जा सकता है, शोर स्तर $\delta = \|\xi\|_Y$

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

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

मुख्य योगदान

सैद्धांतिक विश्लेषण में सुधार: रैखिक व्युत्क्रम समस्याओं को हल करने के लिए SVRG और नियमितकृत SVRG (rSVRG) का संपूर्ण अभिसरण सिद्धांत स्थापित किया
इष्टतम अभिसरण दर: उपयुक्त शर्तों के तहत दोनों विधियां इष्टतम अभिसरण दर $O(\delta^{2\nu/(1+2\nu)})$ प्राप्त कर सकती हैं
नियमितकरण गुण: rSVRG में आंतरिक नियमितकरण तंत्र है, प्रारंभिक रोक नियम की आवश्यकता नहीं है; मानक SVRG पूर्व रोक के तहत भी नियमितकरण गुण रखता है
अपेक्षित और समान अभिसरण: साथ ही अपेक्षित अर्थ और समान अर्थ में अभिसरण दर स्थापित की, मौजूदा परिणामों का विस्तार किया
शर्तों में छूट: मौजूदा कार्य की तुलना में SVRG इष्टतम अभिसरण के लिए शर्तें अधिक शिथिल हैं

विधि विवरण

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

अनुकूलन समस्या पर विचार करें: $J(x) = \frac{1}{2n}\|A_\dagger x - y^\delta\|_Y^2 = \frac{1}{n}\sum_{i=1}^n f_i(x)$ जहां $f_i(x) = \frac{1}{2}\|A_{\dagger,i}x - y^\delta_i\|_{Y_i}^2$

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

मानक SVRG (एल्गोरिदम 1)

प्रारंभिकीकरण: x₀^δ = x₀, आवृत्ति M, चरण आकार {ηₖ}
for K = 0,1,... do
    gₖ = J'(x_{KM}^δ) = (1/n)A_†*(A_†x_{KM}^δ - y^δ) की गणना करें
    for t = 0,1,...,M-1 do
        यादृच्छिक रूप से i_{KM+t} ∈ {1,...,n} का नमूना लें
        अपडेट x_{KM+t+1}^δ = x_{KM+t}^δ - η_{KM+t}(A*_{i_{KM+t}}A_{i_{KM+t}}(x_{KM+t}^δ - x_{KM}^δ) + gₖ)
    end
end

नियमितकृत SVRG (एल्गोरिदम 2)

संचालक $A_\dagger$ को अनुमानित संचालक $A$ से बदलें, काटे गए एकवचन मान अपघटन के माध्यम से प्राप्त: $A(\cdot) = \sum_{j=1}^J \sigma_j\langle\phi_j, \cdot\rangle\psi_j$ जहां $\sigma_j \geq a\delta^b$ को संतुष्ट करने वाले मुख्य एकवचन मान रखे जाते हैं।

मुख्य मान्यताएं (मान्यता 2.1)

चरण आकार शर्त: $\eta_j = c_0 \leq L^{-1}$ , जहां $L = \max_{1\leq i\leq n}\|A_i\|^2$
स्रोत शर्त: $\nu > 0$ और $w \in N(A_\dagger)^\perp$ मौजूद हैं जैसे कि $x_\dagger - x_0 = B_\dagger^\nu w$
संचालक सन्निकटन: जब $a > 0$ हो, तो $A$ काटे गए SVD के माध्यम से निर्मित है, $\sigma_j \geq a\delta^b$ के एकवचन मान रखे जाते हैं

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

त्रुटि अपघटन रणनीति: त्रुटि को पूर्वाग्रह और विचरण दोनों भागों में अपघटित करें, प्रत्येक को सटीक रूप से अनुमानित करें
एंकर बिंदु विश्लेषण: आंतरिक लूप अपडेट के व्यवहार को एंकर बिंदु के संबंध में विश्लेषण करके, महत्वपूर्ण पूर्व अनुमान स्थापित करें
एकीकृत ढांचा: मानक SVRG और नियमितकृत SVRG को संभालने के लिए एकीकृत सैद्धांतिक ढांचा प्रदान करें

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

डेटासेट

Regutools पैकेज में तीन मानक व्युत्क्रम समस्याओं का उपयोग करें:

s-phillips: हल्की रोग समस्या (mildly ill-posed)
s-gravity: गंभीर रोग समस्या (severely ill-posed)
s-shaw: गंभीर रोग समस्या (severely ill-posed)

सभी समस्याओं को $n = m = 1000$ के परिमित-आयामी रैखिक प्रणाली में विवेकित किया गया है।

प्रायोगिक पैरामीटर

सटीक समाधान पीढ़ी: $x_\dagger = \|(A_\dagger^*A_\dagger)^\nu x_e\|_{\ell^\infty}^{-1}(A_\dagger^*A_\dagger)^\nu x_e$
शोर सेटिंग: $y^\delta_i = y_{\dagger,i} + \epsilon\|y_\dagger\|_{\ell^\infty}\xi_i$ , $\xi_i \sim \mathcal{N}(0,1)$
चरण आकार: Landweber विधि के लिए $c_0 = \|A_\dagger\|^{-2}$ , (r)SVRG के लिए $c_0 = O(c)$ , जहां $c = L^{-1}$
आवृत्ति: $M = 2n$
अधिकतम पुनरावृत्ति: $10^5$ राउंड

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

Landweber विधि (LM): शास्त्रीय पुनरावृत्तिमूलक नियमितकरण विधि, विसंगति सिद्धांत का उपयोग करके रोकें
मानक SVRG: इष्टतम त्रुटि बिंदु का उपयोग करके रोकें
नियमितकृत SVRG (rSVRG): सिद्धांत-निर्देशित रोक मानदंड का उपयोग करें

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

मुख्य सैद्धांतिक परिणाम (प्रमेय 2.1)

मान्यता 2.1 के तहत, $k,n,\delta$ से स्वतंत्र एक स्थिरांक $c^*$ मौजूद है जैसे कि:

अपेक्षित अभिसरण दर: