Source-linked AI summary
Sparse Data Augmentation for Optimization with Provable Guarantees
Behrooz Tahmasebi, Melanie Weber
TL;DR
Fully augmented objectives can be computationally prohibitive because their gradients average over all transformations in a large group. The paper studies one-shot augmentation, reusing a fixed random subset throughout gradient descent, and shows that it achieves stationarity for the fully augmented objective with fewer transformation-oracle calls than streaming stochastic methods.
Problem
Evaluating fully augmented gradients requires averaging over all |G| transformations, which can be computationally prohibitive when the group is large.
Method
One-shot augmentation samples a single random subset before optimization, fixes it throughout the trajectory, and runs gradient descent on the resulting partially augmented objective.
Results
O(log |G|/ϵ^2) group-oracle calls suffice for an ϵ-stationary point of the fully augmented objective, compared with O(1/ϵ^4) calls for streaming stochastic methods.
Takeaways & Limitations
Previously sampled transformations can be reused throughout training while retaining a stationarity guarantee for the fully augmented objective under the stated structural and smoothness assumptions.
Takeaways & Limitations
The guarantee relies on structural and smoothness assumptions, including a uniform bound on the average RKHS norms of the gradient functions.
Abstract
from arXiv · showhide
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.
1 Introduction
Data augmentation incorporates transformation invariance by averaging losses, but full-group optimization can be costly. The paper introduces one-shot augmentation, reusing a fixed random subset while proving stationarity for the fully augmented objective.
- Motivation: Full augmentation averages each sample's loss over transformed versions, but evaluating gradients over all |G| transformations can be computationally prohibitive.This motivates sparse alternatives when the transformation group is large.
- Streaming augmentation: Streaming augmentation samples fresh transformation batches each iteration, requiring bT transformations over T iterations.Its group-oracle complexity is O(1/ϵ4) for reaching expected stationarity at most ϵ.
- One-shot augmentation: One-shot augmentation samples a single subset S before optimization, fixes it throughout the trajectory, and runs gradient descent on the resulting partially augmented objective.Conditioned on S, the objective and subsequent optimization are deterministic, requiring only |S| oracle calls.
- Technical challenge: Because iterates depend on the reused subset, pointwise concentration at a fixed parameter is insufficient to compare partially and fully augmented gradients.The analysis therefore seeks a uniform approximation holding across the parameter domain and optimization trajectory.
- Main result: A fixed subset of size O(log |G|/ϵ2) suffices, with high probability, for gradient descent on the partial objective to reach an ϵ-stationary point of the fully augmented objective.This uses only O(log |G|/ϵ2) group-sampling-oracle calls, compared with O(1/ϵ4) for streaming methods.
- Analysis: The proof combines spectral properties of group-induced operators with finite-group representation theory to control dependence between the sampled subset and optimization trajectory.The authors suggest these uniform-approximation techniques may apply to other structured random averages.
2 Problem Statement
The paper formulates fully augmented empirical risk minimization over a finite transformation group and compares streaming group-SGD with one-shot sparse gradient descent. Its focus is the number of costly group-sampling-oracle calls needed to obtain stationarity for the fully augmented objective.
- The target problem is empirical risk minimization with losses averaged over all transformations in a finite group.
- Streaming group-SGD samples a fresh batch of transformations at every iteration, producing randomly changing partially augmented objectives.
- One-shot sparse GD samples one multiset S before optimization and reuses it throughout the optimization trajectory.
- The analysis assumes transformed losses are uniformly L-smooth in the optimization parameter.
- The group-sampling oracle counts fresh uniformly sampled transformations, excluding repeated gradient evaluations over already sampled transformations.
3 Main Results
One-shot sparse GD reuses a fixed random transformation sample while establishing uniform sparse-to-full gradient approximation. Under stated regularity conditions, this yields a high-probability stationarity guarantee with oracle calls independent of the optimization-iteration count.
- One-shot sparse GD samples S before optimization and performs every update using the same sampled transformations.
- The total number of group-oracle calls is exactly m, independently of T, because sampled transformations are reused at every iteration.
- The proof must control dependence between S and the iterates, since the optimization trajectory is generated from the same sparse objective.
- Representation-theoretic spectral analysis approximates full group averaging uniformly, including for unitary representations on potentially infinite-dimensional spaces.
- Under Assumptions 3.1 and 3.4 with ηt = 1/L, Theorem 3.5 gives a probability-at-least-1−δ convergence guarantee for one-shot sparse GD.
4 Proof Sketch
The proof establishes a uniform gradient approximation for the fixed sparse sample and then combines it with standard smooth nonconvex gradient-descent bounds. Uniformity is necessary because every iterate depends on the sampled transformations.
- The operator DS = ΠS − ΠG isolates the difference between sampled and full group averaging and acts on nontrivial representation components.
- Finite-group representation decompositions reduce concentration to finitely many distinct irreducible matrix blocks, even when the function space is infinite-dimensional.
- The operator-norm bound holds simultaneously for every gradient function, rather than only at a parameter selected independently of S.
- Smoothness and the standard descent estimate bound the sparse-gradient optimization error for gradient descent with ηt = 1/L.
- The final triangle-inequality argument separates finite-iteration error from sparse-approximation error and chooses T and m so each is at most ϵ/2.
5 Experiments
The experiment evaluates one-shot sparse augmentation against unaugmented, fully augmented, and streaming methods in nonconvex permutation-invariant sum regression. Larger fixed transformation subsets improve risk and stationarity, with 64 permutations closely matching the augmented baselines using fewer fresh samples.
- 5.1 Permutation-invariant sum regression: The experiment uses a nonconvex Gaussian-kernel predictor with 160 unsorted kernel centers and jointly optimized factorized coefficients.The parameter vectors are projected onto a bounded domain after each update.
- 5.2 Methods and evaluation protocol: The comparison includes no augmentation, full-group GD over 720 permutations, streaming group-SGD, and one-shot sparse GD with fixed subset sizes.All methods use shared initialization, full data batches, a common step size, and 500 iterations across 10 seeds.
- 5.2 Methods and evaluation protocol: The evaluation measures fully augmented training risk, permutation-averaged test risk, the fully augmented gradient norm, and test risk versus fresh permutation queries.Curves average 10 seeds, while risk uncertainty uses one standard deviation.
- 5.3 Results: Augmented methods rapidly reduce training and test risk relative to the unaugmented predictor, while increasing the fixed subset from 4 to 16 substantially improves one-shot trajectories.The improvement from 16 to 64 permutations is smaller.
- 5.3 Results: With 64 fixed permutations, one-shot sparse GD closely tracks full-group GD and streaming group-SGD in test risk while using substantially fewer fresh group samples.Its fully augmented gradient norm also moves progressively closer to full-group GD as the fixed subset grows, whereas streaming group-SGD fluctuates.
6 Conclusion
The paper concludes that a sparse transformation set sampled once can be reused throughout gradient descent while retaining a stationarity guarantee for the fully augmented objective. Under the stated assumptions, this improves transformation-query complexity over standard group-SGD.
- 6 Conclusion: One-shot sparse gradient descent reuses transformations sampled at initialization and still targets an ε-stationary point of the fully augmented objective.The guarantee holds under the paper’s structural and smoothness assumptions.
- 6 Conclusion: O(log |G|/ε^2) group-oracle calls obtain an ε-stationary point with probability at least 1 − δ, improving on O(1/ε^4) for standard group-SGD.The analysis combines spectral approximation of group-averaging operators with uniform control of the augmented gradient field.
LLM usage disclosure
The disclosure states that language-model tools were used for copyediting, while the research direction, core ideas, theoretical results, and experimental design were original author contributions. The related-work passages situate the paper among augmentation, symmetry, equivariance, and nonconvex optimization research.
- LLM usage disclosure: Language-model tools were used primarily for grammar, wording, clarity, and LaTeX presentation improvements.The authors state that they reviewed and verified the technical content.
- Related work: The related work covers data augmentation and invariant learning, including optimization, learnability, kernels, generalization, and transformation-induced covers.It also mentions methods that learn or adapt augmentation distributions.
- Related work: Alternative symmetry mechanisms include frame averaging, minimal frame averaging, canonicalization, and extensions to Lie group actions and neural operators.These approaches enforce or represent symmetry through mechanisms other than the paper’s augmentation procedure.
- Related work: Approximate and data-adaptive equivariance motivates residual pathways, non-stationary filters, approximately equivariant models, and learned layerwise constraints or parameter sharing.The cited methods address settings where hard architectural constraints may be too restrictive.
- Related work: Related symmetry-discovery work tests invariance or learns continuous generators, distribution-preserving transformations, representations, and symmetric embeddings.The passage presents these as neighboring approaches to symmetry testing and discovery.
- Related work: Nonconvex optimization literature includes stochastic methods, variance reduction, random reshuffling, and oracle lower bounds, whereas this paper counts newly sampled transformations.Previously sampled transformations can be reused throughout optimization.
B Proofs and Technical Background
The appendix develops the proof framework using finite-group actions, unitary representations, isotypic decomposition, and spectral approximation of group averages. These ingredients support uniform control of the augmented gradient fields and the one-shot convergence proof.
- B Proofs and Technical Background: The proof proceeds from finite-group and representation-theoretic background to spectral approximation of a random sparse group average and convergence of one-shot descent.The spectral estimate is transferred to augmented gradient fields through the RKHS structure.
- Finite groups and actions: A finite group has closure, associativity, an identity, and inverses, while a left action maps group elements to bijections of the acted-on set.The inverse action supplies the inverse bijection.
- Unitary representations: A group action on a Hilbert space induces operators U_g that form a representation of G.Under the stated assumption, the representation is unitary and preserves inner products.
- Representation decomposition: Every unitary representation decomposes into isotypic components indexed by irreducible representations, with multiplicity spaces carrying repeated-copy structure.Operator-norm control depends on distinct irreducible representations rather than their multiplicities.
- Invariant subspace: The trivial representation is one-dimensional, and its isotypic component is exactly the invariant subspace H^G.This identifies invariant functions as the fixed points of every group operator.
B.3 Full and sampled averaging operators
The full group-averaging operator is an orthogonal projection onto the invariant subspace, while the sampled operator provides an unbiased empirical approximation. Representation-theoretic block structure reduces analysis to nontrivial irreducible components.
- ΠG is the orthogonal projection from H onto the invariant subspace HG.
- The sampled averaging operator formed from independent uniform transformations is an unbiased estimator of ΠG.
- Operator-norm analysis reduces to controlling empirical averages for each nontrivial irreducible representation.Unitary conjugation and direct-sum structure preserve the relevant block-norm characterization.
B.4 Spectral concentration for sparse group averaging
The paper establishes high-probability spectral approximation for sparse group averaging by applying matrix concentration representation by representation. The resulting event is uniform across unitary representations and supports uniform gradient approximation along data-dependent optimization trajectories.
- The spectral argument applies matrix Bernstein concentration to each nontrivial irreducible representation and combines the bounds with a union bound.
- Theorem B.3 gives a high-probability random sparse approximation of group averaging for independent uniform samples.The event depends only on the sampled transformations and applies to averaging operators on possibly infinite-dimensional Hilbert spaces.
- The uniform operator event transfers to every unitary representation regardless of Hilbert-space multiplicities.
- Representation-theoretic decomposition yields logarithmic dependence on |G| rather than log dim(H).Only distinct irreducible representations are controlled, using the dimension relation Σπ∈Ĝ dπ ≤ |G|.
- Theorem B.8 converts spectral approximation into simultaneous sparse-to-full gradient approximation for all parameters.Uniform RKHS bounds preserve this approximation along trajectories whose iterates depend on the sampled transformations.
B.8 Proof of the main theorem
The proof combines uniform gradient approximation with nonconvex descent to establish one-shot sparse GD guarantees. Because transformations are sampled once and cached, its oracle complexity is determined by the initial sample, unlike full-group GD and streaming group-SGD.
- Uniform gradient approximation and the descent estimate are combined to analyze one-shot sparse GD.
- Corollary B.13 provides a high-probability stationarity and group-oracle complexity guarantee under the theorem’s assumptions.
- The sampled transformations are cached after initialization and reused at every optimization iteration.Consequently, no further transformation acquisition is needed during optimization.
- Full-group GD requires access to all |G| group elements while attaining ε-stationarity after T ≥ 2LΔG/ε^2 iterations.
- Streaming group-SGD has group-oracle complexity O(1/ε^4) because each iteration draws fresh transformations, without improvement from batch size.