論文の概要: Dynamic Least-Squares Regression
- arxiv url: http://arxiv.org/abs/2201.00228v1
- Date: Sat, 1 Jan 2022 18:36:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-04 15:15:21.263439
- Title: Dynamic Least-Squares Regression
- Title（参考訳）: 動的Last-Squares回帰
- Authors: Shunhua Jiang, Binghui Peng, Omri Weinstein
- Abstract要約: 大規模教師付き学習における一般的な課題は、モデルをスクラッチから再トレーニングすることなく、事前トレーニングされたモデルに新たなインクリメンタルデータを活用する方法である。
この問題により、動的最小二乗回帰(LSR)の正準問題を再考する。
このセットアップでは、mathbbRt times dtimes mathbbRt$におけるデータおよびラベル $(mathbfA(t), mathbfb(t)) がオンライン形式で進化する。
主な成果
- 参考スコア（独自算出の注目度）: 12.719327447589345
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A common challenge in large-scale supervised learning, is how to exploit new
incremental data to a pre-trained model, without re-training the model from
scratch. Motivated by this problem, we revisit the canonical problem of dynamic
least-squares regression (LSR), where the goal is to learn a linear model over
incremental training data. In this setup, data and labels $(\mathbf{A}^{(t)},
\mathbf{b}^{(t)}) \in \mathbb{R}^{t \times d}\times \mathbb{R}^t$ evolve in an
online fashion ($t\gg d$), and the goal is to efficiently maintain an
(approximate) solution to $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)}
\mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$. Our main result
is a dynamic data structure which maintains an arbitrarily small constant
approximate solution to dynamic LSR with amortized update time $O(d^{1+o(1)})$,
almost matching the running time of the static (sketching-based) solution. By
contrast, for exact (or even $1/\mathrm{poly}(n)$-accuracy) solutions, we show
a separation between the static and dynamic settings, namely, that dynamic LSR
requires $\Omega(d^{2-o(1)})$ amortized update time under the OMv Conjecture
(Henzinger et al., STOC'15). Our data structure is conceptually simple, easy to
implement, and fast both in theory and practice, as corroborated by experiments
over both synthetic and real-world datasets.
- Abstract（参考訳）: 大規模教師付き学習における一般的な課題は、モデルをスクラッチから再トレーニングすることなく、新しいインクリメンタルデータを事前トレーニングされたモデルに活用する方法である。
この問題に触発されて、我々は動的最小二乗回帰(LSR)の正準問題を再考し、漸進的なトレーニングデータよりも線形モデルを学習することを目指す。
このセットアップでは、データとラベルが$(\mathbf{A}^{(t)}, \mathbf{b}^{(t)}) \in \mathbb{R}^{t \times d}\times \mathbb{R}^t$をオンラインのやり方で進化させ、その目標は、$\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)} \mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$に対して効率的に(近似)ソリューションを維持することである。
我々の主な成果は動的データ構造であり、動的LSRに対する任意に小さな定値近似解を保留時間$O(d^{1+o(1)})$で維持し、静的(スケッチベース)ソリューションの実行時間とほぼ一致する。
対照的に、正確な(あるいは1/\mathrm{poly}(n)$-accuracy)ソリューションの場合、静的設定と動的設定の分離、すなわち、動的LSRはOMv Conjecture (Henzinger et al., STOC'15)の下での償却更新時間($\Omega(d^{2-o(1)})$)を必要とすることを示す。
私たちのデータ構造は概念的にはシンプルで、実装が容易で、理論と実践の両方において高速です。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。