論文の概要: Dynamic estimation of slowly varying sequences

• arxiv url: http://arxiv.org/abs/2606.23655v1
• Date: Mon, 22 Jun 2026 17:40:49 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-06-24 20:29:34.447941
• Title: Dynamic estimation of slowly varying sequences
• Title（参考訳）: ゆっくり変化する配列の動的推定
• Authors: Prashant Gokhale, Mikhail Khodak, Sandeep Silwal,
• Abstract要約: 暗黙的トレース推定に関する最近の研究は、$_t$が小さい場合、クエリを過去のシーケンス要素に再利用することで、全体的なコストを削減できることを示している。 我々はこれを様々なベクトル空間上の様々な線型および非線形関数に一般化する枠組みを導入する。 我々は,このフレームワークを用いて,推定予算を$_t$で局所的にスケールする新しいアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 15.847711110274771
• License:
• Abstract: We consider the problem of sequentially approximating functions of each element in a slowly-varying sequence, i.e. one where the magnitude $α_i$ of the difference between the elements at positions $i$ and $i-1$ is small. Recent work on implicit trace estimation shows that when $α_t$ is small, reusing queries to past sequence elements can reduce the overall cost [Dharangutte \& Musco, NeurIPS~2021; Woodruff et al., NeurIPS~2022]. We introduce a framework generalizing this to a variety of linear and nonlinear functions on diverse vector spaces, obtaining novel sequential estimation results for matrix powers, spectral densities, Monte Carlo integration, and a boundary value problem from partial differential equations~(PDEs). Furthermore, we develop a novel algorithm for use with this framework that locally scales the estimation budget with $α_t$, obtaining sharper path-length-style variation bounds of form $\mathcal O(\sum_{i=1}^mα_i)$ on the cost of estimating a sequence of length $m$. This improves upon the previous implicit trace estimation bound of $\mathcal O(m\cdot\max_iα_i)$ [Dharangutte \& Musco, NeurIPS~2021], which is achieved by fixing the query budget using the worst-case $α_i$ and is thus inefficient for stable sequences with rare bursts. Lastly, while all past work assumes a known bound on $α_i$, we show in certain cases how the changes can be estimated on-the-fly with (nearly) no added cost. In summary, our framework makes the sequential approximation toolkit general-purpose and adaptive while improving upon state-of-the-art-guarantees for dynamic trace estimation.
• Abstract（参考訳）: ゆっくりと変化する列における各要素の関数を逐次近似する問題、すなわち、位数 $i$ と $i-1$ の要素間の差の大きさ $α_i$ が小さい場合を考える。 暗黙的トレース推定に関する最近の研究は、$α_t$が小さい場合、クエリを過去のシーケンス要素に再利用することで、全体のコストを削減できることを示している(Dharangutte \& Musco, NeurIPS~2021; Woodruff et al , NeurIPS~2022]。 本稿では、これを様々なベクトル空間上の様々な線型および非線形関数に一般化する枠組みを導入し、行列パワー、スペクトル密度、モンテカルロ積分、偏微分方程式~(PDE)による境界値問題に対する新しい逐次推定結果を得る。 さらに,このフレームワークを用いた新しいアルゴリズムを開発し,$α_t$で推定予算を局所的にスケールし,$\mathcal O(\sum_{i=1}^mα_i)$の急激な経路長スタイルの変動境界を求める。 これは、$\mathcal O(m\cdot\max_iα_i)$ [Dharangutte \& Musco, NeurIPS~2021]の以前の暗黙的トレース推定バウンダリを改善する。 最後に、過去のすべての作業は、$α_i$の既知境界を仮定するが、あるケースでは、変更を(ほぼ)追加コストなしで、オンザフライでどのように見積もることができるかを示す。 まとめると、我々のフレームワークは、動的トレース推定のための最先端ガイダンスを改善しつつ、逐次近似ツールキットを汎用的で適応的にする。

関連論文リスト

• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
  本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。 十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
  論文  参考訳（メタデータ） (2025-07-15T12:52:47Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  対人的マルコフ決定過程における学習の問題を考える。 本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
  論文  参考訳（メタデータ） (2020-07-23T08:23:44Z)

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

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