2025-11-19T10:07:13.697330

Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis

Oikonomidis, Quan, Patrinos
We study nonlinearly preconditioned gradient methods for smooth nonconvex optimization problems, focusing on sigmoid preconditioners that inherently perform a form of gradient clipping akin to the widely used gradient clipping technique. Building upon this idea, we introduce a novel heavy ball-type algorithm and provide convergence guarantees under a generalized smoothness condition that is less restrictive than traditional Lipschitz smoothness, thus covering a broader class of functions. Additionally, we develop a stochastic variant of the base method and study its convergence properties under different noise assumptions. We compare the proposed algorithms with baseline methods on diverse tasks from machine learning including neural network training.
academic

অরৈখিকভাবে পূর্বশর্তযুক্ত গ্রেডিয়েন্ট পদ্ধতি: মোমেন্টাম এবং স্টোকাস্টিক বিশ্লেষণ

মৌলিক তথ্য

  • পেপার আইডি: 2510.11312
  • শিরোনাম: অরৈখিকভাবে পূর্বশর্তযুক্ত গ্রেডিয়েন্ট পদ্ধতি: মোমেন্টাম এবং স্টোকাস্টিক বিশ্লেষণ
  • লেখক: কনস্টান্টিনোস ওইকোনোমিডিস, জান কোয়ান, প্যানাগিওটিস প্যাট্রিনোস (কেইউ লিউভেন)
  • শ্রেণীবিভাগ: math.OC (অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
  • প্রকাশনা সম্মেলন: ৩৯তম নিউরাল ইনফরমেশন প্রসেসিং সিস্টেম সম্মেলন (NeurIPS 2025)
  • পেপার লিংক: https://arxiv.org/abs/2510.11312

সারসংক্ষেপ

এই পেপারটি মসৃণ অ-উত্তল অপ্টিমাইজেশন সমস্যার জন্য অরৈখিক পূর্বশর্তযুক্ত গ্রেডিয়েন্ট পদ্ধতি অধ্যয়ন করে, যা মূলত ব্যাপকভাবে ব্যবহৃত গ্রেডিয়েন্ট ক্লিপিং কৌশলের অনুরূপ সিগময়েড পূর্বশর্তকারীর উপর দৃষ্টি নিবদ্ধ করে। এই ধারণার উপর ভিত্তি করে, লেখকরা একটি নতুন ভারী বল অ্যালগরিদম প্রবর্তন করেন এবং ঐতিহ্যবাহী লিপশিৎজ মসৃণতার সীমাবদ্ধতার চেয়ে আরও শিথিল সাধারণীকৃত মসৃণতার শর্তে সংগ্রহ নিশ্চয়তা প্রদান করেন, যা ফাংশনের একটি বিস্তৃত শ্রেণী কভার করে। অতিরিক্তভাবে, লেখকরা মৌলিক পদ্ধতির স্টোকাস্টিক ভেরিয়েন্ট তৈরি করেছেন এবং বিভিন্ন শব্দ অনুমানের অধীনে এর সংগ্রহ বৈশিষ্ট্য অধ্যয়ন করেছেন।

গবেষণা পটভূমি এবং প্রেরণা

  1. সমাধান করার সমস্যা: ঐতিহ্যবাহী গ্রেডিয়েন্ট ডিসেন্ট (GD) এবং স্টোকাস্টিক গ্রেডিয়েন্ট ডিসেন্ট (SGD) পদ্ধতিগুলি আধুনিক মেশিন লার্নিং অ্যাপ্লিকেশনগুলি পরিচালনা করার সময় যা বৈশ্বিক লিপশিৎজ গ্রেডিয়েন্ট অনুমান পূরণ করে না তার জন্য সতর্ক প্যারামিটার টিউনিং বা ব্যয়বহুল লাইন সার্চ কৌশল প্রয়োজন।
  2. সমস্যার গুরুত্ব: আধুনিক গভীর শেখার অ্যাপ্লিকেশনগুলিতে বেশিরভাগ খরচ ফাংশন ঐতিহ্যবাহী লিপশিৎজ গ্রেডিয়েন্ট অনুমান পূরণ করে না, এবং গ্রেডিয়েন্ট ক্লিপিং কৌশল ভাষা মডেলের মতো কাজগুলির জন্য স্ট্যান্ডার্ড অনুশীলনে পরিণত হয়েছে, যা নিউরাল নেটওয়ার্ক প্রশিক্ষণ স্থিতিশীল করতে ব্যবহৃত হয়।
  3. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:
    • লিপশিৎজ মসৃণতার বাইরে সমস্যাগুলি পরিচালনা করার সময় স্ট্যান্ডার্ড GD/SGD পদ্ধতি সংগ্রহে অসুবিধা পায়
    • বিদ্যমান গ্রেডিয়েন্ট ক্লিপিং পদ্ধতির তাত্ত্বিক বিশ্লেষণ প্রধানত নির্দিষ্ট মসৃণতার শর্তে সীমাবদ্ধ
    • আরও সাধারণ সেটিংসে মোমেন্টাম পদ্ধতির বিশ্লেষণের অভাব
  4. গবেষণা প্রেরণা: গ্রেডিয়েন্ট ক্লিপিং পদ্ধতিগুলিকে অরৈখিক পূর্বশর্তকরণ কাঠামোতে একীভূত করা এবং মোমেন্টাম এবং স্টোকাস্টিক ভেরিয়েন্ট সহ আরও সাধারণ তাত্ত্বিক বিশ্লেষণে প্রসারিত করা।

মূল অবদান

  1. অ্যানিসোট্রপিক গ্রেডিয়েন্ট ডিসেন্ট পদ্ধতি প্রসারিত করা: মৌলিক পুনরাবৃত্তিতে ভারী বল মোমেন্টাম যোগ করে, সাধারণ অ-উত্তল সেটিংসে সংগ্রহ নিশ্চয়তা অধ্যয়ন করা।
  2. স্টোকাস্টিক সম্প্রসারণ প্রস্তাব করা: বিভিন্ন শব্দ অনুমানের অধীনে মৌলিক পদ্ধতির স্টোকাস্টিক সংস্করণ বিশ্লেষণ করা, সীমাবদ্ধ ভেরিয়েন্সের চেয়ে শিথিল শর্ত সহ।
  3. তাত্ত্বিক বিশ্লেষণ অবদান:
    • অ্যানিসোট্রপিক ডিসেন্ট অসমতার অধীনে মোমেন্টাম অ্যালগরিদমের সংগ্রহ প্রমাণ করা
    • সাধারণীকৃত PL শর্তের অধীনে রৈখিক সংগ্রহ হার প্রমাণ করা
    • নতুন শব্দ অনুমানের অধীনে স্টোকাস্টিক পদ্ধতি বিশ্লেষণ করা
  4. পরীক্ষামূলক যাচাইকরণ: স্নায়ু নেটওয়ার্ক প্রশিক্ষণ এবং ম্যাট্রিক্স ফ্যাক্টরাইজেশন সহ বিভিন্ন মেশিন লার্নিং কাজে প্রস্তাবিত পদ্ধতির ভাল কর্মক্ষমতা প্রদর্শন করা।

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

সাধারণ ন্যূনতমকরণ সমস্যা বিবেচনা করুন: min⁡x∈Rnf(x)\min_{x \in \mathbb{R}^n} f(x) যেখানে f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} মসৃণ এবং সম্ভবত অ-উত্তল ফাংশন।

