論文の概要: Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles

• arxiv url: http://arxiv.org/abs/2601.20989v1
• Date: Wed, 28 Jan 2026 19:41:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.405249
• Title: Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
• Title（参考訳）: 予算に関するトップk - 弱みと強いOracleによる適応的ランク付け
• Authors: Lutz Oettershagen,
• Abstract要約: ACEは、重要な境界項目に対する強力なクエリに焦点を当てた適応的な認証アルゴリズムである。 次に、ACEを実行する前に、弱い予算を適応的に割り当てる完全適応型2相法であるACE-Wを紹介する。
• 参考スコア（独自算出の注目度）: 2.233624388203003
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identifying the top-$k$ items is fundamental but often prohibitive when exact valuations are expensive. We study a two-oracle setting with a fast, noisy weak oracle and a scarce, high-fidelity strong oracle (e.g., human expert verification or expensive simulation). We first analyze a simple screen-then-certify baseline (STC) and prove it makes at most $m(4\varepsilon_{\max})$ strong calls given jointly valid weak confidence intervals with maximum radius $\varepsilon_{\max}$, where $m(\cdot)$ denotes the near-tie mass around the top-$k$ threshold. We establish a conditional lower bound of $Ω(m(\varepsilon_{\max}))$ for any algorithm given the same weak uncertainty. Our main contribution is ACE, an adaptive certification algorithm that focuses strong queries on critical boundary items, achieving the same $O(m(4\varepsilon_{\max}))$ bound while reducing strong calls in practice. We then introduce ACE-W, a fully adaptive two-phase method that allocates weak budget adaptively before running ACE, further reducing strong costs.
• Abstract（参考訳）: 最高額のアイテムを特定することは基本的だが、正確なバリュエーションが高価である場合、しばしば禁止される。 高速でノイズの多い弱オラクルと希薄で高忠実な強オラクル(例えば、人間の専門家による検証や高価なシミュレーション)を用いた2つのオーラル設定について検討する。 まず、単純なスクリーン・then-certifyベースライン(STC)を分析し、最大値$m(4\varepsilon_{\max})$強い呼び出しを最大値$\varepsilon_{\max}$で有意な弱い信頼区間を与える。 同じ弱不確実性を持つ任意のアルゴリズムに対して$Ω(m(\varepsilon_{\max})$の条件付き下界を確立する。 ACEは、重要な境界項目に強いクエリを集中させ、実際に強い呼び出しを減らしながら同じ$O(m(4\varepsilon_{\max})$boundを達成する適応的な認証アルゴリズムです。 次に、ACEの動作前に弱い予算を適応的に割り当てる完全適応型二相法ACE-Wを導入し、さらにコストを削減した。

関連論文リスト

• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL [6.996002801232415]
  生成モデルを用いてマルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを求める際のサンプル複雑性について検討した。 我々は,知識を必要とせず,最適なスパンベース複雑性に適合するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-02-16T19:10:55Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities [25.153506493249854]
  min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。 また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-05T00:26:10Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
  サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
  論文  参考訳（メタデータ） (2021-03-29T23:03:24Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)

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

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