ترجمه فارسی مقاله محاسبات سریع جان بیضی با بهینه سازی حریم خصوصی دیفرانسیل

چکیده

Determining the John ellipsoid – the largest volume ellipsoid contained within a convex polytope – is a fundamental problem with applications in machine learning, optimization, and data analytics. Recent work has developed fast algorithms for approximating the John ellipsoid using sketching and leverage score sampling techniques. However, these algorithms do not provide privacy guarantees for sensitive input data. In this paper, we present the first differentially private algorithm for fast John ellipsoid computation. Our method integrates noise perturbation with sketching and leverage score sampling to achieve both efficiency and privacy. We prove that (1) our algorithm provides $(ε,δ)$-differential privacy, and the privacy guarantee holds for neighboring datasets that are $ε_0$-close, allowing flexibility in the privacy definition; (2) our algorithm still converges to a $(1+ξ)$-approximation of the optimal John ellipsoid in $O(ξ^{-2}(\log(n/δ_0) + (Lε_0)^{-2}))$ iterations where $n$ is the number of data point, $L$ is the Lipschitz constant, $δ_0$ is the failure probability, and $ε_0$ is the closeness of neighboring input datasets. Our theoretical analysis demonstrates the algorithm’s convergence and privacy properties, providing a robust approach for balancing utility and privacy in John ellipsoid computation. This is the first differentially private algorithm for fast John ellipsoid computation, opening avenues for future research in privacy-preserving optimization techniques.

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

تعیین جان بیضوی – بیشترین حجم بیضوی موجود در یک پلی تئوپ محدب – یک مشکل اساسی در برنامه های کاربردی در یادگیری ماشین ، بهینه سازی و تجزیه و تحلیل داده ها است.کار اخیر با استفاده از تکنیک های نمونه گیری از طراحی و اهرم ، الگوریتم های سریع را برای تقریب جان بیضوی ایجاد کرده است.با این حال ، این الگوریتم ها برای داده های ورودی حساس ضمانت حریم خصوصی را ارائه نمی دهند.در این مقاله ، ما اولین الگوریتم خصوصی متفاوت را برای محاسبه سریع جان بیضوی ارائه می دهیم.روش ما برای دستیابی به کارآیی و حریم خصوصی ، آشفتگی سر و صدا را با نمونه گیری از طرح و نمونه گیری از اهرم ادغام می کند.ما ثابت می کنیم که (1) الگوریتم ما $ (ε ، δ) $-حریم خصوصی دیفرانسیل را فراهم می کند ، و ضمانت حفظ حریم خصوصی برای مجموعه داده های همسایه که $ ε_0 $ $ هستند ، در اختیار دارد و امکان انعطاف پذیری در تعریف حریم خصوصی را فراهم می کند.(2) الگوریتم ما هنوز هم به یک $ (1 + ξ) $-تقریب جان بیضی بهینه در $ o (ξ^{-2} (\ log (n/δ_0) + (lε_0)^{-2} همگرا می شود.)) تکرارهای $ که در آن $ n $ تعداد داده های داده ، $ l $ ثابت Lipschitz است ، $ Δ_0 $ احتمال خرابی است و $ ε_0 $ نزدیکی مجموعه داده های ورودی همسایه است.تجزیه و تحلیل نظری ما نشان دهنده همگرایی و خصوصیات حفظ حریم خصوصی الگوریتم است و یک رویکرد قوی برای تعادل ابزار و حفظ حریم خصوصی در محاسبات جان بیضوی ارائه می دهد.این اولین الگوریتم خصوصی متفاوت برای محاسبات سریع جان بیضوی است و راه های تحقیقات آینده را در تکنیک های بهینه سازی حفظ حریم خصوصی باز می کند.