Fugu-MT 論文翻訳(概要): Towards an efficient approach for the nonconvex $\ell_p$ ball projection: algorithm and analysis

論文の概要: Towards an efficient approach for the nonconvex $\ell_p$ ball projection: algorithm and analysis

arxiv url: http://arxiv.org/abs/2101.01350v2
Date: Mon, 22 Feb 2021 12:33:46 GMT
ステータス: 処理完了
システム内更新日: 2021-04-11 11:27:40.619670
Title: Towards an efficient approach for the nonconvex $\ell_p$ ball projection: algorithm and analysis
Title（参考訳）: 非凸$\ell_p$ボール射影に対する効率的なアプローチ:アルゴリズムと解析
Authors: Xiangyu Yang, Jiashan Wang, and Hao Wang
Abstract要約: 本稿では, ベクトルのユークリッド射影を $pin(0,1)$ の $ell_p$ 球上に計算することに着目した。我々は、再重み付けされた $ell_1$-ball 上の射影列を解いて定常点を計算する新しい数値的手法を開発した。提案手法は穏やかな条件下で一意に収束し,最悪の場合$o(1/sqrtk)$収束率を持つ。
参考スコア（独自算出の注目度）: 3.4693390973571594
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper primarily focuses on computing the Euclidean projection of a vector onto the $\ell_{p}$ ball in which $p\in(0,1)$. Such a problem emerges as the core building block in statistical machine learning and signal processing tasks because of its ability to promote sparsity. However, efficient numerical algorithms for finding the projections are still not available, particularly in large-scale optimization. To meet this challenge, we first derive the first-order necessary optimality conditions of this problem using Fr\'echet normal cone. Based on this characterization, we develop a novel numerical approach for computing the stationary point through solving a sequence of projections onto the reweighted $\ell_{1}$-balls. This method is practically simple to implement and computationally efficient. Moreover, the proposed algorithm is shown to converge uniquely under mild conditions and has a worst-case $O(1/\sqrt{k})$ convergence rate. Numerical experiments demonstrate the efficiency of our proposed algorithm.
Abstract（参考訳）: 本稿では、主にベクトルのユークリッド射影を $p\in(0,1)$ の $\ell_{p}$ 球上に計算することに焦点を当てる。このような問題は、統計的な機械学習と信号処理タスクの核となる構成要素として現れる。しかし、特に大規模最適化では、射影を見つけるための効率的な数値アルゴリズムはまだ利用できない。この課題に対処するために、まずFr'echet normal coneを用いて、この問題の1次必要最適条件を導出する。この特性に基づいて,再重み付けされた$\ell_{1}$-balls 上の射影列を解いて定常点を計算する新しい数値的手法を開発した。この手法は実装が簡単で計算効率が良い。さらに,提案手法は穏やかな条件下で一意に収束し,最悪の場合$o(1/\sqrt{k})$収束率を持つことを示した。数値実験により提案アルゴリズムの有効性が示された。

関連論文リスト

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文参考訳（メタデータ） (2023-06-30T08:34:29Z)
Projection-Free Online Convex Optimization via Efficient Newton Iterations [10.492474737007722]
本稿では、凸領域$mathcalKサブセットmathbbRd$に対するオンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-19T18:48:53Z)
A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文参考訳（メタデータ） (2023-02-20T05:16:18Z)
PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear regression via Majorization Minimization with an application to semi-supervised graph learning [0.0]
スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
論文参考訳（メタデータ） (2021-10-23T10:19:11Z)
A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文参考訳（メタデータ） (2021-06-22T07:24:17Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
論文参考訳（メタデータ） (2020-10-21T15:05:53Z)
Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
論文参考訳（メタデータ） (2020-07-05T15:23:33Z)
Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文参考訳（メタデータ） (2020-05-10T19:52:03Z)
Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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