論文の概要: Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model

• arxiv url: http://arxiv.org/abs/2606.20082v1
• Date: Thu, 18 Jun 2026 11:00:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:39.807693
• Title: Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
• Title（参考訳）: John Ellipsoid Approximation: Leverage-Scoreモデルにおける高精度アルゴリズム
• Authors: Xiaoyu Li, Junwei Yu, Jiaojiao Jiang, Junbin Gao, Andi Han,
• Abstract要約: 対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
• 参考スコア（独自算出の注目度）: 37.35522173770848
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The John ellipsoid of a symmetric polytope $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$, $\mathbf{A}\in\mathbb{R}^{n\times d}$, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a $(1+\varepsilon)$-approximation in $Θ(\varepsilon^{-1}\log(n/d))$ iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical $\varepsilon^{-1}$ in the first alone. In the equivalent D-optimal-design form $\min_{\mathbf{p}\inΔ_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)$, the leverage-score oracle is exactly the first-order oracle and the $(1+\varepsilon)$-John guarantee the Frank-Wolfe gap $g(\mathbf{p})\le\varepsilon d$; through this dictionary the costs come apart. The $\varepsilon^{-1}$ is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly $Θ(1/T)$, however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in $C(\mathbf{A})+O(\sqrtκ\log(1/\varepsilon))$ queries after an $\varepsilon$-independent setup $C(\mathbf{A})$, and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only $O(\log\log(1/\varepsilon))$ steps, for a total of $C(\mathbf{A})+O(d^2\log\log(1/\varepsilon))$ queries. The accuracy dependence is thus doubly logarithmic after an $\varepsilon$-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.
• Abstract（参考訳）: 対称ポリトープ $P=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{A}\mathbf{x}\|_\infty\le1\}$, $\mathbf{A}\in\mathbb{R}^{n\times d}$ のジョン楕円体は、Cohen, Cousins, Lee and Yang (COLT 2019) からその後継 (WY24, CLS+25] までの長いレバレッジスコアアルゴリズムによって計算される。 我々はこの複雑さを3つのコストに分けて、現代のラインの膨らみ(認証、識別、精度)を犠牲にし、最初だけで歴史的な$\varepsilon^{-1}$を見つける。 等価な D-最適設計形式 $\min_{\mathbf{p}\inΔ_n}-\log\det(\sum_i p_i\mathbf{a}_i\mathbf{a}_i^\top)$ では、レバレッジスコアオラクルはちょうど一階のオラクルであり、$(1+\varepsilon)$-John はフランク=ウルフギャップ $g(\mathbf{p})\le\varepsilon d$ を保証している。 $\varepsilon^{-1}$は認定アーティファクトであり、各イテレーションの均一な平均は、ライン全体で使用される証明書であり、ちょうど$1/T)$のギャップがあるが、各イテレーションは安価である。 ウォームスタートされたアクセラレーションされたメソッドは、$C(\mathbf{A})+O(\sqrtκ\log(1/\varepsilon))$ query after a $\varepsilon$-independent setup $C(\mathbf{A})$, そして最適な顔が特定されたら、ヘシアンのオラクルが正確に回復する非制約の自己調和最小化であるので、ダンプされたニュートンは$O(\log\log(1/\varepsilon))$ steps, for a total of $C(\mathbf{A})+O(\2\log(1/\varepsilon)$ でのみ必要である。 したがって、精度依存は$\varepsilon$-independent、条件依存のセットアップの後に二重対数となる。 正確さは障害ではない。

関連論文リスト

• Deterministic Coreset for Lp Subspace [10.070877057133004]
  本稿では,決定論的$ell_p$サブスペース埋め込みを保証する$varepsilon$-coresetを構築するための最初の反復アルゴリズムを紹介する。 各イテレーションにおいて、アルゴリズムは、保守されたセットの損失が元のデータセットの損失によって上と下の境界であることを保証する。 我々のコアセットは $ell_p$ 回帰問題を決定論的に解くのにも使える。
  論文  参考訳（メタデータ） (2026-01-01T14:31:16Z)
• 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)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Fast swap regret minimization and applications to approximate correlated equilibria [20.047624953965965]
  任意の定数$varepsilon>0$に対して、我々のアルゴリズムは$varepsilon T$-swap regretを$T = Mathsfpolylog(n)$ roundsで取得する。 我々のアルゴリズムは$varepsilon$に指数関数的依存を持つが、我々は一致する新しい下界を証明している。
  論文  参考訳（メタデータ） (2023-10-30T15:35:24Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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