論文の概要: Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic
Approach
- arxiv url: http://arxiv.org/abs/2010.13934v2
- Date: Fri, 20 May 2022 22:29:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 18:39:40.700326
- Title: Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic
Approach
- Title(参考訳): ホモトピックアプローチによるラッソ計算におけるウォームアップ段階の加速
- Authors: Yujie Zhao, Xiaoming Huo
- Abstract要約: ホモトピック法は、ラッソ型推定器で使われる$ell_1$ペナルティを近似するために用いられる。
ラッソ型推定器の計算における既存の手法よりも高速な数値収束率を示す。
- 参考スコア(独自算出の注目度): 2.538209532048867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In optimization, it is known that when the objective functions are strictly
convex and well-conditioned, gradient-based approaches can be extremely
effective, e.g., achieving the exponential rate of convergence. On the other
hand, the existing Lasso-type estimator in general cannot achieve the optimal
rate due to the undesirable behavior of the absolute function at the origin. A
homotopic method is to use a sequence of surrogate functions to approximate the
$\ell_1$ penalty that is used in the Lasso-type of estimators. The surrogate
functions will converge to the $\ell_1$ penalty in the Lasso estimator. At the
same time, each surrogate function is strictly convex, which enables a provable
faster numerical rate of convergence. In this paper, we demonstrate that by
meticulously defining the surrogate functions, one can prove a faster numerical
convergence rate than any existing methods in computing for the Lasso-type of
estimators. Namely, the state-of-the-art algorithms can only guarantee
$O(1/\epsilon)$ or $O(1/\sqrt{\epsilon})$ convergence rates, while we can prove
an $O([\log(1/\epsilon)]^2)$ for the newly proposed algorithm. Our numerical
simulations show that the new algorithm also performs better empirically.
- Abstract(参考訳): 最適化において、目的関数が厳密な凸かつ十分に条件付けられたとき、勾配に基づくアプローチは、例えば指数的収束率を達成するなど非常に効果的であることが知られている。
一方、既存のラッソ型推定器は、原点における絶対関数が望ましくない振舞いのために最適速度を達成することができない。
ホモトピー的手法は、サロゲート関数の列を使って、ラッソ型推定器で使われる$\ell_1$ペナルティを近似する。
サーロゲート関数は lasso estimator の $\ell_1$ ペナルティに収束する。
同時に、それぞれの代理関数は厳密な凸であり、証明可能なより高速な収束率を可能にする。
本稿では,代用関数を厳密に定義することにより,ラッソ型推定器の計算方法よりも高速な数値収束率を証明できることを実証する。
すなわち、最先端アルゴリズムは$O(1/\epsilon)$または$O(1/\sqrt{\epsilon})$収束率しか保証できないが、新たに提案されたアルゴリズムに対して$O([\log(1/\epsilon)]^2)$を証明できる。
数値シミュレーションにより,新しいアルゴリズムは経験的にも優れた性能を示す。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳(メタデータ) (2022-10-11T17:04:45Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳(メタデータ) (2021-07-01T06:43:11Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳(メタデータ) (2021-05-11T08:09:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。