論文の概要: Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization

• arxiv url: http://arxiv.org/abs/2501.02942v1
• Date: Mon, 06 Jan 2025 11:31:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-07 17:05:21.893678
• Title: Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization
• Title（参考訳）: 半定値最適化を用いた低ランク問題に対する近似アルゴリズムの改良
• Authors: Ryan Cory-Wright, Jean Pauphilet,
• Abstract要約: 低ランク最適化問題に対する類似の緩和型サンプル戦略を構築した。 ほぼ最適解が得られる半定緩和とランダムな丸めスキームを導出する。 我々は、緩和とサンプリング方式の有効性とスケーラビリティを数値的に説明する。
• 参考スコア（独自算出の注目度）: 2.1485350418225244
• License:
• Abstract: Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-sample strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme, which obtains provably near-optimal solutions, mimicking the blueprint from Goemans and Williamson for the Max-Cut problem. We then extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations that are both tighter and more broadly applicable than those in prior works. Although our original proposal introduces large semidefinite matrices as decision variables, we show that most of the blocks in these matrices can be safely omitted without altering the optimal value, hence improving the scalability of our approach. Using several examples (including matrix completion, basis pursuit, and reduced-rank regression), we show how to reduce the size of our relaxation even further. Finally, we numerically illustrate the effectiveness and scalability of our relaxation and our sampling scheme on orthogonally constrained quadratic optimization and matrix completion problems.
• Abstract（参考訳）: Goemans-Williamsonアルゴリズムの組合せ最適化への影響に触発されて、低ランク最適化問題に対する類似の緩和-テーマ-サンプル戦略を構築した。 まず、直交的に制約された二次最適化問題に対して、半定値緩和とランダム化された丸めスキームを導出し、それが証明可能な準最適解を求め、マックス・カット問題に対するゴーマンスとウィリアムソンのブループリントを模倣する。 次に、従来よりも厳密かつ広く適用可能な新しい半有限緩和を開発することで、一般の低ランク最適化問題にアプローチを拡大する。 従来の提案では,決定変数として大きな半定値行列を導入したが,最適値を変更することなく,ほとんどのブロックを安全に省略できることが示され,その結果,アプローチのスケーラビリティが向上した。 いくつかの例(行列補完、基底追従、縮小ランク回帰など)を用いて、緩和の規模をさらに小さくする方法を示す。 最後に、直交2次最適化と行列補完問題に対する緩和の有効性と拡張性を数値的に説明する。

関連論文リスト

• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas と Ozturk (2023) は、ブラックボックスのグローバル最適化問題を解決する方法として OCTHaGOn を提案した。 我々は、他のMIO表現可能なMLモデルを用いて、元の問題を近似することで、このアプローチの拡張を提供する。 多くの場合において、ソリューションの実現可能性と最適性の改善を示す。
  論文  参考訳（メタデータ） (2023-11-03T06:33:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints [3.179831861897336]
  低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。 我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
  論文  参考訳（メタデータ） (2020-09-22T08:59:06Z)
• 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)
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning [3.511851311025242]
  一次変数と双対変数を反復的に最適化する原始双対アルゴリズムを提案する。 提案アルゴリズムの収束を証明し,その非漸近収束率を示す。 ファンドマネージメントにおける最適ファンド選択問題に関する予備実験の結果,有効性が確認された。
  論文  参考訳（メタデータ） (2020-05-19T03:31:01Z)

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

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