論文の概要: On the Comparison between Cyclic Sampling and Random Reshuffling

• arxiv url: http://arxiv.org/abs/2104.12112v1
• Date: Sun, 25 Apr 2021 09:29:43 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 14:22:00.418617
• Title: On the Comparison between Cyclic Sampling and Random Reshuffling
• Title（参考訳）: 循環サンプリングとランダム再シャッフルの比較について
• Authors: Xinmeng Huang, Kun Yuan, Xianghui Mao, Wotao Yin
• Abstract要約: 周期的なサンプリングは、サンプルを周期的に再シャッフルするよりも頑丈でない、固定された循環的な順序でサンプルを引き出す。 既存の研究は、循環サンプリングにおける最悪のケース収束率を確立しており、一般にランダムリシャフリングよりも悪い。 本論文では,リシャッフルよりも一定の周期順序の方がはるかに早く,低コストで発見できることを発見した。
• 参考スコア（独自算出の注目度）: 27.27774034428748
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When applying a stochastic/incremental algorithm, one must choose the order to draw samples. Among the most popular approaches are cyclic sampling and random reshuffling, which are empirically faster and more cache-friendly than uniform-iid-sampling. Cyclic sampling draws the samples in a fixed, cyclic order, which is less robust than reshuffling the samples periodically. Indeed, existing works have established worst case convergence rates for cyclic sampling, which are generally worse than that of random reshuffling. In this paper, however, we found a certain cyclic order can be much faster than reshuffling and one can discover it at a low cost! Studying and comparing different sampling orders typically require new analytic techniques. In this paper, we introduce a norm, which is defined based on the sampling order, to measure the distance to solution. Applying this technique on proximal Finito/MISO algorithm allows us to identify the optimal fixed ordering, which can beat random reshuffling by a factor up to log(n)/n in terms of the best-known upper bounds. We also propose a strategy to discover the optimal fixed ordering numerically. The established rates are state-of-the-art compared to previous works.
• Abstract（参考訳）: 確率/増分アルゴリズムを適用する場合、サンプルを描く順序を選択する必要がある。 最も一般的なアプローチは循環サンプリングとランダムリシャッフルであり、一様イドサンプリングよりも経験的に高速でキャッシュフレンドリーである。 周期的なサンプリングは、サンプルを周期的に再シャッフルするよりも頑丈でない、固定された循環的な順序でサンプルを引き出す。 実際、既存の研究は循環サンプリングにおける最悪のケース収束率を確立しており、これは一般にランダムリシャフリングよりも悪い。 しかし,本論文では,ある周期順序はリシャッフルよりもはるかに高速であり,低コストで発見できることがわかった。 異なるサンプリング順序の研究と比較は、通常、新しい分析技術を必要とする。 本稿では, 解までの距離を測定するために, サンプリング順序に基づいて定義されるノルムを提案する。 この手法を近似Finito/MISOアルゴリズムに適用することにより、最適な固定順序付けを特定できる。 また,最適な固定順序を数値的に発見する戦略を提案する。 定価は前作に比べて最先端である。

関連論文リスト

• Sampling in CMA-ES: Low Numbers of Low Discrepancy Points [0.0]
  低差点の小さい固定集合を反復することで、デフォルトの均一分布よりも優れた性能が得られることを示す。 より低次元の場合、32個の特異な差分点を用いると、一様サンプリングよりも近いあるいは良い結果が得られる。
  論文  参考訳（メタデータ） (2024-09-24T10:04:55Z)
• Stochastic optimization with arbitrary recurrent data sampling [2.1485350418225244]
  最も一般的に使われているデータサンプリングアルゴリズムは、軽度な仮定の下にある。 特定のクラスの繰り返し最適化アルゴリズムに対して、他のプロパティは不要であることを示す。 我々は,データセットをカバーするサンプリングアルゴリズムを選択することで,収束を加速できることを示す。
  論文  参考訳（メタデータ） (2024-01-15T14:04:50Z)
• Stable generative modeling using Schrödinger bridges [0.22499166814992438]
  本稿では,Schr"odinger BridgesとLangevin dynamicsを組み合わせた生成モデルを提案する。 我々のフレームワークは自然に条件付きサンプルを生成し、ベイズ推論問題に拡張することができる。
  論文  参考訳（メタデータ） (2024-01-09T06:15:45Z)
• Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization [12.794526174053134]
  滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。 このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
  論文  参考訳（メタデータ） (2022-06-07T00:37:37Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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