論文の概要: On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
- arxiv url: http://arxiv.org/abs/2107.11526v1
- Date: Sat, 24 Jul 2021 04:06:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-27 15:46:50.994927
- Title: On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
- Title（参考訳）: 個人学習軸配置長方形のサンプル複雑性について
- Authors: Menachem Sadigurschi, Uri Stemmer
- Abstract要約: 有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。
サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 16.092248433189816
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a
finite grid $X^d\subseteq{\mathbb{R}}^d$ with differential privacy. Existing
results show that the sample complexity of this problem is at most $\min\left\{
d{\cdot}\log|X| \;,\; d^{1.5}{\cdot}\left(\log^*|X| \right)^{1.5}\right\}$.
That is, existing constructions either require sample complexity that grows
linearly with $\log|X|$, or else it grows super linearly with the dimension
$d$. We present a novel algorithm that reduces the sample complexity to only
$\tilde{O}\left\{d{\cdot}\left(\log^*|X|\right)^{1.5}\right\}$, attaining a
dimensionality optimal dependency without requiring the sample complexity to
grow with $\log|X|$.The technique used in order to attain this improvement
involves the deletion of "exposed" data-points on the go, in a fashion designed
to avoid the cost of the adaptive composition theorems. The core of this
technique may be of individual interest, introducing a new method for
constructing statistically-efficient private algorithms.
- Abstract（参考訳）: 差分プライバシーを持つ有限格子$X^d\subseteq{\mathbb{R}}^d$上で軸整列学習の基本的な問題を再考する。
既存の結果は、この問題のサンプル複雑性は少なくとも$\min\left\{ d{\cdot}\log|x| \;,\; d^{1.5}{\cdot}\left(\log^*|x| \right)^{1.5}\right\}$であることを示している。
つまり、既存の構成は、$\log|X|$で線型に成長するサンプル複雑性を必要とするか、または$d$で超線型に成長する。
我々は、サンプルの複雑さを$\tilde{O}\left\{d{\cdot}\left(\log^*|X|\right)^{1.5}\right\}$に減らし、サンプルの複雑さを$\log|X|$で成長させることなく、次元最適依存を実現する新しいアルゴリズムを提案する。
この手法のコアは個人が興味を持ち、統計的に効率的なプライベートアルゴリズムを構築するための新しい手法を導入する。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳（メタデータ） (2023-03-03T18:03:49Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - 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) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。