論文の概要: Randomized Bregman Coordinate Descent Methods for Non-Lipschitz
Optimization
- arxiv url: http://arxiv.org/abs/2001.05202v1
- Date: Wed, 15 Jan 2020 09:57:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 07:09:43.609143
- Title: Randomized Bregman Coordinate Descent Methods for Non-Lipschitz
Optimization
- Title(参考訳): 非Lipschitz最適化のためのランダム化ブレグマン座標Descent法
- Authors: Tianxiang Gao, Songtao Lu, Jia Liu, Chris Chu
- Abstract要約: そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。
提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
- 参考スコア(独自算出の注目度): 31.474280642125734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new \textit{randomized Bregman (block) coordinate descent}
(RBCD) method for minimizing a composite problem, where the objective function
could be either convex or nonconvex, and the smooth part are freed from the
global Lipschitz-continuous (partial) gradient assumption. Under the notion of
relative smoothness based on the Bregman distance, we prove that every limit
point of the generated sequence is a stationary point. Further, we show that
the iteration complexity of the proposed method is $O(n\varepsilon^{-2})$ to
achieve $\epsilon$-stationary point, where $n$ is the number of blocks of
coordinates. If the objective is assumed to be convex, the iteration complexity
is improved to $O(n\epsilon^{-1} )$. If, in addition, the objective is strongly
convex (relative to the reference function), the global linear convergence rate
is recovered. We also present the accelerated version of the RBCD method, which
attains an $O(n\varepsilon^{-1/\gamma} )$ iteration complexity for the convex
case, where the scalar $\gamma\in [1,2]$ is determined by the
\textit{generalized translation variant} of the Bregman distance. Convergence
analysis without assuming the global Lipschitz-continuous (partial) gradient
sets our results apart from the existing works in the composite problems.
- Abstract(参考訳): 目的関数が凸か非凸かのいずれかであり、滑らかな部分は大域的なリプシッツ連続(部分的)勾配の仮定から解放されるような合成問題を最小化するための新しい \textit{randomized Bregman (block) coordinate descent} (RBCD) 法を提案する。
ブレグマン距離に基づく相対滑らか性の概念の下で、生成された列のすべての極限点が定常点であることを証明する。
さらに、提案手法の反復複雑性は、$O(n\varepsilon^{-2})$で、$\epsilon$-stationary point、$n$は座標のブロック数であることを示す。
目的が凸であると仮定すると、反復複雑性は$O(n\epsilon^{-1} )$に改善される。
さらに、目的が強い凸(参照関数に関連して)であれば、大域的線形収束率は回復される。
また, rbcd 法の高速化版を示し, ブレグマン距離の \textit{generalized translation variant} によってスカラー $\gamma\in [1,2]$ が決定されるような凸ケースに対して $o(n\varepsilon^{-1/\gamma} )$ の反復複雑性を達成する。
グローバルリプシッツ連続(部分的)勾配を仮定しない収束解析は、複合問題における既存の研究とは別の結果となる。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - Penalized Langevin and Hamiltonian Monte Carlo Algorithms for
Constrained Sampling [8.333246626497363]
分布(x)prop ef(x)$と$x$が凸体上で制約されるような制約付きサンプリング問題を考える。
我々は,制限されたサンプリング問題をペナルティ関数制約違反を導入して非拘束なものに変換する,ペナルティ付ハミルトンモンテカルロダイナミクス(PLD)とペナルティ付ハミルトンモンテカルロダイナミクス(PHMC)を提案する。
PHMCでは、Hessianが$であるときに $tildemathcalO(sqrtd/varepsilon7)$に改善します。
論文 参考訳(メタデータ) (2022-11-29T18:43:22Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳(メタデータ) (2022-02-27T09:41:43Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳(メタデータ) (2022-02-19T20:31:05Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。