2025-11-17T13:58:12.673309

Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity

Bravo, Flores-Mella, Guzmán
We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we derive new mixing time bounds for the projected LA which are, in some important cases, dimension-free and poly-logarithmic on the accuracy, closely matching the existing results in the smooth convex case. Additionally, we establish new upper bounds for the privacy curve of the subsampled noisy SGD algorithm. These bounds show a crucial dependency on the regularity of gradients, and are useful for a wide range of convex losses beyond the smooth case. Our analysis relies on a suitable extension of the Privacy Amplification by Iteration (PABI) framework (Feldman et al., 2018; Altschuler and Talwar, 2022, 2023) to noisy iterations whose gradient map is not necessarily nonexpansive. This extension is achieved by designing an optimization problem which accounts for the best possible Rényi divergence bound obtained by an application of PABI, where the tractability of the problem is crucially related to the modulus of continuity of the associated gradient mapping. We show that, in several interesting cases -- namely the nonsmooth convex, weakly smooth and (strongly) dissipative -- such optimization problem can be solved exactly and explicitly, yielding the tightest possible PABI-based bounds.
academic

प्रोजेक्टेड लैंजविन एल्गोरिदम के लिए मिक्सिंग टाइम्स और प्राइवेसी विश्लेषण: कंटीन्यूटी मॉड्यूलस के तहत

मूल जानकारी

  • पेपर आईडी: 2501.04134
  • शीर्षक: प्रोजेक्टेड लैंजविन एल्गोरिदम के लिए मिक्सिंग टाइम्स और प्राइवेसी विश्लेषण: कंटीन्यूटी मॉड्यूलस के तहत
  • लेखक: Mario Bravo, Juan Pablo Flores-Mella, Cristóbal Guzmán
  • वर्गीकरण: stat.ML cs.LG math.OC math.ST stat.TH
  • प्रकाशन समय: जनवरी 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2501.04134

सारांश

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

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

समस्या की पृष्ठभूमि

  1. सैंपलिंग समस्या का महत्व: लॉग-अवतल वितरण π ∝ e^(-f) से सैंपलिंग एक मौलिक एल्गोरिदमिक समस्या है, जो वॉल्यूम अनुमान, अनुकूलन, बेयेसियन सांख्यिकी, मशीन लर्निंग और विभेदक गोपनीयता जैसी समस्याओं के लिए एक मूल निर्माण खंड है।
  2. लैंजविन एल्गोरिदम: लैंजविन एल्गोरिदम लैंजविन प्रसार को असतत करके लक्ष्य वितरण का अनुमान लगाता है:
    dL_t = -∇f(L_t)dt + √2dW_t

    असतत करने के बाद मार्कोव श्रृंखला प्राप्त होती है:
    X_{t+1} = Π_X[X_t - η∇f(X_t) + √(2η)ξ_t]
  3. मौजूदा विधियों की सीमाएं:
    • अधिकांश अनुसंधान दृढ़ता से उत्तल चिकनी संभावित कार्य सेटिंग पर केंद्रित है
    • गैर-चिकनी उत्तल संभावित कार्यों पर अनुसंधान कम है
    • PABI (पुनरावृत्ति द्वारा गोपनीयता प्रवर्धन) तकनीक मुख्य रूप से गैर-विस्तारक पुनरावृत्तियों तक सीमित है

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

यह पेपर PABI तकनीक को गैर-विस्तारक पुनरावृत्तियों से परे विस्तारित करने का लक्ष्य रखता है, कंटीन्यूटी मॉड्यूलस (modulus of continuity) के माध्यम से अंतर्निहित मैपिंग की नियमितता को मापकर, जिससे गैर-अवकलनीय कार्यों सहित अधिक व्यापक संभावित कार्य वर्गों को संभाला जा सके।

