論文の概要: Tree-Projected Gradient Descent for Estimating Gradient-Sparse
Parameters on Graphs
- arxiv url: http://arxiv.org/abs/2006.01662v1
- Date: Sun, 31 May 2020 20:08:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 12:41:03.169027
- Title: Tree-Projected Gradient Descent for Estimating Gradient-Sparse
Parameters on Graphs
- Title（参考訳）: グラフ上のグラディエント・スパースパラメータ推定のためのツリー投影グラディエントDescent
- Authors: Sheng Xu, Zhou Fan, Sahand Negahban
- Abstract要約: mathbbRp$における勾配スパースパラメータの$boldsymboltheta*の推定について検討した。
損失に対する厳密な凸性および滑らかさの仮定が適切に制限されている場合、この推定器は、$G$とは独立な乗法定数までの2乗誤差リスク $fracs*n log (1+fracps*)$を達成する。
- 参考スコア（独自算出の注目度）: 10.846572437131872
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study estimation of a gradient-sparse parameter vector
$\boldsymbol{\theta}^* \in \mathbb{R}^p$, having strong gradient-sparsity
$s^*:=\|\nabla_G \boldsymbol{\theta}^*\|_0$ on an underlying graph $G$. Given
observations $Z_1,\ldots,Z_n$ and a smooth, convex loss function $\mathcal{L}$
for which $\boldsymbol{\theta}^*$ minimizes the population risk
$\mathbb{E}[\mathcal{L}(\boldsymbol{\theta};Z_1,\ldots,Z_n)]$, we propose to
estimate $\boldsymbol{\theta}^*$ by a projected gradient descent algorithm that
iteratively and approximately projects gradient steps onto spaces of vectors
having small gradient-sparsity over low-degree spanning trees of $G$. We show
that, under suitable restricted strong convexity and smoothness assumptions for
the loss, the resulting estimator achieves the squared-error risk
$\frac{s^*}{n} \log (1+\frac{p}{s^*})$ up to a multiplicative constant that is
independent of $G$. In contrast, previous polynomial-time algorithms have only
been shown to achieve this guarantee in more specialized settings, or under
additional assumptions for $G$ and/or the sparsity pattern of $\nabla_G
\boldsymbol{\theta}^*$. As applications of our general framework, we apply our
results to the examples of linear models and generalized linear models with
random design.
- Abstract（参考訳）: グラデーション・スパースパラメータベクトル $\boldsymbol{\theta}^* \in \mathbb{r}^p$ の推定について検討し、基礎となるグラフ $g$ 上で強い勾配分離性$s^*:|\nabla_g \boldsymbol{\theta}^*\|_0$ を持つ。
Z_1,\ldots,Z_n$ および滑らかな凸損失関数 $\mathcal{L}$ に対して、$\boldsymbol{\theta}^*$ は人口リスク $\mathbb{E}[\mathcal{L}(\boldsymbol{\theta};Z_1,\ldots,Z_n)]$ を最小化する。
適切な制限された強凸性と損失に対する滑らかさの仮定の下で、結果として生じる推定器は、$g$から独立な乗算定数まで2乗誤差のリスク$\frac{s^*}{n} \log (1+\frac{p}{s^*}) を達成する。
対照的に、従来の多項式時間アルゴリズムは、より特殊な設定、または$g$と/または$\nabla_g \boldsymbol{\theta}^*$のスパーシティパターンに対する追加の仮定の下でのみこの保証を達成することが示されている。
一般フレームワークの応用として、ランダムな設計を伴う線形モデルや一般化線形モデルの例に適用する。
関連論文リスト
- Conditional regression for the Nonlinear Single-Variable Model [4.565636963872865]
F(X):=f(Pi_gamma):mathbbRdto[0,rmlen_gamma]$ ここで$Pi_gamma: [0,rmlen_gamma]tomathbbRd$と$f:[0,rmlen_gamma]tomathbbR1$を考える。
条件回帰に基づく非パラメトリック推定器を提案し、$one$-dimensionalOptimical min-maxレートを実現できることを示す。
論文 参考訳（メタデータ） (2024-11-14T18:53:51Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors [33.0212223058894]
二次系$y_i=boldsymbol xtopboldsymbol A_iboldsymbol x, i=1,ldots,m$とフルランク行列$boldsymbol A_i$からの信号を回復する問題は、未割り当て距離幾何学やサブ波長イメージングなどの応用で頻繁に発生する。
本稿では、$mll n$ が $boldsymbol x$ の事前知識を取り入れた高次元の場合について述べる。
論文 参考訳（メタデータ） (2023-09-16T16:00:07Z) - 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) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳（メタデータ） (2022-05-03T12:09:59Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Universality of empirical risk minimization [12.764655736673749]
例えば、$boldsymbol x_i inmathbbRp$ が特徴ベクトルで $y in mathbbR$ がラベルであるような i.d. サンプルからの教師付き学習を考える。
我々は$mathsfkによってパラメータ化される関数のクラスに対する経験的リスク普遍性について研究する。
論文 参考訳（メタデータ） (2022-02-17T18:53:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。