Fugu-MT 論文翻訳(概要): A Quasipolynomial Algorithm for $\ell

論文の概要: A Quasipolynomial Algorithm for $\ell_\infty$ Contractions

arxiv url: http://arxiv.org/abs/2610.30122v1
Date: Wed, 21 Oct 2026 17:57:19 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-23 00:40:06.470519
Title: A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
Title（参考訳）: $\ell_\infty$拘縮に対する準ポリノミカルアルゴリズム
Abstract要約: 任意の$d$次元の非展開の固定点を$eps$-approximateで計算するためのアルゴリズムを与える。我々のアルゴリズムは、単純なゲームは準多項式時間で解けることを示唆している。
参考スコア（独自算出の注目度）: 30.90390177306372
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.
Abstract（参考訳）: 我々は、$\eps$-approximate fixed point of any $d$-dimensional nonexpansion with the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$を計算するためのアルゴリズムを与える。その中核となるのは,探索領域を幾何的に縮めるためにブースティング引数を用いる手法である。このアルゴリズムは, 半多項式時間で単純な確率ゲームが解けることを示唆している。

関連論文リスト

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits [0.17398560678845074]
我々は、$|langle x|U|0nrangle|2$ to additive error $varepsilon$ in $mathrmpoly(n, 1/varepsilon)$ timeを推定する決定論的古典的アルゴリズムを与える。
論文参考訳（メタデータ） (2026-10-01T17:49:01Z)
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications [13.39372872460586]
mathbbRn times d$ の行列 $X の 2 つの右幅 q$ノルムは $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$ と定義される。 FOCS(Exponential Time hypothesis)を仮定すると、単純なスペクトルアルゴリズムは2sqrtlog n$よりも近似係数がよいことを示す。
論文参考訳（メタデータ） (2026-05-24T23:56:06Z)
Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
Fixed Point Computation: Beating Brute Force with Smoothed Analysis [28.978340288565118]
本稿では,$varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself。アルゴリズムのランタイムは、スムーズな分析フレームワークの下で、$eO(n)/varepsilon$でバウンドされる。
論文参考訳（メタデータ） (2025-01-18T21:32:26Z)
A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文参考訳（メタデータ） (2024-06-26T18:19:10Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文参考訳（メタデータ） (2023-06-16T17:00:51Z)
Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文参考訳（メタデータ） (2021-06-14T07:36:25Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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