Abstract: Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on "light-tail" noise assumptions or exhibit worse sample complexity. In this work, we show that a wide class of stochastic optimization algorithms for strongly convex problems can be augmented with high confidence bounds at an overhead cost that is only logarithmic in the confidence level and polylogarithmic in the condition number. The procedure we propose, called proxBoost, is elementary and builds on two well-known ingredients: robust distance estimation and the proximal point method. We discuss consequences for both streaming (online) algorithms and offline algorithms based on empirical risk minimization.
Introduction: The Gap in Stochastic Optimization
In the field of stochastic optimization—the engine behind modern machine learning—performance is typically measured "in expectation." For example, when training a model using Stochastic Gradient Descent (SGD), theoretical guarantees usually ensure that the average error over many hypothetical runs will be small. However, for high-stakes applications like medical diagnostics or autonomous vehicle control, average performance is insufficient. Practitioners require "high-probability" guarantees: the assurance that a specific training run will succeed with, say, 99.9% confidence.
Historically, achieving such high confidence has come with significant trade-offs. Existing methods often rely on "light-tailed" noise assumptions (e.g., sub-Gaussian noise), which are frequently violated by real-world, "heavy-tailed" data. When these assumptions are relaxed, the computational or sample cost typically explodes, scaling poorly with the desired confidence level.
The proxBoost Meta-Algorithm
To bridge this gap, the authors introduce proxBoost, a meta-algorithm designed to transform standard stochastic optimization routines into high-confidence algorithms. The framework is "black-box" compatible, meaning it can be wrapped around existing state-of-the-art solvers like Accelerated SGD.
The core of proxBoost relies on the synergy between two classical mathematical techniques:
1. Robust Distance Estimation (The "Clustering" Trick)
Instead of relying on a single optimization run, proxBoost executes the base algorithm multiple times. This generates a set of candidate solutions. Because some runs might fail due to "bad luck" or extreme noise, the algorithm employs a robust estimation technique to identify the most reliable candidate.
By finding a point in the densest region of these results—often conceptualized as finding the "smallest ball" that contains a majority of the points—the algorithm can filter out outlier runs caused by heavy-tailed noise.
2. The Proximal Point Method (The "Continuation" Strategy)
While robust distance estimation is powerful, it can be inefficient when the optimization problem is "ill-conditioned" (i.e., the loss landscape is a narrow, elongated valley). proxBoost addresses this by utilizing the proximal point method. It solves a sequence of "regularized" versions of the original problem. Each step in this sequence is better-conditioned and easier to solve, using the result of the previous step as a starting point. This "continuation" strategy effectively amortizes the cost of achieving robustness.
Key Results and Theoretical Impact
The primary contribution of proxBoost is its efficiency. The authors prove that the overhead cost of moving from "average success" to "high confidence" is only logarithmic in the confidence level ($\log(1/p)$).
- Streaming Algorithms: For accelerated stochastic gradient methods, proxBoost achieves high-confidence bounds with sample complexity that nearly matches best-known average-case bounds, adding only minimal polylogarithmic overhead related to the problem's condition number.
- Empirical Risk Minimization (ERM): In offline learning scenarios, proxBoost significantly outperforms previous high-confidence ERM techniques (such as Hsu-Sabato bounds), particularly in how it scales with the "sharpness" of the loss function.
- Heavy-Tail Resilience: Crucially, these guarantees do not require sub-Gaussian noise assumptions, making the framework robust for practical data science where heavy-tailed distributions are common.
Limitations and Future Directions
While proxBoost represents a major step forward, it currently requires the objective function to be strongly convex. This is a common property in regularized machine learning, but it excludes purely convex or complex non-convex landscapes like those found in deep neural networks. Additionally, the algorithm requires prior knowledge of certain parameters, such as the condition number, which can be difficult to estimate in practice.
Future research aims to extend these confidence-boosting techniques to non-convex optimization and to develop adaptive versions of the algorithm that can estimate required parameters on the fly.
Summary updated