論文の概要: Stochastic Compositional Gradient Descent under Compositional
constraints
- arxiv url: http://arxiv.org/abs/2012.09400v1
- Date: Thu, 17 Dec 2020 05:38:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-02 23:35:09.281411
- Title: Stochastic Compositional Gradient Descent under Compositional
constraints
- Title（参考訳）: 組成制約下での確率的組成勾配降下
- Authors: Srujan Teja Thomdapu, Harshvardhan, Ketan Rajawat
- Abstract要約: 目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。
この問題は、公平な分類/回帰とキューシステムの設計に生じる。
提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
- 参考スコア（独自算出の注目度）: 13.170519806372075
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work studies constrained stochastic optimization problems where the
objective and constraint functions are convex and expressed as compositions of
stochastic functions. The problem arises in the context of fair classification,
fair regression, and the design of queuing systems. Of particular interest is
the large-scale setting where an oracle provides the stochastic gradients of
the constituent functions, and the goal is to solve the problem with a minimal
number of calls to the oracle. The problem arises in fair
classification/regression and in the design of queuing systems. Owing to the
compositional form, the stochastic gradients provided by the oracle do not
yield unbiased estimates of the objective or constraint gradients. Instead, we
construct approximate gradients by tracking the inner function evaluations,
resulting in a quasi-gradient saddle point algorithm. We prove that the
proposed algorithm is guaranteed to find the optimal and feasible solution
almost surely. We further establish that the proposed algorithm requires
$\mathcal{O}(1/\epsilon^4)$ data samples in order to obtain an
$\epsilon$-approximate optimal point while also ensuring zero constraint
violation. The result matches the sample complexity of the stochastic
compositional gradient descent method for unconstrained problems and improves
upon the best-known sample complexity results for the constrained settings. The
efficacy of the proposed algorithm is tested on both fair classification and
fair regression problems. The numerical results show that the proposed
algorithm outperforms the state-of-the-art algorithms in terms of the
convergence rate.
- Abstract（参考訳）: 本研究は、目的関数と制約関数が凸であり、確率関数の合成として表現される確率的最適化問題を制約した。
この問題は、公正な分類、公平な回帰、およびキューシステムの設計という文脈で生じる。
特に興味深いのは、オラクルが構成関数の確率的勾配を提供する大規模な設定であり、その目的は、オラクルへの最小限の呼び出しで問題を解決することである。
この問題は、公平な分類/回帰とキューシステムの設計に生じる。
構成形式により、オラクルによって提供される確率勾配は、目的あるいは制約勾配の偏りのない見積もりを生じさせない。
代わりに, 内関数評価を追跡することで近似勾配を構築し, 準次saddle pointアルゴリズムを導出する。
提案アルゴリズムは最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
さらに、提案アルゴリズムでは、制約違反をゼロにしつつ、$\epsilon$-approximate の最適点を得るために$\mathcal{o}(1/\epsilon^4)$ データサンプルが必要であることも確認する。
その結果、制約のない問題に対する確率的組成勾配降下法のサンプル複雑性が一致し、制約付き設定の最もよく知られたサンプル複雑性結果が改善される。
提案アルゴリズムの有効性は、公平な分類と公平な回帰問題の両方で検証される。
数値計算の結果,提案アルゴリズムは収束率の観点から最先端のアルゴリズムよりも優れていた。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。
提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
論文 参考訳（メタデータ） (2023-04-28T15:30:43Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳（メタデータ） (2022-04-12T16:27:49Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳（メタデータ） (2021-09-07T17:21:09Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳（メタデータ） (2020-10-23T05:24:05Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Non-asymptotic bounds for stochastic optimization with biased noisy
gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。
提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文 参考訳（メタデータ） (2020-02-26T12:53:04Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。