মূল কাঠামো: অরৈখিক পূর্বশর্তযুক্ত গ্রেডিয়েন্ট পদ্ধতি

মৌলিক পদ্ধতি: xk+1=xk−γ∇ϕ∗(∇f(xk))x^{k+1} = x^k - \gamma \nabla \phi^*(\nabla f(x^k))

যেখানে ϕ:Rn→R\phi: \mathbb{R}^n \to \mathbb{R} একটি উত্তল রেফারেন্স ফাংশন, ϕ∗\phi^* এর উত্তল সংযোগ, এবং ∇ϕ∗\nabla \phi^* পূর্বশর্তকারী তৈরি করে।

মূল ধারণা: দৃঢ়ভাবে উত্তল এবং সীমাবদ্ধ ডোমেইন সহ রেফারেন্স ফাংশন ϕ\phi নির্বাচন করে, ম্যাপিং ∇ϕ∗\nabla \phi^* Rn\mathbb{R}^n কে ইউনিট nn-বলে ম্যাপ করে, স্বাভাবিকভাবে গ্রেডিয়েন্ট ক্লিপিং বাস্তবায়ন করে।

অ্যালগরিদম 1: মোমেন্টাম সহ অরৈখিক পূর্বশর্তযুক্ত গ্রেডিয়েন্ট পদ্ধতি (m-NPGM)

