Fugu-MT 論文翻訳(概要): Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension

論文の概要: Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension

arxiv url: http://arxiv.org/abs/2609.05214v1
Date: Fri, 04 Sep 2026 14:49:02 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-07 18:15:24.074911
Title: Dimension-Adaptive Batched Lipschitz Narrowing Without Knowing the Zooming Dimension
Title（参考訳）: ズームング次元を知らない次元適応バッチリプシッツナローリング
Abstract要約: このメモはズーム次元$d_z$への依存を取り除く。結果のCount-Adaptive BLiNアルゴリズムは$d_z$やズーム定数$C_z$を使用しない。元の論文のTheorem 10のアダプティブグリッドローバウンドと合わせて、$d_z$が未知の場合には、最適なバッチ複雑性は$_d(loglog T)$のままである。
参考スコア（独自算出の注目度）: 2.7074235008521246
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension $d_z$. This note removes that dependence. The next edge length is selected from the number of cubes that survive the preceding elimination. The resulting Count-Adaptive BLiN algorithm does not use $d_z$ or the zooming constant $C_z$, yet it attains $\widetilde{\mathcal O}_d(T^{(d_z+1)/(d_z+2)})$ regret with $\mathcal O_d(\log\log T)$ batches. Together with the adaptive-grid lower bound in Theorem 10 of the original paper, the optimal batch complexity remains $Θ_d(\log\log T)$ when $d_z$ is unknown.
Abstract（参考訳）: A-BLiNの適切な組合せエッジ長(ACE)シーケンスはズーム次元$d_z$に依存する。このメモはその依存を取り除きます。次のエッジ長は、前回の除去に耐える立方体の数から選択される。結果のCount-Adaptive BLiNアルゴリズムは$d_z$やズーム定数$C_z$を使用しないが、$\widetilde{\mathcal O}_d(T^{(d_z+1)/(d_z+2)})$ regret with $\mathcal O_d(\log\log T)$ batchesに達する。元の論文のTheorem 10の適応格子下界と共に、最適なバッチ複雑性は、$d_z$が未知のときに、$ s_d(\log\log T)$ のままである。

関連論文リスト

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation [17.156227790252526]
q = Oleft(T + fraclog (1/varepsilon)logleft(e + log (1/varepsilon)/(T) right) 最適なクエリ複雑性を保ち、$Oleft[q left(a + logleft (1 + fracT(+ T)varepsilonを使用する同じアルゴリズムの実装を提供する。
論文参考訳（メタデータ） (2026-08-31T11:39:55Z)
Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文参考訳（メタデータ） (2026-08-27T01:31:46Z)
New Bounds for the Last Iterate of the Stochastic subGradient Method [11.179752660122281]
本稿では,1次元凸リプシッツ目標に対する下段法の最後の繰り返しについて検討する。最後の繰り返しは1/sqrt n$の順序の最適化誤差を特徴とする。 i.d.仮定がなければ、最適化誤差は位数 $(log n)/sqrt n$ となる。
論文参考訳（メタデータ） (2026-06-23T17:55:18Z)
Instance-dependent Stochastic Lipschitz bandit [28.946496440127603]
学習者が未知のリプシッツ関数をドメイン上で逐次最大化するリプシッツバンドイット問題について検討する。既存の後悔境界は最悪の場合であり、$tilde left (Td+1/d+2right )$としてスケールするか、ズーム次元$d_z$で適応する。我々は、そのレベル集合上の$f$の準最適ギャップの積分を通して後悔を特徴づける分析とアルゴリズムを提供する。
論文参考訳（メタデータ） (2026-05-28T10:46:30Z)
Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
論文参考訳（メタデータ） (2026-05-22T12:22:20Z)
Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文参考訳（メタデータ） (2025-08-09T08:28:06Z)
Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
論文参考訳（メタデータ） (2025-06-06T20:33:57Z)
A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文参考訳（メタデータ） (2024-06-07T11:40:54Z)
On the $O(\rac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文参考訳（メタデータ） (2024-02-01T07:21:32Z)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文参考訳（メタデータ） (2022-07-15T11:55:09Z)
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints [18.03695167610009]
サンプルサイズ$n$が最低しきい値$n*(s, d, b)$を超えると、$Oleft( fracsn2bright)$の$ell$推定誤差を達成できることを示す。対話的な設定のために,新しい木に基づく推定手法を提案し,次元自由収束を実現するために必要な最小サンプルサイズを,さらに$n*(s, d, b)$に縮めることを示した。
論文参考訳（メタデータ） (2021-06-16T07:52:14Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

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