論文の概要: Lower Bounds for Linear-Oracle Online Learning
- arxiv url: http://arxiv.org/abs/2609.38375v1
- Date: Tue, 29 Sep 2026 18:34:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:26.592481
- Title: Lower Bounds for Linear-Oracle Online Learning
- Title（参考訳）: 線形Oracleオンライン学習のための下位境界
- Abstract要約: ワイベルらは固定係数法は不可能であると推測した。
我々はそれらの予想を証明し、その下限をオラクルのみのモデルにおける決定論的学習者すべてに拡張する。
最新の勾配の非ゼロ係数を持つ1回の固定スケジュールの場合、第2の構成は、発行されたクエリごとにユニークな最小値を持つ少なくとも3ドルLDT3/4/4$の後悔を与える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For $T$ rounds, at most $b$ calls between decisions, diameter bound $D$, and gradient norm bound $L$, we construct an instance in dimension $d=2b(T-1)+1$ with regret at least $2^{-1/4}LDb^{-1/4}T^{3/4}$. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant $b$, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least $3LDT^{3/4}/4$ with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.
- Abstract（参考訳）: 1ラウンドあたりの線形最小化の定数数は、一般凸集合上のオンラインフランク=ウルフの後悔率$T^{3/4}$で改善できるだろうか?
ワイベルらは固定係数法は不可能であると推測した。
我々はそれらの予想を証明し、その下限をオラクルのみのモデルにおける決定論的学習者すべてに拡張する。
学習者は、最初の実現可能な点と直径境界を受信し、そのオラクルの応答と整合した全ての領域で実行可能でなければならない。
$T$ラウンドの場合、決定の間の少なくとも$b$コール、直径境界$D$、勾配ノルム$L$の場合、少なくとも2^{-1/4}LDb^{-1/4}T^{3/4}$を後悔して、次元$d=2b(T-1)+1$のインスタンスを構築する。
相手は、プレー前にドメイン、初期点、決定論的タイルール、線形損失を修正します。
頂点は、決定の前に利用可能な全ての点が電流損失ゼロの経路を形成し、最後の頂点は全てのラウンドで負の損失を持つ。
定数$b$の場合、その値は次元に依存しない保証の既知の上限値と一致する。
最新の勾配の係数がゼロでない1回の固定スケジュールの場合、第2の構成は、発行されたクエリごとに一意の最小値を持つ少なくとも3LDT^{3/4}/4$を後悔させる。
Weibelらによる調整されたスケジュールの厳密な算術証明は、特異なオラクルの応答を伴う有限水平の最悪のケースと密接に一致している。
関連論文リスト
- The Signed Geometry of One-Shot Recourse: On-Path Validity and the Signed-Curvature Criterion [0.16921396880325776]
クローズドフォームのリコースは、期待される距離によって分類器の$hat g$の単位勾配に沿って、拒否されたユーザーを移動させる。
このワンショットステップがいつ成功し、追加のモデルクエリが変更されるのかを問う。
論文 参考訳（メタデータ） (2026-09-28T20:44:23Z) - 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) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor [47.30196146041476]
我々は、$d$-oracle単位のコンパクト凸部分集合上の非対称非負、非単調DR-部分モジュラ函数について研究する。
オンラインアルゴリズムは、フィードバックが条件付きで偏りがなく、有界であるときに、およその後悔で0.401$に達する。
論文 参考訳（メタデータ） (2026-09-02T06:00:10Z) - 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) - Online Convex Optimization with Sublinear Noisy Probes [6.998574163422056]
オンライン凸最適化(OCO)を凸集合として$Ksubseteq mathbb Rd$で検討する。
我々は最近の2つの作業の行を一般化する統一された探索モデルを導入する: 専門家設定におけるサブ線形ベストエキスパートクエリと、OCOの各ラウンドで利用できるペアワイズフィードバックである。
本研究の主目的は, サブリニアでノイズの多いプローブ予算であっても, OCO体制の完全なフィードバックにおける最悪の後悔を確実に改善できることである。
論文 参考訳（メタデータ） (2026-06-12T17:05:08Z) - Complexity Bounds for Smooth Convex Multiobjective Optimization [0.0]
目的値$m$の滑らかな多目的最適化において,$varepsilon$-Pareto定常点を求める際のオラクルの複雑さについて検討する。
強い凸目的に対して、任意の一階法は、$exp(-Theta(T/sqrtkappa)$ after $T$ oracle call よりも早く線形収束を示す。
適応スカラー化を伴う凸問題や一般スパン法に対して、最終イテレートの勾配ノルムに1/T2$の普遍的下界を確立する。
論文 参考訳（メタデータ） (2025-09-16T21:33:11Z) - Improved and Oracle-Efficient Online $\ell_1$-Multicalibration [14.147331133778916]
本研究では,複数のグループにまたがるキャリブレーション予測を行うフレームワークであるエンフォリン・マルチキャリブレーションについて検討する。
そこで本研究では,$widetildemathcalO(T-1/4)$を改良し,オラクル効率を向上する手法を提案する。
我々のフレームワークは、(ell_H)-multicalibration誤差の1ドルLipschitz特性を利用して、ある無限群の族にも拡張する。
論文 参考訳（メタデータ） (2025-05-23T00:37:49Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。