ইনপুট: x⁰ ∈ ℝⁿ, γ, β > 0 নির্বাচন করুন, m⁻¹ = 0ⁿ সেট করুন
পুনরাবৃত্তি k = 0, 1, ... সংগ্রহ পর্যন্ত:
1. mᵏ = βmᵏ⁻¹ + (1-β)∇φ*(∇f(xᵏ)) গণনা করুন
2. xᵏ⁺¹ = xᵏ - γmᵏ গণনা করুন

সমতুল্য ফর্ম: xk+1=xk−(1−β)γ∇ϕ∗(∇f(xk))+β(xk−xk−1)x^{k+1} = x^k - (1-\beta)\gamma\nabla\phi^*(\nabla f(x^k)) + \beta(x^k - x^{k-1})

অ্যানিসোট্রপিক ডিসেন্ট অসমতা

সংজ্ঞা: ফাংশন ff ϕ\phi এর সাপেক্ষে অ্যানিসোট্রপিক ডিসেন্ট সম্পত্তি সন্তুষ্ট করে, যদি সমস্ত x,xˉ∈Rnx, \bar{x} \in \mathbb{R}^n এর জন্য: f(x)≤f(xˉ)+1L⋆ϕ(x−yˉ)−1L⋆ϕ(xˉ−yˉ)f(x) \leq f(\bar{x}) + \frac{1}{L} \star \phi(x - \bar{y}) - \frac{1}{L} \star \phi(\bar{x} - \bar{y}) যেখানে yˉ=xˉ−1L∇ϕ∗(∇f(xˉ))\bar{y} = \bar{x} - \frac{1}{L}\nabla\phi^*(\nabla f(\bar{x}))।

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. মোমেন্টাম ডিজাইন: স্ট্যান্ডার্ড পদ্ধতির বিপরীতে, এই পেপারের মোমেন্টাম অনুমান পূর্বশর্তযুক্ত গ্রেডিয়েন্টের উত্তল সমন্বয় নিয়ে গঠিত, গ্রেডিয়েন্ট সমন্বয় করে পূর্বশর্ত করার পরিবর্তে।
  2. সাধারণীকৃত মসৃণতা: অ্যানিসোট্রপিক মসৃণতা (L0,L1)(L_0, L_1)-মসৃণতার চেয়ে কম সীমাবদ্ধ, ফাংশনের বিস্তৃত শ্রেণী কভার করে।
  3. একীভূত বিশ্লেষণ কাঠামো: রেফারেন্স ফাংশন ϕ\phi এর উত্তলতার উপর ভিত্তি করে একীভূত সংগ্রহ বিশ্লেষণ প্রদান করা।

তাত্ত্বিক ফলাফল

প্রধান সংগ্রহ উপপাদ্য

উপপাদ্য 2.2: অ্যানিসোট্রপিক মসৃণতার শর্তে, β∈[0,0.5)\beta \in [0, 0.5) এবং γ=α/L\gamma = \alpha/L, α≤1\alpha \leq 1 এর জন্য: min⁡0≤k≤Kϕ(∇ϕ∗(∇f(xk)))≤L(f(x0)−f∗)α(K+1)(1−2β)\min_{0 \leq k \leq K} \phi(\nabla\phi^*(\nabla f(x^k))) \leq \frac{L(f(x^0) - f^*)}{α(K+1)(1-2\beta)}