मुख्य योगदान

  1. PABI फ्रेमवर्क का विस्तार: PABI तकनीक को कंटीन्यूटी मॉड्यूलस वाले सामान्य मैपिंग तक विस्तारित करना, यहां तक कि असंतत मैपिंग को भी संभाल सकता है।
  2. अनुकूलन समस्या डिजाइन: PABI अनुप्रयोग के लिए सर्वोत्तम Rényi विचलन सीमाएं प्राप्त करने के लिए एक अनुकूलन समस्या डिजाइन करना, जिसकी व्यावहारिकता संबंधित ग्रेडिएंट मैपिंग के कंटीन्यूटी मॉड्यूलस से निकटता से संबंधित है।
  3. स्पष्ट समाधान: यह साबित करना कि जब कंटीन्यूटी मॉड्यूलस φ(δ) = √(cδ² + h) रूप का हो, तो अनुकूलन समस्या को सटीक रूप से स्पष्ट रूप से हल किया जा सकता है।
  4. मिक्सिंग टाइम सीमाएं: उत्तल और (p,M)-कमजोर चिकनी मामलों के लिए नई मिक्सिंग टाइम सीमाएं स्थापित करना, कुछ मामलों में आयाम-मुक्त और सटीकता में बहु-लॉगरिदमिक।
  5. प्राइवेसी वक्र विश्लेषण: शोर SGD के लिए नई प्राइवेसी वक्र ऊपरी सीमाएं स्थापित करना, जो ग्रेडिएंट नियमितता पर महत्वपूर्ण निर्भरता दिखाती हैं।

विधि विवरण

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

प्रोजेक्टेड शोर पुनरावृत्ति का अध्ययन करना:

X_{t+1} = Π_X[Φ_t(X_t) + ξ_t], ξ_t ~ N(0, σ²_t I_{d×d})

जहां Φ_t में कंटीन्यूटी मॉड्यूलस φ_t है।

कंटीन्यूटी मॉड्यूलस फ्रेमवर्क

परिभाषा

मैपिंग Φ: X ⊆ ℝ^d → ℝ^d के लिए, गैर-घटता हुआ फ़ंक्शन φ: ℝ₊ → ℝ₊ Φ का कंटीन्यूटी मॉड्यूलस है, यदि:

‖Φ(x) - Φ(y)‖ ≤ φ(‖x - y‖) ∀x, y ∈ X

महत्वपूर्ण मामले

  1. उत्तल Lipschitz: φ(δ) = √(δ² + (2ηL)²)
  2. उत्तल (p,M)-कमजोर चिकनी: φ(δ) = √(δ² + (2η^(1/(1-p))√((1-p)/(1+p))(M/2)^(1/(1-p)))²)
  3. दृढ़ क्षय: φ(δ) = √((1-2ηκ+η²β²)δ² + 2ηλ)

PABI विस्तार

मुख्य लेम्मा

