プライバシー付き決定リストの学習と微分プライバシーに基づく Winnow 法

arXiv:2602.07370v1 発表 タイプ：新規 要約：我々は、PAC モデルおよびオンラインモデルにおける決定リストの学習と大境界半空間の学習という古典的問題において、新たな微分プライバシーアルゴリズムを提供します。PAC モデルにおいては、非プライバシー付きアルゴリズムと比べて最小のサンプルオーバーヘッドで決定リストを学習する計算効率的なアルゴリズムを提供します。オンラインモデルにおいては、次元の多項対数値誤差 bound および閾値の逆多項式誤差 bound を持つ半空間の学習に対する Winnow アルゴリズムのプライバシー対応バージョンを提供します。その応用として、オンラインモデルにおけるプライバシー付き決定リストの学習方法を記述し、状態の最先端の非プライバシー付き保証との定性的な一致を達成することを示します。

arXiv:2602.07370v1 Announce Type: new Abstract: We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms. In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the dimension and inverse polynomial in the margin. As an application, we describe how to privately learn decision lists in the online model, qualitatively matching state-of-the art non-private guarantees.