論文の概要: Lazy Online Gradient Descent is Universal on Polytopes

• arxiv url: http://arxiv.org/abs/2004.01739v2
• Date: Wed, 31 Aug 2022 13:32:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 04:01:06.371162
• Title: Lazy Online Gradient Descent is Universal on Polytopes
• Title（参考訳）: 怠け者のオンライングラディエントDescentはポリトープで普遍的
• Authors: Daron Anderson and Douglas Leith
• Abstract要約: ポリトープドメイン上では、よく知られたLazy Online Gradient Descentアルゴリズムが普遍的であることを証明している。 つまり、i.i.d の相手に対して$O(1)$の擬似レグレットを得ると同時に、よく知られた$O(sqrt N)$最悪の後悔境界を達成できる。
• 参考スコア（独自算出の注目度）: 1.2691047660244335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the familiar Lazy Online Gradient Descent algorithm is universal on polytope domains. That means it gets $O(1)$ pseudo-regret against i.i.d opponents, while simultaneously achieving the well-known $O(\sqrt N)$ worst-case regret bound. For comparison the bulk of the literature focuses on variants of the Hedge (exponential weights) algorithm on the simplex. These can in principle be lifted to general polytopes; however the process is computationally unfeasible for many important classes where the number of vertices grows quickly with the dimension. The lifting procedure also ignores any Euclidean bounds on the cost vectors, and can create extra factors of dimension in the pseudo-regret bound. Gradient Descent is simpler than the handful of purpose-built algorithms for polytopes in the literature, and works in a broader setting. In particular existing algorithms assume the optimiser is unique, while our bound allows for several optimal vertices.
• Abstract（参考訳）: ポリトープドメイン上では、よく知られたLazy Online Gradient Descentアルゴリズムが普遍的であることを示す。 つまり、i.i.d の対戦相手に対して $o(1)$ pseudo-regret を得ると同時に、よく知られた $o(\sqrt n)$ worst-case regret bound を同時に達成する。 比較のために、多くの文献はシンプレックス上のヘッジ(指数重み)アルゴリズムの変種に焦点を当てている。 これらは原則として一般のポリトープに持ち上げられるが、この過程は次元とともに頂点数が急速に増加する多くの重要なクラスでは計算不可能である。 昇降手順はコストベクトル上のユークリッド境界も無視し、擬回帰境界において余分な次元の因子を生成できる。 Gradient Descentは、文学におけるポリトープのための少数のアルゴリズムよりもシンプルで、より広い環境で機能する。 特に既存のアルゴリズムはオプティマイザが一意であると仮定し、我々の境界はいくつかの最適頂点を許容する。

関連論文リスト

• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  ユークリッド空間における集合の被覆数について上限を証明する。 ここでは、イムディン・コントによる最もよく知られた一般境界が改善されることが示される。 本稿では,3つの計算応用における結果のパワーについて説明する。
  論文  参考訳（メタデータ） (2023-11-09T03:06:59Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Frank Wolfe Meets Metric Entropy [0.0]
  フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。 次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。 また、核標準球にもこの現象が成立する。
  論文  参考訳（メタデータ） (2022-05-17T21:23:36Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Complexity of Linear Minimization and Projection on Some Sets [33.53609344219565]
  Frank-Wolfeアルゴリズムは、プロジェクションではなく線形最小化に依存する制約付き最適化の手法である。 本稿では、最適化によく用いられる複数の集合上の両タスクの複雑性境界について検討する。
  論文  参考訳（メタデータ） (2021-01-25T12:14:34Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
  論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
  論文  参考訳（メタデータ） (2020-02-11T23:06:09Z)

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

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