लेम्मा 3.2: मान लीजिए X ⊆ ℝ^d एक बंद उत्तल समुच्चय है, Φ में कंटीन्यूटी मॉड्यूलस φ है। यादृच्छिक चर X, X' और गाऊसी शोर ξ ~ N(0, σ²I) के लिए, मान लीजिए Y = Π_XΦ(X) + ξ, Y' = Π_XΦ(X') + ξ, तो किसी भी 0 < a ≤ φ(δ) के लिए:

R_α^(φ(δ)-a)(Y‖Y') ≤ R_α^(δ)(X‖X') + αa²/(2σ²)

शिफ्ट अनुकूलन समस्या

सबसे कड़ी PABI सीमा प्राप्त करने के लिए, शिफ्ट अनुकूलन समस्या को हल करने की आवश्यकता है:

min_{u∈R} E(u) := Σ_{t=1}^T (φ_{t-1}(u_{t-1}) - u_t)²/σ²_{t-1}

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

प्रमेय 3.4 (मुख्य परिणाम)

मान लीजिए φ_t(δ) = √(c_tδ² + h_t), तो प्रोजेक्टेड शोर पुनरावृत्ति के लिए:

R_α(X_T‖X'_T) ≤ α/2 [Π_{k=0}^{T-1}c_k D² / Σ_{j=0}^{T-1}σ²_j Π_{l=j+1}^{T-1}c_l + Σ_{t=0}^{T-1} h_t Π_{k=t+1}^{T-1}c_k / Σ_{j=t}^{T-1}σ²_j Π_{l=j+1}^{T-1}c_l]

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

सैद्धांतिक विश्लेषण फ्रेमवर्क

यह पेपर मुख्य रूप से एक सैद्धांतिक कार्य है, जो कठोर गणितीय प्रमाण के माध्यम से सीमाएं स्थापित करता है, न कि अनुभवजन्य प्रयोगों के माध्यम से। विश्लेषण में शामिल हैं:

  1. मिक्सिंग टाइम विश्लेषण: कुल भिन्नता दूरी का उपयोग करके अभिसरण गति का मूल्यांकन
  2. गोपनीयता विश्लेषण: Rényi विभेदक गोपनीयता फ्रेमवर्क का उपयोग
  3. अनुकूलन विश्लेषण: शिफ्ट अनुकूलन समस्या के इष्टतम समाधान के अस्तित्व और अद्वितीयता को साबित करना

मूल्यांकन मेट्रिक्स

  • मिक्सिंग टाइम: T_{mix,TV}(ε) = min{t ∈ ℕ: d(t) ≤ ε}
  • Rényi विचलन: R_α(μ‖ν)
  • कुल भिन्नता दूरी: ‖μ - ν‖_

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

मिक्सिंग टाइम सीमाएं

प्रमेय 4.2 (कमजोर चिकनी मामला)

उत्तल और (p,M)-कमजोर चिकनी कार्यों के लिए, यदि 1/η ≥ Θ, तो:

T_{mix,TV}(ε) ≤ ⌈D²/η⌉ · ⌈log₂(1/ε)⌉

जहां Θ = (M/2)^(2/(1+p))(1-p)/(1+p) max{16ln(D(M/2)^(1/(1-p))e), 27}^((1-p)/(1+p))

प्रमेय 4.3 (दृढ़ क्षय मामला)

(λ,κ)-दृढ़ क्षय और β-चिकनी कार्यों के लिए, मान लीजिए c = 1 - 2ηκ + η²β² < 1, तो:

T_{mix,TV}(ε) = O(log_{1/c}(1 + D²(1-c)/(4η)) · (e/(1-c))^{λ/2} log₂(1/ε))

प्राइवेसी वक्र विश्लेषण

प्रमेय 5.2 (शोर SGD)

उत्तल, L-Lipschitz और (p,M)-कमजोर चिकनी हानि के लिए, शोर SGD (α,ε)-RDP को संतुष्ट करता है, जहां:

ε ≤ α/σ² [16L²T/n² + D²/(η²T) + 4η^(2p/(1-p))(1-p)/(1+p)(M/2)^(2/(1-p))ln(T·e)]

मुख्य निष्कर्ष

  1. आयाम स्वतंत्रता: कुछ मामलों में, मिक्सिंग टाइम सीमाएं आयाम d पर निर्भर नहीं करती हैं
  2. नियमितता निर्भरता: गोपनीयता सीमाएं ग्रेडिएंट की नियमितता पैरामीटर p पर महत्वपूर्ण रूप से निर्भर करती हैं
  3. इष्टतमता: φ(δ) = √(cδ² + h) रूप के कंटीन्यूटी मॉड्यूलस के लिए, अनुकूलन समस्या का एक अद्वितीय इष्टतम समाधान है
  4. अपक्षयी मामला: जब p = 0 (Lipschitz मामला) हो, तो n → ∞ के रूप में गायब होने वाली गोपनीयता सीमाएं प्राप्त नहीं की जा सकती हैं

संबंधित कार्य

लैंजविन एल्गोरिदम अनुसंधान

  • चिकनी दृढ़ उत्तल मामला: Dalalyan (2017), Durmus and Moulines (2019) आदि का व्यापक अनुसंधान
  • गैर-चिकनी मामला: अनुसंधान अपेक्षाकृत कम है, मुख्य रूप से Pereyra (2016), Chatterji et al. (2020) आदि को शामिल करता है

PABI तकनीक

  • मूल फ्रेमवर्क: Feldman et al. (2018) द्वारा प्रस्तावित
  • विस्तार अनुप्रयोग: Altschuler and Talwar (2022, 2023) द्वारा चिकनी उत्तल मामले में लागू
  • इस पेपर का योगदान: कंटीन्यूटी मॉड्यूलस फ्रेमवर्क तक विस्तार

विभेदक गोपनीयता

  • शास्त्रीय विश्लेषण: मानता है कि सभी पुनरावृत्तियां प्रकाशित की जाती हैं
  • अंतिम पुनरावृत्ति: Chourasia et al. (2021), Ye and Shokri (2022) आदि द्वारा अंतिम पुनरावृत्ति की गोपनीयता का अध्ययन

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. PABI तकनीक को गैर-विस्तारक पुनरावृत्तियों से परे सफलतापूर्वक विस्तारित करना
  2. कई महत्वपूर्ण संभावित कार्य वर्गों के लिए कड़ी सीमाएं स्थापित करना
  3. कंटीन्यूटी मॉड्यूलस की गोपनीयता और सैंपलिंग विश्लेषण में महत्वपूर्ण भूमिका को साबित करना

सीमाएं

  1. गैर-चिकनी मामला: Lipschitz मामले में गैर-तुच्छ गोपनीयता प्रवर्धन प्राप्त नहीं किया जा सकता है
  2. स्टेप साइज प्रतिबंध: कुछ परिणामों के लिए अधिक कठोर स्टेप साइज बाधाओं की आवश्यकता है
  3. विशिष्ट रूप: मुख्य परिणाम φ(δ) = √(cδ² + h) रूप के कंटीन्यूटी मॉड्यूलस तक सीमित हैं

भविष्य की दिशाएं

  1. अधिक सामान्य कंटीन्यूटी मॉड्यूलस रूपों तक विस्तार
  2. गैर-चिकनी मामले में गोपनीयता सीमाओं में सुधार
  3. सैडल पॉइंट समस्याओं जैसी अधिक जटिल सेटिंग्स का अध्ययन

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक नवाचार: PABI तकनीक को अधिक सामान्य सेटिंग्स तक सफलतापूर्वक विस्तारित करना, महत्वपूर्ण सैद्धांतिक मूल्य है
  2. गणितीय कठोरता: प्रमाण पूर्ण और कठोर हैं, अनुकूलन समस्या का विश्लेषणात्मक समाधान गहरी गणितीय अंतर्दृष्टि प्रदर्शित करता है
  3. व्यावहारिक मूल्य: परिणाम गैर-अवकलनीय कार्यों सहित व्यापक संभावित कार्य वर्गों पर लागू होते हैं
  4. एकीकृत फ्रेमवर्क: कंटीन्यूटी मॉड्यूलस के माध्यम से विश्लेषण के लिए एक एकीकृत फ्रेमवर्क प्रदान करता है

कमियां

  1. सीमित अनुप्रयोग: मुख्य परिणाम विशिष्ट रूप के कंटीन्यूटी मॉड्यूलस तक सीमित हैं
  2. अनुभवजन्य सत्यापन की कमी: सैद्धांतिक परिणामों की कड़ाई को सत्यापित करने के लिए संख्यात्मक प्रयोगों की कमी है
  3. गैर-चिकनी चुनौती: गैर-चिकनी मामले में गोपनीयता परिणाम अपेक्षाकृत निराशाजनक हैं

प्रभाव

  1. सैद्धांतिक योगदान: सैंपलिंग और गोपनीयता विश्लेषण के लिए नए सैद्धांतिक उपकरण प्रदान करता है
  2. पद्धति मूल्य: कंटीन्यूटी मॉड्यूलस विधि अन्य संबंधित अनुसंधान को प्रेरित कर सकती है
  3. व्यावहारिक मार्गदर्शन: वास्तविक एल्गोरिदम डिजाइन के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है

लागू परिदृश्य

  1. बेयेसियन अनुमान: गैर-चिकनी पूर्वों वाले पश्च सैंपलिंग
  2. विभेदक गोपनीयता: सटीक गोपनीयता गारंटी की आवश्यकता वाले मशीन लर्निंग अनुप्रयोग
  3. अनुकूलन: गैर-चिकनी उत्तल अनुकूलन समस्याओं के यादृच्छिक एल्गोरिदम विश्लेषण

संदर्भ

  • Altschuler, J. and Talwar, K. (2022, 2023). पुनरावृत्ति द्वारा गोपनीयता प्रवर्धन
  • Feldman, V. et al. (2018). पुनरावृत्ति द्वारा गोपनीयता प्रवर्धन
  • Dalalyan, A. (2017). लैंजविन मोंटे कार्लो विश्लेषण
  • Bubeck, S. et al. (2018). प्रोजेक्टेड लैंजविन मोंटे कार्लो

यह पेपर सैद्धांतिक मशीन लर्निंग और विभेदक गोपनीयता के क्षेत्र में महत्वपूर्ण योगदान देता है, कंटीन्यूटी मॉड्यूलस के नवीन उपयोग के माध्यम से, PABI तकनीक की प्रयोज्यता की सीमा को सफलतापूर्वक विस्तारित करता है, और गैर-चिकनी अनुकूलन और गोपनीयता-संरक्षित एल्गोरिदम विश्लेषण के लिए नए सैद्धांतिक उपकरण प्रदान करता है।