論文の概要: Sparse Mixed Linear Regression with Guarantees: Taming an Intractable
Problem with Invex Relaxation
- arxiv url: http://arxiv.org/abs/2206.01167v1
- Date: Thu, 2 Jun 2022 17:38:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-03 13:55:25.693596
- Title: Sparse Mixed Linear Regression with Guarantees: Taming an Intractable
Problem with Invex Relaxation
- Title（参考訳）: Sparse Mixed Linear Regression with Guarantees: Taming a Invex Relaxation with Intractable Problem with Invex Relaxation
- Authors: Adarsh Barik, Jean Honorio
- Abstract要約: 本稿では,ラベルのないデータセット上での疎混合線形回帰問題について検討する。
我々は、この難解な問題に対して、証明可能な理論的保証を持つ解をもたらす新しい凸緩和を提供する。
- 参考スコア（独自算出の注目度）: 31.061339148448006
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of sparse mixed linear regression on an
unlabeled dataset that is generated from linear measurements from two different
regression parameter vectors. Since the data is unlabeled, our task is not only
to figure out a good approximation of the regression parameter vectors but also
to label the dataset correctly. In its original form, this problem is NP-hard.
The most popular algorithms to solve this problem (such as
Expectation-Maximization) have a tendency to stuck at local minima. We provide
a novel invex relaxation for this intractable problem which leads to a solution
with provable theoretical guarantees. This relaxation enables exact recovery of
data labels. Furthermore, we recover a close approximation of the regression
parameter vectors which match the true parameter vectors in support and sign.
Our formulation uses a carefully constructed primal dual witnesses framework
for the invex problem. Furthermore, we show that the sample complexity of our
method is only logarithmic in terms of the dimension of the regression
parameter vectors.
- Abstract（参考訳）: 本稿では,2つの異なる回帰パラメータベクトルから線形測定から得られるラベルなしデータセット上での疎混合線形回帰の問題について検討する。
データはラベル付けされていないので,回帰パラメータベクトルの近似値を求めるだけでなく,データセットを正しくラベル付けすることが課題である。
元々の形式では、この問題はNPハードである。
この問題を解決する最も一般的なアルゴリズム(期待最大化など)は、局所的な最小化に固執する傾向がある。
我々は、この難解な問題に対して、証明可能な理論的保証を持つ解をもたらす新しい凸緩和を提供する。
この緩和により、データラベルの正確な回復が可能になる。
さらに,支持と符号の真のパラメータベクトルと一致する回帰パラメータベクトルの近似を復元する。
我々の定式化はinvex問題に対して注意深く構築された原始双対証人の枠組みを用いている。
さらに,本手法のサンプル複雑性は回帰パラメータベクトルの次元についてのみ対数的であることを示した。
関連論文リスト
- Shuffled linear regression through graduated convex relaxation [12.614901374282868]
シャッフル線形回帰問題は、入力と出力の対応が不明なデータセットにおける線形関係を復元することを目的としている。
この問題は、調査データを含む広範囲のアプリケーションで発生する。
後最大化目的関数に基づく線形回帰をシャッフルする新しい最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-30T17:33:48Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。
得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
論文 参考訳（メタデータ） (2021-05-21T14:26:28Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Fair Sparse Regression with Clustering: An Invex Relaxation for a
Combinatorial Problem [32.18449686637963]
我々のモデルにデバイアス/フェアネス制約を組み込むことは、性能に悪影響を及ぼさないことを示す。
また,各サンプルの隠れ属性の正確な値を復元することで,クラスタリング問題を解決する。
論文 参考訳（メタデータ） (2021-02-19T01:46:34Z) - A Hypergradient Approach to Robust Regression without Correspondence [85.49775273716503]
本稿では,入力データと出力データとの対応が不十分な回帰問題について考察する。
ほとんどの既存手法はサンプルサイズが小さい場合にのみ適用できる。
シャッフル回帰問題に対する新しい計算フレームワークであるROBOTを提案する。
論文 参考訳（メタデータ） (2020-11-30T21:47:38Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳（メタデータ） (2020-07-12T19:33:50Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Optimal Feature Manipulation Attacks Against Linear Regression [64.54500628124511]
本稿では,データセットに慎重に設計した有害なデータポイントを付加したり,元のデータポイントを修正したりすることで,線形回帰による係数の操作方法について検討する。
エネルギー予算を考慮し, 目標が指定された回帰係数を1つ変更する場合に, 最適毒素データ点の閉形式解をまず提示する。
次に、攻撃者が1つの特定の回帰係数を変更しつつ、他をできるだけ小さく変更することを目的とした、より困難なシナリオに分析を拡張します。
論文 参考訳（メタデータ） (2020-02-29T04:26:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。