উপপাদ্য 2.4: সাধারণীকৃত PL শর্তে, 2-ডিগ্রি সমজাতীয় রেফারেন্স ফাংশনের জন্য: f(xk)−f∗≤αk(f(x0)−f∗)f(x^k) - f^* \leq \alpha^k(f(x^0) - f^*) যেখানে α=max⁡{1−γμ(β−2β2),β+2β2}\alpha = \max\{1 - \gamma\mu(\beta - 2\beta^2), \beta + 2\beta^2\}।

স্টোকাস্টিক পদ্ধতি বিশ্লেষণ

উপপাদ্য 3.1: শব্দ শর্ত E[ϕ(∇ϕ∗(∇f(x))−∇ϕ∗(g(x)))]≤σ2\mathbb{E}[\phi(\nabla\phi^*(\nabla f(x)) - \nabla\phi^*(g(x)))] \leq \sigma^2 এর অধীনে: E[1K∑k=0K−1ϕ(∇ϕ∗(∇f(xk)))]≤f(x0)−f∗γK+σ2\mathbb{E}\left[\frac{1}{K}\sum_{k=0}^{K-1} \phi(\nabla\phi^*(\nabla f(x^k)))\right] \leq \frac{f(x^0) - f^*}{\gamma K} + \sigma^2

পরীক্ষামূলক সেটআপ

ডেটাসেট

  1. MNIST: হাতে লেখা সংখ্যা শ্রেণীবিভাগ, দুই-স্তরের সম্পূর্ণ সংযুক্ত নেটওয়ার্ক ব্যবহার করে
  2. CIFAR-10/100: ইমেজ শ্রেণীবিভাগ, ResNet-18/34 আর্কিটেকচার ব্যবহার করে
  3. MovieLens 100K: ম্যাট্রিক্স ফ্যাক্টরাইজেশন সমস্যা
  4. পর্যায় পুনরুদ্ধার: অ-উত্তল অপ্টিমাইজেশন সমস্যা

মূল্যায়ন মেট্রিক্স

  • প্রশিক্ষণ ক্ষতি সংগ্রহ গতি
  • পরীক্ষা নির্ভুলতা
  • গ্রেডিয়েন্ট নর্ম ∥∇f(xk)∥\|\nabla f(x^k)\|

তুলনা পদ্ধতি

  • SGD/SGDm: স্ট্যান্ডার্ড স্টোকাস্টিক গ্রেডিয়েন্ট ডিসেন্ট এবং এর মোমেন্টাম সংস্করণ
  • Adam: অভিযোজিত শেখার হার পদ্ধতি
  • GD/GDm: স্ট্যান্ডার্ড গ্রেডিয়েন্ট ডিসেন্ট এবং এর মোমেন্টাম সংস্করণ
  • AdGD-accel: স্ব-অভিযোজিত গ্রেডিয়েন্ট পদ্ধতির ত্বরান্বিত ভেরিয়েন্ট

বাস্তবায়ন বিবরণ

  • নির্দিষ্ট পদক্ষেপ দৈর্ঘ্য ব্যবহার করা
  • হাইপারবোলিক গ্রেডিয়েন্ট ডিসেন্ট (HGD): ϕ(x)=cosh⁡(∥x∥)−1\phi(x) = \cosh(\|x\|) - 1
  • বিচ্ছিন্ন সংস্করণ: ϕ(x)=∑i=1ncosh⁡(xi)−1\phi(x) = \sum_{i=1}^n \cosh(x_i) - 1

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

  1. MNIST শ্রেণীবিভাগ: iHGD দ্রুত ছোট প্রশিক্ষণ ক্ষতিতে পৌঁছায়, SGD এবং Adam এর চেয়ে উন্নত কর্মক্ষমতা
  2. CIFAR-10 শ্রেণীবিভাগ: প্রস্তাবিত পদ্ধতি SGD এবং SGDm এর সাথে তুলনীয় কর্মক্ষমতা, যা এই সমস্যার জন্য অত্যাধুনিক
  3. ম্যাট্রিক্স ফ্যাক্টরাইজেশন: iHGDm অন্যান্য পদ্ধতির চেয়ে উল্লেখযোগ্যভাবে উন্নত, বিভিন্ন র্যান্ডম ইনিশিয়ালাইজেশনে আরও স্থিতিশীল
  4. পর্যায় পুনরুদ্ধার: sHGD গ্রেডিয়েন্ট ক্লিপিং পদ্ধতির সাথে অনুরূপ কর্মক্ষমতা

