論文の概要: Recht-R\'e Noncommutative Arithmetic-Geometric Mean Conjecture is False
- arxiv url: http://arxiv.org/abs/2006.01510v1
- Date: Tue, 2 Jun 2020 10:34:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 23:52:53.529591
- Title: Recht-R\'e Noncommutative Arithmetic-Geometric Mean Conjecture is False
- Title(参考訳): Recht-R\'e Noncommutative Arithmetic-Geometric Mean Conjecture is False
- Authors: Zehua Lai and Lek-Heng Lim
- Abstract要約: 予想されたRecht-R'eの不等式は一般の$n$に対して偽であることを示す。
我々のアプローチは非可換ポシティフサッツに依存している。
- 参考スコア(独自算出の注目度): 10.051309746913512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic optimization algorithms have become indispensable in modern
machine learning. An unresolved foundational question in this area is the
difference between with-replacement sampling and without-replacement sampling
-- does the latter have superior convergence rate compared to the former? A
groundbreaking result of Recht and R\'e reduces the problem to a noncommutative
analogue of the arithmetic-geometric mean inequality where $n$ positive numbers
are replaced by $n$ positive definite matrices. If this inequality holds for
all $n$, then without-replacement sampling indeed outperforms with-replacement
sampling. The conjectured Recht-R\'e inequality has so far only been
established for $n = 2$ and a special case of $n = 3$. We will show that the
Recht-R\'e conjecture is false for general $n$. Our approach relies on the
noncommutative Positivstellensatz, which allows us to reduce the conjectured
inequality to a semidefinite program and the validity of the conjecture to
certain bounds for the optimum values, which we show are false as soon as $n =
5$.
- Abstract(参考訳): 確率最適化アルゴリズムは現代の機械学習では不可欠である。
この領域における解決されていない基礎的な疑問は、非置換サンプリングと無置換サンプリングの違いである。
Recht と R\'e の画期的な結果は、この問題を算術幾何学的平均不等式の不等式(英語版)の非可換な類似に還元し、$n$正の数値を$n$正の定値行列に置き換える。
もしこの不等式がすべての$n$ に対して成り立つなら、no-replacement samplingはwith-replacement samplingよりも優れている。
予想されるRecht-R\'eの不等式は、これまでのところ$n = 2$と$n = 3$の特別な場合のみ確立されている。
recht-r\'e 予想は一般の $n$ に対して偽であることを示す。
このアプローチは非可換なポジティヴシュテルナッツ(英語版)に依存しており、これは予想の不等式を半定値のプログラムに還元し、予想を最適値の特定の境界に妥当性を与えることができる。
関連論文リスト
- Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳(メタデータ) (2024-06-04T15:23:29Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳(メタデータ) (2024-03-15T23:36:55Z) - LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳(メタデータ) (2024-03-05T18:59:47Z) - Efficient Unbiased Sparsification [0.0]
ベクトル $pin mathbbRn$ の非バイアス付き $m$-スパーシフィケーション(unbiased $m$-sparsification of a vector $pin mathbbRn$)は、無作為なベクトル $Qin mathbbRn$ であり、平均 $p$ は少なくとも $mn$ でない座標を持つ。
本研究の主な成果は、置換不変あるいは加法的に分離可能な異種に対する効率的な非偏平スパーシフィケーションである。
論文 参考訳(メタデータ) (2024-02-22T19:15:50Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳(メタデータ) (2022-07-13T16:09:29Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳(メタデータ) (2022-05-26T15:55:44Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳(メタデータ) (2021-10-25T02:53:24Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-01T14:10:38Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳(メタデータ) (2020-11-21T01:33:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。