論文の概要: An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
- arxiv url: http://arxiv.org/abs/2609.10196v1
- Date: Wed, 09 Sep 2026 14:02:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:09.043785
- Title: An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
- Title（参考訳）: ERM-Oracle複雑度における指数決定論的-ランダム化ギャップ
- Abstract要約: Attias, Hanneke, Ramaswami (NeurIPS 2025) は、クラスが神託を通してのみアクセス可能である場合に、オンライン学習に必要な神託呼び出しを、ランダム化が確実に減少させるかどうかを問うた。
未知のTインスタンスの総順序に対するしきい値のトランスダクティブオンライン学習と、クエリされたラベル付きセットと整合した完全な概念を返却する一貫性型ERMオラクル、あるいは非実現可能性の報告。
- 参考スコア（独自算出の注目度）: 6.657272312990604
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle. We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set (or reports non-realizability). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with $M+Q\ge T-\varepsilon$ on some instance ($\varepsilon\in\{0,1\}$, according to whether the empty prefix is a concept), and the constant is exact; hence $O(\log T)$ mistakes cost $T-\varepsilon-O(\log T)$ calls, whereas that paper's randomized learner achieves $O(\log T)$ expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least $((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2$, so $Ω(\log T)$ expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves $O(\log T)$ calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need $Θ(T)$ calls.
- Abstract（参考訳）: Attias, Hanneke, Ramaswami (NeurIPS 2025) は、クラスが神託を通してのみアクセス可能である場合に、オンライン学習に必要な神託呼び出しを、ランダム化が確実に減少させるかどうかを問うた。
未知のTインスタンスの総順序に対するしきい値のトランスダクティブオンライン学習と、クエリされたラベル付きセット(あるいは非実現可能性の報告)に一致した完全な概念を返却する一貫性型ERMオラクルを併用する。
我々の主な成果は、固定された自然のオラクルの分離である。
オラクルが最小のプレフィックスルール(または最大-プレフィックスルール)である場合、すべての決定論的学習者はMミスとQコールを、あるインスタンスで$M+Q\ge T-\varepsilon$(あるインスタンスで$\varepsilon\in\{0,1\}$(空の接頭辞が概念であるかどうかによって$O(\log T)$ミスが$T-\varepsilon-O(\log T)$コールである。
ランダム化順序は最適であり、最小のプレフィックス則の下では、すべての学習者は少なくとも$((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2$を持つ。
法的な実効性のあるERMルールでは、決定論的学習者は$O(\log T)$コールとミスを達成し、グローバルメディアルールは再び線形総コストを強制する。
同じ線形境界は、オラクルの答えが反対に選択され、それから記憶のないオラクルに凍結されたときに成り立つ。
弱い一貫性のオラクルだけで、実現可能性ビットを返すと、決定論的およびランダムな学習者の両方が、$(T)$呼び出しを必要とします。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。
弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-09-08T23:09:39Z) - Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。
本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。
結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2026-08-12T14:54:15Z) - Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning [37.15283418677639]
従来のオンライン学習は、LittlestoneのStandard Optimal Algorithm(SOA)をベースラーナーとして利用して、実現可能な設定に還元することで、古典的に解決される。
私たちはSOAを、オフラインの実証的なリスク最小化のオラクルを通じてのみ概念クラスにアクセスする、実現可能なベースラーナーに置き換えます。
提案アルゴリズムは,クエリの総複雑性を$O(Td_mathrmVC+1)$に減らし,ほぼ最適の後悔を完全保存することを示した。
論文 参考訳（メタデータ） (2026-05-08T02:41:23Z) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。
予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
論文 参考訳（メタデータ） (2025-11-17T23:58:11Z) - Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning [17.389446817000945]
学習者が経験的リスク最小化(Empirical Risk Minimization, ERM)や弱一貫性オラクルによってのみ概念クラスと対話する場合, オンライン学習とトランスダクティブオンライン学習を学習する。
論文 参考訳（メタデータ） (2025-05-30T18:11:58Z) - Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。