PaperlayerView exact revision on arXiv

Source-linked AI summary

Sublinear Optimization for Machine Learning

Kenneth L. Clarkson, Elad Hazan, David P. Woodruff

arXiv:1010.4408v1cs.LG

TL;DR

The paper addresses whether key machine-learning optimization problems can be approximated in sublinear time, including settings where prior sublinear algorithms were unavailable. It combines sampling with a multiplicative-update method, extends the approach to kernelized and semi-streaming settings, and establishes near-best-possible running times for many algorithms. The resulting methods cover linear classification, minimum enclosing balls, and SVM-related problems while supporting arbitrary approximation factors in the semi-streaming model.

  • Problem

    The paper targets machine-learning optimization problems, including kernelized versions for which sublinear-time algorithms were not previously known.

  • Method

    The algorithms combine sampling with a multiplicative-update approach and extend to kernelized, parallel, and semi-streaming implementations.

  • Results

    The methods improve leading-order terms for linear classification and minimum enclosing ball, with classification bounds near-optimal up to polylogarithmic factors and semi-streaming algorithms supporting arbitrary approximation factors.

  • Takeaways & Limitations

    Sublinear primal-dual algorithms provide a general method for approximating classical machine-learning convex programs across standard, kernelized, and semi-streaming settings.

  • Takeaways & Limitations

    Las Vegas algorithms with low expected time and no errors cannot be obtained in sublinear time.

Abstract

from arXiv · show

We give sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and L2-SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model. We also give implementations of our algorithms in the semi-streaming setting, obtaining the first low pass polylogarithmic space and sublinear time algorithms achieving arbitrary approximation factor.

1 Introduction

The paper develops sublinear-time approximation algorithms for machine-learning optimization, extending them to kernelized, parallel, and semi-streaming settings. Its approach combines sampling with multiplicative updates, while lower bounds show near-optimality for many algorithms.

  • 1 Introduction: The new perceptron method learns an adversarial distribution, forms an expected bad vector, and estimates inner products through fast sampling rather than explicitly finding a misclassified vector.This preserves the iterative hyperplane-update structure while avoiding exact scans for a bad example.
  • 1 Introduction: Sublinear algorithms are developed for linear classification, minimum enclosing balls, and hard-margin or L2-SVM formulations.The approach also extends to some popular kernels, including Gaussian and polynomial kernels.
  • 1 Introduction: The algorithms improve leading-order terms for classical problems, while lower bounds make classification nearly best possible and MEB optimal up to an ˜O(ε^-1) factor.The lower bounds use inputs where a randomly planted coordinate determines the output, requiring broad examination for constant success probability.
  • 1 Introduction: Semi-streaming implementations achieve arbitrary approximation factors with low pass, space, and time complexity, including ˜O(ε^-2) passes, ˜O(ε^-2) space, and ˜O(ε^-4(n + d)) total time for linear classification.Prior streaming algorithms required Ω(d) space and did not achieve sublinear o(nd) time.
  • 1 Introduction: O(ε^-2(n + d)(log n) log(n/δ)) time returns an ε-approximate linear-classification solution with probability at least 1 −δ, optimal up to polylogarithmic factors in the unit-cost RAM model.The algorithm therefore uses sublinear time under the paper’s input-access assumptions.
  • 1 Introduction: The method uses a multiplicative-weights variant that handles unbounded updates and manageable ℓ2-sampling variance, replacing exponential multipliers with quadratic ones.The paper also notes that semi-streaming implementations require careful arithmetic-precision analysis and lazy updates.

2 Linear Classification and the Perceptron

