論文の概要: Multiscale regression on unknown manifolds
- arxiv url: http://arxiv.org/abs/2101.05119v1
- Date: Wed, 13 Jan 2021 15:14:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-30 08:03:25.649132
- Title: Multiscale regression on unknown manifolds
- Title（参考訳）: 未知多様体上のマルチスケール回帰
- Authors: Wenjing Liao, Mauro Maggioni and Stefano Vigogna
- Abstract要約: マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。
本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。
私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
- 参考スコア（独自算出の注目度）: 13.752772802705978
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the regression problem of estimating functions on $\mathbb{R}^D$
but supported on a $d$-dimensional manifold $ \mathcal{M} \subset \mathbb{R}^D
$ with $ d \ll D $. Drawing ideas from multi-resolution analysis and nonlinear
approximation, we construct low-dimensional coordinates on $\mathcal{M}$ at
multiple scales, and perform multiscale regression by local polynomial fitting.
We propose a data-driven wavelet thresholding scheme that automatically adapts
to the unknown regularity of the function, allowing for efficient estimation of
functions exhibiting nonuniform regularity at different locations and scales.
We analyze the generalization error of our method by proving finite sample
bounds in high probability on rich classes of priors. Our estimator attains
optimal learning rates (up to logarithmic factors) as if the function was
defined on a known Euclidean domain of dimension $d$, instead of an unknown
manifold embedded in $\mathbb{R}^D$. The implemented algorithm has quasilinear
complexity in the sample size, with constants linear in $D$ and exponential in
$d$. Our work therefore establishes a new framework for regression on
low-dimensional sets embedded in high dimensions, with fast implementation and
strong theoretical guarantees.
- Abstract（参考訳）: 我々は、$\mathbb{r}^d$ で関数を推定する回帰問題を考えるが、$d$-次元多様体 $ \mathcal{m} \subset \mathbb{r}^d $ でサポートされ、$d \ll d $ である。
多分解能解析と非線形近似からアイデアを導き、$\mathcal{M}$の低次元座標を複数スケールで構築し、局所多項式フィッティングによるマルチスケール回帰を行う。
本研究では,関数の未知の規則性に自動的に適応するデータ駆動型ウェーブレットしきい値決定手法を提案し,異なる位置とスケールで不均一な規則性を示す関数を効率的に推定する。
本手法は,事前のリッチクラスに対して高い確率で有限サンプル境界を証明し,一般化誤差を解析した。
我々の推定器は、函数が既知の次元$d$のユークリッド領域上で定義されているような最適学習率(対数因子まで)を、$\mathbb{R}^D$に埋め込まれた未知多様体の代わりに達成する。
実装されたアルゴリズムはサンプルサイズが準線形で、定数は$D$、指数は$d$である。
そこで本研究では,高次元に埋め込まれた低次元集合に対する回帰のための新しい枠組みを確立し,高速実装と強い理論的保証を実現した。
関連論文リスト
- Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - 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) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Generalization Bounds for Stochastic Gradient Descent via Localized
$\varepsilon$-Covers [16.618918548497223]
本稿では,SGDの軌道に局在する新しい被覆手法を提案する。
このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。
これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
論文 参考訳（メタデータ） (2022-09-19T12:11:07Z) - Manifold Free Riemannian Optimization [4.484251538832438]
滑らかな多様体 $mathcalM$ を用いて最適化問題を解くための原理的枠組みを提案する。
代数学M におけるコスト関数 $(x_i, y_i) の雑音のないサンプル集合 mathbbR$ と多様体 $mathcalM$ の固有次元を用いる。
論文 参考訳（メタデータ） (2022-09-07T16:19:06Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。
実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
論文 参考訳（メタデータ） (2020-07-05T18:58:47Z) - 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) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。