Fugu-MT 論文翻訳(概要): Improved Ackermannian lower bound for the VASS reachability problem

論文の概要: 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 が得られる。

関連論文リスト

Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文参考訳（メタデータ） (2024-11-12T11:30:53Z)
Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
論文参考訳（メタデータ） (2024-10-01T13:45:55Z)
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)
New constructive counterexamples to additivity of minimum output Rényi p-entropy of quantum channels [0.0]
我々は、対応する最小出力 R'enyi $p$-エントロピーが加法的でない新しい量子チャネルの族を示す。我々の写本は Grudka et al., J. Phys. A: Math. Theor. 43 425304 の成果によって動機付けられている。
論文参考訳（メタデータ） (2023-01-18T10:55:30Z)
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)
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)

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