論文の概要: Optimal Rates for Robust Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2412.11003v3
• Date: Wed, 23 Apr 2025 23:32:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-25 21:09:46.427126
• Title: Optimal Rates for Robust Stochastic Convex Optimization
• Title（参考訳）: ロバスト確率凸最適化のための最適速度
• Authors: Changyu Gao, Andrew Lowy, Xingyu Zhou, Stephen J. Wright,
• Abstract要約: 我々は、$epsilon$-contaminationモデルの下で、最小最適過剰リスク(対数因子まで)を達成する新しいアルゴリズムを開発した。 我々のアルゴリズムは、個々のサンプル関数のリプシッツ連続性や滑らかさを含む厳密な仮定を必要としない。 我々は、ロバストSCOのための厳密な情報理論の下限でアルゴリズム開発を補完する。
• 参考スコア（独自算出の注目度）: 12.620782629498812
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Machine learning algorithms in high-dimensional settings are highly susceptible to the influence of even a small fraction of structured outliers, making robust optimization techniques essential. In particular, within the $\epsilon$-contamination model, where an adversary can inspect and replace up to an $\epsilon$-fraction of the samples, a fundamental open problem is determining the optimal rates for robust stochastic convex optimization (SCO) under such contamination. We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the $\epsilon$-contamination model. Our approach improves over existing algorithms, which are not only suboptimal but also require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions. By contrast, our optimal algorithms do not require these stringent assumptions, assuming only population-level smoothness of the loss. Moreover, our algorithms can be adapted to handle the case in which the covariance parameter is unknown, and can be extended to nonsmooth population risks via convolutional smoothing. We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.
• Abstract（参考訳）: 高次元環境での機械学習アルゴリズムは、ごく少数の構造化されたアウトリーチの影響を受けやすいため、堅牢な最適化技術が不可欠である。 特に$\epsilon$-contaminationモデルでは、敵がサンプルの$\epsilon$-fractionを検査して置き換えることができる。 我々は、$\epsilon$-contaminationモデルの下で、最小最適過剰リスク(対数因子まで)を達成する新しいアルゴリズムを開発した。 提案手法は, 部分最適であるだけでなく, リプシッツ連続性や個々の標本関数の滑らかさなど, 厳密な仮定を必要とする既存のアルゴリズムよりも改善されている。 対照的に、我々の最適アルゴリズムは、損失の集団レベルの滑らかさのみを仮定して、これらの厳密な仮定を必要としない。 さらに,共分散パラメータが未知の場合にはアルゴリズムを適用でき,畳み込み平滑化により非平滑な集団リスクにまで拡張することができる。 我々は、ロバストSCOのための厳密な情報理論の下限でアルゴリズム開発を補完する。

関連論文リスト

• Towards Weaker Variance Assumptions for Stochastic Optimization [19.339358874690568]
  次数次法の2乗ノルムを最適化変数の2乗ノルムの2乗ノルムと同程度の速さで成長させることができるような勾配アルゴリズムを解析するための古典的な仮定を再検討する。 関数的制約や正規化された凸凹 min-max 問題を用いて凸問題を解析する。 実現可能な集合の有界性を必要としない最適度測度に対するレートを得る。
  論文  参考訳（メタデータ） (2025-04-14T07:26:34Z)
• The Distributionally Robust Optimization Model of Sparse Principal Component Analysis [7.695578200868269]
  乱数パラメータの確率分布が不確実な条件下でのスパース主成分分析(PCA)について考察する。 この問題は、不確実性を捉えるための構成的アプローチに基づいて、分散ロバストな最適化(DRO)モデルとして定式化されている。 内部問題は閉形式解を認め、元の DRO モデルをスティーフェル多様体上の同値な最小化問題に再構成する。
  論文  参考訳（メタデータ） (2025-03-04T11:00:08Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions [15.396561118589577]
  パフォーマンスリスク最小化は、決定依存分布の下での最適化の定式化である。 我々のアルゴリズムは、既存のリプシッツ定数分布パラメータに基づく手法を大幅に改善する。 提案手法は,既存手法と他のブラックボックス楽観的最適化手法に比較して,アルゴリズムの数値的優位性を示す実験結果を提供する。
  論文  参考訳（メタデータ） (2024-02-23T08:36:28Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Langevin dynamics based algorithm e-TH$\varepsilon$O POULA for stochastic optimization problems with discontinuous stochastic gradient [6.563379950720334]
  我々は,不連続勾配による最適化問題を解くために,e-TH$varepsilon$O POULAと呼ばれる新しいランゲヴィン力学に基づくアルゴリズムを導入する。 金融と保険の3つの重要な応用として、多周期ポートフォリオ最適化、多周期ポートフォリオ最適化におけるトランスファーラーニング、保険請求予測がある。
  論文  参考訳（メタデータ） (2022-10-24T13:10:06Z)
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization [44.52870407321633]
  これらの設定の聖杯は、プライバシーと過剰な人口減少の間の最適なトレードオフを保証することです。 微分プライベート・ミニマックス最適化(DP-SMO)問題を解くための一般的なフレームワークを提供する。 我々のフレームワークは、非滑らかな微分プライベート凸最適化(DP-SCO)のための最近提案されたフェイズド・ERM法[20]から着想を得たものである。
  論文  参考訳（メタデータ） (2022-06-01T10:03:20Z)
• Tractable and Near-Optimal Adversarial Algorithms for Robust Estimation in Contaminated Gaussian Models [1.609950046042424]
  ハマーの汚染されたガウスモデルの下での位置と分散行列の同時推定の問題を考える。 まず,非パラメトリック判別器を用いた生成逆数法に対応する最小$f$-divergence推定法について検討した。 ネスト最適化により実装可能な,単純なスプライン判別器を用いたトラクタブル逆数アルゴリズムを開発した。 提案手法は,$f$-divergenceと使用したペナルティに応じて,最小値の最適値またはほぼ最適値を達成する。
  論文  参考訳（メタデータ） (2021-12-24T02:46:51Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• 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)

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

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