論文の概要: On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies
- arxiv url: http://arxiv.org/abs/2006.04046v1
- Date: Sun, 7 Jun 2020 05:19:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 08:39:06.961520
- Title: On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies
- Title（参考訳）: 極小正方形の準最適性と凸体推定への応用
- Authors: Gil Kur, Alexander Rakhlin and Adityanand Guntuboyina
- Abstract要約: 雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。
Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
- 参考スコア（独自算出の注目度）: 74.39616164169131
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a technique for establishing lower bounds on the sample complexity
of Least Squares (or, Empirical Risk Minimization) for large classes of
functions. As an application, we settle an open problem regarding optimality of
Least Squares in estimating a convex set from noisy support function
measurements in dimension $d\geq 6$. Specifically, we establish that Least
Squares is mimimax sub-optimal, and achieves a rate of
$\tilde{\Theta}_d(n^{-2/(d-1)})$ whereas the minimax rate is
$\Theta_d(n^{-4/(d+3)})$.
- Abstract（参考訳）: 大規模関数のクラスに対する最小二乗(または経験的リスク最小化)のサンプル複雑性の下位境界を確立する手法を開発した。
応用として、次元$d\geq 6$の雑音支援関数の測定値から凸集合を推定する際、最小広場の最適性に関するオープンな問題を解決する。
具体的には、Least Squaresはmimimax sub-optimalであり、$\tilde{\Theta}_d(n^{-2/(d-1)})$であるのに対して、minimax rateは$\Theta_d(n^{-4/(d+3)})$である。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Estimating the minimizer and the minimum value of a regression function
under passive design [72.85024381807466]
最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。
2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
論文 参考訳（メタデータ） (2022-11-29T18:38:40Z) - 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) - Localization in 1D non-parametric latent space models from pairwise
affinities [6.982738885923206]
対の親和性から一次元トーラスにおける潜伏位置を推定する問題を考察する。
高確率でsqrtlog(n)/n$の順序の最大誤差で全ての潜伏位置を確実にローカライズする推定手順を導入する。
論文 参考訳（メタデータ） (2021-08-06T13:05:30Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Minimal Constraints in the Parity Formulation of Optimization Problems [0.0]
本稿では,正しい基底状態を保存するために必要な制約の最小限の強度を求める手法を提案する。
問題クラスによっては、指数は線型$alpha propto 1$ から$alpha propto 2$ まで、論理量子ビットの個数に比例する。
論文 参考訳（メタデータ） (2020-08-24T14:04:33Z) - Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators [4.758195657080579]
最小二乗推定器は、$d$が5以上の場合の2乗誤差損失において$d$次元凸関数を推定するのに最適である。
i)ポリトープでサポートされている有界凸関数(ランダム設計)、(ii)任意の凸領域でサポートされているリプシッツ凸関数(ランダム設計)、(iii)ポリトープでサポートされている凸関数(固定設計)である。
論文 参考訳（メタデータ） (2020-06-03T04:57:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。