論文の概要: Chasing Convex Bodies and Functions with Black-Box Advice
- arxiv url: http://arxiv.org/abs/2206.11780v1
- Date: Thu, 23 Jun 2022 15:30:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-24 16:12:17.714469
- Title: Chasing Convex Bodies and Functions with Black-Box Advice
- Title（参考訳）: ブラックボックスアドバイスによる凸体追尾と機能
- Authors: Nicolas Christianson, Tinashe Handina, Adam Wierman
- Abstract要約: ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。
オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。
本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 7.895232155155041
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of convex function chasing with black-box advice,
where an online decision-maker aims to minimize the total cost of making and
switching between decisions in a normed vector space, aided by black-box advice
such as the decisions of a machine-learned algorithm. The decision-maker seeks
cost comparable to the advice when it performs well, known as
$\textit{consistency}$, while also ensuring worst-case $\textit{robustness}$
even when the advice is adversarial. We first consider the common paradigm of
algorithms that switch between the decisions of the advice and a competitive
algorithm, showing that no algorithm in this class can improve upon
3-consistency while staying robust. We then propose two novel algorithms that
bypass this limitation by exploiting the problem's convexity. The first,
INTERP, achieves $(\sqrt{2}+\epsilon)$-consistency and
$\mathcal{O}(\frac{C}{\epsilon^2})$-robustness for any $\epsilon > 0$, where
$C$ is the competitive ratio of an algorithm for convex function chasing or a
subclass thereof. The second, BDINTERP, achieves $(1+\epsilon)$-consistency and
$\mathcal{O}(\frac{CD}{\epsilon})$-robustness when the problem has bounded
diameter $D$. Further, we show that BDINTERP achieves near-optimal
consistency-robustness trade-off for the special case where cost functions are
$\alpha$-polyhedral.
- Abstract（参考訳）: 我々は,オンライン意思決定者が,標準ベクトル空間における意思決定と切り換えのコストを最小化することを目的とした,ブラックボックスアドバイスによる凸関数追跡の問題について考察する。
意思決定者は、$\textit{consistency}$として知られる、うまく機能するときにアドバイスに匹敵するコストを求めると同時に、アドバイスが敵対的である場合でも最悪の場合$\textit{robustness}$を保証する。
まず,提案の判断と競争アルゴリズムを切り替えるアルゴリズムの共通パラダイムを考察し,このクラスでは頑健なまま3-consistencyではアルゴリズムが改善できないことを示した。
次に,この問題の凸性を利用した2つの新しいアルゴリズムを提案する。
最初の interp は、任意の $\epsilon > 0$ に対して $(\sqrt{2}+\epsilon)$-consistency と $\mathcal{o}(\frac{c}{\epsilon^2})$-robustness を達成する。
2つめのbdinterpは、1+\epsilon)$-consistencyと$\mathcal{o}(\frac{cd}{\epsilon})$-robustnessを達成する。
さらに,BDINTERPは,コスト関数が$\alpha$-polyhedralである特別な場合に対して,ほぼ最適の整合性-損耗性トレードオフを実現することを示す。
関連論文リスト
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
論文 参考訳（メタデータ） (2021-10-22T11:49:15Z) - 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) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。