論文の概要: Curse of Dimensionality in Unconstrained Private Convex ERM

• arxiv url: http://arxiv.org/abs/2105.13637v1
• Date: Fri, 28 May 2021 07:28:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-31 13:23:19.645739
• Title: Curse of Dimensionality in Unconstrained Private Convex ERM
• Title（参考訳）: 拘束のないプライベートコンベックスERMの寸法曲線
• Authors: Daogao Liu, Zhou Lu
• Abstract要約: 一般凸関数に対する微分プライベートな経験的リスク最小化の低い境界を考える。 凸一般化線型モデル (GLMs) に対して、制約された場合におけるDP-ERMのよく知られたタイトバウンドは $tildeTheta(fracsqrtpepsilon n)$ であるが、近年では citesstt21 は非制約の場合において DP-ERM のタイトバウンドは $tildeTheta(fracsqrttextrankepsilon n)$ である。
• 参考スコア（独自算出の注目度）: 2.512827436728378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the lower bounds of differentially private empirical risk minimization for general convex functions in this paper. For convex generalized linear models (GLMs), the well-known tight bound of DP-ERM in the constrained case is $\tilde{\Theta}(\frac{\sqrt{p}}{\epsilon n})$, while recently, \cite{sstt21} find the tight bound of DP-ERM in the unconstrained case is $\tilde{\Theta}(\frac{\sqrt{\text{rank}}}{\epsilon n})$ where $p$ is the dimension, $n$ is the sample size and $\text{rank}$ is the rank of the feature matrix of the GLM objective function. As $\text{rank}\leq \min\{n,p\}$, a natural and important question arises that whether we can evade the curse of dimensionality for over-parameterized models where $n\ll p$, for more general convex functions beyond GLM. We answer this question negatively by giving the first and tight lower bound of unconstrained private ERM for the general convex function, matching the current upper bound $\tilde{O}(\frac{\sqrt{p}}{n\epsilon})$ for unconstrained private ERM. We also give an $\Omega(\frac{p}{n\epsilon})$ lower bound for unconstrained pure-DP ERM which recovers the result in the constrained case.
• Abstract（参考訳）: 本稿では,一般凸関数に対する差分プライベートなリスク最小化の下位限について考察する。 凸一般化線型モデル (GLMs) に対して、制約された場合における DP-ERM のよく知られたタイトバウンドは $\tilde{\Theta}(\frac{\sqrt{p}}{\epsilon n})$ であるが、近年では \cite{sstt21} が非制約の場合における DP-ERM のタイトバウンドは $\tilde{\Theta}(\frac{\sqrt{\text{rank}}}{\epsilon n})$ である。 {rank}\leq \min\{n,p\}$ として、自然で重要な疑問は、n\ll p$ の超パラメータモデルに対する次元の呪いを避けることができるか、あるいは glm を超えたより一般的な凸関数を回避できるかである。 一般凸関数に対する非拘束プライベート ERM の第一下界と強下界を与え、非拘束プライベート ERM に対して現在の上界 $\tilde{O}(\frac{\sqrt{p}}{n\epsilon})$ に一致する。 また、制約付きケースで結果を回復するunconstrained pure-dp ermに対して$\omega(\frac{p}{n\epsilon})$ lowerboundを与えます。

関連論文リスト

• 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)
• Keep it Tighter -- A Story on Analytical Mean Embeddings [0.6445605125467574]
  カーネル技術は、データサイエンスにおいて最も人気があり柔軟なアプローチの一つである。 平均埋め込みは、最大平均不一致(MMD)と呼ばれる分岐測度をもたらす。 本稿では,基礎となる分布の1つの平均埋め込みが解析的に利用可能である場合のMDD推定の問題に焦点をあてる。
  論文  参考訳（メタデータ） (2021-10-15T21:29:27Z)
• 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)

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

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