論文の概要: Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter
- arxiv url: http://arxiv.org/abs/2209.07403v6
- Date: Sat, 28 Sep 2024 01:14:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-01 22:01:46.782418
- Title: Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter
- Title（参考訳）: 最大値リプシッツパラメータを用いた個人確率最適化
- Authors: Andrew Lowy, Meisam Razaviyayn,
- Abstract要約: 我々は、全てのデータに対して最悪のリプシッツパラメータを持つ損失関数を持つ差分プライベート(DP)不等式最適化(SO)について検討する。
スムーズな損失関数に対して、我々は最先端の過剰リスクを持つ線形時間アルゴリズムを提供する。
また,非最適凸損失関数を扱う最初のアルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 14.040676498310198
- License:
- Abstract: We study differentially private (DP) stochastic optimization (SO) with loss functions whose worst-case Lipschitz parameter over all data may be extremely large or infinite. To date, the vast majority of work on DP SO assumes that the loss is uniformly Lipschitz continuous (i.e. stochastic gradients are uniformly bounded) over data. While this assumption is convenient, it often leads to pessimistic risk bounds. In many practical problems, the worst-case (uniform) Lipschitz parameter of the loss over all data may be huge due to outliers and/or heavy-tailed data. In such cases, the risk bounds for DP SO, which scale with the worst-case Lipschitz parameter, are vacuous. To address these limitations, we provide improved risk bounds that do not depend on the uniform Lipschitz parameter. Following a recent line of work [WXDX20, KLZ22], we assume that stochastic gradients have bounded $k$-th order moments for some $k \geq 2$. Compared with works on uniformly Lipschitz DP SO, our risk bounds scale with the $k$-th moment instead of the uniform Lipschitz parameter of the loss, allowing for significantly faster rates in the presence of outliers and/or heavy-tailed data. For smooth convex loss functions, we provide linear-time algorithms with state-of-the-art excess risk. We complement our excess risk upper bounds with novel lower bounds. In certain parameter regimes, our linear-time excess risk bounds are minimax optimal. Second, we provide the first algorithm to handle non-smooth convex loss functions. To do so, we develop novel algorithmic and stability-based proof techniques, which we believe will be useful for future work in obtaining optimal excess risk. Finally, our work is the first to address non-convex non-uniformly Lipschitz loss functions satisfying the Proximal-PL inequality; this covers some practical machine learning models. Our Proximal-PL algorithm has near-optimal excess risk.
- Abstract（参考訳）: 我々は,全てのデータに対する最悪のリプシッツパラメータが極端に大きいか無限であるような損失関数を持つ差分プライベート(DP)確率最適化(SO)について検討する。
現在、DP SOに関するほとんどの研究は、損失はデータ上一様リプシッツ連続(すなわち確率勾配は一様有界)であると仮定している。
この仮定は便利であるが、悲観的なリスク境界につながることが多い。
多くの実践的な問題において、すべてのデータに対する損失の最悪の(一様)リプシッツパラメータは、外れ値や重み付きデータのために巨大である可能性がある。
このような場合、最悪のリプシッツパラメータでスケールするDP SOのリスク境界は空である。
これらの制限に対処するため、一様リプシッツパラメータに依存しない改善されたリスク境界を提供する。
最近の研究の行 [WXDX20, KLZ22] に続いて、確率勾配は、ある$k \geq 2$に対して$k$-次モーメントを有界にしていると仮定する。
リプシッツDP SOの均一な研究と比較すると、リスクバウンダリは損失の均一なリプシッツパラメータの代わりに$k$-thのモーメントとスケールし、アウトリーチや重み付きデータの存在下では大幅に高速になる。
滑らかな凸損失関数に対して、我々は最先端の余剰リスクを持つ線形時間アルゴリズムを提供する。
我々は余剰リスクの上限を、新しい下限で補完する。
パラメータの条件によっては、線形時間過剰なリスク境界は極小値である。
第二に、非滑らかな凸損失関数を扱う最初のアルゴリズムを提供する。
そこで我々は, アルゴリズムと安定性に基づく新しい証明手法を開発し, 最適余剰リスクを得るための今後の研究に役立つと考えている。
最後に,PPL不等式を満たす非凸非一様リプシッツ損失関数に対処する最初の研究である。
我々の Proximal-PL アルゴリズムは、ほぼ最適超過リスクを持つ。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted
Activations [52.031701581294804]
ニューラルネットワークのリプシッツ境界は、高い時間保存保証で計算できる。
このギャップを埋めて,リプシッツを傾斜制限活性化関数を超えて拡張する。
提案した解析は一般であり、$ell$ および $ell_infty$ Lipschitz 境界を推定するための統一的なアプローチを提供する。
論文 参考訳（メタデータ） (2024-01-25T09:23:31Z) - Certified Robust Models with Slack Control and Large Lipschitz Constants [102.69689641398227]
本稿では,2つの問題に対処するCalibrated Lipschitz-Margin Loss (CLL)を提案する。
第一に、一般的に使用されるマージン損失は、縮小する出力分布に対する罰則を調整しない。
第二に、$K$の最小化は過度に滑らかな決定関数をもたらす。
我々のCLLは、損失w.r.t.マージンとリプシッツ定数を明示的に調整することでこれらの問題に対処する。
論文 参考訳（メタデータ） (2023-09-12T12:23:49Z) - Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for
Full-Batch GD [31.80268332522017]
我々は、スムーズな損失(おそらく非Lipschitz)に対するフルバッチグラディエントデセント(GD)に対して、鋭い経路依存および過大なエラー保証を提供する。
我々の全バッチ一般化誤差と過剰リスク境界は、損失が滑らかである(しかし、おそらく非リプシッツ)GDの既存の境界よりもかなり厳密である。
論文 参考訳（メタデータ） (2022-04-26T17:05:57Z) - Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural
Networks [77.82638674792292]
ニューラルネットワークのリプシッツ定数は、画像分類の堅牢性、コントローラ設計の安全性、トレーニングデータを超えた一般化性を保証する。
リプシッツ定数の計算はNPハードであるため、リプシッツ定数を推定する手法はスケーラビリティと精度のトレードオフをナビゲートする必要がある。
本研究では,LipSDPと呼ばれる半定値プログラミング手法のスケーラビリティフロンティアを大幅に推し進め,精度の損失をゼロにする。
論文 参考訳（メタデータ） (2022-04-02T11:57:52Z) - Private Non-Convex Federated Learning Without a Trusted Server [7.971065005161566]
非信頼の損失関数を持つクロスサイロ学習(FL)のための新しいアルゴリズムと、他のサイロを信頼していない人のデータを提案する。
我々のアルゴリズムは、凸性やi.d.データを仮定することなく、ISRL-DP FLの最適凸、等質(すなわち等質)を達成する。
数値実験により,我々のアルゴリズムは,ほとんどのプライバシレベルのベースラインよりも精度が高いことがわかった。
論文 参考訳（メタデータ） (2022-03-13T19:17:15Z) - Improved Rates for Differentially Private Stochastic Convex Optimization
with Heavy-Tailed Data [13.465471169118974]
差分プライバシーの制約の下で,重み付きデータを用いた凸最適化について検討した。
我々は、純粋な差分プライバシーの制約の下で、ほぼ一致する低い境界を証明し、我々の境界が厳密であることを示す強力な証拠を与える。
論文 参考訳（メタデータ） (2021-06-02T17:45:47Z) - Stability and Deviation Optimal Risk Bounds with Convergence Rate
$O(1/n)$ [4.1499725848998965]
経験的リスク最小化法で有効な強く凸およびLipschitz損失に対する$O(log n/n)$の確率に拘束される高い確率過剰リスクを示す。
O(log n/n)$ 高確率過剰リスク境界が、通常の滑らかさの仮定なしで強い凸やリプシッツ損失の場合の射影勾配降下に対してどのように可能かについて論じる。
論文 参考訳（メタデータ） (2021-03-22T17:28:40Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳（メタデータ） (2020-06-12T02:45:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。