論文の概要: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity

• arxiv url: http://arxiv.org/abs/2004.07839v2
• Date: Tue, 3 Nov 2020 09:44:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 21:20:43.162015
• Title: Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• Title（参考訳）: 半空間のプライベートラーニング:構成の簡素化とサンプル複雑性の低減
• Authors: Haim Kaplan, Yishay Mansour, Uri Stemmer, Eliad Tsfadia
• Abstract要約: 有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
• 参考スコア（独自算出の注目度）: 63.29100726064574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a differentially private learner for halfspaces over a finite grid $G$ in $\mathbb{R}^d$ with sample complexity $\approx d^{2.5}\cdot 2^{\log^*|G|}$, which improves the state-of-the-art result of [Beimel et al., COLT 2019] by a $d^2$ factor. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem: Given a feasible collection of $m$ linear constraints of the form $Ax\geq b$, the task is to privately identify a solution $x$ that satisfies most of the constraints. Our algorithm is iterative, where each iteration determines the next coordinate of the constructed solution $x$.
• Abstract（参考訳）: 有限格子上の半空間に対して微分プライベートな学習器を,サンプル複雑性が$\approx d^{2.5}\cdot 2^{\log^*|G|}$で$G$ in $\mathbb{R}^d$で示し, [Beimel et al., COLT 2019] の最先端の結果を$d^2$ factorで改善する。 私たちの学習者のためのビルディングブロックは、線形実現可能性問題を概ね解くための新しい微分プライベートアルゴリズムである:$Ax\geq b$という形の線形制約の可能なコレクションを与えられた場合、そのタスクは、ほとんどの制約を満たすソリューションをプライベートに識別することである。 我々のアルゴリズムは反復的であり、各反復は構築された解の次の座標を$x$で決定する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
  非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。 そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-12-09T05:32:30Z)
• Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems [0.49495085874952904]
  特に、この仮定の下では、必ずしもハーフスペースではなく、任意のバイナリ仮説を出力する効率的なアルゴリズムは存在しないことを示す。 これは、最悪の格子問題に基づいて、よく分離されたガウス混合を学習する難しさを示す最近の一連の研究から着想を得たものである。
  論文  参考訳（メタデータ） (2022-07-28T11:44:39Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
  有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。 サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-24T04:06:11Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。 我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。 また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
  論文  参考訳（メタデータ） (2020-06-08T17:59:11Z)
• 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)

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

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