論文の概要: The Complexity of Dynamic Least-Squares Regression
- arxiv url: http://arxiv.org/abs/2201.00228v2
- Date: Thu, 6 Apr 2023 15:06:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 18:32:53.190628
- Title: The Complexity of Dynamic Least-Squares Regression
- Title（参考訳）: 動的最小二乗回帰の複雑性
- Authors: Shunhua Jiang, Binghui Peng, Omri Weinstein
- Abstract要約: 動的最小二乗回帰の複雑さ。
ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
- 参考スコア（独自算出の注目度）: 11.815510373329337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We settle the complexity of dynamic least-squares regression (LSR), where
rows and labels $(\mathbf{A}^{(t)}, \mathbf{b}^{(t)})$ can be adaptively
inserted and/or deleted, and the goal is to efficiently maintain an
$\epsilon$-approximate solution to $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)}
\mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$. We prove sharp
separations ($d^{2-o(1)}$ vs. $\sim d$) between the amortized update time of:
(i) Fully vs. Partially dynamic $0.01$-LSR; (ii) High vs. low-accuracy LSR in
the partially-dynamic (insertion-only) setting.
Our lower bounds follow from a gap-amplification reduction -- reminiscent of
iterative refinement -- rom the exact version of the Online Matrix Vector
Conjecture (OMv) [HKNS15], to constant approximate OMv over the reals, where
the $i$-th online product $\mathbf{H}\mathbf{v}^{(i)}$ only needs to be
computed to $0.1$-relative error. All previous fine-grained reductions from OMv
to its approximate versions only show hardness for inverse polynomial
approximation $\epsilon = n^{-\omega(1)}$ (additive or multiplicative) . This
result is of independent interest in fine-grained complexity and for the
investigation of the OMv Conjecture, which is still widely open.
- Abstract（参考訳）: 行とラベルの$(\mathbf{A}^{(t)}, \mathbf{b}^{(t)})$を適応的に挿入および/または削除することが可能であり、目標は、$\epsilon$-approximate Solution to $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)} \mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$に対して効率よく$\epsilon$-approximate Solutionを維持することである。
償却更新時間の間のシャープな分離(d^{2-o(1)}$ vs. $\sim d$)を証明します。
(i)完全対部分動的$0.01$-LSR
(II)部分力学(挿入のみ)設定における高対低精度LSR
我々の下限はギャップ増幅の削減 -- 反復的洗練を想起させる -- Online Matrix Vector Conjecture (OMv) [HKNS15] の正確なバージョンをロームし、実数に対して一定に近似した OMv となり、$i$-thオンライン製品 $\mathbf{H}\mathbf{v}^{
(i)}$は0.1$-relativeエラーにのみ計算する必要がある。
以前の OMv から近似バージョンへの還元は、逆多項式近似 $\epsilon = n^{-\omega(1)}$ (加法的あるいは乗法的) に対してのみ硬さを示す。
この結果は、微細な複雑さと、まだ広く開いている OMv Conjecture の研究に、独立した関心を持っている。
関連論文リスト
- A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
Lipschitz-of-$nabla f$
$mathcalS_k|p$。
$mathcalS_k|p$。
$nabla f$.
$mathcalS_k|p$。
論文 参考訳（メタデータ） (2024-09-28T18:16:32Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - 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) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - On the Complexity of Dynamic Submodular Maximization [15.406670088500087]
濃度制約の下で$(0.5+epsilon)$-approximateを維持できるアルゴリズムは、任意の定数$epsilon>0$に対して、$mathitpolynomial$ in $n$というアモータイズされたクエリ複雑性を持つ必要がある。
これは、(0.5-epsilon)$-approximation with a $mathsfpolylog(n)$ amortized query complexityを達成している[LMNF+20, Mon20]の最近の動的アルゴリズムとは対照的である。
論文 参考訳（メタデータ） (2021-11-05T00:04:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。