論文の概要: Subgradient Regularized Multivariate Convex Regression at Scale
- arxiv url: http://arxiv.org/abs/2005.11588v3
- Date: Tue, 5 Dec 2023 02:24:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-06 20:48:16.357752
- Title: Subgradient Regularized Multivariate Convex Regression at Scale
- Title（参考訳）: スケールにおける準次正規化多変量凸回帰
- Authors: Wenyu Chen, Rahul Mazumder
- Abstract要約: 次数正規化凸回帰関数を$d$次元で$n$のサンプルに適合させる新しい大規模アルゴリズムを提案する。
本研究のフレームワークは,n=105$と$d=10$で,段階的な正規化凸回帰問題のインスタンスを数分で解くことができることを示す。
- 参考スコア（独自算出の注目度）: 21.55988846648753
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present new large-scale algorithms for fitting a subgradient regularized
multivariate convex regression function to $n$ samples in $d$ dimensions -- a
key problem in shape constrained nonparametric regression with applications in
statistics, engineering and the applied sciences. The infinite-dimensional
learning task can be expressed via a convex quadratic program (QP) with $O(nd)$
decision variables and $O(n^2)$ constraints. While instances with $n$ in the
lower thousands can be addressed with current algorithms within reasonable
runtimes, solving larger problems (e.g., $n\approx 10^4$ or $10^5$) is
computationally challenging. To this end, we present an active set type
algorithm on the dual QP. For computational scalability, we allow for
approximate optimization of the reduced sub-problems; and propose randomized
augmentation rules for expanding the active set. We derive novel computational
guarantees for our algorithms. We demonstrate that our framework can
approximately solve instances of the subgradient regularized convex regression
problem with $n=10^5$ and $d=10$ within minutes; and shows strong computational
performance compared to earlier approaches.
- Abstract（参考訳）: そこで本研究では,準次正規化多変量凸回帰関数を$d$次元のサンプル$n$に適合させるための新しい大規模アルゴリズムを提案する。
無限次元学習タスクは、$O(nd)$決定変数と$O(n^2)$制約を持つ凸二次プログラム(QP)を介して表現することができる。
数千ドル以下のインスタンスは、合理的なランタイム内で現在のアルゴリズムで対処できるが、より大きな問題(例えば、$n\approx 10^4$ または 10^5$)の解決は計算的に難しい。
この目的のために,双対 qp 上のアクティブセット型アルゴリズムを提案する。
計算スケーラビリティのために,削減された部分問題に対する近似最適化を可能にし,アクティブ集合の拡張のためのランダム化拡張規則を提案する。
我々はアルゴリズムに新しい計算保証を導出する。
提案手法は,10^5$ および $d=10$ の下位次正規化凸回帰問題のインスタンスを数分でほぼ解決できることを実証し,従来の手法と比較して強い計算性能を示す。
関連論文リスト
- Convergence analysis of online algorithms for vector-valued kernel regression [0.42970700836450487]
オンライン学習アルゴリズムを用いて雑音の多いベクトル値データから回帰関数を近似する問題を考察する。
RKHSノルムの期待二乗誤差は$C2 (m+1)-s/(2+s)$でバウンドできることを示し、$m$は現在の処理データの数である。
論文 参考訳（メタデータ） (2023-09-14T15:10:47Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Faster Convex Lipschitz Regression via 2-block ADMM [45.217150417108826]
本稿では,2ブロックADMM手法を用いて,幅広い凸関数学習問題を解く方法を示す。
凸リプシッツ回帰のタスクでは、提案アルゴリズムはデータセットに対して$O(n3 d1.5+n2 d2.5+n d3)$で収束する。
従来の手法と異なり,提案手法は既存手法の最大20倍高速であり,最先端技術に匹敵する結果が得られる。
論文 参考訳（メタデータ） (2021-11-02T03:10:41Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。