論文の概要: Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction
- arxiv url: http://arxiv.org/abs/2405.07965v1
- Date: Mon, 13 May 2024 17:46:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-14 12:36:51.923480
- Title: Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction
- Title（参考訳）: 暗黙のシナリオリダクションによる超量子制約最適化の高速計算
- Authors: Jake Roth, Ying Cui,
- Abstract要約: 本稿では、大規模最適化問題を解決するために、高速でスケーラブルで堅牢な2階計算フレームワークを提案する。
超量子ベースの最適化では、テール条件予測を計算するために、すべてのシナリオで評価されたランダム関数のランク付けが必要となる。
- 参考スコア（独自算出の注目度）: 8.756303407351464
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Superquantiles have recently gained significant interest as a risk-aware metric for addressing fairness and distribution shifts in statistical learning and decision making problems. This paper introduces a fast, scalable and robust second-order computational framework to solve large-scale optimization problems with superquantile-based constraints. Unlike empirical risk minimization, superquantile-based optimization requires ranking random functions evaluated across all scenarios to compute the tail conditional expectation. While this tail-based feature might seem computationally unfriendly, it provides an advantageous setting for a semismooth-Newton-based augmented Lagrangian method. The superquantile operator effectively reduces the dimensions of the Newton systems since the tail expectation involves considerably fewer scenarios. Notably, the extra cost of obtaining relevant second-order information and performing matrix inversions is often comparable to, and sometimes even less than, the effort required for gradient computation. Our developed solver is particularly effective when the number of scenarios substantially exceeds the number of decision variables. In synthetic problems with linear and convex diagonal quadratic objectives, numerical experiments demonstrate that our method outperforms existing approaches by a large margin: It achieves speeds more than 750 times faster for linear and quadratic objectives than the alternating direction method of multipliers as implemented by OSQP for computing low-accuracy solutions. Additionally, it is up to 25 times faster for linear objectives and 70 times faster for quadratic objectives than the commercial solver Gurobi, and 20 times faster for linear objectives and 30 times faster for quadratic objectives than the Portfolio Safeguard optimization suite for high-accuracy solution computations.
- Abstract（参考訳）: 近年,統計学習や意思決定問題において,公正性や分布変化に対処するためのリスク対応指標として,スーパーチャンティルが注目されている。
本稿では,超量子的制約による大規模最適化問題を解くために,高速でスケーラブルで堅牢な2階計算フレームワークを提案する。
経験的リスク最小化とは異なり、超量子ベースの最適化は、テール条件予測を計算するために、すべてのシナリオで評価されたランダム関数のランク付けを必要とする。
このテールベースの機能は、計算的に不都合に思えるかもしれないが、半滑らか-ニュートンベースのラグランジアン法に有利な設定を提供する。
超量子作用素は、テール期待がかなり少ないシナリオを含むため、ニュートン系の次元を効果的に減少させる。
特に、関連する2階情報を取得し、行列逆転を行うための余分なコストは、勾配計算に必要な労力に匹敵し、時にはそれ以下である。
提案手法は,シナリオ数が決定変数数を超える場合,特に有効である。
線形および凸対角2次目的の合成問題において, 数値実験により, 提案手法は, 低精度解のOSQPで実装した乗算器の交互方向法よりも, 線形および2次目的の750倍以上の高速化を実現している。
さらに、線形目的の最大25倍、二次目的の最大70倍、線形目的の最大20倍、二次目的の最大30倍、高精度解計算のPortfolio Safeguard最適化スイートよりも高速である。
関連論文リスト
- A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。
ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文 参考訳（メタデータ） (2024-05-03T10:37:34Z) - Fast Numerical Solver of Ising Optimization Problems via Pruning and Domain Selection [4.460518115427853]
本稿では,Ising最適化問題に対する高速かつ効率的な解法を提案する。
我々の解法は古典的解法よりも桁違いに高速で、量子インスパイアされたアニールよりも少なくとも2倍高速である。
論文 参考訳（メタデータ） (2023-12-10T09:43:15Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Distributed Estimation and Inference for Semi-parametric Binary Response Models [8.309294338998539]
本稿では,分散コンピューティング環境下での半パラメトリック二値選択モデルの最大スコア推定について検討する。
直感的な分割・対数推定器は計算コストが高く、機械数に対する非正規制約によって制限される。
論文 参考訳（メタデータ） (2022-10-15T23:06:46Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Global Optimization of Gaussian processes [52.77024349608834]
少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。
このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。
提案手法の順序の順序による時間収束を,総じて低減する。
論文 参考訳（メタデータ） (2020-05-21T20:59:11Z) - Scalable Hyperparameter Optimization with Lazy Gaussian Processes [1.3999481573773074]
本稿では,ガウス過程の高精度な新しい近似法を提案する。
最初の実験では、単一ノードにおける162の係数の高速化と、並列環境における5の係数のさらなる高速化が示されている。
論文 参考訳（メタデータ） (2020-01-16T10:15:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。