論文の概要: Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization

• arxiv url: http://arxiv.org/abs/2312.03218v1
• Date: Wed, 6 Dec 2023 01:16:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-07 16:15:28.757907
• Title: Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization
• Title（参考訳）: 適応部分空間探索によるインスタンス・ファスター最適化の高速化
• Authors: Yuanshi Liu, Hanzhen Zhao, Yang Xu, Pengyun Yue, Cong Fang
• Abstract要約: グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。 本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
• 参考スコア（独自算出の注目度）: 6.896308995955336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient-based minimax optimal algorithms have greatly promoted the development of continuous optimization and machine learning. One seminal work due to Yurii Nesterov [Nes83a] established $\tilde{\mathcal{O}}(\sqrt{L/\mu})$ gradient complexity for minimizing an $L$-smooth $\mu$-strongly convex objective. However, an ideal algorithm would adapt to the explicit complexity of a particular objective function and incur faster rates for simpler problems, triggering our reconsideration of two defeats of existing optimization modeling and analysis. (i) The worst-case optimality is neither the instance optimality nor such one in reality. (ii) Traditional $L$-smoothness condition may not be the primary abstraction/characterization for modern practical problems. In this paper, we open up a new way to design and analyze gradient-based algorithms with direct applications in machine learning, including linear regression and beyond. We introduce two factors $(\alpha, \tau_{\alpha})$ to refine the description of the degenerated condition of the optimization problems based on the observation that the singular values of Hessian often drop sharply. We design adaptive algorithms that solve simpler problems without pre-known knowledge with reduced gradient or analogous oracle accesses. The algorithms also improve the state-of-art complexities for several problems in machine learning, thereby solving the open problem of how to design faster algorithms in light of the known complexity lower bounds. Specially, with the $\mathcal{O}(1)$-nuclear norm bounded, we achieve an optimal $\tilde{\mathcal{O}}(\mu^{-1/3})$ (v.s. $\tilde{\mathcal{O}}(\mu^{-1/2})$) gradient complexity for linear regression. We hope this work could invoke the rethinking for understanding the difficulty of modern problems in optimization.
• Abstract（参考訳）: 勾配に基づくミニマックス最適アルゴリズムは、連続最適化と機械学習の開発を大いに促進してきた。 yurii nesterov [nes83a] による独創的な研究により、$l$-smooth $\mu$-strongly convex の目的を最小化するために$\tilde{\mathcal{o}}(\sqrt{l/\mu})$gradient complexity が確立された。 しかし、理想的なアルゴリズムは、特定の目的関数の明示的な複雑さに適応し、より単純な問題に対してより速いレートを発生させ、既存の最適化モデリングと解析の2つの敗北を再考する。 (i)最悪のケースの最適性は、インスタンスの最適性でもそのようなものでもない。 (ii)従来のl$-smoothness条件は、現代の実用的な問題の主要な抽象化/キャラクタリゼーションではないかもしれない。 本稿では,線形回帰などを含む機械学習を直接応用した勾配に基づくアルゴリズムの設計と解析を行う新しい手法を公開する。 我々は、ヘッセンの特異値がしばしば急降下する観察に基づいて最適化問題の退化条件の記述を洗練させるために、2つの因子$(\alpha, \tau_{\alpha})$を導入する。 我々は、勾配の低下やoracleアクセスの類似した知識なしで、より単純な問題を解決する適応アルゴリズムを設計します。 このアルゴリズムはまた、機械学習におけるいくつかの問題に対する最先端の複雑さを改善し、既知の複雑さの低い境界を考慮してより高速なアルゴリズムを設計する方法というオープンな問題を解決する。 特に、$\tilde{\mathcal{O}(1)$-核ノルムを有界にすると、線形回帰に対して最適な$\tilde{\mathcal{O}}(\mu^{-1/3})$ (v.s.$\tilde{\mathcal{O}}(\mu^{-1/2})$)勾配複雑性が得られる。 この研究が、最適化における現代の問題の難しさを理解するための再考を呼び起こせることを願っている。

関連論文リスト

• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods [18.47705532817026]
  本研究では,スムーズな関数を持つ$epsilon$firstorder stationary point (FOSP) を求める問題について検討する。 本稿では,このオンライン学習問題を解決するために,新しい楽観的な準勾配近似法を提案する。
  論文  参考訳（メタデータ） (2024-12-03T05:20:05Z)
• 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)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning [12.069630105460766]
  AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。 本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-22T04:33:27Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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