論文の概要: Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction
- arxiv url: http://arxiv.org/abs/2103.08280v1
- Date: Mon, 15 Mar 2021 11:20:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-16 14:17:40.132368
- Title: Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction
- Title（参考訳）: 有限和最適化問題の低次複素性境界:結果と構成
- Authors: Yuze Han, Guangzeng Xie, Zhihua Zhang
- Abstract要約: 我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
- 参考スコア（独自算出の注目度）: 18.65143269806133
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The contribution of this paper includes two aspects. First, we study the
lower bound complexity for the minimax optimization problem whose objective
function is the average of $n$ individual smooth component functions. We
consider Proximal Incremental First-order (PIFO) algorithms which have access
to gradient and proximal oracle for each individual component. We develop a
novel approach for constructing adversarial problems, which partitions the
tridiagonal matrix of classical examples into $n$ groups. This construction is
friendly to the analysis of incremental gradient and proximal oracle. With this
approach, we demonstrate the lower bounds of first-order algorithms for finding
an $\varepsilon$-suboptimal point and an $\varepsilon$-stationary point in
different settings. Second, we also derive the lower bounds of minimization
optimization with PIFO algorithms from our approach, which can cover the
results in \citep{woodworth2016tight} and improve the results in
\citep{zhou2019lower}.
- Abstract（参考訳）: 本論文の貢献には2つの側面がある。
まず、目的関数が$ n$の個々の滑らかなコンポーネント関数の平均であるミニマックス最適化問題のより低い境界の複雑さを研究します。
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
この構成は漸進的勾配と近位オラクルの分析に好都合である。
このアプローチでは、異なる設定で$\varepsilon$-suboptimal pointと$\varepsilon$-stationary pointを見つけるための1次アルゴリズムの下位境界を実証する。
第2に、PIFOアルゴリズムによる最小化最適化の下位境界も提案手法から導出し、その結果をcitep{woodworth2016tight} でカバーし、その結果をcitep{zhou2019lower} で改善する。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳（メタデータ） (2023-09-04T19:47:04Z) - Stochastic Nested Compositional Bi-level Optimization for Robust Feature
Learning [11.236838268731804]
ネストされた二段階最適化問題を解くアルゴリズムを開発し,解析する。
提案アルゴリズムは,行列複雑性やミニバッチに依存しない。
論文 参考訳（メタデータ） (2023-07-11T15:52:04Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。