論文の概要: Automatically Bounding the Taylor Remainder Series: Tighter Bounds and New Applications

• arxiv url: http://arxiv.org/abs/2212.11429v2
• Date: Wed, 5 Apr 2023 23:10:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-07 17:24:40.258452
• Title: Automatically Bounding the Taylor Remainder Series: Tighter Bounds and New Applications
• Title（参考訳）: Taylor Remainderシリーズの自動バウンド:タイターバウンドと新しい応用
• Authors: Matthew Streeter and Joshua V. Dillon
• Abstract要約: テイラー剰余級数を自動的に有界化するための新しいアルゴリズムを提案する。 自動微分と同様に、関数$f$はシンボリックな形でアルゴリズムに提供される。 我々のアルゴリズムは機械学習ハードウェアアクセラレーターを効率的に利用することができる。
• 参考スコア（独自算出の注目度）: 10.824474741383723
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a new algorithm for automatically bounding the Taylor remainder series. In the special case of a scalar function $f: \mathbb{R} \to \mathbb{R}$, our algorithm takes as input a reference point $x_0$, trust region $[a, b]$, and integer $k \ge 1$, and returns an interval $I$ such that $f(x) - \sum_{i=0}^{k-1} \frac {1} {i!} f^{(i)}(x_0) (x - x_0)^i \in I (x - x_0)^k$ for all $x \in [a, b]$. As in automatic differentiation, the function $f$ is provided to the algorithm in symbolic form, and must be composed of known atomic functions. At a high level, our algorithm has two steps. First, for a variety of commonly-used elementary functions (e.g., $\exp$, $\log$), we derive sharp polynomial upper and lower bounds on the Taylor remainder series. We then recursively combine the bounds for the elementary functions using an interval arithmetic variant of Taylor-mode automatic differentiation. Our algorithm can make efficient use of machine learning hardware accelerators, and we provide an open source implementation in JAX. We then turn our attention to applications. Most notably, we use our new machinery to create the first universal majorization-minimization optimization algorithms: algorithms that iteratively minimize an arbitrary loss using a majorizer that is derived automatically, rather than by hand. Applied to machine learning, this leads to architecture-specific optimizers for training deep networks that converge from any starting point, without hyperparameter tuning. Our experiments show that for some optimization problems, these hyperparameter-free optimizers outperform tuned versions of gradient descent, Adam, and AdaGrad. We also show that our automatically-derived bounds can be used for verified global optimization and numerical integration, and to prove sharper versions of Jensen's inequality.
• Abstract（参考訳）: テイラー剰余級数を自動的に有界化する新しいアルゴリズムを提案する。 スカラー関数 $f: \mathbb{R} \to \mathbb{R}$ の特別な場合、我々のアルゴリズムは基準点 $x_0$, Trust region $[a, b]$, and integer $k \ge 1$ を入力とし、$f(x)\sum_{i=0}^{k-1} \frac {1} {i! f^{(i)}(x_0) (x - x_0)^i \in i (x - x_0)^k$ すべての$x \in [a, b]$。 自動微分と同様に、関数 $f$ はシンボリックな形でアルゴリズムに提供され、既知の原子関数で構成されなければならない。 高いレベルでは、我々のアルゴリズムには2つのステップがある。 まず、様々な一般的な初等函数(例えば、$\exp$、$\log$)に対して、テイラー剰余級数上の鋭い多項式の上限と下限を導出する。 次に、テイラーモード自動微分のインターバル算術変種を用いて基本関数の有界を再帰的に結合する。 我々のアルゴリズムは機械学習ハードウェアアクセラレータを効率的に利用することができ、JAXでオープンソース実装を提供する。 そして、アプリケーションに注意を向けます。 最も注目すべきは、我々の新しい機械を用いて、最初の普遍的偏極最小化最適化アルゴリズムを作成することである:手ではなく自動で導出される行列化器を用いて任意の損失を反復的に最小化するアルゴリズム。 機械学習に適用すると、ハイパーパラメータチューニングなしで任意の出発点から収束するディープネットワークをトレーニングするためのアーキテクチャ固有の最適化が実現する。 実験の結果,いくつかの最適化問題に対して,これらのハイパーパラメータフリーオプティマイザは勾配降下,Adam,AdaGradの調整版よりも優れていた。 また,全球最適化と数値積分を検証し,jensenの不等式をより鋭いバージョンで証明できることを示す。

関連論文リスト

• 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)
• First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians [4.62316736194615]
  我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。 また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
  論文  参考訳（メタデータ） (2023-09-05T17:40:54Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [8.0153031008486]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
  我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。 この2つを同時に実現したのは初めてである。
  論文  参考訳（メタデータ） (2021-01-30T15:05:34Z)

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

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