مقاله تراز کوواریانس: از تخمین حداکثر احتمال تا گروموف-واسرشتاین

چکیده

Feature alignment methods are used in many scientific disciplines for data pooling, annotation, and comparison. As an instance of a permutation learning problem, feature alignment presents significant statistical and computational challenges. In this work, we propose the covariance alignment model to study and compare various alignment methods and establish a minimax lower bound for covariance alignment that has a non-standard dimension scaling because of the presence of a nuisance parameter. This lower bound is in fact minimax optimal and is achieved by a natural quasi MLE. However, this estimator involves a search over all permutations which is computationally infeasible even when the problem has moderate size. To overcome this limitation, we show that the celebrated Gromov-Wasserstein algorithm from optimal transport which is more amenable to fast implementation even on large-scale problems is also minimax optimal. These results give the first statistical justification for the deployment of the Gromov-Wasserstein algorithm in practice.

چکیده به فارسی (ترجمه ماشینی)

روشهای تراز ویژگی در بسیاری از رشته های علمی برای جمع آوری داده ها ، حاشیه نویسی و مقایسه استفاده می شود.به عنوان نمونه ای از یک مشکل یادگیری جابجایی ، تراز ویژگی چالش های آماری و محاسباتی قابل توجهی را نشان می دهد.در این کار ، ما مدل تراز کواریانس را برای مطالعه و مقایسه روشهای مختلف تراز و ایجاد یک محدوده پایین تر برای تراز کواریانس که به دلیل وجود یک پارامتر مزاحمت ، دارای مقیاس ابعاد غیر استاندارد است ، پیشنهاد می کنیم.این محدوده پایین در واقع Minimax بهینه است و توسط یک شبه طبیعی طبیعی حاصل می شود.با این حال ، این برآوردگر شامل جستجوی تمام مجوزها است که از نظر محاسباتی غیرقابل نفوذ است حتی اگر مشکل دارای اندازه متوسط باشد.برای غلبه بر این محدودیت ، ما نشان می دهیم که الگوریتم مشهور Gromov-Wasserstein از حمل و نقل بهینه که برای اجرای سریع حتی در مورد مشکلات در مقیاس بزرگ قابل تحمل تر است نیز بهینه است.این نتایج اولین توجیه آماری را برای استقرار الگوریتم Gromov-Wasserstein در عمل نشان می دهد.