論文の概要: Denoising modulo samples: k-NN regression and tightness of SDP relaxation

• arxiv url: http://arxiv.org/abs/2009.04850v2
• Date: Sun, 2 May 2021 11:49:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-20 04:14:53.093892
• Title: Denoising modulo samples: k-NN regression and tightness of SDP relaxation
• Title（参考訳）: 除音モジュロ試料:SDP緩和のk-NN回帰ときつい
• Authors: Micha\"el Fanuel and Hemant Tyagi
• Abstract要約: サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
• 参考スコア（独自算出の注目度）: 5.025654873456756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many modern applications involve the acquisition of noisy modulo samples of a function $f$, with the goal being to recover estimates of the original samples of $f$. For a Lipschitz function $f:[0,1]^d \to \mathbb{R}$, suppose we are given the samples $y_i = (f(x_i) + \eta_i)\bmod 1; \quad i=1,\dots,n$ where $\eta_i$ denotes noise. Assuming $\eta_i$ are zero-mean i.i.d Gaussian's, and $x_i$'s form a uniform grid, we derive a two-stage algorithm that recovers estimates of the samples $f(x_i)$ with a uniform error rate $O((\frac{\log n}{n})^{\frac{1}{d+2}})$ holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of $f(x_i)\bmod 1$ via a $k$NN (nearest neighbor) estimator. The second stage involves a sequential unwrapping procedure which unwraps the denoised mod $1$ estimates from the first stage. The estimates of the samples $f(x_i)$ can be subsequently utilized to construct an estimate of the function $f$, with the aforementioned uniform error rate. Recently, Cucuringu and Tyagi proposed an alternative way of denoising modulo $1$ data which works with their representation on the unit complex circle. They formulated a smoothness regularized least squares problem on the product manifold of unit circles, where the smoothness is measured with respect to the Laplacian of a proximity graph $G$ involving the $x_i$'s. This is a nonconvex quadratically constrained quadratic program (QCQP) hence they proposed solving its semidefinite program (SDP) based relaxation. We derive sufficient conditions under which the SDP is a tight relaxation of the QCQP. Hence under these conditions, the global solution of QCQP can be obtained in polynomial time.
• Abstract（参考訳）: 現代の多くのアプリケーションは、関数のノイズの多いmoduloサンプルを$f$で取得し、元のサンプルの見積もりを$f$で回収することを目的としている。 リプシッツ函数 $f:[0,1]^d \to \mathbb{R}$ に対して、サンプル $y_i = (f(x_i) + \eta_i)\bmod 1; \quad i=1,\dots,n$ が与えられると仮定する。 例えば、$\eta_i$ が 0 平均 i.i.d Gaussian's であり、$x_i$'s が一様格子であると仮定すると、f(x_i)$ の誤差率 $O((\frac{\log n}{n})^{\frac{1}{d+2}})$ を高い確率で保持する2段階のアルゴリズムが導出される。 最初の段階は、単位複素円上に点を埋め込んで、$k$NN (nearest neighbor) 推定器を介して$f(x_i)\bmod 1$の分解推定値を得る。 第2段階はシーケンシャル・アンラッピング・プロシージャで、第1段階から denoized mod を1ドル見積もる。 サンプル$f(x_i)$の見積もりは、上記の均一なエラー率を持つ関数$f$の見積もりを構築するために使われる。 最近、Cucuringu と Tyagi は、単位複素円上のそれらの表現と連動するモジュロデータに1ドルを割る別の方法を提案した。 彼らは単位円の積多様体上の滑らかさの正則化最小二乗問題を定式化し、その滑らかさは近接グラフ $G$ のラプラシアンに対して$x_i$'s を含む。 これは非凸2次制約付き二次プログラム(qcqp)であり、半定義型プログラム(sdp)ベースの緩和の解法を提案した。 我々は、SDPがQCQPの厳密な緩和である十分な条件を導出する。 これらの条件下では、qcqpの大域解は多項式時間で得られる。

関連論文リスト

• A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
  Lipschitz-of-$nabla f$ $mathcalS_k|p$。 $mathcalS_k|p$。 $nabla f$. $mathcalS_k|p$。
  論文  参考訳（メタデータ） (2024-09-28T18:16:32Z)
• Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
  閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。 線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
  論文  参考訳（メタデータ） (2024-09-05T16:59:56Z)
• Quantum (Inspired) $D^2$-sampling with Applications [0.138120109831448]
  我々は、$k$-means++の量子実装を示し、その時間は$tildeO(zeta2 k2)$で実行される。 これは、量子バージョンが$O(logk)$近似を保証する$k$-means++の堅牢な近似解析によって示される。 これはQI-$k$-means++と呼ばれ、実行時間は$O(Nd) + tildeO(zeta)である。
  論文  参考訳（メタデータ） (2024-05-22T05:13:28Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。 ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。 PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
  論文  参考訳（メタデータ） (2022-11-29T18:43:22Z)
• 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)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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