論文の概要: PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear
regression via Majorization Minimization with an application to
semi-supervised graph learning
- arxiv url: http://arxiv.org/abs/2110.12190v1
- Date: Sat, 23 Oct 2021 10:19:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-31 22:09:54.190910
- Title: PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear
regression via Majorization Minimization with an application to
semi-supervised graph learning
- Title（参考訳）: PROMPT:算数最小化による$\ell_{p}=ノルム線形回帰の並列反復アルゴリズムと半教師付きグラフ学習への応用
- Authors: R.Jyothi and P.Babu
- Abstract要約: スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。
我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider the problem of $\ell_{p}$ norm linear regression,
which has several applications such as in sparse recovery, data clustering, and
semi-supervised learning. The problem, even though convex, does not enjoy a
closed-form solution. The state-of-the-art algorithms are iterative but suffer
from convergence issues, i.e., they either diverge for p>3 or the convergence
to the optimal solution is sensitive to the initialization of the algorithm.
Also, these algorithms are not generalizable to every possible value of $p$. In
this paper, we propose an iterative algorithm : Parallel IteRative AlgOrithM
for $\ell_{P}$ norm regression via MajorizaTion Minimization (PROMPT) based on
the principle of Majorization Minimization and prove that the proposed
algorithm is monotonic and converges to the optimal solution of the problem for
any value of $p$. The proposed algorithm can also parallelly update each
element of the regression variable, which helps to handle large scale data
efficiently, a common scenario in this era of data explosion. Subsequently, we
show that the proposed algorithm can also be applied for the graph based
semi-supervised learning problem. We show through numerical simulations that
the proposed algorithm converges to the optimal solution for any random
initialization and also performs better than the state-of-the-art algorithms in
terms of speed of convergence. We also evaluate the performance of the proposed
algorithm using simulated and real data for the graph based semi-supervised
learning problem.
- Abstract（参考訳）: 本稿では,スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用が可能な標準線形回帰法である$\ell_{p}$の問題を考察する。
凸であるにもかかわらず、問題は閉形式解を楽しまない。
最先端のアルゴリズムは反復的であるが、収束問題、すなわち、p>3で分岐するか、最適解への収束がアルゴリズムの初期化に敏感である。
また、これらのアルゴリズムは$p$の任意の値に対して一般化できない。
本稿では,数量化最小化の原理に基づく数量化最小化 (prompt) による$\ell_{p}$ノルム回帰のための並列反復アルゴリズムを提案し,提案アルゴリズムが単調であり,任意の値が$p$である問題の最適解に収束することを示す。
提案アルゴリズムは回帰変数の各要素を並列に更新することも可能であり、この時代のデータ爆発の一般的なシナリオである大規模データを効率的に処理するのに役立つ。
次に,提案アルゴリズムは,グラフに基づく半教師付き学習問題にも適用可能であることを示す。
数値シミュレーションにより,提案アルゴリズムは任意のランダム初期化に対して最適解に収束し,収束速度の点で最先端のアルゴリズムよりも優れていることを示す。
また,グラフに基づく半教師付き学習問題に対して,シミュレーションおよび実データを用いて提案アルゴリズムの性能を評価する。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。
我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文 参考訳（メタデータ） (2024-09-06T17:17:52Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Linear regression with partially mismatched data: local search with
theoretical guarantees [9.398989897176953]
本稿では,予測と応答のペアが部分的に一致しない線形回帰の重要な変種について検討する。
最適化定式化を用いて、基礎となる回帰係数とミスマッチに対応する置換を同時に学習する。
我々は,局所探索アルゴリズムが線形速度でほぼ最適解に収束することを証明した。
論文 参考訳（メタデータ） (2021-06-03T23:32:12Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。