2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

র‍্যান্ডম ফিচার সহ মিনিম্যাক্স অপটিমাল কার্নেল টু-স্যাম্পল টেস্ট

মৌলিক তথ্য

  • পেপার আইডি: 2502.20755
  • শিরোনাম: র‍্যান্ডম ফিচার সহ মিনিম্যাক্স অপটিমাল কার্নেল টু-স্যাম্পল টেস্ট
  • লেখক: সোমিয়া মুখার্জি, ভারত কে. শ্রীপেরুম্বুদুর (পেনসিলভেনিয়া স্টেট ইউনিভার্সিটি)
  • শ্রেণীবিভাগ: math.ST cs.LG stat.ML stat.TH
  • প্রকাশনার সময়: ১৭ অক্টোবর, ২০২৫ (arXiv প্রি-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2502.20755

সারসংক্ষেপ

এই পেপারটি পুনর্নির্মাণকারী কার্নেল হিলবার্ট স্পেস (RKHS) এম্বেডিং-এর উপর ভিত্তি করে টু-স্যাম্পল পরীক্ষার সমস্যার সমাধান করে। এটি র‍্যান্ডম ফুরিয়ার ফিচার (RFF) অনুমান ব্যবহার করে একটি বর্ণালী নিয়মিতকৃত টু-স্যাম্পল পরীক্ষা পদ্ধতি প্রস্তাব করে। এই পদ্ধতি পরিসংখ্যানগত সর্বোত্তমতা বজায় রেখে গণনামূলক জটিলতা উল্লেখযোগ্যভাবে হ্রাস করে - ঘনীয় স্তর থেকে প্রায় রৈখিক স্তরে - এবং সম্পূর্ণ ডেটা-চালিত ব্যবহারিক বাস্তবায়নযোগ্য সংস্করণ প্রদান করে।

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

মূল সমস্যা

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

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. MMD পরীক্ষার সাব-অপটিমালিটি: যদিও সর্বাধিক গড় বৈষম্য (MMD) পরীক্ষা ব্যাপকভাবে প্রয়োগ করা হয়, এটি মিনিম্যাক্স সর্বোত্তমতার অভাব রয়েছে এবং শুধুমাত্র গড় এম্বেডিং বিবেচনা করে সহভেদ অপারেটর তথ্য উপেক্ষা করে
  2. বর্ণালী নিয়মিতকরণ পদ্ধতির গণনামূলক বাধা: সম্প্রতি প্রস্তাবিত বর্ণালী নিয়মিতকৃত MMD পরীক্ষা মিনিম্যাক্স সর্বোত্তমতা অর্জন করলেও, এর গণনামূলক জটিলতা O(n³), যা বড় আকারের ডেটায় এর প্রয়োগ সীমিত করে
  3. প্যারামিটার নির্বাচনের অসুবিধা: নিয়মিতকরণ প্যারামিটারের নির্বাচন অজানা বিতরণ বৈশিষ্ট্যের উপর নির্ভর করে, ডেটা-চালিত অভিযোজিত কৌশলের অভাব রয়েছে

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

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

মূল অবদান

  1. গণনামূলকভাবে দক্ষ এবং পরিসংখ্যানগতভাবে অপটিমাল পরীক্ষা: RFF-ভিত্তিক বর্ণালী নিয়মিতকৃত টু-স্যাম্পল পরীক্ষা প্রস্তাব করে, যা গণনামূলক জটিলতা O(n³) থেকে O(nl²+nld) এ হ্রাস করে, একই সাথে পর্যাপ্ত শর্তে মিনিম্যাক্স সর্বোত্তমতা বজায় রাখে
  2. তাত্ত্বিক গ্যারান্টি: RFF অনুমান ক্রম এবং পরিসংখ্যানগত সর্বোত্তমতার মধ্যে তাত্ত্বিক সংযোগ স্থাপন করে, প্রমাণ করে যে ফিচার সংখ্যা l নির্দিষ্ট শর্ত পূরণ করলে পরীক্ষার মিনিম্যাক্স সর্বোত্তমতা
  3. ব্যবহারিক অভিযোজিত সংস্করণ: পারমিউটেশন পরীক্ষার উপর ভিত্তি করে সম্পূর্ণ ডেটা-চালিত সংস্করণ বিকাশ করে, যা নিয়মিতকরণ প্যারামিটার এবং কার্নেল ফাংশনের অভিযোজিত নির্বাচন কৌশল অন্তর্ভুক্ত করে
  4. ব্যাপক পরীক্ষামূলক যাচাইকরণ: সিন্থেটিক ডেটা এবং বেঞ্চমার্ক ডেটাসেটের মাধ্যমে পদ্ধতির কার্যকারিতা যাচাই করে, গণনামূলক দক্ষতা এবং পরিসংখ্যানগত কর্মক্ষমতার মধ্যে ভাল ভারসাম্য প্রদর্শন করে

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

কাজের সংজ্ঞা

বিতরণ P এবং Q থেকে স্বাধীন নমুনা X₁:N এবং Y₁:M দেওয়া, অনুমান পরীক্ষা করুন H₀: P = Q বনাম H₁: P ≠ Q।

মূল পদ্ধতি স্থাপত্য

1. বর্ণালী নিয়মিতকরণ কাঠামো

কার্নেল ফাংশন K-এর জন্য, বর্ণালী নিয়মিতকৃত পার্থক্য সংজ্ঞায়িত করুন:

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

যেখানে T হল সমন্বিত অপারেটর, u = dP/dR - 1 হল সম্ভাবনা অনুপাত বিচ্যুতি, gλ হল নিয়মিতকরণ ফাংশন।

2. র‍্যান্ডম ফুরিয়ার ফিচার অনুমান

K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ) ফর্মের কার্নেল ফাংশনের জন্য, অনুমানিত কার্নেল তৈরি করুন:

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. অনুমানিত পরীক্ষা পরিসংখ্যান

