論文の概要: An Iteratively Reweighted Method for Sparse Optimization on Nonconvex $\ell_{p}$ Ball

• arxiv url: http://arxiv.org/abs/2104.02912v1
• Date: Wed, 7 Apr 2021 04:43:36 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-08 12:35:36.538817
• Title: An Iteratively Reweighted Method for Sparse Optimization on Nonconvex $\ell_{p}$ Ball
• Title（参考訳）: 非凸$\ell_{p}$ボールにおけるスパース最適化の反復加重法
• Authors: Hao Wang, Xiangyu Yang, and Wei Jiang
• Abstract要約: 重み付き$ell_1$-ballプロジェクション部分問題を解く反復的重み付け法を提案する。 本解析では,生成したイテレートが1次定常点に収束することを示す。
• 参考スコア（独自算出の注目度）: 6.821376293635223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is intended to solve the nonconvex $\ell_{p}$-ball constrained nonlinear optimization problems. An iteratively reweighted method is proposed, which solves a sequence of weighted $\ell_{1}$-ball projection subproblems. At each iteration, the next iterate is obtained by moving along the negative gradient with a stepsize and then projecting the resulted point onto the weighted $\ell_{1}$ ball to approximate the $\ell_{p}$ ball. Specifically, if the current iterate is in the interior of the feasible set, then the weighted $\ell_{1}$ ball is formed by linearizing the $\ell_{p}$ norm at the current iterate. If the current iterate is on the boundary of the feasible set, then the weighted $\ell_{1}$ ball is formed differently by keeping those zero components in the current iterate still zero. In our analysis, we prove that the generated iterates converge to a first-order stationary point. Numerical experiments demonstrate the effectiveness of the proposed method.
• Abstract（参考訳）: 本稿では,非凸$\ell_{p}$-ball制約非線形最適化問題を解くことを目的とする。 重み付き$\ell_{1}$-ballプロジェクションサブプロブレムの列を解く反復的再重み付け法を提案する。 各イテレーションにおいて、次のイテレーションは、ステップサイズで負の勾配に沿って移動し、その結果のポイントを重み付き$\ell_{1}$ ballに投影して、$\ell_{p}$ ballを近似することで得られる。 具体的には、現在のイテレートが実行可能集合の内部にある場合、重み付き$\ell_{1}$ 球は、現在のイテレートで$\ell_{p}$ノルムを線形化することによって形成される。 もし現在のイテレートが実現可能な集合の境界にあるなら、重み付けされた$\ell_{1}$ ballは現在のイテレートの零成分をまだゼロに保つことによって異なる形で形成される。 本解析では,生成したイテレートが1次定常点に収束することを示す。 提案手法の有効性を示す数値実験を行った。

関連論文リスト

• Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
  本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。 解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
  論文  参考訳（メタデータ） (2024-04-27T10:20:41Z)
• Avoiding strict saddle points of nonconvex regularized problems [3.92625489118339]
  第二項最適性条件は定常点の零点にのみ依存することを示す。 本稿では,反復再重み付き$ell_1$を含む2つの繰り返し重み付きアルゴリズムを提案する。 これらのアルゴリズムは、サドル点の性質が仮定されるときのみランダムに局所的なサドラーに収束することを示す。
  論文  参考訳（メタデータ） (2024-01-17T15:25:50Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Quasi-Newton Steps for Efficient Online Exp-Concave Optimization [10.492474737007722]
  Online Newton Step (ONS)は、$O(dln T)$を保証できる。 本稿では,自己協和性バリアを正規化器として使用することにより,一般化された投影をサイドステップで行う。 最終的なアルゴリズムはONSのより効率的なバージョンと見なすことができる。
  論文  参考訳（メタデータ） (2022-11-02T17:57:21Z)
• Online Lewis Weight Sampling [62.38157566916501]
  コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。 この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。 オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
  論文  参考訳（メタデータ） (2022-07-17T19:40:51Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• $\lambda$-Regularized A-Optimal Design and its Approximation by $\lambda$-Regularized Proportional Volume Sampling [1.256413718364189]
  本稿では,$lambda$-regularized $A$-optimal design problemについて検討し,$lambda$-regularized proportional volume sample algorithmを紹介する。 この問題は、リッジ回帰モデルにおける真の係数からリッジ回帰予測器の2乗誤差を最小化しようとする、リッジ回帰の最適設計から動機づけられている。
  論文  参考訳（メタデータ） (2020-06-19T15:17:57Z)
• Extremal elements of a sublattice of the majorization lattice and approximate majorization [0.0]
  一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。 また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-01-23T19:09:18Z)

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

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