論文の概要: Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition

• arxiv url: http://arxiv.org/abs/2509.04668v1
• Date: Thu, 04 Sep 2025 21:30:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-08 14:27:25.414501
• Title: Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition
• Title（参考訳）: 通常のリプシッツ制約を超えて:チバコフ雑音条件による個人確率最適化
• Authors: Difei Xu, Meng Ding, Zihang Xiang, Jinhui Xu, Di Wang,
• Abstract要約: 微分プライバシーモデル(DP-SCO)における凸最適化の検討 任意の$thetageq 2$に対して、$rho$-zero集中微分プライバシーのプライベートミニマックスレートが$Omegaleftで制限されることを示す。
• 参考スコア（独自算出の注目度）: 12.926841066732223
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study Stochastic Convex Optimization in the Differential Privacy model (DP-SCO). Unlike previous studies, here we assume the population risk function satisfies the Tsybakov Noise Condition (TNC) with some parameter $\theta>1$, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the $\ell_2$-norm gradient of the loss has bounded $k$-th moment with $k\geq 2$. For the Lipschitz case with $\theta\geq 2$, we first propose an $(\varepsilon, \delta)$-DP algorithm whose utility bound is $\Tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ in high probability, where $n$ is the sample size, $d$ is the model dimension, and $\tilde{r}_{2k}$ is a term that only depends on the $2k$-th moment of the gradient. It is notable that such an upper bound is independent of the Lipschitz constant. We then extend to the case where $\theta\geq \bar{\theta}> 1$ for some known constant $\bar{\theta}$. Moreover, when the privacy budget $\varepsilon$ is small enough, we show an upper bound of $\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ even if the loss function is not Lipschitz. For the lower bound, we show that for any $\theta\geq 2$, the private minimax rate for $\rho$-zero Concentrated Differential Privacy is lower bounded by $\Omega\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{\rho}}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$.
• Abstract（参考訳）: 微分プライバシーモデル(DP-SCO)における確率凸最適化について検討する。 従来の研究とは異なり、人口リスク関数は、損失のリプシッツ定数が極端に大きいか、あるいは非有界であるようなパラメータ$\theta>1$でツィバコフ騒音条件(TNC)を満たすと仮定するが、損失の$\ell_2$-norm勾配は、$k\geq 2$で$k$-th momentに制限されている。 $\theta\geq 2$ のリプシッツの場合、最初に $(\varepsilon, \delta)$-DP アルゴリズムを提案し、そのユーティリティ境界は $\Tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac {\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac {\theta}{\theta-1}\right)$ である。 そのような上限がリプシッツ定数とは独立であることは注目すべきである。 すると、ある既知の定数 $\bar{\theta}$ に対して $\theta\geq \bar{\theta}> 1$ の場合に拡張する。 さらに、プライバシー予算$\varepsilon$が十分小さい場合、損失関数がリプシッツでない場合でも、$\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\varepsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$の上限を示す。 下限については、$\theta\geq 2$の場合、$\rho$-zero 集中微分プライバシーのプライベートミニマックスレートは$\Omega\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{\rho}}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$で下限される。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning [6.416429054645991]
  近似の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。 本稿では, ステップサイズ$alpha>0$のSAを再帰で定義し, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$$, $theta_ninmathbbRd$と$Phi_n$をマルコフ連鎖とする。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Differentially Private Generalized Linear Models Revisited [30.298342283075176]
  本研究では,凸損失のある線形予測器の差分学習における$(epsilon,delta)$-differentially private Learningの問題について検討する。 特に, $tildeOleft(fracVert w*Vertsqrtn + minleftfracVert w*Vert4/3(nepsilon)2/3, fracsqrtdVert w*Vertnepsilon の過剰集団リスクの低い境界を示す。
  論文  参考訳（メタデータ） (2022-05-06T05:01:02Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed Data [22.233705161499273]
  我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。 我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。 我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
  論文  参考訳（メタデータ） (2022-01-10T08:17:05Z)
• Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
  人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。 第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
  論文  参考訳（メタデータ） (2021-07-31T22:23:39Z)
• 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)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

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