論文の概要: On the Oracle Complexity of Interpolation-Based Gradient Descent

• arxiv url: http://arxiv.org/abs/2606.19878v1
• Date: Thu, 18 Jun 2026 07:35:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:39.702225
• Title: On the Oracle Complexity of Interpolation-Based Gradient Descent
• Title（参考訳）: 補間に基づくグラディエントDescent の Oracle 複雑性について
• Authors: Dongmin Lee, William Lu, Anuran Makur,
• Abstract要約: ピースワイズ型勾配勾配勾配法(PPIGD)を提案する。 PPIGDは、データ領域の1次オラクル依存点を問合せすることで、全勾配を近似する。 損失関数が十分に凸である場合、キーレシエーションにおいていくつかのGD変量より優れる。
• 参考スコア（独自算出の注目度）: 11.560648074990366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of $d$-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.
• Abstract（参考訳）: 経験的リスク最小化(ERM)のための一階最適化器の最近の研究は、最適化パラメータではなくトレーニングデータにおけるERM損失関数の滑らかさを利用して勾配降下法(GD)のオラクル複雑性を改善することを示唆している。 本稿では,データ領域の等距離点の1次オラクルを問合せして,データ領域の適切な大きさのパッチに対して得られる勾配サンプルの多項式補間を構成することにより,各イテレーションにおける全勾配を近似する不正確な勾配法であるPPI-GDを提案する。 我々は,データ空間の次元がトレーニングサンプル数の多対数関数で束縛されている場合,PPI-GDの強凸・非凸損失関数に対するオラクル複雑性を解析し,損失関数が十分に滑らかな場合,鍵状態における複数のGD変量より優れていることを示す。 さらに, この解析手法は, バイコビックスプライン補間材の誤差解析から, 補間解析に無関心な$d$-variateテンソル積多項式補間材の設定まで, 様々な手法を拡張している。

関連論文リスト

• An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions [2.738648582869357]
  空間空間の分枝および分枝における部分解析的下界表現が平均値に有効であることを示す。 その結果,PALM-Meanはデータ点数の増加に伴い,汎用的グローバルトレーニングの改善を図っている。
  論文  参考訳（メタデータ） (2026-04-21T01:13:54Z)
• sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation [8.802387139798808]
  本稿では,高次主成分分析(SHOPCA)のための新しいフレームワークを提案する。 本稿では,SparseGeoHOPが高次元画像設定とImageNet上でサポートされていることを示す。
  論文  参考訳（メタデータ） (2025-06-10T10:30:48Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。 非滑らかな正規化はしばしば機械学習タスクに組み込まれる。 本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-17T08:32:25Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Inexact subgradient methods for semialgebraic functions [18.293072574300798]
  機械学習における近似勾配の広範囲な適用を動機として, 永続的な誤差を受ける部分エクサクティヴな加算法について検討する。 我々の分析は、消滅と定常的なステップサイズ体制の両方に対処する。
  論文  参考訳（メタデータ） (2024-04-30T12:47:42Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [7.8086907734474345]
  非滑らか成分による複合最適化問題のクラス。 提案したiLPAは、外れ値と非一様サンプリングを持つロバストな分解モデル行列に適用される。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Piecewise linear regression and classification [0.20305676256390928]
  本稿では,線形予測器を用いた多変量回帰と分類問題の解法を提案する。 本論文で記述されたアルゴリズムのpython実装は、http://cse.lab.imtlucca.it/bemporad/parcで利用可能である。
  論文  参考訳（メタデータ） (2021-03-10T17:07:57Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。 我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。 RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
  論文  参考訳（メタデータ） (2020-02-21T00:43:06Z)

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

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