-
作者：Ahookhosh, Masoud; Nesterov, Yurii
作者单位：University of Antwerp
摘要：We introduce a Bi-level OPTimization (BiOPT) framework for minimizing the sum of two convex functions, where one of them is smooth enough. The BiOPT framework offers three levels of freedom: (i) choosing the order p of the proximal term; (ii) designing an inexact pth-order proximal-point method in the upper level; (iii) solving the auxiliary problem with a lower-level non-Euclidean method in the lower level. We here regularize the objective by a (p+1)\documentclass[12pt]{minimal} \usepackage{a...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
摘要：A vector is dyadic if each of its entries is a dyadic rational number, i.e. of the form (a)/(2)k for some integers a, k with k = 0. A linear system Ax = b with integral data is totally dual dyadic if whenever min{b(T)y : A(T)y = w, y = 0J for w integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of dyadic generating sets for cones and subspaces, the former being the dyadic analogue ...
-
作者：Averkov, Gennadiy; Schymura, Matthias
作者单位：Brandenburg University of Technology Cottbus
摘要：We study the maximal number of pairwise distinct columns in a ?-modular integer matrix with m rows. Recent results by Lee et al. provide an asymptotically tight upper bound of O (m(2)) for fixed ?. We complement this and obtain an upper bound of the form O(?) for fixed m, and with the implied constant depending polynomially on m.
-
作者：Shafiee, Soroosh; Kilinc-Karzan, Fatma
作者单位：Cornell University; Carnegie Mellon University
摘要：Optimization problems involving minimization of a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. These problems are often modeled with indicator variables for identifying the support of the continuous variables. In this paper we investigate compact extended formulations for such problems through perspective reformulation techniques. In contrast to the majority of previous work that relies...
-
作者：Rieger, Alon; Segev, Danny
作者单位：Tel Aviv University
摘要：In spite of its widespread applicability in learning theory, probability, combinatorics, and in various other fields, the Mallows model has only recently been examined from revenue management perspectives. To our knowledge, the only provably-good approaches for assortment optimization under the Mallows model have recently been proposed by Desir et al. (Oper Res 69(4):1206-1227, 2021), who devised three approximation schemes that operate in very specific circumstances. Unfortunately, these algo...
-
作者：Mertikopoulos, Panayotis; Hsieh, Ya-Ping; Cevher, Volkan
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria
摘要：We develop a flexible stochastic approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite). The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, the exponential/multiplicative weights algorithm for learning in finite games, optimistic and bandit variants of the above, etc. In addition to providing an integrated view of these algorithms, our framework further allows us to ob...
-
作者：Chen, Hua; Chen, Lin; Zhang, Guochuan
作者单位：Zhejiang University; Texas Tech University System; Texas Tech University
摘要：In this paper, a special case of the generalized 4-block n-fold IPs is investigated, where B-i = B and B has a rank at most 1. Such IPs, called almost combinatorial 4-block n-fold IPs, include the generalized n-fold IPs as a subcase. We are interested in fixed parameter tractable (FPT) algorithms by taking as parameters the dimensions of the blocks and the largest coefficient. For almost combinatorial 4-block n-fold IPs, we first show that there exists some lambda <= g(gamma ) such that for an...
-
作者：Davis, Damek; Drusvyatskiy, Dmitriy; Charisopoulos, Vasileios
作者单位：Cornell University; University of Washington; University of Washington Seattle
摘要：Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of s...
-
作者：Paquette, Courtney; Paquette, Elliot; Adlam, Ben; Pennington, Jeffrey
作者单位：McGill University; Alphabet Inc.; DeepMind
摘要：We develop a stochastic differential equation, called homogenized SGD, for analyzing the dynamics of stochastic gradient descent (SGD) on a high-dimensional random least squares problem with l(2)-regularization. We show that homogenized SGD is the high-dimensional equivalence of SGD-for any quadratic statistic (e.g., population risk with quadratic loss), the statistic under the iterates of SGD converges to the statistic under homogenized SGD when the number of samples n and number of features ...
-
作者：Matuschke, Jannik
作者单位：KU Leuven
摘要：Given a set system (E,P)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(E, \mathcal {P})$$\end{document} with rho is an element of[0,1]E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \...
