論文の概要: Private Component-by-Component Learning

• arxiv url: http://arxiv.org/abs/2610.05102v1
• Date: Sun, 04 Oct 2026 10:15:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 23:25:33.165935
• Title: Private Component-by-Component Learning
• Title（参考訳）: プライベートコンポーネント・バイ・コンポーネント・ラーニング
• Abstract要約: 仮説を$k$のコンポーネントで特定する、実現可能な環境での差分私的学習問題について検討する。 プライベートコンポーネントの学習者の直接イテレーションは、単純な困難によって妨害される。 本研究では,Beimel,Nissim,StemmerのLabelBoostプロシージャを用いて,実現可能性の回復を図る。
• 参考スコア（独自算出の注目度）: 7.3837987603967425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study differentially private learning problems in the realizable setting, where a hypothesis is specified by $k$ components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy $\varepsilon$, pays only $\widetilde O(\sqrt{k}/\varepsilon)$ overhead relative to the active sample requirement of a single component learning step at target accuracy $Θ(α/k)$. For learning $d$-dimensional halfspaces over a finite coordinate grid of size $L$, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of $\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right),$ which improves on the previously known bound of $\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot\min\{\frac{1}α\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right).$ We also apply the framework to Boolean compositions: given proper private learners for classes $H_1,\ldots,H_k$, we obtain a proper private learner for $G(H_1,\ldots,H_k)$ for any fixed Boolean function $G:\{0,1\}^k\to\{0,1\}$. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from $\widetilde O(k/\varepsilon)$ to $\widetilde O(\sqrt{k}/\varepsilon)$.
• Abstract（参考訳）: 仮説を$k$のコンポーネントで特定する、実現可能な環境での差分私的学習問題について検討する。 次のコンポーネントの近似的な選択は、次のコンポーネントが局所的に正確である場合でも、ラベル付きサンプルの正確な実現性を損なう可能性がある。 我々は,Beimel,Nissim,StemmerのLabelBoost法[SODA '15, Algorithmica '21]を用いて実現可能性の回復と,2つの交互貯水池によるデータのリサイクルを行う。 その結果得られた学習者は、ターゲットのプライバシ$\varepsilonに対して、ターゲットの精度で1つのコンポーネント学習ステップのアクティブなサンプル要求に対して$\widetilde O(\sqrt{k}/\varepsilon)$オーバーヘッドを支払う。 d$ 次元の半空間を L$ の有限座標格子上で学習する際、正確な実現性は直接成分深度を準凸とする。 フレームワークをNissim, Tsfadia, Yan [SODA '26] の IPConcave アルゴリズムと Cohen, Lyu, Nelson, Sarl'os, Stemmer [STOC '23] の準コンカブ最適化器で強化すると、$\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \: d^{2.5} + d^{1.5} 2^{\log^*L}\right) の既知境界の$\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L}\right) が実現可能なサンプル複雑性が得られる。 H_1,\ldots,H_k$ の適切なプライベートラーナが与えられると、固定されたBoolean関数 $G:\{0,1\}^k\to\{0,1\}$ に対して、$G(H_1,\ldots,H_k)$ の適切なプライベートラーナが得られます。 Alon, Beimel, Moran, Stemmer [COLT '20] の閉包定理と比較すると、これは共通成分サンプルのオーバーヘッドを$\widetilde O(k/\varepsilon)$から$\widetilde O(\sqrt{k}/\varepsilon)$に縮める。

関連論文リスト

• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• 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)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• 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)

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

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