論文の概要: Efficient Minimax Optimal Estimators For Multivariate Convex Regression
- arxiv url: http://arxiv.org/abs/2205.03368v1
- Date: Fri, 6 May 2022 17:04:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-09 14:19:17.007679
- Title: Efficient Minimax Optimal Estimators For Multivariate Convex Regression
- Title(参考訳): 多変量凸回帰のための高効率ミニマックス最適推定器
- Authors: Gil Kur and Eli Putterman
- Abstract要約: i) $L$-Lipschitz convex regression (ii) $Gamma$-bounded convex regression undertopal support。
この研究は、非ドンスカー類に対する効率的なミニマックス最適推定器の存在を示す最初のものである。
- 参考スコア(独自算出の注目度): 1.583842747998493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the computational aspects of the task of multivariate convex
regression in dimension $d \geq 5$. We present the first computationally
efficient minimax optimal (up to logarithmic factors) estimators for the tasks
of (i) $L$-Lipschitz convex regression (ii) $\Gamma$-bounded convex regression
under polytopal support. The proof of the correctness of these estimators uses
a variety of tools from different disciplines, among them empirical process
theory, stochastic geometry, and potential theory. This work is the first to
show the existence of efficient minimax optimal estimators for non-Donsker
classes that their corresponding Least Squares Estimators are provably minimax
sub-optimal; a result of independent interest.
- Abstract(参考訳): 本研究では,多変量凸回帰のタスクの計算的側面を次元 $d \geq 5$ で検討する。
本稿では,計算効率の優れたミニマックス最適(対数因子まで)推定器のタスクについて述べる。
(i)$L$-Lipschitz凸回帰
(ii)多面体支持下での$\gamma$-bounded凸回帰。
これらの推定器の正しさの証明は、経験過程理論、確率幾何学、ポテンシャル理論など、様々な分野の様々なツールを使用する。
この研究は、非ドンスカークラスに対する効率的なミニマックス最適推定器の存在を、それらの最小二乗推定器が証明可能なミニマックス部分最適化であることを示す最初の例である。
関連論文リスト
- Online non-parametric likelihood-ratio estimation by Pearson-divergence
functional minimization [55.98760097296213]
iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。
本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
論文 参考訳(メタデータ) (2023-11-03T13:20:11Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳(メタデータ) (2022-12-12T18:58:59Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。
実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
論文 参考訳(メタデータ) (2020-07-05T18:58:47Z) - Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic
Bounds and Applications [0.6445605125467573]
勾配推定は統計学と学習理論において重要である。
ここでは古典的な回帰設定を考えると、実値の正方形可積分 r.v.$Y$ が予測される。
代替推定法で得られた値に対して, 漸近的境界が改良されることを証明した。
論文 参考訳(メタデータ) (2020-06-26T15:19:43Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳(メタデータ) (2020-06-19T22:49:42Z) - Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex
Optimization [9.492903649862761]
階数1の投影から低階行列を復元するための定式化凸を用いた推定器について検討した。
両モデルにおいて、測定値が$r2 (d+d_$2)以上の場合、推定器は高い確率で成功することを示す。
論文 参考訳(メタデータ) (2020-04-06T14:57:54Z) - 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) - Communication-Efficient Distributed Estimator for Generalized Linear
Models with a Diverging Number of Covariates [7.427903819459701]
2ラウンドの通信により,大規模分散データに対する効率の良い推定器を得る手法が提案されている。
本手法では,サーバ数に対する仮定をより緩和し,現実のアプリケーションに対して実用的である。
論文 参考訳(メタデータ) (2020-01-17T08:51:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。