論文の概要: The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
- arxiv url: http://arxiv.org/abs/2608.08826v1
- Date: Sun, 09 Aug 2026 17:19:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:36.964015
- Title: The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
- Title（参考訳）: 適応性のコスト:学習問題における下位境界のマッチング
- Abstract要約: 我々はスライス正規化ミニマックス比を用いてニュアンス適応を定式化する。
また、事前発表された1つのガウスクエリから任意のポストホックインスペクションへ拡張するコストを定義する。
- 参考スコア（独自算出の注目度）: 1.0742675209112622
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.
- Abstract（参考訳）: アダプティブ・プロシージャは、勾配スケールや滑らか度指数などのオラクルが使用可能なニュアンス情報なしで動作しなければなりませんし、ロバスト・プロシージャは、データが見つかった後にのみ座標と検査時間が選択されたクエリに答えなければならないかもしれません。
このような比較は、オラクルの優位性と妥当性の契約が明確に述べられている場合にのみ意味がある。
各ニュアンスススライス内の最悪のケースインスタンスを保持するスライス正規化ミニマックス比を用いてニュアンス適応を定式化し、前述したガウスクエリから任意のポストホック検査へ拡張するロバスト性コストを別々に定義する。
M 個の独立座標から、すべての座標を保護し、T までの時間的証明器は、サンプル平均となる長方形クラスの中で、順序数 log(eM) + log log(e^eT) の最適正規化二乗半幅を支払う。
エポッチ縫合は、座標と幾何学的時間スケールにまたがる独立したガウスブロックの増分を与えるが、既に幾何学的チェックポイントグリッドを保持しており、実現された最大幅の量子化を強制して、選択と税の停止が加算される。
オンライン凸最適化における未知の勾配スケールは一定のコストを伴い、ネストされたホルダークラスに対するポイントワイド適応は順序付けする(log n / log log n)^(s1/(2s1+1))。
モデル監視として、法則はアナリストに任意のデータ依存時間でMスライスメトリクスを検査させる: 単純固定クエリバンドの選択されたカバレッジは、M=1で0.30に、M>=10で0に急激に低下する一方、エポックステッチされた認証者は、追加の反復対数幅コストで家族的にカバレッジを保持する。
実験では、両方の鋭い予測が反感の危険に晒され、どちらも生き残った。
関連論文リスト
- Observation Design for Certified Control Authority: Projection--Estimability Separation and Active-Face Equivalence [2.7954473524479275]
ゲートは認証可能なアクションのみを実行し、その観測がサポートするもののみを認証する。
本稿では,安全な行動の集合を最大化するために,どのように観測を設計すべきかを問う。
論文 参考訳（メタデータ） (2026-09-05T07:57:04Z) - DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning [4.941039246565574]
大規模走行セールスマン問題 (TSP) では、出力の妥当性を保ちながら限られた計算を割り当てることが求められる。
DualCertは、Emphconstraint-coupled learningを導入し、現在の等級方程式と動的に分離されたサブチュール除去制約がそれぞれの学習遷移を定義する。
1000の保持されたTSP1000インスタンス上で、DualCertは、Lin--Kernighan--Helsgaunバージョン3(LKH-3)からの平均的なツアーコストギャップ(0.0573%)をインスタンス当たり9.55秒のバッチ修正秒で達成した。
論文 参考訳（メタデータ） (2026-08-10T02:48:16Z) - Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - Filtered Conformal Ellipsoids for Graph-Native Time Series [0.8460698440162889]
共形キャリブレーションはスカラー半径を選択する。
我々は、観測可能な予測法則で収縮を分析する。
我々は、対角+低ランク共分散を持つGCN-GRUフィルタを用いて、このフレームワークをインスタンス化する。
論文 参考訳（メタデータ） (2026-06-15T17:46:19Z) - Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret [0.0]
選択性推定誤差は、これらの境界付近の臨界領域でのみ、計画後悔(記憶喪失とオラクル戦略)を引き起こすことを示す。
真の近似指数は境界線を誤定しないが、バイアス付きコストモデルは、推定エラーの堅牢性を修正することができない永続的な誤判定帯域を開放する。
論文 参考訳（メタデータ） (2026-06-15T07:44:58Z) - Measuring the Symmetry--Data Exchange Rate [0.2538209532048867]
同一の軌道サイズと一致した計算値を持つ間違った群制御は制約を伴わないよりも悪いことを示す。
相対交換率beta_diff = 1.28は、理論ブートストラップ1.0と符号と桁違いに一致している。
手法的貢献 -- 共有拡散の欠点をキャンセルする相対レート推定器、間違ったグループ制御、および予め特定された失敗分類 - は、強度をパラメータ化できる帰納バイアスに転送される。
論文 参考訳（メタデータ） (2026-05-31T08:17:40Z) - Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
そこで本研究では,単一プロトコルステップを正確なマッチングタスクで監査するためのペアアウトカム計測インタフェースを提案する。
各インスタンスについて、インターフェースはベースラインの正当性ビットと後ステップの正当性ビットを記録する。
これらのレートは精度の変化を予測し、種、混合物、パイプライン間でテスト可能な再利用可能な経験的インターフェースを定義する。
論文 参考訳（メタデータ） (2026-04-20T13:25:40Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Screening for a Reweighted Penalized Conditional Gradient Method [20.62129327196916]
条件勾配法(CGM)は大規模なスパース凸最適化に広く用いられている。
一般化一般化器の疎性獲得特性の調整方法を示す。
本実験では,正則化器の凹凸を調整し,スクリーニング規則のアグレッシブ性を検証する。
論文 参考訳（メタデータ） (2021-07-02T14:37:37Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。