論文の概要: Contextual Search in the Presence of Adversarial Corruptions

• arxiv url: http://arxiv.org/abs/2002.11650v6
• Date: Sat, 6 Aug 2022 15:05:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 15:00:02.983325
• Title: Contextual Search in the Presence of Adversarial Corruptions
• Title（参考訳）: 敵対的腐敗の存在下での文脈探索
• Authors: Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert Schapire
• Abstract要約: より高次元における二項探索の一般化である文脈探索について検討する。 これらのアルゴリズムは, 敵対的腐敗がない場合に, ほぼ最適に後悔することを示す。 我々の手法は学習理論、ゲーム理論、高次元幾何学、凸解析からインスピレーションを得ている。
• 参考スコア（独自算出の注目度）: 33.28268414842846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study contextual search, a generalization of binary search in higher dimensions, which captures settings such as feature-based dynamic pricing. Standard formulations of this problem assume that agents act in accordance with a specific homogeneous response model. In practice, however, some responses may be adversarially corrupted. Existing algorithms heavily depend on the assumed response model being (approximately) accurate for all agents and have poor performance in the presence of even a few such arbitrary misspecifications. We initiate the study of contextual search when some of the agents can behave in ways inconsistent with the underlying response model. In particular, we provide two algorithms, one based on multidimensional binary search methods and one based on gradient descent. We show that these algorithms attain near-optimal regret in the absence of adversarial corruptions and their performance degrades gracefully with the number of such agents, providing the first results for contextual search in any adversarial noise model. Our techniques draw inspiration from learning theory, game theory, high-dimensional geometry, and convex analysis.
• Abstract（参考訳）: 本研究では,より高次元のバイナリ検索の一般化である文脈探索について検討し,機能ベースの動的価格設定などの設定を捉えた。 この問題の標準的な定式化は、エージェントが特定の同種反応モデルに従って作用すると仮定する。 しかし実際には、一部の反応は逆向きに腐敗することがある。 既存のアルゴリズムは、仮定された応答モデルが全てのエージェントに(ほぼ)正確であることに大きく依存しており、そのような任意的な誤特定の存在下でも性能が劣る。 エージェントが基盤となる応答モデルと矛盾する方法で振る舞うことができる場合、文脈探索の研究を開始する。 特に,多次元二元探索法に基づくアルゴリズムと勾配勾配に基づくアルゴリズムの2つを提案する。 これらのアルゴリズムは, 敵対的汚職の欠如と, それらの性能が, エージェント数に応じて優雅に低下していることが示され, 敵対的雑音モデルにおける文脈探索の最初の結果となった。 学習理論,ゲーム理論,高次元幾何学,凸解析から着想を得た。

関連論文リスト

• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。 1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
  論文  参考訳（メタデータ） (2024-02-20T08:30:46Z)
• The Perception-Robustness Tradeoff in Deterministic Image Restoration [34.50287066865267]
  本研究では,画像の逆問題に対する決定論的手法の挙動について検討する。 完全品質と完全整合性にアプローチするには、モデルのリプシッツ定数は無限大に成長しなければならない。 我々は単一画像の超解像アルゴリズムについて,ノイズと雑音の両方に対処する理論を実証する。
  論文  参考訳（メタデータ） (2023-11-14T18:30:34Z)
• PSDiff: Diffusion Model for Person Search with Iterative and Collaborative Refinement [59.6260680005195]
  本稿では,拡散モデルであるPSDiffに基づく新しいPerson Searchフレームワークを提案する。 PSDiffは、ノイズの多いボックスとReID埋め込みから地上の真実へのデュアルデノケーションプロセスとして検索する人を定式化する。 新しいパラダイムに従って、我々は、反復的かつ協調的な方法で検出とReIDサブタスクを最適化する新しいコラボレーティブ・デノナイジング・レイヤ(CDL)を設計する。
  論文  参考訳（メタデータ） (2023-09-20T08:16:39Z)
• Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes [1.7403133838762448]
  隠れたビットをグリーディーな方法で推定する近似再構成アルゴリズムを解析する。 我々の分析はノイズの度合いと$sigma$の空間性に一様である。
  論文  参考訳（メタデータ） (2023-02-28T19:31:40Z)
• RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval [84.33752026418045]
  本稿では, 対向性摂動に対して確実に頑健な1-nearest neighbor(NN)画像検索アルゴリズムであるRetrievalGuardを提案する。 このスムーズな検索モデルはリプシッツ定数を一定に保ち、従って検索スコアは$ell$逆転摂動に不変であることを示す。
  論文  参考訳（メタデータ） (2022-06-17T16:50:50Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  本稿では,2つの多様性探索アルゴリズム,ノベルティ探索アルゴリズムとゴール探索処理アルゴリズムの特性について検討する。 mpアルゴリズムとの関係は、ポリシーパラメータ空間と結果空間の間のマッピングの滑らかさ、あるいは滑らかさの欠如が検索効率において重要な役割を担っていることを示している。
  論文  参考訳（メタデータ） (2021-04-10T13:52:27Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• Query complexity of adversarial attacks [4.873362301533825]
  敵対的文献では、ブラックボックスとホワイトボックスの2つの主要な攻撃モデルが検討されている。 これらの脅威モデルは、敵が問うことのできるクエリの数によってインデックスされた、きめ細かいスペクトルの2つの端であると考えている。 我々は、ホワイトボックスモデルで可能な攻撃に匹敵する攻撃を設計するために、敵が要求するクエリ数を調査する。
  論文  参考訳（メタデータ） (2020-10-02T15:01:29Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)

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

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