論文の概要: On adaptivity and minimax optimality of two-sided nearest neighbors

• arxiv url: http://arxiv.org/abs/2411.12965v1
• Date: Wed, 20 Nov 2024 01:40:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:12:49.408118
• Title: On adaptivity and minimax optimality of two-sided nearest neighbors
• Title（参考訳）: 2辺近傍近傍の適応性と極小最適性について
• Authors: Tathagata Sadhukhan, Manit Paul, Raaz Dwivedi,
• Abstract要約: Nearest neighbor (NN)アルゴリズムは、レコメンダシステムやシーケンシャルな意思決定システムにおいて、欠落したデータ問題に広く使われている。 ここでは, NN を非滑らかな非線形関数で解析する。
• 参考スコア（独自算出の注目度）: 6.6157730528755065
• License:
• Abstract: Nearest neighbor (NN) algorithms have been extensively used for missing data problems in recommender systems and sequential decision-making systems. Prior theoretical analysis has established favorable guarantees for NN when the underlying data is sufficiently smooth and the missingness probabilities are lower bounded. Here we analyze NN with non-smooth non-linear functions with vast amounts of missingness. In particular, we consider matrix completion settings where the entries of the underlying matrix follow a latent non-linear factor model, with the non-linearity belonging to a \Holder function class that is less smooth than Lipschitz. Our results establish following favorable properties for a suitable two-sided NN: (1) The mean squared error (MSE) of NN adapts to the smoothness of the non-linearity, (2) under certain regularity conditions, the NN error rate matches the rate obtained by an oracle equipped with the knowledge of both the row and column latent factors, and finally (3) NN's MSE is non-trivial for a wide range of settings even when several matrix entries might be missing deterministically. We support our theoretical findings via extensive numerical simulations and a case study with data from a mobile health study, HeartSteps.
• Abstract（参考訳）: Nearest neighbor (NN)アルゴリズムは、レコメンダシステムやシーケンシャルな意思決定システムにおいて、欠落したデータ問題に広く使われている。 従来の理論解析では、基礎となるデータが十分に滑らかで、欠落確率が低い場合、NNに対して良好な保証が確立されている。 ここでは, NN を非滑らかな非線形関数で解析する。 特に、下層の行列の成分が、リプシッツより滑らかでないフロンダー関数クラスに属する非線型因子モデルに従うような行列完備化の設定を考える。 1) NNの平均二乗誤差(MSE)は非線形性の滑らかさに適応し,(2) 一定の規則性条件下では, NN誤差率は列と列の遅延因子の両方の知識を備えたオラクルの値と一致し, そして(3) NNのMSEは, 行列成分が決定論的に欠落している場合でも, 広範囲な設定において非自明である。 我々は,広範な数値シミュレーションとモバイルヘルス研究HeartStepsのデータを用いたケーススタディにより,理論的な知見を裏付ける。

関連論文リスト

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。 現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。 本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-10-29T07:24:11Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。 よりスムーズな関数との補間により、より一般化できることを示す。
  論文  参考訳（メタデータ） (2023-05-30T19:37:44Z)
• Individual Fairness Guarantees for Neural Networks [0.0]
  我々は、フィードフォワードニューラルネットワーク(NN)の個人公正性(IF)を認定する問題を考える。 我々は$epsilon$-$delta$-IF の定式化に取り組んでおり、$epsilon$-similar の任意のペア間の出力差は最大決定耐性によって制限される。 この定式化は、NN損失を変更することで、トレーニング時のモデルの公平性を促進するためにどのように使用できるかを示し、我々のアプローチが最先端の手法よりもはるかに公平なNNを生成することを実証的に確認する。
  論文  参考訳（メタデータ） (2022-05-11T20:21:07Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。 目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
  論文  参考訳（メタデータ） (2022-02-15T15:39:30Z)
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes [0.0]
  ニューラルネットワークと一般的な非線形円錐近似スキームの2乗損失を伴うトレーニング問題の最適化景観と安定性特性について検討する。 これらの不安定性に寄与する同じ効果が、サドル点や急激な局所ミニマの出現の原因でもあることを証明している。
  論文  参考訳（メタデータ） (2020-11-06T11:34:59Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• NeuMiss networks: differentiable programming for supervised learning with missing values [0.0]
  線形性仮定の下で最適予測器の解析形式を導出する。 我々はNeuMissネットワークという新しい原則アーキテクチャを提案する。 パラメータの数と、欠落したデータパターンの数に依存しない計算複雑性の両方で、予測精度が良い。
  論文  参考訳（メタデータ） (2020-07-03T11:42:25Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。 線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。 提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-02T17:55:47Z)
• Neural Contraction Metrics for Robust Estimation and Control: A Convex Optimization Approach [6.646482960350819]
  本稿では,ニューラル・コントラクト・メトリック(NCM)の概念を用いて,ロバストな非線形推定と制御のための新しいディープラーニングベースのフレームワークを提案する。 NCMは、最適な収縮距離を大域的に近似するために、ディープロング短期記憶リカレントニューラルネットワークを使用する。 そこで本稿では,NCMを用いた非線形システムの最適推定器と制御器の設計について述べる。
  論文  参考訳（メタデータ） (2020-06-08T05:29:38Z)
• Nonconvex sparse regularization for deep neural networks and its optimality [1.9798034349981162]
  ディープニューラルネットワーク(DNN)推定器は、回帰と分類問題に対して最適な収束率を得ることができる。 スパースDNNに対する新たなペナル化推定法を提案する。 スパースペンタライズされた推定器は、様々な非パラメトリック回帰問題に対する最小収束率を適応的に達成できることを示す。
  論文  参考訳（メタデータ） (2020-03-26T07:15:28Z)

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

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