মূল আবিষ্কার

  1. অভিযোজিত পদক্ষেপ দৈর্ঘ্য: দ্বিঘাতের চেয়ে দ্রুত বৃদ্ধির গতি সহ রেফারেন্স ফাংশনের জন্য, পূর্বশর্তকারী স্বাভাবিকভাবে সিগময়েড আকৃতি গঠন করে, নিহিত অভিযোজিত পদক্ষেপ দৈর্ঘ্য নিয়ম প্রদান করে
  2. স্থিতিশীলতা: ম্যাট্রিক্স ফ্যাক্টরাইজেশনের মতো অ-উত্তল সমস্যায়, প্রস্তাবিত পদ্ধতি উন্নত স্থিতিশীলতা প্রদর্শন করে
  3. ব্যাপক প্রযোজ্যতা: পদ্ধতি বিভিন্ন ধরনের মেশিন লার্নিং কাজে ভাল কর্মক্ষমতা প্রদর্শন করে

সম্পর্কিত কাজ

দ্বৈত-স্থান পূর্বশর্তকরণ/অ্যানিসোট্রপিক গ্রেডিয়েন্ট ডিসেন্ট

  • প্রাথমিকভাবে 32 এ উত্তল সারাংশ মসৃণ সমস্যার জন্য প্রবর্তিত
  • 24 এ অ্যানিসোট্রপিক ডিসেন্ট অসমতা প্রবর্তিত
  • 36 এ দেখানো হয়েছে যে পদ্ধতি অনেক জনপ্রিয় অ্যালগরিদম অন্তর্ভুক্ত করে

গ্রেডিয়েন্ট ক্লিপিং এবং সাধারণীকৃত মসৃণতা

  • 48 (L0,L1)(L_0, L_1)-মসৃণতা ধারণা প্রবর্শন করেছে
  • 47 মোমেন্টাম সহ সাধারণ ক্লিপিং কাঠামো বিশ্লেষণ করেছে
  • শিথিল শব্দ এবং মসৃণতা অনুমানের অধীনে এই ধরনের পদ্ধতি অধ্যয়নে অসংখ্য কাজ

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. অ্যানিসোট্রপিক গ্রেডিয়েন্ট ডিসেন্ট পদ্ধতি সফলভাবে ভারী বল মোমেন্টাম অন্তর্ভুক্ত করতে প্রসারিত করা
  2. ঐতিহ্যবাহী লিপশিৎজ মসৃণতার চেয়ে শিথিল শর্তে সংগ্রহ নিশ্চয়তা প্রদান করা
  3. স্টোকাস্টিক সংস্করণ তৈরি করা এবং নতুন শব্দ অনুমানের অধীনে বিশ্লেষণ করা
  4. বিভিন্ন মেশিন লার্নিং কাজে পদ্ধতির কার্যকারিতা পরীক্ষামূলকভাবে যাচাই করা

সীমাবদ্ধতা

  1. মোমেন্টাম প্যারামিটার β∈[0,0.5)\beta \in [0, 0.5) এ সীমাবদ্ধ, β∈[0,1)\beta \in [0, 1) এ প্রসারিত করা যায় না
  2. পূর্বশর্তযুক্ত লিপশিৎজ ধারাবাহিকতা অনুমান অ্যানিসোট্রপিক মসৃণতার চেয়ে আরও কঠোর
  3. স্টোকাস্টিক মোমেন্টাম পদ্ধতির সম্পূর্ণ বিশ্লেষণ প্রদান করা হয়নি

