論文の概要: Efficient algorithms for multivariate shape-constrained convex
regression problems
- arxiv url: http://arxiv.org/abs/2002.11410v1
- Date: Wed, 26 Feb 2020 11:18:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 15:27:15.268827
- Title: Efficient algorithms for multivariate shape-constrained convex
regression problems
- Title（参考訳）: 多変量形状制約凸回帰問題の効率的なアルゴリズム
- Authors: Meixia Lin, Defeng Sun, Kim-Chuan Toh
- Abstract要約: 最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
- 参考スコア（独自算出の注目度）: 9.281671380673306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Shape-constrained convex regression problem deals with fitting a convex
function to the observed data, where additional constraints are imposed, such
as component-wise monotonicity and uniform Lipschitz continuity. This paper
provides a comprehensive mechanism for computing the least squares estimator of
a multivariate shape-constrained convex regression function in $\mathbb{R}^d$.
We prove that the least squares estimator is computable via solving a
constrained convex quadratic programming (QP) problem with $(n+1)d$ variables
and at least $n(n-1)$ linear inequality constraints, where $n$ is the number of
data points. For solving the generally very large-scale convex QP, we design
two efficient algorithms, one is the symmetric Gauss-Seidel based alternating
direction method of multipliers ({\tt sGS-ADMM}), and the other is the proximal
augmented Lagrangian method ({\tt pALM}) with the subproblems solved by the
semismooth Newton method ({\tt SSN}). Comprehensive numerical experiments,
including those in the pricing of basket options and estimation of production
functions in economics, demonstrate that both of our proposed algorithms
outperform the state-of-the-art algorithm. The {\tt pALM} is more efficient
than the {\tt sGS-ADMM} but the latter has the advantage of being simpler to
implement.
- Abstract（参考訳）: 形状制約凸回帰問題は、成分的な単調性や一様リプシッツ連続性のような追加の制約が課される観測データに凸関数を適合させることを扱う。
本稿では,多変量形状制約付き凸回帰関数の最小二乗推定器を$\mathbb{r}^d$ で計算するための包括的メカニズムを提案する。
最小二乗推定子は、制約付き凸二次計画(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般の大規模凸QPの解法として,対称ガウス-シーデル法に基づく乗算器の交互方向法({\tt sGS-ADMM})と半滑らかニュートン法({\tt SSN})で解ける部分確率の近似拡張ラグランジアン法({\tt pALM})の2つの効率的なアルゴリズムを設計する。
バスケットオプションの価格設定や経済学における生産関数の推定を含む包括的数値実験により,提案手法はともに最先端アルゴリズムよりも優れていることが示された。
pALM {\displaystyle pALM} は {\tt sGS-ADMM} よりも効率的であるが、後者は実装が簡単であるという利点がある。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Ridge regression with adaptive additive rectangles and other piecewise
functional templates [0.0]
関数線形回帰モデルに対する$L_2$ベースのペナル化アルゴリズムを提案する。
提案アルゴリズムは,適切なテンプレートの近似と凸リッジのような問題の解法とを交互に行う方法を示す。
論文 参考訳（メタデータ） (2020-11-02T15:28:54Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳（メタデータ） (2020-06-27T03:05:18Z) - Subgradient Regularized Multivariate Convex Regression at Scale [21.55988846648753]
次数正規化凸回帰関数を$d$次元で$n$のサンプルに適合させる新しい大規模アルゴリズムを提案する。
本研究のフレームワークは,n=105$と$d=10$で,段階的な正規化凸回帰問題のインスタンスを数分で解くことができることを示す。
論文 参考訳（メタデータ） (2020-05-23T19:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。