論文の概要: Untangling Lariats: Subgradient Following of Variationally Penalized Objectives
- arxiv url: http://arxiv.org/abs/2405.04710v1
- Date: Tue, 7 May 2024 23:08:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-09 15:45:06.953612
- Title: Untangling Lariats: Subgradient Following of Variationally Penalized Objectives
- Title（参考訳）: アンタングリング・ラリア:変分刑罰の対象の段階的追従
- Authors: Kai-Chia Mo, Shai Shalev-Shwartz, Nisæl Shártov,
- Abstract要約: 我々は,この装置の特殊な場合として,溶質ラッソおよびイソトニックレグレッションの既知のアルゴリズムを導出する。
最後に,任意の畳み込みフィルタの出力によって特徴づけられる変分罰則に対する格子型下次解法を導出する。
- 参考スコア（独自算出の注目度）: 10.043139484808949
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We describe a novel subgradient following apparatus for calculating the optimum of convex problems with variational penalties. In this setting, we receive a sequence $y_i,\ldots,y_n$ and seek a smooth sequence $x_1,\ldots,x_n$. The smooth sequence attains the minimum Bregman divergence to an input sequence with additive variational penalties in the general form of $\sum_i g_i(x_{i+1}-x_i)$. We derive, as special cases of our apparatus, known algorithms for the fused lasso and isotonic regression. Our approach also facilitates new variational penalties such as non-smooth barrier functions. We next derive and analyze multivariate problems in which $\mathbf{x}_i,\mathbf{y}_i\in\mathbb{R}^d$ and variational penalties that depend on $\|\mathbf{x}_{i+1}-\mathbf{x}_i\|$. The norms we consider are $\ell_2$ and $\ell_\infty$ which promote group sparsity. Last but not least, we derive a lattice-based subgradient following for variational penalties characterized through the output of arbitrary convolutional filters. This paradigm yields efficient solvers for problems in which sparse high-order discrete derivatives such as acceleration and jerk are desirable.
- Abstract（参考訳）: 本稿では,変分ペナルティによる凸問題の最適解を求めるための,新しい段階的追従手法について述べる。
この設定では、配列 $y_i,\ldots,y_n$ を受け取り、滑らかなシーケンス $x_1,\ldots,x_n$ を求める。
滑らかな列は、$\sum_i g_i(x_{i+1}-x_i)$の一般的な形式で加法的変分ペナルティを持つ入力列への最小のブレグマン発散を達成する。
我々は,この装置の特殊な場合として,溶質ラッソおよびイソトニックレグレッションの既知のアルゴリズムを導出する。
また,本手法は非平滑障壁関数などの新たな変分罰を助長する。
次に、$\mathbf{x}_i,\mathbf{y}_i\in\mathbb{R}^d$ と $\|\mathbf{x}_{i+1}-\mathbf{x}_i\|$ に依存する変分罰を導いて解析する。
私たちが考慮するノルムは、群疎性を促進する $\ell_2$ と $\ell_\infty$ である。
最後に,任意の畳み込みフィルタの出力によって特徴づけられる変分罰則に対して,格子に基づく下位次数列を導出する。
このパラダイムは、加速度やジャークのようなスパースな高次微分が望ましい問題に対して効率的な解法を与える。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - High Probability Guarantees for Random Reshuffling [5.663909018247509]
非行列最適化問題に対処するために、ランダムリシャッフル(mathsfRR$)の勾配法を検討する。
本研究ではまず,$mathsfRR$sサンプリング手順におけるニューラルネットワークの複雑さについて検討する。
そこで我々は,乱数化摂動手順の定常点を含むランダムリシャッフル法(mathsfp$mathsfRR$)を設計する。
論文 参考訳（メタデータ） (2023-11-20T15:17:20Z) - First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians [4.62316736194615]
我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。
また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
論文 参考訳（メタデータ） (2023-09-05T17:40:54Z) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳（メタデータ） (2023-01-17T18:44:41Z) - Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
目的が目標分布である$pi(x)prop ef(x)$から$x$が制約されたときにサンプリングする制約付きサンプリング問題を考える。
ペナルティ法によって動機付けられた制約付き問題を,制約違反に対するペナルティ関数を導入することにより,非制約サンプリング問題に変換する。
PSGLD と PSGULMC の場合、$tildemathcalO(d/varepsilon18)$ が強凸で滑らかであるとき、$tildemathcalO(d/varepsilon) を得る。
論文 参考訳（メタデータ） (2022-11-29T18:43:22Z) - Sparse Bayesian Lasso via a Variable-Coefficient $\ell_1$ Penalty [0.9176056742068814]
学習可能なペナルティの重みを、ハイパープライアでlambda_p$と定義します。
我々は,この可変係数$ell_$ペナルティの理論的性質を,ペナル化可能性の文脈で検討した。
我々はスパースベイズ・ラッソと呼ばれるモデルを開発し、ラッソ回帰のような定性的な振る舞いを任意の変分モデルに適用することができる。
論文 参考訳（メタデータ） (2022-11-09T18:19:23Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳（メタデータ） (2022-11-03T14:41:46Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。