論文の概要: Screening for a Reweighted Penalized Conditional Gradient Method
- arxiv url: http://arxiv.org/abs/2107.01106v1
- Date: Fri, 2 Jul 2021 14:37:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-05 12:43:08.830210
- Title: Screening for a Reweighted Penalized Conditional Gradient Method
- Title（参考訳）: ペナル化条件勾配法の再検討
- Authors: Yifan Sun and Francis Bach
- Abstract要約: 条件勾配法(CGM)は大規模なスパース凸最適化に広く用いられている。
一般化一般化器の疎性獲得特性の調整方法を示す。
本実験では,正則化器の凹凸を調整し,スクリーニング規則のアグレッシブ性を検証する。
- 参考スコア（独自算出の注目度）: 20.62129327196916
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The conditional gradient method (CGM) is widely used in large-scale sparse
convex optimization, having a low per iteration computational cost for
structured sparse regularizers and a greedy approach to collecting nonzeros. We
explore the sparsity acquiring properties of a general penalized CGM (P-CGM)
for convex regularizers and a reweighted penalized CGM (RP-CGM) for nonconvex
regularizers, replacing the usual convex constraints with gauge-inspired
penalties. This generalization does not increase the per-iteration complexity
noticeably. Without assuming bounded iterates or using line search, we show
$O(1/t)$ convergence of the gap of each subproblem, which measures distance to
a stationary point. We couple this with a screening rule which is safe in the
convex case, converging to the true support at a rate $O(1/(\delta^2))$ where
$\delta \geq 0$ measures how close the problem is to degeneracy. In the
nonconvex case the screening rule converges to the true support in a finite
number of iterations, but is not necessarily safe in the intermediate iterates.
In our experiments, we verify the consistency of the method and adjust the
aggressiveness of the screening rule by tuning the concavity of the
regularizer.
- Abstract（参考訳）: 条件勾配法(CGM)は大規模なスパース凸最適化において広く用いられ、構造化スパース正規化器の1イテレーション当たりの計算コストが低く、非ゼロの収集に対する欲求的なアプローチである。
非凸正則化器用一般ペナリゼーションCGM(P-CGM)と非凸正則化器用再重み付きペナリゼーションCGM(RP-CGM)について,通常の凸制約をゲージインスパイアされたペナリティーに置き換えた。
この一般化は、イテレーション当たりの複雑さを顕著に増やさない。
有界イテレートや線探索を仮定せずに、各サブプロブレムのギャップを$O(1/t)$収束させ、静止点までの距離を測定する。
我々はこれを凸の場合において安全であるスクリーニング規則と結合し、o(1/(\delta^2))$で真のサポートに収束する。
非凸の場合、スクリーニング規則は有限個の反復において真の支持に収束するが、中間イテレートでは必ずしも安全ではない。
本実験では, 本手法の整合性を検証し, 正則化器の凹凸を調整し, スクリーニング規則の適応性を調整した。
関連論文リスト
- A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum
Optimization [7.014966911550542]
スパースサブ構造を検索するために,非滑らかな正規化を伴うディープニューラルネットワークをトレーニングする問題を考察する。
我々は、収束と最悪のケースの複雑さが勾配のリプシッツ定数の知識や近似なしで確立されるSR2と呼ばれる新しい解法を導出する。
CIFAR-10とCIFAR-100で訓練されたネットワークインスタンスの実験により、SR2はProxGENやProxSGDのような関連する手法よりも常に高い空間性と精度を達成することが示された。
論文 参考訳（メタデータ） (2022-06-14T00:28:44Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Fast Global Convergence of Policy Optimization for Constrained MDPs [17.825031573375725]
勾配法は最適性ギャップと制約違反の両方に対して$mathcalO(log(T)/T)$大域収束率が得られることを示す。
スレーターの条件が満たされ、事前条件が知られているとき、十分大きなT$に対してゼロ制約違反がさらに保証される。
論文 参考訳（メタデータ） (2021-10-31T17:46:26Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
高速収束を提供するランゲヴィン・モンテカルロ(LMC)は勾配近似の計算を必要とする。
実際には、有限差分近似を代理として使用し、高次元では高価である。
本稿では,新しい分散低減手法であるCoordinates Averaging Descent (RCAD)を導入し,過度に損傷を受けたLCCと過度に損傷を受けたLCCを併用する。
論文 参考訳（メタデータ） (2020-06-10T21:08:38Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-03-30T20:44:56Z) - Safe Screening for the Generalized Conditional Gradient Method [2.806911268410107]
一般化条件勾配法(gCGM)の空間性取得特性について検討する。
修正ペナルティのgCGMは,通常のペナルティと類似した特徴選択特性を有することを示す。
論文 参考訳（メタデータ） (2020-02-22T15:07:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。