論文の概要: A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data

• arxiv url: http://arxiv.org/abs/2203.03808v1
• Date: Tue, 8 Mar 2022 02:02:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-10 02:08:56.466845
• Title: A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data
• Title（参考訳）: 非負データをもつ非負極角に対する高速スケール不変アルゴリズム
• Authors: Jelena Diakonikolas, Chenghui Li, Swati Padmanabhan, Chaobing Song
• Abstract要約: 我々は、データ自体が非負であることを示し、この場合の非負性は問題を容易にすることを示した。 特に、制約のない最小二乗問題のオラクルの複雑さは、データ行列定数の1つで必ずスケールするが、非負のデータを含む非負の最小二乗問題は乗法誤差に解けることを示す。
• 参考スコア（独自算出の注目度）: 18.81091632124107
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nonnegative (linear) least square problems are a fundamental class of problems that is well-studied in statistical learning and for which solvers have been implemented in many of the standard programming languages used within the machine learning community. The existing off-the-shelf solvers view the non-negativity constraint in these problems as an obstacle and, compared to unconstrained least squares, perform additional effort to address it. However, in many of the typical applications, the data itself is nonnegative as well, and we show that the nonnegativity in this case makes the problem easier. In particular, while the oracle complexity of unconstrained least squares problems necessarily scales with one of the data matrix constants (typically the spectral norm) and these problems are solved to additive error, we show that nonnegative least squares problems with nonnegative data are solvable to multiplicative error and with complexity that is independent of any matrix constants. The algorithm we introduce is accelerated and based on a primal-dual perspective. We further show how to provably obtain linear convergence using adaptive restart coupled with our method and demonstrate its effectiveness on large-scale data via numerical experiments.
• Abstract（参考訳）: 非負(線形)最小二乗問題(non negative (linear) least square problem)は、統計学習においてよく研究され、機械学習コミュニティで使われている標準プログラミング言語の多くで解法が実装されている問題の基本的なクラスである。 既存のオフ・ザ・シェルフ・ソルバは、これらの問題の非ネガティビティ制約を障害とみなし、制約のない最小二乗と比較して、それに対処する追加の努力を行う。 しかし、一般的なアプリケーションの多くでは、データ自体も非負であり、この場合の非負性が問題を容易にすることを示している。 特に、制約のない最小二乗問題のオラクルの複雑性は、データ行列定数の1つ(典型的にはスペクトルノルム)で必ずスケールし、これらの問題は加法誤差に解決されるが、非負のデータの非負の最小二乗問題は乗算誤差や任意の行列定数とは独立な複雑性に対して解けることを示す。 私たちが導入するアルゴリズムは、原始双対の視点に基づいて加速される。 さらに,本手法と組み合わされた適応再スタートによる線形収束を実現する方法を示し,数値実験による大規模データに対する有効性を示す。

関連論文リスト

• Learning to sample fibers for goodness-of-fit testing [0.0]
  離散指数族モデルに対する完全適合性テストを構築することの問題点を考察する。 この問題をマルコフ決定プロセスに変換し、サンプリングのための「よい動きを学ぶための強化学習アプローチ」を示す。 提案アルゴリズムは,評価可能な収束性を持つアクタ・クリティカル・サンプリング方式に基づいている。
  論文  参考訳（メタデータ） (2024-05-22T19:33:58Z)
• Paired Autoencoders for Inverse Problems [3.355436702348694]
  前方問題は偏微分方程式の離散化である非線形逆問題の解を考える。 典型的なアルゴリズムの主な計算ボトルネックは、データ不適合性の直接推定である。 逆問題に対する確率自由度推定器として,ペアオートエンコーダフレームワークを用いる。
  論文  参考訳（メタデータ） (2024-05-21T22:00:34Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems [0.0]
  本稿では,大規模線形制約付きスパース群正方根ラッソ問題の数値計算に着目する。 本稿では,2つの半平板ニュートン(SSN)をベースとした拡張ラグランジアン法(ALM)を提案する。 数値実験により提案アルゴリズムの有効性が示された。
  論文  参考訳（メタデータ） (2021-11-27T12:20:43Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。 本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。 他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。 驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
  論文  参考訳（メタデータ） (2021-10-21T07:28:11Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares [22.679160149512377]
  多重右辺 (MNNLS) を持つ非負の最小二乗問題は、加法線形結合に依存するモデルに現れる。 本稿では,行列幅制約を用いたスパースMNNLSの新しい定式化を提案する。 提案した2段階の手法は,カラムワイドおよびグローバルの両方に適用された最先端のスパース符号よりも精度の高い結果が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-22T17:21:16Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Consistency analysis of bilevel data-driven learning in inverse problems [1.0705399532413618]
  本稿では,データからの正規化パラメータの適応学習を最適化により検討する。 線形逆問題に対する我々のフレームワークの実装方法を示す。 勾配降下法を用いてオンライン数値スキームを導出する。
  論文  参考訳（メタデータ） (2020-07-06T12:23:29Z)

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

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