অনুমানিত কার্নেল Kₗ-এর উপর ভিত্তি করে পরীক্ষা পরিসংখ্যান তৈরি করুন:

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

যেখানে t ফাংশন নিয়মিতকৃত সহভেদ অপারেটরের বর্গমূল জড়িত।

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

1. তাত্ত্বিক উদ্ভাবন

  • মিনিম্যাক্স সর্বোত্তমতা শর্ত: RFF ফিচার সংখ্যা l এবং পরিসংখ্যানগত সর্বোত্তমতার মধ্যে নির্ভুল সম্পর্ক স্থাপন করে
  • বহুপদী এবং সূচকীয় ক্ষয় ক্ষেত্র: সমন্বিত অপারেটর eigenvalues-এর বিভিন্ন ক্ষয় প্যাটার্ন আলাদাভাবে বিশ্লেষণ করে
  • অ-অ্যাসিম্পটোটিক বিশ্লেষণ: সীমিত নমুনায় কর্মক্ষমতা গ্যারান্টি প্রদান করে

2. অ্যালগরিদম উদ্ভাবন

  • অভিযোজিত নিয়মিতকরণ: যৌথ পরীক্ষার মাধ্যমে নিয়মিতকরণ প্যারামিটারের ডেটা-চালিত নির্বাচন বাস্তবায়ন করে
  • কার্নেল ফাংশন অভিযোজন: একাধিক কার্নেল ফাংশনের অভিযোজিত নির্বাচনে সম্প্রসারিত করে
  • পারমিউটেশন পরীক্ষা বাস্তবায়ন: সম্পূর্ণ ডেটা-চালিত সমালোচনামূলক মান গণনা প্রদান করে

3. গণনামূলক উদ্ভাবন

  • দক্ষ অ্যালগরিদম: বিস্তারিত গণনামূলক জটিলতা বিশ্লেষণ এবং অপ্টিমাইজেশন বাস্তবায়ন
  • সমান্তরালকরণ: পারমিউটেশন পরীক্ষার প্রাকৃতিক সমান্তরালকরণ বৈশিষ্ট্য

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

