論文の概要: Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids
- arxiv url: http://arxiv.org/abs/2511.07504v1
- Date: Wed, 12 Nov 2025 01:01:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-12 20:17:03.371795
- Title: Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids
- Title（参考訳）: 双線形最大化のトラクタブル例:楕円体上のLinUCBの実装
- Authors: Raymond Zhang, Hédi Hadiji, Richard Combes,
- Abstract要約: いくつかの集合に対して、$mathcalX$、例えば$ell_p$ balls with $p>2$に対して、$mathcalP = MathcalNP$ を除いて効率的なアルゴリズムは存在しないことを示す。
我々は、$mathcalX$が中心楕円体である場合、この問題を効率的に解く2つの新しいアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 12.091821597708337
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the maximization of $x^\top θ$ over $(x,θ) \in \mathcal{X} \times Θ$, with $\mathcal{X} \subset \mathbb{R}^d$ convex and $Θ\subset \mathbb{R}^d$ an ellipsoid. This problem is fundamental in linear bandits, as the learner must solve it at every time step using optimistic algorithms. We first show that for some sets $\mathcal{X}$ e.g. $\ell_p$ balls with $p>2$, no efficient algorithms exist unless $\mathcal{P} = \mathcal{NP}$. We then provide two novel algorithms solving this problem efficiently when $\mathcal{X}$ is a centered ellipsoid. Our findings provide the first known method to implement optimistic algorithms for linear bandits in high dimensions.
- Abstract（参考訳）: 我々は、$x^\top θ$ over $(x,θ) \in \mathcal{X} \times >$, with $\mathcal{X} \subset \mathbb{R}^d$ convex and $\subset \mathbb{R}^d$ an ellipsoid の最大化を考える。
学習者は楽観的なアルゴリズムを用いて各ステップで解かなければならない。
まず、ある集合 $\mathcal{X}$ e g $\ell_p$ balls with $p>2$ に対して、$\mathcal{P} = \mathcal{NP}$ がなければ効率的なアルゴリズムは存在しないことを示す。
次に、$\mathcal{X}$ が中心楕円体である場合、この問題を効率的に解く2つの新しいアルゴリズムを提供する。
本研究は,高次元の線形包帯に対する楽観的アルゴリズムの実装法として初めて知られている手法である。
関連論文リスト
- Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model [5.101318208537081]
線形系を解くための準線形時間アルゴリズムについて研究し、$Sz = b$, ここでは$S$は対角的に支配的な行列である。
任意の$u in [n]$に対して、加算誤差のある$z_u$ of $z*_u$を返します。
また、一致する下界を証明し、$S_max$ に対する線型依存が最適であることを示す。
論文 参考訳（メタデータ） (2025-09-16T14:13:31Z) - Linear Bandits on Ellipsoids: Minimax Optimal Algorithms [5.678465386088928]
作用の集合が楕円体であるような計算線形帯域を考える。
この問題に対して、最初の既知のミニマックス最適アルゴリズムを提供する。
実行には、時間$O(dT + d2 log(T/d) + d3)$とメモリ$O(d2)$のみが必要である。
論文 参考訳（メタデータ） (2025-02-24T14:12:31Z) - A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。
また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T14:19:43Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-12-11T17:36:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。