論文の概要: Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions

• arxiv url: http://arxiv.org/abs/2205.09961v1
• Date: Fri, 20 May 2022 04:49:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-23 15:36:31.053310
• Title: Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
• Title（参考訳）: 予測付きワームスタートアルゴリズムの離散凸解析に基づくフレームワーク
• Authors: Shinsaku Sakaue, Taihei Oki
• Abstract要約: アルゴリズムを学習した予測で拡張することは、最悪の場合の境界を越えるための有望なアプローチである。 学習された双対解による温かいスタートは、重み付き完全二分法マッチングのためのハンガリーの手法の時間的複雑さを改善することができることを示す。 重み付き完全二部構造マッチング,重み付きマトロイド交叉,離散エネルギー最小化に適用することで,DCAベースのフレームワークの有用性を示す。
• 参考スコア（独自算出の注目度）: 15.191184049312467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and Vassilvitskii~(2021) have demonstrated that a warm start with learned dual solutions can improve the time complexity of the Hungarian method for weighted perfect bipartite matching. We extend and improve their framework in a principled manner via \textit{discrete convex analysis} (DCA), a discrete analog of convex analysis. We show the usefulness of our DCA-based framework by applying it to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization for computer vision. Our DCA-based framework yields time complexity bounds that depend on the $\ell_\infty$-distance from a predicted solution to an optimal solution, which has two advantages relative to the previous $\ell_1$-distance-dependent bounds: time complexity bounds are smaller, and learning of predictions is more sample efficient. We also discuss whether to learn primal or dual solutions from the DCA perspective.
• Abstract（参考訳）: 学習された予測によるアルゴリズムの強化は、最悪のケース境界を超えるための有望なアプローチである。 Dinitz, Im, Lavastida, Moseley, Vassilvitskii~(2021) は、学習された双対解による温かいスタートが、双対マッチングのハンガリーの手法の時間的複雑さを改善できることを示した。 コンベックス分析の離散アナログであるtextit{discrete convex analysis} (DCA) を用いて, それらの枠組みを原則的に拡張・改善する。 重み付き完全二成分マッチング,重み付きマトロイド交叉,離散エネルギー最小化をコンピュータビジョンに適用し,dcaベースのフレームワークの有用性を示す。 我々のDCAベースのフレームワークは、予測解から最適解への$\ell_\infty$-distanceに依存する時間複雑性境界を求め、これは以前の$\ell_1$-distance-dependent boundsと比較して2つの利点がある。 また、DCAの観点から原始解と双対解を学習するかについても論じる。

関連論文リスト

• $A^*$ for Graphs of Convex Sets [7.9756690088226145]
  本稿では,既存の凸プログラミングに基づくアプローチを情報と融合して最適性を保証する新しいアルゴリズムを提案する。 我々の方法は$A*$にインスパイアされ、指定された頂点の部分集合から最優先的な手順を開始し、さらなる成長が不可能かつ有益になるまで反復的に拡張する。
  論文  参考訳（メタデータ） (2024-07-24T16:48:32Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization [21.64869023699999]
  本研究では, 試料が逆向きに破壊されたり, 分布が重くなったりした場合に, 分布の平均を高次元で推定する問題について検討する。 メタプロブレムと双対性定理は、高次元におけるロバストで重み付き平均推定に関する新しい統一的な見解をもたらす。
  論文  参考訳（メタデータ） (2020-07-31T04:18:32Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)

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

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