Fugu-MT 論文翻訳(概要): Zeroth-Order Alternating Randomized Gradient Projection Algorithms for General Nonconvex-Concave Minimax Problems

論文の概要: Zeroth-Order Alternating Randomized Gradient Projection Algorithms for General Nonconvex-Concave Minimax Problems

arxiv url: http://arxiv.org/abs/2108.00473v1
Date: Sun, 1 Aug 2021 15:23:49 GMT
ステータス: 処理完了
システム内更新日: 2021-08-03 15:29:20.253252
Title: Zeroth-Order Alternating Randomized Gradient Projection Algorithms for General Nonconvex-Concave Minimax Problems
Title（参考訳）: 一般非凸凸ミニマックス問題に対するゼロ次交互ランダム勾配投影アルゴリズム
Authors: Zi Xu, Jingjing Shen, Ziqi Wang, Yuhong Dai
Abstract要約: 本稿では,非畳み込みミニマックス問題に対するゼロ次学習アルゴリズムを提案する。私たちの知識の第一に、私たちの知識の第一に、私たちの知識の第一に、私たちの知識の第一に、私たちの知識の第一に。
参考スコア（独自算出の注目度）: 7.209940933386251
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, and its iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$, and the number of function value estimation is bounded by $\mathcal{O}(d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$ per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving block-wise nonsmooth nonconvex-concave minimax optimization problems, and the iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$ and the number of function value estimation per iteration is bounded by $\mathcal{O}(K d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$. To the best of our knowledge, this is the first time that zeroth-order algorithms with iteration complexity gurantee are developed for solving both general smooth and block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on data poisoning attack problem validate the efficiency of the proposed algorithms.
Abstract（参考訳）: 本稿では,近年,機械学習,信号処理,その他多くの分野で注目されている非凸凹ミニマックス問題に対するゼロ次アルゴリズムについて検討する。本研究では,滑らかな非凸凸型ミニマックス問題に対するゼロ次交互ランダム勾配投影 (zo-agp) アルゴリズムを提案し,その反復複雑性から$\varepsilon$-stationary pointを得るには$\mathcal{o}(\varepsilon^{-4})$,関数値推定の回数は$\mathcal{o}(d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$である。さらに,ブロック方向非滑らかな非凸凸凸型ミニマックス最適化問題を解くために,ゼロ次ブロック交互なランダムな近位勾配アルゴリズム (zo-bapg) を提案し,$\varepsilon$-stationary point を得るための反復複雑性を$\mathcal{o}(\varepsilon^{-4})$ で制限し,各イテレーション当たりの関数値推定数は$\mathcal{o}(k d_{x}\varepsilon^{-4}+d_{y}\varepsilon^{-6})$で制限する。我々の知る限りでは、一般にスムーズかつブロックワイズ非滑らかな非凸凹極小問題を解くため、反復複雑性を保証したゼロ階アルゴリズムが開発されたのはこれが初めてである。データ中毒攻撃問題の数値結果は,提案アルゴリズムの有効性を検証する。

関連論文リスト

Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems [2.3721580767877257]
提案手法は,非強弱畳み込みミニマックス問題の解法である。本稿では,提案アルゴリズムが$mathcalを達成することを示す。スティロン 2階ノルムは上向きであることが証明されている。 tk 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ 400ドルだ $k
論文参考訳（メタデータ） (2024-11-24T09:46:36Z)
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)
Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文参考訳（メタデータ） (2024-01-26T11:22:13Z)
An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems [0.4910937238451484]
我々は、非凹小問題の解法として、正規化モーメント降下アルゴリズム(FORMDA)を高速化する。有界アルゴリズムの最大の複雑さは、客観性関数の停止下での非可逆ミニマックス問題の解法である。
論文参考訳（メタデータ） (2023-10-24T01:45:11Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。本稿では,2種類のミニマックスアルゴリズムを提案する。そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文参考訳（メタデータ） (2023-02-08T01:42:45Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth Nonconvex Minimax Problems with Coupled Linear Constraints [4.70696854954921]
非近位ミニマックス問題は近年、機械学習、信号処理など多くの分野に注目が集まっている。そこで本稿では,非平滑な非畳み込みミニマックス問題の解法としてDAPアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-12-09T05:32:30Z)
Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文参考訳（メタデータ） (2020-06-16T17:55:46Z)
A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文参考訳（メタデータ） (2020-06-03T04:00:52Z)
Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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