Research map / Optimization / Optimizers
Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging
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 AOGD, a lightweight online gradient descent method for kernelized pairwise (AUC) learning that uses a moving-average example plus a random past example per step, with random Fourier features to approximate Gaussian kernels, claiming O(T) complexity and sublinear regret without the iid assumption.
Problem
Online pairwise learning (e.g., AUC maximization, metric learning) requires pairing each new example with all past examples, giving quadratic cost; prior efficient buffer methods are mostly linear and assume iid data, and kernel versions are costly.
Approach
Replace the all-pairs gradient with two steps: one using the gradient against a moving average of past examples, then a correction step using gradient against a randomly sampled past example, with the kernel approximated by random Fourier features so that the per-step cost is linear in T and no iid assumption is needed.
Key results
- AOGD achieves the best AUC on ijcnn1 (92.32), a9a (90.03), mnist (96.98), rcv1 (99.38), usps (92.76) and german (80.75) among compared methods in the reported table.
- On diabetes AOGD (81.91) is slightly below OGD (82.53) and Sparse Kernel (82.64).
- Theory claims sublinear regret and O(sqrt(T) log T) random features suffice for the Gaussian kernel, with per-step gradient complexity O(D/d * T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AOGD instead of Sparse Kernel | AUC maximization · diabetes | AUC: 81.91}$\pm$0.48 vs 82.64$\pm$0.37 | Hurt |
| Use AOGD instead of Projection++ | AUC maximization · ijcnn1 | AUC: 92.20$\pm$0.27 -> 92.32}$\pm$0.77 | Helped |
| Use AOGD instead of OGD | AUC maximization · a9a | AUC: 90.01$\pm$0.42 -> 90.03}$\pm$0.41 | Helped |
| Use AOGD instead of SPAM-NET | AUC maximization · mnist | AUC: {96.57}$\pm$0.54 -> 96.98}$\pm$0.38 | Helped |
| Use AOGD instead of OGD | AUC maximization · rcv1 | AUC: 99.05$\pm$0.57 -> 99.38}$\pm$0.48 | Helped |
| Use AOGD instead of Sparse Kernel | AUC maximization · usps | AUC: 91.25$\pm$0.84 -> 92.76}$\pm$0.48 | Helped |
| Use AOGD instead of Sparse Kernel | AUC maximization · german | AUC: 80.11$\pm$0.44 -> 80.75}$\pm$0.48 | Helped |
Surprising findings
- On diabetes the proposed method is not the best; OGD and Sparse Kernel score higher.
Limitations
- Theoretical guarantees rely on assumptions such as linear separability and bounded variance; the Jensen gap bound depends on data variance.
- Experiments are limited to AUC maximization with a squared loss on seven datasets.
- Claims of O(sqrt(T) log T) features and sublinear regret rest on proof sketches with questionable steps (e.g., the kernel-approximation proof).
Experimental setup
Datasets: diabetes ijcnn1 a9a mnist rcv1 usps german
Benchmarks: diabetes ijcnn1 a9a mnist rcv1 usps german
Metrics: AUC
Baselines: SPAM-NET OGD Sparse Kernel Projection++ Kar
Builds on: online buffer learning reservoir sampling random Fourier features OGD for pairwise learning
Closest papers by meaning
- Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning (NeurIPS 2021 · similarity 0.94)
- Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning (AAAI 2025 · similarity 0.85)
- Learning Curves of Stochastic Gradient Descent in Kernel Regression (ICML 2025 · similarity 0.85)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.85)
- From Logistic Regression to the Perceptron Algorithm: Exploring Gradient Descent with Large Step Sizes (AAAI 2025 · similarity 0.84)
- Joker: Joint Optimization Framework for Lightweight Kernel Machines (ICML 2025 · 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.