論文の概要: AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization
- arxiv url: http://arxiv.org/abs/2504.14741v1
- Date: Sun, 20 Apr 2025 21:07:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-29 20:22:39.363111
- Title: AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization
- Title（参考訳）: AltGDmin:部分分離最適化のための代替GDと最小化
- Authors: Namrata Vaswani,
- Abstract要約: 本稿では、勾配交互降下(GD)と最小化(AltGDmin)と呼ばれる新しい最適化ソリューションフレームワークについて述べる。
AltGDmin はしばしば、(i) 1 つの変数の集合 Zb 上の最小化が他の集合 Za よりもはるかに速く、(ii) コスト関数は w.r.t Za で微分可能であるような問題に対して、AltMin よりも高速な解である。
- 参考スコア（独自算出の注目度）: 20.370944501500762
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This article describes a novel optimization solution framework, called alternating gradient descent (GD) and minimization (AltGDmin), that is useful for many problems for which alternating minimization (AltMin) is a popular solution. AltMin is a special case of the block coordinate descent algorithm that is useful for problems in which minimization w.r.t one subset of variables keeping the other fixed is closed form or otherwise reliably solved. Denote the two blocks/subsets of the optimization variables Z by Za, Zb, i.e., Z = {Za, Zb}. AltGDmin is often a faster solution than AltMin for any problem for which (i) the minimization over one set of variables, Zb, is much quicker than that over the other set, Za; and (ii) the cost function is differentiable w.r.t. Za. Often, the reason for one minimization to be quicker is that the problem is ``decoupled" for Zb and each of the decoupled problems is quick to solve. This decoupling is also what makes AltGDmin communication-efficient for federated settings. Important examples where this assumption holds include (a) low rank column-wise compressive sensing (LRCS), low rank matrix completion (LRMC), (b) their outlier-corrupted extensions such as robust PCA, robust LRCS and robust LRMC; (c) phase retrieval and its sparse and low-rank model based extensions; (d) tensor extensions of many of these problems such as tensor LRCS and tensor completion; and (e) many partly discrete problems where GD does not apply -- such as clustering, unlabeled sensing, and mixed linear regression. LRCS finds important applications in multi-task representation learning and few shot learning, federated sketching, and accelerated dynamic MRI. LRMC and robust PCA find important applications in recommender systems, computer vision and video analytics.
- Abstract（参考訳）: 本稿では、交互勾配降下(GD)と最小化(AltGDmin)と呼ばれる新しい最適化ソリューションフレームワークについて述べる。
AltMin はブロック座標降下アルゴリズムの特別な場合であり、最小化 w.r. 変数の1つの部分集合が閉じたか、あるいは確実に解かれるような問題に有用である。
最適化変数 Z の2つのブロック/サブセットをZ, Zb, すなわち Z = {Za, Zb} で記述する。
AltGDminは、問題に対してAltMinよりも高速なソリューションであることが多い。
i) 1つの変数の集合であるZbに対する最小化は、他の集合であるZaよりもはるかに高速である。
(ii)コスト関数は w.r.t. Za で微分可能である。
多くの場合、1つの最小化がより速くなる理由は、問題は Zb に対して `非結合' であり、それぞれの分離された問題はすぐに解けるからである。
この分離はまた、AltGDmin通信をフェデレーション設定に効率よくする。
この仮定が成立する重要な例としては
(a)ローランク列ワイド圧縮センシング(LRCS)、ローランク行列補完(LRMC)
(b)ロバストPCA、ロバストLRCS、ロバストLRMCなどのアウトラヤ崩壊した拡張
(c) 位相検索とそのスパース及びローランクモデルに基づく拡張
(d)テンソルLRCSやテンソル完備化など,これらの問題の多くに対するテンソル拡張
例えば、クラスタリング、ラベルなしセンシング、混合線形回帰などである。
LRCSはマルチタスク表現学習やショット学習,フェデレートスケッチ,動的MRIの高速化において重要な応用を見出す。
LRMCとロバストPCAは、レコメンデータシステム、コンピュータビジョン、ビデオ分析において重要な応用を見出す。
関連論文リスト
- Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。
思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。
SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
論文 参考訳（メタデータ） (2025-04-13T13:35:41Z) - 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) - Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。
最適パラメトリック解を特徴付ける。
歪みと知覚制約について十分な条件を提供する。
論文 参考訳（メタデータ） (2024-08-27T12:50:12Z) - Efficient Federated Low Rank Matrix Completion [18.471262688125645]
低階行列完備化(LRMC)問題を解くために,AltGDと最小化(AltGDmin)と呼ばれるソリューションを開発し,解析する。
我々の理論的保証は、AltGDminがフェデレートされた環境で最も通信効率の良いソリューションであることを示唆している。
私たちは、AltMinのサンプル複雑性の保証を改善するために、我々の補題をどのように利用できるかを示します。
論文 参考訳（メタデータ） (2024-05-10T16:12:35Z) - Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。
IG/RRスキームの簡易制御による修正を定義する。
我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
論文 参考訳（メタデータ） (2022-12-04T15:26:36Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Smooth over-parameterized solvers for non-smooth structured optimization [3.756550107432323]
非滑らか性 (non-smoothness) は、空間性、群空間性、低ランクエッジ、鋭いエッジなどの解の構造的制約を符号化する。
我々は、基礎となる非滑らかな最適化問題の非重み付きだが滑らかな過度パラメータ化を運用する。
我々の主な貢献は変数の一部を明示的に最小化することで新しい定式化を定義する変数射影(VarPro)を適用することです。
論文 参考訳（メタデータ） (2022-05-03T09:23:07Z) - Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity [14.93584434176082]
擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
論文 参考訳（メタデータ） (2021-08-19T15:50:41Z) - Smooth Bilevel Programming for Sparse Regularization [5.177947445379688]
反復再重み付き最小二乗法(IRLS)は、機械学習における空間的回帰問題を解くための一般的な手法である。
両レベルスキームが組み合わさって、IRLSの驚くほど再パラメータ化が、いかにスパーシティの上位化を実現するかを示す。
論文 参考訳（メタデータ） (2021-06-02T19:18:22Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。