論文の概要: \~Optimal Differentially Private Learning of Thresholds and
Quasi-Concave Optimization
- arxiv url: http://arxiv.org/abs/2211.06387v1
- Date: Fri, 11 Nov 2022 18:16:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 17:20:26.877426
- Title: \~Optimal Differentially Private Learning of Thresholds and
Quasi-Concave Optimization
- Title（参考訳）: 閾値の最適微分プライベート学習と準凸最適化
- Authors: Edith Cohen, Xin Lyu, Jelani Nelson, Tam\'as Sarl\'os, Uri Stemmer
- Abstract要約: しきい値関数の学習問題は、機械学習の基本的な問題である。
Kaplan et al による $tildeO(log* |X|)1.5) のほぼタイトな上界を提供する。
また、プライベート準凹の加法誤差(関連するより一般的な問題)に対して$tildeTheta(2log*|X|)$の上限と下限のマッチングも提供する。
- 参考スコア（独自算出の注目度）: 23.547605262139957
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of learning threshold functions is a fundamental one in machine
learning. Classical learning theory implies sample complexity of $O(\xi^{-1}
\log(1/\beta))$ (for generalization error $\xi$ with confidence $1-\beta$). The
private version of the problem, however, is more challenging and in particular,
the sample complexity must depend on the size $|X|$ of the domain. Progress on
quantifying this dependence, via lower and upper bounds, was made in a line of
works over the past decade. In this paper, we finally close the gap for
approximate-DP and provide a nearly tight upper bound of $\tilde{O}(\log^*
|X|)$, which matches a lower bound by Alon et al (that applies even with
improper learning) and improves over a prior upper bound of $\tilde{O}((\log^*
|X|)^{1.5})$ by Kaplan et al. We also provide matching upper and lower bounds
of $\tilde{\Theta}(2^{\log^*|X|})$ for the additive error of private
quasi-concave optimization (a related and more general problem). Our
improvement is achieved via the novel Reorder-Slice-Compute paradigm for
private data analysis which we believe will have further applications.
- Abstract（参考訳）: しきい値関数の学習問題は、機械学習の基本的な問題である。
古典的学習理論は、$O(\xi^{-1} \log(1/\beta))$(信頼度1-\beta$)のサンプル複雑性を意味する。
しかし、この問題のプライベートバージョンはより困難であり、特に、サンプルの複雑さは、ドメインのサイズ$|X|$に依存する必要がある。
この依存の定量化の進歩は、下限と上限を通じて、過去10年間に一連の研究でなされた。
本稿では、最終的に近似DPのギャップを閉じ、Alon et al による下限(不適切な学習にも適用)と一致する$\tilde{O}(\log^* |X|)^{1.5} のほぼ緊密な上限をKaplan et al の$\tilde{O}((\log^* |X|)^{1.5} の以前の上限よりも改善する$\tilde{O}(\log^* |X|)$を提供する。
また、プライベート準凹最適化(関連するより一般的な問題)の加法誤差に対して、$\tilde{\Theta}(2^{\log^*|X|})$の上限と下限のマッチングも提供する。
我々の改善は、プライベートデータ分析のための新しいReorder-Slice-Computeパラダイムによって達成されます。
関連論文リスト
- Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。
サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-24T04:06:11Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。