論文の概要: Projection-free Constrained Stochastic Nonconvex Optimization with
State-dependent Markov Data
- arxiv url: http://arxiv.org/abs/2206.11346v1
- Date: Wed, 22 Jun 2022 19:43:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-24 13:09:56.644760
- Title: Projection-free Constrained Stochastic Nonconvex Optimization with
State-dependent Markov Data
- Title（参考訳）: 状態依存マルコフデータを用いた投影自由制約確率的非凸最適化
- Authors: Abhishek Roy (1), Krishnakumar Balasubramanian (1), Saeed Ghadimi (2)
((1) Department of Statistics, University of California, Davis, (2)
Department of Management Sciences, University of Waterloo)
- Abstract要約: マルコフ型データを用いた制約付き非マルコフ型ケースチェーン問題に対するプロジェクションフリー勾配型アルゴリズムを提案する。
また,ニューラルネットワークを用いた戦略的分類の問題に対して,アルゴリズムの性能を実証的に示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a projection-free conditional gradient-type algorithm for
constrained nonconvex stochastic optimization problems with Markovian data. In
particular, we focus on the case when the transition kernel of the Markov chain
is state-dependent. Such stochastic optimization problems arise in various
machine learning problems including strategic classification and reinforcement
learning. For this problem, we establish that the number of calls to the
stochastic first-order oracle and the linear minimization oracle to obtain an
appropriately defined $\epsilon$-stationary point, are of the order
$\mathcal{O}(1/\epsilon^{2.5})$ and $\mathcal{O}(1/\epsilon^{5.5})$
respectively. We also empirically demonstrate the performance of our algorithm
on the problem of strategic classification with neural networks.
- Abstract（参考訳）: マルコフデータを用いた制約付き非凸確率最適化問題に対するプロジェクションフリー条件勾配型アルゴリズムについて検討した。
特に、マルコフ連鎖の遷移核が状態依存である場合に焦点を当てる。
このような確率的最適化問題は、戦略分類や強化学習を含む様々な機械学習問題に発生する。
この問題に対して、確率的一階のオラクルと線形最小化オラクルの呼び出し数がそれぞれ$\mathcal{o}(1/\epsilon^{2.5})$と$\mathcal{o}(1/\epsilon^{5.5})$の順で、適切に定義された$\epsilon$-stationary pointを得る。
また,ニューラルネットワークを用いた戦略的分類問題におけるアルゴリズムの性能を実証的に示す。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Stochastic Nested Compositional Bi-level Optimization for Robust Feature
Learning [11.236838268731804]
ネストされた二段階最適化問題を解くアルゴリズムを開発し,解析する。
提案アルゴリズムは,行列複雑性やミニバッチに依存しない。
論文 参考訳（メタデータ） (2023-07-11T15:52:04Z) - Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
本稿では,候補アルゴリズムの集合に有効な手法を提案する。
内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。
提案手法は,他のアルゴリズムのスコアを大幅に改善する。
論文 参考訳（メタデータ） (2023-05-26T21:49:37Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Inequality Constrained Stochastic Nonlinear Optimization via Active-Set
Sequential Quadratic Programming [17.9230793188835]
客観的・決定論的等式と不等式制約を用いた非線形最適化問題について検討する。
本稿では,有理関数として微分可能な拡張ラグランジアンを用いて,能動型逐次適応型プログラミングアルゴリズムを提案する。
アルゴリズムは、拡張ラグランジアンのパラメータを適応的に選択し、行探索を行い、ステップサイズを決定する。
論文 参考訳（メタデータ） (2021-09-23T17:12:17Z) - Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to
Decision-Dependent Risk Minimization [12.742028139557384]
有限和構造を持つ凸凹最小値問題の解法として,無作為なリシャッフィングを基本とした最適勾配Descent-Ascentアルゴリズムを提案する。
このアルゴリズムは凸最小化問題に対するゼロ階アルゴリズムと同じ収束率を持つことを示す。
論文 参考訳（メタデータ） (2021-06-16T18:49:59Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。