Search

Many applications require minimizing a family of optimization problems indexed by some hyperparameter $\lambda \in \Lambda$ to obtain an entire solution path. Traditional approaches proceed by discretizing $\Lambda$ and solving a series of optimization problems. We propose an alternative approach that parameterizes the solution path with a set of basis functions and solves a \emph{single} stochastic optimization problem to learn the entire solution path. Our method offers substantial complexity improvements over discretization. When using constant-step size SGD, the uniform error of our learned solution path relative to the true path exhibits linear convergence to a constant related to the expressiveness of the basis. When the true solution path lies in the span of the basis, this constant is zero. We also prove stronger results for special cases common in machine learning: When $\lambda \in [-1, 1]$ and the solution path is $\nu$-times differentiable, constant step-size SGD learns a path with $\epsilon$ uniform error after at most $O(\epsilon^{\frac{1}{1-\nu}} \log(1/\epsilon))$ iterations, and when the solution path is analytic, it only requires $O\left(\log^2(1/\epsilon)\log\log(1/\epsilon)\right)$. By comparison, the best-known discretization schemes in these settings require at least $O(\epsilon^{-1/2})$ discretization points (and even more gradient calls). Finally, we propose an adaptive variant of our method that sequentially adds basis functions and demonstrates strong numerical performance through experiments.

In this paper, we study a question of Hong from 1993 related to the minimum spectral radii of the adjacency matrices of connected graphs of given order and size. Hong asked if it is true that among all connected graphs of given number of vertices $n$ and number of edges $e$, the graphs having minimum spectral radius (the minimizer graphs) must be almost regular, meaning that the difference between their maximum degree and their minimum degree is at most one. In this paper, we answer Hong's question positively for various values of $n$ and $e$ and in several cases, we determined the graphs with minimum spectral radius., Comment: 22 pages, 6 figures, revised paper taking into consideration the comments from the referees

In this paper, we introduce a new notion of curvature on the edges of a graph that is defined in terms of effective resistances. We call this the Ricci--Foster curvature. We study the Ricci flow resulting from this curvature. We prove the existence of solutions to Ricci flow on short time intervals, and prove that Ricci flow preserves graphs with nonnegative (resp. positive) curvature., Comment: 14 pages, 8 figures, comments welcome!

Devriendt and Lambiotte recently introduced the \emph{node resistance curvature}, a notion of graph curvature based on the effective resistance matrix. In this paper, we begin the study of the behavior of the node resistance curvature under the operation of the Cartesian graph product. We study the natural question of global positivity of node resistance curvature of the Cartesian product of positively-curved graphs, and prove that, whenever $m,n\ge3$, the node resistance curvature of the interior vertices of a $m\times n$ grid is always nonpositive, while it is always nonnegative on the boundary of such grids. For completeness, we also prove a number of results on node resistance curvature in $2\times n$ grids and exhibit a counterexample to a generalization. We also give generic bounds and suggest several further questions for future study.

We propose a novel family of decision-aware surrogate losses, called Perturbation Gradient (PG) losses, for the predict-then-optimize framework. The key idea is to connect the expected downstream decision loss with the directional derivative of a particular plug-in objective, and then approximate this derivative using zeroth order gradient techniques. Unlike the original decision loss which is typically piecewise constant and discontinuous, our new PG losses is a Lipschitz continuous, difference of concave functions that can be optimized using off-the-shelf gradient-based methods. Most importantly, unlike existing surrogate losses, the approximation error of our PG losses vanishes as the number of samples grows. Hence, optimizing our surrogate loss yields a best-in-class policy asymptotically, even in misspecified settings. This is the first such result in misspecified settings, and we provide numerical evidence confirming our PG losses substantively outperform existing proposals when the underlying model is misspecified.

We consider a personalized pricing problem in which we have data consisting of feature information, historical pricing decisions, and binary realized demand. The goal is to perform off-policy evaluation for a new personalized pricing policy that maps features to prices. Methods based on inverse propensity weighting (including doubly robust methods) for off-policy evaluation may perform poorly when the logging policy has little exploration or is deterministic, which is common in pricing applications. Building on the balanced policy evaluation framework of Kallus (2018), we propose a new approach tailored to pricing applications. The key idea is to compute an estimate that minimizes the worst-case mean squared error or maximizes a worst-case lower bound on policy performance, where in both cases the worst-case is taken with respect to a set of possible revenue functions. We establish theoretical convergence guarantees and empirically demonstrate the advantage of our approach using a real-world pricing dataset.