論文の概要: Accelerated zero-order SGD under high-order smoothness and overparameterized regime

• arxiv url: http://arxiv.org/abs/2411.13999v1
• Date: Thu, 21 Nov 2024 10:26:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-22 15:17:57.705341
• Title: Accelerated zero-order SGD under high-order smoothness and overparameterized regime
• Title（参考訳）: 高次滑らか度および過パラメータ状態下における加速零次SGD
• Authors: Georgii Bychkov, Darina Dvinskikh, Anastasia Antsiferova, Alexander Gasnikov, Aleksandr Lobanov,
• Abstract要約: 凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
• 参考スコア（独自算出の注目度）: 79.85163929026146
• License:
• Abstract: We present a novel gradient-free algorithm to solve a convex stochastic optimization problem, such as those encountered in medicine, physics, and machine learning (e.g., adversarial multi-armed bandit problem), where the objective function can only be computed through numerical simulation, either as the result of a real experiment or as feedback given by the function evaluations from an adversary. Thus we suppose that only a black-box access to the function values of the objective is available, possibly corrupted by adversarial noise: deterministic or stochastic. The noisy setup can arise naturally from modeling randomness within a simulation or by computer discretization, or when exact values of function are forbidden due to privacy issues, or when solving non-convex problems as convex ones with an inexact function oracle. By exploiting higher-order smoothness, fulfilled, e.g., in logistic regression, we improve the performance of zero-order methods developed under the assumption of classical smoothness (or having a Lipschitz gradient). The proposed algorithm enjoys optimal oracle complexity and is designed under an overparameterization setup, i.e., when the number of model parameters is much larger than the size of the training dataset. Overparametrized models fit to the training data perfectly while also having good generalization and outperforming underparameterized models on unseen data. We provide convergence guarantees for the proposed algorithm under both types of noise. Moreover, we estimate the maximum permissible adversarial noise level that maintains the desired accuracy in the Euclidean setup, and then we extend our results to a non-Euclidean setup. Our theoretical results are verified on the logistic regression problem.
• Abstract（参考訳）: 本稿では,医学,物理,機械学習などの凸確率最適化問題の解法として,実実験の結果,あるいは相手からの関数評価から得られるフィードバックとして,数値シミュレーションによって目的関数を計算できるような,新たな勾配のないアルゴリズムを提案する。 したがって、目的の関数値へのブラックボックスアクセスのみが利用可能であり、おそらくは逆のノイズ(決定論的または確率的)によって損なわれる可能性があると仮定する。 ノイズのある設定は、シミュレーション内でランダム性をモデル化したり、コンピュータの離散化によって自然に発生するり、プライバシの問題によって関数の正確な値が禁じられたり、不正確な関数のオラクルを持つ凸問題として非凸問題を解くときに発生する。 古典的滑らかさ(あるいはリプシッツ勾配)を仮定して開発されたゼロ階法の性能を向上させる。 提案アルゴリズムは最適なオラクル複雑性を享受し,トレーニングデータセットのサイズよりもモデルパラメータの数がはるかに大きい場合に,オーバーパラメータ化設定の下で設計する。 過度パラメータ化モデルは、トレーニングデータに完全に適合すると同時に、よく一般化され、目に見えないデータ上で過度パラメータ化モデルより優れている。 両種類の雑音下で提案アルゴリズムの収束保証を行う。 さらに、ユークリッド設定において所望の精度を維持する最大可逆雑音レベルを推定し、その結果を非ユークリッド設定に拡張する。 理論的結果はロジスティック回帰問題で検証される。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics [39.07258580928359]
  線形ベルマン完全設定に対する計算的および統計的に効率的な強化学習アルゴリズムについて検討する。 この設定では線形関数近似を用いて値関数をキャプチャし、線形マルコフ決定プロセス(MDP)や線形二次レギュレータ(LQR)のような既存のモデルを統一する。 我々の研究は、線形ベルマン完全設定のための計算効率の良いアルゴリズムを提供し、大きなアクション空間、ランダムな初期状態、ランダムな報酬を持つMDPに対して機能するが、決定論的となる基礎となる力学に依存している。
  論文  参考訳（メタデータ） (2024-06-17T17:52:38Z)
• Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise [19.496063739638924]
  構造スパイクモデルに対するベイズ推定の飽和問題を考える。 適応的なThouless-Anderson-Palmer方程式の理論にインスパイアされた効率的なアルゴリズムを用いて、統計的限界を予測する方法を示す。
  論文  参考訳（メタデータ） (2024-05-31T16:38:35Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。 カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。 我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-10-09T03:55:09Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Distributed Estimation and Inference for Semi-parametric Binary Response Models [8.309294338998539]
  本稿では,分散コンピューティング環境下での半パラメトリック二値選択モデルの最大スコア推定について検討する。 直感的な分割・対数推定器は計算コストが高く、機械数に対する非正規制約によって制限される。
  論文  参考訳（メタデータ） (2022-10-15T23:06:46Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Slowly Varying Regression under Sparsity [5.22980614912553]
  本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。 本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。 結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-02-22T04:51:44Z)
• Stochastic Compositional Gradient Descent under Compositional constraints [13.170519806372075]
  目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。 この問題は、公平な分類/回帰とキューシステムの設計に生じる。 提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
  論文  参考訳（メタデータ） (2020-12-17T05:38:37Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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