Source-linked AI summary
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
Francesco Orabona
TL;DR
Finite-sample SGD convergence depends on step sizes that are often unknown, while cross-validation slows stochastic training. PiSTOL uses data-dependent online step sizes to perform model selection during training without tuning parameters or validation, and the paper reports optimal convergence rates with respect to target smoothness.
Problem
SGD's finite-sample convergence critically depends on step sizes that are often unknown, while cross-validation for selecting them slows stochastic training.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The algorithm automatically self-tunes online for model selection without requiring a validation method.
Source: §7 · p. 9The paper proves convergence with respect to ℓ-risk, and whether high-probability bounds are possible without additional hypotheses remains unclear.
Source: §7 · p. 9
Abstract
from arXiv · showhide
Stochastic gradient descent algorithms for training linear and kernel predictors are gaining more and more importance, thanks to their scalability. While various methods have been proposed to speed up their convergence, the model selection phase is often ignored. In fact, in theoretical works most of the time assumptions are made, for example, on the prior knowledge of the norm of the optimal solution, while in the practical world validation methods remain the only viable approach. In this paper, we propose a new kernel-based stochastic gradient descent algorithm that performs model selection while training, with no parameters to tune, nor any form of cross-validation. The algorithm builds on recent advancement in online learning theory for unconstrained settings, to estimate over time the right regularization in a data-dependent way. Optimal rates of convergence are proved under standard smoothness assumptions on the target function, using the range space of the fractional integral operator associated with the kernel.
1 Introduction
SGD is scalable, but its convergence depends critically on step sizes that are often unknown; cross-validation can select them but slows stochastic training. PiSTOL extends online-learning tools to tune step sizes from data while training, without parameters or cross-validation.
1 Introduction
- SGD's finite-sample convergence depends critically on step sizes, which are rarely known optimally and can yield arbitrarily poor practical performance when chosen incorrectly.Prior approaches in infinite-dimensional RKHS either cover only realizable cases, assume unknown problem characteristics, or use cross-validation, which slows training.Source: §1 · p. 1
- The paper places its approach between IID stochastic learning and online convex optimization, whose adversarial setting is strictly more difficult than the IID setting.OCO algorithms can also be used to solve the corresponding stochastic problems.Source: §1 · p. 2
- PiSTOL extends online-learning tools to achieve optimal finite-sample convergence bounds in infinite-dimensional RKHS while selecting the model during training without tuning parameters or cross-validation.Its step sizes change over time in a data-dependent way, and its computational complexity matches plain SGD.Source: §1 · p. 2
- The paper presents PiSTOL as the first algorithm of this kind with provable optimal convergence rates.The paper roadmap places its adversarial regret bounds before its stochastic convergence results and empirical results.Source: §1 · p. 2
2 Problem Setting and Definitions
The paper formulates learning in a kernel RKHS, with performance measured by loss and online learning framed through regret against a fixed comparator. Its statistical setting uses IID samples, and its analysis relates the target function to fractional powers of the kernel integral operator.
2 Problem Setting and Definitions
- The Mercer kernel defines an RKHS inner product with the reproducing property: the inner product with K(x, ·) returns the function value at x.The paper writes this as ⟨K(x, ·), f(·)⟩_K = f(x).Source: §2 · p. 2
- The paper considers losses that are L-Lipschitz and H-smooth, with smoothness meaning a differentiable loss whose first derivative is H-Lipschitz.A loss can be both Lipschitz and smooth.Source: §2 · p. 2
- In the OCO setting, each round supplies an input and incurs loss at the algorithm's prediction, while regret compares cumulative loss with a fixed RKHS competitor.The statistical setting instead draws training samples IID from a fixed but unknown distribution.Source: §2 · p. 2
- For binary classification, the paper defines misclassification risk by disagreement with the label and calls the minimum measurable risk the Bayes risk.The Bayes classifier is the sign of the regression function.Source: §2 · p. 2
- The kernel integral operator is compact and positive, so its fractional powers are defined; smaller β corresponds to a larger function space in the analysis.The paper identifies this range space as central to its analysis.Source: §2 · p. 3
3 A Gentle Start: ASGD, Optimal Step Sizes, and the Perceptron
Averaged SGD links its step size to regularization, but a fixed choice can be suboptimal when the target's smoothness is unknown. The section motivates an online method with parameter-free regret, while explaining why the Perceptron’s mistake bound does not provide the needed convergence guarantee.
3 A Gentle Start: ASGD, Optimal Step Sizes, and the Perceptron
- Averaged SGD processes each sample once, updates with loss gradients, and returns the averaged solution; for square loss, the section considers a constant step size.The risk bound links step size to regularization: the averaged predictor's expected risk is close to that of the best regularized RKHS function.Source: §3 · pp. 3–4
- For the general assumption considered, ASGD's convergence rate depends on β, making a data-dependent step-size choice a potential self-tuning strategy.The section motivates extending self-tuning tools from online learning to an ASGD-like algorithm.Source: §3 · p. 3
- When the target's smoothness parameter β is unknown, the ASGD step size that is optimal for β = 1/2 is suboptimal in other cases.Under the stated general assumption, the infimum is attained only when β ≥ 1/2, though convergence can be proved for β > 0.Source: §3 · p. 3
- The Perceptron behaves independently of step size, but its mistake bound is not a regret bound and compares different losses for the learner and competitor.The bound is specific to binary classification and cannot establish convergence when β < 1/2.Source: §3 · p. 4
- The section seeks an online algorithm with regret scaling as O(∥h∥_K T^1/2) that returns an averaged solution to support convergence for β < 1/2.The Perceptron bound has the right form but lacks the required regret guarantee.Source: §3 · p. 4
4 PiSTOL: Parameter-free STOchastic Learning
PiSTOL is an SGD-like method that computes its solution from past gradients, with an incremental calculation that keeps its complexity the same as ASGD. Its regret bounds have near-optimal dependence on the comparator and time, with smooth-loss results and a linear-kernel variant also described.
4 PiSTOL: Parameter-free STOchastic Learning
- PiSTOL computes its solution from past gradients, and its incremental norm calculation gives it the same computational complexity as ASGD in an RKHS.The algorithm is presented under convex, L-Lipschitz losses and a bounded kernel-feature norm.Source: §4 · pp. 4–5
- PiSTOL's regret has the intended dependence on comparator norm and time and is optimal up to sqrt(log log T) terms.The stated theorem assumes convex L-Lipschitz losses and kernel-feature norms at most 1.Source: §4 · p. 5
- For smooth losses, the regret bound depends on the sum of absolute gradients rather than T, enabling a tighter bound when losses are H-smooth.The paper gives a smooth-loss corollary and notes that regret can grow slower than sqrt(T) when the competitor's cumulative loss is small.Source: §4 · p. 5
- When the competitor's cumulative loss is zero, PiSTOL's regret still grows, unlike the constant bound for smooth-loss methods.The paper characterizes this as a worse bound than those methods, while noting that they require prior knowledge of the competitor's norm.Source: §4 · p. 5
- PiSTOL does not require prior knowledge of the competitor function's norm, unlike the cited alternatives.Source: §4 · p. 5
- A linear-kernel variant has an almost optimal learning rate for each coordinate and is described as parameter-free, unlike a similar algorithm [13].The variant is presented in the Appendix.Source: §4 · p. 5
5 Convergence Results for PiSTOL
For IID training samples, PiSTOL’s online regret bounds are converted into risk guarantees for an averaged predictor. The guarantees include faster convergence when the optimal ℓ-risk is zero and match known lower bounds up to logarithmic terms in the capacity-independent setting.
Online-to-batch conversion
- The online-to-batch conversion averages the online algorithm’s predictors over IID samples, turning its regret bound into a convergence guarantee for the average.The losses are ℓ_t(x) = ℓ(y_t x).Source: §5 · p. 6
Classification risk
- For binary classification, the paper also bounds excess misclassification risk in the realizable setting, where f^ℓ_ρ ∈ H_K.The bound is stated using Lemma 1.Source: §5 · p. 6
Convergence guarantees
- The averaged PiSTOL predictor is consistent: its ℓ-risk converges at ˜O(T^-3β/(2β+1)) when the optimal ℓ-risk is zero, and ˜O(T^-2β/(2β+1)) otherwise.The theorem’s bounds hold under the assumptions of Corollary 1.Source: §5 · pp. 6–7
- When the optimal ℓ-risk is low, convergence has a faster initial regime that saturates as the sample count grows.The paper notes this regime is relevant when features and the kernel are chosen for low optimal ℓ-risk.Source: §5 · p. 7
- PiSTOL’s guarantees hold simultaneously and are theoretically better than SGD with step sizes tuned using β or with η = O(T^-1/2).The paper also gives an appendix result under a different smoothness condition.Source: §5 · p. 7
Optimality
- In the capacity-independent setting, the lower bound matches Theorem 2’s asymptotic rate up to logarithmic terms, establishing optimal convergence rates.The cited lower bound is for square loss and assumes polynomial eigenvalue decay; it does not cover the zero-risk case.Source: §5 · p. 7
6 Related Work
Prior work establishes strong stochastic-learning rates under specific loss, smoothness, or parameter-knowledge conditions. This paper’s approach is distinguished by being parameter-free and avoiding validation for model selection.
6 Related Work
- Earlier stochastic RKHS rates were improved over time, but prior approaches required knowing β; PiSTOL is parameter-free.The cited work obtains optimal bounds for β > 0 in expectation, while [29] gives high-probability bounds for 1/2 ≤ β ≤ 1.Source: §6 · pp. 7–8
- For 0 < β < 1/2, the range considered in this paper is described as “very tricky,” and the authors point readers to the discussion in.Source: §6 · p. 7
- Prior optimal stochastic results were specific to square loss, whereas PiSTOL supports any smooth and Lipschitz loss.The comparison names and [29] as square-loss-specific approaches.Source: §6 · p. 8
- Batch methods attained matching optimal rates for square loss under stated conditions, but selected the regularization parameter by cross-validation.The cited results cover β > 1/2 in high probability; extends coverage to 0 < β ≤ 1/2 with an additional infinity-norm assumption.Source: §6 · p. 8
- PiSTOL efficiently trains predictors with smooth losses using an implicit norm regularizer, without prior knowledge to set its regularization parameter.The comparison describes the regularizer as ∥h∥K and contrasts it with earlier feasibility concerns for q = 2.Source: §6 · p. 8
7 Discussion
PiSTOL is presented as a parameter-free stochastic method with optimal convergence rates and no validation-based model selection. Preliminary experiments compare it with tuned SVMs, while the discussion also describes a per-coordinate variant and states the assumptions and scope of convergence results.
7 Discussion
- The paper presents PiSTOL as a parameter-free stochastic algorithm with optimal rates tied to predictor smoothness, automatically tuning online without validation.Its stated design draws on online convex optimization and statistical learning theory tools.Source: §7 · p. 9
- PiSTOL closely tracks tuned SVM performance with a Gaussian kernel and is about 7 times faster on SensIT Vehicle: under 1 hour versus about 6.5 hours.The experiments used five random shuffles; the paper describes them as preliminary.Source: §7 · p. 9
- High-probability bounds without additional hypotheses remain unresolved, and the proved convergence is for ℓ-risk; stronger convergence may be possible when β ≥ 1/2.For β ≥ 1/2, the discussion notes f^ℓ_ρ ∈ HK as a basis for stronger results.Source: §7 · p. 9
A Per-coordinate Variant of PiSTOL
- The per-coordinate variant runs an independent PiSTOL copy on each coordinate for linear kernels under bounded-feature and Lipschitz-loss assumptions.The stated conditions include ∥x_t∥∞ ≤ 1 and a ≥ 2.25L; its regret bound is compared with AdaGrad up to logarithmic terms.Source: A Per-coordinate Variant of PiSTOL · p. 11
- Unlike AdaGrad’s dependence on ∥u∥∞² or prior knowledge of ∥u∥∞, the comparison says the per-coordinate bound depends on ∥u∥∞.The passage identifies this as the more important difference between the bounds.Source: A Per-coordinate Variant of PiSTOL · p. 11
B Convergence in L1
- Under IID sampling and the stated condition on (ρ, K), Theorem 3 gives a convergence result for PiSTOL’s averaged solution and improves on the cited result.The supplied passages do not include the theorem’s bound.Source: B Convergence in L1 · p. 12
C Details about the Empirical Results
This appendix section records experimental choices and proof material, including the loss and dataset setup, a conjugate definition, and elements of the regret-bound proof.
C Details about the Empirical Results
- PiSTOL uses a smoothed hinge loss in all experiments, while SVM uses the hinge loss.The reported setup also gives common PiSTOL parameters, though the supplied parameter text is incomplete.Source: C Details about the Empirical Results · p. 12
- The experiments include a9a, SensIT Vehicle, and news20.binary, with dataset-specific sample, feature, and kernel settings.For SensIT Vehicle, the three-class data are converted to a binary task by separating the third class from the other two.Source: C Details about the Empirical Results · p. 12
D.1 Additional Definitions
- The appendix defines the Fenchel conjugate h* of a closed convex function h through a supremum over functions in HK.The displayed expression is stated as h*(g) = sup over f ∈ HK.Source: §D.1 · p. 12
D.2 Proof of (3)
- The proof of equation (3) invokes an inequality extracted from reference.The supplied passage does not identify the inequality’s form.Source: §D.2 · p. 13
D.3 Proof of Theorem 1
- The regret-bound proof uses a time-varying potential that depends explicitly on the sum of past gradients, rather than only on time.The authors contrast this choice with proof methods in [15].Source: §D.3 · pp. 13–14
D.4 Proof of Corollary 1
The corollary proof uses technical lemmas, including a smooth-loss derivative bound and an inequality established through a unique positive solution.
D.4 Proof of Corollary 1
- For an H-smooth function with nonnegative values, the squared derivative is bounded by four times H times the function value.The lemma is attributed to [25, Lemma 2.1].Source: §D.4 · p. 17
- Lemma 6 states that an equation with positive coefficients and ordered exponents has a unique positive solution.The supplied passage introduces the existence and uniqueness claim but omits the equation.Source: §D.4 · p. 17
- Lemma 7 uses that unique-solution result to establish an inequality for positive a, b, c and 0 < α < 1.The proof substitutes y = x + b and applies Lemma 6.Source: §D.4 · p. 17
- The corollary proof applies Cauchy–Schwarz together with Lemmas 5 and 7.The supplied proof excerpt does not include the resulting bound in readable form.Source: §D.4 · p. 17
D.5 Proof of Lemma 1
The proof defines X_f by a disagreement between sign(f) and f_c, then uses prior technical results and Jensen’s inequality to conclude.
D.5 Proof of Lemma 1
- X_f is defined as the set of x in X where sign(f) differs from f_c.Source: §D.5 · p. 18
- The proof invokes Lemma 10.10 and the approach of Theorem 10.5 in, then concludes with Jensen’s inequality.Source: §D.5 · p. 18
D.6 Proof of Theorem 2
The appendix assembles lemma-based bounds for Theorem 2, then derives Theorem 3 using the preceding proof, the loss’s Lipschitzness, and expectation steps.
D.6 Proof of Theorem 2
- Lemma 10 adapts [12, Proposition 8.5] by using fℓρ instead of fρ, with fℓρ in the range of L^β.Source: §D.6 · p. 19
- A supporting lemma strengthens [12, Corollary 10.14] by requiring smoothness rather than a bound on the second derivative.Source: §D.6 · p. 19
- Theorem 2’s proof removes the norm inside the logarithmic term to obtain a bound depending only on the norm of g, then assembles the stated bound.Source: §D.6 · pp. 20, 22
D.7 Proof of Theorem 3
- Theorem 3’s proof starts from Theorem 2, uses the loss’s Lipschitzness and Lemma 9, then applies expectation and Jensen’s inequality.Source: §D.7 · p. 22