2025-11-11T21:07:14.953280

Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

Qiao, Maros
We propose and study Sparse Polyak, a variant of Polyak's adaptive step size, designed to solve high-dimensional statistical estimation problems where the problem dimension is allowed to grow much faster than the sample size. In such settings, the standard Polyak step size performs poorly, requiring an increasing number of iterations to achieve optimal statistical precision-even when, the problem remains well conditioned and/or the achievable precision itself does not degrade with problem size. We trace this limitation to a mismatch in how smoothness is measured: in high dimensions, it is no longer effective to estimate the Lipschitz smoothness constant. Instead, it is more appropriate to estimate the smoothness restricted to specific directions relevant to the problem (restricted Lipschitz smoothness constant). Sparse Polyak overcomes this issue by modifying the step size to estimate the restricted Lipschitz smoothness constant. We support our approach with both theoretical analysis and numerical experiments, demonstrating its improved performance.
academic

Sparse Polyak: উচ্চ-মাত্রিক M-অনুমানের জন্য একটি অভিযোজনশীল পদক্ষেপ আকার নিয়ম

মৌলিক তথ্য

  • পেপার আইডি: 2509.09802
  • শিরোনাম: Sparse Polyak: উচ্চ-মাত্রিক M-অনুমানের জন্য একটি অভিযোজনশীল পদক্ষেপ আকার নিয়ম
  • লেখক: Tianqi Qiao (টেক্সাস A&M বিশ্ববিদ্যালয়), Marie Maros (টেক্সাস A&M বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.OC cs.LG stat.ML
  • প্রকাশনার সময়/সম্মেলন: নিউরাল ইনফরমেশন প্রসেসিং সিস্টেমস সম্মেলনের ৩৯তম সংস্করণ (NeurIPS 2025)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2509.09802

সারসংক্ষেপ

এই পেপারটি Sparse Polyak প্রস্তাব করে এবং অধ্যয়ন করে, যা Polyak অভিযোজনশীল পদক্ষেপের একটি রূপান্তর যা উচ্চ-মাত্রিক পরিসংখ্যানগত অনুমান সমস্যা সমাধানের জন্য বিশেষভাবে ডিজাইন করা হয়েছে, যেখানে সমস্যার মাত্রা নমুনা আকারের চেয়ে অনেক দ্রুত বৃদ্ধি পায়। এই সেটিংয়ে, মান Polyak পদক্ষেপ দুর্বল কর্মক্ষমতা প্রদর্শন করে এবং সর্বোত্তম পরিসংখ্যানগত নির্ভুলতা অর্জনের জন্য ক্রমবর্ধমান বেশি পুনরাবৃত্তির প্রয়োজন হয়—এমনকি যখন সমস্যা সুশৃঙ্খল থাকে এবং/অথবা অর্জনযোগ্য নির্ভুলতা নিজেই সমস্যার স্কেলের সাথে হ্রাস পায় না। এই পেপারটি এই সীমাবদ্ধতাকে মসৃণতা পরিমাপের পদ্ধতিতে অমিলের জন্য দায়ী করে: উচ্চ-মাত্রিকতায়, Lipschitz মসৃণতা ধ্রুবক অনুমান আর কার্যকর নয়। পরিবর্তে, সমস্যা-প্রাসঙ্গিক নির্দিষ্ট দিকগুলিতে সীমাবদ্ধ মসৃণতা অনুমান করা আরও উপযুক্ত (সীমাবদ্ধ Lipschitz মসৃণতা ধ্রুবক)। Sparse Polyak পদক্ষেপ সূত্র সংশোধন করে সীমাবদ্ধ Lipschitz মসৃণতা ধ্রুবক অনুমান করে এই সমস্যা অতিক্রম করে।

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

সমস্যা সংজ্ঞা

এই পেপারটি উচ্চ-মাত্রিক পরিসংখ্যানগত অনুমান সমস্যা অধ্যয়ন করে:

min_{θ∈R^d: ||θ||_0≤s} f(θ) = (1/n) Σ_{i=1}^n ℓ(z_i, θ)

যেখানে মাত্রা d নমুনা আকার n এর তুলনায় খুব দ্রুত বৃদ্ধি পায়, অর্থাৎ d/n → ∞।

মূল সমস্যা

  1. উচ্চ-মাত্রিক চ্যালেঞ্জ: উচ্চ-মাত্রিক সেটিংয়ে, ঐতিহ্যবাহী Lipschitz মসৃণতা ধ্রুবক অনুমান ব্যর্থ হয়, যা পদক্ষেপ নির্বাচনকে অত্যন্ত রক্ষণশীল করে তোলে
  2. কর্মক্ষমতা অবনতি: মান Polyak পদক্ষেপ সমস্যার মাত্রা বৃদ্ধির সাথে সাথে উল্লেখযোগ্যভাবে হ্রাস পায়, এমনকি সমস্যা শর্ত সংখ্যা অপরিবর্তিত থাকলেও
  3. হার অপরিবর্তনীয়তার অভাব: বিদ্যমান পদ্ধতিগুলি উচ্চ-মাত্রিক সেটিংয়ে স্থির পদক্ষেপ IHT এর সমান হার নিশ্চিতকরণ বজায় রাখতে ব্যর্থ হয়

গবেষণা প্রেরণা

  • পুনরাবৃত্তিমূলক কঠিন থ্রেশহোল্ডিং (IHT) অ্যালগরিদম উচ্চ-মাত্রিক বিরল পুনরুদ্ধারে চমৎকার কর্মক্ষমতা প্রদর্শন করে, কিন্তু সীমাবদ্ধ Lipschitz মসৃণতা (RSS) ধ্রুবক L̄ জানার প্রয়োজন
  • বিদ্যমান অভিযোজনশীল পদক্ষেপ পদ্ধতিগুলি উচ্চ-মাত্রিক সেটিংয়ে তাত্ত্বিক গ্যারান্টি এবং ব্যবহারিক কর্মক্ষমতার অভাব রাখে
  • এমন একটি পদ্ধতির প্রয়োজন যা পদক্ষেপ স্বয়ংক্রিয়ভাবে সামঞ্জস্য করতে পারে এবং হার অপরিবর্তনীয়তা বজায় রাখতে পারে

মূল অবদান

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

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

কাজের সংজ্ঞা

সীমাবদ্ধ অপ্টিমাইজেশন সমস্যা বিবেচনা করুন:

min_{θ∈R^d: ||θ||_0≤s} f(θ) = (1/n) Σ_{i=1}^n ℓ(z_i, θ)

যেখানে:

  • θ হল d-মাত্রিক পরামিতি ভেক্টর, সর্বাধিক s অ-শূন্য উপাদানের সাথে সীমাবদ্ধ
  • f(θ) হল অভিজ্ঞতামূলক ঝুঁকি ফাংশন
  • লক্ষ্য হল উচ্চ-মাত্রিক সেটিংয়ে (d/n → ∞) দক্ষতার সাথে সমাধান করা

মূল অ্যালগরিদম: Sparse Polyak পদক্ষেপ

অ্যালগরিদম 1: Sparse Polyak পদক্ষেপ-আকার সহ IHT

ইনপুট: ফাংশন f, লক্ষ্য ফাংশন মান f̂, বিরল পরামিতি s, পুনরাবৃত্তি সংখ্যা T
প্রাথমিকীকরণ: θ_0 ∈ R^d, ||θ_0||_0 ≤ s
t = 0 থেকে T-1 এর জন্য:
    পদক্ষেপ গণনা করুন: γ_t = max{f(θ_t) - f̂, 0} / (5||HT_s(∇f(θ_t))||²)
    আপডেট করুন: θ_{t+1} = HT_s(θ_t - γ_t∇f(θ_t))
শেষ করুন

মূল উদ্ভাবন পয়েন্ট

  1. সংশোধিত পদক্ষেপ সূত্র:
    • ঐতিহ্যবাহী Polyak: γ_t = (f(θ_t) - f̂) / ||∇f(θ_t)||²
    • Sparse Polyak: γ_t = (f(θ_t) - f̂) / ||HT_s(∇f(θ_t))||²
  2. কঠিন থ্রেশহোল্ডিং অপারেটর: HT_s s সর্ববৃহৎ পরিমাণ উপাদান সংরক্ষণ করে, অন্যদের শূন্যে সেট করে
  3. তাত্ত্বিক ভিত্তি:
    • সীমাবদ্ধ শক্তিশালী উত্তলতা (RSC) এবং সীমাবদ্ধ মসৃণতা (RSS) শর্ত ব্যবহার করা
    • L̄ = L + 3τs, μ̄ = μ - 3τs, κ̄ = L̄/μ̄

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

  1. মাত্রা-স্বাধীন পদক্ষেপ: ||∇f(θ_t)||² এর পরিবর্তে ||HT_s(∇f(θ_t))||² ব্যবহার করে, মাত্রা d এর সাথে সম্পর্কিত স্কেলিং এড়ানো
  2. সীমাবদ্ধ দিক অনুমান: সম্পূর্ণ স্থানের পরিবর্তে বিরল দিকগুলিতে মসৃণতার উপর ফোকাস করা
  3. দ্বৈত-লুপ অ্যালগরিদম: অজানা লক্ষ্য মান পরিচালনার জন্য অ্যালগরিদম 2 প্রদান করা

তাত্ত্বিক বিশ্লেষণ

প্রধান উপপাদ্য

উপপাদ্য 1 (প্রধান সংগ্রহ ফলাফল): RSC এবং RSS অনুমানের অধীনে, যখন s ≥ (240κ̄)²s*:

  • রৈখিক সংগ্রহ: ||θ_{t+1} - θ̂||² ≤ (1 - 1/(80κ̄))||θ_t - θ̂||²
  • চূড়ান্ত নির্ভুলতা: O(||HT_s(∇f(θ̂))||²/μ̄²)

উপসিদ্ধান্ত 1 (সমর্থন পুনরুদ্ধার): সংকেত-থেকে-শব্দ অনুপাত শর্ত |θ̂|_min ≥ 7||HT_s(∇f(θ̂))||/μ̄ এর অধীনে, অ্যালগরিদম সমর্থন সেট সঠিকভাবে পুনরুদ্ধার করতে পারে।

পরিসংখ্যানগত মডেল গ্যারান্টি

বিরল লজিস্টিক রিগ্রেশন (উপসিদ্ধান্ত 2):

  • সংগ্রহ হার: (1 - 1/(80κ̄))
  • পরিসংখ্যানগত নির্ভুলতা: O(s log d / n)
  • সম্ভাব্যতা গ্যারান্টি: কমপক্ষে 1 - e^{-c_0 n} - 2/d

ম্যাট্রিক্স রিগ্রেশন (উপসিদ্ধান্ত 3):

  • নিম্ন-র‍্যাঙ্ক ম্যাট্রিক্স পুনরুদ্ধারের জন্য প্রযোজ্য
  • অনুরূপ সংগ্রহ গ্যারান্টি এবং পরিসংখ্যানগত নির্ভুলতা

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

সংশ্লেষিত ডেটা পরীক্ষা

  • মাত্রা সেটিং: d ∈ {5000, 10000, 20000}
  • বিরলতা: s* = 300
  • নমুনা আকার: n = ⌈α s log d⌉, α = 5
  • ডিজাইন ম্যাট্রিক্স: সময় সিরিজ কাঠামো, সম্পর্ক পরামিতি ω = 0.5
  • শব্দ সেটিং: রৈখিক রিগ্রেশন σ² = 0.25, লজিস্টিক রিগ্রেশন মডেল (4) অনুযায়ী উৎপন্ন

বাস্তব ডেটা পরীক্ষা

  • রৈখিক রিগ্রেশন: বড় আকারের ওয়েভ এনার্জি ফার্ম ডেটাসেট (120 নমুনা, 149 বৈশিষ্ট্য)
  • লজিস্টিক রিগ্রেশন: অণু Musk ডেটাসেট (120 নমুনা, 166 বৈশিষ্ট্য)
  • বিরলতা: s = 20

তুলনা পদ্ধতি

  • স্থির পদক্ষেপ সহ IHT γ = 2/(3L̄)
  • ক্লাসিক্যাল Polyak পদক্ষেপ
  • গ্রিড অনুসন্ধান অপ্টিমাইজড স্থির পদক্ষেপ

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

প্রধান ফলাফল

  1. হার অপরিবর্তনীয়তা যাচাইকরণ:
    • Sparse Polyak বিভিন্ন মাত্রা d জুড়ে সামঞ্জস্যপূর্ণ সংগ্রহ আচরণ বজায় রাখে
    • ক্লাসিক্যাল Polyak মাত্রা বৃদ্ধির সাথে উল্লেখযোগ্যভাবে কর্মক্ষমতা হ্রাস করে
    • যখন log(d)/n ধ্রুবক থাকে, পুনরাবৃত্তি সংখ্যা মূলত অপরিবর্তিত থাকে
  2. সংগ্রহ গতি তুলনা:
    • স্থির পদক্ষেপের তুলনায়, Sparse Polyak সাধারণত দ্রুত সংগ্রহ করে
    • লজিস্টিক রিগ্রেশনে সুবিধা আরও স্পষ্ট (স্থানীয় বক্রতা অভিযোজনের কারণে)
    • লক্ষ্য মান f̂ এর পছন্দ সরাসরি অর্জনযোগ্য নির্ভুলতা প্রভাবিত করে
  3. বাস্তব ডেটা কর্মক্ষমতা:
    • লজিস্টিক রিগ্রেশন কাজ: Sparse Polyak > স্থির পদক্ষেপ > ক্লাসিক্যাল Polyak
    • রৈখিক রিগ্রেশন কাজ: সর্বোত্তম স্থির পদক্ষেপ সামান্য উন্নত, কিন্তু Sparse Polyak এখনও ক্লাসিক্যাল Polyak এর চেয়ে ভাল

মূল আবিষ্কার

  1. মাত্রা স্কেলিং সমস্যা: উচ্চ-মাত্রিকতায়, ||∇f(θ_t)|| ≤ √(d/s)||HT_s(∇f(θ_t))||, সবচেয়ে খারাপ ক্ষেত্রে সমতা ধরে
  2. পদক্ষেপ রক্ষণশীলতা: সম্পূর্ণ গ্রেডিয়েন্ট নর্ম ব্যবহার অত্যন্ত রক্ষণশীল পদক্ষেপের দিকে পরিচালিত করে, d বৃদ্ধির সাথে খারাপ হয়
  3. অভিযোজনীয় সুবিধা: অভিযোজনশীল পদক্ষেপ স্থানীয় বক্রতা তথ্য ব্যবহার করতে পারে, অ-সমান বক্রতা সমস্যায় আরও ভাল কর্মক্ষমতা করে

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

বিরল পুনরুদ্ধার অ্যালগরিদম

  • IHT এবং রূপান্তর: Blumensath & Davies (2009), Jain et al. (2014)
  • অন্যান্য পদ্ধতি: Matching Pursuit, OMP, CoSaMP
  • ত্বরান্বিত সংস্করণ: Khanna & Kyrillidis (2018), Zhou et al. (2018)

অভিযোজনশীল পদক্ষেপ পদ্ধতি

  • Polyak পদক্ষেপ: Polyak (1969), সাম্প্রতিক পুনরুজ্জীবন Ren et al. (2022)
  • স্থানীয় Lipschitz পদ্ধতি: Malitsky & Mishchenko (2020, 2024)
  • সীমাবদ্ধ সমস্যা: Cheng & Li (2012), Devanathan & Boyd (2024)

উচ্চ-মাত্রিক পরিসংখ্যান

  • তাত্ত্বিক ভিত্তি: Agarwal et al. (2012), Loh & Wainwright (2015)
  • শর্ত প্রয়োজনীয়তা: RSC/RSS, RIP শর্তের উন্নয়ন

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

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

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

সীমাবদ্ধতা

  1. ধ্রুবক ফ্যাক্টর: পদক্ষেপ সূত্রে 1/5 ফ্যাক্টর বিশ্লেষণ পণ্য হতে পারে, ব্যবহারিকভাবে প্রয়োজনীয় নয়
  2. প্রাথমিকীকরণ প্রয়োজনীয়তা: কিছু ফলাফল নির্দিষ্ট প্রাথমিকীকরণ শর্তের প্রয়োজন
  3. শর্ত সীমাবদ্ধতা: এখনও RSC/RSS শর্তের প্রয়োজন, যদিও RIP শর্তের চেয়ে আরও শিথিল
  4. পরামিতি নির্বাচন: লক্ষ্য ফাংশন মান f̂ পূর্বে জানা বা অনুমান করার প্রয়োজন

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

  1. অন্যান্য অ্যালগরিদমে সম্প্রসারণ: লেখকরা অনুমান করেন যে BB পদ্ধতি ইত্যাদিও অনুরূপ উন্নতির প্রয়োজন হতে পারে
  2. দুর্বল শর্ত: আরও তাত্ত্বিক অনুমান শর্ত শিথিল করা
  3. ব্যবহারিক প্রয়োগ: আরও বাস্তব সমস্যায় পদ্ধতি কার্যকারিতা যাচাই করা
  4. গণনা অপ্টিমাইজেশন: গণনা জটিলতা হ্রাস করা, ব্যবহারিকতা উন্নত করা

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

সুবিধা

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

অপূর্ণতা

  1. শর্ত শক্তিশালী: s ≥ (240κ̄)²s* প্রয়োজনীয়তা কিছু প্রয়োগে অত্যন্ত কঠোর হতে পারে
  2. ধ্রুবক বিশ্লেষণ: কিছু ধ্রুবক যথেষ্ট টাইট নাও হতে পারে, ব্যবহারিক কর্মক্ষমতা প্রভাবিত করে
  3. প্রযোজ্যতা পরিসীমা: প্রধানত বিরল সমস্যার জন্য, অন্যান্য কাঠামোগত সমস্যায় সম্প্রসারণ অজানা
  4. গণনা ওভারহেড: প্রতিটি পুনরাবৃত্তিতে কঠিন থ্রেশহোল্ডিং অপারেশন গণনা করার প্রয়োজন, গণনা খরচ বৃদ্ধি করে

প্রভাব

  1. তাত্ত্বিক মূল্য: উচ্চ-মাত্রিক অপ্টিমাইজেশন তত্ত্বে গুরুত্বপূর্ণ অবদান
  2. ব্যবহারিক তাৎপর্য: মেশিন লার্নিংয়ে বিরল সমস্যার জন্য নতুন সরঞ্জাম প্রদান করে
  3. অনুপ্রেরণামূলক: উচ্চ-মাত্রিক সেটিংয়ে অন্যান্য অভিযোজনশীল পদ্ধতির উন্নতির জন্য চিন্তাভাবনা প্রদান করে
  4. পুনরুৎপাদনযোগ্যতা: তাত্ত্বিক বিশ্লেষণ সম্পূর্ণ, অ্যালগরিদম বর্ণনা স্পষ্ট, বাস্তবায়ন সহজ

প্রযোজ্য দৃশ্যকল্প

  1. উচ্চ-মাত্রিক বিরল রিগ্রেশন: বৈশিষ্ট্য নির্বাচন, জিনোমিক্স ডেটা বিশ্লেষণ
  2. সংকুচিত সংবেদন: সংকেত পুনর্নির্মাণ, চিত্র প্রক্রিয়াকরণ
  3. মেশিন লার্নিং: গভীর শিক্ষায় বিরলতা, নিউরাল নেটওয়ার্ক প্রুনিং
  4. পরিসংখ্যানগত শিক্ষা: উচ্চ-মাত্রিক পরিসংখ্যানগত অনুমান, পরিবর্তনশীল নির্বাচন

রেফারেন্স

মূল রেফারেন্সগুলি অন্তর্ভুক্ত করে:

  1. Jain et al. (2014) - IHT তাত্ত্বিক ভিত্তি
  2. Agarwal et al. (2012) - RSC/RSS শর্ত
  3. Polyak (1969) - মূল Polyak পদক্ষেপ
  4. Loh & Wainwright (2015) - উচ্চ-মাত্রিক পরিসংখ্যান তত্ত্ব
  5. Malitsky & Mishchenko (2020) - আধুনিক অভিযোজনশীল পদ্ধতি

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ-মানের তাত্ত্বিক পেপার যা উচ্চ-মাত্রিক অপ্টিমাইজেশনে একটি গুরুত্বপূর্ণ সমস্যার জন্য উদ্ভাবনী সমাধান প্রস্তাব করে। তাত্ত্বিক বিশ্লেষণ কঠোর, পরীক্ষামূলক যাচাইকরণ পর্যাপ্ত, সম্পর্কিত ক্ষেত্রে গুরুত্বপূর্ণ অবদান মূল্য রয়েছে। যদিও কিছু প্রযুক্তিগত সীমাবদ্ধতা রয়েছে, সামগ্রিকভাবে এটি ক্ষেত্রে একটি গুরুত্বপূর্ণ অগ্রগতি।