論文の概要: Sparse Data Augmentation for Optimization with Provable Guarantees
- arxiv url: http://arxiv.org/abs/2609.08133v1
- Date: Tue, 08 Sep 2026 02:11:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.55144
- Title: Sparse Data Augmentation for Optimization with Provable Guarantees
- Title（参考訳）: Provable Guaranteesを用いたスパースデータ拡張による最適化
- Abstract要約: 固定スパース増分による勾配勾配勾配は、完全に拡張された目的とグループSGDの両方に適用されたGDよりも少ない変換クエリを必要とすることを示す。
我々の証明手法は、独立な興味を持つかもしれないが、ランダム群平均による全群平均勾配場の一様近似を確立する。
- 参考スコア（独自算出の注目度）: 15.56971726974056
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In nonconvex optimization problems arising in geometric machine learning, data augmentation is commonly used to promote invariance by averaging empirical losses over transformations of the data. Computing the fully augmented objective, however, requires access to every element of the transformation group $G$, which may be prohibitively expensive when $G$ is large or accessible only through sampling. We study whether full augmentation can instead be approximated using a small, fixed sample of transformations acquired before optimization and reused thereafter. Under suitable regularity conditions, we show that, with probability at least $1-δ$, gradient descent (GD) on the resulting sparsely augmented objective returns an $\varepsilon$-stationary point of the fully augmented objective using $\mathcal{O}\bigl((\log |G|+\log(1/δ))/\varepsilon^2\bigr)$ group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses $\mathcal{O}(1/\varepsilon^4)$ transformation queries. Therefore, gradient descent with fixed sparse augmentation requires fewer transformation queries than both GD applied to the fully augmented objective and group-SGD. Our proof techniques, which may be of independent interest, establish a uniform approximation of the full group-averaged gradient field by a random group average using spectral properties of group-induced operators and tools from representation theory.
- Abstract（参考訳）: 幾何機械学習における非凸最適化問題では、データの変換に対する経験的損失を平均化することにより、データの増大が不変性を促進するのが一般的である。
しかし、完全に拡張された目的を計算するには、変換グループのすべての要素に$G$にアクセスする必要がある。
そこで本研究では,最適化前に得られた変換の小さな,固定されたサンプルを用いて,完全な拡張を近似できるかどうかを検証した。
適切な正則性条件下では、少なくとも1-δ$の確率で、得られた疎拡張対象に対する勾配降下(GD)は、$\mathcal{O}\bigl((\log |G|+\log(1/δ))/\varepsilon^2\bigr)$群変換オーラルクエリを用いて、完全拡張対象の$\varepsilon$-stationaryポイントを返す。
比較すると、各反復で新しい変換をサンプリングする標準群確率勾配降下(group-SGD)は$\mathcal{O}(1/\varepsilon^4)$変換クエリを使用する。
したがって、固定スパース増分による勾配降下は、完全に拡張された目的とグループSGDの両方に適用されるGDよりも変換クエリが少ない。
我々の証明手法は, 群誘導作用素と表現論からのツールのスペクトル特性を用いて, グループ平均勾配場の一様近似をランダム群平均で確立する。
関連論文リスト
- Data Augmentation: A Fourier Analysis Perspective [52.00584777952869]
部分的なデータ拡張は、一般化やサンプルの複雑さの観点から、完全な拡張と同じ統計的利点が得られることを示す。
この結果から, 部分拡張が, ほぼ対称性を保っているにもかかわらず, 完全拡張の統計的利点を維持できる理由を理論的に説明できる。
論文 参考訳（メタデータ） (2026-06-23T10:54:14Z) - Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
低ランク近似と残差に基づくサンプリングに基づく新しいデータ選択フレームワークを提案する。
平均損失がデータセット全体の平均損失を近似した$tildeOleft(k + frac1varepsilon2right)$データポイントの重み付きサブセットを選択することができることを示す。
論文 参考訳（メタデータ） (2026-06-14T22:29:59Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
単純降下レンズ(GD)によるToeplitz共分散推定の再検討
K = P$ のとき、GD は準最適解に収束する。
本稿では,振幅と周波数の学習率の異なる高速なGD変種を提案する。
論文 参考訳（メタデータ） (2025-11-03T14:07:53Z) - MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳（メタデータ） (2023-09-03T19:21:59Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳（メタデータ） (2022-07-16T03:09:30Z) - Never Go Full Batch (in Stochastic Convex Optimization) [42.46711831860667]
凸最適化のための$textfull-batch$最適化アルゴリズムの一般化性能について検討する。
我々は、勾配降下のようなアルゴリズムが人口リスクを$O(1/epsilon2)$の後に$epsilon$に一般化し、最適化する一方で、フルバッチ法は少なくとも$Omega(1/epsilon4)$の反復を必要とするか、あるいは次元依存的なサンプル複雑性を示すことを示した。
論文 参考訳（メタデータ） (2021-06-29T16:07:50Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。