論文の概要: Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations
- arxiv url: http://arxiv.org/abs/2405.00837v1
- Date: Wed, 1 May 2024 19:56:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 20:32:52.675499
- Title: Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations
- Title（参考訳）: 局所性正規化再建 : 構造的疎度とDlaunay三角測量
- Authors: Marshall Mueller, James M. Murphy, Abiy Tasissa,
- Abstract要約: 線形表現学習は、その概念的単純さと、圧縮、分類、特徴抽出といったタスクにおける経験的有用性から、広く研究されている。
本研究では、正則化最小二乗回帰問題を解くことにより、$mathbfy$の局所再構成を形成する$mathbfw$を求める。
すべてのレベルの正則化と、$mathbfX$ の列が独自のデラウネー三角形を持つという穏やかな条件の下では、最適係数の非零成分の数は$d+1$ で上界となることを証明している。
- 参考スコア（独自算出の注目度）: 7.148312060227714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear representation learning is widely studied due to its conceptual simplicity and empirical utility in tasks such as compression, classification, and feature extraction. Given a set of points $[\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n] = \mathbf{X} \in \mathbb{R}^{d \times n}$ and a vector $\mathbf{y} \in \mathbb{R}^d$, the goal is to find coefficients $\mathbf{w} \in \mathbb{R}^n$ so that $\mathbf{X} \mathbf{w} \approx \mathbf{y}$, subject to some desired structure on $\mathbf{w}$. In this work we seek $\mathbf{w}$ that forms a local reconstruction of $\mathbf{y}$ by solving a regularized least squares regression problem. We obtain local solutions through a locality function that promotes the use of columns of $\mathbf{X}$ that are close to $\mathbf{y}$ when used as a regularization term. We prove that, for all levels of regularization and under a mild condition that the columns of $\mathbf{X}$ have a unique Delaunay triangulation, the optimal coefficients' number of non-zero entries is upper bounded by $d+1$, thereby providing local sparse solutions when $d \ll n$. Under the same condition we also show that for any $\mathbf{y}$ contained in the convex hull of $\mathbf{X}$ there exists a regime of regularization parameter such that the optimal coefficients are supported on the vertices of the Delaunay simplex containing $\mathbf{y}$. This provides an interpretation of the sparsity as having structure obtained implicitly from the Delaunay triangulation of $\mathbf{X}$. We demonstrate that our locality regularized problem can be solved in comparable time to other methods that identify the containing Delaunay simplex.
- Abstract（参考訳）: 線形表現学習は、その概念的単純さと、圧縮、分類、特徴抽出といったタスクにおける経験的有用性から、広く研究されている。
一組の点 $[\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n] = \mathbf{X} \in \mathbb{R}^{d \times n}$ とベクトル $\mathbf{y} \in \mathbb{R}^d$ が与えられたとき、目標は係数 $\mathbf{w} \in \mathbb{R}^n$ を見つけることである。
この研究において、正規化された最小二乗回帰問題を解くことにより、$\mathbf{w}$ の局所的再構成を形成する $\mathbf{y}$ を求める。
正規化項として使われるとき、$\mathbf{X}$ の列が $\mathbf{y}$ に近いような局所関数を通して局所解を得る。
すべてのレベルの正規化と、$\mathbf{X}$ の列が独自のデラウネー三角形を持つという穏やかな条件の下では、最適係数の非零成分の数は$d+1$ で上界し、$d \ll n$ のとき局所スパース解を与える。
同じ条件の下では、$\mathbf{y}$ の凸包に含まれる任意の $\mathbf{y}$ に対して、$\mathbf{X}$ を含むデラウネー単純体の頂点上で最適係数が支持されるような正規化パラメータの規則が存在することも示している。
これは、空間性は、$\mathbf{X}$のデラウネー三角形から暗黙的に得られる構造である、という解釈を与える。
我々の局所性正規化問題は、デラウネーの単純度を含む他の方法と同等の時間で解決できることを実証する。
関連論文リスト
- Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-11-11T03:43:52Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Compressing Large Language Models using Low Rank and Low Precision Decomposition [46.30918750022739]
この研究は、新しい訓練後のLLM圧縮アルゴリズムである$rm CALDERA$を導入している。
重量行列 $mathbfW$ の固有の低ランク構造を利用して、低ランクで低精度な分解によってそれを近似する。
その結果、LlaMa-$2$$7$B/$13B$/$70$BとLlaMa-$3$B $rm CALDERA$は、既存のトレーニング後の圧縮技術より優れていることが示された。
論文 参考訳（メタデータ） (2024-05-29T08:42:30Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Fast Partition-Based Cross-Validation With Centering and Scaling for $\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$ [0.0]
機械学習モデルの分割に基づくクロスバリデーションを大幅に高速化するアルゴリズムを提案する。
我々のアルゴリズムは、例えば、主成分分析(PCA)、主成分回帰(PCR)、隆起回帰(RR)、通常最小二乗(OLS)、部分最小二乗(PLS)のモデル選択に応用できる。
文献に見られる代替手段とは異なり、前処理によるデータの漏洩を避ける。
論文 参考訳（メタデータ） (2024-01-24T02:16:03Z) - Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する
私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。
我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
論文 参考訳（メタデータ） (2024-01-08T10:55:41Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - 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) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。