論文の概要: Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity
- arxiv url: http://arxiv.org/abs/2208.03811v1
- Date: Sun, 7 Aug 2022 20:53:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-09 14:26:28.530046
- Title: Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity
- Title（参考訳）: 近距離勾配Oracle複雑度を用いた非滑らかな凸最適化
- Authors: Sally Dong, Haotian Jiang, Yin Tat Lee, Swati Padmanabhan, and
Guanghao Ye
- Abstract要約: 上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
- 参考スコア（独自算出の注目度）: 15.18055488087588
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many fundamental problems in machine learning can be formulated by the convex
program \[ \min_{\theta\in R^d}\ \sum_{i=1}^{n}f_{i}(\theta), \] where each
$f_i$ is a convex, Lipschitz function supported on a subset of $d_i$
coordinates of $\theta$. One common approach to this problem, exemplified by
stochastic gradient descent, involves sampling one $f_i$ term at every
iteration to make progress. This approach crucially relies on a notion of
uniformity across the $f_i$'s, formally captured by their condition number. In
this work, we give an algorithm that minimizes the above convex formulation to
$\epsilon$-accuracy in $\widetilde{O}(\sum_{i=1}^n d_i \log (1 /\epsilon))$
gradient computations, with no assumptions on the condition number. The
previous best algorithm independent of the condition number is the standard
cutting plane method, which requires $O(nd \log (1/\epsilon))$ gradient
computations. As a corollary, we improve upon the evaluation oracle complexity
for decomposable submodular minimization by Axiotis et al. (ICML 2021). Our
main technical contribution is an adaptive procedure to select an $f_i$ term at
every iteration via a novel combination of cutting-plane and interior-point
methods.
- Abstract（参考訳）: 機械学習における多くの基本的な問題は、convexプログラム \[ \min_{\theta\in r^d}\ \sum_{i=1}^{n}f_{i}(\theta), \] によって定式化することができる。
この問題に対する一般的なアプローチは、確率勾配降下によって例示され、各イテレーションで1$f_i$項をサンプリングして進行させる。
このアプローチは、条件番号によって正式にキャプチャされた$f_i$s全体の均一性の概念に決定的に依存する。
本研究では,上記の凸定式化を$\epsilon$-accuracy in $\widetilde{O}(\sum_{i=1}^n d_i \log (1 /\epsilon))$グラデーション計算で最小化するアルゴリズムを提案する。
条件数に依存しない以前の最良のアルゴリズムは標準的な切削平面法であり、$O(nd \log (1/\epsilon))$グラデーション計算を必要とする。
Axiotis et al. (ICML 2021) による分解可能な部分モジュラー最小化のための評価オラクルの複雑さを改善した。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせて、各イテレーションで$f_i$項を選択する適応的な手順である。
関連論文リスト
- Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - 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) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。