論文の概要: Adaptive Batch Size for Privately Finding Second-Order Stationary Points

• arxiv url: http://arxiv.org/abs/2410.07502v1
• Date: Thu, 10 Oct 2024 00:34:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 16:46:37.154281
• Title: Adaptive Batch Size for Privately Finding Second-Order Stationary Points
• Title（参考訳）: 2次定常点をプライベートに見つけるための適応バッチサイズ
• Authors: Daogao Liu, Kunal Talwar,
• Abstract要約: 一階定常点(FOSP)と二階定常点(SOSP)の差がある。 適応的なバッチサイズを使用し,バイナリツリー機構を組み込んだ新しいアプローチを提案する。 この改良された境界はFOSPを見つけるための最先端技術と一致し、SOSPをプライベートに見つけることは追加コストなしで達成可能であることを示唆している。
• 参考スコア（独自算出の注目度）: 28.574858341430858
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is a gap between finding a first-order stationary point (FOSP) and a second-order stationary point (SOSP) under differential privacy constraints, and it remains unclear whether privately finding an SOSP is more challenging than finding an FOSP. Specifically, Ganesh et al. (2023) demonstrated that an $\alpha$-SOSP can be found with $\alpha=O(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{3/7})$, where $n$ is the dataset size, $d$ is the dimension, and $\epsilon$ is the differential privacy parameter. Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism. Our method improves the results for privately finding an SOSP, achieving $\alpha=O(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{1/2})$. This improved bound matches the state-of-the-art for finding an FOSP, suggesting that privately finding an SOSP may be achievable at no additional cost.
• Abstract（参考訳）: 一階定常点(FOSP)と二階定常点(SOSP)との差があり、私的にSOSPを見つけることがFOSPを見つけることよりも難しいかどうかは不明である。 具体的には、Ganesh et al (2023)は$\alpha$-SOSPを$\alpha=O(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{3/7})$で見つけることができることを示した。 SpiderBoostアルゴリズムフレームワークをベースとして,適応的なバッチサイズを使用し,バイナリツリー機構を組み込んだ新しいアプローチを提案する。 我々の手法は、SOSPをプライベートに見つける結果を改善し、$\alpha=O(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{1/2})$を得る。 この改良された境界はFOSPを見つけるための最先端技術と一致し、SOSPをプライベートに見つけることは追加コストなしで達成可能であることを示唆している。

関連論文リスト

• Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry [20.068722738606287]
  我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。 強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。 我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
  論文  参考訳（メタデータ） (2024-11-07T21:45:05Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
  多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。 我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
  論文  参考訳（メタデータ） (2024-03-05T12:28:00Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。 準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
  論文  参考訳（メタデータ） (2022-05-27T02:02:17Z)
• Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
  線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。 本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
  論文  参考訳（メタデータ） (2021-10-25T08:34:00Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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