ডেটাসেট

  1. সিন্থেটিক ডেটা:
    • গাউসীয় গড় স্থানান্তর: P = N(0,I), Q = N(μ,I)
    • গাউসীয় স্কেল স্থানান্তর: P = N(0,I), Q = N(0,σ²I)
    • কচি মধ্যমা স্থানান্তর: বিভিন্ন মধ্যমা সহ কচি বিতরণ
  2. বাস্তব ডেটা:
    • MNIST ডেটাসেট: 7×7 পিক্সেল হস্তলিখিত সংখ্যা চিত্র, মাত্রা d=49
    • বিভিন্ন সংখ্যা উপসেটের বিতরণ পার্থক্য সনাক্তকরণ

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

  • পরিসংখ্যানগত শক্তি (Power): বিকল্প অনুমানের অধীনে মূল অনুমান সঠিকভাবে প্রত্যাখ্যান করার সম্ভাবনা
  • গণনামূলক সময়: অ্যালগরিদম চালানোর সময়ের তুলনা
  • প্রথম ধরনের ত্রুটি: α=0.05 স্তরে নিয়ন্ত্রণ

তুলনামূলক পদ্ধতি

  • নির্ভুল অভিযোজিত পরীক্ষা: সম্পূর্ণ কার্নেল ম্যাট্রিক্সের উপর ভিত্তি করে বর্ণালী নিয়মিতকৃত পরীক্ষা
  • বিভিন্ন RFF ফিচার সংখ্যা: l ∈ {1,3,5,7,9,15,20}-এর কর্মক্ষমতা তুলনা

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

  • নিয়মিতকরণ ফাংশন: Showalter regularizer gλ(x) = (1-e^(-x/λ))/x
  • কার্নেল ফাংশন: গাউসীয় এবং ল্যাপ্লেস কার্নেল, ব্যান্ডউইথ অভিযোজিত নির্বাচন
  • পারমিউটেশন সংখ্যা: RFF সংস্করণ B=550-800, নির্ভুল সংস্করণ B'=250-450

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

প্রধান ফলাফল

1. পরিসংখ্যানগত কর্মক্ষমতা

  • গাউসীয় গড় স্থানান্তর: RFF ফিচার সংখ্যা l≥7 হলে, শক্তি নির্ভুল পদ্ধতির কাছাকাছি
  • গাউসীয় স্কেল স্থানান্তর: l≥5 হলে ভাল কর্মক্ষমতা অর্জন করে
  • কচি বিতরণ: ভারী-লেজ বিতরণ পরিচালনা করতে আরও বেশি ফিচার প্রয়োজন (l≥10-15)
  • MNIST ডেটা: l≥15 হলে জটিল বাস্তব ডেটায় ভাল কর্মক্ষমতা

2. গণনামূলক দক্ষতা

উল্লেখযোগ্য গণনামূলক সময় সাশ্রয়:

  • গাউসীয় পরীক্ষা: RFF পদ্ধতি মাত্র 33-44% গণনামূলক সময় প্রয়োজন
  • স্কেল স্থানান্তর: 30-40% সময় খরচ
  • কচি পরীক্ষা: মাত্র 5-6% গণনামূলক সময়
  • MNIST: 5-15% সময় খরচ

3. তাত্ত্বিক যাচাইকরণ

পরীক্ষামূলক ফলাফল তাত্ত্বিক পূর্বাভাস যাচাই করে:

  • ফিচার সংখ্যার প্রয়োজনীয়তা ডেটা মাত্রা এবং বিতরণ জটিলতার সাথে সম্পর্কিত
  • গণনামূলক-পরিসংখ্যানগত ট্রেড-অফ তাত্ত্বিক বিশ্লেষণের সাথে সামঞ্জস্যপূর্ণ

অ্যাবলেশন পরীক্ষা

বিভিন্ন RFF ফিচার সংখ্যার তুলনার মাধ্যমে, যাচাই করে:

  1. ফিচার সংখ্যা থ্রেশহোল্ডের অস্তিত্ব
  2. অত্যন্ত কম ফিচার শক্তি হ্রাস করে
  3. উপযুক্ত ফিচার সংখ্যা সর্বোত্তম ভারসাম্য অর্জন করে

