論文の概要: Improved Ackermannian lower bound for the VASS reachability problem
- arxiv url: http://arxiv.org/abs/2105.08551v1
- Date: Tue, 18 May 2021 14:36:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-19 18:16:10.534563
- Title: Improved Ackermannian lower bound for the VASS reachability problem
- Title(参考訳): VASS到達性問題に対するアッカーマン下界の改善
- Authors: S{\l}awomir Lasota
- Abstract要約: このドラフトは、状態を持つベクトル付加系における到達可能性問題に対するアッカーマン下限のフォローアップである。
従って私達は固定次元のVASSのための下限を改善する前の構造の単純化を提供します。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This draft is a follow-up of the Ackermannian lower bound for the
reachability problem in vector addition systems with states (VASS), recently
announced by Czerwi\'nski and Orlikowski. Independently, the same result has
been announced by Leroux, but with a significantly different proof. We provide
a simplification of the former construction, thus improving the lower bound for
VASS in fixed dimension: while Czerwi\'nski and Orlikowski prove $F_k$-hardness
in dimension $6k$, and Leroux in dimension $4k+9$, the simplified construction
yields $F_k$-hardness already in dimension $3k+2$.
- Abstract(参考訳): このドラフトは、最近 Czerwi\'nski と Orlikowski によって発表された状態を持つベクトル加算系(VASS)における到達可能性問題に対するアッカーマン下界のフォローアップである。
独立して、同じ結果がlerouxによって発表されたが、かなり異なる証拠がある。
czerwi\'nski と orlikowski は、次元 6k$ で $f_k$-hardness、次元 4k+9$ で leroux を証明しているが、単純化された構成により、既に次元 3k+2$ で $f_k$-hardness が得られる。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳(メタデータ) (2024-06-18T08:54:04Z) - Sixfold Way of Traversable Wormholes in the Sachdev-Ye-Kitaev Model [0.0]
赤外線限界では、2次元のほぼ反ド・ジッター時空は弱い二重トレース変形によって摂動される。
この関係を利用して、$N$, $q$, $r$, with $q>2r$ に依存するトラバーサブルワームホールの対称性分類を提案し、レベル統計解析により確認する。
興味深いことに、時間反転状態は新しい状態にはならないため、A、AI、BDI、CI、C、Dの6つの普遍性クラスしか発生しない。
論文 参考訳(メタデータ) (2023-05-16T17:58:53Z) - Variance-aware robust reinforcement learning with linear function
approximation with heavy-tailed rewards [6.932056534450556]
AdaOFUL と VARA という2つのアルゴリズムを,重み付き報酬の存在下でのオンラインシーケンシャルな意思決定のために提案する。
AdaOFULは、$widetildemathcalObigの最先端の後悔境界を達成する。
VarA は $widetildemathcalO(dsqrtHmathcalG*K)$ のより厳密な分散を考慮した後悔境界を達成する。
論文 参考訳(メタデータ) (2023-03-09T22:16:28Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳(メタデータ) (2022-04-06T13:50:33Z) - Byzantine-Robust Federated Linear Bandits [27.77095339417368]
分散エージェントの集合が共通の線形帯域モデルを協調的に学習するフェデレート環境で線形帯域最適化問題を研究する。
標準的な連邦学習アルゴリズムは、少数のエージェントに対するビザンチン攻撃に対して脆弱である。
提案アルゴリズムは, エージェントの半数未満に対するビザンチン攻撃に対して堅牢であり, サブ線形$tildemathcalO(T3/4)$ regret with $mathcalO(sqrtT)$ steps of communicationを実現している。
論文 参考訳(メタデータ) (2022-04-03T20:22:26Z) - Optimal Dynamic Regret in Proper Online Learning with Strongly Convex
Losses and Beyond [23.91519151164528]
適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。
また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
論文 参考訳(メタデータ) (2022-01-21T22:08:07Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳(メタデータ) (2020-12-29T14:06:09Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳(メタデータ) (2020-11-08T16:48:11Z) - Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits [9.833844886421694]
ロジスティック・バンディットは、パラメタライズド・バンディットにおける非線形性の影響を理解するための、散らかったが挑戦的な枠組みを提供することによって、かなりの注目を集めている。
非線型性の効果を精密に解析する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-23T20:07:31Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies [74.39616164169131]
雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。
Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
論文 参考訳(メタデータ) (2020-06-07T05:19:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。