論文の概要: An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time
Algorithms and Applications to the Linear Convergence of Minimax Problems
- arxiv url: http://arxiv.org/abs/2001.08826v7
- Date: Fri, 9 Jul 2021 16:19:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 13:32:04.681324
- Title: An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time
Algorithms and Applications to the Linear Convergence of Minimax Problems
- Title（参考訳）: 離散時間アルゴリズム理解のための$O(s^r)$-resolution ODE Frameworkとミニマックス問題の線形収束への応用
- Authors: Haihao Lu
- Abstract要約: 汎用DTAの挙動を解析するための新しい機械($O(sr)$- resolution ODE フレームワーク)を提案する。
DTAからユニークな$O(sr)$- resolution ODEを構築するための主要なアプローチを提案する。
固有エネルギー関数に対する$O(sr)$- resolution ODEの線型収束は、DTAの線型収束を自動的に保証できることを示す。
- 参考スコア（独自算出の注目度）: 8.782204980889079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There has been a long history of using ordinary differential equations (ODEs)
to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly,
there are still two fundamental and unanswered questions: (i) it is unclear how
to obtain a \emph{suitable} ODE from a given DTA, and (ii) it is unclear the
connection between the convergence of a DTA and its corresponding ODEs. In this
paper, we propose a new machinery -- an $O(s^r)$-resolution ODE framework --
for analyzing the behavior of a generic DTA, which (partially) answers the
above two questions. The framework contains three steps: 1. To obtain a
suitable ODE from a given DTA, we define a hierarchy of $O(s^r)$-resolution
ODEs of a DTA parameterized by the degree $r$, where $s$ is the step-size of
the DTA. We present a principal approach to construct the unique
$O(s^r)$-resolution ODEs from a DTA; 2. To analyze the resulting ODE, we
propose the $O(s^r)$-linear-convergence condition of a DTA with respect to an
energy function, under which the $O(s^r)$-resolution ODE converges linearly to
an optimal solution; 3. To bridge the convergence properties of a DTA and its
corresponding ODEs, we define the properness of an energy function and show
that the linear convergence of the $O(s^r)$-resolution ODE with respect to a
proper energy function can automatically guarantee the linear convergence of
the DTA. To better illustrate this machinery, we utilize it to study three
classic algorithms -- gradient descent ascent (GDA), proximal point method
(PPM) and extra-gradient method (EGM) -- for solving the unconstrained minimax
problem $\min_{x\in\RR^n} \max_{y\in \RR^m} L(x,y)$.
- Abstract（参考訳）: 離散時間アルゴリズム(dtas)のダイナミクスを理解するために、通常の微分方程式(odes)を用いた長い歴史がある。
意外なことに、まだ基本的な疑問と答えが2つあります。
i)所定のDTAから \emph{suitable} ODE を取得する方法が不明確で、
(ii) DTA の収束と対応する ODE との関係は不明確である。
本稿では、上記の2つの疑問に答える汎用DTAの挙動を分析するための新しい機械、$O(s^r)$- resolution ODEフレームワークを提案する。
フレームワークには3つのステップがある。
1. 与えられた DTA から適切な ODE を得るには、$s$ が DTA のステップサイズである次数 $r$ でパラメータ化された DTA の $O(s^r)$- resolution ODE の階層を定義する。
DTA からユニークな $O(s^r)$- resolution ODE を構築するための主要なアプローチを提案する。
2) 得られたODEを解析するために,DTAのエネルギー関数に対する$O(s^r)$-linear-convergence条件を提案し,そこで$O(s^r)$- resolution ODEが最適解に線形に収束する。
3) DTA とその対応する ODE の収束特性をブリッジするために、エネルギー関数の固有性を定義し、適切なエネルギー関数に対する$O(s^r)$-解像度 ODE の線型収束が、DTA の線形収束を自動的に保証できることを示す。
この機構をよりよく説明するために、制約のないミニマックス問題 $\min_{x\in\RR^n} \max_{y\in \RR^m} L(x,y)$ の解法として、勾配降下昇降法(GDA)、近点法(PPM)、外勾配法(EGM)の3つの古典的アルゴリズムについて検討する。
関連論文リスト
- Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
確率フローODEに基づく決定論的サンプリング器の収束特性を理論的・数値的両面から検討する。
連続時間レベルでは、ターゲットと生成されたデータ分布の総変動を$mathcalO(d3/4delta1/2)$で表すことができる。
論文 参考訳（メタデータ） (2024-04-15T12:29:28Z) - Oracle Complexity Reduction for Model-free LQR: A Stochastic
Variance-Reduced Policy Gradient Approach [4.422315636150272]
離散時間線形擬似レギュレータ(LQR)問題に対する$epsilon$-approximateソリューションの学習問題について検討する。
本手法は,二ループ分散推定アルゴリズムにおいて,一点推定と二点推定を併用する。
論文 参考訳（メタデータ） (2023-09-19T15:03:18Z) - Learning High-Dimensional Nonparametric Differential Equations via
Multivariate Occupation Kernel Functions [0.31317409221921133]
通常の微分方程式の非パラメトリック系を学ぶには、$d$変数の$d$関数を学ぶ必要がある。
明示的な定式化は、スパーシティや対称性といったシステム特性に関する追加の知識が得られない限り、$d$で2次的にスケールする。
本稿では,ベクトル値の再現Kernel Hilbert Spacesによる暗黙の定式化を用いた線形学習手法を提案する。
論文 参考訳（メタデータ） (2023-06-16T21:49:36Z) - Convergence Analysis of the Deep Galerkin Method for Weak Solutions [9.920833699101195]
DGMWの収束率は$mathcalO(n-1/d)$であり、弱解に対する最初の収束結果である。
我々は、$H1$ノルムの近似誤差の上限を導出し、Rademacher複雑性による統計的誤差を導出する。
論文 参考訳（メタデータ） (2023-02-05T15:25:16Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
ODE/PDEを解決するためにデュアルニューラルネットワークを利用するdNNsolveを紹介します。
我々は,dNNsolveが1,2,3次元の幅広いODE/PDEを解くことができることを示す。
論文 参考訳（メタデータ） (2021-03-15T19:14:41Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。