Fugu-MT 論文翻訳(概要): A Resolution of the SS--RS--GD Inequalities

論文の概要: A Resolution of the SS--RS--GD Inequalities

arxiv url: http://arxiv.org/abs/2607.22620v1
Date: Tue, 16 Jun 2026 16:17:42 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-02 22:55:38.988737
Title: A Resolution of the SS--RS--GD Inequalities
Title（参考訳）: SS--RS--GD不等式の解法
Abstract要約: 証明は著者によって拡張された GPT-5.5 Pro を通じて発見された。予想は解決され、$bullet$ SS-RS 不等式は失敗する。 $bigl (1-frac14n2+1bigr) Ipreceq A_ipreceq I$ を持つすべての対称 $A_i$ に対して、$|W_rs|le|W_gd|$ を持つ。
参考スコア（独自算出の注目度）: 9.373325778575127
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Yun, Sra, and Jadbabaie (COLT 2021, open question) conjectured the SS--RS--GD inequalities: for well-conditioned symmetric matrices $A_1,\dots,A_n$, the operators $W_{ss}$, $W_{rs}$, and $W_{gd}$ that encode the expected iterate of single-shuffle SGD, random-reshuffle SGD, and gradient descent on a quadratic finite sum should satisfy \[ \|W_{ss}\|\le \| W_{rs}\|\le \|W_{gd}\|. \] The conjecture is resolved, $\bullet$ SS-RS inequality fails. Already for $n=3$, $K=2$, and $d=4$, we exhibit explicit PSD matrices whose condition number is arbitrarily close to $1$, yet $\|W_{ss}\|>\|W_{rs}\|$. $\bullet$ RS-GD inequality holds. For every symmetric $A_i$ with $\bigl(1-\frac1{4n^2+1}\bigr)I\preceq A_i\preceq I$, one has $\|W_{rs}\|\le\|W_{gd}\|$. The proof was found via GPT-5.5 Pro extended prompted by the author.
Abstract（参考訳）: Yun, Sra, and Jadbabaie (COLT 2021, open question) は、SS--RS-GDの不等式を予想した: 十分に条件付けられた対称行列に対して、$A_1,\dots,A_n$, the operator $W_{ss}$, $W_{rs}$, $W_{gd}$, $W_{gd}$ は、単一シャッフル SGD, ランダムリシャッフル SGD の予想イテレートを符号化し、二次有限和上の勾配勾配は \[ \|W_{s}\|\le \|W_{rs}\|\le \|W_{gd}\| を満たす。この予想は解決され、$\bullet$ SS-RS 不等式は失敗する。既に$n=3$, $K=2$, $d=4$に対して、条件数が任意に$$, $\|W_{ss}\|>\|W_{rs}\|$に近づく明示的なPSD行列を示す。 $\bullet$ RS-GDの不等式は成立する。すべての対称 $A_i$ に対して $\bigl(1-\frac1{4n^2+1}\bigr)I\preceq A_i\preceq I$ は $\|W_{rs}\|\le\|W_{gd}\|$ を持つ。証明は著者によって拡張された GPT-5.5 Pro で発見された。

関連論文リスト

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)
A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results [1.8051706864605614]
唐と張はすべての有限$p>1$に対して明示的な公式を予想した。 2leq pinfty$ のとき、最も1つの和のランクのすべての族に対して、予想されるシャープな境界が証明される。
論文参考訳（メタデータ） (2026-08-16T06:10:33Z)
The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文参考訳（メタデータ） (2026-08-03T17:57:01Z)
On the convergence of graph Laplacians with a symmetric divergence [0.0]
測地線距離 $d_g$ の鍵推定は、$0 leq d_g(p, q)2 - |p-q|2 leq K d_g(p, q)4$ であるような$K > 0$ が存在することである。これは、$D$で構築されたグラフラプラシアンの点収束に十分であることを示すとともに、確率測度パラの族上のシンクホーン発散によって$D$が与えられる例について議論する。
論文参考訳（メタデータ） (2026-07-07T06:41:21Z)
Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
論文参考訳（メタデータ） (2026-05-22T12:22:20Z)
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
我々は、$ell_p$ norm(mathsfSVP_p$)およびUnique-SVP(mathsfuSVP_p$)における最短ベクトル問題に対する近似結果の決定的困難性を確立する。すべての$p > 2$に対して、定数比硬さを証明します: no-time algorithm almosts $mathsfSVP_p$ or $mathsfuSVP_p$ in a ratio of $sqrt2 - o(1)$。
論文参考訳（メタデータ） (2025-10-19T20:17:26Z)
Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文参考訳（メタデータ） (2025-09-15T14:26:11Z)
Non-representable quantum measures [55.2480439325792]
次数-$d$測度 a $sigma$-algebra $mathcalAsubseteq 2X$ over a set $X$ は弱加法的型条件の階層の1つを満たす測度の一般化である。署名されたすべてのpoly measure $lambda$ on $(X,mathcalA)d$は、その対角的な$widetildelambda(A):=lambda(A,cdots,A)$としてグレード$d$測度を生成する。
論文参考訳（メタデータ） (2025-08-20T00:47:24Z)
PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文参考訳（メタデータ） (2022-02-10T23:44:09Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
On the continuous Zauner conjecture [0.0]
本稿では, [-frac1d2-1, frac1d+1] setminus0$ the equality $textebr(Phi_t)=d2$ is equivalent to a pair of a informationally complete unit norm tight frames。
論文参考訳（メタデータ） (2021-12-11T00:14:35Z)
The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文参考訳（メタデータ） (2021-03-17T00:59:33Z)

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