Research map / Learning theory and algorithms / Prediction and decision losses
A representation-learning game for classes of prediction tasks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a zero-sum game formulation for learning dimensionality-reducing representations given only a known class of response functions; derives closed-form pure and mixed minimax representations for the linear MSE setting and an incremental MWU-based algorithm for general classes and losses.
Problem
Learning low-dimensional representations of features when only a class of future prediction tasks is known, rather than a specific task or labels.
Approach
A representation player chooses a (possibly randomized) linear/general representation, and an adversary chooses a response function from a known class; the payoff is the regret relative to using original features. Closed-form minimax solutions are derived for linear MSE, and an incremental boosting-like algorithm that adds representation atoms via gradients handles general classes and losses.
Key results
- In the linear MSE setting, the algorithm's regret is within a ratio of about 1.15-1.2 of the theoretical minimax regret across tested dimensions.
- On the synthetic shape-image dataset, an optimized representation with r=3 matches PCA with at least r=12 dimensions.
- Mixed (randomized) minimax regret is strictly lower than pure minimax regret in the linear MSE setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Randomize the representation instead of using a single deterministic representation | Linear MSE minimax representation · Linear MSE setting | minimax regret | Helped |
| Use prior knowledge S to select representation directions | Pure minimax representation · Linear MSE setting | minimax regret | Helped |
| Randomize the representation rather than use top-r PCA directions | Minimax representation · Standard PCA setting | minimax regret | No clear effect |
| Use the incremental algorithm to learn a mixed representation | Incremental mixed-representation algorithm · Linear MSE setting, randomly drawn diagonal covariance matrices | ratio to theoretical regret: 1.15-1.2 | Hurt |
| Increase the support size m of the randomized representation | Incremental mixed-representation algorithm · Linear cross-entropy setting, isotropic normal features | regret | Helped |
| Use the optimized minimax representation instead of PCA | Simplified incremental algorithm · Multi-label shape classification | cross-entropy loss | Helped |
| Use the optimized minimax representation instead of PCA | Simplified incremental algorithm · Multi-label shape classification | accuracy | Helped |
Surprising findings
- Mixed randomized representations do not improve regret in standard unsupervised PCA, but do strictly improve it under prior knowledge on the response class.
Limitations
- No convergence guarantees for the general non-convex-concave algorithm.
- Closed-form results limited to linear MSE and linear cross-entropy settings.
- Combinatorial growth of the mixed-strategy support size in the linear case for high dimensions.
Experimental setup
Datasets: synthetic Gaussian features synthetic shape-composition images (1000 train, 1000 test)
Benchmarks: synthetic linear MSE setting synthetic linear cross-entropy setting synthetic multi-label shape classification
Metrics: regret ratio to theoretical value cross-entropy loss accuracy
Baselines: PCA
Builds on: PCA decodable information bottleneck game boosting multiplicative weights update
Closest papers by meaning
- Controllable Invariance through Adversarial Feature Learning (NeurIPS 2017 · similarity 0.87)
- Impact of Representation Learning in Linear Bandits (ICLR 2021 · similarity 0.86)
- Deep Learning Games (NeurIPS 2016 · similarity 0.86)
- Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees (NeurIPS 2022 · similarity 0.86)
- No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation (NeurIPS 2022 · similarity 0.85)
- NfgTransformer: Equivariant Representation Learning for Normal-form Games (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.