Papperoni

2011

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

John Duchi, Elad Hazan, Yoram Singer

Open PDF Google Scholar

citations

Cite Score

89

AI summary

This paper introduces Adaptive Subgradient Methods (ADAGRAD) for online learning and stochastic optimization, dynamically adjusting learning rates based on data geometry, achieving improved regret guarantees and outperforming non-adaptive methods on various datasets like ImageNet and RCV1.

Main Contributions

Introduces ADAGRAD, a new family of subgradient methods for online learning and stochastic optimization.
The methods dynamically incorporate knowledge of data geometry to perform more informative gradient-based learning.
Proposes an apparatus for adaptively modifying the proximal function, simplifying learning rate setting and offering improved regret guarantees.
Provides efficient algorithms for empirical risk minimization with common regularization functions and domain constraints.
Demonstrates that ADAGRAD methods outperform state-of-the-art non-adaptive subgradient algorithms in experimental studies.

Abstract

We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms.

Citation Graph

Loading graph...

References [44]

Sort:

Filter:

[1]ImageNet: A Large-Scale Hierarchical Image Database

J. Deng, W. Dong, Richard Socher, L. J. Li, K. Li, Li Fei Fei - 2009

28 papers in library cite

Very nice idea and huge impact!

[2]Term Weighting Approaches in Automatic Text Retrieval

G. Salton, C. Buckley - 1988

2 papers in library cite

TF-IDF!

[3]A Discriminative Kernel-Based Model to Rank Images From Text Queries

D. Grangier, Samy Bengio - 2008

2 papers in library cite

[4]An Optimal Method for Stochastic Composite Optimization

G. Lan - 2010

2 papers in library cite

[5]Online Convex Programming and Generalized Infinitesimal Gradient Ascent

M. Zinkevich - 2003

2 papers in library cite

[6]Online Passive-Aggressive Algorithms

K. Crammer, O. Dekel, J. Keshet, S. S. Shwartz, Yoram Singer - 2006

2 papers in library cite

[7]Rcv1: A New Benchmark Collection for Text Categorization Research

D. D. Lewis, Yining Yang, T. G. Rose, F. Li - 2004

2 papers in library cite

[8]SGD-Qn: Careful Quasi-Newton Stochastic Gradient Descent

Antoine Bordes, Leon Bottou, P. Gallinari - 2009

2 papers in library cite

[9]UCI Machine Learning Repository

K. Bache, M. Lichman - 2013

2 papers in library cite

[10]A New Approach to Variable Metric Algorithms

R. Fletcher - 1970

1 paper in library cites

[11]A Second-Order Perceptron algorithm

N. C. Bianchi, A. Conconi, C. Gentile - 2005

1 paper in library cites

[12]Adaptive and Self-Confident Online Learning Algorithms

P. Auer, C. Gentile - 2000

1 paper in library cites

[13]Adaptive Bound Optimization for Online Convex Optimization

H. B. Mcmahan, M. Streeter - 2010

1 paper in library cites

[14]Adaptive Online Gradient Descent

P. L. Bartlett, Elad Hazan, A. Rakhlin - 2007

1 paper in library cites

[15]Adaptive Regularization of Weight Vectors

K. Crammer, Mark Dredze, A. Kulesza - 2009

1 paper in library cites

[16]An Algorithm for a Singly Constrained Class of Quadratic Programs Subject to Upper and Lower Bounds

P. M. Pardalos, J. B. Rosen - 1990

1 paper in library cites

[17]An O(n) algorithm for Quadratic Knapsack Problems

P. Brucker - 1984

1 paper in library cites

[18]Comments on and Complements to Inequalities: Theory of Majorization and Its Applications

J. V. Bondar - 1994

1 paper in library cites

[19]Composite Objective Mirror Descent

John Duchi, S. S. Shwartz, Yoram Singer, A. Tewari - 2010

1 paper in library cites

[20]Concavity of Certain Maps on Positive Definite Matrices and Applications to Hadamard Products

T. Ando - 1979

1 paper in library cites

[21]Convex Analysis and Minimization Algorithms II

J. B. H. Urruty, C. Lemarechal - 1996

1 paper in library cites

[22]Convex Optimization

S. Boyd, L. Vandenberghe - 2004

1 paper in library cites

[23]Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization

L. Xiao - 2010

1 paper in library cites

[24]Efficient Algorithms for Online Decision Problems

A. Kalai, S. Vempala - 2003

1 paper in library cites

[25]Efficient Online and Batch Learning Using Forward Backward Splitting

John Duchi, Yoram Singer - 2009

1 paper in library cites

[26]Exact Convex Confidence-Weighted Learning

K. Crammer, Mark Dredze, Fernando Pereira - 2008

1 paper in library cites

[27]Extracting Certainty From Uncertainty: Regret Bounded by Variation in Costs

Elad Hazan, S. Kale - 2008

1 paper in library cites

[28]Improved Second-Order Bounds for Prediction With Expert Advice

N. C. Bianchi, Y. Mansour, G. Stoltz - 2007

1 paper in library cites

[29]Joint Covariate Selection for Grouped Classification

G. Obozinski, B. Taskar, M. Jordan - 2007

1 paper in library cites

[30]Lecture Notes on Online Learning

A. Rakhlin - 2009

1 paper in library cites

Reference title contains 'et al'

[31]Logarithmic Regret Algorithms for Online Convex Optimization

Elad Hazan, A. Kalai, S. Kale, Akshat Agarwal - 2006

1 paper in library cites

[32]Matrix Analysis

R. A. Horn, C. R. Johnson - 1985

1 paper in library cites

[33]Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization

A. Beck, M. Teboulle - 2003

1 paper in library cites

[34]Notions Generalizing Convexity for Functions Defined on Spaces of Matrices

C. Davis - 1963

1 paper in library cites

[35]On Accelerated Proximal Gradient Methods for Convex-Concave Optimization

P. Tseng - 2008

1 paper in library cites

[36]On the Generalization Ability of on-Line Learning Algorithms

N. C. Bianchi, A. Conconi, C. Gentile - 2004

1 paper in library cites

[37]Optimal Strategies and Minimax Lower Bounds for Online Convex Games

J. Abernethy, P. L. Bartlett, A. Rakhlin, A. Tewari - 2008

1 paper in library cites

[38]Primal-Dual Subgradient Methods for Convex Problems

Y. Nesterov - 2009

1 paper in library cites

[39]Problem Complexity and Efficiency in Optimization

A. S. Nemirovski, D. B. Yudin - 1983

1 paper in library cites

[40]Robust Stochastic Approximation Approach to Stochastic Programming

A. Nemirovski, A. Juditsky, G. Lan, A. Shapiro - 2009

1 paper in library cites

[41]Smooth Minimization of Nonsmooth Functions

Y. Nesterov - 2005

1 paper in library cites

[42]Solving Variational Inequalities With the Stochastic Mirror-Prox algorithm

A. Juditsky, A. Nemirovski, C. Tauvel - 2008

1 paper in library cites

[43]Subgradient Methods for Convex Minimization

A. Nedic - 2002

1 paper in library cites

[44]Utilization of the Operation of Space Dilation in the Minimization of Convex Functions

N. Z. Shor - 1972

1 paper in library cites

Cited by

19

papers in your library

Cites

2

papers in your library

Read

on February 15, 2026

I actually skimmed through most of this. It's not a bad paper, but it's a math paper, not AI.

Tags

Paper Aliases

No aliases