論文の概要: 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)$を証明できる。 数値シミュレーションにより,新しいアルゴリズムは経験的にも優れた性能を示す。

関連論文リスト

• Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function [14.986031916712108]
  勾配追跡手法の一点推定に基づくゼロ階分散最適化手法を提案する。 我々は,この手法が雑音条件下で数値関数と収束することを証明した。
  論文  参考訳（メタデータ） (2024-10-08T11:45:45Z)
• Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions [26.543628010637036]
  非函数に対して$mathcalO(log T)$の最適収束率を達成する新しい適応還元法を導入する。 また、提案手法を拡張して、合成最適化のために$mathcalO(log T)$と同じ最適率を得る。
  論文  参考訳（メタデータ） (2024-06-04T04:39:51Z)
• 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 [75.34939761152587]
  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 [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique [23.63073074337495]
  本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。 分散勾配追跡法を,勾配推定のない帯域設定に拡張する。 近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
  論文  参考訳（メタデータ） (2022-10-11T17:04:45Z)
• 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)

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

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