The sublinear perceptron replaces explicit searches for misclassified examples with randomized sampling and multiplicative updates, achieving approximate linear classification in sublinear time. Its analysis combines sampling, regret bounds, concentration, verification, and probability amplification.

  • Algorithm: Randomized online gradient and multiplicative-weights updates replace explicit bad-vector searches while using unbiased sampled estimates of the relevant products.The algorithm samples rows using p_t and columns using x_t, with clipping controlling the estimator analysis.
  • Running time: O(ε−2 log n) iterations and total time O(ε−2(n + d) log n) yield the sublinear perceptron’s stated efficiency.Each iteration uses one ℓ2 sample and updates requiring O(n + d) time.
  • Analysis: A variance-sensitive multiplicative-weights lemma supplies a regret bound for random losses whose variance is controlled by ℓ2 sampling.This lemma is identified as a key ingredient for the upper-bound results.
  • Amplification and verification: Verification and repetition amplify the basic result: an ε-approximate solution can be verified, and a high-probability solution can be obtained with expected near-sublinear work.The Las Vegas version gives expected O(M + ε−2(n + d) log n) work for a verified solution.
  • Implications in the PAC model: The approach improves a standard PAC-model running-time bound by a factor of ˜O(σ2d) under the stated assumptions.The sublinear perceptron is used to compute a σ/2-approximation over the test data.

3 Strongly convex problems: MEB and SVM

The paper develops sublinear primal-dual algorithms for MEB and related convex quadratic problems, including hard-margin and L2-SVM formulations. For MEB, the method achieves approximate solutions with provable sublinear complexity and high-probability variants.

  • 3.1 Minimum Enclosing Ball: With probability 1/2, Algorithm 2 returns an ε-approximate MEB solution.The algorithm uses a primal-dual update scheme with multiplicative-weight updates and sampled rows and coordinates.
  • 3.1 Minimum Enclosing Ball: The MEB algorithm runs for O(ε−2 log n) iterations, while updates to the primal vector occur only O(ε−1 log T) times in expectation.Batching iterations in which the primal vector does not change reduces the cost of expensive operations.
  • 3.1 Minimum Enclosing Ball: For MEB, a high-probability algorithm returns an ε-approximation in expected time ˜O(n ε−2 log n ε).Verification converts the constant-probability procedure into a Las Vegas-style expected-time guarantee.
  • 3.3 Convex Quadratic Programming in the Simplex: The approach extends to hard-margin SVM, L2-SVM, and other convex quadratic programs represented over the unit simplex.The formulation includes MEB, margin estimation, hard-margin SVM, and L2-SVM as instances of a common optimization problem.
  • 3.3 Convex Quadratic Programming in the Simplex: When σ^2 > ϵ, the margin procedure returns a solution with ˆσ ≥ σ − ϵ′ in time ˜O(n/(ϵσ)^2 + d/ϵ′σ).The guarantee follows after scaling the approximate solution; when σ^2 ≤ ϵ, the procedure provides no useful information.

4 A Generic Sublinear Primal-Dual Algorithm

