論文の概要: 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} )$ の反復複雑性を達成する。
グローバルリプシッツ連続(部分的)勾配を仮定しない収束解析は、複合問題における既存の研究とは別の結果となる。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - 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) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、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) - On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization [31.714928102950584]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳（メタデータ） (2022-09-21T13:30:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。