論文の概要: A stochastic smoothing framework for nonconvex-nonconcave min-sum-max problems with applications to Wasserstein distributionally robust optimization

• arxiv url: http://arxiv.org/abs/2502.17602v1
• Date: Mon, 24 Feb 2025 19:36:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-26 15:21:06.758318
• Title: A stochastic smoothing framework for nonconvex-nonconcave min-sum-max problems with applications to Wasserstein distributionally robust optimization
• Title（参考訳）: 非凸非凸 min-sum-max 問題に対する確率的滑らか化フレームワークとワッサーシュタイン分布論的ロバスト最適化への応用
• Authors: Wei Liu, Muhammad Khan, Gabriel Mancino-Ball, Yangyang Xu,
• Abstract要約: 本研究は,mboxlog-sumexp関数に基づく新しいトレーニング平滑化フレームワークを提案する。 我々は,計算困難に対処し,クラーク/方向性定常点への収束を保証する反復的平滑化アルゴリズムを開発した。 我々の手法は、ニュース問題、ディープラーニング回帰、対向的に堅牢なディープラーニングの解決において、最先端の手法よりも優れているか、競争的である。
• 参考スコア（独自算出の注目度）: 15.21599021645008
• License:
• Abstract: Applications such as adversarially robust training and Wasserstein Distributionally Robust Optimization (WDRO) can be naturally formulated as min-sum-max optimization problems. While this formulation can be rewritten as an equivalent min-max problem, the summation of max terms introduces computational challenges, including increased complexity and memory demands, which must be addressed. These challenges are particularly evident in WDRO, where existing tractable algorithms often rely on restrictive assumptions on the objective function, limiting their applicability to state-of-the-art machine learning problems such as the training of deep neural networks. This study introduces a novel stochastic smoothing framework based on the \mbox{log-sum-exp} function, efficiently approximating the max operator in min-sum-max problems. By leveraging the Clarke regularity of the max operator, we develop an iterative smoothing algorithm that addresses these computational difficulties and guarantees almost surely convergence to a Clarke/directional stationary point. We further prove that the proposed algorithm finds an $\epsilon$-scaled Clarke stationary point of the original problem, with a worst-case iteration complexity of $\widetilde{O}(\epsilon^{-3})$. Our numerical experiments demonstrate that our approach outperforms or is competitive with state-of-the-art methods in solving the newsvendor problem, deep learning regression, and adversarially robust deep learning. The results highlight that our method yields more accurate and robust solutions in these challenging problem settings.
• Abstract（参考訳）: 逆ロバストなトレーニングやWasserstein Distributionally Robust Optimization (WDRO)のような応用は、自然にmin-sum-max最適化問題として定式化することができる。 この定式化は、等価な min-max 問題として書き換えることができるが、最大項の和は、計算上の問題を引き起こす。 これらの課題は、WDROにおいて特に顕著であり、既存のトラクタブルアルゴリズムは、しばしば目的関数に対する制限的な仮定に依存し、ディープニューラルネットワークのトレーニングのような最先端の機械学習問題に適用性を制限する。 本研究では,mbox{log-sum-exp}関数に基づく新しい確率的平滑化フレームワークを導入し,min-sum-max問題における最大演算子を効率的に近似する。 最大作用素のクラーク正則性を活用することにより、これらの計算困難に対処し、クラーク/方向定常点にほぼ確実に収束する反復的平滑化アルゴリズムを開発する。 さらに、提案アルゴリズムは、元の問題において、$\epsilon$-scaled Clarke固定点が$\widetilde{O}(\epsilon^{-3})$であることを示す。 我々の数値実験は, ニューズベンダー問題, ディープラーニング回帰, 対角的に頑健な深層学習において, 最先端の手法に勝るもの, あるいは競合するものであることを実証した。 その結果,これらの問題設定において,より正確でロバストな解が得られることがわかった。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization [36.743632418094]
  マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。 我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
  論文  参考訳（メタデータ） (2022-06-01T06:42:36Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)

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

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