論文の概要: Proximal and Federated Random Reshuffling
- arxiv url: http://arxiv.org/abs/2102.06704v1
- Date: Fri, 12 Feb 2021 18:59:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-15 12:57:51.251340
- Title: Proximal and Federated Random Reshuffling
- Title（参考訳）: 近縁・連成ランダムリシャッフル
- Authors: Konstantin Mishchenko and Ahmed Khaled and Peter Richt\'arik
- Abstract要約: ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
- 参考スコア（独自算出の注目度）: 11.83842808044211
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD)
without replacement, is a popular and theoretically grounded method for
finite-sum minimization. We propose two new algorithms: Proximal and Federated
Random Reshuffing (ProxRR and FedRR). The first algorithm, ProxRR, solves
composite convex finite-sum minimization problems in which the objective is the
sum of a (potentially non-smooth) convex regularizer and an average of $n$
smooth objectives. We obtain the second algorithm, FedRR, as a special case of
ProxRR applied to a reformulation of distributed problems with either
homogeneous or heterogeneous data. We study the algorithms' convergence
properties with constant and decreasing stepsizes, and show that they have
considerable advantages over Proximal and Local SGD. In particular, our methods
have superior complexities and ProxRR evaluates the proximal operator once per
epoch only. When the proximal operator is expensive to compute, this small
difference makes ProxRR up to $n$ times faster than algorithms that evaluate
the proximal operator in every iteration. We give examples of practical
optimization tasks where the proximal operator is difficult to compute and
ProxRR has a clear advantage. Finally, we corroborate our results with
experiments on real data sets.
- Abstract（参考訳）: ランダムリシャッフル法(Random Reshuffling, RR)は、有限サム最小化法として人気があり理論上は基礎的な手法である。
新しいアルゴリズムとして、ProximalとFederated Random Reshuffing(ProxRRとFedRR)を提案する。
最初のアルゴリズムであるproxrrは、対象が(潜在的に非スムースな)凸正則化子と平均で$n$の滑らかな目的の和である複合凸有限サム最小化問題を解く。
2番目のアルゴリズムであるFedRRをProxRRの特別なケースとして取得し、均質または異質なデータによる分散問題の形式化に適用する。
アルゴリズムの収束特性を定数および減少ステップ数で検討し、近位および局所SGDよりも有意な利点を有することを示した。
特に,本手法は複雑度が優れており,ProxRRはエポックに1度だけ近位演算子を評価する。
近位演算子が計算にコストがかかると、この小さな差により、proxrrは各イテレーションで近位演算子を評価するアルゴリズムよりも最大で10ドル高速になる。
我々は、近位演算子が計算が困難であり、ProxRRが明確な利点を有する実用的な最適化タスクの例を与える。
最後に、実際のデータセットに関する実験で結果を裏付ける。
関連論文リスト
- SOREL: A Stochastic Algorithm for Spectral Risks Minimization [1.6574413179773761]
スペクトルリスクは機械学習、特に現実世界の意思決定において幅広い応用がある。
異なるサンプルポイントの損失に異なる重みを割り当てることで、平均的なパフォーマンスと最悪のパフォーマンスの間にモデルのパフォーマンスを配置することができる。
SORELはスペクトルリスク最小化のための収束保証をもつ最初の勾配に基づくアルゴリズムである。
論文 参考訳（メタデータ） (2024-07-19T18:20:53Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。
本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。
最後に,提案手法に適用可能な最終収束率を導出する。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Distributed Random Reshuffling over Networks [7.013052033764372]
凸関数と滑らかな対象関数の問題を解くために分散resh-upr (D-RR) アルゴリズムを提案する。
特に、滑らかな凸対象関数に対して、D-RRはD-T収束率(T がエポック数を数える)を大域ドライブ間の距離で達成する。
論文 参考訳（メタデータ） (2021-12-31T03:59:37Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。
数値実験では, 既存の再起動バージョンよりも改善が見られた。
論文 参考訳（メタデータ） (2021-08-10T07:15:07Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Random Reshuffling: Simple Analysis with Vast Improvements [9.169947558498535]
ランダムリシャッフル(Random Reshuffling, RR)は、データリシャッフルと共に反復降下ステップを利用する有限サム関数を最小化するアルゴリズムである。
論文 参考訳（メタデータ） (2020-06-10T17:57:21Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。