論文の概要: Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

• arxiv url: http://arxiv.org/abs/2006.04299v3
• Date: Sat, 2 Oct 2021 21:29:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 02:18:13.275602
• Title: Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis
• Title（参考訳）: 大規模モデルのハルティング時間は予測可能である:普遍性特性と平均ケース解析
• Authors: Courtney Paquette, Bart van Merri\"enboer, Elliot Paquette, Fabian Pedregosa
• Abstract要約: 最悪のケース分析と比較して、平均ケース分析はアルゴリズムの典型的な振る舞いをよりよく表す。 これは、一階法で訓練された大規模問題のクラスには当てはまらないことを示す。 数値シミュレーションは、この普遍性はアルゴリズムと問題のより一般的なクラスに当てはまることを示唆している。
• 参考スコア（独自算出の注目度）: 14.863027146736696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show that this is not the case for a class of large-scale problems trained with first-order methods including random least squares and one-hidden layer neural networks with random weights. In fact, the halting time exhibits a universality property: it is independent of the probability distribution. With this barrier for average-case analysis removed, we provide the first explicit average-case convergence rates showing a tighter complexity not captured by traditional worst-case analysis. Finally, numerical simulations suggest this universality property holds for a more general class of algorithms and problems.
• Abstract（参考訳）: 平均ケース解析は、全ての可能な入力に対して平均化されたアルゴリズムの複雑さを計算する。 最悪のケース解析と比較すると、アルゴリズムの典型的な振る舞いをよりよく表すが、最適化においてほとんど探索されていない。 1つの困難は、解析がモデルに対する入力の確率分布に依存することである。 しかし、これはランダムな最小二乗法やランダムな重み付き一重層ニューラルネットワークを含む一階法で訓練された大規模な問題には当てはまらない。 実際、停止時間は普遍性特性を示し、確率分布とは独立である。 この平均ケース解析の障壁を除去することで、従来の最悪のケース解析では得られないより厳密な複雑さを示す最初の明示的な平均ケース収束率を提供する。 最後に、数値シミュレーションは、この普遍性がより一般的なアルゴリズムと問題のクラスをもたせることを示唆する。

関連論文リスト

• A Note on High-Probability Analysis of Algorithms with Exponential, Sub-Gaussian, and General Light Tails [34.465259431606405]
  このようなアルゴリズムの解析はブラックボックス方式で削減でき、対数係数の損失はわずかである。 このアプローチは指数関数、準ガウス分布、より一般的な高速分解分布を含む任意の光尾ランダム化にも同時に適用される。
  論文  参考訳（メタデータ） (2024-03-05T11:38:20Z)
• A Provably Accurate Randomized Sampling Algorithm for Logistic Regression [2.7930955543692817]
  本稿では,ロジスティック回帰問題に対する単純なランダム化サンプリングに基づくアルゴリズムを提案する。 正確な近似は、観測総数よりもはるかに小さい試料で達成できることを示す。 概して、ロジスティック回帰における推定確率を効率的に近似するためにランダム化サンプリング手法を用いる可能性に光を当てている。
  論文  参考訳（メタデータ） (2024-02-26T06:20:28Z)
• Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima [12.009357100208353]
  本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。 EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
  論文  参考訳（メタデータ） (2023-10-06T06:32:07Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions [42.6763105645717]
  少数の破損したサンプルが与えられた場合、ゴールは確率の高い$mu$を正確に近似する仮説を効率的に計算することである。 本アルゴリズムは, 周辺次元と対数的にスケーリングするサンプルを多数使用して, 最適誤差を実現する。 我々の分析は、ある空間特性を満たす正の半定値に対する(非スペクトル)分解の繊細な設計を含む、独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2022-11-29T16:13:50Z)
• A Novel Convergence Analysis for Algorithms of the Adam Family [105.22760323075008]
  本稿ではAdam, AMSGrad, AdaboundなどのAdamスタイルの手法群に対する収束の一般的な証明を示す。 我々の分析は非常に単純で汎用的なので、より広範な非構成最適化問題の族を解くための収束を確立するために利用することができる。
  論文  参考訳（メタデータ） (2021-12-07T02:47:58Z)
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition [34.235007566913396]
  ラベルに関連付けられた用語への分散の解釈可能で対称的な分解について述べる。 バイアスはネットワーク幅とともに単調に減少するが、分散項は非単調な振る舞いを示す。 我々はまた、著しく豊かな現象論も分析する。
  論文  参考訳（メタデータ） (2020-11-04T21:04:02Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• 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)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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