-
作者：Piccialli, Veronica; Schwiddessen, Jan; Sudoso, Antonio M.
作者单位：Sapienza University Rome; University of Klagenfurt
摘要：Support vector machines (SVMs) are well-studied supervised learning models for binary classification. Large amounts of samples can be cheaply and easily obtained in many applications. What is often a costly and error-prone process is to label these data points manually. Semi-supervised support vector machines (S3VMs) extend the well-known SVM classifiers to the semi-supervised approach, aiming to maximize the margin between samples in the presence of unlabeled data. By leveraging both labeled ...
-
作者：Mirka, Renee; Smedira, Devin; Williamson, David P.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger et al. (J ACM 45(2):246-265, 1998) give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optima...
-
作者：Hunkenschroeder, Christoph
作者单位：Technical University of Berlin
摘要：We show that the problem of deciding whether a given Euclidean lattice L has an orthonormal basis is in NP and co-NP. Since this is equivalent to saying that L is isomorphic to the standard integer lattice, this problem is a special form of the lattice isomorphism problem, which is known to be in the complexity class SZK. We achieve this by deploying a result on characteristic vectors by Elkies that gained attention in the context of 4-manifolds and Seiberg-Witten equations, but seems rather u...
-
作者：Tian, Lai; So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong
摘要：We consider the oracle complexity of computing an approximate stationary point of a Lipschitz function. When the function is smooth, it is well known that the simple deterministic gradient method has finite dimension-free oracle complexity. However, when the function can be nonsmooth, it is only recently that a randomized algorithm with finite dimension-free oracle complexity has been developed. In this paper, we show that no deterministic algorithm can do the same. Moreover, even without the ...
-
作者：Kannan, Rohit; Bayraksan, Guezin; Luedtke, James R.
作者单位：Virginia Polytechnic Institute & State University; University System of Ohio; Ohio State University; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained using Wasserstein, sample robust optimization, and phi-divergence-based ambiguity sets within ...
-
作者：Joyce, Alexander; Yang, Boshi
作者单位：Clemson University
摘要：Let F subset of R-n be a nonempty closed set. Understanding the structure of the closed convex hull (C) over bar (F) := <(conv{over bar>{( x, xx(T))|x is an element of F} in the lifted space is crucial for solving quadratic programs related to F. This paper discusses the relationship between C(F) and (C) over bar (G), where G results by adding non-intersecting quadratic constraints to F. We prove that C(G) can be represented as the intersection of C(F) and half spaces defined by the added cons...
-
作者：Guenin, Bertrand; Heo, Cheolwon
作者单位：University of Waterloo; Korea Institute for Advanced Study (KIAS)
摘要：Even-cycle matroids are elementary lifts of graphic matroids. An even-cycle matroid is pinch-graphic if it has a signed-graph representation with a blocking pair. We present a polynomial algorithm to check if an internally 4-connected binary matroid is pinch-graphic. Combining this with a result in Guenin and Heo (Small separations in pinch-graphic matroids. Math Program (2023). https://doi.org/10.1007/s10107-023-01950-8) this allows us to check, in polynomial time, if an arbitrary binary matr...
-
作者：Lodi, Andrea; Olivier, Philippe; Pesant, Gilles; Sankaranarayanan, Sriram
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal; Indian Institute of Management (IIM System); Indian Institute of Management Ahmedabad
摘要：Decision making problems are typically concerned with maximizing efficiency. In contrast, we address problems where there are multiple stakeholders and a centralized decision maker who is obliged to decide in a fair manner. Different decisions give different utility to each stakeholder. In cases where these decisions are made repeatedly, we provide efficient mathematical programming formulations to identify both the maximum fairness possible and the decisions that improve fairness over time, f...
-
作者：Sanchez-Fernandez, Luis; Fernandez-Garcia, Norberto; Fisteus, Jesus A.; Brill, Markus
作者单位：Universidad Carlos III de Madrid; Universidad Carlos III de Madrid; Technical University of Berlin
摘要：We propose the maximin support method, a novel extension of the D'Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the voter support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D'Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relat...
-
作者：Aardal, Karen; Sanita, Laura
作者单位：Delft University of Technology; Bocconi University
