論文の概要: Hashing embeddings of optimal dimension, with applications to linear
least squares
- arxiv url: http://arxiv.org/abs/2105.11815v1
- Date: Tue, 25 May 2021 10:35:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-26 20:51:44.579560
- Title: Hashing embeddings of optimal dimension, with applications to linear
least squares
- Title（参考訳）: 最適次元のハッシュ埋め込みと線形最小二乗への応用
- Authors: Coralia Cartis, Jan Fiala and Zhen Shao
- Abstract要約: スケッチの射影次元$m$で最適である$sgeq 1$のスケッチ行列に対して、サブスペース埋め込み特性を提示する。
これらの結果をLinear Least Squares (LLS) の特殊なケースに適用し,これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発する。
- 参考スコア（独自算出の注目度）: 1.2891210250935143
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The aim of this paper is two-fold: firstly, to present subspace embedding
properties for $s$-hashing sketching matrices, with $s\geq 1$, that are optimal
in the projection dimension $m$ of the sketch, namely, $m=\mathcal{O}(d)$,
where $d$ is the dimension of the subspace. A diverse set of results are
presented that address the case when the input matrix has sufficiently low
coherence (thus removing the $\log^2 d$ factor dependence in $m$, in the
low-coherence result of Bourgain et al (2015) at the expense of a smaller
coherence requirement); how this coherence changes with the number $s$ of
column nonzeros (allowing a scaling of $\sqrt{s}$ of the coherence bound), or
is reduced through suitable transformations (when considering hashed -- instead
of subsampled -- coherence reducing transformations such as randomised
Hadamard). Secondly, we apply these general hashing sketching results to the
special case of Linear Least Squares (LLS), and develop Ski-LLS, a generic
software package for these problems, that builds upon and improves the
Blendenpik solver on dense input and the (sequential) LSRN performance on
sparse problems. In addition to the hashing sketching improvements, we add
suitable linear algebra tools for rank-deficient and for sparse problems that
lead Ski-LLS to outperform not only sketching-based routines on randomly
generated input, but also state of the art direct solver SPQR and iterative
code HSL on certain subsets of the sparse Florida matrix collection; namely, on
least squares problems that are significantly overdetermined, or moderately
sparse, or difficult.
- Abstract（参考訳）: 第一に、$s$-hashing スケッチ行列に対する部分空間埋め込み特性を$s\geq 1$ で提示することであり、これはスケッチの投影次元 $m$ において最適であり、すなわち $m=\mathcal{o}(d)$ であり、ここで $d$ は部分空間の次元である。
A diverse set of results are presented that address the case when the input matrix has sufficiently low coherence (thus removing the $\log^2 d$ factor dependence in $m$, in the low-coherence result of Bourgain et al (2015) at the expense of a smaller coherence requirement); how this coherence changes with the number $s$ of column nonzeros (allowing a scaling of $\sqrt{s}$ of the coherence bound), or is reduced through suitable transformations (when considering hashed -- instead of subsampled -- coherence reducing transformations such as randomised Hadamard).
第二に、これらの一般的なハッシュスケッチ結果をLinear Least Squares(LLS)の特殊なケースに適用し、これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発した。
ハッシュスケッチの改善に加えて,Ski-LLSがランダムに生成した入力に対してスケッチベースルーチンを上回り,スパースフロリダ行列コレクションの特定の部分集合上のアートダイレクトソルバSPQRおよび反復コードHSLの状態,すなわち,過度に決定された,あるいは適度にスパースされた,あるいは難しい問題に対して適切な線形代数ツールを追加する。
関連論文リスト
- Sparse Linear Regression and Lattice Problems [9.50127504736299]
格子問題の平均ケース硬度を仮定したSLRw.r.t.の全ての効率的なアルゴリズムの平均ケース硬度を示す。
具体的には,SLR に対する格子上の境界距離復号法 (BDD) 問題の変種からインスタンス・バイ・インスタンス・リダクションを与える。
論文 参考訳（メタデータ） (2024-02-22T15:45:27Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Optimal N-ary ECOC Matrices for Ensemble Classification [1.3561997774592662]
アンサンブル分類法における誤り訂正出力符号(ECOC)の新たな構成について述べる。
任意の素数$N$が与えられたとき、この決定論的構成は基底-$N$対称二乗行列を$M$で生成する。
論文 参考訳（メタデータ） (2021-10-05T16:50:15Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares [22.679160149512377]
多重右辺 (MNNLS) を持つ非負の最小二乗問題は、加法線形結合に依存するモデルに現れる。
本稿では,行列幅制約を用いたスパースMNNLSの新しい定式化を提案する。
提案した2段階の手法は,カラムワイドおよびグローバルの両方に適用された最先端のスパース符号よりも精度の高い結果が得られることを示す。
論文 参考訳（メタデータ） (2020-11-22T17:21:16Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。