論文の概要: Constructing Segmented Differentiable Quadratics to Determine
Algorithmic Run Times and Model Non-Polynomial Functions
- arxiv url: http://arxiv.org/abs/2012.01420v1
- Date: Thu, 3 Dec 2020 00:22:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-24 05:01:18.619505
- Title: Constructing Segmented Differentiable Quadratics to Determine
Algorithmic Run Times and Model Non-Polynomial Functions
- Title（参考訳）: アルゴリズムの実行時間とモデル非多項関数を決定するための分節微分可能二次関数の構成
- Authors: Ananth Goyal
- Abstract要約: アルゴリズム効率の連続的な進行を決定する手法を提案する。
提案手法は,任意のインデックスに対して,実行時の動作を$F$で効果的に決定できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose an approach to determine the continual progression of algorithmic
efficiency, as an alternative to standard calculations of time complexity,
likely, but not exclusively, when dealing with data structures with unknown
maximum indexes and with algorithms that are dependent on multiple variables
apart from just input size. The proposed method can effectively determine the
run time behavior $F$ at any given index $x$ , as well as $\frac{\partial
F}{\partial x}$, as a function of only one or multiple arguments, by combining
$\frac{n}{2}$ quadratic segments, based upon the principles of Lagrangian
Polynomials and their respective secant lines. Although the approach used is
designed for analyzing the efficacy of computational algorithms, the proposed
method can be used within the pure mathematical field as a novel way to
construct non-polynomial functions, such as $\log_2{n}$ or $\frac{n+1}{n-2}$,
as a series of segmented differentiable quadratics to model functional behavior
and reoccurring natural patterns. After testing, our method had an average
accuracy of above of 99\% with regard to functional resemblance.
- Abstract（参考訳）: 提案手法は,未知の最大インデックスを持つデータ構造を扱う場合や,入力サイズ以外の複数の変数に依存するアルゴリズムを扱う場合,時間的複雑性の標準的な計算の代替として,アルゴリズム効率の連続的な進行を決定する手法である。
提案手法は,任意の指数$x$における実行時挙動$F$と,1つあるいは複数の引数のみの関数として,ラグランジアン多項式の原理とそれぞれのセカント線に基づいて,$\frac{n}{2}$2次セグメントを組み合わせることで,有効に決定できる。
提案手法は, 計算アルゴリズムの有効性を解析するために設計されているが, 関数の振る舞いをモデル化し, 自然パターンを再帰的に再帰させる, 分割微分可能な2次関数の系列として, $\log_2{n}$ や $\frac{n+1}{n-2}$ などの非ポリノミカル関数を構成する新しい方法として, 純粋数理場内で用いられる。
実験後,本手法は機能的類似度について平均99\%以上の精度を示した。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Private graphon estimation via sum-of-squares [10.00024942014117]
ブロックモデルを学習し,任意のブロックに対して一定の実行時間でグラフトン推定を行うための,最初の純粋ノード微分プライベートアルゴリズムを開発した。
統計的ユーティリティは、これらの問題に対する以前の最良の情報理論(指数時間)ノードプライドメカニズムのそれと一致することを保証している。
論文 参考訳（メタデータ） (2024-03-18T19:54:59Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Efficient One Sided Kolmogorov Approximation [7.657378889055477]
本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。
これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
論文 参考訳（メタデータ） (2022-07-14T10:03:02Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - DiffPrune: Neural Network Pruning with Deterministic Approximate Binary
Gates and $L_0$ Regularization [0.0]
現代のニューラルネットワークアーキテクチャは通常、数百万のパラメータを持ち、有効性を著しく損なうことなく、大幅に刈り取ることができる。
この作品の貢献は2つある。
1つ目は、任意の実数値確率変数の決定論的かつ微分可能変換によって多変量ベルヌーイ確率変数を近似する方法である。
2つ目は、決定論的あるいは乗法的に計算され、正確なゼロ値を取る近似二進ゲートを持つ要素的パラメータによるモデル選択の方法である。
論文 参考訳（メタデータ） (2020-12-07T13:08:56Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳（メタデータ） (2020-05-21T17:36:09Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。