論文の概要: Online Multiserver Convex Chasing and Optimization

• arxiv url: http://arxiv.org/abs/2004.07346v1
• Date: Wed, 15 Apr 2020 21:17:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 04:14:51.620834
• Title: Online Multiserver Convex Chasing and Optimization
• Title（参考訳）: オンライン・マルチサーバ・凸追跡と最適化
• Authors: S\'ebastien Bubeck, Yuval Rabani, Mark Sellke
• Abstract要約: 競合するオンラインアルゴリズムは存在しており、その上、非次元の競合比も示している。 消滅する後悔を達成することは可能だが、トップワンのアクションケースとは異なり、消滅率は強い凸関数ではスピードアップしない。 我々は,情報理論の議論を通じて,線形損失に対する無次元後悔を証明した。
• 参考スコア（独自算出の注目度）: 4.3411150520024115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the problem of $k$-chasing of convex functions, a simultaneous generalization of both the famous k-server problem in $R^d$, and of the problem of chasing convex bodies and functions. Aside from fundamental interest in this general form, it has natural applications to online $k$-clustering problems with objectives such as $k$-median or $k$-means. We show that this problem exhibits a rich landscape of behavior. In general, if both $k > 1$ and $d > 1$ there does not exist any online algorithm with bounded competitiveness. By contrast, we exhibit a class of nicely behaved functions (which include in particular the above-mentioned clustering problems), for which we show that competitive online algorithms exist, and moreover with dimension-free competitive ratio. We also introduce a parallel question of top-$k$ action regret minimization in the realm of online convex optimization. There, too, a much rougher landscape emerges for $k > 1$. While it is possible to achieve vanishing regret, unlike the top-one action case the rate of vanishing does not speed up for strongly convex functions. Moreover, vanishing regret necessitates both intractable computations and randomness. Finally we leave open whether almost dimension-free regret is achievable for $k > 1$ and general convex losses. As evidence that it might be possible, we prove dimension-free regret for linear losses via an information-theoretic argument.
• Abstract（参考訳）: 本稿では、凸関数の$k$-chasingの問題、有名なkサーバ問題を$R^d$で同時に一般化すること、および凸体や関数を追尾する問題を紹介する。 この一般的な形式に対する基本的な関心とは別に、$k$-medianや$k$-meansのような目的を持ったオンラインの$k$-clustering問題への自然な応用がある。 この問題は行動の豊かな景観を示している。 一般に、$k > 1$ と $d > 1$ の両方が有界な競合性を持つオンラインアルゴリズムは存在しない。 これとは対照的に、優れた振る舞いをする関数(特に上記のクラスタリング問題を含む)のクラスを示し、競争力のあるオンラインアルゴリズムの存在を示し、さらに次元のない競争比率を示す。 また,オンライン凸最適化の分野では,最大$k$アクション後悔最小化という並列問題も導入する。 さらには、$k > 1$という、より粗いランドスケープも出現する。 後悔を消失させることは可能であるが、トップワンのアクションケースとは異なり、消失の速度は強い凸関数に対して加速しない。 さらに、失う後悔は、難解な計算とランダム性の両方を必要とします。 最後に、ほぼ次元のない後悔が、k > 1$ と一般凸損失で達成可能かどうかを明記する。 可能かもしれないという証拠として、情報理論的な議論を通じて線形損失に対する次元フリーな後悔を証明する。

関連論文リスト

• On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
  滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。 この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-11-21T22:06:25Z)
• No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting [23.188831772813103]
  オンラインM$natural$-concave関数問題について検討し,Murota と Shioura (1999) によるインタラクティブ版について検討した。 バンドイット設定では、$O(T-1/2)$-simple regretと$O(T2/3)$-regretアルゴリズムを、M$natural$-concave関数のノイズ値オーラクルに$T$倍のアクセスで提示する。 完全な情報フィードバックであっても,ラウンド毎に実行されたアルゴリズムは,任意の一定の$cに対して,O(T1-c)$後悔を達成できないことを証明しています。
  論文  参考訳（メタデータ） (2024-05-21T01:31:44Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Dueling Convex Optimization with General Preferences [85.14061196945599]
  本研究の目的は, エンフィロンリングフィードバックの弱い形を条件として, 凸関数を最小化することである。 我々の主な貢献は、滑らかな凸対象関数に対する収束$smashwidetilde O(epsilon-4p)$と、その目的が滑らかで凸であるときに効率$smashwidetilde O(epsilon-2p)を持つ効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2022-09-27T11:10:41Z)
• Chasing Convex Bodies and Functions with Black-Box Advice [7.895232155155041]
  ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。 オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。 本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-23T15:30:55Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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