পরীক্ষামূলক আবিষ্কার

  1. মাত্রা প্রভাব: উচ্চ-মাত্রিক ডেটা আরও বেশি RFF ফিচার প্রয়োজন
  2. বিতরণ ধরনের প্রভাব: ভারী-লেজ বিতরণ কর্মক্ষমতা নিশ্চিত করতে আরও বেশি ফিচার প্রয়োজন
  3. ব্যবহারিক থ্রেশহোল্ড: তাত্ত্বিকভাবে প্রয়োজনীয় ফিচার সংখ্যা অনুশীলনে যুক্তিসঙ্গতভাবে হ্রাস করা যায়

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

কার্নেল পদ্ধতি টু-স্যাম্পল পরীক্ষা

  • MMD পরীক্ষা: Gretton et al. (2006, 2012)-এর যুগান্তকারী কাজ
  • মিনিম্যাক্স সর্বোত্তমতা: Li & Yuan (2024), Schrab et al. (2023)-এর সাম্প্রতিক অগ্রগতি
  • বর্ণালী নিয়মিতকরণ: Hagrass et al. (2024)-এর তাত্ত্বিক অগ্রগতি

র‍্যান্ডম ফিচার অনুমান

  • RFF তত্ত্ব: Rahimi & Recht (2007)-এর মৌলিক কাঠামো
  • MMD ত্বরণ: Zhao & Meng (2015), Choi & Kim (2024)-এর প্রয়োগ
  • গণনামূলক-পরিসংখ্যানগত ট্রেড-অফ: Sriperumbudur & Sterge (2022)-এর তাত্ত্বিক বিশ্লেষণ

এই পেপারের সুবিধা

বিদ্যমান কাজের তুলনায় প্রধান সুবিধা:

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

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

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

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

সীমাবদ্ধতা

  1. ফিচার সংখ্যা নির্বাচন: যদিও তাত্ত্বিক নির্দেশনা প্রদান করে, ব্যবহারিক নির্বাচন এখনও অভিজ্ঞতামূলক সমন্বয় প্রয়োজন
  2. কার্নেল ফাংশন নির্ভরতা: কর্মক্ষমতা এখনও কার্নেল ফাংশন নির্বাচনের উপর নির্ভর করে
  3. ভারী-লেজ বিতরণ: চরম ভারী-লেজ বিতরণের জন্য বিপুল সংখ্যক ফিচার প্রয়োজন হতে পারে

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

  1. অন্যান্য অনুমান পদ্ধতি: Nyström ইত্যাদি বিকল্প অনুমান কৌশল অন্বেষণ করে
  2. সস্তা পারমিউটেশন পরীক্ষা: গণনামূলক খরচ আরও হ্রাস করতে সস্তা পারমিউটেশন পরীক্ষার সাথে সংমিশ্রণ করে
  3. স্বয়ংক্রিয় প্যারামিটার সমন্বয়: আরও বুদ্ধিমান হাইপারপ্যারামিটার নির্বাচন কৌশল বিকাশ করে

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

শক্তি

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

অপূর্ণতা

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

প্রভাব

  1. তাত্ত্বিক মূল্য: কার্নেল পদ্ধতির গণনামূলক-পরিসংখ্যানগত ট্রেড-অফের জন্য নতুন তাত্ত্বিক কাঠামো প্রদান করে
  2. ব্যবহারিক মূল্য: বড় আকারের ডেটার টু-স্যাম্পল পরীক্ষায় গুরুত্বপূর্ণ প্রয়োগ সম্ভাবনা রয়েছে
  3. পদ্ধতিগত অবদান: পরিসংখ্যানগত পরীক্ষায় RFF অনুমানের প্রয়োগ সম্পর্কিত গবেষণার জন্য নতুন চিন্তাভাবনা প্রদান করে

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

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

সংদর্ভ

  1. Gretton, A., et al. (2012). A kernel two-sample test. JMLR.
  2. Hagrass, O., et al. (2024). Spectral regularized kernel two-sample tests. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. NIPS.
  4. Choi, I., & Kim, I. (2024). Computational-statistical trade-off in kernel two-sample testing with random Fourier features.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). Approximate kernel PCA: Computational versus statistical trade-off. Annals of Statistics.

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