論文の概要: Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

• arxiv url: http://arxiv.org/abs/2202.13212v1
• Date: Sat, 26 Feb 2022 19:10:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-03 08:41:47.684741
• Title: Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization
• Title（参考訳）: 複合凸最小化のための高速ワンサンプル確率条件勾配法
• Authors: Gideon Dresdner, Maria-Luiza Vladarean, Gunnar R\"atsch, Francesco Locatello, Volkan Cevher, Alp Yurtsever
• Abstract要約: 滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
• 参考スコア（独自算出の注目度）: 61.26619639722804
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm's execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.
• Abstract（参考訳）: 滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化する確率的条件勾配法(CGM)を提案する。 このテンプレートの既存のCGM変種は、収束速度が遅いか、アルゴリズムの実行中にバッチサイズを慎重に増やさなければならないため、完全な勾配が計算される。 対照的に,確率的平均勾配(sag)推定器を備えた提案手法では,反復毎に1つのサンプルしか必要としない。 それでも、より洗練された分散低減技術と同等の高速収束率を保証する。 アプリケーションでは、多くの分離可能な制約のある問題に特に重点を置いています。 このような問題は、機械学習や理論計算機科学で生じる半定値プログラミング(SDP)の定式化に多い。 本研究では,行列補完,教師なしクラスタリング,スペルストカットSDPに関する数値実験を行う。

関連論文リスト

• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。 平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
  論文  参考訳（メタデータ） (2024-05-17T21:17:27Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties [8.294148737585543]
  本稿では,非二次絶対および非平滑収束ペナルティの存在下での凹凸および切断された量子レグレッションについて検討する。 本稿では,スパース回帰に特化してSIADと呼ばれるペナルティ乗算器が増加する新しいループADMアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-04T21:48:51Z)
• Aiming towards the minimizers: fast convergence of SGD for overparametrized problems [25.077446336619378]
  本稿では,勾配法と同一のケース複雑性を有する勾配法を提案する。 既存の保証は全て勾配法で小さなステップを踏む必要があり、結果として収束速度ははるかに遅くなる。 我々は,線形出力層を用いた十分に広いフィードフォワードニューラルネットワークのトレーニングにおいて,この条件が成り立つことを実証した。
  論文  参考訳（メタデータ） (2023-06-05T05:21:01Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization [15.82816385434718]
  本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。 我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。 我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
  論文  参考訳（メタデータ） (2020-06-20T13:40:27Z)
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
  高速収束を提供するランゲヴィン・モンテカルロ(LMC)は勾配近似の計算を必要とする。 実際には、有限差分近似を代理として使用し、高次元では高価である。 本稿では,新しい分散低減手法であるCoordinates Averaging Descent (RCAD)を導入し,過度に損傷を受けたLCCと過度に損傷を受けたLCCを併用する。
  論文  参考訳（メタデータ） (2020-06-10T21:08:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。