論文の概要: Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

• arxiv url: http://arxiv.org/abs/2607.10963v1
• Date: Mon, 13 Jul 2026 00:16:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-14 17:47:21.288667
• Title: Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
• Title（参考訳）: Smoothed Online Learning への効果的なオンライン比例サンプリング
• Abstract要約: 我々は,高次元領域からの効率的なオンライン比例サンプリングの問題を,$$smoothedの逆条件下で検討した。 この設定は、プリンシパルエージェントゲーム(価格や契約設計など)を含む幅広いアプリケーションを取り込む。 我々は、データ構造の深さに厳密な$O(sqrtT)$バウンドを証明し、ランダムなオーダー逆数の下で$O(log T)$バウンドを証明した。
• 参考スコア（独自算出の注目度）: 17.03942758909167
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of efficient online proportional sampling from a high-dimensional domain under a $σ$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as $O(t^d)$ by round $t$ in $d$ dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a $σ$-smoothed adaptive adversary, we prove a tight $O(\sqrt{σT})$ bound on the depth of our data structure, and an $O(\log T)$ bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.
• Abstract（参考訳）: 我々は,高次元領域からの効率的なオンライン比例サンプリングの問題を$σ$-smoothedの逆数の下で検討し,この場合,サンプリング分布は断片的に構造化された分割列上に定義された動的に変化する重み関数によって誘導される。 この設定は、プリンシパルエージェントゲーム(例えば、価格と契約設計)、アルゴリズム設定とパラメータチューニングなど、幅広いアプリケーションを取り込む。 本質的には、サブリージョンの数は$O(t^d)$ by round $t$ in $d$ dimensionsとして成長することができる。 我々は、この指数的成長を明示的に維持するコストを回避しつつ、効率的な更新と比例サンプリングをサポートするデータ構造を設計する。 σ$-smoothed Adaptive Adversary(英語版)の下では、データ構造の深さに厳密な$O(\sqrt{σT})$バウンドを証明し、ランダムな順序の敵の下では$O(\log T)$バウンドを証明します。 本枠組みは,完全情報と包括的フィードバックの両面から効率の良いノンレグレットアルゴリズムを得られるオンライン学習に応用し,証明可能なサブ線形後悔保証を付与する。

関連論文リスト

• Denoising growth complexity: Data geometry and certified schedules for diffusion sampling [14.877292137182422]
  我々は、$mathsfDGC$インクリメントが、革新表現に適用されたオイラースキームのKL誤差に単純で明示的な境界をもたらすことを示す。 我々は、より単純なシングルブロック設定とより洗練された$K$ブロック設定の両方において、最適化されたステップサイズスケジュールに対するKLサンプリング保証を導出する。
  論文  参考訳（メタデータ） (2026-07-28T21:26:16Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  我々は,既存のGNNベースのレコメンデータアーキテクチャとシームレスに統合可能な,効率的かつモジュール化されたフレームワークである textbfLighter-X を提案する。 提案手法は,基本モデルの理論的保証と経験的性能を保ちながら,パラメータサイズと計算複雑性を大幅に低減する。 実験の結果、Lighter-Xはパラメータが大幅に少ないベースラインモデルに匹敵するパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2025-10-11T08:33:08Z)
• Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels [24.314013749328677]
  本研究では,レスレスマルチアームバンド (RMAB) における資源配分について,未知および非定常力学の下で検討する。 我々は,時変カーネルに適応しながら計算効率を保ちながら,スライディング・ウィンドウ・オンラインウィトル (SW-Whittle) ポリシーを提案する。 我々のアルゴリズムは一貫してベースラインを上回り、様々な非定常環境において最も低い累積的後悔を達成している。
  論文  参考訳（メタデータ） (2025-06-22T22:04:52Z)
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
  ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。 十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
  論文  参考訳（メタデータ） (2025-06-02T01:58:48Z)
• Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional Systems [3.6773638205393198]
  高次元モデルにおける効率的な推論は、機械学習における中心的な課題である。 本稿では,Gaussian Ensemble Belief Propagation (GEnBP)アルゴリズムを紹介する。 本稿では,GEnBPが既存の信念手法よりも精度と計算効率で優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-13T03:31:36Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Linearly-scalable learning of smooth low-dimensional patterns with permutation-aided entropic dimension reduction [0.0]
  多くのデータサイエンス応用において、高次元データセットから適切に順序付けられた滑らかな低次元データパターンを抽出することが目的である。 本研究では, ユークリッドの滑らか度をパターン品質基準として選択する場合, これらの問題を数値的に効率的に解けることを示す。
  論文  参考訳（メタデータ） (2023-06-17T08:03:24Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  本稿では,SGDの軌道に局在する新しい被覆手法を提案する。 このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。 これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
  論文  参考訳（メタデータ） (2022-09-19T12:11:07Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks [42.43493635899849]
  畳み込み残余ネットワーク(ConvResNet)の理論的保証を関数近似および二項分類の統計的推定の観点から確立する。 その結果,ConvResNetsはデータセットの低次元構造に適応していることがわかった。
  論文  参考訳（メタデータ） (2021-09-07T02:58:11Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• $P^2$ Net: Augmented Parallel-Pyramid Net for Attention Guided Pose Estimation [69.25492391672064]
  拡張ボトルネックとアテンションモジュールによる特徴改善を施したパラレルピラミドネットを提案する。 並列ピラミド構造は、ネットワークによって導入された情報損失を補うために続く。 提案手法は, MSCOCO と MPII のデータセットにおいて, 最適な性能を実現する。
  論文  参考訳（メタデータ） (2020-10-26T02:10:12Z)

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

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