論文の概要: Distributionally Robust Optimization via Ball Oracle Acceleration

• arxiv url: http://arxiv.org/abs/2203.13225v1
• Date: Thu, 24 Mar 2022 17:31:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-25 15:50:02.518572
• Title: Distributionally Robust Optimization via Ball Oracle Acceleration
• Title（参考訳）: Ball Oracle Accelerationによる分散ロバスト最適化
• Authors: Yair Carmon, Danielle Hausler
• Abstract要約: 凸損失の分散ロバスト最適化(DRO)のためのアルゴリズムを開発し,解析する。 この問題に対する既存のアルゴリズムと比較して、最大$epsilon-4/3$の係数で複雑性を改善する。
• 参考スコア（独自算出の注目度）: 8.417186276756336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. In particular, we consider group-structured and bounded $f$-divergence uncertainty sets. Our approach relies on an accelerated method that queries a ball optimization oracle, i.e., a subroutine that minimizes the objective within a small ball around the query point. Our main contribution is efficient implementations of this oracle for DRO objectives. For DRO with $N$ non-smooth loss functions, the resulting algorithms find an $\epsilon$-accurate solution with $\widetilde{O}\left(N\epsilon^{-2/3} + \epsilon^{-2}\right)$ first-order oracle queries to individual loss functions. Compared to existing algorithms for this problem, we improve complexity by a factor of up to $\epsilon^{-4/3}$.
• Abstract（参考訳）: 凸損失の分散ロバスト最適化(DRO)のためのアルゴリズムを開発し解析する。 特に、グループ構造および有界な$f$-divergenceの不確かさ集合を考える。 我々のアプローチは、ボール最適化オラクル、すなわちクエリポイント周辺の小さなボール内の目的を最小化するサブルーチンをクエリする高速化手法に依存している。 我々の主な貢献は、DRO目的のためのこのオラクルの効率的な実装である。 非滑らかな損失関数を持つDROの場合、結果は$\epsilon$-accurate solution with $\widetilde{O}\left(N\epsilon^{-2/3} + \epsilon^{-2}\right)$ one-order oracle query to individual loss functionである。 この問題に対する既存のアルゴリズムと比較して、複雑性を最大$\epsilon^{-4/3}$で改善する。

関連論文リスト

• 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)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal [23.94542304111204]
  本研究では,1次凸最適化に最適なオラクル複雑性を実現するためには,二次記憶が必要であることを示す。 単位球上の1ドルのLipschitz凸関数を1/d4$精度で最小化するためには、少なくともd2-delta$ビットのメモリを使用する決定論的一階述語アルゴリズムは$tildeOmega(d1+delta/3)$クエリを生成する必要がある。
  論文  参考訳（メタデータ） (2023-02-09T22:37:27Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-19T16:04:40Z)
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
  我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。 古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
  論文  参考訳（メタデータ） (2021-03-15T11:20:31Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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