論文の概要: New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

• arxiv url: http://arxiv.org/abs/2605.18035v1
• Date: Mon, 18 May 2026 08:24:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:49.122062
• Title: New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions
• Title（参考訳）: ゼロ次ハードThresholdingにおける変化の新たな洞察:グラディエントエラーと拡張性矛盾の緩和
• Authors: Xinzhe Yuan, William de Vazelhes, Bin Gu, Huan Xiong,
• Abstract要約: ハードThresholdingは機械学習において重要なタイプのアルゴリズムであり、$ell_0$制約付き最適化問題を解くのに使用される。 SZOHTアルゴリズムは、これまでのZO勾配で$ell$ sparsityの制約に対処する唯一のアルゴリズムである。 本稿では, 一般化分散低減ZOハードスレッディングアルゴリズムと, 標準仮定に基づく一般化収束解析を提案する。
• 参考スコア（独自算出の注目度）: 32.99873080040697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hard-thresholding is an important type of algorithm in machine learning that is used to solve $\ell_0$ constrained optimization problems. However, the true gradient of the objective function can be difficult to access in certain scenarios, which normally can be approximated by zeroth-order (ZO) methods. The SZOHT algorithm is the only algorithm tackling $\ell_0$ sparsity constraints with ZO gradients so far. Unfortunately, SZOHT has a notable limitation on the number of random directions % in ZO gradients due to the inherent conflict between the deviation of ZO gradients and the expansivity of the hard-thresholding operator. This paper approaches this problem by considering the role of variance and provides a new insight into variance reduction: mitigating the unique conflicts between ZO gradients and hard-thresholding. Under this perspective, we propose a generalized variance reduced ZO hard-thresholding algorithm as well as the generalized convergence analysis under standard assumptions. The theoretical results demonstrate the new algorithm eliminates the restrictions on the number of random directions, leading to improved convergence rates and broader applicability compared with SZOHT. Finally, we illustrate the utility of our method on a ridge regression problem as well as black-box adversarial attacks.
• Abstract（参考訳）: ハードThresholdingは機械学習において重要なタイプのアルゴリズムであり、$\ell_0$制約付き最適化問題を解くのに使用される。 しかしながら、目的関数の真の勾配は、通常ゼロ階数 (ZO) 法で近似できる特定のシナリオでアクセスすることが困難である。 SZOHTアルゴリズムは、これまでのZO勾配で$\ell_0$スペーサ性制約に対処する唯一のアルゴリズムである。 残念なことに、SZOHT は ZO 勾配の偏差と強保持作用素の拡張性との間の固有の矛盾により、ZO 勾配のランダムな方向 % の個数に顕著な制限がある。 本稿では、分散の役割を考慮してこの問題にアプローチし、分散の低減に関する新たな洞察を与える:ZO勾配とハードスレッディングのユニークな矛盾を緩和する。 この観点から、標準仮定の下での一般化収束解析と同様に、一般化分散低減ZOハードスレッディングアルゴリズムを提案する。 理論的な結果は、新しいアルゴリズムがランダムな方向数を制限することを証明し、SZOHTと比較して収束率と適用性の向上につながった。 最後に,リッジ回帰問題およびブラックボックス攻撃に対する本手法の有用性について述べる。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Quantitative Error Bounds for Scaling Limits of Stochastic Iterative Algorithms [10.022615790746466]
  アルゴリズムのサンプルパスとOrnstein-Uhlenbeck近似の非漸近関数近似誤差を導出する。 我々は、L'evy-Prokhorov と有界ワッサーシュタイン距離という2つの一般的な測度で誤差境界を構築するために、主要な結果を使用する。
  論文  参考訳（メタデータ） (2025-01-21T15:29:11Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。 我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。 我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
  論文  参考訳（メタデータ） (2024-10-21T22:40:42Z)
• Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity [34.84170466506512]
  本稿では,新しいランダムサンプリングを用いた一般ZO勾配推定器を用いたゼロ階ハードスレッディング(SZOHT)アルゴリズムを提案する。 SZOHTの問合せ複雑性は, 異なる条件下での次元性に依存しないか, あるいは弱く依存していることが判明した。
  論文  参考訳（メタデータ） (2022-10-11T09:23:53Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。 我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
  論文  参考訳（メタデータ） (2021-12-24T17:21:04Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。 提案アルゴリズムの有効性と有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-04T16:49:29Z)
• Reparameterized Variational Divergence Minimization for Stable Imitation [57.06909373038396]
  確率的発散の選択における変動が、より高性能なILOアルゴリズムをもたらす可能性について検討する。 本稿では,提案する$f$-divergence最小化フレームワークの課題を軽減するために,逆模倣学習のための再パラメータ化手法を提案する。 経験的に、我々の設計選択は、ベースラインアプローチより優れ、低次元連続制御タスクにおける専門家のパフォーマンスとより密に適合するIOOアルゴリズムを許容することを示した。
  論文  参考訳（メタデータ） (2020-06-18T19:04:09Z)

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

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