論文の概要: The Power of Sampling: Dimension-free Risk Bounds in Private ERM

• arxiv url: http://arxiv.org/abs/2105.13637v4
• Date: Mon, 3 Jun 2024 21:31:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 05:08:03.915241
• Title: The Power of Sampling: Dimension-free Risk Bounds in Private ERM
• Title（参考訳）: サンプリングの力:民間EMMにおける次元自由リスク境界
• Authors: Yin Tat Lee, Daogao Liu, Zhou Lu,
• Abstract要約: 本アルゴリズムは,ゼロ次オラクルのみを用いて,非平滑凸対象に対するランク依存的リスクバウンダリを実現することができることを示す。 これは、差分プライバシーにおけるサンプリングのパワーを強調します。
• 参考スコア（独自算出の注目度）: 25.676350220943274
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private empirical risk minimization (DP-ERM) is a fundamental problem in private optimization. While the theory of DP-ERM is well-studied, as large-scale models become prevalent, traditional DP-ERM methods face new challenges, including (1) the prohibitive dependence on the ambient dimension, (2) the highly non-smooth objective functions, (3) costly first-order gradient oracles. Such challenges demand rethinking existing DP-ERM methodologies. In this work, we show that the regularized exponential mechanism combined with existing samplers can address these challenges altogether: under the standard unconstrained domain and low-rank gradients assumptions, our algorithm can achieve rank-dependent risk bounds for non-smooth convex objectives using only zeroth order oracles, which was not accomplished by prior methods. This highlights the power of sampling in differential privacy. We further construct lower bounds, demonstrating that when gradients are full-rank, there is no separation between the constrained and unconstrained settings. Our lower bound is derived from a general black-box reduction from unconstrained to the constrained domain and an improved lower bound in the constrained setting, which might be of independent interest.
• Abstract（参考訳）: DP-ERM(differially private empirical risk minimization)は、プライベート最適化における基本的な問題である。 DP-ERMの理論はよく研究されているが、大規模モデルが普及するにつれて、従来のDP-ERM法は、(1)周囲次元への禁忌的依存、(2)非滑らかな目的関数、(3)高価な一階勾配オラクルなど、新しい課題に直面している。 このような課題は、既存のDP-ERM方法論を再考することを要求する。 本研究では,既存のサンプルと組み合わせた正規化指数関数機構が,これらの課題を完全に解決できることを示す: 標準の非制約領域と低ランク勾配仮定の下では,従来の手法では達成されなかったゼロ次オーラクルのみを用いて,非滑らかな凸対象に対するランク依存的リスクバウンダリを実現することができる。 これは、差分プライバシーにおけるサンプリングのパワーを強調します。 さらに下限を構築し、勾配がフルランクの場合、制約された設定と制約のない設定の間には分離がないことを示す。 我々の下限は、制約された領域に制限されない一般的なブラックボックス還元と、独立した関心を持つかもしれない制約された設定における改善された下限から導かれる。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Enlarging Feature Support Overlap for Domain Generalization [9.227839292188346]
  不変リスク最小化(IRM)は、不変機能を学び、異なるドメインにわたるリスクを最小限にすることでこの問題に対処する。 本稿では,ドメイン一般化のための機能サポートオーバーラップを拡大する新しい手法を提案する。 具体的には、サンプルの多様性を高め、IRMの欠如を克服するためにベイズランダムデータ拡張を導入する。
  論文  参考訳（メタデータ） (2024-07-08T09:16:42Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。 制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
  論文  参考訳（メタデータ） (2024-02-16T16:35:18Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent(GD)は、現代の機械学習の強力な仕事場である。 GDが局所最小値を見つける能力は、リプシッツ勾配の損失に対してのみ保証される。 この研究は、2段階の勾配更新の分析を通じて、単純だが代表的でありながら、学習上の問題に焦点をあてる。
  論文  参考訳（メタデータ） (2022-06-08T21:32:50Z)
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs [21.347689976296834]
  我々は、割引された最適レート問題を解くために、自然政策勾配法を用いる。 また、2つのサンプルベースNPG-PDアルゴリズムに対して収束と有限サンプル保証を提供する。
  論文  参考訳（メタデータ） (2022-06-06T04:28:04Z)
• Improving Generalization via Uncertainty Driven Perturbations [107.45752065285821]
  トレーニングデータポイントの不確実性による摂動について考察する。 損失駆動摂動とは異なり、不確実性誘導摂動は決定境界を越えてはならない。 線形モデルにおいて,UDPがロバスト性マージン決定を達成することが保証されていることを示す。
  論文  参考訳（メタデータ） (2022-02-11T16:22:08Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization [4.649999862713523]
  我々は、整数格子上の領域である連続利益(CPM-MS)問題を形成する。 格子に基づく二重グリードアルゴリズムを導入し, 定数近似を求める。 本稿では,格子型反復プルーニング手法を提案し,探索空間を効果的に縮小することができる。
  論文  参考訳（メタデータ） (2020-04-12T05:35:19Z)

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

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