論文の概要: Optimal and Private Learning from Human Response Data

• arxiv url: http://arxiv.org/abs/2303.06234v2
• Date: Sat, 11 Nov 2023 00:16:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 22:16:58.784756
• Title: Optimal and Private Learning from Human Response Data
• Title（参考訳）: 人間反応データからの最適・プライベート学習
• Authors: Duc Nguyen and Anderson Y. Zhang
• Abstract要約: 最近、NguyenとZhangは、効率的かつ正確な新しいスペクトル推定アルゴリズムを提案した。 結果は2つの重要な方法で拡張します。 我々は、独自のマルコフ連鎖の定式化と離散ガウス機構を利用して、スペクトルアルゴリズムのプライベート拡張を開発する。
• 参考スコア（独自算出の注目度）: 13.869502085838452
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Item response theory (IRT) is the study of how people make probabilistic decisions, with diverse applications in education testing, recommendation systems, among others. The Rasch model of binary response data, one of the most fundamental models in IRT, remains an active area of research with important practical significance. Recently, Nguyen and Zhang (2022) proposed a new spectral estimation algorithm that is efficient and accurate. In this work, we extend their results in two important ways. Firstly, we obtain a refined entrywise error bound for the spectral algorithm, complementing the `average error' $\ell_2$ bound in their work. Notably, under mild sampling conditions, the spectral algorithm achieves the minimax optimal error bound (modulo a log factor). Building on the refined analysis, we also show that the spectral algorithm enjoys optimal sample complexity for top-$K$ recovery (e.g., identifying the best $K$ items from approval/disapproval response data), explaining the empirical findings in the previous work. Our second contribution addresses an important but understudied topic in IRT: privacy. Despite the human-centric applications of IRT, there has not been any proposed privacy-preserving mechanism in the literature. We develop a private extension of the spectral algorithm, leveraging its unique Markov chain formulation and the discrete Gaussian mechanism (Canonne et al., 2020). Experiments show that our approach is significantly more accurate than the baselines in the low-to-moderate privacy regime.
• Abstract（参考訳）: 項目応答理論 (IRT) は、人々が確率的意思決定を行う方法の研究であり、教育試験やレコメンデーションシステムなどに様々な応用がある。 IRTにおける最も基本的なモデルの1つであるバイナリ応答データのラッシュモデルは、重要な実践的重要性を持つ研究の活発な領域である。 最近、Nguyen と Zhang (2022) は、効率的かつ正確な新しいスペクトル推定アルゴリズムを提案した。 本研究では2つの重要な方法で結果を拡張する。 まず,スペクトルアルゴリズムにおいて,「平均誤差」$\ell_2$バウンド」を補足する改良されたエントリワイド誤差を求める。 特に、軽度のサンプリング条件下では、スペクトルアルゴリズムは最小誤差境界(ログ係数の変調)を達成する。 改良された分析に基づいて、スペクトルアルゴリズムは、上位$K$回復のための最適なサンプル複雑さ(例えば、承認/不承認応答データから最高の$K$アイテムを識別する)を享受し、前回の研究の実証的な結果を説明する。 第2のコントリビューションでは、IRTで重要だが未検討のトピックであるプライバシーについて取り上げています。 IRTの人間中心の応用にもかかわらず、文献にはプライバシー保護機構が提案されていない。 我々は、独自のマルコフ連鎖定式化と離散ガウス機構を利用したスペクトルアルゴリズムのプライベート拡張を開発する(Canonne et al., 2020)。 実験により、我々のアプローチは低レベルのプライバシー体制のベースラインよりもはるかに正確であることが示されている。

関連論文リスト

• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。 我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。 本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-19T15:29:32Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。 本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。 低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
  論文  参考訳（メタデータ） (2022-11-03T16:42:40Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Understanding the Generalization Performance of Spectral Clustering Algorithms [11.025579607812167]
  本稿では,一般的なスペクトルクラスタリングアルゴリズムであるEmphrelaxed RatioCutとEmphrelaxed NCutの過剰なリスク境界について検討する。 本稿では,この量をペナルライズするだけでなく,サンプル全体を再固有分解することなくサンプル外のデータをクラスタリングする2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-30T14:21:56Z)
• Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods [18.317488965846636]
  クエリリリースのためのプライベート合成データ生成について検討する。 目標は、差分プライバシーの対象となるセンシティブデータセットの衛生バージョンを構築することだ。 本枠組みでは,2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-14T04:19:35Z)
• Spectral Methods for Data Science: A Statistical Perspective [37.2486912080998]
  スペクトル法は、巨大でノイズの多い不完全なデータから情報を抽出するための単純で驚くほど効果的な手法として登場した。 この本は、現代の統計学的観点から、体系的で包括的でアクセスしやすいスペクトル法の導入を意図している。
  論文  参考訳（メタデータ） (2020-12-15T18:40:56Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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