論文の概要: Pseudonorm Approachability and Applications to Regret Minimization
- arxiv url: http://arxiv.org/abs/2302.01517v1
- Date: Fri, 3 Feb 2023 03:19:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-06 17:41:35.991254
- Title: Pseudonorm Approachability and Applications to Regret Minimization
- Title（参考訳）: 擬似ノルムアプローチとレグレット最小化への応用
- Authors: Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider,
Balasubramanian Sivan
- Abstract要約: 我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
- 参考スコア（独自算出の注目度）: 73.54127663296906
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Blackwell's celebrated approachability theory provides a general framework
for a variety of learning problems, including regret minimization. However,
Blackwell's proof and implicit algorithm measure approachability using the
$\ell_2$ (Euclidean) distance. We argue that in many applications such as
regret minimization, it is more useful to study approachability under other
distance metrics, most commonly the $\ell_\infty$-metric. But, the time and
space complexity of the algorithms designed for $\ell_\infty$-approachability
depend on the dimension of the space of the vectorial payoffs, which is often
prohibitively large. Thus, we present a framework for converting
high-dimensional $\ell_\infty$-approachability problems to low-dimensional
pseudonorm approachability problems, thereby resolving such issues. We first
show that the $\ell_\infty$-distance between the average payoff and the
approachability set can be equivalently defined as a pseudodistance between a
lower-dimensional average vector payoff and a new convex set we define. Next,
we develop an algorithmic theory of pseudonorm approachability, analogous to
previous work on approachability for $\ell_2$ and other norms, showing that it
can be achieved via online linear optimization (OLO) over a convex set given by
the Fenchel dual of the unit pseudonorm ball. We then use that to show, modulo
mild normalization assumptions, that there exists an
$\ell_\infty$-approachability algorithm whose convergence is independent of the
dimension of the original vectorial payoff. We further show that that algorithm
admits a polynomial-time complexity, assuming that the original
$\ell_\infty$-distance can be computed efficiently. We also give an
$\ell_\infty$-approachability algorithm whose convergence is logarithmic in
that dimension using an FTRL algorithm with a maximum-entropy regularizer.
- Abstract（参考訳）: ブラックウェルの有望なアプローチ可能性理論は、後悔の最小化を含む様々な学習問題の一般的な枠組みを提供する。
しかし、ブラックウェルの証明と暗黙のアルゴリズムは、$\ell_2$ (ユークリッド)距離を用いてアプローチ可能性を測定する。
後悔の最小化のような多くの応用において、他の距離メトリクス(最も一般的には$\ell_\infty$-metric)の下でアプローチ可能性を研究することがより有用であると主張する。
しかし、$\ell_\infty$-approachabilityのために設計されたアルゴリズムの時間と空間の複雑さは、しばしば禁止的に大きいベクトル的ペイオフの空間の次元に依存する。
そこで本稿では,高次元$\ell_\infty$-approachability問題を低次元疑似ノルムアプローチ可能性問題に変換する枠組みを提案する。
まず、平均ペイオフと接近可能性セットの間の$\ell_\infty$- distance を、我々が定義する低次元平均ベクトルペイオフと新しい凸集合の間の擬似距離として等価に定義できることを示す。
次に,$\ell_2$ などのノルムに対するアプローチ可能性に関する従来の研究と類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発し,単位疑似ノルムボールのフェンシェル双対によって与えられる凸集合上のオンライン線形最適化 (olo) によって実現可能であることを示した。
次に、モジュロ弱正規化仮定(modulo mild normalization assumptions)を用いて、元のベクトルペイオフの次元に依存しない$\ell_\infty$-approachabilityアルゴリズムが存在することを示す。
さらに、元の$\ell_\infty$-distanceを効率的に計算できると仮定して、このアルゴリズムが多項式時間複雑性を持つことを示す。
また、最大エントロピー正規化器を持つFTRLアルゴリズムを用いて、その次元における収束が対数である$\ell_\infty$-approachabilityアルゴリズムを提案する。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Differentiable Linear Bandit Algorithm [6.849358422233866]
アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。
勾配上昇による信頼度を学習できる勾配推定器を導入する。
提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
論文 参考訳（メタデータ） (2020-06-04T16:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。