論文の概要: Stochastic Cutting Planes for Data-Driven Optimization
- arxiv url: http://arxiv.org/abs/2103.02506v1
- Date: Wed, 3 Mar 2021 16:21:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-06 18:15:47.147064
- Title: Stochastic Cutting Planes for Data-Driven Optimization
- Title（参考訳）: データ駆動最適化のための確率的切断平面
- Authors: Dimitris Bertsimas, Michael Lingzhi Li
- Abstract要約: 我々は、アルゴリズムが高い確率で$epsilon$optimalソリューションに収束することができることを示しています。
我々は, 切削面のサンプリング限界を実験的に検討し, 多くの問題に対して, 高品質な解には, サンプリングサイズ$o(sqrt[3]n)$ が十分であることを示す。
- 参考スコア（独自算出の注目度）: 6.243995448840211
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a stochastic version of the cutting-plane method for a large
class of data-driven Mixed-Integer Nonlinear Optimization (MINLO) problems. We
show that under very weak assumptions the stochastic algorithm is able to
converge to an $\epsilon$-optimal solution with high probability. Numerical
experiments on several problems show that stochastic cutting planes is able to
deliver a multiple order-of-magnitude speedup compared to the standard
cutting-plane method. We further experimentally explore the lower limits of
sampling for stochastic cutting planes and show that for many problems, a
sampling size of $O(\sqrt[3]{n})$ appears to be sufficient for high quality
solutions.
- Abstract（参考訳）: 大規模データ駆動型Mixed-Integer Nonlinear Optimization (MINLO)問題に対する切断面法の確率的バージョンを紹介する。
非常に弱い仮定の下で、確率的アルゴリズムは高い確率で$\epsilon$-Optimal解に収束できることを示す。
いくつかの問題に関する数値実験は、確率的切断面が標準的な切断面法と比較して複数の倍率の速度アップを提供することができることを示している。
さらに, 確率的切断面に対するサンプリングの限界を実験的に検討し, 多くの問題に対して, 高品質な解には, $o(\sqrt[3]{n})$ のサンプリングサイズが十分であることを示す。
関連論文リスト
- Differentiable Cutting-plane Layers for Mixed-integer Linear
Optimization [1.7398512809572197]
本稿では,パラメータ混合整数線形最適化問題の一群を,入力データにいくつかの項目が存在する場合に解く問題について考察する。
我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。
論文 参考訳（メタデータ） (2023-11-06T18:57:07Z) - Multistage Stochastic Optimization via Kernels [3.7565501074323224]
我々は,多段階最適化問題に対する非パラメトリック,データ駆動,トラクタブルアプローチを開発した。
本稿では,提案手法が最適に近い平均性能で決定ルールを生成することを示す。
論文 参考訳（メタデータ） (2023-03-11T23:19:32Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Random Manifold Sampling and Joint Sparse Regularization for Multi-label
Feature Selection [0.0]
本稿では,$ell_2,1$および$ell_F$正規化の連立制約付き最適化問題を解くことで,最も関連性の高いいくつかの特徴を得ることができる。
実世界のデータセットの比較実験により,提案手法が他の手法よりも優れていることが示された。
論文 参考訳（メタデータ） (2022-04-13T15:06:12Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳（メタデータ） (2022-03-18T05:49:13Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳（メタデータ） (2021-06-12T10:59:02Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。