論文の概要: Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails

• arxiv url: http://arxiv.org/abs/2604.06492v1
• Date: Tue, 07 Apr 2026 21:54:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.257778
• Title: Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails
• Title（参考訳）: 重機を用いたPure {\varepsilon} の最適速度-差分私的確率凸最適化
• Abstract要約: 純粋エプシロン微分プライバシー(DP)下での重み付き勾配を用いた凸最適化について検討する。 損失の最悪の場合のリプシッツパラメータの有界を仮定する代わりに、有界 k-次モーメントのみを仮定する。 我々のアプローチは、経験的損失のリプシッツ拡張をプライベートに最適化するための新しい枠組みに基づいている。
• 参考スコア（独自算出の注目度）: 10.43808453274953
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure epsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded k-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. The minimax optimal rate for approximate (epsilon, delta)-DP SCO is known in this setting, but the pure epsilon-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure epsilon-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in polynomial time with probability 1 when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes - including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes - we achieve the same excess-risk guarantee in polynomial time with probability 1 even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our excess risk upper bound with a novel high probability lower bound.
• Abstract（参考訳）: 純粋エプシロン微分プライバシー (DP) の下で, 重み付き勾配を有する確率凸最適化 (SCO) について検討した。 損失の最悪の場合のリプシッツパラメータの有界を仮定する代わりに、有界 k-次モーメントのみを仮定する。 この仮定は、非有界で重い尾の確率勾配分布を許容し、より急激な過剰なリスク境界をもたらす。 この設定では、近似 (epsilon, delta)-DP SCO のミニマックス最適速度が知られているが、純粋な Epsilon-DP ケースは未開のままである。 純エプシロンDP重み付きSCOの極小最大過リスク率を対数因子まで特徴付ける。 我々のアルゴリズムは多項式時間でこの速度を高い確率で達成する。 さらに、最悪のケースリプシッツパラメータが多項式境界のとき、確率 1 で多項式時間で実行される。 ユークリッド球、楕円体、ポリトープに対するヒンジ/ReLU型および絶対値損失を含む重要な構造化問題クラスに対して、最悪のケースリプシッツパラメータが無限である場合でも、確率 1 の多項式時間で同じ過リスク保証を達成する。 我々のアプローチは、経験的損失のリプシッツ拡張をプライベートに最適化するための新しい枠組みに基づいている。 過大なリスク上限と、新しい高い確率上限を補完する。

関連論文リスト

• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。 Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-04T21:26:29Z)
• 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)
• Stochastic Weakly Convex Optimization Beyond Lipschitz Continuity [5.866816093792934]
  次数法を含む幅広い連続性アルゴリズムが, 一定の故障率で$mathO収束率を保っていることを示す。 リプシッツパラメータは、$|x|$の一般的な成長関数によって境界付けられたり、独立したランダムサンプルを通して局所的に推定されたりする。
  論文  参考訳（メタデータ） (2024-01-25T06:06:31Z)
• Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter [14.040676498310198]
  我々は、全てのデータに対して最悪のリプシッツパラメータを持つ損失関数を持つ差分プライベート(DP)不等式最適化(SO)について検討する。 スムーズな損失関数に対して、我々は最先端の過剰リスクを持つ線形時間アルゴリズムを提供する。 また,非最適凸損失関数を扱う最初のアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2022-09-15T16:03:23Z)
• Beyond Uniform Lipschitz Condition in Differentially Private Optimization [28.04430869054056]
  微分プライベート勾配降下(DP-SGD)に関するほとんどの先行結果は、一様リプシッツ性(英語版)という単純な仮定の下で導出される。 我々は、サンプルごとのリプシッツ定数が有界であるとき、一般バージョンのリプシッツネスのノルム依存度を選択する原理的なガイダンスを提供する。
  論文  参考訳（メタデータ） (2022-06-21T20:11:30Z)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data [13.465471169118974]
  差分プライバシーの制約の下で,重み付きデータを用いた凸最適化について検討した。 我々は、純粋な差分プライバシーの制約の下で、ほぼ一致する低い境界を証明し、我々の境界が厳密であることを示す強力な証拠を与える。
  論文  参考訳（メタデータ） (2021-06-02T17:45:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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