Fugu-MT 論文翻訳(概要): Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan

論文の概要: Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan

arxiv url: http://arxiv.org/abs/2408.05431v1
Date: Sat, 10 Aug 2024 04:26:19 GMT
ステータス: 処理完了
システム内更新日: 2024-08-13 19:01:07.724072
Title: Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
Title（参考訳）: Gauss-JordanによるRanc-1テンソル完了の簡易かつほぼ最適サンプリング
Authors: Alejandro Gomez-Leos, Oscar López,
Abstract要約: ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
参考スコア（独自算出の注目度）: 49.1574468325115
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We revisit the sample and computational complexity of completing a rank-1 tensor in $\otimes_{i=1}^{N} \mathbb{R}^{d}$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N = \Theta(1)$, we prove it uses no more than $m = O(d^2 \log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $\Omega(d\log d)$ samples. By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} \mu^{\Omega(1)} \log^{\Omega(1)} d$, where $\mu$ can be $\Theta(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms.
Abstract（参考訳）: ランク1テンソルを$\otimes_{i=1}^{N} \mathbb{R}^{d}$で完備する際のサンプルと計算の複雑さを再考する。一対のランダム線形系上でガウス・ヨルダンに等しいアルゴリズムを許容する問題(すなわち、ゼロでないエントリ)の特徴づけを示す。例えば、$N = \Theta(1)$の場合、$m = O(d^2 \log d)$サンプルを使用せず、$O(md^2)$時間で実行されることを証明します。さらに、任意のアルゴリズムが$\Omega(d\log d)$サンプルを必要とすることを示す。対照的に、サンプル複雑性の既存の上限は少なくとも$d^{1.5} \mu^{\Omega(1)} \log^{\Omega(1)} d$であり、最悪の場合$\mu$は$\Theta(d)$である。以前の研究では、この問題の上位バージョンではこれらの緩い保証が得られ、より複雑なアルゴリズムが伴う傾向にあった。

関連論文リスト

A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文参考訳（メタデータ） (2024-03-07T18:23:51Z)
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文参考訳（メタデータ） (2023-09-25T09:50:15Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Gaussian Mean Testing Made Simple [46.03021473600576]
a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-10-25T01:59:13Z)
Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文参考訳（メタデータ） (2022-09-09T23:35:25Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文参考訳（メタデータ） (2020-11-22T01:22:37Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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