Abstract
In this paper, we consider convex stochastic optimization problems arising in machine learning applications (e.g., risk minimization) and mathematical statistics (e.g., maximum likelihood estimation). There are two main approaches to solve such kinds of problems, namely the Stochastic Approximation approach (online approach) and the Sample Average Approximation approach, also known as the Monte Carlo approach, (offline approach). In the offline approach, the problem is replaced by its empirical counterpart (the empirical risk minimization problem). The natural question is how to define the problem sample size, i.e., how many realizations should be sampled so that the quite accurate solution of the empirical problem be the solution of the original problem with the desired precision. This issue is one of the main issues in modern machine learning and optimization. In the last decade, a lot of significant advances were made in these areas to solve convex stochastic optimization problems on the Euclidean balls (or the whole space). In this work, we are based on these advances and study the case of arbitrary balls in the $\ell_p$-norms. We also explore the question of how the parameter $p$ affects the estimates of the required number of terms as a function of empirical risk.
Introduction: The Online vs. Offline Dilemma
In machine learning and statistics, the fundamental goal is often to minimize an "expected risk"—the average loss over an unknown distribution. Since the full distribution is rarely available, researchers rely on two primary strategies:
- Stochastic Approximation (Online): Models are updated incrementally as each new data point arrives, exemplified by methods like Stochastic Gradient Descent (SGD).
- Sample Average Approximation / ERM (Offline): A fixed batch of data is collected to create an empirical average of the loss, which is then solved as a standalone optimization problem.
A critical question in modern optimization is determining the sample complexity ($N$): how many samples are required to ensure that the solution to the offline empirical problem serves as a high-quality proxy for the true underlying problem? While much of the existing literature focuses on standard Euclidean ($L_2$) spaces, this research extends these theoretical bounds to arbitrary $L_p$-norm balls and explores how functional conditions like strong convexity or saddle-point structures influence these requirements.
Methodology: Generalizing Geometry and Conditions
The study provides a rigorous theoretical analysis of sample complexity by moving beyond standard assumptions. The methodology focuses on four key areas:
- Generalizing Norms: The analysis extends beyond Euclidean distance to study optimization on balls defined by $L_p$ norms where $p \ge 1$.
- Condition Relaxation: The authors demonstrate that the restrictive assumption of "strong convexity" can be replaced by the broader "quadratic growth" condition without sacrificing efficiency.
- Regularization Strategies: For general convex problems where offline methods typically underperform compared to online methods, the research shows how adding a strongly convex regularization term can bridge the gap in sample complexity.
- Saddle Point Analysis: The study extends to min-max problems (crucial for GANs and robust optimization) using a "$\gamma$-growth" condition to characterize objective behavior.
Key Insights
The Impact of Geometry
The choice of $p$ in the $L_p$-norm significantly shifts sample complexity. In general convex cases, online methods typically dominate offline ones by a factor related to the dimension $d$, except in the specific case of the $L_\infty$ norm. This highlights that the geometry of the parameter space is a primary driver of algorithm efficiency.
Quadratic Growth as an Equalizer
The perceived advantage of online methods largely disappears when the objective function satisfies a quadratic growth condition. Under these circumstances, both online and offline approaches require roughly the same number of samples to reach a target accuracy, simplifying the choice for practitioners.
The Efficiency of Sharp Minima
For saddle point problems, the research identifies a significant result: if the problem possesses a "sharp" minimum (a case of $\gamma$-growth where $\gamma=1$), the required sample size becomes almost independent of the desired precision ($\epsilon$). This suggests that for "sharp" problems, massive datasets may not be necessary to achieve high-accuracy results.
Results and Complexity Bounds
The paper establishes explicit formulas for sample size ($N$) across various scenarios:
- Strongly Convex Cases: Sample size scales with $O(1/\epsilon)$.
- General Convex Cases: Sample size scales with $O(1/\epsilon^2)$.
- The Euclidean Gap: For $p=2$, the offline approach typically requires $d$ times more samples than the online approach in general convex settings, but this gap vanishes under strong convexity.
Conclusion and Future Directions
This work bridges the gap between online and offline methods by providing a unified framework for $L_p$-norm balls. While the bounds are mathematically optimal, a gap remains between these theoretical results and practical high-dimensional deep learning architectures. Future research is needed to generalize conditions like the Polyak-Łojasiewicz (PL) condition for all $L_p$ norms and to explore non-convex or more complex saddle-point landscapes.
Summary updated