The generic sublinear primal-dual framework combines low-regret optimization with constant-time unbiased sampling. It applies beyond classification and yields sublinear algorithms for zero-sum games and broader constrained optimization problems.

  • 4 A Generic Sublinear Primal-Dual Algorithm: The framework applies whenever low-regret optimization and efficient low-variance sampling are available for the constrained problem.The generic formulation assumes bounded costs and a constant-time unbiased estimator with variance at most one.
  • 4.1 More applications: Applied to zero-sum games, the method obtains an ε-approximate solution in O(log n ε−2) iterations and total time ˜O(n+d.The simplex is used as the strategy space, and multiplicative weights supplies the required low-regret algorithm.
  • 4.1 More applications: The same framework can approximate essentially any constrained optimization problem with convex or linear constraints over a simple convex body such as a ball or simplex.Soft-margin SVM is identified as an application of this broader perspective.

5 A Semi-Streaming Implementation

The semi-streaming implementation avoids explicitly storing solution vectors by maintaining sampled row and coordinate indices that implicitly represent them. It achieves low-pass, low-space, sublinear-time guarantees for classification and MEB under a row-streaming access model.

  • 5 A Semi-Streaming Implementation: The streaming model assumes that complete input points arrive row by row, with arbitrary row ordering.The implementation relies on streaming sketches and sampling procedures for implicitly represented vectors.
  • 5 A Semi-Streaming Implementation: An augmented ℓ2-sampler selects coordinate j with probability proportional to |x_j|^2 while returning its value, using polylogarithmic space.This enables sampling from iterate vectors that cannot be stored explicitly.
  • 5 A Semi-Streaming Implementation: The implementation uses norm sketches and ℓ2-sampling to reconstruct the sampled updates while storing only a small set of indices.For MEB, an unbiased norm estimator is used because explicitly computing norms would require too much space.
  • 5 A Semi-Streaming Implementation: The classification implementation uses ˜O(ε−2) passes and space, total time ˜O(ε−4(n + d)), and an implicit representation of the normal vector.It outputs sampled row indices together with an additive-ε margin approximation.
  • 5 A Semi-Streaming Implementation: The MEB implementation uses ˜O(ε−1) passes and ˜O(ε−2) space, total time ˜O(ε−3(n+d)), and implicitly represents the center.The output includes sampled row indices and an additive ε-approximation to the MEB radius.

6 Kernelizing the Sublinear algorithms

The paper extends its sublinear optimization framework to kernelized linear predictors, using implicit feature representations and sampled kernel products. It develops Kernel-L2-Sampling estimators and derives running-time guarantees for polynomial, Gaussian, and strongly convex kernelized problems.

  • Kernelized approach: Kernelized algorithms operate in an implicit Hilbert-space representation, estimating needed inner products without explicitly computing Ψ(A_i).Kernel-L2-Sampling uses implicit representations and properties of the chosen kernel to estimate ⟨x_t, Ψ(A_i)⟩.
  • Kernel-L2-Sampling: With probability at least 1 −δ, the norm estimates satisfy |Ŷ_t(t^2/2T) − ∥y_t∥| ≤ ε, using O((log(1/εδ)T^2/ε^2)) calls to the approximate kernel.Exact computation instead requires T^2 calls to the exact kernel.
  • Kernel-L2-Sampling: Kernel-L2-Sampling has additive bias O(ε) and variance at most one, enabling the kernel perceptron to retain the properties of the un-kernelized algorithm.Apart from norm estimation, one iteration takes nL_k expected time, leading to the stated total running-time bound.
  • Scope: The framework applies to Gaussian and polynomial kernels and also supports Las Vegas guarantees and soft-margin SVM extensions.For Las Vegas algorithms, output guarantees always hold while only the running time is probabilistic.
  • Kernel estimators: The polynomial and Gaussian kernels are handled through unbiased or low-bias estimators built from ℓ2-sampling and kernel-specific randomization.Polynomial estimation multiplies q independent ℓ2-samples, while Gaussian estimation uses Poisson-distributed products of sampled inner-product estimates.
  • Kernelized MEB: The kernelized MEB algorithm runs in O(L_k(ε^−2n + ε^−1d)) time because it never needs to estimate ∥y_t∥.This removes the norm-estimation component required by the kernel perceptron.

7 Lower bounds

The lower bounds show that sublinear optimization algorithms must inspect substantial portions of the input for classification and MEB tasks. These information-theoretic bounds establish near-optimality for classification and constrain MEB algorithms that output coresets or convex-combination centers.

  • General framework: The lower bounds are information-theoretic: successful algorithms must read a specified number of entries of A, which directly lower-bounds unit-cost RAM time.The constructions hide decisive information in input coordinates that must be examined.
  • Classification: The classification lower bounds remain valid even when every row of A has unit norm.This condition is stated for both the n-dependent and d-dependent constructions.
  • Consequences: The lower-bound results imply near-optimal classification algorithms up to polylogarithmic factors, while the MEB bounds are optimal up to an ˜O(ε^−1) factor.The paper explicitly states these optimality comparisons for its algorithms.
  • Minimum Enclosing Ball: For MEB, the lower bounds include Ω(n) and Ω(d) entry requirements, with stronger bounds applying when algorithms output a coreset or a convex combination of input rows.The stronger results establish ˜Ω(nε^−2) under the stated dimensional regimes.
  • Minimum Enclosing Ball: The MEB lower-bound constructions distinguish instances whose radii differ between 0 and 1 or by an additive ε while preserving unit-norm rows in the relevant settings.These distinctions allow query lower bounds to transfer to approximation algorithms.

8 Concluding Remarks

The paper presents a general sublinear method for constrained convex programs and applies it to linear classification and minimum enclosing ball. It also notes a sparsity-sensitive implementation condition and identifies soft-margin SVM extensions as ongoing work.

  • Contributions: The paper’s general method yields sublinear algorithms for classical machine-learning problems including linear classification and minimum enclosing ball.The authors report improvements in leading-order terms over the state of the art.
  • Future work: Applications to soft-margin SVM and related convex problems remain ongoing work.The conclusion specifically identifies this extension as joint work with Nati Srebro.
  • Sparsity-sensitive implementation: The dimension d can be replaced by the maximum row sparsity S when row entries can be recovered in O(S) time.The parameters satisfy d ≥ S ≥ M/n, and hash-table or sorted-row storage supports the required access.

A.1 Tools from online learning

This section collects online-learning tools used to analyze the algorithms, including online gradient descent, lazy projection, and strongly convex variants. The lemmas allow the losses or gradients to depend on earlier iterates while retaining boundedness assumptions.

  • Online gradient descent: The online-learning toolkit includes standard and lazy-projection online gradient descent for bounded vectors over the unit ball.The lazy version is used for streaming and parallel implementations.
  • Online gradient descent: The stated online-gradient-descent guarantees remain applicable when each q_t depends on earlier iterates.This dependency condition is explicitly allowed in the corresponding lemmas.
  • Strong convexity: For H-strongly convex functions with gradient norm bounded by G, the strongly convex lemmas provide the corresponding online optimization analysis.The assumptions require Hessian eigenvalues at least H throughout the unit ball.
  • Strong convexity: The strongly convex analysis also permits each function f_t to depend on x_1, …, x_{t−1}.This preserves the applicability of the lemmas to adaptive sequences of functions.
  • Streaming implementation: Lazy updates are particularly useful for the MEB application and related streaming problems.The section introduces a lazy strongly convex lemma as the analogous tool needed there.

B Auxiliary lemmas

This section establishes auxiliary bounds for clipped random variables and convex combinations. Clipping controls expectation bias, while convex combinations preserve a second-moment bound.

  • B Auxiliary lemmas: Clipping a random variable with bounded variance controls the deviation between its clipped and original expectations.The proof uses a variance-over-threshold bound for the clipping level C.
  • B Auxiliary lemmas: The second moment of a convex combination of random variables is at most the larger of their individual second moments.The result follows by induction from the two-variable inequality.
  • B Auxiliary lemmas: The convex-combination bound is obtained by expanding the square and applying Cauchy-Schwarz to the cross term.

B.1 Martingale and concentration lemmas

This section adapts Bernstein-style concentration from independent variables to martingale difference sequences. The proof controls an exponential generating function through conditional expectations and then applies the usual Markov-inequality argument.

  • B.1 Martingale and concentration lemmas: The concentration argument requires centered variables with bounded second moments and uniformly bounded magnitudes.These assumptions appear explicitly in the independent-variable setup used by the adapted proof.
  • B.1 Martingale and concentration lemmas: The paper develops a Bernstein-type concentration bound for martingale differences under a filtration whose states depend only on the preceding state.The martingale setting replaces independence while retaining bounded conditional second moments and ranges.
  • B.1 Martingale and concentration lemmas: The key proof step bounds the exponential generating function of the sum using conditional expectations and iterated expectation.This is the point where the martingale filtration substitutes for independence.
  • B.1 Martingale and concentration lemmas: The resulting bound follows the independent Bernstein proof after optimizing the parameter and applying Markov’s inequality.The optimization uses V log(1 + αV/Ts), followed by a logarithmic inequality.

B.2 Proof of lemmas used in main theorem

This section applies the auxiliary clipping and martingale concentration lemmas to the estimates used in the main theorem. It verifies boundedness, variance, bias, and high-probability control for the relevant sampled quantities.

  • B.2 Proof of lemmas used in main theorem: The sampled estimates are clipped variables whose expectation bias is at most η because their pre-clipping variance is at most one.The clipping operation also preserves a bounded variance needed later.
  • B.2 Proof of lemmas used in main theorem: The resulting failure probability is at most 1/n^2 after choosing the relevant concentration parameters.
  • B.2 Proof of lemmas used in main theorem: The proofs combine bounds on conditional variance, variable range, and clipping bias to establish the stated high-probability estimates.A union bound over coordinates is used in one of the conclusions.
  • B.2 Proof of lemmas used in main theorem: The martingale concentration lemma applies because the centered sampled terms have zero conditional expectation and bounded magnitude.The construction gives |Z_t^i| ≤ 2/η before invoking the Bernstein-type inequality.
  • B.2 Proof of lemmas used in main theorem: Markov’s inequality supplies the final lemma once the relevant nonnegative quantities are bounded.

C Bounded precision

This section shows that the algorithms can use bounded-precision representations and tolerate approximation of training functions, played points, and vector norms. The resulting approximations retain controllable regret under explicit error bounds.

  • C Bounded precision: All algorithms in the paper can be implemented with bounded precision.
  • C Bounded precision: Approximating both training functions and played points increases regret in a controlled way rather than invalidating the guarantee.The general approximation lemma transfers regret against approximate functions and points to regret against the true functions.
  • C Bounded precision: For the paper’s function class, function approximation follows from additive errors in b_t and q_t, while point approximation follows from a norm bound on ˜x_t − x_t.The stated sufficient condition for point approximation is ∥˜x_t − x_t∥ ≤ α_x/3.
  • C Bounded precision: Approximate vector sequences preserve regret when their l1 distance from the exact sequence is bounded.A corresponding perturbation lemma also handles approximate payoff vectors q_t.
  • C Bounded precision: Relative entrywise accuracy is sufficient for the needed l1 approximation, enabling approximate norm computation in semi-streaming and kernelized algorithms.The norm calculations need only relative accuracy of roughly ϵ.

C.1 Bit Precision for Algorithm 1

The implementation requires finite arithmetic precision for both the OGD and multiplicative-weights components, with errors controlled so they alter only constant factors. Under the stated simplex and boundedness assumptions, the precision analysis carries over up to constants.

  • C.1 Bit Precision for Algorithm 1: OGD needs row and iterate approximations within Euclidean distance γ, while estimating ∥y_t∥ requires only relative error γ.Here γ is a sufficiently small constant fraction of ϵ.
  • C.1 Bit Precision for Algorithm 1: Sampling approximates the update quantity so its expectation matches A x̂_t, with x̂_t remaining within O(γ) Euclidean distance of x_t.This sampling error is charged to the OGD analysis.
  • C.1 Bit Precision for Algorithm 1: For multiplicative weights, ηϵ/5 relative precision before clipping and comparable clipping precision keep the computed quantity within ϵ/5 of its exact value.The clipping bound is B = 1/η because clipping bounds ∥q_t∥∞.
  • C.1 Bit Precision for Algorithm 1: Keeping update-step relative error at a small fraction of ηϵ/T limits cumulative update error to ηϵ/3 and α_q to ϵ/3, adding at most Tϵ regret.The stated bounds are α_p ≤ ηϵ/3 and α_q ≤ ϵ/3.
  • C.1 Bit Precision for Algorithm 1: Arithmetic precision yields additive Tϵ/10 regret relative to exact computation, adding only ϵ/10 error to the solution.The resulting change affects only constant factors in the algorithm.
  • C.1 Bit Precision for Algorithm 1: The precision discussion applies to convex quadratic programming in the simplex when every A_i belongs to B, without needing to compute ∥y_t∥.The transfer is stated to hold up to constants.
Loading 1010.4408v1…