論文の概要: Fast Screening Rules for Optimal Design via Quadratic Lasso
Reformulation
- arxiv url: http://arxiv.org/abs/2310.08939v1
- Date: Fri, 13 Oct 2023 08:10:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 13:41:37.463848
- Title: Fast Screening Rules for Optimal Design via Quadratic Lasso
Reformulation
- Title（参考訳）: 擬似ラッソ改質による最適設計のための高速スクリーニング法
- Authors: Guillaume Sagnol and Luc Pronzato
- Abstract要約: 本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。
新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。
本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
- 参考スコア（独自算出の注目度）: 0.135975510645475
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problems of Lasso regression and optimal design of experiments share a
critical property: their optimal solutions are typically \emph{sparse}, i.e.,
only a small fraction of the optimal variables are non-zero. Therefore, the
identification of the support of an optimal solution reduces the dimensionality
of the problem and can yield a substantial simplification of the calculations.
It has recently been shown that linear regression with a \emph{squared}
$\ell_1$-norm sparsity-inducing penalty is equivalent to an optimal
experimental design problem. In this work, we use this equivalence to derive
safe screening rules that can be used to discard inessential samples. Compared
to previously existing rules, the new tests are much faster to compute,
especially for problems involving a parameter space of high dimension, and can
be used dynamically within any iterative solver, with negligible computational
overhead. Moreover, we show how an existing homotopy algorithm to compute the
regularization path of the lasso method can be reparametrized with respect to
the squared $\ell_1$-penalty. This allows the computation of a Bayes
$c$-optimal design in a finite number of steps and can be several orders of
magnitude faster than standard first-order algorithms. The efficiency of the
new screening rules and of the homotopy algorithm are demonstrated on different
examples based on real data.
- Abstract（参考訳）: ラッソ回帰と実験の最適設計の問題は重要な性質を共有している:それらの最適解は典型的には \emph{sparse} である。
したがって、最適解の支持体の同定は問題の次元性を減少させ、計算の大幅な単純化をもたらすことができる。
最近、emph{squared} $\ell_1$-normスペーシティ誘導ペナルティを用いた線形回帰は最適な実験設計問題と同値であることが示されている。
本研究では,この等価性を用いて,不要なサンプルの廃棄に使用できる安全なスクリーニングルールを導出する。
従来のルールと比較して、新しいテストは特に高次元のパラメータ空間に関わる問題に対して計算がはるかに速く、計算オーバーヘッドが無視できるような反復解法内で動的に使用できる。
さらに、ラッソ法の正規化経路を計算するための既存のホモトピーアルゴリズムが、正方形の$\ell_1$-penaltyに対して再パラメータ化可能であることを示す。
これにより、ベイズ$c$-最適設計を有限ステップで計算でき、標準的な一階アルゴリズムよりも数桁早く計算できる。
新しいスクリーニングルールとホモトピーアルゴリズムの効率は実データに基づいて異なる例で示される。
関連論文リスト
- l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
簡単な比率とソート手法を用いた新しいフィッティング法を提案する。
提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
論文 参考訳（メタデータ） (2024-02-26T16:30:58Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Minimal Cycle Representatives in Persistent Homology using Linear
Programming: an Empirical Study with User's Guide [4.46514714749204]
永続ホモロジークラスのサイクル代表は、データ内のトポロジ的特徴の説明に使用することができる。
この問題を解決するためのアプローチの1つは、データのコンテキストで意味のある尺度に対して代表者の選択を最適化することです。
論文 参考訳（メタデータ） (2021-05-14T18:38:48Z) - Slowly Varying Regression under Sparsity [5.22980614912553]
本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。
本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。
結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-02-22T04:51:44Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。
このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
論文 参考訳（メタデータ） (2020-02-20T12:04:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。