Fugu-MT 論文翻訳(概要): Private Learning of Littlestone Classes, Revisited

論文の概要: Private Learning of Littlestone Classes, Revisited

arxiv url: http://arxiv.org/abs/2510.00076v1
Date: Tue, 30 Sep 2025 01:22:40 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-03 16:59:20.16515
Title: Private Learning of Littlestone Classes, Revisited
Title（参考訳）: リトルストーンクラスの私的学習について再考
Authors: Xin Lyu,
Abstract要約: 偏微分プライバシーの制約を考慮したLittlestoneクラスのオンライン学習とPAC学習について考察する。我々の主な成果は、オンラインで学習するLittlestoneクラスに対して、$tildeO(d9.5cdot log(T))$の誤りを許容可能なケースで与える、プライベートな学習者です。これは最先端[GL'21]に対する2倍の指数的改善であり、このタスクの下位境界に近づきます。
参考スコア（独自算出の注目度）: 2.1043427184533035
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider online and PAC learning of Littlestone classes subject to the constraint of approximate differential privacy. Our main result is a private learner to online-learn a Littlestone class with a mistake bound of $\tilde{O}(d^{9.5}\cdot \log(T))$ in the realizable case, where $d$ denotes the Littlestone dimension and $T$ the time horizon. This is a doubly-exponential improvement over the state-of-the-art [GL'21] and comes polynomially close to the lower bound for this task. The advancement is made possible by a couple of ingredients. The first is a clean and refined interpretation of the ``irreducibility'' technique from the state-of-the-art private PAC-learner for Littlestone classes [GGKM'21]. Our new perspective also allows us to improve the PAC-learner of [GGKM'21] and give a sample complexity upper bound of $\widetilde{O}(\frac{d^5 \log(1/\delta\beta)}{\varepsilon \alpha})$ where $\alpha$ and $\beta$ denote the accuracy and confidence of the PAC learner, respectively. This improves over [GGKM'21] by factors of $\frac{d}{\alpha}$ and attains an optimal dependence on $\alpha$. Our algorithm uses a private sparse selection algorithm to \emph{sample} from a pool of strongly input-dependent candidates. However, unlike most previous uses of sparse selection algorithms, where one only cares about the utility of output, our algorithm requires understanding and manipulating the actual distribution from which an output is drawn. In the proof, we use a sparse version of the Exponential Mechanism from [GKM'21] which behaves nicely under our framework and is amenable to a very easy utility proof.
Abstract（参考訳）: 偏微分プライバシーの制約を考慮したLittlestoneクラスのオンライン学習とPAC学習について考察する。我々の主な成果は、Littlestoneクラスをオンラインで学習し、$\tilde{O}(d^{9.5}\cdot \log(T))$の誤りを許容できる場合、$d$はLittlestone次元を表し、$T$は時間水平線を表す。これは最先端の[GL'21]に対する二重指数改善であり、このタスクの下位境界に多項式的に近づく。この進歩は2つの材料によって実現される。 1つ目は、Littlestone クラスのための最先端のプライベート PAC-learner [GGKM'21] からの `irreducibility'' テクニックのクリーンで洗練された解釈である。我々の新しい視点はまた、[GGKM'21] の PAC-learner を改善し、それぞれ$\widetilde{O}(\frac{d^5 \log(1/\delta\beta)}{\varepsilon \alpha})$, $\alpha$ と $\beta$ は、PAC学習者の正確さと信頼度を表す。これは$\frac{d}{\alpha}$によって[GGKM'21]よりも改善され、$\alpha$への最適な依存が得られる。提案アルゴリズムでは,強い入力依存候補のプールから,プライベートスパース選択アルゴリズムを用いてemph{sample}を抽出する。しかし,従来のスパース選択アルゴリズムでは出力の有効性のみを気にするのに対して,本アルゴリズムでは,出力が描画される実際の分布を理解し操作する必要がある。この証明では、[GKM'21] のスパースバージョンの Exponential Mechanism を使用し、我々のフレームワークの下でうまく動作し、非常に簡単なユーティリティ証明に対処できる。

関連論文リスト

Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文参考訳（メタデータ） (2024-06-18T08:54:04Z)
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)
Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文参考訳（メタデータ） (2022-09-09T08:54:13Z)
Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文参考訳（メタデータ） (2021-06-25T09:08:33Z)
Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文参考訳（メタデータ） (2021-02-16T02:48:16Z)
Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文参考訳（メタデータ） (2020-12-07T18:17:46Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)
Closure Properties for Private Classification and Online Prediction [31.115241685486392]
オンライン学習とプライベートPAC学習のための閉鎖特性を導出する。実現可能な場合において、関数のクラスを学習する任意のプライベートアルゴリズムは、その場合のクラスを学習するプライベートアルゴリズムに変換可能であることを示す。
論文参考訳（メタデータ） (2020-03-10T02:34:16Z)

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

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