論文の概要: Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications

• arxiv url: http://arxiv.org/abs/2605.25303v2
• Date: Thu, 28 May 2026 17:16:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:54.639677
• Title: Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
• Title（参考訳）: ポリノミカルImproved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
• Authors: Samuel B. Hopkins, Stefan Tiegel,
• Abstract要約: 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$よりも近似係数がよいことを示す。
• 参考スコア（独自算出の注目度）: 13.39372872460586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $2 \rightarrow q$ norm of a matrix $X \in \mathbb{R}^{n \times d}$ is defined as $\lVert X \rVert_{2 \rightarrow q} = \sup_{\lVert v \rVert_2 = 1} \lVert Xv \rVert_q$. We give polynomial-time multiplicative approximation algorithms for this norm when $q > 2$ (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what approximation factors we can achieve for this problem in polynomial time, even though such approximations have significant downstream consequences. Barak, Brandão, Harrow, Kelner, Steurer, and Zhou showed that no polynomial-time algorithm can achieve an approximation factor better than $2^{\sqrt{\log n}}$, assuming the Exponential Time Hypothesis (FOCS'12). On the other hand, a simple spectral algorithm gives a $d^{1/4}$-approximation as a baseline. We give, to the best of our knowledge, the first polynomial-time approximation algorithm beating this baseline by polynomial factors. For the important special case of $q = 4$ it achieves a $d^{1/8}$-approximation. All previous algorithms required additional assumptions on $X$, or only surpassed the baseline for small values of $n$. Moreover, we construct sum-of-squares certificates for the $2 \rightarrow q$ norm. This directly implies improved algorithms for robust mean and covariance estimation, robust regression, and clustering, when the data only satisfies a bound on its $q$-th moment.
• Abstract（参考訳）: 行列 $X \in \mathbb{R}^{n \times d}$ の $2 \rightarrow q$ norm は $\lVert X \rVert_{2 \rightarrow q} = \sup_{\lVert v \rVert_2 = 1} \lVert Xv \rVert_q$ と定義される。 このノルムに対する多項式時間乗法近似アルゴリズムは、$q > 2$ である(すなわち、超収縮的設定において)。 この問題は、組合せ最適化と近似の硬度(例:小集合展開)、量子情報(例:最良の分離状態)、アルゴリズム統計学における長年の未解決問題に直接、あるいは密接に関連している。 このような近似が下流で顕著な結果をもたらすにもかかわらず、多項式時間でこの問題に対してどのような近似因子が達成できるかは、ほとんど分かっていない。 Barak, Brandão, Harrow, Kelner, Steurer, Zhou は、指数時間仮説 (FOCS'12) を仮定して、多項式時間アルゴリズムが 2^{\sqrt{\log n}}$ 以上の近似係数を達成できないことを示した。 一方、単純なスペクトルアルゴリズムはベースラインとして$d^{1/4}$-approximationを与える。 我々の知る限りでは、最初の多項式時間近似アルゴリズムがこの基底線を多項式因子によって破る。 q = 4$の重要な特別な場合、$d^{1/8}$-approximationを達成する。 以前のアルゴリズムはすべて、$X$で追加の仮定を必要としたか、あるいは$n$の小さな値でベースラインを超えただけであった。 さらに,2 の \rightarrow q$ norm に対して二乗証明を構築する。 これは、データが$q$-thのモーメントのみを満たす場合、ロバスト平均と共分散推定、ロバスト回帰、クラスタリングのための改良されたアルゴリズムを直接意味する。

関連論文リスト

• Computational Hardness of Private Coreset [84.99100741615423]
  与えられた点の入力集合に対して、コアセットは任意の候補解に対する$k$-meansの目的が乗法的な$(, 1/n(1))$ factor(およびいくつかの加法因子)まで保存されるような点の別の集合である。 no-time $(, 1/n(1))$-DPアルゴリズムは、ある定数$> 0$(およびいくつかの定数加法因子)に対して$ell_infty$-metricの$k$-meansのコアセットを計算することができることを示す。 $k$-means in the
  論文  参考訳（メタデータ） (2026-02-19T15:58:49Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products [9.661328973620531]
  自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。 我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。 我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
  論文  参考訳（メタデータ） (2023-11-03T14:56:24Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
  我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。 また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
  論文  参考訳（メタデータ） (2022-02-11T23:53:43Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。 局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
  論文  参考訳（メタデータ） (2021-05-31T14:41:40Z)

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

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