論文の概要: Nested Elimination: A Simple Algorithm for Best-Item Identification from Choice-Based Feedback

• arxiv url: http://arxiv.org/abs/2307.09295v1
• Date: Thu, 13 Jul 2023 05:05:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-23 12:06:44.620134
• Title: Nested Elimination: A Simple Algorithm for Best-Item Identification from Choice-Based Feedback
• Title（参考訳）: Nested Elimination: 選択に基づくフィードバックからのベスト項目識別のための簡易アルゴリズム
• Authors: Junwen Yang, Yifan Feng
• Abstract要約: 選択に基づくフィードバックから最良項目識別の問題について検討する。 この問題において、企業は、顧客集団に順次かつ適応的に表示セットを表示し、その選択を収集する。 情報理論の下界にインスパイアされたネスト構造にインスパイアされた,除去に基づくアルゴリズムNested Elimination(NE)を提案する。
• 参考スコア（独自算出の注目度）: 8.043586007062858
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the problem of best-item identification from choice-based feedback. In this problem, a company sequentially and adaptively shows display sets to a population of customers and collects their choices. The objective is to identify the most preferred item with the least number of samples and at a high confidence level. We propose an elimination-based algorithm, namely Nested Elimination (NE), which is inspired by the nested structure implied by the information-theoretic lower bound. NE is simple in structure, easy to implement, and has a strong theoretical guarantee for sample complexity. Specifically, NE utilizes an innovative elimination criterion and circumvents the need to solve any complex combinatorial optimization problem. We provide an instance-specific and non-asymptotic bound on the expected sample complexity of NE. We also show NE achieves high-order worst-case asymptotic optimality. Finally, numerical experiments from both synthetic and real data corroborate our theoretical findings.
• Abstract（参考訳）: 選択に基づくフィードバックから最良項目識別の問題を検討する。 この問題において、企業は顧客集団に表示セットを順次かつ適応的に表示し、選択を収集する。 その目的は、最少のサンプル数と高い信頼度で、最も好ましいアイテムを特定することである。 本稿では,情報理論下界に暗示されるネスト構造に触発された除去に基づくアルゴリズムであるネスト除去(ne)を提案する。 NEは構造がシンプルで実装が容易で、サンプルの複雑さに対する理論的な保証が強い。 具体的には、NEは革新的な除去基準を利用し、複雑な組合せ最適化問題の解決を回避している。 ne のサンプル複雑性に対するインスタンス固有かつ非漸近的境界を提供する。 また、NEは高次最悪の漸近的最適性を達成することを示す。 最後に、合成データと実データの両方による数値実験は、我々の理論的知見を裏付けるものである。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Debiasing Conditional Stochastic Optimization [15.901623717313493]
  本稿では,ポートフォリオ選択や強化学習,堅牢な学習など,さまざまな応用をカバーする条件因果最適化(CSO)問題について検討する。 有限変量変量CSO問題に対する新しいアルゴリズムを開発し、既存の結果を大幅に改善する。 我々は,本手法が他の最適化問題と同様の課題に対処するための有用なツールとなる可能性があると考えている。
  論文  参考訳（メタデータ） (2023-04-20T19:19:55Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。 本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。 提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
  論文  参考訳（メタデータ） (2021-10-22T19:49:59Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  グループテストは、いくつかの魅力的なソリューションでよく研究されている問題である。 近年の生物学的研究は、従来の方法と相容れない新型コロナウイルスの実践的な制約を課している。 我々は,Bloomフィルタと信条伝搬を組み合わせた新しい手法を開発し,n(100以上)の大きい値に拡張し,良好な経験的結果を得る。
  論文  参考訳（メタデータ） (2020-07-21T19:31:41Z)

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

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