Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimizing Star-Convex Functions
63
0
0.0
(
0
)
Added by
Jasper C.H. Lee
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce a polynomial time algorithm for optimizing the class of star-convex functions, under no restrictions except boundedness on a region about the origin, and Lebesgue measurability. The algorithms performance is polynomial in the requested number of digits of accuracy, contrasting with the previous best known algorithm of Nesterov and Polyak that has exponential dependence, and that further requires Lipschitz second differentiability of the function, but has milder dependence on the dimension of the domain. Star-convex functions constitute a rich class of functions generalizing convex functions to new parameter regimes, and which confound standard variants of gradient descent; more generally, we construct a family of star-convex functions where gradient-based algorithms provably give no information about the location of the global optimum. We introduce a new randomized algorithm for finding cutting planes based only on function evaluations, where, counterintuitively, the algorithm must look outside the feasible region to discover the structure of the star-convex function that lets it compute the next cut of the feasible region. We emphasize that the class of star-convex functions we consider is as unrestricted as possible: the class of Lebesgue measurable star-convex functions has theoretical appeal, introducing to the domain of polynomial-time algorithms a huge class with many interesting pathologies. We view our results as a step forward in understanding the scope of optimization techniques beyond the garden of convex optimization and local gradient-based methods.
rate research
Read More
Given a separation oracle $mathsf{SO}$ for a convex function $f$ that has an integral minimizer inside a box with radius $R$, we show how to find an exact minimizer of $f$ using at most (a) $O(n (n + log(R)))$ calls to $mathsf{SO}$ and $mathsf{poly}(n, log(R))$ arithmetic operations, or (b) $O(n log(nR))$ calls to $mathsf{SO}$ and $exp(n) cdot mathsf{poly}(log(R))$ arithmetic operations. When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of $f$. This improves upon the previously best oracle complexity of $O(n^2 (n + log(R)))$ for polynomial time algorithms obtained by [Grotschel, Lovasz and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most $O(n^3)$ calls to an evaluation oracle, and an exponential time algorithm that makes at most $O(n^2 log(n))$ calls to an evaluation oracle. These improve upon the previously best $O(n^3 log^2(n))$ oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Vegh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity $O(n^3 log(n))$ given in the former work. Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We show how an approximately shortest vector of certain lattice can be used to effectively reduce the dimension of the problem. Our analysis of the oracle complexity is based on a potential function that captures simultaneously the size of the search set and the density of the lattice, which we analyze via technical tools from convex geometry.
Arithmetic automata recognize infinite words of digits denoting decompositions of real and integer vectors. These automata are known expressive and efficient enough to represent the whole set of solutions of complex linear constraints combining both integral and real variables. In this paper, the closed convex hull of arithmetic automata is proved rational polyhedral. Moreover an algorithm computing the linear constraints defining these convex set is provided. Such an algorithm is useful for effectively extracting geometrical properties of the whole set of solutions of complex constraints symbolically represented by arithmetic automata.
We analyze a class of sublinear functionals which characterize the interior and the exterior of a convex cone in a normed linear space.
Coreset is usually a small weighted subset of $n$ input points in $mathbb{R}^d$, that provably approximates their loss function for a given set of queries (models, classifiers, etc.). Coresets become increasingly common in machine learning since existing heuristics or inefficient algorithms may be improved by running them possibly many times on the small coreset that can be maintained for streaming distributed data. Coresets can be obtained by sensitivity (importance) sampling, where its size is proportional to the total sum of sensitivities. Unfortunately, computing the sensitivity of each point is problem dependent and may be harder to compute than the original optimization problem at hand. We suggest a generic framework for computing sensitivities (and thus coresets) for wide family of loss functions which we call near-convex functions. This is by suggesting the $f$-SVD factorization that generalizes the SVD factorization of matrices to functions. Example applications include coresets that are either new or significantly improves previous results, such as SVM, Logistic regression, M-estimators, and $ell_z$-regression. Experimental results and open source are also provided.
Joint operation of power, water, and heating networks is expected to improve overall efficiency of infrastructure while also known as a challenging problem, due to complex couplings of electric, hydraulic, and thermal models that are nonlinear and nonconvex. We formulate an optimal power-water-heat flow (OPWHF) problem and develop a computationally efficient and privacy preserving heuristic to solve it. The proposed heuristic decomposes OPWHF into subproblems, which are solved via convex relaxation and convex-concave procedure while iteratively exchanging information to reach consensus on coupling variables. Simulation results validate that the joint optimization can improve operational flexibility and social welfare of the interconnected system, wherein the water and heating networks respond to time-varying electricity price and electric load as virtual energy storage. We also compare two modes of heating network control: by flow rate and by temperature; case studies reveal that the latter is more effective for most practical systems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
