論文の概要: Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization

• arxiv url: http://arxiv.org/abs/2302.00928v1
• Date: Thu, 2 Feb 2023 08:00:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-03 14:57:23.455076
• Title: Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization
• Title（参考訳）: 予測によるウォームスタートの再検討:より高速な$\text{l}$-/$\text{l}^\natural$-convex関数最小化のための最適解のセットに近い学習予測
• Authors: Shinsaku Sakaue and Taihei Oki
• Abstract要約: 新たな研究のラインでは、マシンが学習した予測は、二部マッチングのような離散最適化問題に対するアルゴリズムのウォームスタートに有用である。 我々のフレームワークは、予測と全ての最適解の間の距離に比例した境界を提供する。 したがって、複数の最適解によらず、アルゴリズムを確実にウォームスタートさせることができる予測の初回学習性を与える。
• 参考スコア（独自算出の注目度）: 15.191184049312467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An emerging line of work has shown that machine-learned predictions are useful to warm-start algorithms for discrete optimization problems, such as bipartite matching. Previous studies have shown time complexity bounds proportional to some distance between a prediction and an optimal solution, which we can approximately minimize by learning predictions from past optimal solutions. However, such guarantees may not be meaningful when multiple optimal solutions exist. Indeed, the dual problem of bipartite matching and, more generally, $\text{L}$-/$\text{L}^\natural$-convex function minimization have arbitrarily many optimal solutions, making such prediction-dependent bounds arbitrarily large. To resolve this theoretically critical issue, we present a new warm-start-with-prediction framework for $\text{L}$-/$\text{L}^\natural$-convex function minimization. Our framework offers time complexity bounds proportional to the distance between a prediction and the set of all optimal solutions. The main technical difficulty lies in learning predictions that are provably close to sets of all optimal solutions, for which we present an online-gradient-descent-based method. We thus give the first polynomial-time learnability of predictions that can provably warm-start algorithms regardless of multiple optimal solutions.
• Abstract（参考訳）: 機械学習による予測は、二成分マッチングのような離散最適化問題に対するウォームスタートアルゴリズムに有用であることを示した。 従来の研究では、予測と最適解の間の距離に比例した時間複雑性が示されており、過去の最適解から予測を学習することで、ほぼ最小化することができる。 しかし、複数の最適解が存在する場合、そのような保証は意味をなさない。 実際、二部マッチングの双対問題とより一般的には、$\text{L}$-/$\text{L}^\natural$-convex関数の最小化は任意に多くの最適解を持ち、そのような予測依存境界は任意に大きい。 この理論的に重要な問題を解決するために、$\text{L}$-/$\text{L}^\natural$-convex関数最小化のための新しいウォームスタート予測フレームワークを提案する。 我々のフレームワークは、予測と最適解の集合の間の距離に比例した時間複雑性を提供する。 主な技術的困難は、オンラインの漸進的未熟な方法を示す最適解の集合に確実に近い予測を学習することにある。 したがって、複数の最適解によらず、確実にウォームスタートアルゴリズムを実現できる予測の多項式時間学習性を与える。

関連論文リスト

• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
  論文  参考訳（メタデータ） (2024-11-25T17:31:34Z)
• Online Convex Optimization with Memory and Limited Predictions [19.7248150754102]
  メモリと予測によるオンライン凸最適化の問題点を水平線上で検討する。 本稿では,この問題を解くアルゴリズムを提案し,予測ウィンドウ長とともにアルゴリズムの動的後悔が指数関数的に減衰することを示す。
  論文  参考訳（メタデータ） (2024-10-31T02:33:47Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Faster Matchings via Learned Duals [31.61057940283721]
  機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。 まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。 第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
  論文  参考訳（メタデータ） (2021-07-20T21:11:09Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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