論文の概要: Slowly Varying Regression under Sparsity

• arxiv url: http://arxiv.org/abs/2102.10773v5
• Date: Sat, 11 Nov 2023 15:08:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-15 00:50:21.950660
• Title: Slowly Varying Regression under Sparsity
• Title（参考訳）: 緩やかに不安定な回帰
• Authors: Dimitris Bertsimas, Vassilis Digalakis Jr, Michael Linghzi Li, Omar Skali Lami
• Abstract要約: 本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。 本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。 結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 5.22980614912553
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the framework of slowly varying regression under sparsity, allowing sparse regression models to exhibit slow and sparse variations. The problem of parameter estimation is formulated as a mixed-integer optimization problem. We demonstrate that it can be precisely reformulated as a binary convex optimization problem through a novel relaxation technique. This relaxation involves a new equality on Moore-Penrose inverses, convexifying the non-convex objective function while matching the original objective on all feasible binary points. This enables us to efficiently solve the problem to provable optimality using a cutting plane-type algorithm. We develop a highly optimized implementation of this algorithm, substantially improving upon the asymptotic computational complexity of a straightforward implementation. Additionally, we propose a fast heuristic method that guarantees a feasible solution and, as empirically illustrated, produces high-quality warm-start solutions for the binary optimization problem. To tune the framework's hyperparameters, we suggest a practical procedure relying on binary search that, under certain assumptions, is guaranteed to recover the true model parameters. On both synthetic and real-world datasets, we demonstrate that the resulting algorithm outperforms competing formulations in comparable times across various metrics, including estimation accuracy, predictive power, and computational time. The algorithm is highly scalable, allowing us to train models with thousands of parameters. Our implementation is available open-source at https://github.com/vvdigalakis/SSVRegression.git.
• Abstract（参考訳）: 疎度下での緩やかな回帰の枠組みを示し、スパース回帰モデルでは緩やかでスパースな回帰を示す。 パラメータ推定の問題は混合整数最適化問題として定式化される。 新たな緩和手法により,二項凸最適化問題として正確に再構成できることを実証した。 この緩和はムーア・ペンローズ逆数に対する新しい等式を含み、すべての実現可能な二分点上の元の目的と一致しながら非凸目的函数を凸化する。 これにより,切断平面型アルゴリズムを用いて効率よく最適性を証明できる。 このアルゴリズムの高度に最適化された実装を開発し、簡単な実装の漸近的計算複雑性を大幅に改善する。 さらに,実現可能な解を保証する高速ヒューリスティック手法を提案し,実証的に示すように,二項最適化問題に対する高品質なウォームスタート解を生成する。 フレームワークのハイパーパラメータを調整するために、ある仮定の下では、真のモデルパラメータを復元することが保証されるバイナリ検索に依存する実用的な手順を提案する。 合成データと実世界のデータの両方について, 推定精度, 予測能力, 計算時間など, 様々な指標で比較して, 結果のアルゴリズムが競合する定式化を上回っていることを示す。 アルゴリズムは非常にスケーラブルで、数千のパラメータでモデルをトレーニングすることができます。 実装はhttps://github.com/vvdigalakis/ssvregression.gitで公開しています。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。 本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
  論文  参考訳（メタデータ） (2023-09-04T19:47:04Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Adaptive Sampling of Pareto Frontiers with Binary Constraints Using Regression and Classification [0.0]
  本稿では,二項制約を持つブラックボックス多目的最適化問題に対する適応最適化アルゴリズムを提案する。 本手法は確率的回帰モデルと分類モデルに基づいており,最適化目標のサロゲートとして機能する。 また,予想される超体積計算を高速化するために,新しい楕円形トランケーション法を提案する。
  論文  参考訳（メタデータ） (2020-08-27T09:15:02Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
  シンボリック回帰(SR)問題は、機械学習において難しい問題である。 混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。 我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
  論文  参考訳（メタデータ） (2020-06-11T20:53:17Z)

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

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