Here is the list of interesting papers accepted in NIPS 2012 related to Online Learning and Convex Optimization:

**A. Online Learning**

- No-Regret Algorithms for Unconstrained Online Convex Optimization

- Mirror Descent Meets Fixed Share (and feels no regret)

- Relax and Randomize : From Value to Algorithms

- Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence

- Confusion-Based Online Learning and a Passive-Aggressive Scheme

- Risk-Aversion in Multi-armed Bandits

- Efficient Monte Carlo Counterfactual Regret Minimization in Games with Many Player Actions

**B. Convex Optimization**

- Optimal Regularized Dual Averaging Methods for Stochastic Optimization

- Proximal Newton-type Methods for Minimizing Convex Objective Functions in Composite Form

- Query Complexity of Derivative-Free Optimization

- Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

- A quasi-Newton Proximal Splitting Method

- Stochastic Gradient Descent with Only One Projection

- A Stochastic Gradient Method with an Exponential Convergence
Rate with Finite Training Sets

- Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization

- Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

- Feature Clustering for Accelerating Parallel Coordinate Descent