論文の概要: An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

• arxiv url: http://arxiv.org/abs/2004.04250v1
• Date: Wed, 8 Apr 2020 20:56:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-15 08:27:17.615771
• Title: An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
• Title（参考訳）: 凸最適化のための改良された切削面法,凸凸ゲームとその応用
• Authors: Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong
• Abstract要約: 本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。 また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
• 参考スコア（独自算出の注目度）: 28.54236118020831
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Given a separation oracle for a convex set $K \subset \mathbb{R}^n$ that is contained in a box of radius $R$, the goal is to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$. We propose a new cutting plane algorithm that uses an optimal $O(n \log (\kappa))$ evaluations of the oracle and an additional $O(n^2)$ time per evaluation, where $\kappa = nR/\epsilon$. $\bullet$ This improves upon Vaidya's $O( \text{SO} \cdot n \log (\kappa) + n^{\omega+1} \log (\kappa))$ time algorithm [Vaidya, FOCS 1989a] in terms of polynomial dependence on $n$, where $\omega < 2.373$ is the exponent of matrix multiplication and $\text{SO}$ is the time for oracle evaluation. $\bullet$ This improves upon Lee-Sidford-Wong's $O( \text{SO} \cdot n \log (\kappa) + n^3 \log^{O(1)} (\kappa))$ time algorithm [Lee, Sidford and Wong, FOCS 2015] in terms of dependence on $\kappa$. For many important applications in economics, $\kappa = \Omega(\exp(n))$ and this leads to a significant difference between $\log(\kappa)$ and $\mathrm{poly}(\log (\kappa))$. We also provide evidence that the $n^2$ time per evaluation cannot be improved and thus our running time is optimal. A bottleneck of previous cutting plane methods is to compute leverage scores, a measure of the relative importance of past constraints. Our result is achieved by a novel multi-layered data structure for leverage score maintenance, which is a sophisticated combination of diverse techniques such as random projection, batched low-rank update, inverse maintenance, polynomial interpolation, and fast rectangular matrix multiplication. Interestingly, our method requires a combination of different fast rectangular matrix multiplication algorithms.
• Abstract（参考訳）: 凸集合 $K \subset \mathbb{R}^n$ が半径 $R$ の箱に含まれるような分離オラクルが与えられた場合、その目標は、K$ の点を計算するか、または、$K$ が半径 $\epsilon$ の球を含まないことを証明することである。 そこで我々は,最適な$O(n \log (\kappa))$評価と追加の$O(n^2)$評価を用いる切削平面アルゴリズムを提案し,$\kappa = nR/\epsilon$とする。 vaidya の $o( \text{so} \cdot n \log (\kappa) + n^{\omega+1} \log (\kappa))$ time アルゴリズム [vaidya, focs 1989a] $n$ の多項式依存性の観点から、$\omega < 2.373$ は行列の乗算の指数、$\text{so}$ は oracle の評価の時間である。 $\bullet$ これは、$\kappa$への依存の観点から、Lee-Sidford-Wong氏の$O( \text{SO} \cdot n \log (\kappa) + n^3 \log^{O(1)} (\kappa))$ time algorithm [Lee, Sidford and Wong, FOCS 2015]を改善する。 経済学における多くの重要な応用に対して、$\kappa = \Omega(\exp(n))$ は $\log(\kappa)$ と $\mathrm{poly}(\log (\kappa))$ の間に大きな違いをもたらす。 また,評価当たりのn^2$時間の改善が不可能であり,実行時間が最適であることを示す。 以前の切断平面法のボトルネックは、過去の制約の相対的重要性の尺度であるレバレッジスコアを計算することである。 この結果は,ランダムプロジェクション,バッチ化低ランク更新,逆メンテナンス,多項式補間,高速長方行列乗算など,多種多様な手法を組み合わせた新しい多層データ構造によって実現されている。 興味深いことに、この方法は異なる高速矩形行列乗算アルゴリズムの組み合わせを必要とする。

関連論文リスト

• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Faster Stochastic Algorithms for Minimax Optimization under Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
  我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。 SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
  論文  参考訳（メタデータ） (2023-07-29T02:26:31Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。 我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
  論文  参考訳（メタデータ） (2022-12-29T19:26:12Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
  本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。 簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
  論文  参考訳（メタデータ） (2021-06-15T11:21:06Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。 この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
  論文  参考訳（メタデータ） (2021-03-18T15:12:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Improved quantum algorithm for A-optimal projection [4.248054546466641]
  本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。 我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
  論文  参考訳（メタデータ） (2020-06-10T09:31:53Z)

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

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