論文の概要: Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter: Optimal Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses

• arxiv url: http://arxiv.org/abs/2209.07403v5
• Date: Sat, 28 Oct 2023 01:40:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-01 01:27:15.539656
• Title: Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter: Optimal Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses
• Title（参考訳）: 最大最悪ケースリプシッツパラメータを用いたプライベート確率最適化:(非スムース)凸損失の最適速度と非凸損失への拡張
• Authors: Andrew Lowy, Meisam Razaviyayn
• Abstract要約: 多くの実践的な問題において、すべてのデータポイントにおける損失の最悪の(一様)リプシッツパラメータは非常に大きいかもしれない。 この研究は、損失の均一なリプシッツパラメータに依存しない準最適超過リスク境界を提供する。
• 参考スコア（独自算出の注目度）: 16.587199291939346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study differentially private (DP) stochastic optimization (SO) with loss functions whose worst-case Lipschitz parameter over all data points may be extremely large. To date, the vast majority of work on DP SO assumes that the loss is uniformly Lipschitz continuous over data (i.e. stochastic gradients are uniformly bounded over all data points). While this assumption is convenient, it often leads to pessimistic excess risk bounds. In many practical problems, the worst-case (uniform) Lipschitz parameter of the loss over all data points may be extremely large due to outliers. In such cases, the error bounds for DP SO, which scale with the worst-case Lipschitz parameter of the loss, are vacuous. To address these limitations, this work provides near-optimal excess risk bounds that do not depend on the uniform Lipschitz parameter of the loss. Building on a recent line of work (Wang et al., 2020; Kamath et al., 2022), 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 excess risk scales with the $k$-th moment bound 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 convex and strongly convex loss functions, we provide the first asymptotically optimal excess risk bounds (up to a logarithmic factor). In contrast to (Wang et al., 2020; Kamath et al., 2022), our bounds do not require the loss function to be differentiable/smooth. We also devise a linear-time algorithm for smooth losses that has excess risk that is tight in certain practical parameter regimes. Additionally, 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の誤差境界は空である。 これらの制限に対処するため、この研究は損失の均一なリプシッツパラメータに依存しない最適超過リスク境界を提供する。 最近の研究(Wang et al., 2020; Kamath et al., 2022)に基づいて構築された確率勾配は、約$k \geq 2$に対して$k$-次モーメントを束縛したと仮定する。 均一なリプシッツdpの作業と比較すると、損失の均一なリプシッツパラメータではなく、k$-th モーメントバウンドで過大なリスクがスケールし、異常値や重み付きデータの存在下での速度が大幅に速くなります。 凸および強い凸損失関数に対しては、最初の漸近的に最適な超過リスク境界(対数係数まで)を提供する。 Wang et al., 2020; Kamath et al., 2022)とは対照的に、我々の境界は損失関数を微分可能/滑らかにする必要がない。 また,特定のパラメーター条件で厳密な過大なリスクを持つスムーズな損失に対する線形時間アルゴリズムを考案する。 さらに、我々の研究は、近近偏pl不等式を満たす非凸非一様リプシッツ損失関数に最初に対処した。 近位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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。