論文の概要: Conservative Stochastic Optimization with Expectation Constraints
- arxiv url: http://arxiv.org/abs/2008.05758v2
- Date: Sat, 29 May 2021 05:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-31 00:07:42.505105
- Title: Conservative Stochastic Optimization with Expectation Constraints
- Title（参考訳）: 期待制約を伴う保守的確率的最適化
- Authors: Zeeshan Akhtar, Amrit Singh Bedi, and Ketan Rajawat
- Abstract要約: 本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
- 参考スコア（独自算出の注目度）: 11.393603788068777
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers stochastic convex optimization problems where the
objective and constraint functions involve expectations with respect to the
data indices or environmental variables, in addition to deterministic convex
constraints on the domain of the variables. Although the setting is generic and
arises in different machine learning applications, online and efficient
approaches for solving such problems have not been widely studied. Since the
underlying data distribution is unknown a priori, a closed-form solution is
generally not available, and classical deterministic optimization paradigms are
not applicable. State-of-the-art approaches, such as those using the saddle
point framework, can ensure that the optimality gap as well as the constraint
violation decay as $\O\left(T^{-\frac{1}{2}}\right)$ where $T$ is the number of
stochastic gradients. The domain constraints are assumed simple and handled via
projection at every iteration. In this work, we propose a novel conservative
stochastic optimization algorithm (CSOA) that achieves zero constraint
violation and $\O\left(T^{-\frac{1}{2}}\right)$ optimality gap.
Further, the projection operation (for scenarios when calculating projection
is expensive) in the proposed algorithm can be avoided by considering the
conditional gradient or Frank-Wolfe (FW) variant of the algorithm. The
state-of-the-art stochastic FW variants achieve an optimality gap of
$\O\left(T^{-\frac{1}{3}}\right)$ after $T$ iterations, though these algorithms
have not been applied to problems with functional expectation constraints. In
this work, we propose the FW-CSOA algorithm that is not only projection-free
but also achieves zero constraint violation with
$\O\left(T^{-\frac{1}{4}}\right)$ decay of the optimality gap. The efficacy of
the proposed algorithms is tested on two relevant problems: fair classification
and structured matrix completion.
- Abstract（参考訳）: 本稿では、変数の領域における決定論的凸制約に加えて、目的関数と制約関数がデータ指標や環境変数に対する期待を伴う確率的凸最適化問題を考察する。
設定は汎用的で、異なる機械学習アプリケーションで発生するが、そのような問題を解決するためのオンラインかつ効率的なアプローチは、広く研究されていない。
基礎となるデータ分布が未知であるため、一般にクローズドフォームソリューションは利用できず、古典的決定論的最適化パラダイムは適用できない。
saddle pointフレームワークを使用するような最先端のアプローチでは、最適性ギャップと制約違反の減衰が$\o\left(t^{-\frac{1}{2}}\right)$となることが保証される。
ドメインの制約は単純であると仮定し、イテレーション毎にプロジェクションによって処理される。
本研究では,ゼロ制約違反と$\O\left(T^{-\frac{1}{2}}\right)$Optimity gapを実現する新しい保守的確率最適化アルゴリズム(CSOA)を提案する。
さらに、提案アルゴリズムの条件勾配やfrank-wolfe(fw)変種を考慮して、提案アルゴリズムにおける投影演算(投影計算のシナリオは高価)を回避することができる。
最先端の確率的FW変種は$\O\left(T^{-\frac{1}{3}}\right)$の最適性ギャップを$T$反復後に達成するが、これらのアルゴリズムは機能期待制約の問題には適用されていない。
本研究では,プロジェクションフリーなだけでなく,$\O\left(T^{-\frac{1}{4}}\right)$最適性ギャップの減衰によるゼロ制約違反を実現するFW-CSOAアルゴリズムを提案する。
提案手法の有効性は, 公平な分類と構造化行列の完全性という2つの問題で検証された。
関連論文リスト
- Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳（メタデータ） (2023-11-18T23:06:33Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - 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) - Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained
Optimization [13.170519806372075]
2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。
最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。
提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
論文 参考訳（メタデータ） (2021-07-14T08:01:30Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。