論文の概要: A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions

• arxiv url: http://arxiv.org/abs/2507.05562v2
• Date: Sun, 19 Oct 2025 01:07:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:38.454322
• Title: A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions
• Title（参考訳）: 微分包含を用いたホモトピーを伴わないラッソ問題の高速解法
• Authors: Gabriel P. Langlois, Jérôme Darbon,
• Abstract要約: 我々は、新しい微分包摂法を用いて、ホモトピーを使わずに、よく知られたラッソ問題を正確に解くことができることを証明した。 解析結果から, 機械の精度まで, ラッソ問題に対する精度の高いアルゴリズムが得られた。 数値実験により,本アルゴリズムは効率と精度の両方で最先端のアルゴリズムより優れていることを確認した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove in this work that the well-known lasso problem can be solved exactly without homotopy using novel differential inclusions techniques. Specifically, we show that a selection principle from the theory of differential inclusions transforms the dual lasso problem into the problem of calculating the trajectory of a projected dynamical system that we prove is integrable. Our analysis yields an exact algorithm for the lasso problem, numerically up to machine precision, that is amenable to computing regularization paths and is very fast. Moreover, we show the continuation of solutions to the integrable projected dynamical system in terms of the hyperparameter naturally yields a rigorous homotopy algorithm. Numerical experiments confirm that our algorithm outperforms the state-of-the-art algorithms in both efficiency and accuracy. Beyond this work, we expect our results and analysis can be adapted to compute exact or approximate solutions to a broader class of polyhedral-constrained optimization problems.
• Abstract（参考訳）: この研究で、よく知られたラッソ問題は、新しい微分包摂法を用いてホモトピーを使わずに、正確に解けることを証明した。 具体的には、微分包含理論から選択原理が双対ラッソ問題を、我々が証明した射影力学系の軌道を計算する問題に変換することを示す。 我々の解析は、機械の精度まで数値的にラッソ問題の正確なアルゴリズムを導き、正規化パスの計算に適しており、非常に高速である。 さらに、ハイパーパラメータの観点から、積分可能射影力学系に対する解の継続が、厳密なホモトピーアルゴリズムを自然に生み出すことを示す。 数値実験により,本アルゴリズムは効率と精度の両方で最先端のアルゴリズムより優れていることを確認した。 この研究の他に、我々の結果と分析は、より広範な多面体制約付き最適化問題に対する正確な解や近似解を計算できることを期待している。

関連論文リスト

• Towards minimax optimal algorithms for Active Simple Hypothesis Testing [0.0]
  固定予算ベストアーム識別問題の簡易な変種である能動簡易仮説テスト(ASHT)問題について検討した。 ASHT問題の上界の新たなゲーム理論の定式化を提供する。 本稿では,前処理に比べて計算能力に優れた近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-26T20:03:53Z)
• WENDy for Nonlinear-in-Parameters ODEs [1.9573380763700712]
  WEN(Wak-form Estimation of Non-linear Dynamics)は、非線形インである通常の微分方程式の系に対応するために拡張される。 提案手法の実用的メリットを実証するために,一連のベンチマークシステムに結果を提示する。
  論文  参考訳（メタデータ） (2025-02-13T01:40:21Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)
• Boosting Algorithms for Estimating Optimal Individualized Treatment Rules [4.898659895355356]
  最適な個別化処理規則を推定するための非パラメトリックアルゴリズムを提案する。 提案アルゴリズムは機械学習文学において最も強力なアルゴリズムの1つであるXGBoostアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2020-01-31T22:26:38Z)

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

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