論文の概要: Faster Convex Lipschitz Regression via 2-block ADMM

• arxiv url: http://arxiv.org/abs/2111.01348v1
• Date: Tue, 2 Nov 2021 03:10:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-03 22:00:04.426258
• Title: Faster Convex Lipschitz Regression via 2-block ADMM
• Title（参考訳）: 2ブロックADMMによる高速凸リプシッツ回帰
• Authors: Ali Siahkamari, Durmus Alp Emre Acar, Christopher Liao, Kelly Geyer, Venkatesh Saligrama, Brian Kulis
• Abstract要約: 本稿では,2ブロックADMM手法を用いて,幅広い凸関数学習問題を解く方法を示す。 凸リプシッツ回帰のタスクでは、提案アルゴリズムはデータセットに対して$O(n3 d1.5+n2 d2.5+n d3)$で収束する。 従来の手法と異なり,提案手法は既存手法の最大20倍高速であり,最先端技術に匹敵する結果が得られる。
• 参考スコア（独自算出の注目度）: 45.217150417108826
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The task of approximating an arbitrary convex function arises in several learning problems such as convex regression, learning with a difference of convex (DC) functions, and approximating Bregman divergences. In this paper, we show how a broad class of convex function learning problems can be solved via a 2-block ADMM approach, where updates for each block can be computed in closed form. For the task of convex Lipschitz regression, we establish that our proposed algorithm converges at the rate of $O(n^3 d^{1.5}+n^2 d^{2.5}+n d^3)$ for a dataset $X \in R^{n\times d}$. This new rate improves the state of the art $O(n^5d^2$) available by interior point methods if $d = o( n^4)$. Further we provide similar solvers for DC regression and Bregman divergence learning. Unlike previous approaches, our method is amenable to the use of GPUs. We demonstrate on regression and metric learning experiments that our approach is up to 20 times faster than the existing method, and produces results that are comparable to state-of-the-art.
• Abstract（参考訳）: 任意の凸関数を近似するタスクは、凸回帰、凸関数(DC)の差による学習、ブレグマン発散の近似など、いくつかの学習問題に現れる。 本稿では,各ブロックの更新を閉じた形式で計算できる2ブロックadmmアプローチにより,凸関数学習問題の幅広いクラスをいかに解くかを示す。 凸リプシッツ回帰のタスクに対して、提案アルゴリズムはデータセット$X \in R^{n\times d}$に対して$O(n^3 d^{1.5}+n^2 d^{2.5}+n d^3)$の速度で収束する。 この新たなレートは、$d = o(n^4)$ の場合、内部ポイントメソッドで利用可能な $O(n^5d^2$) の状態を改善します。 さらに,直流回帰とブレグマン分岐学習に類似した解法を提供する。 従来の手法とは異なり、我々の手法はGPUの使用に適している。 回帰および計量学習実験において、我々の手法は既存の手法の最大20倍高速であり、最先端技術に匹敵する結果が得られることを示した。

関連論文リスト

• 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)
• Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
  多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。 我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
  論文  参考訳（メタデータ） (2024-03-05T12:28:00Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Optimality of Robust Online Learning [4.21768682940933]
  再生カーネルヒルベルト空間(RKHS)上の回帰のために,ロバストな損失関数$mathcalL_sigma$を用いたオンライン学習アルゴリズムについて検討する。 提案アルゴリズムは,条件付き平均関数の推定を目的としたオンライン最小二乗回帰の頑健な代替手段である。
  論文  参考訳（メタデータ） (2023-04-20T03:00:33Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• 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)
• Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
  本稿では,データに対する凸関数(DC関数)の差を利用した線形回帰手法を提案する。 実際に実装可能であることを示すとともに,実世界のデータセット上で既存の回帰/分類手法に匹敵する性能を有することを実証的に検証した。
  論文  参考訳（メタデータ） (2020-07-05T18:58:47Z)
• Subgradient Regularized Multivariate Convex Regression at Scale [21.55988846648753]
  次数正規化凸回帰関数を$d$次元で$n$のサンプルに適合させる新しい大規模アルゴリズムを提案する。 本研究のフレームワークは,n=105$と$d=10$で,段階的な正規化凸回帰問題のインスタンスを数分で解くことができることを示す。
  論文  参考訳（メタデータ） (2020-05-23T19:08:39Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。