論文の概要: Big-Step-Little-Step: Efficient Gradient Methods for Objectives with
Multiple Scales
- arxiv url: http://arxiv.org/abs/2111.03137v1
- Date: Thu, 4 Nov 2021 20:09:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-08 15:13:20.334954
- Title: Big-Step-Little-Step: Efficient Gradient Methods for Objectives with
Multiple Scales
- Title（参考訳）: Big-Step-Little-Step:複数スケール対象に対する効率的な勾配法
- Authors: Jonathan Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory
Valiant, Honglin Yuan
- Abstract要約: 関数 $f : mathbbRd rightarrow mathbbR$ の最小化は、未知の非相互作用な滑らかで凸な函数の和として暗黙的に分解可能である。
そこで我々は,多種多様な条件の最適化問題を効率的に解くために,勾配に基づく新しい手法を提案する。
- 参考スコア（独自算出の注目度）: 45.994415581007054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide new gradient-based methods for efficiently solving a broad class
of ill-conditioned optimization problems. We consider the problem of minimizing
a function $f : \mathbb{R}^d \rightarrow \mathbb{R}$ which is implicitly
decomposable as the sum of $m$ unknown non-interacting smooth, strongly convex
functions and provide a method which solves this problem with a number of
gradient evaluations that scales (up to logarithmic factors) as the product of
the square-root of the condition numbers of the components. This complexity
bound (which we prove is nearly optimal) can improve almost exponentially on
that of accelerated gradient methods, which grow as the square root of the
condition number of $f$. Additionally, we provide efficient methods for solving
stochastic, quadratic variants of this multiscale optimization problem. Rather
than learn the decomposition of $f$ (which would be prohibitively expensive),
our methods apply a clean recursive "Big-Step-Little-Step" interleaving of
standard methods. The resulting algorithms use $\tilde{\mathcal{O}}(d m)$
space, are numerically stable, and open the door to a more fine-grained
understanding of the complexity of convex optimization beyond condition number.
- Abstract（参考訳）: 最適化問題の幅広いクラスを効率的に解くための新しい勾配ベース手法を提案する。
未知の非相互作用的滑らかで強い凸関数の和として暗黙的に分解可能な関数 $f : \mathbb{R}^d \rightarrow \mathbb{R}$ の最小化の問題を考えるとともに、成分の条件数の平方根の積としてスケールする勾配評価(対数因子まで)でこの問題を解決する方法を提案する。
この複雑性境界(ほぼ最適であることが証明されている)は、条件数$f$の平方根として成長する加速勾配法よりも指数関数的に改善することができる。
さらに, このマルチスケール最適化問題の確率的, 二次的変種を効率的に解く手法を提案する。
この方法では、$f$の分解を学習する代わりに、標準的なメソッドのクリーンな再帰的な"Big-Step-Little-Step"インターリービングを適用する。
結果のアルゴリズムは$\tilde{\mathcal{O}}(d m)$ space を使い、数値的に安定であり、条件数を超えた凸最適化の複雑さをより詳細に理解するための扉を開く。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Accelerated Gradient Algorithms with Adaptive Subspace Search for
Instance-Faster Optimization [6.896308995955336]
グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。
本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
論文 参考訳（メタデータ） (2023-12-06T01:16:10Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - 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) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。