Unverified

Learning Sparse Linear Concepts by Priming the Features

In the online square-loss setting, let $(X_t,y_t)$ denote all examples observed through time $t$ , let $p_t=p(X_t,y_t)$ be a data-dependent priming vector, and predict with

w_t=\operatorname{diag}(p_t) (X_t\operatorname{diag}(p_t))^\dagger y_t.

Problem 1.

Are there competitive regret bounds for any of the proposed priming methods?

Problem 2.

What is the optimal priming function for sparse linear problems?

Problem 3.

Are there priming methods for learning sparse disjunctions?

Problem 4.

Can a kernel be primed efficiently, so that one approximately primes the implicit feature space before computing weights with the primed kernel?

Problem 5.

For which losses can an expert algorithm be reparameterized as gradient descent on a spindly network?

Problem 6.

What does the spindly gradient method converge to, and does its limit have a closed-form solution?

Download

Abstract

Sparse linear problems can be learned well with online multiplicative updates, whose regret grows only logarithmically with the feature dimension, but these updates lack closed-form batch solutions. Feature priming applies linear least squares, rescales each feature by a data-dependent prime factor, and applies least squares again. Experiments show behavior similar to multiplicative updates on sparse targets without hurting dense targets. The main open problem is whether such priming methods have provably competitive online regret bounds, together with related questions about optimal priming, sparse disjunctions, kernels, and spindly reparameterizations.

Background and progress

Exponentiated-gradient updates learn sparse linear regression with square-loss regret logarithmic in the feature dimension [Kivinen and Warmuth, 1997]. By contrast, gradient descent, ridge regression, and linear least squares are rotation invariant and have bounds linear in the dimension on dense instances. Multiplicative updates can be reparameterized as gradient descent on a two-layer ``spindly'' network, recovering sparse-regression and sparse-disjunction guarantees [Amid and Warmuth, 2020, Amid and Warmuth, 2020].

For past examples represented by a design matrix $X$ and label vector $y$ , ordinary least squares gives $w_{\mathrm{LLS}}=X^\dagger y$ . Given prime factors $p$ , feature priming rescales column $i$ by $p_i$ and returns

w_p=\operatorname{diag}(p)(X\operatorname{diag}(p))^\dagger y.

The source considers coordinatewise one-dimensional least squares, Pearson correlations, and $p=w_{\mathrm{LLS}}$ . Experiments suggest all three rapidly identify sparse targets while behaving like least squares for dense targets, but no worst-case regret bounds are known. The open problem is posed directly in [Warmuth and Amid, 2023].

Reference papers

Open Problem: Learning sparse linear concepts by priming the featuresManfred K. Warmuth, Ehsan AmidProceedings of Thirty Sixth Conference on Learning Theory · 2023 ↗
Reparameterizing Mirror Descent as Gradient DescentEhsan Amid, Manfred K. WarmuthAdvances in Neural Information Processing Systems · 2020
Winnowing with Gradient DescentEhsan Amid, Manfred K. Warmuth33rd International Conference on Algorithmic Learning Theory (COLT) · 2020
Exponentiated Gradient versus Gradient Descent for Linear PredictorsJyrki Kivinen, Manfred K. WarmuthInformation and Computation · 1997