論文の概要: CLASSO: a practical primal path-following algorithm for the constrained LASSO

• arxiv url: http://arxiv.org/abs/2610.17024v1
• Date: Mon, 12 Oct 2026 16:02:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 03:39:14.347868
• Title: CLASSO: a practical primal path-following algorithm for the constrained LASSO
• Title（参考訳）: CLASSO:制約付きLASSOのための実用的な原始経路追従アルゴリズム
• Abstract要約: CLASSO は一般線形等式制約および不等式制約を受ける LASSO の経路追従法である。 我々は、原始経路が有限個のキンクを持つ部分的アフィンであり、制約条件や一意の乗数を持たないことを証明した。 本研究は,399ドル(約3万3000円)の合成スイートと6種類の糖尿病ベンチマークの制約付きバージョンの実装について評価する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present CLASSO, a path-following method for the LASSO subject to general linear equality and inequality constraints. The local direction is obtained from a quadratic programme on an augmented active set, which determines both the coefficients that leave zero and the weakly active inequalities that remain binding. For a positive-definite Hessian and a nonempty feasible set, this programme has a unique primal minimiser, even when the binding constraint rows are dependent, and gives the local derivative of the solution path. The construction recovers the LASSO-modified LARS direction without constraints, and over the full cone gives the segment leaving the origin. We prove that the primal path is piecewise affine with finitely many kinks, without a constraint qualification or unique multipliers. A finite path does not imply a finite traversal: re-certifying at each kink can fail to terminate. CLASSO instead follows the minimum-norm certificate along a lexicographic rate; we prove that this rule reaches $λ=0$ in exact arithmetic within an explicit bound and traverses the whole path. These results are machine-checked in Lean~4, and the floating-point implementation agrees with an exact rational one on all $210$ small test problems. We assess the implementation on a $39$-case synthetic suite and six constrained versions of the diabetes benchmark. On the $31$ nontrivial synthetic cases with $n\ge p$, sampled relative objective differences from numerical reference solves are below $10^{-9}$ in magnitude; unnormalised endpoint differences reach $1.5\times10^{-7}$ in magnitude. For $n<p$, matched differences range from $-3.6\times10^{-7}$ to $2\times10^{-9}$ across five ridge strengths. Across the synthetic and diabetes benchmarks, checks of all $580$ recorded segments found no missed interior event and all checked KKT residuals within the stated tolerances.
• Abstract（参考訳）: 一般線形等式制約と不等式制約を対象とするLASSOの経路追従法であるCLASSOを提案する。 局所方向は加法的能動集合上の二次計画から得られ、ゼロとなる係数と結合を保った弱活性不等式の両方を決定する。 正定値のヘッセン集合と空でない実現可能集合に対して、このプログラムは、束縛制約行が依存している場合でも、一意の原始最小値を持ち、解路の局所微分を与える。 構造は、LASSO修飾LARS方向を制約なく復元し、全円錐上には、原点を残しているセグメントを与える。 我々は、原始経路が有限個のキンクを持つ部分的アフィンであり、制約条件や一意の乗数を持たないことを証明した。 有限経路は有限トラバーサルを含まない: 各kinkにおける再検定は終了することができない。 代わりに、CLASSOは、語彙速度に沿って最小ノルム証明に従っており、この規則が明示的な境界内で正確な算術で$λ=0$に達し、全経路を横切ることを証明している。 これらの結果はLean~4でマシンチェックされ、浮動小数点の実装は、210ドルの小さなテスト問題すべてにおいて、正確な合理的な結果と一致します。 本研究は,399ドル(約3万3000円)の合成スイートと6種類の糖尿病ベンチマークの制約付きバージョンの実装について評価する。 $n\ge p$を持つ31ドルの非自明な合成ケースでは、数値参照解からの相対目的差は10^{-9}$以下であり、非正規化エンドポイントの差は1.5\times 10^{-7}$以下である。 n<p$の場合、一致した差は$3.6\times10^{-7}$から$2\times10^{-9}$までの5つの尾根強度がある。 人工および糖尿病のベンチマーク全体で、記録された580ドルのセグメントのチェックでは、内部イベントが見逃されず、すべてのチェックされたKKT残基が許容範囲内で検出された。

関連論文リスト

• Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization [2.834413535942792]
  非畳み込みミニマックス最適化における一階アルゴリズムの下位境界を確立する。 私たちの貢献は、分散還元を許容するゼロ境界クラスに対する下界である。 これらの結果は、凹凸と凹凸構造をまたいだ複雑さの障壁を同定する。
  論文  参考訳（メタデータ） (2026-10-01T13:24:15Z)
• Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization [1.6921396880325779]
  我々は,SAPD+の決定論的複雑性における線形条件数依存性が,非連続性最適化に必要であることを証明した。
  論文  参考訳（メタデータ） (2026-09-25T06:34:04Z)
• Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
  我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。 コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
  論文  参考訳（メタデータ） (2026-09-23T22:25:52Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  ネストした縮小可能な領域を2つの設定でオンライン最適化する。 懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。 決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
  論文  参考訳（メタデータ） (2026-08-29T06:01:56Z)
• DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning [4.941039246565574]
  大規模走行セールスマン問題 (TSP) では、出力の妥当性を保ちながら限られた計算を割り当てることが求められる。 DualCertは、Emphconstraint-coupled learningを導入し、現在の等級方程式と動的に分離されたサブチュール除去制約がそれぞれの学習遷移を定義する。 1000の保持されたTSP1000インスタンス上で、DualCertは、Lin--Kernighan--Helsgaunバージョン3(LKH-3)からの平均的なツアーコストギャップ(0.0573%)をインスタンス当たり9.55秒のバッチ修正秒で達成した。
  論文  参考訳（メタデータ） (2026-08-10T02:48:16Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)

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

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