論文の概要: A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition

• arxiv url: http://arxiv.org/abs/2508.06693v1
• Date: Fri, 08 Aug 2025 20:34:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.512225
• Title: A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
• Title（参考訳）: 高次特異値分解の近似保証のための高次下界
• Authors: Matthew Fahrbach, Mehrdad Ghadiri,
• Abstract要約: 我々は、高階特異値分解(HOSVD)の古典的な近似保証がきついことを証明した。 また、Vannieuwenhoven et al. (2012) の ST-HOSVD アルゴリズムと、De Lathauwer et al. (2000b) の高階直交反復 (HOOI) が厳密であることを示す。
• 参考スコア（独自算出の注目度）: 5.724311218570011
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the classic approximation guarantee for the higher-order singular value decomposition (HOSVD) is tight by constructing a tensor for which HOSVD achieves an approximation ratio of $N/(1+\varepsilon)$, for any $\varepsilon > 0$. This matches the upper bound of De Lathauwer et al. (2000a) and shows that the approximation ratio of HOSVD cannot be improved. Using a more advanced construction, we also prove that the approximation guarantees for the ST-HOSVD algorithm of Vannieuwenhoven et al. (2012) and higher-order orthogonal iteration (HOOI) of De Lathauwer et al. (2000b) are tight by showing that they can achieve their worst-case approximation ratio of $N / (1 + \varepsilon)$, for any $\varepsilon > 0$.
• Abstract（参考訳）: 我々は、高階特異値分解(HOSVD)に対する古典的な近似保証が、任意の$\varepsilon > 0$に対して、HOSVDが$N/(1+\varepsilon)$の近似比を達成できるテンソルを構築することにより、密であることを示す。 これはDe Lathauwer et al (2000a)の上限値と一致し、HOSVDの近似比は改善できないことを示す。 より高度な構成を用いて、Vannieuwenhoven et al (2012) の ST-HOSVD アルゴリズムと、De Lathauwer et al (2000b) の高階直交反復 (HOOI) に対する近似保証が、任意の$\varepsilon > 0$ に対して、最悪の場合の近似比 (N / (1 + \varepsilon)$) を達成できることを証明している。

関連論文リスト

• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond [15.871535287520393]
  本稿では,バンディットの腕識別のための新しいサンプリングルールであるEB-TC$varepsilon$を提案する。 EB-TC$varepsilon$に対して3種類の理論的保証を提供する。 EB-TC$varepsilon$が既存のアルゴリズムと比較して好適に動作することを示す。
  論文  参考訳（メタデータ） (2023-05-25T13:19:11Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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