論文の概要: Private Stochastic Optimization in the Presence of Outliers: Optimal
Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses
- arxiv url: http://arxiv.org/abs/2209.07403v1
- Date: Thu, 15 Sep 2022 16:03:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-16 12:28:35.660057
- Title: Private Stochastic Optimization in the Presence of Outliers: Optimal
Rates for (Non-Smooth) Convex Losses and Extension to Non-Convex Losses
- Title（参考訳）: 外乱の存在下でのプライベート確率最適化:(非滑らかな)凸損失に対する最適速度と非凸損失への拡張
- Authors: Andrew Lowy, Meisam Razaviyayn
- Abstract要約: 非Lipschitz損失関数を含むデータを用いたDPキュレータ最適化(SO)について検討した。
強凸損失関数に対して、第一に最適な余剰リスク境界(対数係数まで)を提供する。
以前の作品 [WXDX20, KLZ22] とは対照的に、我々の境界は損失関数を微分可能/滑らかにする必要がない。
我々の Proximal-PL アルゴリズムは、強い凸下界とほぼ一致する最適余剰リスクを持つ。
- 参考スコア（独自算出の注目度）: 9.416757363901295
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study differentially private (DP) stochastic optimization (SO) with data
containing outliers and loss functions that are not Lipschitz continuous. To
date, the vast majority of work on DP SO assumes that the loss is Lipschitz
(i.e. stochastic gradients are uniformly bounded), and their error bounds scale
with the Lipschitz parameter of the loss. While this assumption is convenient,
it is often unrealistic: in many practical problems where privacy is required,
data may contain outliers or be unbounded, causing some stochastic gradients to
have large norm. In such cases, the Lipschitz parameter may be prohibitively
large, leading to vacuous excess risk bounds. Thus, building on a recent line
of work [WXDX20, KLZ22], we make the weaker assumption that stochastic
gradients have bounded $k$-th moments for some $k \geq 2$. Compared with works
on DP Lipschitz SO, our excess risk scales with the $k$-th moment bound instead
of the Lipschitz parameter of the loss, allowing for significantly faster rates
in the presence of outliers. For convex and strongly convex loss functions, we
provide the first asymptotically optimal excess risk bounds (up to a
logarithmic factor). Moreover, in contrast to the prior works [WXDX20, KLZ22],
our bounds do not require the loss function to be differentiable/smooth. We
also devise an accelerated algorithm that runs in linear time and yields
improved (compared to prior works) and nearly optimal excess risk for smooth
losses. Additionally, our work is the first to address non-convex non-Lipschitz
loss functions satisfying the Proximal-PL inequality; this covers some classes
of neural nets, among other practical models. Our Proximal-PL algorithm has
nearly optimal excess risk that almost matches the strongly convex lower bound.
Lastly, we provide shuffle DP variations of our algorithms, which do not
require a trusted curator (e.g. for distributed learning).
- Abstract（参考訳）: リプシッツ連続ではない外れ値と損失関数を含むデータを用いて微分プライベート (dp) 確率最適化 (so) について検討した。
これまで、dp の研究の大部分は、損失がリプシッツである(すなわち確率勾配は一様有界である)と仮定しており、その誤差境界は、損失のリプシッツパラメータとともにスケールする。
この仮定は便利だが、しばしば非現実的である:プライバシーが要求される多くの実践的な問題において、データは外れ値を含むか、非有界である可能性がある。
そのような場合、リプシッツパラメータは制限的に大きいため、過剰なリスク境界が生じる。
したがって、最近の作業(wxdx20, klz22]に基づいて、確率的勾配が約$k \geq 2$に対してk$-th モーメントを持つという弱い仮定をする。
DP Lipschitz SOの研究と比較すると、我々の余剰リスクは損失のリプシッツパラメータの代わりに$k$-thのモーメントバウンドでスケールし、オフラヤの存在下では大幅に高速になる。
凸および強い凸損失関数に対しては、最初の漸近的に最適な超過リスク境界(対数係数まで)を提供する。
さらに、以前の作品 [WXDX20, KLZ22] とは対照的に、我々の境界は損失関数を微分可能/滑らかにする必要がない。
また,線形時間内で動作する高速化アルゴリズムを考案し,スムースな損失に対して(以前の作業と比較して)改善し,ほぼ最適に過大なリスクを与える。
さらに,本研究は近近偏pl不等式を満たす非凸非リプシッツ損失関数に対する最初の対処である。
我々の Proximal-PL アルゴリズムは、強い凸下界とほぼ一致する最適余剰リスクを持つ。
最後に、信頼できるキュレーター(例えば分散学習)を必要としないアルゴリズムのシャッフルDPのバリエーションを提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。