Designing smoothing functions for improved worst-case competitive ratio in online optimization
Online optimization covers problems such as online resource allocation, online bipartite matching, adwords (a central problem in e-commerce and advertising), and adwords with separable concave returns. We analyze the worst case competitive ratio of two primal-dual algorithms for a class of online convex (conic) optimization problems that contains the previous examples as special cases defined on the positive orthant. We derive a sufficient condition on the objective function that guarantees a constant worst case competitive ratio (greater than or equal to 1 2 ) for monotone objective functions. We provide new examples of online problems on the positive orthant that satisfy the sufficient condition. We show how smoothing can improve the competitive ratio of these algorithms, and in particular for separable functions, we show that the optimal smoothing can be derived by solving a convex optimization problem. This result allows us to directly optimize the competitive ratio bound over a class of smoothing functions, and hence design effective smoothing customized for a given cost function.
In this paper, the authors study a family of methods for online optimization in the (for lack of a better general descriptive term--if the authors know one, that would be great) generalized concave adwords problem. I am not as familiar with the area as I ought to be, so my review may be somewhat that of a neophyte.  The general problem is to understand the difference between the online solution of the problem  max. \psi(\sum_t A_t x_t)   s.t. x_t \in F_t  and its offline solution, where we measure quality by competitive ratio. The authors give a fairly clean analysis of the competitive ratio, based on convex analysis and the FTRL family of algorithms, and provide an extension to show how smoothing the function \psi can yield improved behavior. 
I am pro-acceptance for this paper, though I have (of course) criticisms.  Below are a number of comments I have about the paper, not particularly organized, but hopefully cogent enough.  The approach via convex analysis/online regret/duality is cleaner than the literature I have seen on this problem, which focuses on the "continuous update" idea of Devanur and Jain ([DJ] from here)--frankly, a somewhat obtuse and confusing idea--so that using duality more carefully is nice.  The main assumption on the superdifferentials relative to the cone inclusion, Assumption 1, certainly is important for the analysis, but I had a hard time understanding how much more generality it allowed over the standard separable case in [DJ]. The PSD cone is a nice example that makes clear that the generality is helpful, though I wonder if other natural examples exist. That would be quite helpful, as the notation in the paper is somewhat heavy, and I found constructing examples on the fly for intuition more challenging than I usually do.  Because the algorithm in the simultaneous case is the same (I believe?) as the "continuous update" of [DJ], I thought that when specialized to linear problems one should attain a competitive ratio of 1 - 1/e rather than 1/2. Am I missing something? Is this a weakness in the analysis? Is there actually a gap? The smoothing appears to achieve 1 - 1/e, so some similar algorithm achieves the correct competitive ratio... I found this a bit unclear.  A somewhat problematic issue with the paper is that the interaction of the smoothing operation with Assumption 1---the cone ordering condition on the superdifferential of \psi---is quite unclear. It appears that separable functions maintain good behavior on the positive orthant, which falls back into the [DJ] analysis. But the authors do not mention non-separable functions in Section 3, which I understood to be one of the major points of the current paper. Why the lack of discussion? To be clear, also, the "optimal" smoothing is chosen by optimization of a *bound* on the competitive ratio, not the ratio itself.  A second issue with the paper is the lack of compelling examples. The plots of smoothed functions are fine, but I would really like to see an example of behavior of these operations on a real problem. Just because one has improved a bound does not always mean one has improved the algorithm.  Frankly, I wish there were a "resubmission" period for these reviews, because this paper could use (1) a bit more space for clarity and (2) a few better experiments so that we could see the real effects of smoothing. I think there are nice ideas, but with a bit of touching up, they could become very nice.   Minor comments:  The authors never defined competitive ratio; it might be useful to have early on.  I found the notation a tiny bit confusing, as I had to swap all standard notation from convex analysis to the concave case (e.g. convex vs. concave conjugate, etc.). I am not sure if this is avoidable, though the NIPS audience is more generally familiar with the convex case and it might be clearer to form the primal problem as minimization. Not a deal-breaker or anything.  Pg. 4, line 112: calling D_seq the dual value was a little strange to me, as the sequence $\hat{y}_t$ does not obviously yield a dual feasible point, though as Theorem 1 shows D_sim and D_seq are actually tighter than D^*, the optimal dual value. It might be worth noting this earlier.  Pg. 8, lines 284-end. A relevant reference for understanding regret vs. competitive ratio, at least in a restricted set of problems, might be Andrew et al.'s "Tale of Two Metrics" (http://users.cms.caltech.edu/~katrina/papers/twometrics.pdf).