ভবিষ্যত দিকনির্দেশনা

  1. শিথিল রেফারেন্স ফাংশন অনুমানের অধীনে মোমেন্টাম অ্যালগরিদমের একীভূত বিশ্লেষণ
  2. নির্বিচারে β∈[0,1)\beta \in [0, 1) মোমেন্টাম প্যারামিটারে প্রসারিত করা
  3. সম্পূর্ণ প্রক্সিমাল গ্রেডিয়েন্ট-ধরনের অ্যালগরিদম মোমেন্টাম অন্তর্ভুক্ত করতে প্রসারিত করা
  4. স্টোকাস্টিক অ্যালগরিদমের জন্য ব্যাচ আকারের উপর নির্ভরতা অপসারণ করা এবং মোমেন্টাম অন্তর্ভুক্ত করা

গভীর মূল্যায়ন

সুবিধা

  1. তাত্ত্বিক উদ্ভাবন: অ্যানিসোট্রপিক মসৃণতার শর্তে মোমেন্টাম পদ্ধতির প্রথম বিশ্লেষণ প্রদান করা
  2. একীভূত কাঠামো: গ্রেডিয়েন্ট ক্লিপিং সহ একাধিক পদ্ধতি অরৈখিক পূর্বশর্তকরণ কাঠামোতে একীভূত করা
  3. ব্যবহারিক মূল্য: পদ্ধতি প্রকৃত মেশিন লার্নিং কাজে ভাল কর্মক্ষমতা প্রদর্শন করে
  4. বিশ্লেষণ গভীরতা: নিশ্চিত এবং স্টোকাস্টিক সেটিংসে সম্পূর্ণ তাত্ত্বিক বিশ্লেষণ প্রদান করা

অপূর্ণতা

  1. প্যারামিটার সীমাবদ্ধতা: মোমেন্টাম প্যারামিটারের সীমাবদ্ধতা (β<0.5\beta < 0.5) স্ট্যান্ডার্ড বিশ্লেষণের তুলনায় আরও কঠোর
  2. অনুমান শক্তি: কিছু তাত্ত্বিক ফলাফল অতিরিক্ত প্রযুক্তিগত অনুমান প্রয়োজন
  3. পরীক্ষার পরিসর: পরীক্ষা প্রধানত স্ট্যান্ডার্ড মেশিন লার্নিং কাজে কেন্দ্রীভূত, বিস্তৃত অ্যাপ্লিকেশন যাচাইকরণের অভাব

প্রভাব

  1. তাত্ত্বিক অবদান: অরৈখিক পূর্বশর্তকরণ পদ্ধতির তাত্ত্বিক বিশ্লেষণের জন্য নতুন সরঞ্জাম এবং অন্তর্দৃষ্টি প্রদান করা
  2. ব্যবহারিক মূল্য: স্ট্যান্ডার্ড মসৃণতা অনুমানের বাইরে অপ্টিমাইজেশন সমস্যা পরিচালনার জন্য নতুন পদ্ধতি প্রদান করা
  3. পুনরুৎপাদনযোগ্যতা: লেখকরা জনসাধারণের জন্য কোড বাস্তবায়ন প্রদান করেছেন

প্রযোজ্য পরিস্থিতি

  1. নিউরাল নেটওয়ার্ক প্রশিক্ষণ, বিশেষত যেখানে গ্রেডিয়েন্ট খুব বড় হতে পারে এমন পরিস্থিতিতে
  2. অ-উত্তল অপ্টিমাইজেশন সমস্যা, যেমন ম্যাট্রিক্স ফ্যাক্টরাইজেশন
  3. গ্রেডিয়েন্ট ক্লিপিং বা স্ট্যান্ডার্ডাইজেশন প্রয়োজন এমন অ্যাপ্লিকেশন
  4. স্ট্যান্ডার্ড লিপশিৎজ মসৃণতার বাইরে অপ্টিমাইজেশন সমস্যা

সংদর্ভ

পেপারটি ৪৮টি সংদর্ভ অন্তর্ভুক্ত করে, যা অপ্টিমাইজেশন তত্ত্ব, মেশিন লার্নিং এবং সংখ্যাসূচক পদ্ধতি সহ সম্পর্কিত ক্ষেত্রের গুরুত্বপূর্ণ কাজ কভার করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।