More Like this

1. Analog Joint Source-Channel Coding for Distributed Functional Compression using Deep Neural Networks

   https://doi.org/10.1109/ISIT45174.2021.9517797  

   Saidutta, Yashas Malur ; Abdi, Afshin ; Fekri, Faramarz ( July 2021 , IEEE International Symposium on Information Theory)

   null (Ed.)

   In this paper, we study Joint Source-Channel Coding (JSCC) for distributed analog functional compression over both Gaussian Multiple Access Channel (MAC) and AWGN channels. Notably, we propose a deep neural network based solution for learning encoders and decoders. We propose three methods of increasing performance. The first one frames the problem as an autoencoder; the second one incorporates the power constraint in the objective by using a Lagrange multiplier; the third method derives the objective from the information bottleneck principle. We show that all proposed methods are variational approximations to upper bounds on the indirect rate-distortion problem’s minimization objective. Further, we show that the third method is the variational approximation of a tighter upper bound compared to the other two. Finally, we show empirical performance results for image classification. We compare with existing work and showcase the performance improvement yielded by the proposed methods. 

   more » « less
2. A faster algorithm for the constrained minimum covering circle problem to expedite solving p ‐center problems in an irregularly shaped area with holes

   https://doi.org/10.1002/nav.22023  

   Liu, Yanchao ( September 2021 , Naval Research Logistics (NRL))

   This paper introduces several means to expedite a known Voronoi heuristic method for solving a continuousp‐center location problem, which is to cover a polygon withpcircles such that no circle's center lies outside the polygon, no circle's center drops inside a polygonal hole, and the radius of the largest circle is as small as possible. A key step in the Voronoi heuristic is the repeated task of determining the constrained minimum covering circle (CMCC), but the best‐known method for this task is brute‐force and inefficient. This paper develops an improved method by exploiting the convexity of a related subproblem and employing an optimized search procedure. The algorithmic enhancements help to drastically reduce the effort required for finding the CMCC, and in turn, significantly expedite the solution of thep‐center problem. On a realistic‐scale test case, the proposed algorithm ran 400× faster than the literature benchmark.

    

   more » « less
3. A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem

   Jiang, Ruichen ; Abolfazli, Nazanin ; Mokhtari, Aryan ; Yazdandoost Hamedani, Erfan ( April 2023 , Proceedings of Machine Learning Research)

   Ruiz, Francisco ; Dy, Jennifer ; van de Meent, Jan-Willem (Ed.)

   In this paper, we study a class of bilevel optimization problems, also known as simple bilevel optimization, where we minimize a smooth objective function over the optimal solution set of another convex constrained optimization problem. Several iterative methods have been developed for tackling this class of problems. Alas, their convergence guarantees are either asymptotic for the upper-level objective, or the convergence rates are slow and sub-optimal. To address this issue, in this paper, we introduce a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane and then runs a conditional gradient update to decrease the upper-level objective. When the upper-level objective is convex, we show that our method requires ${O}(\max\{1/\epsilon_f,1/\epsilon_g\})$ iterations to find a solution that is $\epsilon_f$-optimal for the upper-level objective and $\epsilon_g$-optimal for the lower-level objective. Moreover, when the upper-level objective is non-convex, our method requires ${O}(\max\{1/\epsilon_f^2,1/(\epsilon_f\epsilon_g)\})$ iterations to find an $(\epsilon_f,\epsilon_g)$-optimal solution. We also prove stronger convergence guarantees under the Holderian error bound assumption on the lower-level problem. To the best of our knowledge, our method achieves the best-known iteration complexity for the considered class of bilevel problems. 

   more » « less
4. A real‐valued auction algorithm for optimal transport

   https://doi.org/10.1002/sam.11443  

   Walsh, III, Joseph D. ; Dieci, Luca ( November 2019 , Statistical Analysis and Data Mining: The ASA Data Science Journal)

   Optimal transportation theory is an area of mathematics with real‐world applications in fields ranging from economics to optimal control to machine learning. We propose a new algorithm for solving discrete transport (network flow) problems, based on classical auction methods. Auction methods were originally developed as an alternative to the Hungarian method for the assignment problem, so the classic auction‐based algorithms solve integer‐valued optimal transport by converting such problems into assignment problems. The general transport auction method we propose works directly on real‐valued transport problems. Our results prove termination, bound the transport error, and relate our algorithm to the classic algorithms of Bertsekas and Castañón.

    

   more » « less
5. On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation

   Kwon, Jeongyeol ; Kwon, Dohyun ; Wright, Stephen ; Nowak, Robert D ( January 2024 , International Conference on Learning Representations)

   In this work, we study first-order algorithms for solving Bilevel Optimization (BO) where the objective functions are smooth but possibly nonconvex in both levels and the variables are restricted to closed convex sets. As a first step, we study the landscape of BO through the lens of penalty methods, in which the upper- and lower-level objectives are combined in a weighted sum with penalty parameter . In particular, we establish a strong connection between the penalty function and the hyper-objective by explicitly characterizing the conditions under which the values and derivatives of the two must be -close. A by-product of our analysis is the explicit formula for the gradient of hyper-objective when the lower-level problem has multiple solutions under minimal conditions, which could be of independent interest. Next, viewing the penalty formulation as -approximation of the original BO, we propose first-order algorithms that find an -stationary solution by optimizing the penalty formulation with . When the perturbed lower-level problem uniformly satisfies the {\it small-error} proximal error-bound (EB) condition, we propose a first-order algorithm that converges to an -stationary point of the penalty function using in total accesses to first-order stochastic gradient oracles. Under an additional assumption on stochastic oracles, we show that the algorithm can be implemented in a fully {\it single-loop} manner, {\it i.e.,} with samples per iteration, and achieves the improved oracle-complexity of . 

   more » « less