論文の概要: Analyzing and Improving Greedy 2-Coordinate Updates for
Equality-Constrained Optimization via Steepest Descent in the 1-Norm
- arxiv url: http://arxiv.org/abs/2307.01169v1
- Date: Mon, 3 Jul 2023 17:27:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 12:10:21.001121
- Title: Analyzing and Improving Greedy 2-Coordinate Updates for
Equality-Constrained Optimization via Steepest Descent in the 1-Norm
- Title（参考訳）: 等質制約最適化のための2座標2次更新の解析と改善
- Authors: Amrutha Varshini Ramesh, Aaron Mishkin, Mark Schmidt, Yihan Zhou,
Jonathan Wilder Lavington, Jennifer She
- Abstract要約: 我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。
次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
- 参考スコア（独自算出の注目度）: 12.579063422860072
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider minimizing a smooth function subject to a summation constraint
over its variables. By exploiting a connection between the greedy 2-coordinate
update for this problem and equality-constrained steepest descent in the
1-norm, we give a convergence rate for greedy selection under a proximal
Polyak-Lojasiewicz assumption that is faster than random selection and
independent of the problem dimension $n$. We then consider minimizing with both
a summation constraint and bound constraints, as arises in the support vector
machine dual problem. Existing greedy rules for this setting either guarantee
trivial progress only or require $O(n^2)$ time to compute. We show that bound-
and summation-constrained steepest descent in the L1-norm guarantees more
progress per iteration than previous rules and can be computed in only $O(n
\log n)$ time.
- Abstract（参考訳）: 我々は,変数の和制約を受ける滑らかな関数の最小化を検討する。
この問題に対するグリーディ 2-座標更新と1-ノルムにおける等式制約付き急降下との接続を利用することで、確率選択よりも高速で問題次元$n$の独立な近位ポリアック-ロジャシエヴィチ仮定の下でグリーディ選択の収束率を与える。
次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
この設定の既存のgreedyルールは、自明な進行のみを保証するか、計算に$O(n^2)$時間を必要とする。
L1-ノルムにおける有界和の制約付き急降下は、以前の規則よりも反復毎の進行を保証し、O(n \log n)$時間でしか計算できないことを示す。
関連論文リスト
- 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) - First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - An efficient algorithm for the $\ell_{p}$ norm based metric nearness
problem [4.700135257490953]
本稿では, 半平滑なニュートン型近位拡張ラグランジアン法(PALM)で解いた各サブプロブレムを用いた遅延制約生成法を提案する。
我々のアルゴリズムの喜ばしい側面は、最大108ドルの変数と1013ドルの制約を含むこれらの問題を解決することができることである。
論文 参考訳（メタデータ） (2022-11-02T16:29:05Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。
提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。
提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文 参考訳（メタデータ） (2021-03-29T18:53:57Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。