More Like this

1. Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization

   Sadeghi, Omid ; Fazel, Maryam ( January 2023 , Proceedings of SIAM Conference on Applied and Computational Discrete Algorithms)

   Berry, Jonathan ; Shmoys, David ; Cowen, Lenore ; Naumann, Uwe (Ed.)

   Continuous DR-submodular functions are a class of functions that satisfy the Diminishing Returns (DR) property, which implies that they are concave along non-negative directions. Existing works have studied monotone continuous DR-submodular maximization subject to a convex constraint and have proposed efficient algorithms with approximation guarantees. However, in many applications, e. g., computing the stability number of a graph and mean-field inference for probabilistic log-submodular models, the DR-submodular function has the additional property of being strongly concave along non-negative directions that could be utilized for obtaining faster convergence rates. In this paper, we first introduce and characterize the class of strongly DR-submodular functions and show how such a property implies strong concavity along non-negative directions. Then, we study L-smooth monotone strongly DR-submodular functions that have bounded curvature, and we show how to exploit such additional structure to obtain algorithms with improved approximation guarantees and faster convergence rates for the maximization problem. In particular, we propose the SDRFW algorithm that matches the provably optimal approximation ratio after only iterations, where c ∈ [0,1] and μ ≥ 0 are the curvature and the strong DR-submodularity parameter. Furthermore, we study the Projected Gradient Ascent (PGA) method for this problem and provide a refined analysis of the algorithm with an improved approximation ratio (compared to ½ in prior works) and a linear convergence rate. Given that both algorithms require knowledge of the smoothness parameter L, we provide a novel characterization of L for DR-submodular functions showing that in many cases, computing L could be formulated as a convex optimization problem, i. e., a geometric program, that could be solved efficiently. Experimental results illustrate and validate the efficiency and effectiveness of our algorithms. 

   more » « less
2. Tectonic advection of contacts enhances landscape transience

   https://doi.org/10.1002/esp.5559  

   Mitchell, Nate ; Forte, Adam M. ( February 2023 , Earth Surface Processes and Landforms)

   Contrasts in bedrock erodibility have been shown to drive landscape transience, but it is unclear whether horizontal tectonic displacements would enhance such effects. Furthermore, one might expect these factors to coexist, as tectonic convergence helps to create rock strength contrasts in settings like the Himalayas. How do landscapes respond when contacts separating units are raised vertically and shifted horizontally by tectonics? To evaluate such questions, we use landscape evolution models to simulate the exposure of a weak unit in a landscape equilibrated to a strong unit. We explore different simulations varying factors like weak unit erodibility, diffusivity, contact dip, and topographic advection rate. In these simulations, we assess the migration of the main drainage divide as well as changes in channel steepness and topographic relief within the strong unit. Our model results show that the horizontal movement of a contact does enhance drainage divide migration and increases in channel steepness, especially when the contact migrates along rivers with low drainage areas. Across all simulations, however, increases in topographic relief are minimal and temporary. Unexpected behaviors emerge in our simulations in which the mass balance of topography is influenced by horizontal tectonic displacements. For example, the exposure of the weak unit causes a gradual decline in the steepness of the strong unit. We interpret such behaviors to be artifacts related to the fixed boundaries of our domain and likely unrepresentative of natural landscapes. Instead, we focus on simulations where advection does not influence the mass balance of topography. These models show that the horizontal movement of contacts can enhance landscape transience, but this transience is marked by features one can use as diagnostic characteristics. Detecting such characteristics in natural landscapes featuring tectonic convergence would be difficult, however, due to the natural coincidence of factors such as faulting, folding, and landslides.

    

   more » « less
3. A Converse to Banach's Fixed Point Theorem and its CLS Completeness

   Daskalakis, Constantinos ; Tzamos, Christos ; Zampetakis, Manolis ( January 2018 , 50th Annual ACM Symposium on the Theory of Computing)

   Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games. 

   more » « less
4. A Converse to Banach's Fixed Point Theorem and its CLS Completeness

   Daskalakis, Constantinos ; Tzamos, Christos ; Zampetakis, Manolis ( June 2018 , Proceedings of the annual ACM Symposium on Theory of Computing)

   Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games. 

   more » « less
5. Impact of Atmospheric Circulation Variability on U.S. Midwest Moisture Sources

   https://doi.org/10.1175/JCLI-D-23-0178.1  

   Carr, Theo ; Ummenhofer, Caroline C. ( January 2024 , Journal of Climate)

   Elevated spring and summer rainfall in the U.S. Midwest is often associated with a strong Great Plains low-level jet (GPLLJ), which transports moist air northward to the region from the Gulf of Mexico. While the intensity of hourly precipitation extremes depends on local moisture availability and vertical velocity, sustained moisture convergence on longer time scales depends on horizontal moisture advection from remote sources. Therefore, the magnitude of moisture convergence in the Midwest depends in part on the humidity in these moisture source regions. Past work has identified the time-mean spatial distribution of moisture sources for the Midwest and studied how this pattern changes in years with anomalous rainfall. Here, using reanalysis products and an Eulerian moisture tracking model, we seek to increase physical understanding of this moisture source variability by linking it to the GPLLJ, which has been studied extensively. We find that on interannual time scales, an anomalously strong GPLLJ is associated with a shift in the distribution of moisture sources from land to ocean, with most of the anomalous moisture transported to—and converged in—the Midwest originating from the Atlantic Ocean. This effect is more pronounced on synoptic time scales, when almost all anomalous moisture transported to the region originates over the ocean. We also show that the observed positive trend in oceanic moisture contribution to the Midwest from 1979 to 2020 is consistent with a strengthening of the GPLLJ over the same period. We conclude by outlining how projected changes in a region’s upstream moisture sources may be useful for understanding changes in local precipitation variability.

   In this work, we study how the origin of moisture that forms precipitation in the U.S. Midwest covaries with large-scale atmospheric circulation. Our results show that an intensification of the mean winds tends to increase the proportion of total rainfall that originates from the ocean. This analysis may help to constrain future projections of rainfall extremes in the central United States, as projected changes in humidity over the ocean are typically more robust and better understood than those over land.

    

   more » « less