論文の概要: Permutation-Based SGD: Is Random Optimal?

• arxiv url: http://arxiv.org/abs/2102.09718v1
• Date: Fri, 19 Feb 2021 03:14:28 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-22 13:30:24.159473
• Title: Permutation-Based SGD: Is Random Optimal?
• Title（参考訳）: 置換に基づくSGD:ランダム最適か?
• Authors: Shashank Rajput, Kangwook Lee, Dimitris Papailiopoulos
• Abstract要約: 置換に基づくSGDの最近の接地結果の行は、広く観察されている現象を裏付けている: ランダムな置換は、置換サンプリングサンプリングよりも収束を提供する。 このギャップは、私たちがどのような機能であるかに大きく依存し、指数から非存在に変化する可能性があることを示しています。
• 参考スコア（独自算出の注目度）: 11.83842808044211
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent line of ground-breaking results for permutation-based SGD has corroborated a widely observed phenomenon: random permutations offer faster convergence than with-replacement sampling. However, is random optimal? We show that this depends heavily on what functions we are optimizing, and the convergence gap between optimal and random permutations can vary from exponential to nonexistent. We first show that for 1-dimensional strongly convex functions, with smooth second derivatives, there exist optimal permutations that offer exponentially faster convergence compared to random. However, for general strongly convex functions, random permutations are optimal. Finally, we show that for quadratic, strongly-convex functions, there are easy-to-construct permutations that lead to accelerated convergence compared to random. Our results suggest that a general convergence characterization of optimal permutations cannot capture the nuances of individual function classes, and can mistakenly indicate that one cannot do much better than random.
• Abstract（参考訳）: 置換に基づくSGDの画期的な結果の最近のラインは、広く観察されている現象と相関している:ランダムな置換は、置換標本よりも高速収束を提供する。 しかし、ランダムは最適か? これは最適化している関数に大きく依存しており、最適順列とランダム順列の間の収束ギャップは指数関数から非存在まで様々である。 まず、滑らかな第二導関数を持つ1次元強凸函数に対して、ランダムよりも指数関数的に高速収束をもたらす最適な置換が存在することを示す。 しかし、一般的な強凸関数の場合、ランダムな置換が最適である。 最後に, 2次, 強凸関数に対しては, 構築が容易で, ランダムに比較して収束が加速することを示す。 この結果から,最適置換の一般収束特性は個々の関数クラスのニュアンスを捉えることができず,乱数よりもはるかに優れていることを示すことが示唆された。

関連論文リスト

• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
  論文  参考訳（メタデータ） (2024-04-25T17:08:34Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。 我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
  論文  参考訳（メタデータ） (2023-02-28T06:38:05Z)
• High Probability Convergence for Accelerated Stochastic Mirror Descent [29.189409618561964]
  領域の直径に対して最適解への初期距離に依存する境界による高確率収束を示す。 アルゴリズムは標準設定に類似したステップサイズを使用し、リプシッツ関数、滑らかな関数、およびそれらの線形結合に普遍的である。
  論文  参考訳（メタデータ） (2022-10-03T01:50:53Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。 我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。 我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
  論文  参考訳（メタデータ） (2020-04-22T07:47:00Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
  大きな探索空間では、アルゴリズムは関数の最適値に達する前に、いくつかの低関数値領域を通過する。 このコールドスタートフェーズの1つのアプローチは、最適化を加速できる事前知識を使用することである。 本稿では,関数の事前分布を通じて,関数の最適性に関する事前知識を示す。 先行分布は、探索空間を最適関数の高確率領域の周りに拡張し、最適関数の低確率領域の周りに縮小するようにワープする。
  論文  参考訳（メタデータ） (2020-03-27T06:18:49Z)

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

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