Affine-Invariant Online Optimization and the Low-rank Experts Problem
We present a new affine-invariant optimization algorithm called Online Lazy Newton. The regret of Online Lazy Newton is independent of conditioning: the algorithm's performance depends on the best possible preconditioning of the problem in retrospect and on its intrinsic dimensionality. As an application, we show how Online Lazy Newton can be used to achieve an optimal regret of order √ rT for the low-rank experts problem, improving by a √ r factor over the previously best known bound and resolving an open problem posed by Hazan et al. [15].
Summary:
This paper proposes a new optimization algorithm, Online Lazy Newton (OLN), based on Online Newton Step (ONS) algorithm. Unlike ONS which tries to utilize curvature information within convex functions, OLN aims at optimizing general convex functions with no curvature.  Additionally, by making use of low rank structure of the conditioning matrix, the authors showed that OLN yields better regret bound under certain conditions. Overall, the problem is well-motivated and the paper is easy to follow. 
 
Major Comments:
1. The major difference between OLN and ONS is that ONS introduces a lazy evaluation step, which accumulates the negative gradients at each round.  The authors claimed in Lines 155-157 that this helps in decoupling between past and future conditioning and projections and it is better in the case when transformation matrix is changing between rounds.  It would be better to provide some explanations.
 
2. Lines 158-161, it is claimed that ONS is not invariant to affine transformation due to its initialization.  In my understanding, the regularization term is added partly because it allows for an invertible matrix and can be omitted if Moore-Penrose pseudo-inverse is used as in the FTAL.
 
3. Line 80 and Line 180, it is claimed that  O(\sqrt(r T logT)) is improved upon O(r \sqrt(T)). The statement will hold under the condition that r/logT = O(1), is this always true?
 
Minor:
1. Lines 77-79, actually both ONS and OLN utilizes first-order information to approximate second-order statistics. 
 
2. Line 95, there is no definition of the derivative on the right-hand-side of the equation prior to the equation.
 
3. Line 148-149, on the improved regret bound.  Assuming that there is a low rank structure for ONS (similar to what is assumed in OLS), would the regret bound for OLS still be better than ONS?
 
4. Line 166, 'In The...' -> 'In the...'
 
5. Line 181, better to add a reference for Hedge algorithm.
 
6. Line 199,  what is 'h' in '... if h is convex ...'?
 
7. Line 211-212,  '...all eigenvalues are equal to 1, except for r of them...', why it is the case?  For D = I + B defined in Line 209, the rank for B is at most r, then at least r of the eigenvalues of D are equal to 1.
 
The regret bound depends on the low rank structure of matrix A as in Theorem 3, another direction that would be interesting to explore is to consider the low rank approximation to the matrix A and check if similar regret bound can be derived, or under which conditions similar regret bound can be derived.  I believe the proposed methods will be applicable to more general cases along this direction.