論文の概要: 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次定常点に収束することを示す。
提案手法の有効性を示す数値実験を行った。
関連論文リスト
- A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳(メタデータ) (2023-11-17T22:07:18Z) - Measurement-induced phase transition for free fermions above one
dimension [50.444903773362995]
自由フェルミオンモデルに対する$d>1$次元における測定誘起エンタングルメント相転移の理論を開発した。
臨界点は、粒子数と絡み合いエントロピーの第2累積のスケーリング$$elld-1 ln ell$でギャップのない位相を分離する。
論文 参考訳(メタデータ) (2023-09-21T18:11:04Z) - 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) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-05-27T11:23:57Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - 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) - A fast and simple modification of Newton's method helping to avoid
saddle points [0.0]
この論文は、$f$が$C3$でシーケンス$x_n$であれば、極限点は臨界点であり、サドル点ではなく、収束速度はニュートンの方法と同じである。
論文 参考訳(メタデータ) (2020-06-02T10:38:00Z) - Extremal elements of a sublattice of the majorization lattice and
approximate majorization [0.0]
一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。
また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
論文 参考訳(メタデータ) (2020-01-23T19:09:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。