論文の概要: Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting

• arxiv url: http://arxiv.org/abs/2202.02406v1
• Date: Fri, 4 Feb 2022 21:56:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-08 18:49:56.405091
• Title: Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting
• Title（参考訳）: ユニバーサルコインベッティングによるサイド情報を用いたパラメータフリーオンライン線形最適化
• Authors: J. Jon Ryu, Alankrita Bhatt, Young-Han Kim
• Abstract要約: パラメータフリーオンライン線形最適化アルゴリズムのクラスを提案する。 彼らは、いくつかの側情報を適用することによって、敵列の構造を利用する。 提案アルゴリズムは、全ての適応アルゴリズムに対して最高の性能を達成するためにさらに改良されている。
• 参考スコア（独自算出の注目度）: 21.584183030149084
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and P{\'a}l (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.
• Abstract（参考訳）: パラメータフリーオンライン線形最適化アルゴリズムのクラスは、ある側情報に適応することで、逆列の構造を利用する。 これらのアルゴリズムは、オンライン線形最適化のためのコインベッティングアルゴリズムと、シーケンシャルサイド情報をコインベッティングに組み込む情報理論におけるユニバーサル圧縮技術に適応するためのOlabona と P{\'a}l (2016) の還元手法を組み合わせたものである。 具体的な例としては、辺情報が木構造を持ち、固定次数や可変次マルコフの場合を含む、逆数列の前のシンボルの量子化値からなる。 willems, shtarkov, tjalkens (1995) の文脈木重み付け手法を改良することにより, 提案アルゴリズムを改良し, 与えられた最大次数の木構造側情報を含む全ての適応アルゴリズムに対して, 最適性能を計算効率良く達成する。

関連論文リスト

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization [33.38582292895673]
  完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 これを用いて、一般メタアルゴリズムを記述し、決定論的アルゴリズムを同様の後悔境界を持つゼロ次アルゴリズムに変換する。
  論文  参考訳（メタデータ） (2024-02-13T17:42:27Z)
• Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm [0.589889361990138]
  そこで我々は,このクラスに緩和型近似アルゴリズムが存在するという自然な仮定の下で,新しいミートアラウンドアルゴリズムを提案する。 私たちのアルゴリズムは理論的にも実用的にもはるかに効率的です。
  論文  参考訳（メタデータ） (2023-10-19T10:22:03Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version] [56.94699829208978]
  本稿では,動的システムのスマートでスケーラブルな抽象化のための適応的洗練手順を提案する。 最適構造を学ぶために、マルコフ連鎖の間のカントロビッチに着想を得た計量を定義する。 本稿では,従来の線形プログラミング手法よりも計算量が多くなることを示す。
  論文  参考訳（メタデータ） (2023-03-30T11:26:40Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning [3.0204520109309843]
  機械学習における連続最適化問題に対処する一階法と二階法を考察する。 一階述語の場合、半決定論的から二次正規化への遷移の枠組みを提案する。 本稿では,適応的なサンプリングと適応的なステップサイズを持つ新しい1次アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-29T18:10:00Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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