We consider a mechanism design problem where an auctioneer allocates k units of an item to multiunit demand buyers arriving in an online fashion, each with a constant private marginal value. The auctioneer can inspect buyers allocated to learn their types and use this information to lower payments to reward truthful buyers. By using tools from the Calculus of Variations, we fully characterize the optimal mechanism for a single-buyer problem subject to an upper bound on the allocation expectation. In particular, we characterize the optimal allocation strategy as the solution of an ordinary differential equation and establish that it is a continuous and monotonically increasing function of the buyer's types. With the solution to the single-buyer problem, and by using connections to the prophet inequality literature, we design an online mechanism that achieves [EQUATION] of the optimal (offline) revenue, where αmax denotes the highest fraction of all units a buyer requests.1

We consider the problem of optimizing an approximately convex function over a bounded convex set in \mathbbR^n using only function evaluations. The problem is reduced to sampling from an \emphapproximately log-concave distribution using the Hit-and-Run method, which is shown to have the same \mathcalO^* complexity as sampling from log-concave distributions. In addition to extend the analysis for log-concave distributions to approximate log-concave distributions, the implementation of the 1-dimensional sampler of the Hit-and-Run walk requires new methods and analysis. The algorithm then is based on simulated annealing which does not relies on first order conditions which makes it essentially immune to local minima. We then apply the method to different motivating problems. In the context of zeroth order stochastic convex optimization, the proposed method produces an ε-minimizer after \mathcalO^*(n^7.5ε^-2) noisy function evaluations by inducing a \mathcalO(ε/n)-approximately log concave distribution. We also consider in detail the case when the “amount of non-convexity” decays towards the optimum of the function. Other applications of the method discussed in this work include private computation of empirical risk minimizers, two-stage stochastic programming, and approximate dynamic programming for online learning.