重い尾を持つ確率的凸最適化に対する、純粋{}-微分プライバシーでの最適レート

Abstract

本研究では、純粋なε-微分プライバシー（DP）下で、裾の重い（heavy-tailed）勾配を伴う確率的凸最適化（SCO）を扱う。損失の最悪ケースのリプシッツ定数パラメータに対する上界を仮定する代わりに、有界なk次モーメントのみを仮定する。この仮定により、無界で裾の重い確率的勾配分布が許容され、より鋭い過剰リスク（excess risk）の評価（境界）を得ることができる。この設定における、近似（ε, δ）-DPのSCOに対するミニマックス最適レートは既知であるが、純粋なε-DPの場合は未解決のままであった。本研究では、対数因子までを除いて、純粋なε-DP下での裾の重いSCOにおけるミニマックス最適な過剰リスクレートを特徴づける。提案アルゴリズムは、高い確率で多項式時間内にこのレートを達成する。さらに、最悪ケースのリプシッツ定数パラメータが多項式的に有界であるときには、確率1で多項式時間で動作する。重要な構造化問題クラス、すなわちユークリッド球、楕円体、ポリトープ上でのヒンジ／ReLU型および絶対値損失を含む場合において、最悪ケースのリプシッツ定数が無限であっても、確率1で多項式時間内に同じ過剰リスク保証を達成する。我々のアプローチは、経験損失のリプシッツ拡張をプライベートに最適化するための新しい枠組みに基づく。加えて、過剰リスクの上界を、新たな高確率下界によって補完する。