論文の概要: Extensions to the Proximal Distance Method of Constrained Optimization
- arxiv url: http://arxiv.org/abs/2009.00801v2
- Date: Tue, 11 Jan 2022 23:10:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 20:06:09.708167
- Title: Extensions to the Proximal Distance Method of Constrained Optimization
- Title（参考訳）: 制約付き最適化の近距離法の拡張
- Authors: Alfonso Landeros, Oscar Hernan Madrid Padilla, Hua Zhou, Kenneth Lange
- Abstract要約: 損失 $f(boldsymbolx)$ を S$ の $boldsymbolx の形に制約する問題について検討する。
融合制約は、滑らかさ、疎さ、あるいはより一般的な制約パターンをキャプチャすることができる。
- 参考スコア（独自算出の注目度）: 7.813460653362097
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The current paper studies the problem of minimizing a loss
$f(\boldsymbol{x})$ subject to constraints of the form
$\boldsymbol{D}\boldsymbol{x} \in S$, where $S$ is a closed set, convex or not,
and $\boldsymbol{D}$ is a matrix that fuses parameters. Fusion constraints can
capture smoothness, sparsity, or more general constraint patterns. To tackle
this generic class of problems, we combine the Beltrami-Courant penalty method
with the proximal distance principle. The latter is driven by minimization of
penalized objectives
$f(\boldsymbol{x})+\frac{\rho}{2}\text{dist}(\boldsymbol{D}\boldsymbol{x},S)^2$
involving large tuning constants $\rho$ and the squared Euclidean distance of
$\boldsymbol{D}\boldsymbol{x}$ from $S$. The next iterate
$\boldsymbol{x}_{n+1}$ of the corresponding proximal distance algorithm is
constructed from the current iterate $\boldsymbol{x}_n$ by minimizing the
majorizing surrogate function
$f(\boldsymbol{x})+\frac{\rho}{2}\|\boldsymbol{D}\boldsymbol{x}-\mathcal{P}_{S}(\boldsymbol{D}\boldsymbol{x}_n)\|^2$.
For fixed $\rho$ and a subanalytic loss $f(\boldsymbol{x})$ and a subanalytic
constraint set $S$, we prove convergence to a stationary point. Under stronger
assumptions, we provide convergence rates and demonstrate linear local
convergence. We also construct a steepest descent (SD) variant to avoid costly
linear system solves. To benchmark our algorithms, we compare against the
alternating direction method of multipliers (ADMM). Our extensive numerical
tests include problems on metric projection, convex regression, convex
clustering, total variation image denoising, and projection of a matrix to a
good condition number. These experiments demonstrate the superior speed and
acceptable accuracy of our steepest variant on high-dimensional problems.
- Abstract（参考訳）: 現在の論文では、損失$f(\boldsymbol{x})$を、パラメータを融合する行列である$\boldsymbol{D}\boldsymbol{x} \in S$という形式の制約を最小化する問題を研究している。
融合制約は、滑らかさ、疎さ、あるいはより一般的な制約パターンをキャプチャすることができる。
このような一般的な問題に対処するために、ベルトラミ・コースト法と近距離原理を組み合わせる。
後者はペナル化対象の最小化によって駆動される: $f(\boldsymbol{x})+\frac{\rho}{2}\text{dist}(\boldsymbol{D}\boldsymbol{x},S)^2$ で、大きなチューニング定数が $\rho$ で、平方ユークリッド距離が $\boldsymbol{D}\boldsymbol{x}$ である。
対応する近距離アルゴリズムの次のイテレート$\boldsymbol{x}_{n+1}$は、主要なサロゲート関数$f(\boldsymbol{x})+\frac{\rho}{2}\|\boldsymbol{d}\boldsymbol{x}-\mathcal{p}_{s}(\boldsymbol{d}\boldsymbol{x}_n)\|^2$を最小化することにより、現在のイテレート$\boldsymbol{x}_n$から構成される。
固定 $\rho$ と部分解析損失 $f(\boldsymbol{x})$ と部分解析制約セット $s$ に対して、我々は定常点への収束を証明する。
強い仮定の下では、収束率を提供し、線形局所収束を示す。
また, コストのかかる線形システム問題を回避するために, 最急降下型 (sd) も構築した。
アルゴリズムをベンチマークするために、乗算器の交互方向法(ADMM)と比較する。
大規模な数値実験では, 距離予測, 凸回帰, 凸クラスタリング, 総変動像のデノイング, 行列の良好な条件数への投影に関する問題を含む。
これらの実験は,高次元問題に対する最も急な変形の速度と許容可能な精度を示す。
関連論文リスト
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk [12.842909157175582]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto exp(-f(theta))$ for $L$-Lipschitz $f$を考える。
本稿では,各繰り返しにおける障壁関数のヘシアンに対するスペクトル近似を計算するインプロバストサンプリングフレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-08T05:32:51Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - 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) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Minimax Optimal Regression over Sobolev Spaces via Laplacian
Regularization on Neighborhood Graphs [25.597646488273558]
非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。
ラプラシアン滑らか化が多様体適応であることを証明する。
論文 参考訳（メタデータ） (2021-06-03T01:20:41Z) - Optimal Combination of Linear and Spectral Estimators for Generalized
Linear Models [59.015960528781115]
最適に $hatboldsymbol xrm L$ と $hatboldsymbol xrm s$ を組み合わせる方法を示す。
我々は,$(boldsymbol x, hatboldsymbol xrm L, hatboldsymbol xrm s)$の制限分布を確立するために,Adroximate Message Passing (AMP)アルゴリズムの設計と解析を行う。
論文 参考訳（メタデータ） (2020-08-07T18:20:05Z) - 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) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。