論文の概要: On the Equivalence between Online and Private Learnability beyond Binary
Classification
- arxiv url: http://arxiv.org/abs/2006.01980v3
- Date: Sat, 9 Oct 2021 03:24:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 00:12:55.723468
- Title: On the Equivalence between Online and Private Learnability beyond Binary
Classification
- Title(参考訳): 二分分類を超えたオンライン学習能力とプライベート学習能力の等価性について
- Authors: Young Hun Jung, Baekjin Kim, Ambuj Tewari
- Abstract要約: プライベートな学習性は、両方の設定においてオンライン学習性を意味することを示す。
オンライン学習が多クラス分類において個人的学習可能性を示す一方で、現在の証明手法は回帰設定において重大なハードルに直面していることを示す。
- 参考スコア(独自算出の注目度): 26.400891660337777
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Alon et al. [2019] and Bun et al. [2020] recently showed that online
learnability and private PAC learnability are equivalent in binary
classification. We investigate whether this equivalence extends to multi-class
classification and regression. First, we show that private learnability implies
online learnability in both settings. Our extension involves studying a novel
variant of the Littlestone dimension that depends on a tolerance parameter and
on an appropriate generalization of the concept of threshold functions beyond
binary classification. Second, we show that while online learnability continues
to imply private learnability in multi-class classification, current proof
techniques encounter significant hurdles in the regression setting. While the
equivalence for regression remains open, we provide non-trivial sufficient
conditions for an online learnable class to also be privately learnable.
- Abstract(参考訳): アロンなど。
[2019]とBun et al。
[2020] は近年,オンライン学習性とプライベートPAC学習性がバイナリ分類において等価であることを示した。
この同値性は多クラス分類や回帰にまで及んでいるか検討する。
まず,2つの設定でオンライン学習可能性を示す。
我々の拡張は、許容パラメータと二項分類を超えた閾値関数の概念の適切な一般化に依存する新しいリトルストーン次元の変種を研究することを含む。
第2に,オンライン学習性は多クラス分類において個人的学習可能性を示し続けているが,現在の証明手法は回帰設定において重大なハードルに直面している。
回帰の等価性は依然としてオープンだが、オンライン学習可能なクラスがプライベートに学習できるような、非自明な条件を提供する。
関連論文リスト
- Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。
まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。
オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
論文 参考訳(メタデータ) (2023-07-07T21:39:25Z) - A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
本稿では,任意だが有界な損失関数に対する仮説クラスのオンライン学習可能性について検討する。
連続最小次元と呼ばれる新しいスケール感性次元を与え、オンライン学習可能性の厳密な定量的評価を与えることを示す。
論文 参考訳(メタデータ) (2023-07-07T20:11:07Z) - On Differentially Private Online Predictions [74.01773626153098]
オンラインプロセスを扱うために,共同微分プライバシーのインタラクティブなバリエーションを導入する。
グループプライバシ、コンポジション、ポストプロセッシングの(適切なバリエーション)を満たすことを実証する。
次に、オンライン分類の基本設定において、インタラクティブな共同プライバシーのコストについて検討する。
論文 参考訳(メタデータ) (2023-02-27T19:18:01Z) - Long-tail Recognition via Compositional Knowledge Transfer [60.03764547406601]
末尾クラスの少数ショット問題に対処する長尾認識のための新しい戦略を導入する。
我々の目標は、情報に富んだ共通クラスから得られた知識を、意味的に類似しているがデータに富む稀なクラスに伝達することである。
実験結果から,本手法は稀なクラスにおいて,堅牢な共通クラス性能を維持しつつ,大幅な性能向上を達成できることが示唆された。
論文 参考訳(メタデータ) (2021-12-13T15:48:59Z) - Offline Reinforcement Learning: Fundamental Barriers for Value Function
Approximation [74.3002974673248]
本稿では,ログデータから意思決定方針を学習することを目的としたオフライン強化学習問題を考察する。
オンラインデータ収集は安全クリティカルなドメインに適しているため、オフラインのRLは現実的にますます重要になっている。
以上の結果から, サンプル効率の良いオフライン強化学習には, 制限的カバレッジ条件か, あるいは複雑性学習を超える表現条件が必要であることが示唆された。
論文 参考訳(メタデータ) (2021-11-21T23:22:37Z) - Realizable Learning is All You Need [21.34668631009594]
実現可能かつ不可知的な学習可能性の同値性は、学習理論における基本的な現象である。
実現可能かつ不可知な学習可能性の同値性を説明する最初のモデルに依存しないフレームワークを提示する。
論文 参考訳(メタデータ) (2021-11-08T19:00:00Z) - A Computational Separation between Private Learning and Online Learning [19.001036556917818]
概念クラスは、オンライン学習可能であれば、かつ、オンライン学習可能であれば、プライベートに学習可能である。
この等価性は、サンプルと計算効率の両方に大きな損失をもたらす。
単方向関数の存在を前提として、そのような効率的な変換は、サンプル複雑性を持つ純粋にプライベートな学習者にとって不可能であることを示す。
論文 参考訳(メタデータ) (2020-07-11T02:41:54Z) - Bookworm continual learning: beyond zero-shot learning and continual
learning [52.95405249201296]
本稿では,セマンティックモデルを用いて未確認のクラスを推論し,ビジュアルモデルを継続的に更新するフレキシブルな設定を提案する。
また、過去と将来の両方のクラスの特徴が生成されるBCLに対処するための双方向イマジネーション(BImag)フレームワークを提案する。
論文 参考訳(メタデータ) (2020-06-26T19:07:18Z) - On Learnability under General Stochastic Processes [20.22409095000365]
一般の非イド過程における統計的学習は、未熟である。
一般プロセスの下で関数クラスの学習可能性に関する2つの自然な概念を提供する。
我々の結果は二項分類と回帰の両方に当てはまる。
論文 参考訳(メタデータ) (2020-05-15T15:49:23Z) - An Equivalence Between Private Classification and Online Prediction [43.37646702577754]
有限リトルストーン次元を持つすべての概念クラスは、(近似)微分プライベートアルゴリズムによって学習可能であることを証明している。
我々は「グローバル安定性」と呼ばれる新しい安定性の概念を導入し、これは我々の証明に不可欠であり、独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2020-03-01T19:20:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。