論文の概要: The Condition-Number Barrier in Sparse Least Squares

• arxiv url: http://arxiv.org/abs/2608.02588v1
• Date: Mon, 03 Aug 2026 17:57:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-04 15:07:25.748953
• Title: The Condition-Number Barrier in Sparse Least Squares
• Title（参考訳）: スパースラストスクエアにおけるコンディション・ノーバーバリア
• Abstract要約: AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
• 参考スコア（独自算出の注目度）: 77.64108812086542
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed $γ\in(0,1]$, there is no randomized polynomial-time algorithm that, with probability at least $2/3$, returns a vector $x$ such that, writing $s=\lVert x\rVert_0$, \[ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\!\left(k\,κ_{s+k}^{\,1-γ}\right), \] where $κ_r$ is the restricted condition number at sparsity level $r$. The result holds even on rational instances with $A$ of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.
• Abstract（参考訳）: AxiotisとSviridenkoは[AS21]において、スパース凸最適化における制限条件数への線形依存は多項式時間アルゴリズムでは改善できないと推測した。 我々は、Raghavendra, Steurer, Tulsiani [RST12] の重み付き正規グラフ定式化におけるランダム化された完全体積小セット展開仮説に基づく、最小二乗目的に対するそれらの予想下界を確立する。 具体的には、すべての固定された$γ\in(0,1]$に対して、少なくとも2/3$の確率で、$s=\lVert x\rVert_0$, \[ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\! \left(k\,κ_{s+k}^{\,1-γ}\right), \] ここで$κ_r$はスパーシティレベル$r$の制限条件数である。 その結果は、完全列ランクの$A$の有理インスタンスにも当てはまる。 この証明は、Google社内で開発された完全に自動化されたジェミニベースのエージェントシステムを用いて最初に得られた。 著者らは証明を検証し、提示の明確さのために編集した。

関連論文リスト

• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee [12.89814955033651]
  ランダム化されたスケッチと解法アルゴリズムは、入力を小さな問題に置き換えることで、過剰に制約された$ell$レグレッションを加速する。 我々のスケッチは$ell_infty$ guarantee with $m=O(-2dlog d)$ rows, using one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is effective to apply。
  論文  参考訳（メタデータ） (2026-08-27T02:43:30Z)
• 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)
• The sharp SAT/UNSAT phase transition in random ellipsoid fitting [5.7652356955571085]
  エンフェレプソイド整合は行列 $S succeq 0$ であり、すべての$i$に対して$x_itop S x_i =d$ となる。 我々は、ソーンダーソン、パリロ、ウィルスキーの予想を証明し、$n,d を infty$ にすると、この半確定実現可能性問題は $n sim d2/4$ で急移行する。
  論文  参考訳（メタデータ） (2026-08-10T19:55:11Z)
• A Simple Algorithm for Best Separable State [5.5559749120901385]
  本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
  論文  参考訳（メタデータ） (2026-08-10T19:04:15Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits [8.86974002494041]
  線形包帯における$varepsilon$-best腕識別のミニマックスサンプル複雑性について検討した。 目標は、$langle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x であるようなarm $widehatxinmathcalX$を出力することである。
  論文  参考訳（メタデータ） (2026-05-15T06:35:31Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• 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)
• High-Dimensional Calibration from Swap Regret [40.9736612423411]
  任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。 我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
  論文  参考訳（メタデータ） (2025-05-27T17:31:47Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Optimal Strategies for Graph-Structured Bandits [0.0]
  Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
  論文  参考訳（メタデータ） (2020-07-07T06:27:51Z)

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

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